Torch is a simple rougelike personal project I’m programming using C++ and OpenGL with the primary goal of making a simple 2D game with lots of state that needs to be simulated and without using any third-party libraries. I also want to have at least a few working mechanics that inject a little more Dungeons and Dragons into the genre—think creating new walls using a stone shape spell or turning floor tiles into vats of acid.
Movements are made on a per-tile basis, and we need a way for monsters to plan their moves around and through those tiles. That might mean running toward the player, maintaining a minimum distance, or heading toward where the player was last seen. Since the player moves, then the all the monsters, then the player again, we have to run pathfinding every time a monster moves (always following a player move or action), because the player is probably in a new place and the terrain may have changed (either becoming more costly, dangerous, or totally impossible to move through). So we only really need to store which cardinal direction a monster should move in, but divining that accurately means plotting an entire path. Searching every possible path is clearly pretty slow, and would more or less amount to either breadth-first
A-star is generally the default algorithm for pathfinding in games, and it’s clearly a good choice here, but the way it’s usually described in pseudocode or tutorials leaves a lot to be desired. First, I don’t want Torch to do any memory allocation inside the main game loop. Asking Windows for memory is expensive, you can’t leak memory if you don’t keep asking for it, and our simple 2D game has a lot of clearly defined constraints. So we’d like to have a bounded heap segment set aside for any AI or simulation tasks.
A-star typically uses min-heaps (a complete binary tree where each node’s children carry a value that is greater than the node’s, and the root of the tree is therefore always equal to the minimum value). This works well for our memory arena setup, because we can just grab a pointer to a flat array, ignore the 0th slot, and then the child of each node number i is either i*2 or i*2+1. However, every time A-star explores a tile, it considers each of that tile’s cardinal neighbors. When a tile is done being considered as part of a path, it is placed into a “closed” list, and every time a tile is considered we must check if it is on that list (i.e., if it’s already been explored). Without this check we could potentially consider the same tile several times, and would forgo much of what makes A-star efficient, keeping in mind that under a good heuristic, we’ve found the least costly path to a tile as soon as it is explored and added to the closed list. Similarly, tiles should only be added once to the open list (which is really just another name for our min-heap), because again, we’d potentially end up exploring it more than once.
Most pseudocode describes these lists as…lists. There are a lot of options on how to make them. They could just be flat unordered arrays, but then checking for a tile takes O(n) time. We could sort them with merge sort (which is probably the best pick here since we don’t want to allocate more memory and merge sort can be done in place), but then we’re spending even more time during the sort. Hashing them would be great, but more complicated, and now we’re back to feeling pretty uncomfortable about using a set memory arena.
Here’s what I’ve settled on: every tile has an integer data member called navListNum that is initialized to 0, and the game’s state tracks an integer called currentAStarNum that is initialized to 1. When a tile is examined and added to our min-heap, that tile’s navListNum is set to be equal to currentAStarNum. When it is added to the closed list, a tile’s navListNum is incremented. When a run of A-star for a single entity is done, currentAStarNum is incremented by two.
And that’s it! There a problem with this approach: the open list is implemented as nodes of objects with a cost from the starting tile, a heuristic cost to the goal, and a pointer to the actual tile object. If A-star ever finds another route by which to reach a tile on the open list, we then have to search the open list for that tile, and under the current scheme, that means searching the open list linearly. This could be done in constant time by giving each tile a pointer to a tile node, but that means maintaining those pointers even when they aren’t needed. Additionally, we’re mostly concerned with providing monsters with straight(ish) lines to where the player was last seen, and these paths will usually require relatively few steps, meaning small open lists. Finally…a linear for() loop is really simple! If by the end of it we haven’t found an entity, we know something is wrong with our A-star implementation, not with any hashing or sorting routines.
It’s forgivable to dismiss a lot of this under the auspice of “Why Bother, Computers Are Fast,” but I think it’s always worth considering how specific data structures can help support specific problems. And if you can’t do that in a project that’s intentionally from-scratch, where can you!
Leave a Reply