Article
i/2008/05/swiss_army_knife

The Little-Used Tools of Game AI

Dave Mark on May 14, 2008

This week’s developer discussion on AiGameDev.com is introduced by Dave Mark from Intrinsic Algorithm. Let him know how many tools you use for your game AI and why; post a comment below or in the forums.

What? No hammer?

I’ve never been the type of guy who can spend all weekend in the garage or the workshop. I am far more likely to linger in the electronics department at the store than I am to sigh wistfully over the endless aisles of power tools. However, like many people, I remember being rather impressed by things such as the almost cliched Swiss Army Knife. Examining one is an adventure of exploration. As you unfold each appendage from it’s slot, there is that moment of curiosity (“What could this be?”), followed by a moment of discovery (“Wow! It’s a corkscrew!”), followed-up by a sense of wonder (“That surgical knife could come in handy!”). It’s only later that a more sobering, pragmatic reality sets in. (“It would certainly suck to try and cut firewood with a 2-inch saw.”) Put into practice, a vast majority of the people use one of the knives and maybe a screwdriver. The rest of the now overly bulky tool is relegated to the “gee whiz” effect wherein you pull out your massive knife and, while exchanging wise, serious nods with your camping buddies, state with grave certainty “it’s nice to have these other tools around just in case I need them.”

Game AI seems to have a similar problem of late. Looking through web sites, books, and the various conferences such as GDC and AIIDE, there is an endless parade of esoteric, seemingly mystical techniques. As perpetual students in our rapidly-changing art, we read and attend with a reverent demeanor of an exploratory scientist. We soak up all the knowledge and ponder the applications and implications. We engage in heady, philosophical discussions with our peers. We exclaim our exuberance and proclaim our allegiance to new methodologies. And then, upon returning home to our individual, pragmatic realities. We resign ourselves to the relatively bland, yet utilitarian knife and screwdriver: Finite State Machines and Pathfinding.

And what of the other tools in the Swiss Army Knife of game AI? What about the planning and fuzzy logic? The lofty towers of neural networks and genetic algorithms? Game theory and reasoning under uncertainty? Influence maps? Minimax plays a killer game of Tic Tac Toe, right? Flocking? We’ve all seen articles on flocking! Not being used? Wow… there sure are a lot of tools in this knife. We can all see places where they may come in handy. Granted, some of them may be like trying to cut firewood with a 2-inch saw - but aren’t some of them truly useful? So why don’t we use them in the real world of creating our pretend worlds rather than simply pretending we are going to use them in the real world?

GDC AI Roundtable - Day 2

Photo 1: The subjects of the informal poll at the 2008 Game Developers Conference, AI Roundtable, Day 2

So What Are We Using?

For all the talk and books and the articles and the conference session and the message board posts, there seems to be relatively little “fancy stuff” making it into games. At the recent Game Developers Conference in San Jose, perennial editor of AI tomes, Steve Rabin, posed an informal poll to the attendees at the 2nd day of AI Roundtables. (GDC notes and audio: Steve’s question can be found at 16:25 of the day 2 audio file.)

Steve Rabin at the AI Roundtable

He first asked “what are the 2 most used technologies in game AI”. The answer, in relative unison, was Finite State Machines and Pathfinding. From there he went to the other side of the spectrum asking for a show of hands of anyone using a neural network in a commercial game. There was no response. (I will ‘fess up and claim the semi-serious follow-up question where I asked “has seen a newbie on a message board ask if he should use a neural network in a commercial game.” In playing along with the joke, many hands shot up in response. In a way, the point I made by that joke - and laughingly conceded by the group - was the same that I am making now.) Steve asked the same regarding genetic algorithms that received only two responses: One in a middleware product and, with the caveat that Steve had allowed pre-processing, one used to creating fire in “Ratchet and Clank”.

Learning? A little - but only in limited roles.

Planning? A couple of people. Steve commented that Jeff Orkin’s much heralded lecture from the 2006 GDC didn’t seem to garner any traction.

There was a mention of behavior trees in the context of glorified HFSMs. However, there was little response on who was using them.

Fuzzy logic? One person claimed it was a main system they used. Otherwise… pffftt!

When all you need is a Finite State Machine…

Flocking? Two people - which is way out of proportion with how much buzz it seems to garner.

I brought up my pet concept of response curves which actually generated more questions than it did answers. (Which solidified my decision to include it in a possible book or the next AI Wisdom.)

Gesture recognition? A couple of people spoke up. Looks like it’s heyday was with casting spells in Black & White.

Natural language processing? Not really. Again, after Nintendogs, no one has done too much.

Somehow, by this point, we had skipped over Minimax and other search algorithms of that ilk. Surprisingly, despite all the press it tends to get, there was no response. (Steve commented that obviously no one was working on a chess game.)

I tossed out a question about how people may have been using standard techniques in novel ways… not unlike using the knife as a screwdriver. I even gave an example of some of the work that was done on Empire Earth where they used pathfinding to pre-process random maps to identify choke points, wall and tower locations etc. Nope.

Influence maps and their kin, potential fields, got a murmur of acquiescence.

Reasoning under uncertainty? (e.g. Bayesian Networks and Markov Decision Processes) You would think that since this particular sub-group of developers was RTS-heavy, there would have been at least some response. We must all have been deflated by Soren Johnson’s lecture on the Civ 4 AI where he commented about how it is just too expensive for each enemy AI to keep and process their own fog of war. (For now.)

Ok… now this is getting ridiculous!

Extending the metaphor to the “AI Game Programming Wisdom” series, we really should have no shortage of tools.

… and Why Not?

While it is a relatively academic exercise to look at the above techniques and count the hands, I think the interesting question is one that was not really touched on in the chronological constraints of a 1-hour roundtable. Why aren’t we using those techniques? When we read their very names, many of us immediately picture some sort of potential use… perhaps the example that was used when we were introduced to it. With a little prodding, we can all hypothesize over how the various approaches would work for potential situation. Often we even make the connection in reverse - by looking at a situation and saying, if somewhat tentatively, “I bet a [insert nifty technology] could solve that problem!” However, if Steve’s informal poll (and others like it) are any guide, we aren’t following through.

I can’t imagine that we are so completely satisfied by the knife and screwdriver that are FSM’s and pathfinding that we are perfectly willing to ignore the rest of the fascinating and ostensibly useful tools that are included in our little red knife. And yet we don’t. Or at least not as much as our imaginations tell us is possible. To me, that seems unfortunate. I wonder if it is a function of just not knowing exactly what that odd-looking appendage is that is parked neatly next to our trusty (and rusty?) knife and screwdriver. After all, isn’t that the case at times with a Swiss Army Knife? You unfold something and say, “well it sure looks nifty, but I have no idea what it does!” Perhaps future copies of game AI books should spend less time on the tools themselves and more time on suggesting (or showing) ways that they can actually be used.

So, to sum up, I will extend Steve’s poll… What ARE you using? What are you NOT using? And why? Or why not? And aren’t you just dying to find yourself deep in the wilderness of development and have the opportunity to solve that inevitable crisis by reaching into your pocket and exclaiming… “I have JUST the thing!

Discussion 6 Comments

Hodgman on May 14th, 2008

I hadn't heard of Empire Earth using pathfinding as a pre-compute step like that, but I've done a similar thing with an FPS AI before. It was a simple waypoint/node-based navigation system - I found that pathfinding from every node to every other node and counting how many times each node was 'visited' (and then normalizing the results) gave a pretty decent influence map for recognising choke-points. I actually got the idea from a GDC 2001 paper called "Terrain reasoning for 3D action games" By William van der Sterren, which explains how to make influence maps for good sniper locations, specifically. However, in line with this article, after finding ways to pre-compute all of these great influence maps, I didn't get time to actually make much use of them! Some of them were used to supplement the A* heuristics (move from A to B, but stay in cover), but that's about it...

kofman on May 14th, 2008

A few months ago, I got my first opportunity in a small team to develop game AI on a deadline project. While I never claimed to have had proficiency in all the techniques, or the experience for that matter. I ended up using deciding on FSM due to their predictability and almost plug and play behavior. And doing steering behaviors (flocking, etc) for movement due to the fact that it was largely a two dimensional game with simple minded creatures (Amoeba). It worked well. The biggest concern I had with it, was for the more aggressive (enemy player) AI, it would change states quite frequently. Something I felt [B]after[/B] the project could have been better solved with fuzzy logic etc... Also after the project the idea of using a Flyweight design pattern on the FSM would alleviate some of the fallacies with the system and that got me thinking further. How else can I improve upon the FSM currently in place. That is how (I theorize) other would go about it as well. Instead of pulling out another tool from their arsenal they would simply upgrade their original.

alexjc on May 14th, 2008

There's certainly nothing wrong with using tools if they work well for the problem at hand. However, I do firmly believe that most often there's a better solution that can offer orders of magnitudes more benefits... But once you've factored in the cost of R&D prototyping, it just no longer makes sense! This is a sad state of affairs really, but I think it can be attributed to a few things:[LIST] [*]Cost of implementation is currently very high. Prototyping stuff quickly is almost impossible with C++. If you use another language, you'll end up in trouble down the road... [*]C++ is a standard language for games, but for AI there aren't any useful libraries to reuse. You can't plug 'n play to try out new ideas easily. [*]Writing stuff from scratch takes a long time since the most useful AI algorithms take a little while to figure out how to implement.[/LIST] Anyway, I can think of many answers to these problems -- but the fact is that it's holding back the advancement of game AI. Alex

BrianL on May 14th, 2008

The popular set of AI primitives emerged based on experience meeting design needs and requirements. In my experience, design basically describes the behavior they would like to see AIs perform (or many cases, that they require for the AI to be considered acceptable) like an expert system. 'If the AI outnumber the player 3:1, one of the AI should charge in.' 'If the AI is takes damage, I want it to displace' 'Can I get the AI to move to particular places based on where the player is? Don't let him get too close though - hes uses a assault rifle which isn't a good short range weapon' People start looking beyond FSM permutations when the behavior design based on more complex design requirements, implementation complexity or maintenance issues. Pay more in performance/complexity when it is needed. See offline vs online data processing; doing it online means more opportunity to be dynamic, but offline may allow you to allocate those resources to other interesting AI behavior. Moving forward, I think the next big application of AI/automation to be in the tools. Content creation has been the dominate dev cost (and therefore one of the biggest barriers to iteration/exploration of the design space) for a while. Surely there are plenty of ways we could apply AI techniques to increase production rate.

RyanP on May 15th, 2008

I do agree that many of the games today do not seem to use much in the way of the more abstract or complex ideas and stick mostly to A* and FSM's as people have mentioned. However I pose a few questions, Is that due to lack of time? External Libraries (middleware)? or just a lack of understanding of the "new/different" subjects? Would people be more willing to experiment if there was an external library that was available that had many of these items in it?

notarikon on May 16th, 2008

Things I use: Modified pathfinding, flocking, BDI architectures, GAs and Influence Maps. Pathfinding - My approach differs in that each of my agents (including the player) has an egg-shaped ellipsoid that expands its pathfinder in certain circumstances. Think of the ellipsoid as an egg with the "pointier" end down. The top dictates vertical jump to grab a ledge/object to climb up/over, the radius dictates jumping ability across divides, and the bottom dictates the maximum distance an agent can jump down from a ledge/object. This allows my pathfinder to create paths like "run to the edge of the cliff, jump down to the ground, run over to the stream, jump over, climb over the tree and attack the player from behind." Flocking - Used primarily for the fish and birds in my game which give visual clues as to the location of agents (birds bursting out of the trees, fish darting downstream), but the steering behaviour code used also helps with navigation around obstacles, and getting multiple agents through chokepoints. BDI (Belief, Desire, Intention) Architecture - I am using this as the basis for my agents actions, with both fixed and dynamic beliefs & desires. This allows me to have set actions or methods that I want them to have, but also allows for emergent behaviour and unpredictibility in their tactics. At any point I can save out their database and copy/paste any functionality as a into the agents fixed behaviour scripts. BDI can also be disabled to just allow the agents to run on their set rules (or vice versa). GAs - I mainly use these outside of real-time gameplay to train the agents in combat, and as well as storing the 'genes' for future pools, I also have them output their behaviours in my scripting language to allow them to be loaded back in at will into the game without having to use much of their (memory-intensive) internals. I'm also trialling them in my map generator to automatically optimise the quantity and positioning of agents to maximise their effectiveness on my maps. Influence Maps - Very simple, co-generated by hand and by the map generator. Is an RGB image that overlays the map, each color layer records separate information. Red is the weight for sniping locations, blue is the weight for ambushing locations, and green is the weight for hiding locations. When an agent decides to do one of these three things, it can create a target node at any of the highest weighted points (depending on other factors - closeness, speed to get to, proximity to player) and know that it's suitable for the task. However, it doesn't automatically have access to all this information, as it is just as limited in knowledge of the map as the player - I use a quadtree to store information on how much of the map an agent has seen, and this also masks any other influence maps to restrict the options to only those areas that have been explored/scouted already. That's where I'm at, but I still have a long way to go. This stuff is quite memory intensive, so wherever I can simplify or simulate without the player noticing the difference, I probably will - just like most other developers.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!