Namespace: pathfinding

Type Aliases

KeyMapping

Ƭ KeyMapping<K, T>: (location: T) => K

A method to convert a location to a unique key. The key type must be usable in a map. This permits using the faster map lookup, while overcoming the limitations of Javascript Map comparing keys directly and not equivalently or using a method.

Type parameters

Name	Type
K	extends KeyType
T	T

Type declaration

▸ (location): K

Parameters

Name	Type
location	T

Returns

K

---

KeyType

Ƭ KeyType: string | number | symbol

---

SearchProximityHeuristic

Ƭ SearchProximityHeuristic<T>: (start: T, dest: T) => number

Used in A* search, returns the estimated distance between two points. Can safely return the euclidian or manhattan distance, ignoring walls.

As the heuristic approachs too small estimates (always 0), A* approaches Dijkstra’s algorithm.

As the heuristic approaches too large estimates (+inf), A* approaches Breadth-First-Search

Type parameters

Name
T

Type declaration

▸ (start, dest): number

Parameters

Name	Type
start	T
dest	T

Returns

number

---

SearchResult

Ƭ SearchResult<K, T>: Object

The result of searching for a path along a graph. Used with reconstructPath to produce path arrays.

If the graph state changes (ie. valid connections), then this data becomes stale. It can still be used, but may no longer produce correct paths.

If the search was unable to reach the goal, this will be flagged as incomplete.

Type parameters

Name	Type
K	extends KeyType
T	T

Type declaration

Name	Type
cameFrom	Map<K, T | undefined>
getUniqueKey	KeyMapping<K, T>
goal	T
incomplete	boolean
start	T

---

WeightedSearchResult

Ƭ WeightedSearchResult<K, T>: SearchResult<K, T> & { costs: Map<K, number> }

The result of searching for a path along a weighted graph. Used with reconstructPath to produce path arrays.

If the graph state changes (ie. valid connections or their weights), then this data becomes stale. It can still be used, but may no longer produce correct paths.

Type parameters

Name	Type
K	extends KeyType
T	T

Functions

aStarSearch

▸ aStarSearch<K, T>(graph, start, goal, getUniqueKey, heuristic): WeightedSearchResult<K, T>

A* pathfinding algorithm. Traverses a weighted graph to find the shortest path between two points.

A* uses a heuristic function to approximate the distance between a location and the goal. See SearchProximityHeuristic

This implementation requires a getUniqueKey method to convert a location to a unique key. See KeyMapping.

Type parameters

Name	Type
K	extends KeyType
T	T

Parameters

Name	Type
graph	WeightedGraph<T>
start	T
goal	T
getUniqueKey	KeyMapping<K, T>
heuristic	SearchProximityHeuristic<T>

Returns

WeightedSearchResult<K, T>

A WeightedSearchResult object, which can be passed to reconstructPath in order to get the path as an array

---

breadthFirstSearch

▸ breadthFirstSearch<K, T>(graph, start, goal, getUniqueKey): SearchResult<K, T>

Breadth-First-Search’s pathfinding algorithm. Traverses a graph to find shortest paths. Does not handle weights.

This implementation requires a getUniqueKey method to convert a location to a unique key. See KeyMapping.

Type parameters

Name	Type
K	extends KeyType
T	T

Parameters

Name	Type
graph	Graph<T>
start	T
goal	T
getUniqueKey	KeyMapping<K, T>

Returns

SearchResult<K, T>

A SearchResult object, which can be passed to reconstructPath in order to get the path as an array

---

dijkstraSearch

▸ dijkstraSearch<K, T>(graph, start, goal, getUniqueKey): WeightedSearchResult<K, T>

Dijkstra’s pathfinding algorithm. Traverses a weighted graph to find shortest paths.

This is equivalent to A* with a distance heuristic which always returns 0. See SearchProximityHeuristic

This implementation requires a getUniqueKey method to convert a location to a unique key. See KeyMapping.

Type parameters

Name	Type
K	extends KeyType
T	T

Parameters

Name	Type
graph	WeightedGraph<T>
start	T
goal	T
getUniqueKey	KeyMapping<K, T>

Returns

WeightedSearchResult<K, T>

A WeightedSearchResult object, which can be passed to reconstructPath in order to get the path as an array

---

reconstructPath

▸ reconstructPath<K, T>(searchResults): T[]

This method converts SearchResults into paths as arrays.

This approach allows reusing previously computed searches when generating paths. To do this, the start point should remain on the original path; otherwise the paths may not complete correctly. Additionally, the goal location must have been visited in the search data. Changing the goal can result in non-optimal paths if it is outside of the original path.

Type parameters

Name	Type
K	extends KeyType
T	T

Parameters

Name	Type	Description
searchResults	SearchResult<K, T>	The data to use to build the path from

Returns

T[]

An array of locations