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?
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.)
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!
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.)
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!“