Plan for Justin Mette

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?