Pathfinding | UroboroStudio

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

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*

Breadth First Searh (BFS)

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.

AVAILABLE ON STEAM

Icons made by Lorc. Available on Game-Icons.net