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 now. 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.
I don’t understand how you’re not more popular than you are now. You’re very smart and know so much about this topic that I could imagine it from many angles. It’s like men and women aren’t interested until it’s something to do with Woman gaga. Your stuffs nice, keep it up.
Excellent effort