Dynamic Pathfinding

Introduction

As humans, we like to implement solutions which are familiar to us. We get caught up doing things the way we know how to do them, rather than the “best” way to do them. It’s easy to get caught up in thinking like this and as a result we end up using outdated technologies and implement features in ways that our modern contemporaries don’t understand, or are simply less effective or efficient. My purpose with this and future papers will be to expose readers to a broad spectrum of solutions that will hopefully help them in their own coding. Today I’ll be covering Pathfinding: Node Networks in Dynamic 2D Environments. Pathfinding is a broad topic with many strategies and implementations available for the discerning AI programmer. While a wide variety of information is available both online and in print on pathfinding through 2D and 3D environments, very little has been written about how to setup pathfinding solutions in side scrolling games where characters move non-linearly due to the effects of gravity. Even in 3D environments jumping or other non-linear movement is considered an edge case rather than the norm. Even less has been written about how to deal with dynamic environments; that is, environments which frequently change. With this paper I intend to address this dearth of information with one way of creating a robust node network in a dynamic, side scrolling 2D environment. While I normally include a lot of code examples in my writing, this system is large enough that code examples aren’t practical, and so I will stick to a high-level implementation overview instead.

Once Upon a Time

Some time ago I was sitting in my office, leaning back and with my feet kicked up on my desk thinking about how to get the units in my game to move from one side of the map to the other. Previously, and with ample help from my mad scientist dog Fankie, I had figured out how to setup an intelligent AI which could decide what actions to take given some in-game context. Now I faced a related challenge – the AI knew WHEN it should move to its objective, but had no idea HOW to get there.

And I had no idea how to go about it either. I needed some help. Dog help. So I swiveled my chair around to where Frankie was writing her dissertation on the… honestly I’m not what. It’s all noise to me. “Hey Frankie, how does a Squire get to a gold pile?”

“Grab me a carrot and I’ll help you out. We can start with generating a node network to provide the squires with some information.”

Ok, so first step, generating a node network. Well, grabbing a carrot, then generating a node network.

Generating a Node Network: Nodes

If you’ve done any sort of pathfinding work before, you’re probably familiar with node networks. If you’re not, then this isn’t the time or place for me to get into it in too much detail, so you might need to read some other materials before jumping in. Proceed at your own discretion. In general, nodes represent space which a unit can occupy. In grid based A* pathfinding, for example, every grid square the agent can move through is a node. In King Randall’s Party, every block the player can stand on has a node on it. I place these nodes slightly above the block in the space the agent will actually stand.

But wait, you say! You’re missing some nodes. Right you are – we are missing the nodes that are on internal walls or covered dirt blocks. These nodes need to be placed as well, even if the agent can’t actually use them because they are blocked. There are ladder nodes too, but for the purposes of this example we will ignore them for now as they clutter up the picture a lot.

The purpose of having all these nodes is to create a data model of all the positions in the game world which the agent can stand/sit/hang from or otherwise occupy. This is the reason we position the nodes above the blocks – they represent where the unit will stand. By running collision checks on the nodes position we can check if that node is blocked or unblocked. Ok, so now that we have identified all of the spaces the agent can occupy, we need to figure out how the agent can move between the nodes. This is where linking comes into play, and where we diverge the largest from typical A* or other pathfinding examples. And as Frankie reminded me “You’re going to have to make sure either your nodes have a reference to your game objects, or your game objects have a reference to your nodes, so that when the game objects are destroyed or otherwise removed from the game world the nodes know they must also be removed from the pathfinding model. Same with your pathfinding links, which we are about to cover.” Smart dog.

Generating a Node Network: Links

So far so good! I was pretty pleased with myself - I had generated a bunch of pathfinding nodes based on the objects I have in the world  But just as I was ready to rest on my laurels, Frankie burst my bubble. “So what are you going to do about the links?” “Links?” I responded. “Yeah”, Frankie responded as she moved over to her favorite sunspot on the floor and rolled over for belly rubs. “Links, the data structure which connects two nodes so that the units know they can move between those two nodes.”

Here I got stumped. Unlike in a top down game where unit generally moved in straight lines between nodes, units in King Randall’s Party units didn’t necessarily move in a straight line unless they are walking. They often jumped, climbed, mounted ladders, fell, or otherwise moved in non-linear ways. If the agent attempted to move linearly through the air, not only would it look strange, but it would collide with the blocks and prevent otherwise desirable movement.

Frankie said “Take it step by step. First, cull out nodes which are just too far apart to realistically have any kind of movement between them. Then, just like how in top down games you simulate straight line movement to connect nodes, you’ll need to simulate the jump path in order to determine if you can link two nodes via a jump link.” Ok, I thought to myself, spinning wildly in my swivel chair, we need to have links model actual jump curves and then simulate the actual jump to see if the agent would collide with anything along its jump path to determine its on/off state. Since this is so different from straight line walking links, we end up with two different link types. Walking, which link nodes on the same Y level that are adjacent to each other, and Jumping, which link any nodes within distance that have a clear jumping path between them. That will work.

But wait, you say! If units can jump, there must be more jumping links than to just diagonally adjacent blocks! Just so. In fact, while each node can only create two outgoing walk links (to adjacent nodes), it can create a ton of jumping links.

And that is just the jump links from one node to the surrounding nodes, not including the links every other node in the area has. Showing all of those links would make the picture indecipherable, so we will simplify the example images by only showing some of the jumping links.

Determining On/Off States

Ok, so I had setup my nodes, and I had hooked them all up with links. And even better, these links had some fancy collision checking code in them which could tell if the path was clear. When the game started, my code would check to see which links were obstructed and would set an in-code toggle letting my pathfinding system that these links were “off” and could not be considered for pathfinding. But here is where I ran into a common gotcha…

Adding Objects to the Game World

When adding or removing objects from the game world, I needed to update my pathfinding nodes and links so that they could turn off if the new object blocked them or turn on if the object removed was previously blocking them. For adding objects, this was fairly easy, I would add the object to the game world, it would generate a pathfinding node and link that node to the existing nodes in the world via links. I would then run several collision checks – one to see what previously existing nodes and links the new game object collided with so that I could mark those as blocked, and some more to determine what nodes my new node could link to, and if they were blocked by existing game world objects. But what about… removing an object? I could also run a collision check to see what objects it was colliding with here, but this can actually be a pretty expensive collision check; while objects tend to be added to the game world pretty slowly (as fast as the player can click), when large structures collapse a LOT of objects can get removed at the same time.

Removing Objects from the Game World

So instead of running collision checks whenever we remove an object from the game world, a better solution is for the pathfinding objects (nodes and links) to keep track of objects that are blocking them. This way when an object is removed from the world we can update the affected links without running a collision check. If the pathfinding objects don’t have any blocking objects in their list, they mark themselves as unblocked. If they are still tracking blocking objects even after removing one instance, then they remain blocked. You could also have a third system track these blockages instead of the pathfinding objects if you wanted to separate the functionality.

“Well great! Now I’m done. I can generate nodes when objects are added, and those nodes and their links can keep track of if they are blocked or unblocked, and I can later remove objects and nodes from the game and the node network will update appropriately.” “Yeah”, Frankie responded while rolling on her back “You’re a regular genius; but shut it down, its time for our walk.”  

Handling Pathfinding Requests

Now we have our pathfinding network all setup, it can handle objects being dynamically added and removed. I ended up using a standard A* pathfinding algorithm. I went for a standard A* pathfinding algorithm, but really I could have used any pathfinding algorithm that uses nodes and edges. The world is your oyster, or dog bone, or whatever.

A note: A* requires that we can assume there will be a path between the start and end nodes, if this is not the case and you have a really complicated map then you probably want to go with another algorithm.

Drawbacks to This System

There are some drawbacks to this system. Since the nodes are generated on a per-block basis, if your blocks are too big or too small than your network may not have the required fidelity to match wat you want to see in your units movement. Also, this is not an immediately scalable solution; as your map size and the number of options for unit movement (walk, jump, climb, swing, fly, etc) grows, the amount of time required to setup these networks will grow quickly out of hand. You will definitely need to do some hard thinking about how to manage scale if you want to keep this kind of solution for larger projects.

Ways to Extend This System

This isn’t an extension so much as an improvement, but setting up this system so that all of the heavy lifting of node generation and pathfinding on a secondary thread is something you should strongly consider when deploying to a platform which supports multithreading. Barring that, you can set up your pathfinding system so that it limits the amount of processing it handles during any given frame to avoid stuttering when a lot of requests come in at the same time. Both of these solutions are too complicated to go into any depth in this paper. For either one of these extensions I recommend that you setup a separate Pathfinding Manager class which queues all requests related to pathfinding and then either launches them on a separate thread of processes them for a specific time slice before giving control back to the game loop.

Conclusion

Whew, that’s a lot of high level stuff to take in, so let’s summarize it. Here are some of the key takeaways.

• Generating node networks on the fly for dynamic environments is possible and can work well, but breaks down at larger scale without systems to mitigate or offset the size and usage of the network.
• You’ll need to account for paths which are blocked by objects in your game work, and enable your pathfinding objects to turn on or off accordingly.

As a reminder, this isn’t the only, or even necessarily the best way, to setup a node network for a dynamic 2D environment, but as always it is important to keep a large variety of coding tools in our toolbox so that we can pick the right one for the problem at hand. This system ended up working quite well for King Randall’s Party.