See the discussion of this post on Hacker News.
My wife and I decided to make an 8-bit, top-down, Zelda-like game written for the PPU466 (from CMU 15-466 Computer Game Programming course). The PPU466 is a graphics API kind of like the PICO-8 fantasy console, in the sense that it’s restricted to 8-bit graphics, 4 colors per tile, fixed backgrounds, and a low number of sprites.
As a part of the game, I wanted our monsters to chase the player. So I spent some time exploring and implementing different pathing techniques and I wanted to share what I discovered, especially some fun A* tricks not covered by Wikipedia.
Linear Pathing
Let’s start with the most basic pathing: draw a straight line between the monster and the player and have the monster go in that direction.
Everything is great until the monster hits a wall and then it stops dead. You can fix this particular issue with wall-sliding: instead of stopping when you hit a wall, you move along the wall.
This approach works surprisingly well for pathing, but it really shines for player movement. Nearly every game uses this technique for player movement (and have since Pac-Man) because it makes movement controls more responsive near walls and edges. (Pac-Man Championship Edition DX+ adds sparks when the player wall-slides which is really cool)
One side-effect of wall-sliding in linear pathing is monster trapping:
This is not necessarily as bad as it looks. Many games even use this as a feature, adding monster trapping as a strategic element (e.g. safespotting in Runescape). But this isn’t what I wanted for our game, so I looked into true path-finding algorithms.
Dijkstra’s Algorithm
This is the algorithm everyone learns in school. It’s straightforward to implement and it’s guaranteed to find the shortest path. But the problem is that it does too much work: for the starting node, it finds the shortest path to every other node in the graph. You can stop once you find your destination node, but there’s no way to direct the algorithm to make progress towards that node in particular. And in a videogame, the monster’s destination changes every frame as the player moves! And really, the monster doesn’t even need the full path: it just needs to know which direction to go.
You could pre-compute the shortest path for every pixel or tile on your map, but that’s a lot of memory.
So if you are designing your game to run on a legacy or resource-constrained platform, Dijkstra’s isn’t going to work.
Luckily there’s a better way.
A* Search Algorithm
Wikipedia has an in-depth overview of the algorithm (and a really nice animation showing how it works), so I’ll just share my intution for how it works.
First, steps are weighted by the distance of the starting node to the destination node. This means the algorithm starts by trying to go in a straight line to the destination. Unlike Dijkstra’s, it won’t waste a bunch of time going in the opposite direction (unless it has to).
Second, if a wall is blocking the path, it will start investigating nearby nodes to try to get around the wall. And most importantly, it won’t get stuck: like Dijkstra, it won’t revisit node’s it’s already seen, so it will eventually find a way to get around the way, even it has to backtrack a lot.
Here’s the algorithm in action:
Note that the monster does not get stuck behind the wall.
A* Tricks
Here’s a few tricks to make the algorithm faster and easier to implement.
Implicit Graph Data Structure
In textbooks, graphs are represented by a list of nodes and an adjacency matrix or adjacency list. But you can be a little more flexible about representing adjacency nodes.
For example, let’s say our game screen has 256 * 240 pixels. We’ll call the coordinates of each pixel a node. Then we can say there are 8 adjacent pixels: up, down, left, right, and the 4 diagonals. The cardinal directions have a weight of 1, while the diagonals have a weight of the square root of 2 (~1.4).
We don’t need to create a huge adjacency list: we can generate it on the fly. Moreover, not every pixel is a valid position for the monster: it might be on a wall or occupied by another sprite. In that case, we can dynamically exclude that pixel from the adjacency list.
Here’s how this might look:
# suppose current is some data structure with x and y coordinates
neighbors = [current + dir for dir in [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]]
for neighbor in neighbors:
if out_of_bounds(neighbor) or occupied(neighbor):
continue
# do something with neighborSo we only need to generate the adjacency list for the nodes we are actually going to visit, and we don’t have to manually exclude adjacent nodes with a map editor.
Geometry Informed Heuristics
You can also manually tune aspects of the algorithm based on the geometry of your map.
Step size
Above I talked about using the pixels as nodes, but in a 2d tile based game, you can use the tiles as nodes. This speeds up the search dramatically, since the monster can find a path to the player in fewer iterations.
With this method, the path really isn’t an exact sequence of steps: your monster likely isn’t moving at a speed of 1 tile per frame. Now the path is a series of directions the monster should go.1
And that’s okay! As I said in the Dijkstra section, our monster doesn’t actually care about the exact path, which is changing each frame as the player moves. It just needs to move in a direction that could possibly reach the player (i.e. not straight into a wall).
Iteration depth
One cool feature about A*: once a node comes off the priority queue, we know that that node represents the last step in the best path we’ve seen so far. Therefore, if we stopped the algorithm at some fixed number of iterations, we would know that the resulting path is our best guess for the shortest path to the destination. So we can get reasonable progress without the running the algorithm to completion.
You need to tune this maximum iteration depth to the geometry of the level. For example, if the depth is too small you can still have monsters get stuck behind a wall:
With a fixed iteration depth of 30 tiles, we can position the player so the monster gets traps and can’t make progress towards the player. How does this happen? Remember that A* is recomputed each frame. On the first frame once reaching the wall, the monster calculates that it should move down. But on the next frame, it calculates that it should move up. This casuses the monster to get stuck in a loop. However, as soon as the player moves into it’s range, the monster is able to correctly find a path to the player.
You can see this effect exaggerated with a fixed depth of 1:
frame 1 frame 2
4
3 | . | m
2 p | m p | .
1 | |
0The monster always returns to pxiel 2 because it’s the shortest (Euclidean) distance to the player.
If you wanted to be really fancy, you could pre-compute the maximum depth A* needs to find a path from any position on the map. Unlike the pre-computed Dijkstra, you only have to save that maximum, since you know A* will find a valid path in real time, given that maximum depth.
Technically, this is true of the pixel-based path as well. The monster isn’t moving at a speed of 1 pixel per frame either! It’s probably not even moving an integer number of pixels each frame!↩︎