Working on one of the subgame prototypes for a larger game idea and needed to implement pathfinding on a 2D map.
One of the most common algorithms for this kind of pathfinding is called A* (read as A Star). The precursor is doing just a Breadth First Search. I was going to make a full A* implementation but the breadth first search was more than fast enough for my small, 2D maps. And as this is a prototype, going with good enough while I flesh out ideas.
The Algorithm
To begin we want 4 things: the map, your starting point, your target point, and some way to keep track of where you are going next and where you have been.
The explanation I was following referred to the places you have to visit next as the “frontier” and I liked that name so we will use it here.
Begin by putting your starting point in your frontier.
Then we loop over the frontier like this:
- Get the next location from the frontier
- If this location is our target point
- We are done. Exit the loop.
- If we haven’t visited this location before
- add it to our visited list
- get all of its neighbors (up, down, left, right)
- add them to the frontier if they are not walls
- mark this location as their parent or previous tile.
Once this loop is complete, because either we hit the target or can’t get to it. Take the last tile we visited and build a path by backtracking thru the parent or previous tile property until we get to our starting point.
Really a fairly straightforward algorithm that was actually kinda fun to implement and then see working.
This is the rough code I used for the prototype:
class Pathfinder {
// map is a 2D array of integers, where 0 is a wall and anything else is walkable
constructor(map) {
this.map = map
this.map_width = this.map[0].length
this.map_height = this.map.length
}
findPath(start, end) {
start.parent = null
let frontier = [start]
let neighbors = []
let visited = []
let current_point = start
while (frontier.length > 0 && (current_point.x !== end.x || current_point.y !== end.y)) {
current_point = frontier.shift()
if(Object.keys(visited).includes(`${current_point.x}_${current_point.y}`)) {
continue
}
neighbors = this.getTileNeighbors(current_point)
neighbors.forEach(function (n_tile) {
if(!Object.keys(visited).includes(`${n_tile.x}_${n_tile.y}`)) {
frontier.push(n_tile)
}
})
visited[`${current_point.x}_${current_point.y}`] = current_point
}
let path = []
while(current_point.x !== start.x || current_point.y !== start.y) {
path.unshift(current_point)
if(current_point.parent == null) {
break
}
current_point = current_point.parent
}
return path
}
getTileNeighbors(tile) {
let neighbors = []
if(tile.x > 0 && this.isFreeTile(tile.x - 1, tile.y)) {
neighbors.push({ x: tile.x - 1, y: tile.y, parent: tile })
}
if(tile.y > 0 && this.isFreeTile(tile.x, tile.y - 1)) {
neighbors.push({ x: tile.x, y: tile.y - 1, parent: tile })
}
if(tile.y < this.map_height - 1 && this.isFreeTile(tile.x, tile.y + 1)) {
neighbors.push({ x: tile.x, y: tile.y + 1, parent: tile})
}
if(tile.x < this.map_width - 1 && this.isFreeTile(tile.x + 1, tile.y)) {
neighbors.push({ x: tile.x + 1, y: tile.y, parent: tile})
}
return neighbors
}
isFreeTile(x, y) {
if(this.map[y][x] === 0) {
return false
}
return true
}
}To make this into a more efficient pathfinding algorithm like A* you would need to change the Frontier into something like a Priority Queue that sorts the next tile to check based on a heuristic like distance to target.
You can find another good article comparing Breadth First, A*, and Dijkstra algorithms here.
Keep getting wiser, stronger, and better.