Pathfinding

Finding the shortest path from one point to another. That's the objective of pathfinding algorithms. Let's see how it's done.

In this interactive example you can see how two different pathfinding methods works. There are two algorithms, Breadth First Search (BFS) and A Star (A*). Click on any cell to generate a path between the two purple points. The green cells are the shortest path and the blue ones are the cells visited (less blue, faster algorithm).

Your browser does not support the HTML5 canvas tag.

Building a grid of nodes is very easy in 2D games, and especially if you are using tilemaps. You have to divide your map size in cells. With tilemaps every cell has the same size of the tile (32x32, 64x64...). Then create a Grid using vector, matrix or your own data structure.

Fill the grid at the same time you load the tilemap. Then check if a tile is the type that blocks the terrain, like a rock or a wall, and change the grid: `Grid[x][y] = 1; // 1 == blocked`

As you will see, A Star is more efficient than BFS. But why?

Let's take a look at the Breadth First Search code.

``````struct Node
{
int x;	// position.x
int y;  // position.y

bool visited;	// if the node has been processed
Node parent;	// where come from
};

struct Grid
{
// return the node(x,y) in the grid
void getNode(int x, int y);

// marks node N if is visited or not
void setNodeVisited(Node N, bool b);

// marks all nodes in the grid as "not visited"
void resetNodes();

// returns true if the node has been visited
bool isNodeVisited(Node N);

...
// the grid can be filled with vector or arrays
// of 1 and 0. Or any type of data struct you want
};

// returns all the nodes that can be accessed through A (no diagonals)
std::vector<Node> getNeightbours(Node A)
{
std::vector<Node> neightbours;

// UP
if (!isBlocked(A.x, A.y - 1))
neightbours.pushback(getNode(A.x, A.y - 1));

// DOWN
if (!isBlocked(A.x, A.y + 1))
neightbours.pushback(getNode(A.x, A.y + 1));

// LEFT
if (!isBlocked(A.x + 1, A.y))
neightbours.pushback(getNode(A.x + 1, A.y));

// RIGHT
if (!isBlocked(A.x - 1, A.y))
neightbours.pushback(getNode(A.x - 1, A.y));

return neightbours;
}

std::vector<Node> findPath(Node Start, Node End)
{
std::queue<Node> Q;

Grid.resetNodes();

// add the first node to the queue
Q.push(Start);

while (!Q.empty())
{
Node current = Q.pop();

// mark the node has visited
Grid.setNodeVisited(current, true);

// reach the end
if (current == End)
{
std::vector<Node> path;

path.pushback(current);

// recontruct the path until we reach the Start node
while (current.parent != NULL)
{
current = current.parent;
path.pushback(current);
}

// the current path is from End to Start
// reverse the vector (Start -> End)
std::reverse(path.begin(), path.end());

return path;
}

std::vector<Node> Neightbours = getNeightbors(current);

// add to the queue all neightbors not visited
for (Node n : Neightbours)
{
if (Grid.isNodeVisited(n)) continue;
n.parent = current;
Q.push(n);
}
}
}
``````

The logic behind Breadth First Search is simply to expand from one point in all directions possible until it finds the end node. It's like pouring water in a labyrinth and wait to reach the exit. It's very simple but inneficient, because the time it takes to get the shortest path increases more and more as the grid size.

For that reason, it's not recomended to use BFS for pathfinding in games. You have to see time as an asset. The more time you take finding paths, the less you have to do other things. Inneficient code will eventually slow down your program (and fps).

This two images show a direct comparison between BFS and A*  A Star (A*)

A Star takes less steps to reach the same goal. It no longer go crazy in all directions, but instead it search for the "best" node available towards the exit. And how is it done? By adding an heuristic function in the algorithm Manhattan Distance.

The idea is to process first the nodes with higher chance to get faster to the end node. This is done by calculating the distance between the current node and the end node, and using a priority queue to always get the node with less "cost" to get from A to B.

To do so, we need to change a few things in the algorithm.

``````struct Node
{
int x;	// position.x
int y;  // position.y

bool visited;	// if the node has been processed
Node parent;	// where come from

int g;  // cost from the start node
int h;  // estimated cost to the end node
}

// compare function for the priority queue
bool operator<(const Node &A, const Node &B)
{
return (A.g + A.h) < (B.g + B.h);
}

// returns the estimated distance between two points
int ManhattanDistance(Node A, Node B)
{
return abs(A.x - B.x) + abs(A.y - B.y);
}

...
/* same other functions as before */
...

std::vector<Node> findPath(Node Start, Node End)
{
std::priority_queue<Node> Q;

Grid.resetNodes();

Start.g = 0;
Start.h = ManhattanDistance(Start, End);

// add the first node to the queue
Q.push(Start);

while (!Q.empty())
{
// always give us the best node possible
Node current = Q.pop();

// mark the node has visited
Grid.setNodeVisited(current);

// reach the end
if (current == End)
{
std::vector<Node> path;

path.pushback(current);

// recontruct the path until we reach the Start node
while (current.parent != NULL)
{
current = current.parent;
path.pushback(current);
}

// the current path is from End to Start
// reverse the vector (Start -> End)
std::reverse(path.begin(), path.end());

return path;
}

std::vector<Node> Neightbours = getNeightbors(current);

// add to the queue all neightbors not visited
for (Node n : Neightbours)
{
if (Grid.isNodeVisited(n)) continue;

n.parent = current;

// increment the cost of moving to another cell
n.g = current.g + 1;

// estimate the distance to End
n.h = ManhattanDistance(n, End);

// automatically order the new node in the Queue
Q.push(n);
}
}
}
``````

Thanks to the priority queue and the heuristic values, we can reach the end node much more faster. You can use other type of heuristic function like Euclidean Distance or Chebyshev Distance.

A Star is a well rounded pathfinding algorithm for most 2D games. But is also customizable and can be improved. For example, this code only uses 4 directions (N-S-E-W). You can change it to make diagonal movements modifying the `getNeightbors()` function.

And if you need something more fast than A*, you can read more about Jump Point Search. The idea behind JPS is to improve the A* algorithm by discarding/pruning nodes that are not relevant to find the solution. Is very useful if your grid has rectangular empty spaces (like rooms or hallways).

If you never used a pathfinding algorithm before, start implementing a BFS first. It will give you the basic knowledge and is good for learning different techniques. From then, go for A*, you will notice the improvement. And if you need more, try JPS. It's more complex but it pays off.