CyberDunk Devlog #1: AI Navigation

Hi, I’m Riley and I like to learn stuff. Today I’m learning about AI navigation for my platform game CyberDunk. The way I do these videos is by writing the script as I learn the topic. So let’s dive in to what I know right now.

In order for my enemy AI to make smart decisions, it needs good information. This is what the node graph provides. Since CyberDunk is using tilemap based on a 32x32 pixel grid, the node graph will advance 32 pixels at a time while “propagating”. Propagating is a fancy way to say calculating the next node in the node graph. The end result should be an algorithm that grows like a vine from its starting point to cover all walkable surfaces of the map.

So, let’s start. First I’m going to make a new script and have it run in the Unity editor. I want my node graph to calculate while editing my maps, not during runtime. The first thing I’m going to do is have it move left and right until it hits a wall, making nodes along the way.

Awesome. That totally didn’t take an hour and I didn’t make any mistakes during the process. Each green circle is a node and the number above it is it’s X position on the map. When it hits a wall it stops. Great! Now let’s make it try to crawl over blocks. I’m going to make the script move upwards when it hits a wall then check if a node can exist to the left or right.

Alright it’s been almost two hours and now my Node Graph can work out jumps. I didn’t completely refactor the entire script. I promise.

You’ll notice that the Node Graph doesn’t know how to drop yet, so that’s my next goal. See you in a few hours.

Turns out that was actually a bug causing the Node Graph to not drop. Some extra jump nodes are being added as a result of fixing that bug, so I need to fix the extra jump nodes now. The Node Graph was also looping back on itself, so I made sure to only process a single location once by using a Dictionary with the key as the Vector3 of the node.

After a lot of fan-dangling I managed to remove the extra nodes. Now my NodeGraph can be used to calculate a path. First I need to link the Nodes together. I’ll adjust the Node generation script to also create links other Nodes while they are being propagated. I’ll represent connections with lines.

Now all my nodes are connected in a meaningful way. At this point I should be able to program a navigator. I’ll start by making a script that calculates the start and end node of the path based on the position of some new start and end targets.

And that’s done! I even added a dirty flag so this is only calculated if the positions change. Now I need to use the previously created links to generate a path. I think I could implement A* to do this but for now I’m going to KISS and just get the next nearest node to the target.

Now we’re rolling. That’s the path calculated. No time to celebrate, we need to get a character moving along this path. I’m going to drop in the CharacterController I use for the player then create a script that can follow this path. #therestofthefuckingowl

After a few hours of debugging and optimization I have an AI character that can mostly follow the player around this relatively simple terrain.

It's amazing how effective this pathing is. It can't figure out complex jumps yet or calculate multiple paths but the player is still hard pressed to find a location the AI can't reach.

More later!