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

- 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.

- 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.

For a full overview of how this was implemented please download and review the source code with comments.

```
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)
.addClosed(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;
}
```