by date
Plan for Justin Mette
Plan for Justin Mette
| Name: | Justin Mette |  |
|---|---|---|
| Date Posted: | Mar 15, 2004 | |
| Rating: |  4.0 out of 5 | |
| Public: | YES | |
| Comments: | YES | |
| RSS Feed: |  or Subscribe with  . | |
| Profile Page: | View profile page for Justin Mette |
Blog post
Torque AI
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...
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...
Recent Blog Posts
| List: | 08/08/06 - Players Choice Awards 02/23/06 - TubeTwist-iness 10/10/05 - Plan for Justin Mette 08/28/05 - Plan for Justin Mette 04/26/05 - Plan for Justin Mette 06/15/04 - Plan for Justin Mette 03/15/04 - Plan for Justin Mette 11/30/03 - Plan for Justin Mette |
|---|
Submit your own resources!| Phil Carlisle (Mar 15, 2004 at 17:44 GMT) |
Have to think about it I guess :)
| Ben Garney (Mar 15, 2004 at 19:03 GMT) |
Wow. This is pretty damn awesome. I am _very_ impressed. :)
| Matt Fairfax (Mar 15, 2004 at 19:38 GMT) |
I guess I'll have to post my AI .plan sooner rather than later =)
I am glad my .plan's can be inspirational to others. I was actually inspired by Brett Fattori's .plan's in turn so we can all blame it on him =)
It costs very little time to make the screenshots and not much more to actually write up the .plan but it can be amazingly inspiring to others to see cool stuff and to yourself to hear positive feedback. In my opinion, well worth the investment!
| Brett Fattori (Mar 15, 2004 at 20:22 GMT) |
- Brett
| Stefan Beffy Moises (Mar 15, 2004 at 23:13 GMT) |
| Anthony Rosenbaum (Mar 16, 2004 at 01:18 GMT) |
| Eric Risser (Mar 16, 2004 at 06:04 GMT) |
| Luigi Rosso (Mar 16, 2004 at 10:59 GMT) |
I've been working on integrating the PathEngine, http://www.pathengine.com/, with Torque for Cyberfuge: Second Battalion. It's powerful, quick, and implements well with Torque (after some work) however it's pricey for us and we're still attempting to allocate funds. This looks like an awesome alternative.
Let me know if you need help, I'd be glad to do anything which can aid in getting this done.
| Trent Reimer (Mar 16, 2004 at 19:04 GMT) |
| Stefan Beffy Moises (Mar 18, 2004 at 20:00 GMT) |
I'm sure this will be an alternative for you, although it might not have all the bells and whistles PathEngine has, but it will be more widespread (Task Management, Behaviours, Steering, ...)
But as Justin said: we'll need some more months to get everything implemented (Justin's pathfinding part is already working great though :))
| Luigi Rosso (Mar 18, 2004 at 23:49 GMT) |
You don't get the full SDK with the evaluation but you get most of it. It's very easy to work with and I'm very impressed with what I've seen so far.
I'd tried out some custom pathfinding implementations previously. We had implemented a pretty solid A* pathfinder but the real bottleneck was locating the best closest node to any random position before performing the pathfinding (I was naively not using any coherence between lookups, which you could make good use of especially with such a tight grid as the one you guys are using).
Splitting the pathfinding proccess into multiple frames is a great idea! Are you using any hierarchical pathfinding to ensure the path is valid before splitting the load off into multiple frames for refinement (so a bot can start travelling before the path is fully refined) or will the bots only start walking a path once it's been fully discovered?
Good luck with your work and, again, if any help is needed, drop me a line!
| Ben Carnes (Mar 20, 2004 at 05:41 GMT) Resource Rating: 5 |
You can optimize a navigation mesh by merging nodes with equivalent normals into bigger convex nodes. The article I read uses different terminology/metaphors than you use, so let me translate that to what your doing here to the best of my understanding.
Each node in your navigation graph can belong to a region. A regoin is a convex grouping of agecent polygons, where a polygon is a triangle bounded by 3 nodes. A region is convex because this ensure that the bot can always travel in a straight line across the region. Also, each polygon in a region has (nearly) the same normal. Once again, this ensures that the bot can travel across the region in a straight line (the cost does not vary over the region).
Regions optimize the navigation graph. If the path does not start or end inside a particular region, only the nodes bordering that region need to be examined (you pretend that there are edges connecting each of the border nodes and skipping over the intermediate nodes).
The has the additional advantage that bots zig-zag less over large flat areas (don't think splines would completely fix this problem).
What do you think?
Also, is there any way we can get your code, even if it is not finished?
Edited on Mar 20, 2004 05:53 GMT
| Justin Mette (Mar 21, 2004 at 13:02 GMT) |
We do probably need to get some folks to help us test this code in their game before we drop it back into Torque. I'll be talking with GG next week at GDC about the procedure for dropping this much code back into Torque - I assume it needs to be tested in a variety of situations first. If so, we will be contacting you and others that are interested.
| Ben Carnes (Apr 01, 2004 at 11:58 GMT) Resource Rating: 5 |
I am currently working on my own navigation mesh and was curious how you represent the navigation mesh in memory. How do you get such a large and detailed nav mesh to fit into 6MB?
| Justin Mette (Apr 02, 2004 at 13:12 GMT) |
struct AINavNode
{
U32 id;
Point3F position;
Point3F normal;
S32 type;
Vector<U32> links;
};
The links vector stores indexes into the array of AINavNode structures.
The stronghold mission currently has 52,941 nodes and 409,302 links adding up to about 6MB. We have some work to do in culling out many of those nodes that are on flat surfaces and what not - which should reduce the memory usage.
| Ben Carnes (Apr 06, 2004 at 01:26 GMT) Resource Rating: 5 |
Using pointers as IDs may also improve the time cost, since you can retrieve a node instantly instead of searching for a node having a particular ID.
When saving or loading the nav graph from cache, you can map between a U32 ID and AINavNode*.
Edited on Apr 06, 2004 01:27 GMT
| Timothy Aste (Apr 06, 2004 at 11:45 GMT) |
| Ben Carnes (Apr 06, 2004 at 13:04 GMT) Resource Rating: 5 |
Edited on Apr 06, 2004 13:04 GMT
| OtakuNoZoku (Apr 07, 2004 at 09:28 GMT) |
Assuming that "ID" is a requirement then my suggestions, if interested in compacting this structure, would be:
struct AllNavNode
{
Point3F position;
Point3F normal;
S32 type;
Vector<U32> links; // can this be made a vector of U16s?
U16 id;
}
Or
struct AllNavNode
{
U16 id;
U16 type; // if you only have 2^16 types
Point3F position;
Point3F normal;
Vector<U32> links; // can this be made a vector of U16s?
}
Or
struct AllNavNode
{
U32 type_and_id; // top 8 bits are the type, lower 24 bits are the id
Point3F position;
Point3F normal;
Vector<U32> links; // can this be made a vector of U16s?
}
And then use logical-AND to extract type or ID.
Also, if the Vector<U32> can be a made to be a pointer to a Vector outside of the structure, with an appropriate counter for the number of links, then there would be a saving in terms of memory allocating to all the Vectors in each structure. e.g.
Vector<U32> NodeLinks ;
struct AllNavNode
{
U32 type_and_id; // top 8 bits are the type, lower 24 bits are the id
Point3F position;
Point3F normal;
U32 offset; // index in to the NodeLinks vector for first index for this node
U16 length; // number of links in the NodeLinks vector that this node references
// number of links could be made a U8
} ;
A further optimisation is possible by then re-arranging the Vector for NodeLinks by determing what links overlap and merging them together. e.g.
Node A has the links 2,3,4,5
Node B has the links 3,4,5,7
Node C has the links 5,7,8,9
Rather than storing these links in three separate Vectors, or storing each group of links in one long vector with no coherency you could interleave the links.
The final link Vector could be compacted as 2,3,4,5,7,8,9 with Node A having the start index of 1 and a length of 4, Node B having a start index of 2, and a length of 4, and Node C having a start index of 4 and a length of 4.
In a grid of links there will be a lot of coherency that allows you to do this overlapping/interleaving technique. A naive algorithm can make a single pass at the overlapping, a complex algorithm would be multiple pass, with several attempts at interleaving different subsets of the Vector to see what returns the maximum amount of groupings.
| OtakuNoZoku (Apr 07, 2004 at 09:35 GMT) |
| OtakuNoZoku (Apr 07, 2004 at 09:36 GMT) |
| Cameron Aycock (Apr 09, 2004 at 15:54 GMT) |
Was that you in the corner in the GG suite at the GDC? (working on the laptop?) I didn't get a chance to meet you. I talked a lot with Rick, and he recommended I get in touch with you guys concerning your AI system. We are working on a game that could make HEAVY use of this system. I was planning on implementing my own, but I hate to re-invent the wheel. Do you guys need any help? If not, I am more than will ing to do some serious testing. I had to break the 1024 object limit for our game, and have plenty of obstacles.
Edited on Apr 09, 2004 15:54 GMT
| Justin Mette (Apr 10, 2004 at 12:41 GMT) |
Cameron - We will be looking for some folks to help test this code out as it will be rolled back into Torque. Right now, I'm working on optimizing the NavGraph, Stefan is working on obstacle avoidance, and Phil is working on the high level "task" system. That said, if you wanted to come into the #torqueai channel on irc.maxgaming.net, the three of us hang out in there regularily and we could talk about your requirements to make sure we are going to solve some of your core issues.
In fact, that invite goes to anyone watching this thread that is interested in learning more and participating ideas to the project.
| Bucko (Apr 19, 2005 at 19:05 GMT) |
| Justin Mette (Apr 19, 2005 at 19:09 GMT) |
| Misifu (Jul 06, 2005 at 11:09 GMT) |
| Tim Muenstermann (Aug 12, 2005 at 20:33 GMT) |
| Bill (Sep 12, 2006 at 05:10 GMT) |
You must be a member and be logged in to either append comments or rate this resource.
