@excaliburjs/excalibur-pathfinding

Readme top

Excalibur-Graph Plugin

A plug in that assists in creating graph networks of nodes and edges, allowing for path finding, dijkstra's, dfs, and bfs algorithms

Table of Contents

About The Plug-In
Getting Started
Usage of the Graph Module
- Graph module
Usage of the A* path finding module
- A* module
Contact
Acknowledgments

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

(back to top)

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.

(back to top)

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

(back to top)

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);

(back to top)

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.

(back to top)

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.

(back to top)

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;
};

(back to top)

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);

(back to top)

GraphTileMap

See above section on setting up a GraphTilemap

let tilemap: GraphTileMap = {
  name: "tilemap",
  tiles: [],
  rows: 3,
  cols: 4,
};
let myGraph = new ExcaliburAStar(tilemap);

(back to top)

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.

(back to top)

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.

(back to top)

Contact

Justin Young - @jyoung424242 (Twitter) - Mookie4242 (itch.io)

Project Link: GitHub Repo: Excalibur-Graph

(back to top)

Acknowledgments

Special thanks to two great communities that are always available to jump in help, and inspire little projects like these!!!!

(back to top)