Pathfinding algorithms in Demon Keeper

While ZedZed required only simple directional pathfinding (zombies are stupid, so advanced pathfinding is not needed), Demon Keeper required some more advanced techniques to facilitate targeting.

I found a great A* tutorial, and some great additional information, which helped me get started, but it wasn’t quite what I needed. The first thing I did was to split out the core logic into a function, and create two functions to access it for either a targeted A* route finder, or a Dijkstra search of multiple potential targets. The latter ended up being more heavily used for actions like finding the closest nearby hostile to attack, whereas the A* function is then used to maintain a route once the target is acquired.

What still remains insufficient however, is a node’s binary state of being either a pass or block in pathing. This created two problems: actors immediately in the way of the moving sprite would block its progress flat, and targetable features with no pathing data would return as unreachable. The ultimate solution to this was to pass in three separate path arrays: the board, the features, and the actors.

These three boards may then be analyzed in different ways, depending on where in the path you are. The actor board may be ignored entirely in all but the first move (since that’s the only one in which you can count on it being a factor), or weighted in a node’s F-value, based on distance (i.e. an actor blocking a node will have less value the further it is away from origin). The feature board will be used for the path along the way, but ignored at the final destination point, allowing for blocking features to be targeted, but still routed around along the way.