A*, pronounced “A star”, is a pathfinding algorithm. I implemented it in JavaScript to explore how to move from one node to another in a grid with obstacles.
Represent the map
The AStar constructor receives an implementation of Grid. The grid describes which nodes exist and which are traversable. The repository’s Table class is an example of that implementation.
let grid = new Table(cols, rows);
... // Populate the grid
const astar = new AStar(grid);Request a route
After obtaining the start and destination nodes, pass them to route. If a path exists, the method returns its sequence of positions; otherwise, it returns null.
let n1 = grid.getNode(x1, y1); // Get the start node at x1, y1
let n2 = grid.getNode(x2, y2); // Get the destination node at x2, y2
const route = astar.route(n1, n2); // Find a pathWhat makes a path the best one?
A* combines the cost so far with an estimate of the remaining cost. Whether the result is optimal depends on the heuristic, movement costs, and how visited nodes are handled. Changing the map’s rules may also require changing that estimate.
Try an enclosed destination, a narrow corridor, and an open map. Comparing these cases helps explain the search beyond its final route.