Sign in to follow this  
  • entries
    235
  • comments
    509
  • views
    172053

Final Navigation

Sign in to follow this  

68 views

Well, looks like I finally nailed the navigation system. I re-wrote it last night to actuall sweep spheres through the level instead of trying to estimate walkability. It's times like these that make we wish I had restricted the game to be tile-based...

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 :

Sign in to follow this  


4 Comments


Recommended Comments

Guest Anonymous Poster

Posted

Heh some bugs sure are nasty, because they seem to be working pretty fine in some cases but its just because of coincidence! And its very true that it takes a lot of time just to find out where to set a breakpoint. Its worse working on an embedded system with bad tools when such cases arise!

Sometimes if a function becomes too large I try to create blocks inside that. So that some variables are accessible throughout the function and some are only local to certain blocks - as its not always possible to split some big functions into smaller ones, I mean we could, but it could have an ugly number of parameters.

Also I like how you constantly visualize the stuff.

Share this comment


Link to comment
Those are some of the worst bugs to uncover. Just the other day when I was implementing geomipmapping we ran into the same problems. After refactoring the code a few times, we left some unused variables around and after the refactor some of the variable names didn't make sense.

It wasn't until we went back and cleaned up the variable names did we resolve some of the bugs. I'm glad you got that cleared up though.

All in all, how is the path finding going, are most of the bugs worked out of the system, or are there still problems?

- Dave

Share this comment


Link to comment
Of course, after fixing the bugs the other day, I managed to introduce some latent bugs while trying various solutions to the first bug.

I still have a very few issues, but it works on the tower level, with all of the vertical stairs, as well as the more flat areas.

One trick I added today was a distance cost penalty to the a* for vertical movements. This was to prevent the A* from going up small inclines that were unnatural ( like cutting across the base of a pillar ).

I tried this before, and what I found is that if you have a ramp or stairs, it would force the A* to check every conceivable area below the ramp before going directly up the ramp to the player. So, what I did was only apply the penalty if the node you're estimating the cost to is less than 5 meters away. That way, it applies it only for local decisions, and not for global ones. Seems to make more natural paths without exploring the whole map.

During a demo I gave today, I did manage to get one of my enemies stuck near a fallen pillar, so I still need to sort that out, but it feels much more solid.

Another thing I removed was the entity steering. I allow the enemies to move in any direction, irrespective of their facing. This is the same as the player character. The facing is merely a weighted average of the old facing and the new desired velocity, weighted by the distance to the next node. This way they appear to turn, without getting stuck or taking corners to tight and falling into pits.

I also made the entities slow down during path node changes, which looks a bit more natural as well.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now