Module gamejs/pathfinding/astar
AStar 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 interface gamejs.pathfinding.Map. This class really holds an example implementation & data for you to study. If you understand what this calls provides, you understand this module.
Optionally, the search is cancelled after timeout in millseconds.
If there is no route null is returned.
See
Functions
- findRoute(map, origin, destination, timeout)
Class Map
Instance Methods
- actualDistance(pointA, pointB)
- adjacent(origin)
- equals(a, b)
- estimatedDistance(pointA, pointB)
- hash(a)
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 |
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!). |