# A* Pathfinding Demo

Author: Ash Blue

In tile based games the most popular pathfinding algorithm is A* (pronounced A Star). It allows you to search through tiles on a two-dimensional plane. But can be easily upgraded to allow three-dimensional searching. There are faster algorithms out there, but this one is by far the most customizable and easy to implement.

The following interactive demo focuses on implementing A Star in the context of a tile game. If you wanted to implement it on a two-dimensional sidescroller you may want to think about implementing it differently.Click on the map to toggle blockers.

Set the start/end point by clicking their corresponding buttons. Then click Find Path to activate the demo. For more details see the legend.

• Open
• Closed
• Begin
• End
• Opened Set
• Closed Set
• Path

## Tile Stats Overview

F = Calculated Total
Sum of the heuristic (H) and current step cost (G)
G = Step Cost
Total number of steps required to walk here from the start tile.
H = Heuristic Estimate
Heuristic uses Manhattan distance. Measures distance from current tile to the goal.
Level
Current level of the tile. Rating of 1 - 4. No rating present means a 1 will be assumed.
F G H

### Movement Rules

• Player can only move up/down one level at a time. This means a player cannot go from level 1 to 3.
• It costs 2 movement points to move up/down a level.

## Implementation Code

``````function findPath(xC, yC, xT, yT) {
var current, // Current best open tile
neighbors, // Dump of all nearby neighbor tiles
neighborRecord, // Any pre-existing records of a neighbor
stepCost, // Dump of a total step score for a neighbor
i;

// You must add the starting step
this.reset()
.addOpen(new jp.Step(xC, yC, xT, yT, this.step, false));

while (this.open.length !== 0) {
current = this.getBestOpen();

// Check if goal has been discovered to build a path
if (current.x === xT && current.y === yT) {
return this.buildPath(current, []);
}

// Move current into closed set
this.removeOpen(current)

// Get neighbors from the map and check them
neighbors = jp.map.getNeighbors(current.x, current.y);
for (i = 0; i < neighbors.length; i++) {
// Get current step and distance from current to neighbor
stepCost = current.g + jp.map.getCost(current.x, current.y, neighbors[i].x, neighbors[i].y);

// Check for the neighbor in the closed set
// then see if its cost is >= the stepCost, if so skip current neighbor
neighborRecord = this.inClosed(neighbors[i]);
if (neighborRecord && stepCost >= neighborRecord.g)
continue;

// Verify neighbor doesn't exist or new score for it is better
neighborRecord = this.inOpen(neighbors[i]);
if (!neighborRecord || stepCost < neighborRecord.g) {
if (!neighborRecord) {
this.addOpen(new jp.Step(neighbors[i].x, neighbors[i].y, xT, yT, stepCost, current));
} else {
neighborRecord.parent = current;
neighborRecord.g = stepCost;
neighborRecord.f = stepCost + neighborRecord.h;
}
}
}
}

return false;
}``````

## References 