Enemy Pathfinding in Robocalypse: Beaver Defense.
Introduction
The game genre is tower defense. By design, enemy units spawn at the map entrance, then walk towards the headquarters, then shoot it.
Each passable cell can contain any number of units. Units can only walk in one of the 8 directions.
The game map is a matrix of square cells. But, the graph algorithms work on graph. So, graph node = map cell, graph edge = the line connecting the adjacent cells. So the passable cell surrounded by 8 other passable cells = graph node having 8 edges.
Problem Statement
Initially, all units used the modified version of Dijkstra's algorithm. That early alpha version suffered from the following 3 problems:
- When the game designers increased the number of enemy units that spawn simultaneously, the performance dropped severely: the symptom was the newly spawned enemy unit thinks for a second, only then he starts moving to the headquarters.
- When the game designers created maps with complex topology — due to some reasons the enemy units were unable to find the path. Of course the Dijkstra's algorithm contains no graph size constraints, however due to the performance reasons the search depth was limited.
- And, I didn’t like the enemy unit is that stupid so they rush towards the turrets and die ingloriously, not firing a single shot towards the headquarters they going to destroy.
Solution Overview
The main reason it became possible to dramatically improve the pathfinding code is the fact that every enemy unit wants to reach the same destination. That’s why, unlike for example RTS games, there’s a vector field of the directions where the unit should go next. All we have to do is pre-calculate the “next” direction for every passable map cell, and carefully update this data when the map changes.
With this approach, finding the path is just a single memory lookup (execution time is several nanoseconds). And more units don’t take more resources for pathfinding, thus solving the problem #1.
We only build the path map once. That’s why we can afford spending more resources then for a unit pathfinding: there’re lots of units on the map, but there’s only one map. Removing the search depth limit solves the problem #2.
When I was developing the code, I thought my version uses the Dijkstra's algorithm, too. However, currently as I’m googling while writing this article, it seems my implementation is much closer to the A* algorithm.
Because I wanted the units to elude the turrets, in addition to the “edge” cost, I introduced the “node” cost, the cost to visit the given node. If the map cell is safe for the enemy (not covered by any turret), the node cost is zero. If however the map cell is within the turret’s range of fire, the node cost is non-zero, depending on the turret’s weapon power.
Here’s the screenshot from an NDEV, with my debug rendering visualizing both target direction (see the small arrows), and cell danger (note the color of those arrows is changing from white = completely safe, to various shades of red = dangerous):
I gave our level designers a single slider ranging from 0 to 255, AFAIR it’s called something like “Enemy pathfinding danger/distance factor”: if it’s 0, the enemy units completely ignore the danger always choosing the shortest path. While if it’s set to 255, enemy units almost completely ignore the distance, they always choose the safest path. This value is stored in the map file, so the level designer may try different values and find the best one for the map he’s designing.
However, this “danger/distance factor” was only implemented in the game not in the Windows demo, that’s why this logic is completely missing from the attached source code.
Implementation Details
After I’ve got the main idea, the implementation was pretty straightforward.
I was new for the Wii platform. And the involved algorithms seemed to be not that trivial: it’s much more complex then “hello worlds” or even “spinning teapots” application.
So I thought it was a good idea to first implement and debug it using all power of the Microsoft’s development tools, then port to the Wii. The time showed I was right: I estimate it would take me two times longer to implement and debug the code if I was using the Nintendo’s proposed IDE.
That’s why I’ve created the windows demo I’m sharing here. Here’s the source code, and I’ve also compiled and uploaded the binary if you only want to check out the algorithm in action, and not interested in the source code.
Here’s a screenshot of Windows demo application:
The heart of the algorithm is CPathMap class, implemented in main\PathMap.h and main\PathMap.cpp source files.
The derived CPathMapWin contains some logic that was already implemented in the various parts of the rest of the game: e.g. map loading, towers placement and removal, etc. Needless to say, I paid very little attention to the correctness of that code, that’s why it’s possible to place many turrets on the same cell, or completely block the way to the HQ. Remember, my main goal was implementing the pathfinding code, and then integrating it into the game. Cool demos were out of my scope, sorry.
The path map is backed up by a CArray2D template class, the template container class that holds 2D array of elements, accessible by both 2D index (by the CPoint structure holding item coordinates), and single-dimensional index (size_t holding the item offset from the {0,0} element).
Every map cell holds the CPathMap::SMapEntry structure. It’s sizeof is 8, and it holds all the information required for the map updates.
My A*’s initial nodes is the enemy’s destination. So the A* algorithm starts from the HQ, and the “hot wave” is then spreading across the whole map. In the Windows demo application, hot cells are marked in yellow.
In the game, map is updated every frame (if anything needs updating). The Windows application updates the map every second, to visualize the update process.
My A* algorithm has no goal to find. Instead, its goal is to traverse all passable cells, storing the found direction towards the HQ. The “Open set” from the A* equals to “the set of map cells where FLAG_HOT is set”. “Closed set of nodes” equals to “the set of map cells where FLAG_DONE is set”.
During each step of the A*, we need to fetch the minimal cost node from the open set. The whole map can easily take 200kb RAM. Searching over that dataset for every cell is expensive. To save both CPU ticks and cache misses, I cache the best subset of the “hot” cells in the “CPathMap::CBestUnvisitedCache” nested class.
Final Words
As you can see, the solution is both computationally cheap, and reasonably optimal. But remember, the main source of the optimization comes from the fact that every unit wants to reach the same destination. So I think it’s only useful for tower defense games.