by date
Plan for Justin Mette
Plan for Justin Mette
| Name: | Justin Mette |  |
|---|---|---|
| Date Posted: | Jun 15, 2004 | |
| Rating: |  4.3 out of 5 | |
| Public: | YES | |
| Comments: | YES | |
| RSS Feed: |  or Subscribe with  . | |
| Profile Page: | View profile page for Justin Mette |
Blog post
Torque AI
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?
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!| Davis Ray Sickmon, Jr (Jun 15, 2004 at 04:31 GMT) |
| Ian Roach (Jun 15, 2004 at 04:39 GMT) |
| Eric Forhan (Jun 15, 2004 at 04:44 GMT) |
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
| Josh Williams (Jun 15, 2004 at 05:24 GMT) |
| X-Tatic (Jun 15, 2004 at 05:51 GMT) |
| Jorgen Ewelonn (Jun 15, 2004 at 06:32 GMT) |
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!
| Steven Jackson (Jun 15, 2004 at 06:34 GMT) |
| Thomas "Man of Ice" Lund (Jun 15, 2004 at 07:32 GMT) |
| Torsten Schneider (Jun 15, 2004 at 07:55 GMT) |
| Marco Meier (Jun 15, 2004 at 10:19 GMT) |
This would be a fantastic pack. Go for it!
| Stefan Beffy Moises (Jun 15, 2004 at 10:27 GMT) |
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
| Alexander "taualex" Gaevoy (Jun 15, 2004 at 10:34 GMT) |
| Michael Cozzolino (Jun 15, 2004 at 11:02 GMT) Resource Rating: 5 |
| David Dougher (Jun 15, 2004 at 12:49 GMT) |
| Justin Mette (Jun 15, 2004 at 12:58 GMT) |
| Justin Mette (Jun 15, 2004 at 13:13 GMT) |
Edited on Jun 15, 2004 13:16 GMT
| Nick Zafiris (Jun 15, 2004 at 13:44 GMT) |
| Josh Albrecht (Jun 15, 2004 at 13:52 GMT) |
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
Edited on Jun 15, 2004 13:58 GMT
| Justin Mette (Jun 15, 2004 at 14:15 GMT) |
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.
| Phil Carlisle (Jun 15, 2004 at 15:04 GMT) |
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.
| monki (Wesley Beary) (Jun 15, 2004 at 16:58 GMT) |
| Josh Albrecht (Jun 15, 2004 at 17:33 GMT) |
However, that experience of creating the system was the important thing to me. I AM a student, and I plan on doing AI research after I graduate, so whether I created something totally new, or just totally new to me is kind of irrelevant from my perspective. The questions that I had to ponder and the obstacles that I had to overcome have given me a ton of firsthand experience in AI programming. I've done a ton of research, both before starting my system and while I was coding it, that allowed me to learn alot of cool things I never would have been exposed to otherwise. So it's been a worthwhile experience, and maybe, just maybe, I did make something useful. But probably not, and that's ok too! :)
| Luke *V8motorhead* Jones (Jun 15, 2004 at 21:35 GMT) |
And yes, if you have put that much effort into it and want to reward yourselves somehow, a Bot Pack (AI Pack?) would be a good way to do it.
| Jon Britton (Jun 25, 2004 at 22:22 GMT) |
| Justin Mette (Jun 26, 2004 at 11:53 GMT) |
| Jon Britton (Jun 26, 2004 at 18:40 GMT) |
| Tim Muenstermann (Jul 12, 2004 at 23:17 GMT) Resource Rating: 5 |
| Michael Loftis (Aug 05, 2004 at 21:45 GMT) |
| Jason Granum (Dec 08, 2004 at 04:38 GMT) |
| Justin Mette (Dec 08, 2004 at 12:48 GMT) |
| Nick Zafiris (Dec 08, 2004 at 13:09 GMT) |
| Chad Compton (Dec 13, 2004 at 12:08 GMT) |
| Pete (Dec 27, 2004 at 12:58 GMT) |
| Justin Mette (Jan 07, 2005 at 11:36 GMT) |
| Romano Del Vecchio (Feb 18, 2005 at 18:24 GMT) |
| Ed Johnson (Mar 12, 2005 at 00:38 GMT) |
YES!!! YES I WILL BUY IT!!! PLEAAASE RELEASE THIS!!!
*throws money and naked women at you*
| Treb Connell(formerlyMasterTreb) (Mar 12, 2005 at 00:53 GMT) |
| arda (Mar 17, 2005 at 22:51 GMT) |
*Another customer*
| Ed Johnson (Mar 21, 2005 at 22:15 GMT) |
Quote:
It'll give life to TGE
Literally.
| James Olomos (Jun 18, 2005 at 18:20 GMT) |
Any news on a release date?
| Tim Muenstermann (Jul 25, 2005 at 19:14 GMT) Resource Rating: 5 |
Tim
| Denis Linardic (Nov 08, 2005 at 18:34 GMT) |
| Jason Granum (Nov 08, 2005 at 19:20 GMT) |
| Justin Mette (Nov 09, 2005 at 16:07 GMT) |
| Jason Granum (Nov 09, 2005 at 17:31 GMT) |
| Denis Linardic (Nov 11, 2005 at 10:47 GMT) |
If you find some extra time drop us some info ocasionally ;)
| Ashley Kelley (Nov 22, 2005 at 02:20 GMT) Resource Rating: 5 |
| Luke (Soul) Horobin (Jan 16, 2006 at 16:55 GMT) |
| Jorgen Ewelonn (Jan 16, 2006 at 18:34 GMT) |
Edited on Jan 16, 2006 18:40 GMT
| Tom (Sep 01, 2006 at 15:51 GMT) |
seems like another purchase is in order ;)
truely awesome, good job u 2!
| Robert Wyatt (Nov 15, 2006 at 15:10 GMT) |
| Gurpreet Nijjar (Apr 02, 2007 at 05:36 GMT) |
if so, does it have pathfinding, and collision working?
thanks in advance
| Tahlilgarantadbir (May 09, 2007 at 11:48 GMT) |
just a question !
how could you raycast in an interior ?
i am using radiussearch but in an interior always return the interior that within .
how can i get the position of point that near the wall .
| Javier Canon (Nov 06, 2007 at 00:06 GMT) |
You must be a member and be logged in to either append comments or rate this resource.
