Pathfinder

The Pathfinder utility is used for the shortest path between two points. Note that there may be more than one 'shortest path', so the resulting path may not look like the prettiest solution.

Basic Usage

The Pathfinder class (and friends) can be used in both CommonJS and Browser environments.

Browser

In the Browser environment, you must include the script in your html page:

<script src='/path/to/Pathfinder.js'></script>

After the script is run, the global variable Pathfinder (window.Pathfinder) will be set. A new instance can created with the 'new' keyword:

var pf = new Pathfinder(options);

CommonJs/Node

In a CommonJS environment, such as Node.js, you can require it as a module:

var Pathfinder = require("/path/to/Pathfinder.js");

Grid and Node classes

The Grid and Node classes are members of the Pathfinder class. This way, only one global variable is created (in the Browser environment). It's easy to get references to the classes:

var Node = Pathfinder.Node;
var Grid = Pathfinder.Grid;

Or, if you prefer CoffeeScript:

{Grid, Node} = Pathfinder

The same syntax can be used with JavaScript (provided you prefix var and use a semicolon), however it seems only some/recent browsers support it (MDN, Compatibility Table)

Node Class

A Node is a location on a grid, a simple (x, y) location. Nodes also have a bit of extra information: movement cost. and "allowed neighbor movement".

To create a Node, use the static function fromObject():

var options = Node.defaultOptions(); // Get defaults (x/y are 0 and all directions of movement are allowed)
// Edit options (explained below)
var node = Node.fromObject(options)

Node.defaultOptions() returns the following object:

{
  x: 0,
  y: 0,
  up: true,
  down: true,
  left: true,
  right: true,
  topLeft: true,
  topRight: true,
  bottomLeft: true,
  bottomRight: true,
}

x and y are used to tell Pathfinder where the Node is located. When it's added to a Grid, the two values aren't checked, so be sure it matches. (If you are using a function or loop to generate the Grid, it's kinda hard to mess up)

Creating a Wall

If you haven't created the Node yet, you can:

• Set all the directions from the object returned by Node.defaultOptions() to false (which is tedious) or
• Set options.wall to true:

var options = Node.defaultOptions();
options.wall = true;
var node = Node.fromOptions(options)

If you have created the Node, you can:

• Set all directions to 'not allowed':

var dirs = Node.ALL_DIRECTIONS;
for(var i = 0; i < dirs.length; i++) {
  node.setDirectionAllowed(dirs[i], false);
}

Or, in CoffeeScript:

node.setDirectionAllowed(dir, false) for dir in Node.ALL_DIRECTIONS

• Or, give it a movement cost that you (and Pathfinder) consider 'impossible'. This depends on the size of the map/grid, but generally a really high value will do. Pathfinder will use the default of 10000 (ten thousand) if you do not specify it in the options of Pathfinder's constructor.

node.setMovementCost(25); // It costs 25 to move to this node
node.getMovementCost(); // => 25
// Note: '25' isn't exactly a high number. This is just an example to show you can set movement costs.

Grid Class

In order for Pathfinder to know where to look, you need to create a Grid. In order to create a grid, you need an array of nodes (or an empty array). The above examples show you how to make some.

var grid = new Grid(nodes, width, height)

Note:

• The contents of the array of nodes are not checked. For the best results that won't confuse anyone please be sure your array only contains Node objects.
• width and height are optional, they each have a default of 10. If you do specify them, be sure to use integers.

Setting a Specific Node

In case you created an empty Grid, or you want to change a certain node, you can use the set() function. (Conversely, the get function gets the node and the given location)

grid.set(x, y, node);

Where x and y is the location of the node, and node is the Node itself.

Finding a Path

Finally, what you really wanted to see, right? How to find the path. Well, be sure to read everything above first, because I'm going to assume you know it.

To find a path between two nodes, you will need a Grid and two Node objects, one being the start and one the goal.

// Only 'grid' is required, I simply added the other two to show their default values
var pf = new Pathfinder({grid: grid, distanceFormula: Pathfinder.MANHATTAN, impossibleCost: 10000})
var path = pf.findPath(start, goal);

• grid - This is your Grid object
• distanceFormula - This is a constant from the Pathfinder class or a function. (The explanation of each can be found in this repo's README.md)
• start - Where the Pathfinder should begin. This should be an instance of Node
• goal - Where the Pathfinder should to try go. This should be an instance of Node

The returned path is an array of Nodes, in order from start to goal. You can do whatever you want with it, such as drawing it onto a MapRenderer.