Last weekend, the Global Game Jam was held worldwide and we took the opportunity to turn it into an AI Marmalade. (For those of you that still don't get the breakfast joke: jam, marmalade. See what I did there?) Part of the AiGameDev.com "team" of contributors was available on Saturday and Sunday — Radu, Richard, and partly Nick — and I (Alex Champandard) made some changes in my usual schedule for the weekend, and we built a stealth game!

As a base for the implementation, we decided to use our AI Sandbox as a framework and build this game on top. The goal of the AI Sandbox, beyond just demonstrating AI algorithms and techniques, is to be a good prototyping environment for gameplay & AI — so we figured this would be a good stress test! (The AI Sandbox is currently only available to Premium members, but there's now an official site you can visit!)

NOTE: Parts of this article were written by Radu Septimiu Cristea, who was the main driving force behind the coding this weekend. I'll post a video of the game after the next release of the AI Sandbox, which will include the source code.

Screenshot 1: A screenshot from the final game. The player is in white, and guards in red. (Click to enlarge.)

Design

The idea to make a stealth game made the most sense for a few reasons:

1. Such games often exhibit fascinating AI & interesting gameplay dynamics.

2. They don't necessarily require you to implement an entire combat system!

The design came together in discussions on Friday (and a few before). I described the basic idea in our project log in the forums:

“You play a character that's infiltrating a premise: indoor building, or outside location. Your goal is to try to get to one or more point in the building to pick up / drop off something.

There are guards on patrol, and their behavior is mostly predictable. These guards move relatively slowly and don't see too far. If they get suspicious they approach the last known position, look around and repeat.

An old cleaning lady is also on the premises, she's pretty smart. If she sees something, she'll keep looking and do an exhaustive and methodical search — albeit very slowly. She's there to keep the pressure on.”

The idea of the little old cleaning lady was the best received on Twitter — clearly one of the best modern tools for early design feedback! The cleaner provides a good way to keep the pressure on as a gameplay mechanic, but she’s a good comedy addition to the game too. In fact, we got quite a few suggestions from other Jammers on Twitter for what the old cleaning lady could do.

Anyway, That design was good enough to get started…

Preparations

Screenshot 2: The reports of our build servers, as we stabilized the repository post-merge. (Click to widen.)

Reusing an existing framework seems like taking shortcuts for a Game Jam, but in our case it took the best part of Saturday morning to get to our starting position. In particular, we wanted to merge some experimental branches into the trunk that we’d been working on in our SVN repository:

• An improved skeleton that Richard Fredriksson has been working on. The new skeleton is designed to be much faster and simpler to mirror at runtime, and comes with its own Rig in our animation tools.
• The 2D grid for pathfinding that Nick Samarin had implemented as a dynamic alternative to the waypoint graph, similar to UNCHARTED 2.

It paid off in the end, however. We managed to reuse everything, including the A* pathfinding, the navigation, the locomotion, and the basic character animation to build a real 3D game. Also, since Richard had the character Rig, we managed to make some new walk animations when we needed them. Nick’s code was intended to be the base of the occupancy grid that the cleaning lady would use to hunt you down, but unfortunately we didn’t get around to implementing that…

From then on, we could start work on the behaviors.

NPC Behaviors, by Radu

Once the preparation were over, the starting point of our game was a skeleton of the Hide & Seek demo. After removing the code that was not needed, the first order of business was creating two brain components for the guard and cleaning lady. It soon became apparent that this is going to be the perfect time to stress test out the behavior tree framework and the helper functionality that came with it, namely the tree builder.

Where the guards BT was somewhat similar to the seekers in the Hide & Seek demo, the star of the show was the cleaning lady’s BT. It consisted of three main parts. The idle part — represented by the cleaning around behavior; the suspicious part, which called for movement in the direction of the most likely player position and finally the combat part that made the cleaning lady call the guards on the player’s position. Careful monitoring insured a reactive BT that would reliably switch from one part to another, depending on the world state. This was insured by the monitor and check node decorators that used atomic conditional actions that did the actual state checks. Being under time pressure I didn’t fully use the modules that the framework provides and some code duplication issues are visible. Fortunately, I plan to refactor the code into reusable modules that use the build-in-place construction technique. This would especially help out with the game state monitoring nodes.

Screenshot 3: A test level that Radu hand-designed, along with the cleaning lady in yellow who just alerted the guard in red. (Click to enlarge.)

Another problem that we had to solve was one of “communication” between the level dwellers. The cleaning lady notified the guards of the players’ intrusion by setting a flag in its brain blackboard and subsequently a controller would read the flag and dispatch that message to the guards. I found this technique really lacking and the fact that it would not scale very well pretty obvious. The use of an event system would be really well suited to solve this problem of inter-actor notification.

The recently added reasoning layer (as described in the masterclass with Damian Isla) was adapted to handle IsInView interrogations from the BT conditional actions. As we have seen in our previous implementation of this reasoning layer, this proves to be a very powerful technique greatly simplifying the actual BT actions that just have to pull data from this layer. The layer made heavy use of the underlying Query – Job Processor, constantly sending LOS queries to the sensory system. At this point it was obvious that the LOS queries and inherent querying mechanism was not flexible enough, having to hardcode the field of view in the LOS job.

Navigation & Moving Targets, by Alex

Screenshot 4: Four guards following the player while moving around, with the debug rendering for the navigation enabled. In red pixelated sprites you see the patrol routes and the last known player position. (Click to enlarge.)

One thing that inevitably came up was the navigation system. So far, it was only used for situations where the targets were static and the AI planned ahead until its next destination. When used on dynamic targets, there were problems with starting and stopping every time the target changed. Radu mentioned these concerns:

“One concern was the navigation system, having to handle a constantly changing destination point and keep the motion fluent enough to make chasing the player exciting and engaging. This concern was laid to rest sometime Sunday afternoon when I got the first glimpse of the walk animation from Rikki and improvements in the navigation system from Alex.”

Supporting dynamic targets in a navigation system is a topic that often comes up, and the best solution is often the easiest. When the target has moved a certain distance (say 5m) then run the pathfinder again, or if the target has moved a bit and a certain time has elapsed (say 5s) then also run the pathfinder again.

The only change that was required in the AI Sandbox code was to not tell Locomotion system to stop and go into Idle, and instead keep it Running. The results look pretty good, despite some issues in the underlying locomotion...

Locomotion Improvements, by Alex

Screenshot 5: The set of walking motion clips (individual steps) that make up the walking motion graph. In yellow are left to right steps, and in white are right to left steps. (Click to enlarge.)

So far, we've only used running motions in the AI Sandbox since the motion capture we used was focused on running, jogging and sprinting. There were also some walks, but they weren't as useful nor as good quality animations. Luckily, Richard touched them up for the new skeleton, and re-exported them and so I had something to work with. However, I ran into a bit of trouble with the motion graph code…

The core of the problem was the footplant detector. I need to detect footplants for the different types of motion, so they can be aligned when the foot is down. For the running motions, I managed to create a function that extracts local minima of the feet position, and filters out the false positives to hopefully end up with only the exact footplants. However, this broke for the new walks and I had to make some adjustments to thresholds and various parameters.

The code works fine now, but in retrospect there are a few problems with our current solution, in particular that the code finds footplants one side at a time, and does not consider the other foot nor the rest of the body. There’s lots of academic research on the topic, but so far we’ve not needed it. That may not be the case for much longer!

One last problem that remains is a question of alignment in the motion graph builder. The two walk steps are not aligned or synchronized quite perfectly, which leads to a zombie like walk. It works well enough for this game though, since it is supposed to be an old cleaning lady, but this part of the code will need reworking a little in the future…

Game Logic & User Interface, by Radu

Another technique that proved its value was the Model-View-Controller pattern. I was quickly able to get a “treasure” entity and graphical representation in the world, but I was very surprised how I was able to create a game state controller class that handled win/loose conditions and plug painlessly plug it into the main controller manager class of the game.

The duties of the controller that handled the burden of handling the game state included monitoring of the player position in regards to the guards, checking if the player collected all the gold on the map. While collecting all the gold would trigger loading of the next level, the consequence of getting caught by the guard was basically a game reset. The reset, as trivial as it sounds, implied resetting player position and gold, resetting the blackboards and positions of the NPCs and finally stopping the execution of the BT interpreter. Except the behavior part, everything went smoothly.

Resetting the behavior called for cleaning of the blackboard that holds a considerable amount of data. It became apparent that in the near future this has to be broken up into smaller components (ordering, visualization flags, patrol data…) to avoid the monolithic construct that the blackboard is slowly becoming as it holds more and more data. Another minor issue was stopping the interpreter that called for a stop feature to the Brain base class in the behavior library. As necessity is the mother of invention, this feature will surely make it in the next sandbox release.

Screenshot 6: The user interface elements all together, including top-left progress icons, over-head indicators for each NPC, and the game logic overlay for winning/losing the game. (Click to enlarge.)

With a couple of hours left on the clock, and energy resources slowly dwindling I got to revisit the UI system I have written some months ago. The test driven development approach used a while back, suggested and enforced by Alex, really paid off in full. The UI code quickly fell into place with the use of the WidgetHelpers and behaved as expected without any problems. Most of the time was spent tweaking colors, timing and finding nice pictures to use.

Gameplay & Levels, by Alex

In parallel, I was working on the camera system. I started out experimenting with a GTA-like follow camera; being involved so closely certainly increased the tension of the game. However, such cameras often need a lot of fine tuning to work, for example to avoid obstacles when walking close by, to move into better positions to help the player visualize the scene. Instead, I reverted back to the top-down camera which we used for early development, but I moved it lower down to only about 25 meters above the ground and added smooth following movement.

This camera works relatively well because you can see the action locally around you (as the player), but you can't see the whole level. You still have to be careful locally, but you have enough information to be tactical. Also, it makes it much easier to see what the AI is doing, so we can show it off in a better light this way, for instance watching the old cleaning woman track you down!

After that, Radu and I spend a bit of time tweaking variables that affected the AI, for instance the field of view or maximum view distance, and various timers that trigger behaviors. Speed and movement of the player relative to the guards was also an important thing to adjust, and I experimented with a simple sprint button locally to help you loose guards if you get into too much trouble. Finally, I finished of implementing random level generation, so you get some nice structured levels (with walls and recognizable features) that are beyond just randomly placed blocks.

Summary

The biggest lesson learned here is probably the most common from Game Jams: short events are really great for focusing attention and development on ambitious yet achievable goals. This was both great for those of us that worked on the game, but also for the AI Sandbox itself. We now have a much clearer picture of where to spend our time — although many of the things that came up were already known issues!

Beyond that, a big take-away for me was the real-world value of unit testing. Not just automated testing, we have functional tests for most of the components and systems. I mean specifically unit testing. The parts of the code that were unit tested "Just Worked™" and scaled whenever we needed them without sweating. This was the case for my Behavior Tree code and Radu's User Interface code. The pathfinding in the navigation that Jad Nohra wrote with tests also had no issues... However, the locomotion builder and its component caused lots of trouble — and those have little or no unit tests.

Going forward, we will be holding these AI Marmalades more often, possibly once every month or two. They'll help apply our code and bring the team together for a weekend event! As a result, we'll also have a large prioritized list of things to work on for the AI Sandbox, as we do now!

The Global Game Jam will take place worldwide this weekend. For those of you participating that are looking for a challenge, fresh ideas to distinguish your game, moral support or help for building your AI, then the AI Marmalade is for you!

AiGameDev.com is proud to announce the AI Marmalade, which will take place on January 29-31 at the same time as the Global Game Jam. You don't have to be at an official Jam location to participate in the Marmalade; in fact you can do it from anywhere!

Here's how it works...

What Is the AI Marmalade?

The AI Marmalade is a common underlying theme for the Global Game Jam. If you're interested in pushing the boundaries of Game AI or just learning something new in this area, then join in!

The AI Marmalade is here to help by providing:

• Inspiration and Ideas — If you'd like to design something innovative, or find a topic that explores artificial intelligence in games, then come and talk to us!
• Technical Advice — We'll also be around for programming support if you need it. Brainstorm about solutions with the resident experts at AiGameDev.com!
• Feedback or Comments — As you get something up and running, you need play testers or a review of your design, we'll be there too.

You can at least count on Phil Carlisle and I (Alex Champandard) on being around, and presumably the regulars in the forums and IRC channel too.

Where Will it Happen?

The AI Marmalade will take place online, so you can join in from whatever location of the Game Jam you chose. In particular

1. The Official #gameai channel on IRC.freenode.net. Join us at any time during the weekend to discuss any of the topics above.

2. The AiGameDev.com forums. Use the Projects forum to post reports of your progress, screenshots, videos, descriptions, etc.

3. We may even use our online meeting room with audio and whiteboard to brainstorm or explain things if necessary.

If in doubt, join the IRC channel and you'll find friendly people to help at most times of the day!

How Does it End?

We'll finish the AI Marmalade at the same time as the Global Game Jam. However, afterwards we'll post about all the games, screenshots, descriptions, videos on the AiGameDev.com blog.

That's all you need to know... I hope to see you on IRC or in the forums this Saturday and Sunday.

Let's make some AI Marmalade!

2009 has been a very important year for game AI as a discipline, possibly one of the most significant yet. I feel a bit less guilty about struggling to keep up with everything just looking at how fast our field is moving!

In this editorial, I'll break down some of the things I expected to happen and what actually did happen. There were also quite a few significant moments this year, as well as a few controversies, which I'll describe in their juicy details as well.

I'd love to hear from you what you thought was significant about 2009, and which moments you think we'll remember in the distant future! Please post a comment below. Also, while you're in the forums, don't hesitate to share some of your predictions for 2010...

Look Back at 2009 Predictions

I posted my predictions for 2009 in this forum thread. They were...

#1
More Experience Management

The first thing on my list of predictions was based on LEFT 4 DEAD 1's momentum in last year's Awards and critical acclaim:

“Use of high-level AI as experience management (the big gain, better gameplay), and slowly moving towards better procedural narrative.”

The key word in there was slowly. Certainly, there has been some progress in this area. For example:

• UNCHARTED 2: AMONG THIEVES — This game had a very complete in-game context-sensitive hints system which made sure you'd never get stuck. However, some players felt it was a little too aggressive in helping you out while you were still thinking about a solution!

• LEFT 4 DEAD 2 — The concept wasn't broken, so Valve didn't make too many changes to the core mechanics. If anything, the zombies were made a bit more aggressive and the hordes seem to be more frequent. The new features of the AI Director 2.0 seem to be either scripted (e.g. weather in Hard Rain) or random (e.g. the procedural geometry).

• HALO 3: ODST — Bungie's latest game introduced an open-world hub which required a mechanism to guide the player towards interesting areas. You can see this in action in the CO-OP review of the game. See the screenshow below with the yellow highlight.

Even though it's a variation on a concept that you can find in the user interfaces of many games before, HALO 3: ODST's design is interesting as it's more subtle and blends with the world better. It feels more like "experience management" rather than a gameplay mechanic displayed on a UI. Matt Chandronait from Area5.tv mentions this in his review:

“I thought the environmental cues did a really good job. The AI that controls the city is guiding you around subtly to different areas.”

The big open questions for 2010 are how to take this experience management beyond layered randomness for scenario alterations, beyond an in-game hints system that helps you complete a linear story, and beyond a user-interface displays that help you orient yourself in the world. Can these things be combined? What other opportunities are there to adapt the game to the player and make it more fun to play?

#2
Thriving Indie Game AI Scene

There's always been a trickle of talented developers from big publishers going independent, but I predicted an increase at the start of 2009:

“The rise of independent game developers, using less conventional AI.”

It's been a prolific year for independent games and with more layoffs from big publishers more talented developers are becoming independent developers. What's particularly interesting is the different techniques that independent developers are using, in particular:

• AI WAR: FLEET COMMAND — This indie game is the brainchild of Chris Park, who comes from a database background. He used those ideas to manage the simulation of tens of thousands of ships.

• GALACTIC ARMS RACE — Implemented by Ken Stanley's team, this game's purpose is to demonstrate content generation research technology. It certainly poses more questions than it answers!

This diversity is very healthy for the industry as a whole, and I think it's arguably the best way for new ideas to make their way into the mainstream. That said, it will take a bit more time to see the indie scene really shine, for example with character AI. But there are many things to look forward to in 2010... In particular, look forward to contributions from Damian Isla and Borut Pfeifer.

#3
Progress in Character Animation

In early 2009, I rather ambitiously predicted the following:

“Developers place much focus on character animation / locomotion, and reach a near-consensus how to "solve" it.”

Games such as ASSASSIN'S CREED 2 and UNCHARTED 2: AMONG THIEVES (among others) are leading by example. It's now more obvious what kind of technology makes up a cutting-edge game animation system:

• State-based blend tree,

• Multi-layered blending,

• Motion capture driven,

• Inverse kinematics solvers,

• ...and occasional ragdolls.

In the future, there are going to be variations on this theme and improvements in each of the components. But the overall approach has established itself over the past few years, and it's solid enough to move forwards.

As for locomotion, there are still some sliding artefacts for things like walking and running. I'd argue we can still make good progress in this department, as I hinted in my presentation at the Game Developer's Conference where I talked about the holy grail of locomotion. However, we're not quite there yet; it'll take a few years more — though it's refreshing to hear about studios attempting this now!

#4
Industry Consolidation

At the start of the year, based on the economic downturn, I predicted the following:

“Industry consolidation in the middleware business in general, possibly with big publishers buying startups.”

Buy outs or mergers didn't happen as I expected. Big publishers have been spending less money, cutting staff, and investing in social media rather than technology companies. All the middleware companies working in artificial intelligence are still officially in business though!

That said, middleware companies have been collaborating increasingly together — which is arguably a form of consolidation. Many AI vendors have worked on the integration of their solutions within third-party engines, in an attempt to reach more customers. There's also been a "Race to the Bottom" and a competition based on low price or free services, for instance providing free integration or cheap licenses for independent developers.

#5
Useful Multi-threading

Parallelism and multi-threading isn't new to 2009, but I predicted last year to be a turning point:

“More talk about useful multi-threading beyond "cosmetic improvements" (from all sides) and good prototypes emerge showing this.”

While more and more games leverage multi-threading, both on console platforms like UNCHARTED 2: AMONG THIEVES, or on the PC like OPERATION FLASHPOINT: DRAGON RISING to great effect, games that leverage these resources for AI are few and far between. KILLZONE 2 is another great example of leveraging current-generation "fixed" console hardware (in this case PS3) for the purposes of artificial intelligence.

In terms of massive parallelism and large scale multi-core applications on more flexible hardware (like on the PC), the responses beyond cosmetic improvements are mixed:

1. CUDA applied to a simulation of flocking planes (see this YouTube video). It's a promising approach, although the question is how this will work as a game.

2. Intel's TBB used for scaling up ambient animation and AI. This works in practice easily, though the improvements are not as impressive.

The big question is whether better hardware can be leveraged for AI at all, without it becoming a very different game. I mean, if you're using 1 TFlops extra computation for your AI, that's going to affect the gameplay — so you'll have to treat it as a separate game. A second big topic is how we can push the limits of console hardware with multi-threading, while still preserving the determinism of the simulation required by many networked games these days.

Along these lines, 2009 did bring the advent of promising technologies such as OpenCL, CUDA, and Intel's TBB. OpenCL in particular seems to be the most promising, as I discuss below.

Bonus
Academic Integration

In retrospect, this last bonus prediction of mine was a little overly ambitious! I claimed:

“More academic AI concepts/ideas/techniques make it into industry thanks to a better flow of research knowledge.”

There's certainly been some transfer of knowledge in the area, as the awards for Most Influential Research in our 2009 Awards indicated. That said, objectively it's hard to claim the situation is improving. In fact, subjectively it feels like the divide is getting bigger — as I mention in more details below.

I remain optimistic about this, but it will take a long time. From reviewing recent conferences, I get the sense part of the new generation of research associates and Ph.D. students are better in touch with industry, and of course this will help educate professors and supervisors that don't have a gaming background. But I also hope that the tight budgets this year help increasingly raise the bar, and make institutions a bit more competitive at providing useful research for industry.

Trends for 2009 in Retrospect

#1
Parallelism and Data-Oriented Design

Because of particularly long console hardware cycles, game developers have been able to spend more time optimizing their software. What the programmers have increasingly found is that memory is the biggest concern as well as the most precious resource.

• Tony Albrecht's Latency Elephant Article

• Mike Acton's Sketches on Concurrency, Data Design and Performance

• Data-Oriented Design on Game Developer Magazine

How does this affect AI? As we apply multi-threading to various aspects of the collision raytests or pathfinding searches, understanding the layout of the data is becoming particularly important. Beyond that, as these low-level parts of the AI are optimized, the high-level AI — in particular behavior trees — impose a huge toll on the cache.

#2
The Challenges of Sandbox AI

It's always tough to find enough time to polish the AI in any game, if you want to keep your deadlines! However, sandbox games have it particularly tough... When I interviewed Mikko Mononen 18 months ago, we also discussed his work as Lead AI Programmer on Crysis, a game which certainly had its fair share of YouTube fan clips made about the AI's bugs after launch. However, a few patches later and the game's AI on Hard mode is still cited in gaming forums as a reference for combat AI.

I attribute such bugs to the complexity of making AI for sandbox games. Because there's just so much more that can happen in open worlds, there are more edges to smoothen out. If anything, this year has seen more sandbox games than any other year, so there are quite a few examples to draw upon, ranging from super-hero style city combat games to highly realistic military simulations. With few exceptions, the AI that shipped in those sandbox games this year originally received criticism in their reviews — only for the bugs to be addressed later via multiple patches.

Is there hope for solid AI in a Sandbox game at launch?

#3
Better Characters: Money Talks

This year, the bar has been raised for non-player characters thanks to games such as DRAGON AGE: ORIGINS, GRAND THEFT AUTO: GAY TONY and of course UNCHARTED 2: AMONG THIEVES. As resident expert Phil Carlisle pointed out however, there's a direct correlation between the quality of the results and the amount of money spent. In particular, things like:

• Voice acting
• Motion capture
• Hand animation
• Facial expressions
• Texturing and modeling

The AI & behavior comes into play afterwards, but it's main responsibility seems to not break the illusion once the character has been established with all these other expensive and time consuming processes!

In particular, the whole process of hiring actors, rehearsing and shooting the scenes has had more impact on the critical reception of UNCHARTED 2: AMONG THIEVES than any other game. Watch the Behind The Scenes video Our Process Was Different and see how important this was for establishing the characters, compared to anything the AI could do.

#4
Utility-based Architectures

Utility-based architectures describe a whole decision making system that chooses actions based on individual floating-point numbers that indicate value. (At least that's as close to an official definition I can come up with.) Utility in itself isn't new, and you'll no doubt remember using it as a voting or scoring system for specific problems like threat selection, target selection, etc. What's new in 2009 for is:

1. There's now an agreed-upon name for this architecture: utility-based, which is much more reflective of how it works. Previous names, such as "Goal-Based Architectures" that Kevin Dill used were particularly overloaded already.

2. A group of developers advocate building entire architectures around utility, and not only sprinkling these old-school scoring-systems around your AI as you need them.

The second point is probably the most controversial. That said, there are entire middleware engines, such as motivational graphs which have been effective in military training programs, and Spir.Ops' drive-based engine applied in other virtual simulations. The discussion about applicability to games is worth another article in itself, and the debate will certainly continue into 2010!

#5
Would You Like to... Parkour With Me?

A general trend for the last few years has been the rise of Parkour-based movement. What's special about 2009, is that the AI seems to be following in the player avatar's footsteps, notably in traversing the world in a more complex manner than before... Notable examples are:

• UNCHARTED 2: AMONG THIEVES — As Christian Gyrling mentioned in his interview with me last year, making the AI NPCs traverse as well as the player was a major goal for this sequel.
• ASSASSIN'S CREED 2 — When you cause trouble in the game, soldiers will somehow find their way on to the rooftops to challenge you, though they don't seem to be quite as agile as the player (by design).

It's great to see that NPCs with better abilities that are symetrical with the player's has indeed improve the diversity of the gameplay!

#6
Academic Rift

The main academic conferences in game AI this year, AIIDE and CIG, brought together academics (mostly) with a handful of developers from industry — in a similar format to previous years. What was new this year is that tensions at AIIDE erupted onto Twitter. It's a bit difficult to piece together 140 charater messages to figure out what caused these underlying tensions to bubble to the surface, but what seemed to be missing was someone neutral to arbitrate and reprimand the cheeky or out-of-line comments from both sides!

Reading back about the 2007 and 2005 editions of AIIDE from Tara Teich's notes, it seems this "disconnect" between academia and industry has been there since the start — most likely due to the format of the event. For CIG, the problem is less obvious as the conference attracts fewer people from industry. Luckily, research keeps going and now there's more information flowing from industry conferences & publications the relevance of research projects can only improve...

#7
The Rise of the GPU

This year started out with a marketing drive from NVIDIA and AMD to establish the benefits of GPGPU computations for game AI. The idea is that general purpose processing units on graphics cards (GPGPU) would be ideal for certain pathfinding operations in dynamic worlds. The article cited Relic's Chris Jurney, who used such techniques on Dawn of War 2.

Interestingly enough, Chris Jurney wasn't even aware of this marketing drive, and only found out about it when I mentioned it to him! (This was during the HPAA* masterclass with Daniel Harabor, if you have a Premium AiGameDev.com account.) Chris Jurney then went on to elaborate how there were significant issues with using a GPU for AI, in particular Dawn of War 2, since the entire engine must be deterministic for networking reasons, and no graphics driver could guarantee that.

Since then, however, OpenCL hit the scene and its standard apparently guarantees a deterministic implementation... At this stage, we can still only speculate about applications though.

#8
Behavior Trees Everywhere

If there was a battle over the past few years for an AI technique that could provide scalable, designer-controllable, programmer-extensible behaviors — then behavior trees would have won it in 2009. Games this year including [PROTOTYPE], DARK SECTOR, UNCHARTED 2: AMONG THIEVES, HALO 3: ODST (and many indie games) are all using a variation of behavior trees under the hood.

This trend is in my opinion due to the strength of the technique, plus the fact it describes the many patterns that actually work and that game developers use in practice. I like to think of behavior trees as the first thing you should establish, as it gives you a framework to insert any other decision-making technique into your AI in a modular way. Of course, our evangelism of behavior trees here on AiGameDev.com may also have helped a bit!

Notable Moments in 2009

#1
Industry Conferences & Events

Photo: The audience at the Paris Game AI Conference 2009.

Artificial intelligence in games has always had its fair share of academic conferences. However, 2009 marked the year of industry events on the subject. In March, the inaugural AI Summit took place at the GDC. This event was a highlight of the first two days at GDC, otherwise normally made up of a "series of press releases" in sponsored events — as one attendee told me! The down side is that this Summit sucked the AI out of the rest of the GDC, which seemed rather bland in comparison.

In June, AiGameDev.com ran its second annual Paris Game AI Conference. This standalone event brought together around 200 people from around the world, in contrast mostly programmers from industry, middleware developers and students. This conference was unique in its friendly atmosphere, and everyone in the audience attended specifically because of their passion in game AI. In case you missed it, the event will return by popular demand in 2010!

#2
What's the IGDA AI SIG?

The Game Developer's Conference 2009 featured a roundtable about the IGDA 's AI SIG. It's a officially a "Special Interest Group" like many other SIGs in the IGDA. The AI SIG is infamous for its AI Standards Committee, which unofficially went into cardiac arrest silently a few years ago without a defibrillator nearby.

The roundtable was the most uncomfortable GDC session I've ever been to, firstly because the topic of the AIISC was not officially on the agenda, and discussion was rushed along awkwardly when the topic came up. Secondly, there was almost no acknowledgement that the AI SIG is only an annual newsletter, and that nobody will actually implement the ideas discussed. Andrew Armstrong, a very active IGDA contributor, asked about this and there was no answer. Here's Andrew's report of the roundtable:

“Something that annoyed me was, despite this being a sometimes good set of ideas being put forwards, without anyone actually wanting to do the work, nothing will get done and the SIG will continue to stagnate. None of the ideas raised are easy to do.”

I had lengthy discussions with IGDA members from other SIGs about this subsequently... We came to the conclusion and a big problem seems to be the process these special interest groups go through. The chairperson can be self-proclaimed and there's nothing that can be done about it. In fact, people with the drive and initiative about their respective "special interests" tend to be driven away from under the IGDA's wing for these reasons — although it varies depending on the SIG and the chairperson. It's certainly the case with the IGDA AI SIG.

For reference, the rest of the year since the roundtable has been entirely quiet on the IGDA AI SIG front, as Andrew suspected would be the case.

#3
R.I.P. AI Game Programming Wisdom

The bad news of the year came as an announcement just before the Paris Game AI Conference 2009; the AI Game Programming Wisdom series was terminated by the publisher. Steve Rabin (series editor) and I were discussing the book publishing business generally after the AI Summit; we were joking that websites like AiGameDev.com and our Premium area are one of the reasons why books are having a hard time...

Little did we know that a few months later, the series would be permanently shelved. The four books in the series will remain on the desks of serious programmers in industry, and hopefully future papers will be published via more academic channels such as AIIDE, TCIAIG or CIG.

#4
Mikko Mononen's Recast

In April this year, Mikko Mononen (Lead AI on Crysis and ex-Programmer at Crytek) released his navigation mesh and pathfinding library called Recast and Detour, which have since become open source. The libraries have since been stimulating a burgeoning indie game development scene, which was severely lacking an open-source pathfinding library.

For me, it was most incredible to see the professional respect and encouragement towards Mikko from established middleware companies — excluding of course the vendor that threatened to sue! Of course in the long run, such a library can only improve AI in the open-source community as well as industry as a whole.

#5
Infinite Mario Goes Mainstream

At CIG this year there was a Mario AI Competition, held alongside the usual Bot Prize in Unreal. The competition hit the mainstream press thanks to Robin Baumgarten's A*-based implementation that showed Mario solving an infinite level.

Such a widespread coverage of this as news was quite incredible to watch, including Robin's interviews with reputable print newspapers. This in itself was more of an achievement than the competition itself, showing off the power of AI in computer games to the masses. I certainly hope this inspired some people to get into game AI!

Conclusion

Now you can see why 2009 was such an important year for game AI as a field and an industry. It's hard to believe how things changed over the past few years let alone this decade!

Stay tuned for the follow-up with predictions for (the rest of) 2010. Be sure to post your own predictions for the coming year in the forums in the meantime.

NOTE: Make sure you don't miss out on all the action in 2010, and sign-up now for our Paris Game AI Conference this year. Tickets are already available!

Those of you who stay up-to-date with AiGameDev.com behind the scenes (on Twitter or in the Forums) know that we've been preparing the 2010 edition of the Paris Game AI Conference for many months already. Organizing last year's event entirely was one of the most rewarding moments of my career, but at the same time it was probably the most difficult thing Petra (Mrs. AiGameDev.com) & I had done so far professionally!

It took a lot of preparation and scouting around before committing to taking the event into its third year, but thanks to your tremendous feedback from 2009 and early support from our Conference Sponsors this year, we're pleased to announce that we'll return to the CNAM in June. In particular, we'd like to thank Autodesk, PathEngine, Spir.Ops, and Four Door Lemon for their sponsorship and making it possible.

Read on for details about the conference itself, the call for proposals, and how you can secure your seat at the event...

The (Un)Official Details

Officially, the event is scheduled for the 23rd and 24th of June and is co-organized by AiGameDev.com and the CNAM, where the event is held. The organizing committee consists of Petra & Alex Champandard from AiGameDev.com, Stephane Natkin from the CEDRIC lab, and Axel Buendia of the Paris-based AI middleware company Spir.Ops. You can check the standalone site below for more details...

Paris Game AI Conference — Official Website

Photo 1: Q&A with the audience at the end of the Paris Game AI Conference 2009. (Click to enlarge if you recognize someone!)

Unofficially, I think the conference is absolutely unique. Of course, it brings together many of the brightest game developers in the world working on artificial intelligence in industry, including Ubisoft, Crytek, Arkane, Splash Damage, Rebellion, Quantic Dream, etc. But beyond that, it's what you said about the event that made it unique...

• Friendly — Outside the amphi-theatre in the photo above, there's a small-sized courtyard. You'd think this wouldn't be a feature of the event, but seeing almost 200 people chatting there about the practical side of game AI during coffee breaks made it obvious. At bigger conferences, people just disappear after sessions to hang out with people they knew before. Here, the busy courtyard was a great opportunity to network without pressure.
• Passionate — Everyone who came to Paris in 2009 came especially for the conference. These were actual developers from industry, designers, technical animators, students in computer science, programmers from other fields, etc. At larger conferences, many business-minded people, PR or managers tend to show up rather than developers, and frankly, they have nowhere near as much passion for game AI!

I don't believe this is a coincidence. We never set out to achieve this explicitly, but that's the kind of energy we put into the organization and the event itself, so it's not a surprise that's how it turned out. The little decisions and lucky breaks, from making the conference affordable to finding a great venue, all contribute to this!

For 2010, we won't be changing the recipe of the event, though there's always room for improvement with the various ingredients. Rest assured, we're working on that already. :-)

Tickets, Registration and Bonuses!

Last year's event was completely free to attend, which contributed significantly to the unique atmosphere and that almost palpable passion . However, it was also one of the main reasons we spent so much time managing the event. This year, it'll cost a symbolic amount between €47 and €97 to attend depending how you choose to sign up, and subject to the following discounts. You can get 50% off the listed price under these conditions:

1. If you're a Premium member at AiGameDev.com,

2. If you're currently an under-graduate Student,

3. If you're specifically traveling from outside of Europe.

The first Silver (€77) and Gold (€97) tickets will be available on the official conference site from January 15th onwards, at exactly 13:00 CET or 12:00 GMT. This is the best way to secure your seat for the conference and show your support! For the past the past two years we stopped registrations once we reached room capacity, and we expect to sell out again this year. Be sure to plan accordingly...

Screenshot 2: Ticket registration page that will open on January 15th. A limited number of Bronze tickets will be on sale from February 15th onwards.

To encourage you to register sooner rather than kick yourself later, if you purchase a Gold ticket in the first seven (7) days before January 22nd, you'll receive the following bonuses:

• If you're an individual Premium member of AiGameDev.com already, you get a whole bonus month of free membership! (First 10 individuals.)
• Otherwise, you'll receive access to the audio/video interview with Christian Gyrling about the AI in UNCHARTED 2: AMONG THIEVES. (First week only.)

Later on February 15th, we'll have the Early Bird sale for Bronze tickets (€47). There are a limited number of these tickets, and they'll only be available for a few weeks at the most, so make sure you're around!

Program Committee

No details about the conference program have been announced yet, but you can rest assured we'll have the best invited speakers and featured games we can find — at least as good as 2009! We've picked from best independent developers who presented last year as Advisors to make sure the conference program is the best it can be.

Mikko Mononen

Mikko was the Lead AI on Crysis, and worked as a Programmer at Crytek for multiple years. He's also an independent developer, AI consultant and leading open-source developer. You can find information about his projects on his blog.

Phil Carlisle

Phil is an industry veteran who worked on the Worms franchise at Team 17 for many years. As well as doing research into emotions, animation and expression, he's working on an indie title called Box Mental. See his blog for details.

William van der Sterren

William is a game AI consultant for CGF-AI, who worked on Shellshock 'Nam and Killzone 1 with Guerrilla Games. He's currently developing mission planning as scenario generators for the ArmA game series.

Call for Proposals

If you'd like to speak at the Paris Game AI Conference 2010, now's also your chance. We're interested in hearing about game development of course, but specifically artificial intelligence in the broad sense, including character animation, or gameplay integration, including how it relates to testing and production.

We're also interested in hearing short talks about any of the following:

1. Independent Games — Did you build an independent game that includes AI? Was it an interesting experience?

2. Innovative Research — Are you applying AI to new aspects of games or simulations that you'd like to show?

3. Experimental AI — Did you build a prototype or demo that shows off something new and unique?

If you're interested, contact <events at AiGameDev.com> with your proposal!

Conference Sponsors

Autodesk® Kynapse® middleware is a trusted artificial intelligence solution for game development and real-time simulations adopted for over 100 game titles. This high-performance AI engine supports 3D pathfinding in destructible environments, including large-crowd pathfinding in complex terrains, dynamic 3D topology analysis, and team coordination. With its efficient production tools and architecture designed for easy integration & customization, Kynapse helps streamline the process of creating top-quality console and PC games.

PathEngine provides a sophisticated toolkit for agent movement, built around an advanced points-of-visibility pathfinding core. This gives you powerful paired path planning and collision against a sophisticated, continuous space, pathfinding movement model, with robust integrated dynamic obstacle functionality and exact representation of agent shape, for seamless movement over overlapping ground geometry.

SpirOps is a middleware development team focused on AI. Their ultimate goal is to allow video games and simulations development teams to enter what we call "the Living Game era." To design more realistic behaviors with a never reached complexity, the SpirOps developed an artificial intelligence design paradigm called "Drive Oriented" which allows designing AI with graphical tools and keeping a linear complexity during the brain creation process.

Four Door Lemon is an indie games developer who offer work-for-hire, prototyping and technology to the games and interactive industries. Established in 2005, FDL have been involved in over 35 projects across multiple platforms of varying scale. Recently FDL launched their trivia game QuizQuizQuiz on the iPhone which was a great success in the UK/Europe, further great games and related announcements will follow in 2010. If you need help with your project in any way, please get in touch!

This 3rd edition is set to be the most controversial — yet fascinating — Annual Awards for Game AI! Let me clarify. The whole procedure, including the nominations and the voting, is done by the community here at AiGameDev.com. Of course, there's a certain editorial process involved in picking the nominees, but the rest is mechanical and just a question of collecting the results.

Typically, I've been able to predict the winners... mostly. This year, however, that wasn't the case! I speculate this could be due to the following reasons:

1. It's been a very constructive year for Game AI, more games deserve the spotlight, and it's harder to separate the candidates.

2. The community is by definition self-selecting and this reflects in the way its best games are chosen...

3. I'm getting older, my taste in games is changing, and everyone voting in the awards thinks radically differently than I do. :-)

It's probably a combination of the three, but the bottom line is that I've decided to include as "Editor's Pick" along with the "Vote Winner" for each award. If anything, I hope this helps shine a spotlight onto more games that are worthy of attention.

Anyway, without further ado...

Best AI in a AAA Game

Editor's Pick
THE SIMS 3

The third major version of EA's money-making franchise hit the streets in February 2009. Don't be fooled by the numerous expansion packs that preceeded it, this release was a radical departure from THE SIMS 2 in almost every way, not least in the character AI department. The Sims' new personality traits, their ability to interact socially and behave autonomously within living neighborhoods all combine to make this a very unique simulation game.

A series of blog posts about Alice and Kev which was featured in mainstream media earlier this year is a perfect example of the kind of emergent storytelling made possible thanks to the game's new mechanics. This example alone classifies it as a significant milestone for AI characters in games. From the site, here's the description of the experiment:

“This is an experiment in playing a homeless family in The Sims 3. I created two Sims, moved them in to a place made to look like an abandoned park, removed all of their remaining money, and then attempted to help them survive without taking any of the game’s unrealistically easy cash routes.”

Richard Evans, the man behind THE SIMS 3 and also the AI from BLACK & WHITE at Lionhead, told me at the GDC last year that he managed to get "only" 80% of his ideas implemented in the game. I told him that any portion of his ideas was still probably better by 8x than anyone else would have done! His influence shows in the game, and only time will tell how the ideas behind this game will affect the industry as a whole or whether this is a series unique to Electronic Arts and the high production values it put into the game.

Vote Winner
KILLZONE 2

The combat AI that Guerrilla Games built over the past 7-8 years since Shellshock: Nam '67, including Killzone 1 for the PS2 and Killzone: Liberation for the PSP has arguably become the best in industry with this latest iteration. The enemy behaviors are dynamic and adaptive, showing off both linear sections and large open areas of the game thanks to its tactical reasoning.

The AI in KILLZONE 2 in particular shines in the Skirmish mode where you can play with computer-controlled bots in large open maps designed for multiplayer, and free of scripts and trigger boxes. The bots were intended for offline play where you have 7 bots on your side against 8 enemies, but you can also compete online with your friends against various combinations of bots. Not only were the bots fun to play against, according many reviewers including to Ryan O'Donnell of Area5.TV, but they even passed an informal Turing test with journalists from the CO-OP show (season 2, episode 1) and others:

“The bot thing is pretty amazing. I was telling you earlier that I was playing it and it was behaving in such a particularly clever way in this one area that I had to check that I wasn't play online.”
— John Davison, WhatTheyPlay.com

Some reviewers even speculated that Skirmish and multiplayer bots were included simply to emphasize the strength of the combat AI. You can watch some High Quality videos of matches against the bots in the Salmun Market or the Radec Academy.

Cooperative buddy AI that accompany you through the game (while actually fighting alongside you) is generally a hard problem that nobody has got entirely right to-date, and there's still room for improvement in Killzone 2's buddies. However, it's one of the best attempts yet and given the underlying engine there's even more potential. In particular, there's a balance to be found between the aggressiveness that can save you in tricky situations vs. buddies playing safe so you don't need to revive them too often.

Best Non-Player Character

Vote Winner
Morrigan in DRAGON AGE

Because many different characters are required to set the scene in DRAGON AGE, individually the characters may not seem as polished as other games. However, as Kevin Dill points out, overall the characters make for a very compelling role-playing experience.

Kevin continues:

• The overall production values are outstanding. There is a wealth of high quality animation and voice acting that really brings the characters to life, as well as solid assets and rendering.
• Reasonably good facial animation, including expressions, gestures, and so forth. Nothing groundbreaking here, but a state-of-the-art execution of a very challenging set of problems.
• The level of detail in the social interactions. Responses vary on all sorts of features, so that if you replay the game with a different character, and do things in different ways or in a different order you will get very different interactions with the various NPCs. This does a lot for believability.

All this goes a long way towards explaining how games last 60 to 80 hours!

Editor's Pick
Chloe in UNCHARTED 2: AMONG THIEVES

In terms of quality and sheer polish, the characters in UNCHARTED 2 are unmatched. From the animation and motion capture to the voice acting and in-game dialog lines, including the AI behaviors. Everything fits together to create an entirely compelling character that not accompanies Drake around the world as he engages in combat, but also provides gameplay moments on cue.

Naughty Dog have done an impressive job with all the characters in the game, but Chloe in particular seems to have captured the attention of many gamers — and without the use of excess nudity!

Best AI in an Independent Game

Vote Winner
AI WAR

AI War was the clear winner of the Best AI in an Independent Game Award. The game has become famous for its huge battles and over 30,000 active ships in the universe, but innovates on the RTS design front as well with its procedural population.

• Decentralized, Emergent and Fuzzy Intelligence: 30,000 Units in AI WAR (Premium)

Editor's Pick
GALACTIC ARMS RACE

Ken Stanley's team are not only leading academic research in game AI, but they're setting an example by also building games around their ideas. In particular, they chose to tackle the problem of content generation using neural networks and evolutionary algorithms. Galactic Arms Race is a space combat and exploration game, as well as an application of NEAT technology to generate diverse weapon behaviors. The game is free to play and you can download it from the homepage.

• Applying Evolutionary Algorithms to the Galactic Arms Race (Blog)

Design Innovation in Game AI

Vote Winner
Procedural Geometry in LEFT 4 DEAD 2

The original LEFT 4 DEAD won the Best AI Award last year, and the community voting felt the next iteration should win the design innovation award thanks to version 2.0 of its AI Director controlling changes in levels.

• Procedural Level Geometry from LEFT 4 DEAD 2: Spying on the AI Director 2.0 (Blog)

Editor's Pick
The Animals in WORLD OF ZOO

This game was suggested by Kevin Dill. Here's how he described the game:

“Although this isn't a game that most of us would play (it's target market is much younger), the characters are extremely well realized and, frankly, lovable. The team responsible for creating them was headed by Bruce Blumberg, who did some of the foremost research on believable agents while he was at MIT, and the quality of the result reflects his influence.”

Kevin continues with what makes this an important milestone for AI design:

“Their integration of tools made it possible for much of the AI development for their characters to be done directly by the animators and designers. In addition, a large part of their success in crafting so much compelling behavior for so many different types of animals in such a short time resulted directly from the tight integration between animation, engineering, and design, and their flexibility in working together to solve problems. Often a problem that was hard to solve with AI (for example) was easy for animators — or vice versa.”

AI Technology in a Supporting Role

Editor's Pick
The City in ASSASSIN'S CREED 2

Two years ago, the original ASSASSIN'S CREED won the award for Technical Innovation in game AI thanks to its crowds, and with the sequel Ubisoft has managed to raise the bar even further. The various cities in the game have come to life thanks to the various different pedestrians: their behaviors, their animations and their interactions. Each of these features add to the overall feeling of the game's environment.

Most significantly, the development team did an amazing job integrating the various elements of the city into the gameplay. The concept of social stealth remains, but you can now also leverage the thieves and courtesans to help with your missions — for instance to sneak past the guards. With the new pocket picking mechanic, walking through a crowd becomes more fun in the process as well!

Vote Winner
The AI Director in LEFT 4 DEAD 2

This year's edition of LEFT 4 DEAD brought a few key innovations, including the ability for the AI Director to control the path that survivors have to take by blocking doors and alleyways, but also support for changing the weather patterns. The final scores in the voting suggests that both Valve's design is on the pulse of its gamers, but also that the marketing strategy is still working wonders!

• 11 Secrets about Left 4 Dead's AI Director and its Procedural Zombie Population (Premium)

Technical Innovation in Game AI

Vote Winner
Combat AI in KILLZONE 2

If you take a look at the extensive list of articles on this site about KILLZONE 2's AI technology, there's little doubt that Guerrilla Games is not only a very open studio about what it does, but it's also very focused on pushing the technology that goes into its games. In particular, this is the first documented application of an HTN planner in a real-time action combat game, as well as a use of AI strategy that's essentially bridged the gap between RTS and FPS technology.

Knowing how the team, and it's Lead AI Programmer Remco Straatman, is keen to reuse and improve upon its existing technology, this makes for a very fascinating prospect for upcoming games from Guerrilla Games!

• Waypoint Cover Maps and Efficient Raycasts on PS3 in KILLZONE 2 (Insiders)
• Not in My Line of Fire! Sensible Combat Behaviors using SPU Jobs (Insiders)
• Where Did That Enemy Go? Threat Prediction and Reasoning in KILLZONE 2 (Insiders)
• The AI in KILLZONE 2's Bots: Architecture and HTN Planning with Remco Straatman (Premium)
• From Squad Tactics to Real-time Strategy: High-Level Multiplayer Bot AI in KILLZONE 2 (Premium)

Editor's Pick
Hero Planner in DEMIGOD

DEMIGOD was the most controversial nomination of them all. It generated instant love or hate responses on our official IRC channel and even on Twitter when I brought it up. However, the game is among those I played the most this year, and I only competed against the AI in its offline Skirmish mode. It turns out over 70% of players only experienced the game offline, possibly due to the networking issues the game faced at launch.

Either way, the AI opponents are nothing short of an incredible achievement. The game is a complex strategy game where the hero Demigod's persist over the duration of the game and make RPG-style decisions, and in other moments require RTS-style strategy to decide how to achieve gameplay objectives. Given the scope of the problem, and the way the team at Gas Powered Games solved it using a hybrid planning/optimization algorithm, I think this is quite an achievement!

• DEMIGOD's AI from Role-Playing to Real-Time Strategy with Dru Staltman (Premium)
• Goal-Based Action Optimization and the Hybrid Hero AI in DEMIGOD (Premium)

Most Influential Published Research

Vote Winner
Multi-Agent Control in Adversarial Games

Over the past few years, animation research has become more and more relevant for character AI as it's been moving into the domain of control systems — for example how to create an optimal policy to traverse a motion graph using reinforcement learning. Such techniques are not only fascinating since they blur the gap between the low-level motion capture and the high-level goals, but they address a real-world need of being able to make trade-offs between these two opposing sides.

This particular paper builds on previous work in the field by tying in the traversal policy of motion clips together with gameplay dynamics of two player games. Sometimes there simply is no optimal policy and playing randomly withing known distributions is the safest bet. See the paper and its accompanying video for more details!

Multi-Agent Control in Adversarial Games Download PDF

Editor's Pick
An Architecture for Game Behavior AI: Behavior Multi-Queues

This paper elegantly avoids the common pitfalls of game AI research by tackling a problem that's relevant to developers, by respectfully citing recent work from the games industry, and building on commonly used techniques. That's quite a noteworthy achievement in itself, which few other papers from 2009 manage to equal.

On top of that, the solution is elegant and not very far from what developers are using in industry. Behavior trees are a great architecture to build at the base of any game AI architecture to help connect different components together, and being able to support coordination (one increasingly important problem) is an added bonus.

An Architecture for Game Behavior AI: Behavior Multi-Queues Download PDF

Also check the following articles on the topic of behavior trees and coordination:

• Behavior Trees for Next-Gen Game AI (Insider)
• Coordinating Agents using Behavior Trees with Ricardo Pillosu (Premium)

Summary

Both objectively from my coverage of the games and their technology this year, and subjectively via my involvement with KILLZONE 2^*, I feel this has been a great year for game AI as a whole — even compared to last year. It makes for a very promising decade ahead!

On a more personal note, I've now been working full time (and more) on AiGameDev.com for over a year now. From the many links and references scattered around this article, I hope it's obvious to what extent we've tracked down and documented the great applications of game AI this year. This is a huge part of why we exist, so thank you for your support and best wishes for 2010!

^*: Yes, that means all the votes were rigged. Not. :)

If you have any thoughts or comments, don't hesitate to post them in the forum thread...

What common mistakes do new AI engineers make when they first move into game development? How long does it take for them to realize that designers will find edge cases in the code no matter what? And why do all public discussions about game AI end up with programmers complaining about designers? We have the answers, and they are below...

A few weeks ago, the Boston Postmortem held a panel about artificial intelligence in games. It featured Damian Isla, John Abercrombie, Jeff Orkin, and finally Christian Baekkelund as moderator. As you'd expect from the star cast, the discussion was highly stimulating and provided a fresh take on the most commonly addressed topics in our field.

Below in this post you'll find the full transcript of that part of the panel discussion, as well as a festive Thank You from our sponsors!

The Isla Principle of AI Presentations

In the segment of the panel transcribed further below, Damian Isla outlines his theory about all AI talks given publicly. He postulates that each talk has a minimum estimated time until the discussion drifts towards speaking about designers — not in the most positive way.

I'm calling this The Isla Principle of AI Presentations or the "Isla Principle" for short!

Of course, making great artificial intelligence in games requires both a balance of design and code, and this part of the daily workflow is arguably the most important thing you can do. But, well, it's always a source of passionate disagreements, bugs and funny stories too — which explains this principle.

Big Mistakes of New AI Engineers

Christian Baekkelund: What do guys think are some of the biggest mistakes that a new AI engineer makes?

Damian Isla: I feel like AI programmers in general are torn between two opposing goals, one of which is AI as a game mechanic: the AI as a means to support very basic gameplay (what are you doing from second to second), and on the other hand AI as life simulation, AI for compelling characters and window dressing essentially to sell the world and sell entities in the world.

In general, I think a lot of new AI programmers don't necessarily don't think of AI as a mechanic. And I think the mistake both for the programmer and organizationally, is that the AI programmer is not brought into the design fold quite enough, and is not made to understand the high-level design goals quite enough. What is the player meant to experience, now let's craft the AI to support that. That is really the most important job for the AI programmer, much more than life-like flocking or something like that.

John Abercrombie: The key is to make an experience for the player, and as an AI programmer that's what you're doing, and even as an organization as a whole. The systems and features you build have to support that, otherwise... Just building new systems to try out new things is a good thing, but in the end you're developing a product for some player to come and have fun with. You have to keep your mind on that, it's your end goal and all your work has to support that end goal.

Another mistake that AI engineers make is that they don't try to keep things simple. Certainly, getting really complicated... as a coder sometimes you want to go out and build this awesome complicated system, but really if you try to keep things simple. The way things are direct, it's a more beautiful thing for building AI than anything else. You're going to hit all these edge cases that your really complex construction isn't going to handle well, and trust me, once designers get involved, you're going to get those edge cases a lot. By keeping things simple it keeps you agile, as design chances, as content changes, you're able to stay very agile in the face of a design [scope] that can change from RPG-style first-person shooter to a more Action first-person shooter. That's a huge change right there, and that happened on Bioshock. If you're not able to keep things simple you can't stay agile and you can't adjust to those changes.

Jeff Orkin: The only thing I would add is understanding who the design team is, what their strengths are. The mistake I've made myself and I believe I've seen other development teams make is trying to force the designers to be programmers by providing them some kind of scripting access to your AI, thinking you can offload all of the development behavior to the design team. With some studios that does work well, but my own personal opinion is that it's better to have autonomous behaviors where designers create worlds that can showcase the behaviors, and the AI developers can take care of the details.

John Abercrombie: I like to say, give the designers a lot of rope, but not enough to hang themselves. Build the tools that they need, and build an autonomous AI, and the tools that you need to control that autonomy, rather than total simulation or total scripting.

Damian Isla: Every single AI talk that you'll ever see done publicly, there's an estimated time to start complaining about designers. It's going to be a common theme here...

John Abercrombie: It's like "time to crate" or something like that.

Christian: I've just realized my role as moderator is now going to be the defense of designers too.

Best Wishes from Our Sponsors!

SpirOps is a middleware development team focused on AI. Their ultimate goal is to allow video games and simulations development teams to enter what we call “the Living Game era”. To design more realistic behaviors with a never reached complexity, the SpirOps developed an artificial intelligence design paradigm called “Drive Oriented” which allows designing AI with graphical tools and keeping a linear complexity during the brain creation process.

PathEngine provides a sophisticated toolkit for agent movement, built around an advanced points-of-visibility pathfinding core. This gives you powerful paired path planning and collision against a sophisticated, continuous space, pathfinding movement model, with robust integrated dynamic obstacle functionality and exact representation of agent shape, for seamless movement over overlapping ground geometry.

Havok is the premier provider of interactive software and services for digital media creators in the games and movie industries. With world leading expertise in physics, animation and tools, Havok’s business is to turn customers’ creative aspirations into technical realities. Havok’s modular suite of tools gives power to the creator, making sure that clients can reach new standards of realism and interactivity, while mitigating the overall cost and risks associated with creating today’s leading video games and movies.

We bring bytes alive! This is the vision and motivation that drives Artificial Technology GmbH. Graphically, many computer games already emulate the real world quite faithfully. The behavior of the characters, on the other hand, is often less authentic. EKI One Middleware (emotional & artificial intelligence) is a new solution by Artificial Technology GmbH which allows game developers to bestow on their characters with emotional behavior.

In December for the past couple years, AiGameDev.com has hosted The Game AI Awards to celebrate the games that came out over the previous twelve months — and particularly those with great artificial intelligence. This time it's a bit different, however...

This year, the awards have been extended to encompass innovative applications of artificial intelligence, and creative uses of Game AI in general. This means you have a much more important role to play by submitting in your nominations, to help reward current games that broke the mold and help shape future developments in the field!

The Golden Marvins

Welcome to the 3rd Annual AiGameDev.com Awards for Game AI, where the best games of the year are nominated and voted for by professionals, enthusiasts, and researchers in artificial intelligence for games.

Here's the plan for the new few weeks:

1. THIS WEEK — Post your nominations for the games you think are worthy of an award. Either write a comment below, on the forums, or email in your suggestions to alexjc at AiGameDev.com.

2. NEXT WEEK — The most popular nominations are selected, and voting begins in The Game AI Forums. You'll need to sign-up before you can participate!

The winners will be announced on December 28th.

Screenshot 1: Marvin needs your nominations!

Change of Focus

Past editions of the AiGameDev.com awards have focused more on the "event" behind the nomination process and the voting. It brings the community together and it's a nice way to reflect over the games that came out this year. Last year I introduced an award for the Best Research in Game AI, which turned out to be both interesting and refreshingly different!

The new award helped emphasize which research the community finds the most useful. Based on this positive impact, I've expanded the scope of the awards even further this year, by picking categories to help drive the development of artificial intelligence in the games industry as a whole... In particular, a big space where there's huge room for improvement is Design & AI, as well as Better Characters.

These new award categories require more input from you over the next week, during the nominations, so be sure to add your comment below!

Categories

There are now seven categories in this year’s nominations.

Best AI in a AAA Game

What was the best artificial intelligence in game with a big budget and high production values, published via the traditional distribution channels?

Best Non-Player Character

AI technology doesn't exist in a vacuum; it requires character design, art, animation, writing and voice acting. Which game character combined these together best?

Best AI in an Independent Game

Which game written by a small team of developers, either web based or available on PC/Mac/Digital Distribution, had the best AI?

Design Innovation in Game AI

AI requires some solid ideas and a good game design to really shine. Which game showed off the best AI design?

AI Technology in a Supporting Role

Non-character AI (and non-actor AI) is becoming increasingly important as games become more complex. Which game used artificial intelligence best in unusual places?

Technical Innovation in Game AI

Who had the best ideas and technology for 2009, including middleware vendors or games listed above?

Most Influential Published Research

Which white paper, book or in-depth article about game AI has & will influence the field most?

All the items you nominate of course must have been released after the 1st January 2009 and before 31st December 2009.

Criteria

Remember, you’re giving an award for the best artificial intelligence in a game. This means it must be a balance of two things:

• Entertainment — The AI in a game isn’t supposed to behave perfectly; in fact it’s often supposed to make mistakes in a convincing way. So, are the non-player characters (NPC) or non-character AIs fun to play with or against?

• Intelligence & Believability — Do the in-game actors fit in with the design and story? It’s not purely about smarts, but it helps!

Of course, the two are not mutually exclusive, on the contrary! The best games each year successfully use intelligent behaviors to create a fun experience for the players.

Click here to let us know about your nominees. The voting will begin next week, so stay tuned for this year’s best game AI.

Finite-state machines have been getting a lot of bad press over the past couple years, and justifiably so! When applied to AI for building purposeful goal-directed behaviors, traditional FSMs just don't scale very well. This is the main reason developers in the games industry have been primarily moving towards systems like behavior trees instead...

However, hierarchical concurrent state machines (aka. HCSM) were bumped up to the top of our list of topics since the bots in Left 4 Dead are apparently based on HCSM. Indeed, as Mike Booth (Project Lead at Valve on the game) confirmed for this article, the implementation of the bots is based on ideas in the paper discussed here. Read on to find out more!

The rest of this white paper review is written by Luke Dicken, researcher at the University of Strathclyde and our resident academic here at AiGameDev.com. He's also known as @LukeD on Twitter.

Screenshot 1: The bots in Left 4 Dead 1 are controlled using HCSM.

Motivation

Designing and organizing sophisticated AI systems is very hard, particularly when building them as one large monolithic control system. Working out the processes by which you can make a system do what you want it to in a complex and changing environment can be a lengthy process, and invariably some set of circumstances that the system needs to cope with end up being overlooked.

In this article, you'll learn about the Hierarchical Concurrent State Machine (HCSM) which gives a framework in which AI systems can be described in a modular manner, whilst still capturing the interactions between aspects of the world and the system, or between different components of the system itself.

Contribution

HCSMs were introduced in 1995 in a paper entitled HCSM: A Framework for Behavior and Scenario Control in Virtual Environments, written by Cremer, Kearney and Papelis. The concept of the HCSM has been influenced heavily by the Statechart extension to State Automata. Designed primarily for embedded and real-time systems, statecharts allow for a group of states to be gathered into a single superstate. Superstates can then be linked with transitions and treated more or less as states themselves. (This is a very very brief synopsis of statecharts, see the paper linked from this page for details).

HCSM takes this notion a stage further, by abolishing the concept of state altogether; the basic building block in an HCSM is an HCSM. However, unlike in statecharts, HCSMs are not made transparent to their parent HCSM. Another difference is that each HCSM has an "activity function" associated with it which is used to generate an output based on, but independent of, the active state within the HCSM. The HCSM specification defines input wires used to supply a continuous stream of data to the machine, as well as controls and dials which are used to set parameters within the machine. It is important to note that time within the machine is discretely modeled, and although changes to the input are visible immediately inside the machine, changes made to the controls are not reflected until the next tick.

An HCSM is "Sequential" if the HCSMs it contains are linked by transitions, and "Concurrent" if the HCSMs are not linked by transitions. In sequential HCSMs, a single HCSM child can be active at a given tick, whilst concurrent HCSMs allow for all the children to be active at each tick.

Figure 2: Diagram from the paper showing the structure of an HCSM. (Click to enlarge.)

HCSMs provide a very robust modular formalism in which you can define the behaviors of an AI system, and easily capture intricate interactions between these behavior. This avoids a lot of the confusion that designing these complex systems might otherwise lead to, and makes for a much more understandable representation of what you are trying to achieve.

Abstract & Download

Here's the official abstract of the white paper, published in 1995:

“This paper presents a framework for behavior modeling and scenario control based on hierarchical, concurrent state machines (HCSM). We present the structure and informal operational semantics of hierarchical, concurrent state machines. We describe the use of HCSM for scenario control in the Iowa Driving Simulator (IDS), a virtual environment for real-time driving simulation. The paper concludes with an outline of a forthcoming HCSM-based scenario authoring system that will permit non-specialists to graphically program behaviors and design experiments for IDS.”

Here's the reference for the paper and the link for downloading the PDF:

HCSM: A Framework for Behavior and Scenario Control in Virtual Environments
J. Cremer, J. Kearney & Y. Papelis
Download PDF

Discussion

It isn't a massive leap to see how this approach can be used to design control systems for agents, for example the bots in Left 4 Dead. After all, at their core they are still State Automata. HCSMs can be arranged such that behaviors that need to execute simultaneously are contained within a concurrent HCSM, while more traditional mode-switching can be captured using a sequential HCSM, and these can be nested within each other, and feed into each other in order to generate a complex system using a set of very basic building blocks.

However, one of the main proposed uses for the HCSM technique is not for agent control, but for scenario control. HCSMs being used in this manner are termed "Directors" and can be used to orchestrate specific conditions within a noisy environment. In the paper introducing the technique, the authors talk specifically about creating specific circumstances within the "Iowa Driving Simulator" (a precursor to the more modern "National Advanced Driving Simulator"), a virtual environment with a physical simulator component based around an actual vehicle shell, making for a very advanced simulation experience — comparable for example to airline training simulators.

The problem with this simulated environment at the time was that there was not a good technique to allow situations to be created that a user of the simulator would need to react to. For example, consider another driver in traffic who cuts the user off. It is difficult to orchestrate this as a general case whilst making the simulation seem fluid, since it depends to a large extent on the behavior of the user — not just from a timing point of view but also from an aggression point of view. A naive technique might have the other vehicle execute its maneuver when the user's vehicle hits a specific trigger point in the road, but in a fully dynamic world, a vehicle sat waiting to be triggered would be very noticeable and jar the user out of the suspension of disbelief that the simulation encourages.

Screenshot 3: Bots moving through a warehouse in Left 4 Dead 1.

An initial solution used a complex one-layer state machine to model speed matching and slowing behavior to put the "enemy" vehicle in the right position at the right time to perform the required action that the user would need to react to, but as you can imagine, a typical state diagram that could capture this level of complexity was of unmanageable complexity, leading to significant issues in terms of code reuse and debugging.

HCSMs model these interactions in a much more elegant way, making the whole process easier by virtue of their modular hierarchical nature — the states for speed control to make sure an incident occurs at the correct location relevant to the user's vehicle for example are much more portable under this architecture and can be lifted with much less trauma and put into another structure to replicate the functionality in a different scenario, essentially providing a behavior-centric view of a state machine.

Implementation

Conceptually this seems a robust approach, but how does this work in practice? After all, what really matters is how you can implement this in our own applications. The original paper on HCSM kindly provides some pseudo-code algorithms that define exactly how an HCSM is put together. The original pseudo-code is as follows:

ExecuteHCSM(hcsm)
{ ExecutePreActivity(hcsm.pre_activity_function); transition_to_fire := SelectTransitionToFire(hcsm); if (transition_to_fire) then hcsm.active := transition_to_fire.to_state; ActivateState(hcsm.active); for each active child m of hcsm do ExecuteHCSM(m); return(ExecuteActivity(hcsm.activity_function));
}

So you can see from this that each HCSM is made up of essentially four functions — at the top level you see the overall ExecuteHCSM function. There is a pre-activity function which allows controlling the flow of information into the child HCSMs to be executed this iteration. You then select which transition to fire using the SelectTransitionToFire function, and then activate the relevant state for that transition within the HCSM. Remember that transitions are only relevant for sequential HCSMs, concurrent ones will have all the children active at all times. Then, you iterate across the list of active child HCSMs and execute each one. Note importantly that this is a recursive process, and the algorithm descends the hierarchy of the HCSM structure executing the pre-activity functions of each one in a descending manner, but the activity functions themselves are activated as you bubble back up the execution stack. This is a very important aspect of the temporal order of each iteration as it allows the children of an HCSM to directly affect the activity function of their parent HCSM.

Figure 4: A hierarchical graph-like structure representing a HCSM. (Click to enlarge.)

Evaluation

Applicability to Games: 9/10

Not all games are going to benefit from this technology, but any developer that wants to retain a degree of directorial control over the play whilst at the same not constricting the choices offered to the players will find it beneficial.

Usefulness for Character AI: 6/10

HCSMs don't really bring much new to the table in terms of controlling NPCs. They would be appropriate for use, but they aren't necessarily the best approach.

Simplicity to Implement: 6/10

HCSMs are more of a paradigm than something precisely implementable. As such they can be as simple or complicated as you need them to be. At their most basic, an HCSM object is 4 functions, making implementation relatively straightforward, but this overlooks the interplay of multiple HCSMs and parents with children.

HCSMs provide a useful way for reworking traditional state automata into an architecture better suited to the kind of work AI developers do. Their power lies in the simplistic way they represent complex interactions, with an almost emergent component in the way that they can be put together to create interesting behaviors. Their use as a stage manager is particularly significant for game developers since it provides a lightweight reusable technique to create game worlds that are both interesting and believable, and support altering the world and NPCs within it so that things you want to happen in the world happen in a way that is appropriate given the player's activity. This brief introduction to HCSMs has been based off the original paper by Cremer, Kearney and Papelis, and for a much more detailed overview of the technique I recommend reading this.

Note: This article was written by Jeremy Cothran and Alex Champandard (editor) about Jeremy's winning entry to the 2009 edition of the 2K Bot Prize.

Most AI systems in the games industry focus on short-term reactive memory and combat behaviors applying techniques such as behavior trees.  However, there seems to be little support for long-term memory, for example remembering locations in space that mark events that occurred.  In our daily lives, we internally map, model and remember our surroundings and experiences.  This begs the question, how can we similarly organize and leverage longer-term memory within modern AI?

This article looks into the concepts and implementation that went into creating the winning Bot Prize entry this year.  In particular, it shows how a SQL database was used for long term memories of hotspots which were analyzed to improve the AI.  It also discusses the performance and benefits of such an approach and possible future improvements.

Screenshot 1: The BotPrize winning entry in Unreal Tournament 2004.

Long-Term Memory using SQLite

One experimental approach towards providing long-term memory for AI is to use a relational database (RDB).  The database would be responsible for managing lists of information recently acquired within a set of tables.  In particular, an ideal candidate implementation is SQLite: a lightweight, portable, file-based relational database which can help in this regard.

SQLite provides persistent file-based records in an easily query-able format which can be accessed via a Structured Query Language (SQL).  One important benefit of this approach is that it provides a shared data model for either the game representation (e.g. map, waypoints, etc.) or arbitrary events (consisting of type, location of combat, outcomes).  Maintaining such data enables both in-game or offline analysis using a variety of techniques/tools such as R — an increasingly popular statistical language.

(Note: Such techniques are already gaining popularity for gameplay analysis and data-mining, for example Valve's so-called Death Maps in Team Fortress 2.)

Runtime Database Usage & the Bot Prize

For the 2009 Bot Prize contest, the winning entry was my sqlitebot (see video, powerpoint, code) which utilized a sqlite database.  The RDB was used for two things:

1. Tracking the locations of kill/death events, also called map hotspots.

2. Storing the cross-visibility of waypoints for use in evasive behavior.

The bot started from the example 'advanced' bot from the Pogamut website with a circle-strafing function added from the previous year's winning AMIS bot (both documented and credited within the code).  Pogamut is a collection of Java based projects primarily providing a Java NetBeans developer/debug interface and Java object API to control Unreal Tournament 2004 bots.  Pogamut uses the Gamebot message API as an intermediary between itself and the game.  Screenshot 2 shows the IDE with sample bot state/log messages in the lower right corner and controls for sending game commands such as gameplay speed, changing maps or adding bots in the upper left.

During development of the bot, I noticed that the previous years winners had some memory processes in regards to weapon selection and effectiveness, but not in regards to map events.  The example bot included a 'pursue' function, but this only tracked the last known enemy location.  An easy initial long-term behavior to add would be knowledge of the map level hotspots: areas where the bot had scored a kill or been killed.

Screenshot 2: Pogamut IDE. (Click to enlarge.)

Hotspot Behavior

To enable a long-term memory of recently active locations, whenever the bot kills another player or is killed by another player, a row is inserted to the observations table with the location of the event, a timestamp, and a weight set to 1.0.  When the bot is respawned or looking for a destination, it randomly picks from the most recent n recentRow locations that have been created in the past t recentTime seconds.  In practice, n is set to 3 recent rows which are queried from within the past 45 seconds.

In terms of performance, reading and writing to the database are currently millisecond operations — and these insertions and selections should scale to table sizes in the millions of records.  This is acceptable for performance since the decision is used for strategic/tactical pathfinding decisions, and any lag in the write or read would not effect more immediately noticeable combat reactive decisions.

Database tables and search indexes are created once initially before the game begins.  The database can be file saved and copied for reuse among other games in its initial unpopulated state or a later populated state.  In this experiment, while the database is only accessed by a single agent, the database could be concurrently accessed by several agents across multiple games.

The rows added to the tables are timestamped with real-world time and game time for reference.  Here's how the table is specified:

CREATE TABLE observations ( row_id integer PRIMARY KEY, row_entry_date TEXT, map_level TEXT, navpoint_id INT, unreal_id TEXT, event_location TEXT, event_time REAL, event_weight REAL);

When the bot is later looking for a target destination the following table query is issued:

String statement = "SELECT * FROM observations WHERE row_entry_date > strftime('%Y-%m-%d %H:%M:%S','now','-2 minute') AND event_time > "+gameTime-recentTime+" AND event_weight = 1 AND map_level = '"+map_level+"' ORDER BY row_entry_date DESC LIMIT "+recentRows+";";

Here's the query's result representing the most recent 3 locations of a map kill/death:

1333|2009-08-15 15:54:41|DM-Test1|1|DM-Test1.PathNode16|5663.6,-1403.66,-86.15|290.35|1.0
1332|2009-08-15 15:54:29|DM-Test1|0|DM-Test1.InventorySpot5|6739.6,-344.48,-86.15|277.33|1.0
1331|2009-08-15 15:54:16|DM-Test1|1|DM-Test1.PathNode16|6503.56,-1667.54,-86.15|262.97|1.0

One of these rows is randomly chosen as the hotspot, and the bot heads towards that location.

Screenshot 3: Areas around weapons and items quickly become hotspots for the bot.

Evasive Behavior

Another human-like behavioral feature that's noticeably absent in most bots is retreating or evading an enemy after combat initially begins. In the case of sqlitebot, this happens when the health reaches a minimum target threshold (less than half).

Diagram 3 demonstrates how an evasive behavior works; the bot's target destination navpoint is selected outside of the enemy's current visibility set.  The from/to navpoint visibility table was populated in an initial pre-game bot map survey step that logs all this information and stores it for runtime use.

Diagram 4: Green locations are navpoints not in player to_navpoint_id visible set, and red locations are from_navpoint_id closest to player.

The table that stores this visibility lookup table is the following:

CREATE TABLE navpoint ( row_id integer PRIMARY KEY, row_entry_date text, map_level text, from_navpoint_id int, to_navpoint_id int, visibility int);

A unique index is also added to prevent possible duplication of the same rows during the initial map survey process:

CREATE UNIQUE INDEX i_navpoint on navpoint (map_level,from_navpoint_id,to_navpoint_id);

When the bot has low health and is looking to evade, the AI selects visible navpoints from this table based on the nearest enemy navpoint, which should obviously not be pathed to:

String statement = "SELECT to_navpoint_id FROM navpoint WHERE map_level = '"+map_level+"' AND from_navpoint_id = "+memory.getKnownNavPoints().get(hideFromNav).ID+";"; ResultSet rs = stat.executeQuery(statement);
ArrayList<Integer> ArrayToGet = new ArrayList<Integer> ();
while (rs.next()) { ArrayToGet.add(rs.getInt(1));
}

The code then selects a random hidden navigation point as the destination, assuming it's not in the player visible arrayset that was determined using the previous query.

boolean hideNavFound = false;
int thisNavpoint = 0; if (!ArrayToGet.isEmpty()) { while (!hideNavFound) { int myRandHide = random.nextInt(memory.getKnownNavPoints().size()); thisNavpoint = memory.getKnownNavPoints().get(myRandHide).ID; if (ArrayToGet.contains(thisNavpoint)) { log.info("Navpoint is visible:"+memory.getKnownNavPoints().get(myRandHide).UnrealID.toString()); } else { log.info("navpoint not visible:"+memory.getKnownNavPoints().get(myRandHide).UnrealID.toString()); hideNavFound = true; } }
}

Screenshot 5: Unreal 2004 is still used by academia as the primary research platform for FPS AI.

Other Additions

In addition to the hotspot and evasive behaviors, further tweaks were made to the original bot's AI based on the following observations.  The two most obvious giveaways that an agent is a bot are:

1. Futile behaviors, such as running in an endless loop without progress towards the goal, or

2. Predictable behaviors, for example repeatedly jumping, dodging or employing the same move or tactic.

I added a simple associative array which instructed the bot to ignore a goal (e.g. weapon, health, pickup) for a period of time if it was unable to currently path to or complete that goal.  To achieve this, I used a hash reference between a goal and a failed attempt time.  The goal associative array allowed the bot to temporarily dismiss goals which might produce futile behaviors.

Furthermore, to avoid predictable behaviors, some random fuzziness was added to the bots most common combat reactive decisions, for instance using simple random choices between acceptable alternatives such as ignore, dodge or jump direction on an incoming projectile.

Finally, the bots reaction times to incoming projectiles and weapon switching was also slowed by around 200 milliseconds (implemented as simple delay loop) to give a more human reaction time appearance.

Screenshot 6: UT 2004 features a collection of both indoor and outdoor levels, though vehicles were not part of the Bot Prize.

Further Work

It would be useful to have a common database schema abstraction of such game data for analysis by multiple tools or agents.  For instance for a map representations, the following waypoint attributes and associations would be useful to have for many 3D environments:

• Waypoint positions and their connectivity with each other,

• The initial association between waypoints with tactical attributes such as cover or open area, and

• The changing association over time with gameplay events and shifting tactics in the game.

As for performance, a faster intermediate caching layer for the data could avoid the slower latencies handling database connection via a socket, or supporting disk I/O.  If multiple parallel agents are using the same database resource, then there can be concurrency latencies related to read state or write access.  Performance for reading and writing from the database also depends on the number of rows in the table, so effective search indexes are important for scaling up to millions of records or larger.

SQLite also has the option of running the database in-memory and not to disk, which would most likely offer performance benefits.  Spatialite is a 'spatially enabled' sqlite database including common geometry datatypes and related indexes/functions which may offer some further ease of implementation and performance gains.

Finally, it would be interesting to explore how multiple agents might synthesize and share their combined knowledge via such database information, over the course of several games.  Further, these ideas could be applied to squads to help with strategic reasoning also.

Conclusions

Many human-like behaviors such as evasion or a "volley"-type dynamic between players in combat are particularly suited to competitive multiplayer games.  The ability to model, cache, analyze and recall individual events strategies across multiple games opens up opportunities opportunities for stronger and richer AI to develop in a more open-ended competitive environment.

Since Valve announced Left 4 Dead 2, the feature of the AI Director 2.0 that grabbed the most attention has to be the dynamically changing level geometry. Apparently the game can not only control the weather patterns, but it can also change the route the survivors take while moving through the world.

In this article, you'll find out exactly how the AI Director 2.0 adapts the geometry procedurally. There's also proof in the form of exclusive screenshots from the demo of L4D2, which was released to the general public a few days ago. (The screenshots are exclusive in the sense that I took them myself, and nobody else has these!)

(Special thanks to @RevFry on Twitter for helping isolate all these variations.)

How It Works

Last week we held a Zombie AI Halloween Special, in which Phil Carlisle and I (Alex Champandard) speculated how L4D2 would handle the procedural geometry. Based on our combined experience, and the in-depth Premium feature I wrote about the original AI Director in Left 4 Dead 1, it turns out we came really close.

Here's how it works:

1. There are individual variations in the geometry that are manually edited by level designers.

2. These are grouped into sets of possibilities for the geometry around a particular location in the level.

3. The AI Director uses it's pseudo-random selection among these sets to determine what happens in each game.

This approach is very similar to the way the AI Director handled the placement of scavenge items and weapons in the original game, allowing control by the designers yet sufficient unpredictability to keep things interesting.

The Demo

The only part that wasn't easy to guess was the scale at which the levels would be varied. Phil assumed there would be small rooms or segments in the world that would change, and I figured doors and fences would be the easiest way to introduce variation into the levels.

Based on the demo so far, the AI Director 20 is indeed using boarded doors, riot fences, and walls to block off alleys. In this part of the first level, there are three different paths the survivors can take. From experimental evidence, 1-2 of these paths are left open and the other 1-2 are closed off procedurally. This seems to happen only in Advanced and Expert modes.

(See the screenshots below. Click to enlarge.)

The Stairs

The Alley

The Door

Discuss!

Anyway, based on this we can start speculating about the rest of Left 4 Dead 2!

• Do you expect there to be larger segments of geometry that change in the full version?

• Will such local path changes (barely 10-20 meters difference) affects the gameplay enough?

• How do you think this kind of technology can be applied to other games or genres?

Let everyone know what you think and post your reply by commenting in the forums.

INVITATION: What are the next big challenges for Zombie AI? Join resident expert Phil Carlisle and your regular host Alex Champandard in a Halloween Special this weekend. The online presentation is open for anyone signed-up (free) to AiGameDev.com and will take place live on Sunday, November 1st. Details here.

Of all the game modes in Left 4 Dead, Survival has some of the most interesting dynamics from an AI perspective. From the initial concept, to survive as long as you can with help of your four buddies, the game mode quickly turns into a process of finding optimal locations in the map to defend...

Obviously, when there's a medal or achievement involved, this optimization process becomes particularly creative! What makes this interesting for the Zombie AI, is that the best locations are those that the infected horde has a hard time reaching... Cue unexpected results.

This article starts by explaining how the navigation system in L4D works. Then, you'll find out the kinds of problems that occur when players are challenged with finding loopholes in the zombie's ability to move around the world! Finally, the last part discusses the variety of solutions that would be available to resolve such issues.

With What Shall I Build It?

Screenshot 1: Navigation Mesh chunk in the forest. A single polygon is highlighted in yellow, with its neigbours drawn in red.

Left 4 Dead uses navigation meshes as the basis for the zombie's movement around the world. These are based on the technology from Counter Strike: Source that includes the official bot. (See Mike Booth's GDC 2004 presentation.)

• The navigation meshes are built partly automatically, but there are many commands in the game's console for manual editing.

• Each polygon is an axis-aligned quad, so the orientation is constrained — though the size seems to be very flexible.

• The polygons are connected through a variety of links, which can be traversed by walking, jumping, etc.

This solution, in particular the axis aligned quads, is not very common. Most often, polygons can be placed arbitrarily in space — either manually or using automated analysis.

Screenshot 2: Navigation mesh chunk inside an apartment building, littered with debris. (Click to enlarge.)

How Shall I Exploit It?

Zombies are supposed to reach you, the player, anywhere you can stand to keep the pressure on. The Survival levels are in fact customized with barricades and invisible polygons to keep players within the playing area. However, there are bits of the level without (adequate) navigation meshes, so they become inaccessible by the AI zombies.

The following scenario is a typical illustration of the process of exploiting the game's Survival mechanics:

“If you manage to jump onto a tricky location such as the cargo plane in Dead Air, or the chimney in the Lighthouse, the bulk of the horde will not manage to reach you. In fact, they'll simply rush to the location in a polygon on the level beneath you.

Since nobody is killing the zombies, the game ends up with too many entities on the server, and the networking seems to slow the game to a crawl. As long as you can dispatch the occasional Smoker without falling out of position, you can effectively defeat the game.”

Another particularly creative exploit in the Sewers is to jump through the ventilation tunnel and rush back to the Safe Room to deal with (smaller) waves of infected there.

Screenshot 3: Navigation mesh chunk outside in the street, including jump links and drop-down connections.

How Shall I Fix It?

It seems there are three solutions to resolve this problem:

1. Manually update the navigation meshes in the Survival maps as loopholes are found. Valve has extensive statistics about the game, and can easily find locations in the level that are easy to exploit.

2. Develop more robust automatic navigation mesh extraction tools and a more flexible (non axis-aligned) representation that reduces the chances of there being discrepancies between the collision mesh and the AI's navigation representation.

3. Address the problems using game design changes, encouraging the players to move more rather than remain in a fixed position. This is a problem generally with the design of Left 4 Dead as a whole, though, not just survival mode.

Most likely the reason these issues have not been fixed by Valve is that it's not cost effective to implement either of these solutions. And arguably, experienced players take pride in finding loopholes and exploits anyway, so why punish them? For reference, Left 4 Dead 2 seems to address these issues using a redesign.

Screenshot 4: Quad polygons outside near the farmhouse. (Click to enlarge.)

Summary

Replayable games are a good thing for both the developers and the players. However, highly replayable games put a heavy burden on the underlying technology — and AI is no different. Navigation is one of the first things to break in a game, and with highly replayable experiences this becomes more obvious.

Modern technology can be used to resolve such issues and avoid holes in navigation meshes, for example using BSP-based analysis or voxelization techniques. However, by the time you notice the problem it's most likely too late to do anything about it! In that case, redesigning the core mechanics and shipping a sequel the year after is a sensible option.

REMINDER: Join resident expert Phil Carlisle and your regular host Alex Champandard in a Halloween Special titled “Zombie AI That's Not Brain Dead.” Discussion will focus on the big challenges of zombie behaviors, and what's next for infected AI. The session is open to attend for anyone signed-up (free) to AiGameDev.com and will take place live online on Sunday, November 1st at 16:00 Eastern / 13:00 Pacific / 22:00 Central Europe / 21:00 U.K. time.

Editor's Note: This coverage from IEEE Symposium on Computational Intelligence and Games 2009 was written by Luke Dicken. In particular, his article looks at some of the key research from the conference, and discusses the relationship between industry and academia as it came across at the conference.

CIG is a refreshing conference to my mind because you can put any three attendees in a room and get four different takes on what the conference is about. There are the Game Theorists, talking Nash Equilibria and mixed strategies (Hingston, 2009), the Serious Games people dealing with a more simulated what-if approach to the world — in scenarios such as Disaster Relief or Naval Strategy (Avery, Louis, & Avery, 2009). There are researchers working on a whole range of more classical board and card games such as Poker, Diplomacy or Risk (Kemmerling et al., 2009). And of course, there are the Video Game researchers — but even within this group there are further classifications to be made between those using games as a controlled environment in which to develop better AI techniques (Thompson & Levine, 2009), those using AI to push forward the use of technology in contemporary games (Galli, Loiacono, & Lanzi, 2009), and those using the marriage of advanced AI methodology with video games for some other end, such as behavioural modelling of players (Drachen, Canossa, & Yannakakis, 2009) or automated content creation (Tanimoto, Robison, & Fan, 2009).

Even within our own specific niche, our community remains very diverse. Not only diverse but also of a very high quality — it's hard to single out specific pieces of research to point to as being worth mentioning, because it almost certainly means excluding something else that deserves to be here. You can see the full proceedings here to make sure you don't miss anything. (Also see the bottom of this article for the full references from the previous paragraph!)

Research Highlights

By far the most interesting paper to me was describing an application of AI to creating an agent to play Magic: The Gathering (Ward & Cowling, 2009). I'm sure that many of you will recall Magic fondly from your childhood or adolescence — many more of you might remember it more as a significant money-sink that consumed your entire life for a period. The paper presented an approach to a subset of the game, using only the "creature" spells (i.e. those that summon minions which you can use to attack the opponent or use to defend against such an attack) and was designed using a Monte Carlo based approach. This plays out a set of games from the current state using the UCT algorithm to simulate play in order to gather a sample of how the game is likely to turn out based on your choice of action at this point. So far the results of applying this to the slim-line version of Magic have proven pretty promising, and it will be very interesting to see this develop into more advanced versions of the game — not only to develop great automatic Magic players (a challenging goal in itself), but also to prove the power of the approach in an environment with extremely complex interacting effects — if it proves effective then it could reinforce even more the potential of Monte Carlo for game strategies in general.

Monte Carlo Search Applied to Card Selection in Magic: The Gathering
Ward, C. D. & Cowling, P. I., CIG 2009.
Download PDF

Another great paper showcased an approach to extracting data from Starcraft replays in order to predict the strategy being used by the opponent (Weber & Mateas, 2009). Broadly speaking the idea is to characterise a replay as a feature vector reflecting key points within the game such as when building are create and units trained. This allows for an analysis of the manner in which the tech tree is being expanded, which gives the option to predict what the aim of a player is — as a naïve example, they are unlikely to focus on unlocking high-end units unless they intend to use them for example, although the technique presented is much more powerful than just this level of observation.

Generalising these into more broad strategies for classification can then identify trends within games that can be used, as well as invariants, particularly with an emphasis on the different game races being represented by the players. For example, in Terran vs Protoss games, a trend was identified where the vast majority of Terran players would create a Factory type building at around four minutes into the game. These trends can then be isolated and named to provide a broad description of a strategy being used, which can then be used to analyse the frequency with which it is employed in different. It was then shown that using this data, machine learning techniques could be used to predict strategies as early as five minutes into the game with a fair degree of accuracy (70%).

A Data Mining Approach to Strategy Prediction
Weber, B. & Mateas, M., CIG 2009
Download PDF

Many of you will have seen the recent interview with Robin Baumgarten talking about his recent entry in the Infinite Mario competition, but one paper presented a complete inversion of the same basic toolkit. Instead of creating an agent capable of playing any level generated of Mario Bros, it sought to identify characteristics of a level that appealed to players in an effort to allow content designers to better understand what they are making (Pedersen, Togelius, & Yannakakis, 2009). In order to do this, it generated a range of levels and humans were invited to play through them. By capturing the behaviour that these players exhibited, along with feedback on their opinions, a neural network was able to map the characteristic traits of the level to a range of metrics such as "challenge", "frustration" or "fun". Although by their own admission, the approach isn't quite there yet, its definitely one to watch as it gets enhanced.

Modeling Player Experience in Super Mario Bros
Pedersen, C., Togelius, J. & Yannakakis, G. N., CIG 2009.
Download PDF

I also wanted to mention a paper that presented an approach to evolving multi-modal behaviours which was awarded Best Student Paper at the conference (Schrum, Miikkulainen, & Member, 2009)⁠. The work presented an approach to evolving different behaviours within a neural net by introducing distinct operators that could be used to duplicate the network and introduce new connections between nodes. The example used was a small demonstration called "Fight or Flight" in which NPCs were evolved to either fight the player or run away from the player. The aim of the game is for the NPC team (four agents) to kill the player, however there are two distinct modes:

1. Fight, in which the player agent is equipped with a weapon to fight back and damage the NPCs, and

2. Flight, in which the player agent has no weapon, making the NPC agents invulnerable.

This gives rise to two competing behavioural techniques, one cautious and one aggressive, which both must be expressed. Using the new mutation operators they proposed, the authors were able to evolve agents capable of tackling either task with great success, meaning that this new approach to evolving neural networks for more complex domains is definitely looking promising.

Evolving Multi-modal Behavior in NPCs
Schrum, J., Miikkulainen, R. & Member, S., CIG 2009.
Download PDF

The Diversification of AI

Photo 1: The center of Milan, Italy where CIG '09 was held.

The highlight of the conference for me was how seeing how powerful AI techniques are becoming as they begin to be applied in much more interesting and non-obvious ways. The award for Best Paper was presented to Hastings, Guha and Stanley of the University of Central Florida for their work on Galactic Arms Race (Hastings, Guha, & Stanley, 2009), summarised in an excellent paper and presentation given by Stanley. Galactic Arms Race was previously covered on AiGameDev.com in this article, so I won't go into too much detail. However, the broad idea is that rather than focusing on using AI to build harder or more realistic opponents, the UCF team has instead created a game in which the weaponry evolves — the chromosomes define the mechanics of the weapon: spread, rate and even aesthetics and then fitness is evaluated based on the amount of use a particular weapon receives. Based on this a new group of weapons are made available for the players to collect (or ignore) at the next iteration, and the process repeats itself.

GAR is played on centralised servers, so the research team has access to see the results of the evolutionary algorithms first hand, and rumour has it that the game will shortly be available through XBox Live. The game itself was developed inhouse by UCF, but despite this the visuals remain of quality fully comparable to industry — a far throw from what you might expect from an academic project, but proof positive that academia can create a high quality gaming experience around a specific research area (although this is somewhat less surprising given the team's track record; Stanley was the originator of the NERO project implementing the rtNEAT algorithm for trainable squad-based battles).

The Keynotes...

Screenshot 2: Forza Motorsport 1, with the original Drivatar technology.

In contrast, the keynote by Microsoft Research's David Stern was something of a letdown for me; although a great presentation in its own right, it covered three main areas in which AI techniques have been applied to gaming. Firstly, the Drivatar system built into Forza Motorsport, in which gamers could "train" the console to drive the way they do, and then allow some races in the long career-mode to be played by simulation. This training is done using Neural Networks and attempts to replicate the way a player handles specific situations and types of track elements such as hairpin bends or chicanes. All well and good — interesting even — but Forza shipped in 2005.

Secondly a Reinforcement Learning approach to fighting games was demonstrated, using Tao Feng: Fists of Lotus. This was a very interesting section of the presentation, being able to watch as reward tables were updated based on the AI's evaluation of what moves worked in given situations, along with video to highlight it in action at various stages in its learning, served as a great demonstration of the power of the approach. However, Tao Feng shipped in 2003, and regardless, this system did not end up being part of the shipped product. Finally there was discussion of the MS TrueSkill system for player matching and ranking — a nice application but again, something that has been built into all XBox Live titles since 2005.

On a personal level I found these demonstrations interesting, and getting a look "under the hood" was quite informative, but there does seem to be something amiss when one of the biggest industry research labs is not able to show any work more recent than four year old research that has already been reasonably well disseminated. To some extent I believe (and certainly hope) that this lag is more due to commercial concerns of documenting ongoing projects than an entire research team resting on their laurels, but it was very noticeable for such a big name to be highlighting titles now a full generation behind that being discussed elsewhere at the conference.

Mutual Engagement

These two examples demonstrate the extreme ends of a full spectrum of AI which is starting to come to the fore, and AI research being taken increasingly seriously. It was recently asserted at the IEEE AI/Games Networking Event held at Imperial College in June 2009 that 90% or more of AI in games comes down to A*. I think it would also be fair to say that a significant portion of the remaining 10% are recent games starting to take advantage of proven AI technologies.

In general there is an increasing amount of interest and engagement between academia and industry. A few examples of this growing trend are the fact that Introversion's Defcon now includes an AI API to allow development of external bots, 2K Australia's healthy sponsorship of the annual "BotPrize" competition, and Eidos allowing data about XBox Live gamers playstyle to be recorded in Tombraider Underworld to enable player modelling. However it isn't just this industrial encouragement of AI as a side-project undertaken solely by academics and merely facilitated by contributions from industry that gives me hope for the future, it's something that seems pervasive right now, and its evident in all the articles you can read right here on AiGameDev.com.

It's palpable how much more complex things are becoming as AAA titles start to implement more modern approaches to AI — perhaps finally this is the shift towards fulfilment of the Physics and AI Game Developers' often heard cries that surely this time, graphics have been pushed far enough and emphasis can be placed on other areas? Certainly, its true that the era of games having a single AI developer (if that) with a rudimentary understanding of a couple of algorithms from the 70's or 80's is over, and we are now all starting to talk the same language of architectures, models, evolution and a whole host of other modern techniques — and I for one welcome our new NPC overlords!

References

Player Modeling using Self-Organization in Tomb Raider: Underworld
Drachen, A., Canossa, A. & Yannakakis, G. N., CIG 2009.
Download PDF

Learning a Context-Aware Weapon Selection Policy for Unreal Tournament III
Galli, L., Loiacono, D., & Lanzi, P. L., CIG 2009.
Download PDF

Evolving Content in the Galactic Arms Race Video Gam
Hastings, E. J., Guha, R. K., & Stanley, K. O., CIG 2009.
Download PDF

Iterated Prisoner’s Dilemma for Species
Hingston, P., CIG 2009.
Download PDF

A Game-Building Environment for Research in Collaborative Design
Tanimoto, S. L., Robison, T. & Fan, S. B., CIG 2009.
Download PDF

Realtime Execution of Automated Plans using Evolutionary Robotics
Thompson, T. & Levine, J. CIG 2009.
Download PDF