constellation

A grid geometry toolkit for controlling 2D sprite motion.

npm install constellation
2 downloads in the last week
4 downloads in the last month

Constellation.js

A grid geometry toolkit for controlling 2D sprite motion.

Constellation manages 2D point grids and pathfinding navigation. The library is designed to control dynamic sprite motion within a 2D environment. Constellation expands upon the motion system used in the What Makes You Tick? adventure game series. Features include:

  • Point and polygon grid management.
  • Pathfinding with A-star.
  • Polygon hit testing with ray-scan.
  • Snapping points to line segments.
  • Optimized nearest-point searching.
  • Dynamic point-to-point bridges via grid geometry.

For a grid builder demo, see lassiegames.com/constellation

Const

Constellation root scope provides basic geometry operations and geometric primitives. All of these methods may be called directly on the Const namespace, and are passed simple arrays and/or Constellation primitives (Point & Rect).

Const.Point var point = new Const.Point( x, y );
Constellation point primitive. Const.Point objects have the following properties:

  • x: horizontal coordinate of the point.
  • y: vertical coordinate of the point.

Const.Rect var rect = new Const.Rect( x, y, width, height );
Constellation rectangle primitive. Const.Rect objects have the following properties:

  • x: horizontal coordinate of the rectangle origin.
  • y: vertical coordinate of the rectangle origin.
  • width: rectangle width.
  • height: rectangle height.

Const.distance var result = Const.distance( point1, point2 );
Calculates the distance between two provided Const.Point objects.

Const.ccw var result = Const.ccw( point1, point2, point3, exclusive? );
Tests for counter-clockwise winding among three Const.Point objects. Returns true if the three points trend in a counter-clockwise arc. Useful for intersection tests. Passing true for the optional exclusive param will pass balanced arcs.

Const.intersect var result = Const.intersect( pointA, pointB, pointC, pointD );
Tests for intersection between line segments AB and CD. Returns true if the line segments intersect.

Const.getRectForPointRing var result = Const.getRectForPointRing( [points] );
Takes an array of Const.Point objects; returns a Const.Rect object of their bounding box.

Const.hitTestRect var result = Const.getRectForPointRing( pointP, rect );
Takes a target point P and a rectangle object; returns true if the point falls within the rectangle.

Const.hitTestPointRing var result = Const.hitTestPointRing( pointP, [points] );
Takes a target point P and an array of points defining a ring. Returns true if P falls within the ring of points. Hit test is performed using the ray-casting method.

Const.snapPointToLineSegment var result = Const.snapPointToLineSegment( pointP, pointA, pointB );
Takes a target point P, and snaps it to the nearest point along line segment AB.

Const.getNearestPointToPoint var result = Const.getNearestPointToPoint( pointP, [points] );
Takes a target point P, and an array of points to search. Returns the nearest point to P within the point collection.

Const.Grid

Constellation Grid must be instanced.

Const.Grid var grid = new Const.Grid( data? );
Constructor for a new Constellation grid. All grid operations must be invoked on an instance.

Grid.Node use... grid.addNode();
Constellation grid Node object; use a Grid instance to create and manage nodes. Grid nodes have the following properties:

  • id: unique identifier for the node. Don't touch this.
  • x: horizontal coordinate of the node.
  • y: vertical coordinate of the node.
  • to: Table of connections to other nodes. Seriously, don't touch this.
  • data: A data object of user-defined data attached to the node.

Grid.Polygon use... grid.addPolygon();
Constellation grid Polygon object; use a Grid instance to create and manage polygons. Grid polygons have the following properties:

  • id: unique identifier for the node. Don't touch this.
  • nodes: Array of node ids defining the polygon ring.
  • data: A data object of user-defined data attached to the polygon.

grid.addNode grid.addNode( x, y, {data}? ); or grid.addNode( {data}? );
Adds a new Node object with specified X and Y coordinates, and an optional data object. Returns a reference to the new Node object. A data object may be provided as the sole parameter, if the data object contains an id property, that id will be assigned to the new node.

grid.getNodeById grid.getNodeById( id );
Gets a node by id reference. Returns a Node object, or null for missing ids.

grid.getNodes grid.getNodes( id, ... ); or grid.getNodes( [id, ...] );
Gets one or more grid nodes by id reference, or maps an array of grid nodes to an array of ids. Returns an array of Node objects. Invalid ids return as null.

grid.getNumNodes grid.getNumNodes();
Specifies the number of nodes in the grid.

grid.hasNodes grid.hasNodes( id, ... ); or grid.hasNodes( [id, ...] );
Tests if one or more node ids, or an array of node ids, exists within the grid.

grid.joinNodes grid.joinNodes( id1, id2, ... ); or grid.joinNodes( [id1, id2, ...] );
Takes two or more node ids, or an array with two or more node ids, and joins them with connections. Returns true if changes are made.

grid.splitNodes grid.splitNodes( id1, id2, ... ); or grid.splitNodes( [id1, id2, ...] );
Takes two or more node ids, or an array with two or more node ids, and splits apart their common connections. Returns true if changes are made.

grid.detachNodes grid.detachNodes( id, ... ); or grid.detachNodes( [id, ...] );
Takes one or more node ids, or an array of node ids, and splits them from all of their respective connections. Returns true if changes are made.

grid.removeNodes grid.removeNodes( id, ... ); or grid.removeNodes( [id, ...] );
Takes one or more node ids, or an array of node ids, detaches them from all connections, then removes them each from the grid. Any dependent polygons are also removed. Returns true if changes are made.

grid.addPolygon grid.addPolygon( [node ids], data? );
Takes an array of three or more node ids and creates a new Polygon object with the optional data object attached. Returns a reference to the new Polygon object.

grid.getPolygonById grid.getPolygonById( id );
Gets a polygon by id reference. Returns a Polygon object, or null for missing ids.

grid.getPolygons grid.getPolygons( id, ... ); or grid.getPolygons( [id, ...] );
Gets one or more polygons by id reference, or maps an array of polygons to an array of ids. Returns an array of Polygon objects. Invalid ids return as null.

grid.getNodesForPolygon grid.getNodesForPolygon( id );
Takes a polygon id and returns an array of Node objects defining its polygon ring. Returns null if the specified polygon id is undefined.

grid.getNumPolygons grid.getNumPolygons();
Specifies the number of polygons in the grid.

grid.removePolygons grid.removePolygons( id, ... ); or grid.removePolygons( [id, ...] );
Takes an array of polygon ids and removes them from the grid. All nodes defining the polygon rings are left intact. Pass true as the optional second argument to perform changes silently without triggering an update event. Returns true if changes are made.

grid.findPath grid.findPath( startId, goalId, weightFunction?, estimateFunction? );
Takes two node ids defining start and goal nodes, then finds the shortest path between them. By default, routing favors the shortest path based on coordinate geometry. However, you may customize path routing using the optional weight and estimate functions:

  • weightFunction: function( startNode, currentNode ) { return numericCost; }
    This function is used to calculate the weight (or cost) of each new grid segment added to a path. The function is provided two Grid.Nodes as arguments, and expects a numeric segment weight to be returned. The pathfinder returns a path that accrues the lowest total weight. By default, Const.distance is used to measure the weight of each segment.

  • estimateFunction: function( currentNode, goalNode ) { return numericEstimate; }
    This function optimizes search performance by providing a best-case scenario estimate for each node's cost to reach the goal. This function is provided two Grid.Node objects as arguments: the current search node, and the goal node. An estimated cost-to-goal value should be returned. By default, Const.distance is used to estimate the best-case distance from a working path to the goal.

grid.findPathWithFewestNodes grid.findPathWithFewestNodes( startId, goalId );
Convenience method for running grid.findPath configured to find a path to goal using the fewest node connections rather than the shortest distance.

grid.snapPointToGrid grid.snapPointToGrid( point );
Snaps the provided point to the nearest position among all joined line segments within the node grid. The snapped point will be plotted at the nearest available line segment, or the nearest grid point if no line segments are defined. Returns a meta object with the following attributes:

  • point: the snapped Point object.
  • offset: the snapped offset distance from the original point.
  • segment: an array of node ids defining the line segment on which the point was snapped.

grid.bridgePoints grid.bridgePoints( startPt, goalPt, confineToGrid? );
Creates a grid path bridging between two Point objects that are not connected to the grid. This is a composite operation intended to take two dynamic input locations, and intelligently connect them through the existing grid structure. The steps of this algorithm operate as follows:

  1. Test if start and goal are contained within a common polygon; if so, return a direction-connection array specifying: [start, goal].

  2. (...not yet implemented...) Test if points fall within adjacent polygons, and if they may be connected directly through the common side.

  3. Dynamically join start and goal points into the motion grid, then run pathfinder. Dynamic point inclusion works as follows:

    • If start or goal points fall within a polygon, then they'll be connected to their encompassing polygons' node rings.

    • Otherwise, start and goal points will create tether nodes that snap and join to the grid.

The bridgePoints method will always return an array of point objects starting with the originally specified startPt. The array will also contain additional path positions, and finally the goalPt. Optionally, you may specify confineToGrid as true, at which time the goalPt will be adjusted to either fall within a polygon area or snap to a grid line.

grid.getNearestNodeToPoint grid.getNearestNodeToPoint( point );
Finds and returns the closest grid Node object to the specified Point position. Performs an optimized sorted search rather than brute-force distance comparisons.

grid.getNearestNodeToNode grid.getNearestNodeToNode( id );
Finds the next closest grid node to the specified node id. Similar to getNearestNodeToPoint, except that the input is a node id rather than a point object.

grid.hitTestPointInPolygons grid.hitTestPointInPolygons( point );
Returns true if the provided point intersects any Polygon objects within the grid.

grid.getPolygonHitsForPoint grid.getPolygonHitsForPoint( point );
Tests a Point object for intersections with all Polygon objects in the grid, then returns an array of polygon ids that encompass the point.

grid.getNodesInPolygon grid.getNodesInPolygon( id );
Takes a polygon id and tests it for intersections with all nodes in the grid, then returns an array of the contained node ids. Nodes that compose the polygon's ring will be included in the returned array, even though their edge positions may fail a mathematical hit test.

grid.getNodesInRect grid.getNodesInRect( rect );
Tests a Rect object for intersections with all nodes in the grid, and returns an array of the contained node ids.

Const.utils

Constellation includes implementations of several common collection management functions for working with arrays and objects. These are very similar to Underscore.js methods, although their implementations may vary.

Const.utils.size Const.utils.size( object );
Counts the number of items in an array, or the number of properties on an object.

Const.utils.contains Const.utils.contains( object, value );
Accepts an array or object and a value to search for. Returns true if an array contains the provided value, or an object defines a key for the specified value.

Const.utils.each Const.utils.each( object, iteratorFunction, context? );
Iterates an array or object with the provided function. Iterator is passed ( value, index ) for arrays, and ( value, key ) for objects. An optional scope context may be provided in which to run the interator.

Const.utils.map Const.utils.map( object, mutatorFunction, context? );
Iterates an array or object with the provided mutator function. Mutator is passed each value, and returns a modified value to replace the original within the collection. An optional scope context may be provided in which to run the interator.

Const.utils.all Const.utils.all( array, testFunction, context? );
Iterates through the provided array and performs a test function on each value. Returns true if all values pass the test.

npm loves you