Plan for Gary Haussmann

With all the AI-related posts in the last month, I figured I should throw this up. I figured it was time to make my AI navigation a little better than the "head straight for the target" method used by AIPlayer. I originally tried a dynamic reactive system, where the AIplayer would shoot out several rays each tick and run around walls, but that eats up a lot of processor cycles and only works for simple obstacles. So of course I had to switch to using precomputed navigation graphs and A* code...

I wanted to avoid having to place waypoints manually so my method is very similar to that of other navigation methods you've seen in GG plans, such as Justin Mette's navmesh code. In my setup the level designer slaps down a single node somewhere, typically in the center of the mission area or at a spawn point. The generator will then try to find all the places that are reachable from that point, basically by doing simple "can I walk from here to here?" queries over and over again between nearby points. The drawback is that places you can't get to by walking are not examined, so elevators and teleporters will screw it up. For simple levels it seems to work quite well, though. The mesh node spacing is smaller in areas near interiors while it is quite coarse in the big open terrain areas.


Of course, on top of this navigation graph is the A* algorithm. If no path is found using A* the move behavior falls back on the "go straight at the target" method. It needs some polish, like an actual priority queue in the open list and perhaps some path smoothing, but it is loads better than the previous garbage I had written. Now I just need to write up some code that figures out when to properly recompute the path from start to destination.