Module gamejs/pathfinding

A* path finding algorithm

Use the findRoute(map, from, to, [timeout]) function to get the linked list leading from a point to another on the given map.

The map must implement the interface gamejs.pathfinding.Map. This class already holds an example implementation for debugging use.

Optionally, the search is cancelled after timeout in millseconds.

If there is no route null is returned.

See

http://en.wikipedia.org/wiki/A*_search_algorithm
http://eloquentjavascript.net/chapter7.html

Functions

Class Map

Instance Methods


Map ()

This is the interface for a Map that can be passed to the findRoute() function. Map is not instantiable - see the unit tests for an example implementation of Map.


Map.prototype.actualDistance (pointA, pointB)

Actual distance between two points.

Parameters

Object pointA
Object pointB

Returns

Number the actual distance between two points

Map.prototype.adjacent (origin)

Parameters

Array origin

Returns

Array list of points accessible from given Point

Map.prototype.equals (a, b)

Parameters

Object a one of the points ot test for equality
Object b ... the other point

Returns

Wheter the two points are equal.

Map.prototype.estimatedDistance (pointA, pointB)

Estimated lower bound distance between two points.

Parameters

Object pointA
Object pointB

Returns

Number the estimated distance between two points

Map.prototype.hash (a)

Parameters

Object a point

Returns

String hash for the point

findRoute (map, origin, destination, timeout)

A* search function.

This function expects a Map implementation and the origin and destination points given. If there is a path between the two it will return the optimal path as a linked list. If there is no path it will return null.

The linked list is in reverse order: the first item is the destination and the path to the origin follows.

Parameters

Map map map instance, must follow interface defined in {Map}
Array origin
Array destination
Number timeout milliseconds after which search should be canceled

Returns

Object the linked list leading from `to` to `from` (sic!).