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