Plan for Justin Mette
by Justin Mette · 03/15/2004 (8:42 am) · 28 comments
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...
About the author
Recent Blogs
• Defense Net• Players Choice Awards
• TubeTwist-iness
• Plan for Justin Mette
• Plan for Justin Mette
#3
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!
03/15/2004 (11:38 am)
Very cool! I now have all sorts of game ideas popping through my head about what to do with something like this =)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!
#4
- Brett
03/15/2004 (12:22 pm)
I like what I see! This will make AI work much cleaner for people. Now, the hardest part (of course) will be translating all this good work into 3 dimensions... Or am I missing something? Right now, it would appear that most navigation is done as Forward/Backward, Left/Right. It'll be interesting to see how someone applies this to 3D like a flight sim or space combat game (hint hint)..- Brett
#5
03/15/2004 (3:13 pm)
Since Phil is probably going to use this stuff for his space game, too, he/we will probably have to get everything (well, not everything, but at least *something*... :P) working for 3 dimensions... not really sure about the pathfinding in 3D (especially for air/space situations...), but at least basic steering and of course goal oriented action planning / task management etc. 
#6
03/15/2004 (5:18 pm)
Very Cool guys, I will try to pop in the chat and help in any way I can.
#7
03/15/2004 (10:04 pm)
this sounds great!
#8
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.
03/16/2004 (2:59 am)
Wow, astounding!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.
#9
03/16/2004 (11:04 am)
Awesome, we need this!
#10
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 :))
03/18/2004 (12:00 pm)
@Luigi: yeah, I've heard of PathEngine, but I think I've read somewhere that it's kinda expensive (like a couple of 1000$ or even 10.000s), not sure... did you already buy it or do you get the whole SDK with the evaluation version?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 :))
#11
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!
03/18/2004 (3:49 pm)
Thomas Young, the developer behind PathEngine, is lenient with indies but the price is still high for a self funded team. He'll accept an initial downpayment on the commercial license (which is around 9000 euros in total) of a couple thousand euros. He's very competent and supportive, if you have the funds PathEngine is an excellent solution. We've got an evaluation license for CSB and it's working out nicely (you do need to build the groundmeshes manually though, we've added .lwo exporting to map2dif which allows you to build the groundmeshes over the building in lightwave) however PathEngine is capable of connecting the individual groundmeshes automatically to the terrain constructing one large connected mission groundmesh.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!
#12
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?
03/19/2004 (9:41 pm)
I was reading about optimizing navigation meshes in "AI Game Programming Wisdom" (highly recomended book).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?
#13
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.
03/21/2004 (5:02 am)
Ben - that sounds like a great approach even to just culling nodes out of the graph that are in a region with similar node normals. I'm trying to work on reducing memory use because the current NavGraph for the Stronghold mission is like 6MB - and can be much bigger for more complex missions. The memory used by the path finding routines also grows pretty fast when there are alot of nodes in the graph. Anyway, culling nodes is my next task and using the region concept may just work out - thanks!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.
#14
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?
04/01/2004 (3:58 am)
I was wondering how big is too big for the navigation mesh. 6MB doesn't seem too big for the average game PC with 256 MB RAM. Also, I think using more memory might be better if it improves the CPU performance of the algorithm.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?
#15
struct AINavNode
{
U32 id;
Point3F position;
Point3F normal;
S32 type;
Vector 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.
04/02/2004 (5:12 am)
Here is structure I'm using to store each node in the graph:struct AINavNode
{
U32 id;
Point3F position;
Point3F normal;
S32 type;
Vector
};
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.
#16
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*.
04/05/2004 (6:26 pm)
Just a thought. You could shave a little memory off by getting rid of AINavNode::id. AINavNode already has a unique identifier, its pointer. Pointers are 32 bits, so using pointers as IDs shouldn't affect the size of the links.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*.
#18
04/06/2004 (6:04 am)
You can save .9 MB just by using U16 id instead of U32 id (unless you need more than 2^16 nods).
#19
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 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 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 links; // can this be made a vector of U16s?
}
And then use logical-AND to extract type or ID.
Also, if the Vector 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 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.
04/07/2004 (2:28 am)
Actually he can't. If he changes the "U32 id" to "U16 id" then the compiler will do one of two things depending on compiler switches. a) It will pad the U16 with two blank bytes so that the Point3F is properly aligned on a 32-bit boundary, or b) It will make all of the following structure members mis-aligned and therefore generate an alignment fault in the CPU. Depending on the architecture of the CPU it will either have to make two 16-bit memory retrievals and then patch them together, thereby taking multiple lookups and instructions to achieve this, or it will do a mis-aligned 32-bit read, which is a performance hit. This is even worse on a 64-bit CPU than performing two 16-bit reads.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
U16 id;
}
Or
struct AllNavNode
{
U16 id;
U16 type; // if you only have 2^16 types
Point3F position;
Point3F normal;
Vector
}
Or
struct AllNavNode
{
U32 type_and_id; // top 8 bits are the type, lower 24 bits are the id
Point3F position;
Point3F normal;
Vector
}
And then use logical-AND to extract type or ID.
Also, if the Vector
Vector
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.
#20
04/07/2004 (2:35 am)
As one final optimisation note, almost all the normals for a mesh will fall within some fixed range, lots of 15 degree slopes inside of buildings, lots of flat surfaces. By using either a 16-bit or 32-bit index as a lookup into a table of normals the 12-bytes for the Point3F normal could be drastically reduced. I used this exact same trick for a certain PlayStation 2 surfing game. The normals could also be quantised to 24-bits or less by the simple fact that most path-finding does not require a 12-byte normal to operate effectively -- not many games require a bot to run around on vertical walls or upside down on the ceiling. 
Torque 3D Owner Phil Carlisle
Have to think about it I guess :)