@excaliburjs/excalibur-pathfinding
v0.29.0-alpha.1
Published
excalibur-pathfinding provides ability to use A* and Dijkstra's Algorithm for pathfinding and with Excalibur.js
Downloads
3
Readme
Readme top
About The Plug-In
This plug in creates a class that is a collection of nodes and edges.
In the API:
- adding nodes, edges, and resetting data
- Depth First Search between nodes (dfs)
- Breadth First Search between nodes (bfs)
- Dijkstra's Algorithm which analyzes the distance between starting node and all other connected nodes
- Shortest path, utilizing Dijkstra's Algo, we can return the shortest path between two nodes
UPDATED
- add a class for A* path algorithm
- added support for diagonal traversal
- added checks for unreachable nodes
Getting Started
To import the plug-in, from your shell:
npm i @excalibur/excalibur-graph
Declare and instantiate the new graph
import { ExcaliburGraph, GraphTileMap } from "@excaliburjs/excalibur-graph";
let myGraph = new ExcaliburGraph();
//...or...
let myAstar = new ExcaliburAStar();
Usage of the Graph Module
To use the Graph.ts module included with this project, you can build your 'graph' manually, or import a tilemap object and let the module parse it itself.
Types
What is a node?
type Node = {
name: string;
value?: any;
};
Nodes are discrete unis or vertices in the graph, they optionally can be provided some data of any type that can be associated with that vertex. Nodes will be connected to other Nodes via Edges
What is an Edge?
type Edge = {
name: string;
from: Node;
to: Node;
value?: number;
};
Edges are the relationship between Nodes. The are unidirectional, as such they each have a required 'from' an 'to' property that designates the direction of the edge. Also, an optional 'value' number property exists to assign a weight or distance value to the Edge. This is very important for shortest path and Dijkstra's Algorithm analysis. Tilemaps get imported with a default value of 1 for each Edge.
What is a GraphTile?
export type GraphTile = {
name?: string;
index?: number;
coordinates?: { x: number; y: number };
data?: any;
collider?: boolean;
};
A GraphTile is the atomic unit of a GraphTileMap. When a GraphTileMap is loaded and parsed, each unit is read as a GraphTile, and then the parser looks for the collider property to establish the necessary relationships to the Tile's neighbor Tiles.
What is a GraphTileMap?
export type GraphTileMap = {
name: string;
tiles: Array<GraphTile>;
rows: number;
cols: number;
};
A GraphTileMap is a collection of GraphTiles along with the parameters for the tilemap dimensions. The 'tiles' property comes in as a flat array, and the parser uses 'rows' and 'cols' to manage determining the shape of the tile map overall, including establishing the neighbor Nodes with respect to each Node.
Manual Entry
To manually load this example graph, we need to :
- Load each node using myGraph.addNode();
myGraph.addNode({ name: "a" });
myGraph.addNode({ name: "b" });
myGraph.addNode({ name: "c" });
myGraph.addNode({ name: "d" });
myGraph.addNode({ name: "e" });
myGraph.addNode({ name: "f" });
- manually load the edge relationship with distance values
myGraph.addEdge({ name: "ab", from: myGraph.nodes.get("a")!, to: myGraph.nodes.get("b")!, value: 10 }, true);
myGraph.addEdge({ name: "bf", from: myGraph.nodes.get("b")!, to: myGraph.nodes.get("f")!, value: 10 }, true);
myGraph.addEdge({ name: "ac", from: myGraph.nodes.get("a")!, to: myGraph.nodes.get("c")!, value: 5 }, true);
myGraph.addEdge({ name: "cd", from: myGraph.nodes.get("c")!, to: myGraph.nodes.get("d")!, value: 15 }, true);
myGraph.addEdge({ name: "de", from: myGraph.nodes.get("d")!, to: myGraph.nodes.get("e")!, value: 3 }, true);
myGraph.addEdge({ name: "be", from: myGraph.nodes.get("b")!, to: myGraph.nodes.get("e")!, value: 8 }, true);
- you are now free to run Depth First Search (dfs), Breadth First Search(bfs), Dijkstra's Algorithm, and find shortest path between nodes
** dev's note, the true
that's passed as last parameter automatically creates the reverse path to make it bi-directional
Importing Tilemap
If you wanted to load this example tilemap on the left in order to 'create' the graph on the right...
- using a GraphTileMap object, create your tilemap config object
let tilemap: GraphTileMap = {
name: "tilemap",
tiles: [],
rows: 3,
cols: 4,
};
- load up your tiles with tile objects
example tile object
class Grass extends Tile {
constructor() {
super();
this.name = "grass";
this.collider = false;
}
}
The graph parser simply consumes the collider property, and uses it to create the edge connections automatically, so if a tile is a collider, and its true, then the 'node' won't be created, and it will influence/manipulate the graph design. This is visually represented in the above image, where the 'wall' tiles do not show up in the graph.
tilemap.tiles = [
new Grass(),
new Grass(),
new Grass(),
new Wall(),
new Grass(),
new Wall(),
new Grass(),
new Grass(),
new Grass(),
new Grass(),
new Grass(),
new Grass(),
];
- Pass the tilemap to the Graph, and it will create your nodes and edges automatically
myGraph.addTileMap(tilemap);
Output from Graph
DFS
The Depth First Search api is:
dfs(startnode: Node, endnode: Node, visited = new Set()): boolean
The dfs will conduct a node search to see if startnode can reach endnode. If its found, it returns true, else false.
BFS
The Breadth First Search api is:
bfs(startnode: Node, endnode: Node): boolean
The bfs will conduct a node search to see if startnode can reach endnode. If its found, it returns true, else false.
Dijkstra's Algorithm
the Dijkstra's Algorithm api is:
dijkstra(sourcenode: Node): Array<{ node: Node; distance: number; previous: Node | null }>
It takes the starting 'source' node as input, and will return an array of objects that include properties node, distance, and previous node.
Shortest Path
the shortest path calculation api is:
shortestPath(startnode: Node, endnode: Node): Node[]
The shortest path method takes the starting node and ending node as params, and returns an array of nodes consisting of, and in order, from starting node to ending node, and includes every node in between. REPEAT... this DOES include the starting node in its analysis.
Utility Methods
ResetGraph
resetGraph();
This method clears out the nodes and edges data, creating a clean graph.
getNodes() and getEdges()
getNodes();
getEdges();
These methods return a Map of the current overall collection of nodes and edges respectively.
getAdjacentNodes,getAdjacentEdges,getAdjacentEdgesTo
getAdjacentNodes(node: Node): Node[];
getAdjacentEdges(node: Node): Edge[];
getAdjacentEdgesTo(node: Node): Edge[];
These methods will return information regarding the neighbors and relationships of the Node passed in.
Since relationships have directions, the getAdjacentEdges and getAdjacentEdgesTo provide a list of the coming and going edges respectively.
Usage of the A star module
The A* path finding algorithm is an optimized algorithm of path finding. This module is tailored to Tilemaps specifically, and can handle importing of dedicated GraphTilemaps or the Excalibur Tilemap.
Types for Astar
What is an aStarNode?
export type aStarNode = {
id: number | string;
collider: boolean;
gCost: number;
hCost: number;
fCost: number;
x: number;
y: number;
checked: boolean;
parent: aStarNode | null;
};
Importing Tilemaps
You can use either a GraphTileMap, the same as the Graph Module, or you can pass an Excalibur Tilemap to the Astar module
Excalibur Tilemap
// Create a tilemap
const tilemap = new TileMap({
rows: 10,
columns: 10,
tileWidth: 16,
tileHeight: 16,
});
// loop through tilemap cells
let tileIndex = 0;
for (let tile of tilemap.tiles) {
//...
//logic for setting up tiles
}
// create astar instance
let myGraph = new ExcaliburAStar(tilemap);
GraphTileMap
See above section on setting up a GraphTilemap
let tilemap: GraphTileMap = {
name: "tilemap",
tiles: [],
rows: 3,
cols: 4,
};
let myGraph = new ExcaliburAStar(tilemap);
Output from A star
astar(sourcenode: aStarNode, endnode: aStarNode, diagonal = false): aStarNode[]
After you input your tilemap into the A* class, you can call the astar()
method as many times you need. It will return an array of
nodes representing the shortest path, starting with the first node to move to... i.e. does NOT include the starting node.
Utility Methods In A star
getNodeByIndex(index: number): aStarNode
Based on input number (index) passed to function returns the associated Node object
getNodeByCoord(x: number, y: number): aStarNode
Based on the x/y coordinates passed to function returns the associated Node object
resetGrid();
Set's the grid costing back to 0, clears out starting/stopping nodes, and is ready to 'rerun' astar method with new start and stop nodes.
Contact
Justin Young - @jyoung424242 (Twitter) - Mookie4242 (itch.io)
Project Link: GitHub Repo: Excalibur-Graph
Acknowledgments
Special thanks to two great communities that are always available to jump in help, and inspire little projects like these!!!!