I had a bug that was driving me insane. Basically, on very simple levels, the ai navigation code seemed to be working pretty well, with some minor issues. On the tower level, it would only find paths for a small percentage of the level. It seemed that it would find the paths near the character's start position, but then fail to find any more after a certain distance away. This seemed to be why small levels were working, but not bigger ones. Of course, big levels are much harder to debug.
After fixing a logical error this morning with a loop that was causing some invalid paths to be created, I was still stuck with the problem of many valid paths would not be created on the tower level.
This is how I find the walkable areas :
1) I find the character's initial starting point in the level. If it's not near a walkable area, I complain and try the old voxel-based method, that can create some paths that aren't really navigable.
2) This starting point serves as the first valid navigation node, which I push onto a stack of nodes
2) Then, for each node I pop off the stack, I try to physically push it ( using the same physics as the game ) to the next spot to the n,s,e,w,ne,sw,se,nw.
3) I then look to see if it made it to that spot, and if that spot is walkable itself, if so, I push it on the stack as well to check ITS neighbors.
This wasn't working, even though I could clearly manually navigate through the area with the same radius capsule as the test sphere I was using!
I find one of the hardest things with modern games is the sheer amount of data that needs to be sifted through. It is so hard to even find the right spot to set breakpoints at times. I figured the best method in this case would be to visualize the spheres at each test point. As the simulator moved them along, it would drop the sphere position into a vector, and after each step in the search, I would draw the spheres transparently to show the attempted navigation path.
In the process of refactoring the code to support this, I broke apart a rather large function in order to make it handle one node per call, rather than the whole stack. Along the way, I got a compiler error about an unknown variable pNode. In the other parts of the code nearby, I was using pCheck. Turns out I was reusing the wrong variable from the top of the original function for the sphere height.
That was causing the navigation system to only be able to navigate to heights very similar to the initial height. Since small levels also don't have much height variation, they more or less worked, whereas the tower level did not. As soon as I fixed that and then increased the test sphere's velocity enough to allow it to mount stairs better, it started working exactly as expected.
So, what can we learn from this?
1) Don't use generic variable names like pNode. pCheck is better b/c it is the one you are currently checking. pOriginalNode would have made it more obvious as well.
2) Don't have large functions. The larger your function, the greater the number of variables in scope, so the greater chance you may have a variable mis-type go uncaught.
3) Large functions are harder to debug. Prefer solutions that let you do one step at a time with a function call, so you can interrupt & visualize the process.
Here is a stripped-down version of the tower level, showing the proper navigation map.
And finally, a big thanks to those who have commented on my Journal so far. Yesterday the comments helped me find a bug in my camera code that was causing the straight-top-down perspective. The camera is meant to be a bit lower to give more of a sense of depth. Plus, it's nice to know that people are enjoying the journal.
I still need to fix the zooming to take the offset camera into account, so I don't get cool, but confusing shots like this :