Plan for Justin Mette

Matthew Fairfax has been inspiring me to write more about some of the cool technical stuff we are working on here at 21-6. His .plans are always so cool to read and include fun screen shots. I'm going to follow suit.

Over the past 3 months or so, I've been working on teaching bots how to navigate Torque missions using a combination of an auto-generated navigation graph and A* path finding. This technology is being developed as part of a project we are working on with GarageGames. Early on in the project, we decided that this AI code should be rolled back into Torque for everyone to benefit from and help evolve.

I had also read that Stefan and Phil were working on some higher level AI code including obstacle avoidance and a task management system. It ends up that they had the same thoughts of integrating their code back into Torque. As we discussed the technologies we had both been developing there was some great alignment in functionality and the two sets of code should fit together nicely, providing a relatively complete solution.

Over the last couple weeks; Rick O has graciously set up a branch of Torque for us to work in, I have ported my code over to this new branch, Stefan is re-working his steering/avoidance code to use the path finding architecture, and Phil is designing the higher level task management system.

Now for some tech-talk!

Navigation Graph
The foundation of "path finding" is a navigation graph, which is essentially a collection of nodes that are linked together to form a grid. Most of the time spent over these last 3 months has been on automatically generating this navigation graph (NavGraph) for a Torque mission.

Auto-generating the NavGraph requires many steps including processing individual interiors (including multi-level), terrain, water, and static objects placed outdoors. Essentially, the algorithm uses a series of ray casts to place nodes throughout the mission area.

Node Generation
Interiors are processed individually in order for node placement to be consistent, regardless of the rotation of the interior in the mission. The terrain around interiors will have tighter node placement than open areas of the terrain in an effort to link entrances of the interior to nearby terrain.


As mentioned earlier, each level of a multi-level interior will be mapped properly. This was tricky to accomplish with ray casts because of solid brushes in an interior. The NavGraph generation process can subsequently take a while to process which is why the graph is cached (much like a .ml lighting file).


Link Generation
The next phase of NavGraph generation deals with linking the nodes together. A series of filters are used to determine whether two nodes should be linked together most have to do with whether a player model can travel from one node to the next unobstructed. There is also a filter that will reject potential links based on their slope which allows you to block off areas of your level from bot navigation using height.

In order to keep the NavGraph simple to navigate, each node will only have 8 links one in each 45 degree quadrant around the node. The final phase of NavGraph generation will go through and filter down links to meet this requirement. The result allows tight and loose grids to be merged together without hundreds of needless links.


Customization
There are going to be many configurable options for NavGraph generation as we have found many parameters to be game-specific. For example, the node placement algorithms currently have a filter that checks to see whether a 2m tall player model can stand on that node unobstructed. If you were making a racing game, this filter would be implemented differently.

To support this level of customization there will be some C++ classes you can derive from and implement game specific features. A great example of these classes would be filters for node placement and link generation.

Path Finding
Implementing A* path finding was actually not that difficult once I learned how the algorithm worked. Instead, most of the time has been spent figuring out how to get the algorithm to perform well when generating long complex paths. I spent many hours with the Torque Profiler to find bottlenecks and fix them. If you don't use the Torque Profiler and are trying to solve performance issues you are missing out on a valuable tool. It really is amazing.


While I'm sure there are many more optimizations that can be made to the current A* implementation, it became obvious that long complex paths were still going to take a while to calculate. Therefore, I also implemented the ability to distribute the processing over time.

Each bot will now calculate a small percentage of the overall path each "tick" that it thinks instead of all at once. This allows many bots to be calculating paths simultaneously without bogging down the CPU.

Just recently, Stefan added the use of splines for the generated paths. This is a great addition. Check out these screen shots.

Follow Mode
To show off all this path finding goodness, I wrote a "follow" mode for the AIPlayer class. The bot will calculate a path to the "follow object" and then start traversing it. Right after the bot calculates the first path and starts moving along it, he immediately starts calculating a new path to the target. When the new path is finally generated, it is merged with the current path. Essentially, the bot is continuously calculating a new path to the target allowing it to follow a moving target.

Summary
A few people have asked when this project will be done; but that's really hard for us to answer. We all are working on other projects that take higher priority and are only working on Torque AI when we can find the time. I would hope that we could have a basic framework in place after a couple of months but that's really speculation at this point.

We will do our best to post progress in .plans throughout the project.

To be continued...