Plan for Justin Mette
by Justin Mette · 06/15/2004 (4:23 am) · 55 comments
There's been a lot of .plans lately from the Torque AI team talking about all the gory details of our progress. I thought I would take a moment to recap how we got to this point because it's kind of a fun story.
The whole thing started back in August (or so) when 21-6 was working on a now defunct project called Incursion which was a pretty traditional FPS using the whole alien vs marine theme. As part of the project, we needed to add some more intelligent AI so that the bots could do more than run from point A to point B and hope the enemy was within range.
I started expanding the AI in Torque to follow the path between a series of waypoints defined by the level designer using a few updates to the Torque editor for placing and linking waypoints. The bot would choose a nearby enemy and follow the path to get as close as possible, firing its weapon when within range.
This worked pretty well at first, however after jumping in and fighting the bots for a while, I realized rather quickly that manually placing and linking these waypoints was going to be a major pain in the butt for a level designer especially on more complex levels. I also realized that it was way too easy for the bot to get off the waypoint path from explosions, collisions with other players, etc. Once off the path, the bots really couldn't reliably get back on it. For example falling off a bridge or having a large tree in its path caused the bot to be hopelessly lost.
Then one morning I had the idea to automatically generate a graph of connected nodes around the terrain that the bots could use to navigate back on to the pre-defined routes. I started with brute force, shooting raycasts from the sky down to the terrain at regular intervals and linking them together with a quick distance check algorithm.
Ah yes, this was working out nicely as the bots were able to find their way back to the route with a light-weight path finding algorithm I snagged off the net. We were cooking with gas and loving it ... until Chris came up with a sweet multi-level interior complete with stairs, ramps, bridges, etc. Although it was cool to watch the bots patrol through the new interior the NavGraph was a total mess inside the interior and bots were getting stuck everywhere.
Back to the drawing board I went trying to improve the NavGraph generation process to handle complex, multi-level interiors. Using the basic raycast algorithm described earlier, I extended it to find the ceilings and floors of every level in the interior.
I was so very proud of my fancy new NavGraph (how geeky) that I quickly started fighting our beloved bots yet again only to find that they continued to get stuck on crates, stairs, and pretty much any obstacle in their path whenever they strayed from the pre-defined routes.
Talk about doing this the hard way. We really didn't have the intention of building this complex AI system but at each evolution it became more and more evident that quick answers weren't going to cut it. We needed to bring in the big guns namingly A* path finding. Now that we had a pretty decent graph of connected nodes, we really didn't need those pre-defined waypoint routes to get around if we had a good path finding system.
So off I went to go learn A*. This was a fun little project and I learned a lot like how expensive it was to do A* with complex navigation graphs. The first implementations were extremely memory intensive and slow as hell. That's when I got all warm and fuzzy with the Torque Profiler which pointed me in the direction of the bottlenecks. More reading and weeks of optimizations later the A* algorithm ended up being pretty fast and even distributed over multiple "think ticks" to help balance the load of many bots path finding at once.
Ah finally, a good solid path finding foundation. Now it was finally time to fight that damn Orc and show him who is boss! But alas, the bots were still getting stuck and couldn't handle getting in and out of interiors very well especially for those that were rotated or scaled in the mission environment. "You have to be kidding me..." I said as I stared at the problem areas of the FPS Starter Kit mission.
The next few weeks were spent refining (yet again) the generation of the NavGraph. Improvements included generating nodes for interiors in local space so that regardless of their rotation in the mission, the nodes were always in the same place. Also, a more dense series of nodes needed to be placed around the interiors to help the bots find their way in and out of the doors.
These improvements and others actually resulted in a pretty solid experience. I implemented a quick "follow mode" for the bots and armed them with weapons. They actually were chasing me in and out of the interiors, up stairs, cutting me off on the opposite side of bridges, etc in other words, the bots were starting to give me a challenge.
It was about this time that Stefan "Beffy" Moises and Phil Carlisle started posting more about their work on AI for Torque. They were coming at the problem from a different angle dealing with real-time steering (obstacle avoidance) and behaviors (patrolling, chasing, fleeing, etc). I knew I had a good path finding foundation but had not really even started on the higher level functions. It was a perfect match of code, skills, and vision between the three of us.
After getting acquainted with each other's work, we decided that combining forces was the best way to get all this work done in a timely manner. So Stefan took over for me with the foundational aspects of automatic NavGraph generation, path finding, and obstacle avoidance. He has been extending that functionality in fantastic ways like node occlusion brushes, terrain material occlusion, and fixes for many of the problems that were yet to be solved when I worked on the code.
Stefan's Recent Related Plans
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5824
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5716
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5687
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5673
Knowing that we had a good foundation of path finding, Phil has been implementing the higher level brain functions for the bots using a task/action system giving the bot programmers complete script-level access to all functionality. In other words, the final piece to this long and winding road.
Phil's Recent Related Plans
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5842
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5814
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5727
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5699
We still had one area of the project that wasn't covered which is editor support for viewing and manipulating the NavGraph as well as defining the tasks and actions for each bot to obey. Thankfully, Nicolas Quijano jumped into IRC one day to ask if he could help with the project. Ah Nicolas, what timing indeed! Expect to see some .plans from Nic in the near future showing off his work on the project.
So what is my role on the project now? Basically to make sure that we keep the scope of the project reasonable, make sure everyone is moving forward without obstacles, and lending assistance to the technical brainstorming sessions on how to solve the problems we still face in reaching our goals (see recent .plans from Stefan and Phil for more details there).
All in all, we have a rock solid team of experienced Torque programmers working on this project and I am honored to be in such great company.
We meet every week, Thursday at 12PM EST in #torqueai on the irc.maxgaming.net servers. If anyone is interested in learning more about our progress, please don't hesitate to drop in and ask questions or lend some brain power to the effort.
What's next for the Torque AI team? Well, we are considering taking all these months of work and putting it into a "Bot Pack" for FPS style games that would be sold here on GG like other content packs. This won't be an end-all-be-all solution because most higher-level AI is very game specific. What it will provide is a foundation for an FPS game that can be built upon very quickly leaving the majority of the work to programming the game-specific intelligence for bots.
What do you all think would you buy a Bot Pack that had an automatically generated navigation graph, distributed and optimized A* path finding, a fully scriptable behavior framework, and editor support?
The whole thing started back in August (or so) when 21-6 was working on a now defunct project called Incursion which was a pretty traditional FPS using the whole alien vs marine theme. As part of the project, we needed to add some more intelligent AI so that the bots could do more than run from point A to point B and hope the enemy was within range.
I started expanding the AI in Torque to follow the path between a series of waypoints defined by the level designer using a few updates to the Torque editor for placing and linking waypoints. The bot would choose a nearby enemy and follow the path to get as close as possible, firing its weapon when within range.
This worked pretty well at first, however after jumping in and fighting the bots for a while, I realized rather quickly that manually placing and linking these waypoints was going to be a major pain in the butt for a level designer especially on more complex levels. I also realized that it was way too easy for the bot to get off the waypoint path from explosions, collisions with other players, etc. Once off the path, the bots really couldn't reliably get back on it. For example falling off a bridge or having a large tree in its path caused the bot to be hopelessly lost.
Then one morning I had the idea to automatically generate a graph of connected nodes around the terrain that the bots could use to navigate back on to the pre-defined routes. I started with brute force, shooting raycasts from the sky down to the terrain at regular intervals and linking them together with a quick distance check algorithm.
Ah yes, this was working out nicely as the bots were able to find their way back to the route with a light-weight path finding algorithm I snagged off the net. We were cooking with gas and loving it ... until Chris came up with a sweet multi-level interior complete with stairs, ramps, bridges, etc. Although it was cool to watch the bots patrol through the new interior the NavGraph was a total mess inside the interior and bots were getting stuck everywhere.
Back to the drawing board I went trying to improve the NavGraph generation process to handle complex, multi-level interiors. Using the basic raycast algorithm described earlier, I extended it to find the ceilings and floors of every level in the interior.
I was so very proud of my fancy new NavGraph (how geeky) that I quickly started fighting our beloved bots yet again only to find that they continued to get stuck on crates, stairs, and pretty much any obstacle in their path whenever they strayed from the pre-defined routes.
Talk about doing this the hard way. We really didn't have the intention of building this complex AI system but at each evolution it became more and more evident that quick answers weren't going to cut it. We needed to bring in the big guns namingly A* path finding. Now that we had a pretty decent graph of connected nodes, we really didn't need those pre-defined waypoint routes to get around if we had a good path finding system.
So off I went to go learn A*. This was a fun little project and I learned a lot like how expensive it was to do A* with complex navigation graphs. The first implementations were extremely memory intensive and slow as hell. That's when I got all warm and fuzzy with the Torque Profiler which pointed me in the direction of the bottlenecks. More reading and weeks of optimizations later the A* algorithm ended up being pretty fast and even distributed over multiple "think ticks" to help balance the load of many bots path finding at once.
Ah finally, a good solid path finding foundation. Now it was finally time to fight that damn Orc and show him who is boss! But alas, the bots were still getting stuck and couldn't handle getting in and out of interiors very well especially for those that were rotated or scaled in the mission environment. "You have to be kidding me..." I said as I stared at the problem areas of the FPS Starter Kit mission.
The next few weeks were spent refining (yet again) the generation of the NavGraph. Improvements included generating nodes for interiors in local space so that regardless of their rotation in the mission, the nodes were always in the same place. Also, a more dense series of nodes needed to be placed around the interiors to help the bots find their way in and out of the doors.
These improvements and others actually resulted in a pretty solid experience. I implemented a quick "follow mode" for the bots and armed them with weapons. They actually were chasing me in and out of the interiors, up stairs, cutting me off on the opposite side of bridges, etc in other words, the bots were starting to give me a challenge.
It was about this time that Stefan "Beffy" Moises and Phil Carlisle started posting more about their work on AI for Torque. They were coming at the problem from a different angle dealing with real-time steering (obstacle avoidance) and behaviors (patrolling, chasing, fleeing, etc). I knew I had a good path finding foundation but had not really even started on the higher level functions. It was a perfect match of code, skills, and vision between the three of us.
After getting acquainted with each other's work, we decided that combining forces was the best way to get all this work done in a timely manner. So Stefan took over for me with the foundational aspects of automatic NavGraph generation, path finding, and obstacle avoidance. He has been extending that functionality in fantastic ways like node occlusion brushes, terrain material occlusion, and fixes for many of the problems that were yet to be solved when I worked on the code.
Stefan's Recent Related Plans
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5824
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5716
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5687
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5673
Knowing that we had a good foundation of path finding, Phil has been implementing the higher level brain functions for the bots using a task/action system giving the bot programmers complete script-level access to all functionality. In other words, the final piece to this long and winding road.
Phil's Recent Related Plans
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5842
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5814
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5727
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=5699
We still had one area of the project that wasn't covered which is editor support for viewing and manipulating the NavGraph as well as defining the tasks and actions for each bot to obey. Thankfully, Nicolas Quijano jumped into IRC one day to ask if he could help with the project. Ah Nicolas, what timing indeed! Expect to see some .plans from Nic in the near future showing off his work on the project.
So what is my role on the project now? Basically to make sure that we keep the scope of the project reasonable, make sure everyone is moving forward without obstacles, and lending assistance to the technical brainstorming sessions on how to solve the problems we still face in reaching our goals (see recent .plans from Stefan and Phil for more details there).
All in all, we have a rock solid team of experienced Torque programmers working on this project and I am honored to be in such great company.
We meet every week, Thursday at 12PM EST in #torqueai on the irc.maxgaming.net servers. If anyone is interested in learning more about our progress, please don't hesitate to drop in and ask questions or lend some brain power to the effort.
What's next for the Torque AI team? Well, we are considering taking all these months of work and putting it into a "Bot Pack" for FPS style games that would be sold here on GG like other content packs. This won't be an end-all-be-all solution because most higher-level AI is very game specific. What it will provide is a foundation for an FPS game that can be built upon very quickly leaving the majority of the work to programming the game-specific intelligence for bots.
What do you all think would you buy a Bot Pack that had an automatically generated navigation graph, distributed and optimized A* path finding, a fully scriptable behavior framework, and editor support?
About the author
Recent Blogs
• Players Choice Awards• TubeTwist-iness
• Plan for Justin Mette
• Plan for Justin Mette
• Plan for Justin Mette
#3
Content packs such as these are the way to go, IMHO. Rather than have one Godzilla of an engine to work with, we will be able to pick and choose what we need to help speed along the creation of our Frankenstein's monster. And with this AI pack, we almost truly can say, "It's alive! It's alive!" ;)
Really, it sounds like you guys have put in some long hours and are coming up with something solid. If creating a content pack means you'll get some return on your work (other than your own projects), and that odds are better of it staying more up-to-date (unlike so many freebies that have fallen by the wayside), I'm all for it. Good luck!
-Eric
06/15/2004 (4:44 am)
I agree with Davis... thanks for the synopsis. :)Content packs such as these are the way to go, IMHO. Rather than have one Godzilla of an engine to work with, we will be able to pick and choose what we need to help speed along the creation of our Frankenstein's monster. And with this AI pack, we almost truly can say, "It's alive! It's alive!" ;)
Really, it sounds like you guys have put in some long hours and are coming up with something solid. If creating a content pack means you'll get some return on your work (other than your own projects), and that odds are better of it staying more up-to-date (unlike so many freebies that have fallen by the wayside), I'm all for it. Good luck!
-Eric
#4
06/15/2004 (5:24 am)
I think the stuff you guys are working on definitely would make sense as a code pack. Go for it!
#6
A big thank you is also in place here.
As a general designer it is a relief to not having to worry about these complex aspects of the creation process. Buy the AI extension, plug it in and start designing around it. That would really speed up the progress of my project.
This takes alot of stress away from me... thx guys!
06/15/2004 (6:32 am)
I would buy it in a heartbeat!! This is great... to good to be true actually!!A big thank you is also in place here.
As a general designer it is a relief to not having to worry about these complex aspects of the creation process. Buy the AI extension, plug it in and start designing around it. That would really speed up the progress of my project.
This takes alot of stress away from me... thx guys!
#7
06/15/2004 (6:34 am)
Count me in. I'd definitely buy this - saves me tons of time with the effort you guys have put into this.
#8
06/15/2004 (7:32 am)
Yep - another customer here
#9
06/15/2004 (7:55 am)
Me too.
#10
This would be a fantastic pack. Go for it!
06/15/2004 (10:19 am)
great .plan and great work! This is awesome.This would be a fantastic pack. Go for it!
#11
Really glad you guys like that whole pack idea :)
To concentrate feedback and to collect some requirements and additional ideas and requests I have created a forum thread where you can post if you like :)
Check it out here: www.garagegames.com/mg/forums/result.thread.php?qt=19187
06/15/2004 (10:27 am)
Awesome .plan Justin! those old pics are new to me, too - cool to see how it all evolved! Really glad you guys like that whole pack idea :)
To concentrate feedback and to collect some requirements and additional ideas and requests I have created a forum thread where you can post if you like :)
Check it out here: www.garagegames.com/mg/forums/result.thread.php?qt=19187
#12
06/15/2004 (10:34 am)
I would buy it too. ;) looks promissing! 
#13
06/15/2004 (11:02 am)
Hell yeah I would buy. 
#14
06/15/2004 (12:49 pm)
Would I buy it? Is the Pope Polish? Reaches for credit card... How much?
#15
06/15/2004 (12:58 pm)
Wow, I wrote this just before I went to bed. I get up this morning and there are all these great comments. Thanks everyone for your support on the Bot Pack - we are all fired up now!
#16
06/15/2004 (1:13 pm)
I should also mention that starting this week, we will get more serious about the sellable Bot Pack with regards to figuring out a timeline for completion, price, code integration, maintenance, etc. Expect to hear more from us on these fronts as the project progresses - I'm sure we will need your opinions on how best to proceed.
#17
06/15/2004 (1:44 pm)
I would definitaly buy it! Just make it quick:)
#18
Yours is a much more 'traditional' system than mine... I invented my algorithm from scratch. It seems to work flawlessly now though, and I'm only missing a few minor features, like the ability for bots to find strange paths that requrie them to crouch or jump, and the ability for them to navigate through multilevel buildings (this will be very easy to add given the way my system is set up).
I also have the ability to dynamically find cover from enemies, and a tool for editing the pathfinding info in the mission editor, and of course a few minor modifications to the max2map editor to allow easy automated creation of the pathfinding information.
I dont plan on selling my system, and I dont mean to steal buisness from you Justin, but I already planned on releasing this as a rather disgustingly large resource to a few people at first who would be willing to implement it with their games, and tell me what bugs they encounter. I will in turn fix them, and then probably release it as a full fledged resourec once I feel it is stable.
Would anyone be interested in helping my test this system?
I'm not quite ready to test it yet (the code is ready, but I havent made any patch files or documentation other than the exisiting comments), but I should be ready within a month or so. Email me at the email in my profile with the topic: GarageGames
06/15/2004 (1:52 pm)
Well, I've actually been working on the same thing as you guys (AI/pathfinding) and coming at it from yet ANOTHER completely different angle. I doubt you will find it very useful, but I'll try to stop by the IRC channel this week to really talk to you guys about it. I am also curious to see how my system compares against yours Yours is a much more 'traditional' system than mine... I invented my algorithm from scratch. It seems to work flawlessly now though, and I'm only missing a few minor features, like the ability for bots to find strange paths that requrie them to crouch or jump, and the ability for them to navigate through multilevel buildings (this will be very easy to add given the way my system is set up).
I also have the ability to dynamically find cover from enemies, and a tool for editing the pathfinding info in the mission editor, and of course a few minor modifications to the max2map editor to allow easy automated creation of the pathfinding information.
I dont plan on selling my system, and I dont mean to steal buisness from you Justin, but I already planned on releasing this as a rather disgustingly large resource to a few people at first who would be willing to implement it with their games, and tell me what bugs they encounter. I will in turn fix them, and then probably release it as a full fledged resourec once I feel it is stable.
Would anyone be interested in helping my test this system?
I'm not quite ready to test it yet (the code is ready, but I havent made any patch files or documentation other than the exisiting comments), but I should be ready within a month or so. Email me at the email in my profile with the topic: GarageGames
#19
That said, we are always interested in new ideas and your "from scrath" solution does sound intriguing. Please do drop by the channel and fill us in.
06/15/2004 (2:15 pm)
Josh, don't worry - you won't steal our business. Our "traditional" approach to AI uses techniques (like A* path finding) that are tried and true in the industry. There are many great books written that teach different AI techniques built upon these "traditional" algorithms - which allows the user of the Bot Pack to more easily extend the system to fit their game.That said, we are always interested in new ideas and your "from scrath" solution does sound intriguing. Please do drop by the channel and fill us in.
#20
I'm not trying to have a go, but as a lecturer this kind of statement irritates me (because students use it) mainly because what you might have "invented" is something we might already know by another name.
06/15/2004 (3:04 pm)
Josh, you surely should know by now that almost any algorithm "invented by scratch" has probably been re-hashed many many times under some other name.I'm not trying to have a go, but as a lecturer this kind of statement irritates me (because students use it) mainly because what you might have "invented" is something we might already know by another name.
Torque Owner Davis Ray Sickmon, Jr