This week, the Game Developers Conference (GDC) 2012 is taking place in San Francisco, and we're proud to announce that the AiGameDev.com Squad is covering the event live and interactively. Read on for details and highlights from the first few days!

Photo 1: The AiGameDev.com Squad, from left to right Jose, Alex, Phil and Guilherme.

AI Summit Highlights

Here are some moments from Monday that stand out. (Not all sessions have been included here, more will follow.)

• Daniel Brewer showed how simple coordination techniques can help provide enemy barks and responses that are unique and diverse during combat. He also showed how The Darkness 2 uses reciprocal velocity obstacles to resolve low-level collision issues, among many other interesting combat technique implementations.
• Michael Dawe showed some entertaining examples of how the work of AI programmers can often be abused by designers, in particular boss-specific Lua script hacks that are then later expected to work generally for all characters. Or taking 22ms to spawn and unspawn chicken on a regular basis.
• Kevin Dill showed how you can build modular decisions for your AI by creating considerations that you can plug together easily, each based on a combination of rank and weight. Both these floating point numbers are used in a utility-based fashion to pick the most sensible behavior applicable at any time.
• Guild Wars 2 faced some very interesting challenges to provide AI on such a large scale, but they were mostly system and architectural rather than AI-related. Mike Lewis described a pragmatic solution based on assigning specific cores to simulate games/worlds as a single thread of game logic, with underlying infrastructure helping make everything simple and thread safe.
• In his rant, Brian Schwab lamented the situation why designers seemed to fear and mis-understand AI programmers and that we should all work together — especially with the coming invasion of the cyborg robots.
• Neil Kirby explained stories from the testing department trenches, and how developers can make the most of them to produce robust and high-quality AI code.

This page will be updated as more details are compiled from the second day of the AI Summit, currently underway.

Live Coverage

1. Forum Coverage — Visit this thread for detailed reports from interesting presentations.
2. Twitter Stream — If you're on social media, follow the new company account at @AiGameDev, and consider becoming a fan on Facebook too!
3. Meetup Opportunity — If you are attending GDC and would like to meet up contact us on twitter or by email via <team at AiGameDev.com> if you'd like to share ideas!

In related news, Monday morning was the big day of our "Believable Tactics for Squad AI" presentation at the AI Summit. Thanks to everyone who attended and it's been a pleasure to hear such great feedback. We'll be making the an extended edition / directors cut available at some stage, so stay tuned for details.

Photo 2: Post-presentation question mob keen to pick the brain of Alex, Matthew and Phil.

As the games industry struggles with designing increasingly complex systems and mechanics, AI is proving to be a great tool for handling this complexity. In particular, there's an increasing number of researchers and companies looking into using AI as a tool for assisting game design and consequently reduce time taken fine tuning the particular properties of game elements.

In this interview with Paul Tozour we will take a look at his current kickstarter project City Conquest, a tower defense game that breaks off the usual pattern by including an offensive part as well. Yet what we will be covering over this interview won't be the novel mechanics or features but instead we will take a look at the evolutionary process Paul used to tune up the difficult parameters that keep the game balanced.

The Big Picture

Q: Did you find it necessary to try to express 'player fun' or 'player experience' into your fitness function? Is that even possible to achieve in practice?

For the first 16 years that I worked in the industry, I thought machine learning in games was pointless. I used to love to say "There’s no fitness function for fun." Whenever a conversation turned to machine learning techniques like neural nets or genetic algorithms, I’d just say "There’s no fitness function for fun" and argue that that makes machine learning useless for games, and that would be the end of it.

A Shield Generator.

And if you take it at face value, it's absolutely correct! I mean, imagine that you had a computer program that could actually tell you how much “fun” any given part of a game was. How could a program like that even work? How could it know that a certain part of your game is too repetitive? How could it know that fighting the Swamp Boss is more fun than the Lava Boss, that level 5 isn’t engaging because it has too much traversal, that the Plasma Gun isn’t fun to use while the Lightning Blaster is a thrill?

Writing a program like that would be like solving the Turing Test, only harder. You’d have to be able to fully model the player’s perception of the game and their interaction with it and accurately model all of the thousands of little reward centers buried in the human brain to know what actually makes a human player happy, and why we get such a bizarre thrill from making plumbers jump and clicking on cows.

So of course, that's impossible.

And saying “there’s no fitness function for fun” is actually more than correct – it’s also useful! Particularly in game AI development, people who are new to the industry sometimes come in with wildly unrealistic expectations for what machine learning can do and where it’s appropriate to use it. If they come from an academic background, sometimes they seem to think it’s “wrong” to solve game AI problems by hand, and they look for a magic wand they can wave to create the whole AI at once.

You have to push back against that mindset and shatter those illusions, and remind such developers that sometimes you can use machine learning to make a good AI system better, but it’s a terrible tool for trying to make a good AI in the first place.

And for a long time, I was satisfied with that answer.

But I eventually came around to the realization that while it’s correct, it's also irrelevant!

And I had a huge change in perspective. I came to the realization that machine learning isn’t a tool for game AI – it’s a tool for game design.

You may not be able to write a fitness function to put an exact number on entertainment value, but if you can state your design goals clearly, then you can very often write a fitness function that measures whether some part of your game satisfies them.

And then it's about selecting the right design goals in the first place to create the kind of entertainment experience you’re looking for, and determining which of those design goals are appropriate targets for any kind of AI-assisted tuning.

For example, with City Conquest, I had a specific tactical role in mind for every offensive and defensive building, and a lot of ideas as to what I expected would constitute effective offensive and defensive strategies. But I also had specific design goals for how the buildings should work together:

• Uniqueness: Each of the nine defensive buildings (towers) and offensive buildings (dropship pads for units) should be distinct from all the others
• Minimum bound on utility: No building type should be "underpowered" – every building should be important, and it should have some clear tactical role, and there should always be some scenario in which that building is the most important to winning.
• Maximum bound on utility: No building type should be "overpowered" – in other words, no single building type, or combination of a limited number of building types, should allow the player to win the game against a non-reactive opponent.
• Cost equivalence: Every building in the game should have a resource cost equivalent to its actual utility in the game.
• Combined arms: Combinations of several different building types should be far more effective than building only a small number of building types (both offensively and defensively).
• Reactivity: The optimal strategy for each player should depend significantly on the other player's strategy.

» Click here to view this embedded content.

Q: Do you feel that machine learning algorithms have been unfairly prejudiced against in the game industry?

The Disruptor tower.

Not necessarily. There’s a bias, but it’s not completely unjustified.

Some forms of ML (neural networks) are genuinely useless; many of them (genetic algorithms) are much too slow to be used at runtime; the results aren’t predictable; and as I mentioned, newcomers to the industry are sometimes very unrealistic about its potential and give it a bad reputation. There’s nothing worse than an AI developer who wants to wave the magic wand of “machine learning” instead of writing code.

But I’m not doing this because I’m any kind of ivory-tower academic or a starry-eyed idealist. I’m an industry veteran; I worked on two Metroid Prime games and was employee #3 at Gas Powered Games. I’m doing it because it works, and because I’m a capitalist and I believe in raising quality and lowering costs.

Q: What led you to use computational intelligence for game balancing?

I got tired of designing AI, and I realized it was time to “AI” design.

Here’s a thought experiment:

How are people going to design games 100 years from now?

Never mind that we have no idea what games themselves will look like that far into the future. A “game” probably won’t look anything like it does today. Maybe they’ll be holodecks or something. But it doesn’t matter.

In the year 2112, how will game designers get their jobs done?

What kind of tools are they going to use?

I don’t know the answer, but there’s no question it’s not going to look like what we have today. Game design is still in its infancy – or maybe its messy and chaotic pre-teen years.

A century from now, what it means to be a “game designer” will have evolved beyond recognition. We won’t have designers giving hand-wavy answers to basic design questions, making sweeping design changes without understanding the side-effects, or spending inordinate amounts of their team’s time (and their company’s resources) exploring the design space in the name of “iteration”.

At a minimum, we’ll have a shared design language across the industry, a shared understanding of what constitutes “good design”, and vastly more powerful design tools.

Imagine that you wanted to build a bridge. You’d need to hire a licensed structural engineer, wouldn’t you? That engineer would have to have earned a civil engineering degree with 3-5 years of study under their belt, and then satisfy a host of requirements to become certified to build bridges.

And that happens because everybody understands that bridges can fail, and earthquakes and wind and traffic accidents can topple them if they’re not designed correctly, and things like that can kill people and destroy the bridges. So you have to spend a lot of time studying to understand how to build a bridge the right way.

Everybody appreciates all of that, so everybody accepts that certifying civil engineers is the right thing to do to make sure they build good bridges.

But there’s nothing like that for games.

We consistently hire people who are enthusiastic rather than people who are genuinely qualified – we prefer charismatic designers who can talk the talk over cautious practitioners who can walk the walk. We take million-dollar projects and put them in the hands of people with no adequate design training, and then we fail to train them further or build a shared design vision between them. We let them endlessly throw ideas against the wall to see what sticks, and then we wonder why we end up with burned-out teams, failed projects, and studio failures out the other end.

The Ground Slammer.

And mostly that happens because we don’t talk about what happens when designers fail. We hide the devastating consequences of design failure. When a bridge collapses somewhere, it’s too big to hide and the whole world knows about it … but in the game industry, a design collapse is painful and embarrassing and we have the luxury of hiding it in our own studios.

And that has to stop. It’s just too expensive and too risky to keep doing design that way. Design has become the bottleneck.

So we need two things to happen.

First, game design needs to grow into a real discipline. I’m not saying we need actual certification like you have in civil engineering (though that might not be a bad idea), but the discipline of game design needs get out of its infancy (or chaotic pre-teen years) in a hurry.

And secondly, we need vastly better tools.

If you were to go back in time 30 years and asked designers what tools they’d like to see in the future, they would have described some amazing tools for building levels and doing scripting in three entire dimensions. And now those tools exist! We have engines like Unity and Unreal and Gamebryo that are everything a designer in 1981 would have asked for and more.

But these aren’t the only tools we need. Unity and Unreal can’t give you any insights on your game design. They can help you build your game, but they can’t tell you anything at all about the design decisions you make.

There’s so much more that can exist, and that will have to exist someday. It’s just that we don’t see that, because those tools haven’t been built yet – so we don’t realize they should exist, and we don’t realize they’re missing!

We have game “engines,” but we don’t realize that the rest of the car is missing.

Again, I used to think machine learning techniques were useless. But I got to a point where I stopped thinking of machine learning as a game AI tool and started thinking of it as a design tool, and that changed everything.

Take Wall Street as an example. There used to be a time when the New York Stock Exchange was full of traders yelling and making complicated hand gestures to each other to buy and sell shares. It only took a decade for all those pits to be abandoned and replaced with computers. Since then it’s been an ongoing arms race of ever faster servers and ever tighter connections and lower latency for high-frequency trading within microseconds. And it will never go back to the old days.

Or I could compare it to baseball recruiting. Baseball recruiting used to be a very subjective process. It was ten managers sitting in a room arguing about who to recruit to fix a broken baseball team, without really understanding what they should be looking for and no clear idea how to properly evaluate the factors that make a baseball team work. “We can’t hire that guy – he has an ugly girlfriend; that means no self-confidence!”

And in the book and movie Moneyball, you see how Billy Beane (played by Brad Pitt) hired an economics PhD from Yale and put together a statistical modeling approach that ultimately drove the Oakland Athletics to a staggering string of victories and changed baseball recruiting into a quantitative discipline. And it will never go back to the old days.

Game design right now is like the NYSE before computers, or baseball recruiting before Billy Beane.

And it will change, so we might as well embrace it. Moore’s Law is still in effect, and we have a massive amount of computing power at our disposal in cloud computing clusters.

Every day, computing power becomes a little bit cheaper and game designers become a little bit more expensive.

We’ve finally arrived at the point where we can actually run the millions of gameplay simulations we need to run to do GAs effectively and get those insights back into the hands of designers in a few hours or days, and it’s inevitable that that will transform the design process.

Q: So can we get to a point where we replace designers once and for all? :-)

The Lightning Tower.

My hope is that the future will bring much more powerful tools to bear on game design problems. We’ll have all the powerful game engines we have today, but we’ll also have the equivalent of a GPS and navigation system for game designers to guide them toward the decisions that satisfy their design goals.

And that will also raise the bar for what a game designer is expected to do to work effectively. So the best designers will have more powerful tools that help them design better games, faster … and the pretenders will find themselves out of their league and will probably have to find new jobs.

Both of those are good things.

Q: Currently you're using AI as a tool to assist the design process. Do you think it's possible to use genetic algorithms to optimize the game's parameters rather than just finding the dominant strategy?

Definitely. My approach is just one particular way of using GAs for one particular kind of balancing problem. It’s only a starting point; it’s not the only approach and it’s not necessarily the best one.

Phillipa Avery and Julian Togelius wrote a really neat paper (with Alistar and van Leeuwen) on using GAs to tune parameters for a more traditional tower defense game, where they evolved the parameters for their creeps and towers directly.

Alex Jaffe of UW also has a really terrific paper coming out on this topic (along with several co-authors). I’ve gotten a sneak preview but I’m sworn to secrecy.

There’s one company I know of with a broadly similar overall concept – the +7 Balance Engine. But their approach is very different. Their webpage says that they want to ensure that there are no dominant strategies.

I don’t think that’s a valid approach. You have to empower designers, and let them decide whether there should be any dominant strategies. Maybe they do want one dominant strategy! You can’t take someone else’s game and say “Here, let me balance that for you” because you can’t know what they mean by “balance.” You can’t anticipate all of their design goals in advance.

It’s about giving valuable feedback to the designers so they can ensure that their gameplay meets their design goals.

The big-picture goal is to build systems that dramatically expand designers’ visibility over the dynamics of the gameplay they create. We’d like to build systems that shine a floodlight on the fitness landscape and which player strategies emerge from every design decision.

And we want to be able to give them visibility on how any design change they could make will affect those dynamics, so designers can ask questions like, “what happens if I tune this parameter here – how does that change the set of viable player strategies?” Or alternatively, “What would I need to change in my parameters to make strategy X more (or less) desirable?”

Behind The Scenes

Q: How would you rate the importance of the underlying evolutionary algorithm compared to the overall infrastructure/process? How long did it take to implement this part of the code?

It’s been ~10% of my total engineering time. There were 3-4 days of dedicated coding to create Evolver in September – we had to split Evolver into a separate build, disable the renderer, increase the time step in the update loop, optimize the gameplay code, and then make it parallel using Microsoft’s PPL library. That got us to a point where we can run several million entire games overnight.

Since October, it’s only been 30-90 minutes a day of tuning. We have a dedicated Dell desktop PC running Evolver 24/7. Every day or two, we terminate the Evolverand extract the two best players by fitness score (one each from the red and blue player populations). Then we plug them into the game, play them back, and watch how they play each other and decide how to tune it based on that gameplay session. Then we make the code changes and run it again, and only occasionally dig deeper and make tweaks to Evolver itself.

The Grenade Launcher.

So that’s very handy. It’s like having a virtual playtesting team that works for free. It cost me a few days of development, but when I compare that to the salary I’d have to pay somebody to do that full-time, it’s a no-brainer.

Of course, it’s not a magic bullet. You still have to do manual playtesting, and it’s still a good idea to plug your parameters into Excel every now and then and fit them to a curve with Solver. But those are now small, secondary tasks, not the core of the balancing process itself.

So once I get Evolver’s output, I can plug it back into my game and watch the red and blue players duke it out. If I see a pattern where both players are over-using certain buildings or upgrades or combinations of buildings, then I probably need to “nerf” those features somehow – either I need to make them weaker, or I need to increase the resource cost to buy them in the first place.

Similarly, if there are certain buildings or upgrades that they never buy at all, I need to stop and ask myself why. Are they too expensive? Are they not useful enough? Or is there something else going on? Why is the Evolver not finding it useful enough to survive evolution? So I’ll increase its utility or decrease its cost to compensate.

And finally, I look at the context in which everything is being used and see if it matches my design goals for each unit. Sometimes I find the Evolver adapts the strategies I expected it to; other times, it surprises me, and I have to figure out whether I should tune the game to stop it from happening, or embrace it as an unexpected new strategy.

Some of the AI researchers I've been speaking with have raised the issue that my approach can really only identify one dominant strategy at a time. For example, you might have two strategies, A and B, that are both dominant, and with the way I’m doing it, the computer can only identify one of those dominant strategies.

And that's true, but you have to keep in mind that tuning is an ongoing process – it's not something you do in a single pass! I'm running the Evolver continuously and re-tuning every day or two based on its output. So if it only happens to find that A is the dominant strategy today, that’s fine, because it means I’m going to respond to that, and A will get nerfed so that B has a much greater chance to stick out like a sore thumb the next time I run it.

Q: Can you give us some examples of interesting results Evolver has given you?

This is more of a bug than a balancing issue, but I had a really interesting phenomenon on October 30 where the best red player script was always winning the game by a huge margin. And looking through the evolved script, it didn’t seem to be doing anything really unusual; the only unusual thing I could see was that it was building a Laser tower at a particular spot fairly early in the game.

Now, the Laser tower is a very unusual building in City Conquest. It’s the only defensive tower that doesn’t have a range limit – it can fire all the way across the map. It was designed to do a very small amount of damage to a very large number of units. The trick is to set it up the right way to ensure that it hits as much of the enemy army as possible.

So when I started playing back the scripts in the game, I was floored – the red player’s Laser was positioned in just the right spot where it could target the blue player’s Collectors from all the way across the map! It took 8-9 shots to take them out, but once it did, the blue player’s Collectors were destroyed with no way to rebuild them, so it would be starved of resources and it would lose every time.

Again, it’s more of a bug than a feature – Collectors were supposed to be invulnerable, and Lasers shouldn’t even be able to target them anyway, but invulnerability and targeting tweaks hadn’t been implemented yet and were scheduled for a later date. But it goes to show you how computational intelligence can find a path through the design space that a human designer might never even imagine.

A Laser attacking the blue player’s Collectors. The red player’s Laser is firing from offscreen to the upper-left.

Here’s a different example that shows some really good behaviors that I think closely mirror what a smart City Conquest player would do. These are two screenshots from a recent run that I discussed in Update 4 of my Kickstarter campaign. Again, keep in mind that everything you see in these screenshots (excluding the pyramid-shaped Mining Facilities on the crystals) was evolved entirely by the computer.

Here’s the blue player’s base:

There are five really interesting things going on with this base:

• Single point of entry in the back of the base: The blue player forces all the enemy units to funnel around to a single attack point at the rear of its Capitol. This is the best possible positioning for the attack point, because it forces enemy units to go all the way around before they can attack, and it gives the blue player many more opportunities to defeat them.
• Dividers to separate enemy forces: The blue player divides and conquers the red player's forces, splitting them between a northern and a southern route around his city. Since one route is longer than the other, enemy units will arrive at different times, and this makes them much easier to deal with as they will reach the Capitol at different times.
• A well-placed Disruptor (the floating sphere with yellow stripes) near the top entrance allows him to interrupt the red army's cloaking, shielding, and healing effects at exactly the right time, just as they're beginning to get truly pounded by the blue player's defenses.
• A fully-upgraded Shield Generator unit toward the upper left (the dropship pad with three aqua-colored lights) allows the blue player to protect nearby units from damage.
• A set of 3 Lightning Towers cleverly dispersed at the front, side, and rear of the blue player's base, ensuring that these expensive buildings rarely waste time targeting the same units simultaneously.

Here’s a screenshot of the red player’s base. Notice how it employs many of the same intelligent strategies as the blue player, which are exactly the behaviors I intended to be good strategies in City Conquest.

• Single point of entry: Like the blue player, the red player forces the opposing army to attack at the rear of his Capitol. The design of the base forces blue’s units around to the north, above the Mining Facilities, and then back through the rear entrance on the left side of the image.
• Dividers to separate enemy forces: Like the blue player, the red player splits the opposing army into two different paths (east and west paths at the front of his base) to upset their arrival timing.
• A perfectly-placed Disruptor (the floating sphere with yellow stripes above the Capitol) allows the red player to interrupt cloaking, shielding, and healing effects all along the front and side of its base (all along the north edge five Mining Facilities you see), as well as when enemy units circle around to the rear and finally close in on the Capitol.
• A Lightning Tower at just the right spot (black spiral just above and to the right of the Capitol) gives excellent coverage, allowing the red player to zap enemy units at the front, side, and rear of its base. This placement ensures that this relatively expensive tower will see as much utilization as possible.
• A pair of Ground Slammers, one at the front of the red player's base and another at the rear (shaped like tall pillars wearing metallic thumpers), allow the red player to create earthquakes and give area-effect damage to all ground-based units that pass by.
• A pair of Grenade Tossers (deep holes in the ground on the left and right sides) is also nicely distributed in a very similar way, with an upgraded Grenade Tosser in the front and another non-upgraded Grenade Tosser in the rear. These allow the red player to hit all ground units in a wide area with a moderate amount of area-effect damage -- enough to weaken them considerably and allow the other towers to take them out.

Q: What type of evolutionary approach and individual representation did you use? Simply put, what did you evolve?

In this particular case, we’re just trying to evolve highly competent players to see what strategies good players use. We essentially evolve scripts of build orders.

City Defense is a tower defense variant, so it only has three player verbs: “build,” “upgrade,” and “sell” (I’m excluding the verbs for “game effects,” which are more like spells that players can cast). Also, selling buildings is usually a bad idea since you can’t get a full refund, so there’s no reason for Evolver to do it.

So an Evolver player script just boils down to a sequence of build and upgrade commands – build a building of type T at (X,Y), or upgrade the building at position (X,Y). There are no timing values associated with the commands; Evolver will ensure that each player executes a command as soon as it can afford to do so.

Also, since every building in City Conquest has a resource cost in terms of gold or crystals, but not both, it effectively processes the build order as two separate lists in parallel, one for each resource.

We start by generating 500 random build scripts for each of the red and blue players. Then we run four tournaments, each one pitting all 500 red player scripts against all 500 blue player scripts, using a random offset so that we’re pitting each blue player script against a different red player script in every tournament.

It’s probably easiest just to show you the C++ pseudo-code:

static int const skNumTournaments = 4;
static int const skPopulationSize = 500;

// Run 4 tournaments which pit all 500 blue scripts and all 500 red scripts 
// against each other
for ( int tournament_iterator = 0; tournament_iterator < skNumTournaments; 
++tournament_iterator )
{
    int random_offset = rand() % skPopulationSize;

    for ( int i = 0; i < skPopulationSize; ++i )
    {
        // This ensures that ALL members of BOTH populations will play a game
        Script & blue = blue_player_scripts» Click here to view this embedded content.;
        Script & red = 
            red_player_scripts» Click here to view this embedded content.;

        // Now play a full game, and adjust the scores for “blue” and “red” 
        // as appropriate
        RunSimulation( blue, red );
    }
}

We do 4 tournaments of 500 games each (pitting each red player script against a random blue player script) to make sure we get good coverage and reasonably accurate fitness values at the end of each tournament. Once the tournament is completed, we sort the scripts for each player by their fitness score, and apply standard genetic operators – random replacement of the lowest-scoring scripts (falling off linearly to a fixed minimum value over the first few hundred tournaments); random mutation of each script; and performing “crossover” to combine two scripts (biased toward crossover with higher-scoring scripts rather than lower-scoring ones).

A “mutation” has a random chance to change a building’s type, change a command’s location, swap the ordering of two commands in the script, or copy a command on top of an existing command.

We also added additional safeguards to ensure that scripts would stay flexible. For example, if Evolver tries to execute a build command and there’s already a building there, in most cases it will sell the existing building to allow it to build the new one and continue executing the script.

Of course, this is a relatively simple application, and it’s made easier by the fact that City Conquest lends itself to this as a TD game. Not every game can get away with a non-reactive build script like this. Most games are more complicated, and you need an entire AI system to get a reasonable simulation of a player.

For our next project, we’re planning to evolve entire behavior trees to allow us to generate more complex reactive behaviors rather than just a fixed build order. We’re also planning to move the Evolver into a cloud computing cluster and separate the populations out using an “evolution islands” approach with metadata.

Q: How do you determine the fitness of an individual? Evolutionary algorithms are often very sensitive to the definition of the fitness function.

Yes, they are. It depends on the particular game and what you’re trying to evolve.

In City Conquest, it’s back-and-forth tower defense gameplay, and the Capitol is the only attackable building. The game ends when one player’s Capitol gets to zero health. So the ratio of the health of the two Capitols is actually a VERY good indicator of who's winning. And when the game ends, the health of the winning player’s Capitol tells you a lot about how close a game it was. In an evenly-matched game, both players will do a lot of damage to each other’s Capitols; in an uneven game, the winner will destroy the opposing player’s Capitol without allowing much damage to his own.

Each script has a fitness score associated with it. After each game, Evolver takes the health of the winning player’s Capitol and adds that to the score of the winning player script and subtracts it from the score of the losing player script. This ensures that the greater the victory, the greater the effect on both scripts’ fitness scores.

When I started development on Evolver, I discussed my plans with a number of the top researchers in AI-based design and automated game balancing – Phillipa Avery of the University of Nevada – Reno, Gillian Smith and Adam Smith of UCSC, Alex Jaffe of UW, and a few others.

A few of them suggested that I set up “archetype” scripts using standardized “known” player strategies to ensure that I’d evolve against a broad set of possible human strategies. I recorded my own gameplay as I executed half a dozen standard strategies, and then for a few weeks I tried using Evolver to test against all six of those archetype scripts.

But I found that as I rebalanced my game every day based on the feedback from Evolver, it would invalidate all of those “archetype” scripts. I couldn’t commit to re-recording all those scripts every week or two as my balancing changed, so I had to abandon that approach.

Later in the development cycle, I also tried adding additional fitness qualifiers to encourage the evolved scripts to do more of what I felt a human player should do. Some of these didn’t work out, but one that did was adding a fudge factor to the fitness function for building and upgrading Skyscrapers. This is critical to success in City Conquest, since Skyscrapers expand your buildable territory, and upgrading them not only consolidates your hold over your territory but also gives you additional resources over time. But it’s the type of thing that isn’t necessarily immediately rewarded in a fitness function, because an evolved script won’t immediately capitalize on the additional territory and additional resources right when the Skyscraper is first added.

The Skyscraper fitness adjustment helps compensate for the natural delay between building and upgrading a Skyscraper and then evolving everything else you need to actually reap the benefits from it. This is purely a way of telling Evolver, “trust me, you want to be doing this, and we don’t want to wait for evolution to prove it every time.”

Final Thoughts

Q: What advice would you give to other developers thinking about using machine learning algorithms in their games?

I was the founder of my startup, so I already had the buy-in I needed from the upper management to run the experiment. And I undeniably realized major benefits from it.

But I can’t imagine trying to push something like this at any of the studios I’ve ever worked at.

Machine learning will take time to prove itself. It’s not going to happen overnight. The (often justified) skepticism toward machine learning in the industry makes it a tough sell to launch this kind of initiative internally. It’s probably going to have to enter from the outside, disruptively, rather than from inside studios that would offer enormous cultural resistance.

I’m reminded of when I worked on Thief: Deadly Shadows and Deus Ex: Invisible War at Ion Storm Austin. I had to fight tooth and nail to gain acceptance for the use of navigation meshes for pathfinding. I think almost every single programmer and designer in the studio argued against it at one point or another. Some of them treated me like I was crazy; others treated me like I had to be some kind of pointy-haired academic who ought to be off in a research lab somewhere if he cared so damned much about obscure academic issues like good pathfinding.

And now, they’re very common. I can make a list as long as my arm of successful AAA products that used navigation meshes.

But at the time, it was open warfare, and it was very difficult to make the case for something that seemed to me blindingly obvious.

It will be the same for machine learning and AI-based game design for some time to come.

So my advice is to make sure you have buy-in. Don’t put yourself through the pain if you can’t get full support and commitment at every level. Otherwise, you’re just painting a target on your back.

And if you can’t get it, and you see the possibilities, consider quitting your job. Launch a startup, or join mine!

If you liked this interview don't forget to take a look and back this interesting project at City Conquest Kickstarter Project!

This article was written by Daniel Harabor, Ph.D. researcher at the NICTA and The Australian National University, specializing in pathfinding and game AI. You can contact him by email at <daniel.harabor at nicta.com.au >

In this article I attempt to explain path symmetry: a property of uniform-cost grid maps and other regular search domains which can significantly slow down pathfinding. I describe how symmetry manifests itself and briefly discuss some approaches that other people have tried to improve things. Finally, I introduce two recent ideas from my doctoral research: Rectangular Symmetry Reduction (RSR) and Jump Point Search (JPS). Both are optimality-preserving techniques that explicitly identify and eliminate symmetry in order to speed up pathfinding by an order of magnitude and more. I discuss their strengths, weaknesses and observed performance on two popular video-game benchmarks kindly made available by Nathan Sturtevant and BioWare: Baldur's Gate II and Dragon Age: Origins.

Acknowledgements:

I would like to give due credit to my amazing collaborators without whom I could not have come so far nor achieved so much. I would also like to thank the generous academic institutions that have supported this work. In particular:

• The RSR algorithm was developed in conjunction with Adi Botea and Philip Kilby. It first appeared in the 2011 proceedings of the Syposium on Abstraction, Reformulation and Approximation (SARA).
• JPS was developed in conjunction with Alban Grastien and first appeared in the 2011 proceedings of the National Conference of the Association for the Advancement of Artificial Intelligence (AAAI).
• All authors are affiliated with NICTA and the Australian National University.
• NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.

Electronic copies of the academic papers mentioned here are available from my homepage.

1. Path Symmetries

Often appearing as a pathfinding domain in areas such as robotics and video games, grid maps are a simple yet popular method for representing an environment. As it turns out, grids are also academically interesting for the following reason: between any given pair of locations, there usually exists many possible paths. Sometimes these paths represent alternative ways of reaching one location from the other but more often they are symmetric in the sense that the only difference between them is the order in which moves appear.

Figure 1: Symmetry A simple grid-based pathfinding problem. For simplicity (but not in general) we allow only straight moves and not diagonal. Many optimal length paths could be returned as the solution; we highlight only a few. Notice that each one is a permutation of all the others. In such cases we say that a symmetry exists between the paths.

Before proceeding further it is necessary to establish some precise terminology. For example: what exactly is a path? Traditionally, Computer Scientists define paths as ordered sequences of connected edges. The conjunction of these edges represents a walk in the search graph from some arbitrary start location to some arbitrary goal location. However this definition is too general to capture the idea of symmetry in grid maps. For that, we need a slightly different notion of a path:

A path in a grid map is an ordered sequence of vectors, where each vector represents a single step from one node on the grid to an adjacent neighbouring node.

The distinction between edges and vectors is an important one as it allows us to distinguish between paths that are merely equivalent (i.e. of the same length) and those which are symmetric. But what, exactly, does it mean to have a symmetric relationship between paths?

Two grid paths are symmetric if they share the same start and end point and one can be derived from the other by swapping the order of the constituent vectors.

As a clarifying example, consider the problem instance in Figure 1. Each highlighted path is symmetric to the others since they all have the same length and they all involve some permutation of 9 steps up and 9 steps right.

In the presence of symmetry a search algorithm such as A* is forced to explore virtually every location along each optimal path. In Figure 1, depending on how we break ties, A* might expand every node on the entire map before reaching the goal. Further, A* will usually consider many other nodes that appear promising but that are not on any optimal path. For example, each time A* expands a node from the fringe of the search, it has already likely found almost every symmetric shortest path leading to that node (again, depending on how we break ties when two nodes appear equally good). But this effort is in vain if these expansions do not lead the search closer to the goal and instead into a dead-end. Thus arises the question which I will attempt to answer in this article: how do we deal with symmetry when pathfinding on grid maps?

1.1 Existing Methods For Speeding Up Search

A large number of techniques have been proposed to speed up pathfinding. Most can be classified as variations on three themes:

1. Reducing the size of the search space through abstraction.

   Algorithms of this type are fast and use little memory but compute paths which are usually not optimal and must be refined via further search. Typical examples: HPA* » Click here to view this embedded content., MM-Abstraction » Click here to view this embedded content..

2. Improving the accurary of heuristic functions that guide search.

   Algorithms of this type usually pre-compute and store distances between key pairs of locations in the environment. Though fast and optimal, such methods can incur signficant memory overheads which is often undesirable. Typical examples: Landmarks » Click here to view this embedded content., True Distance Heuristics » Click here to view this embedded content..

3. Dead-end detection and other state-space pruning methods.

   Algorithms of this type usually aim to identify areas on the map that do not need to be explored in order to reach the goal optimally. Though not as fast as abstraction or memory heuristics, such methods usually have low memory requirements and can improve pathfinding performance by several factors. Typical examples: Dead-end Heuristic » Click here to view this embedded content., Swamps » Click here to view this embedded content., Portal Heuristic » Click here to view this embedded content..

1.2 Rectangular Symmetry Reduction and Jump Point Search

1. Rectangular Symmetry Reduction (RSR).

   RSR » Click here to view this embedded content.» Click here to view this embedded content. can be described as a pre-processing algorithm which identifies symmetries by decomposing the grid map into empty rectangular regions. The central idea, then, is to avoid symmetries by only ever expanding nodes from the perimeter of each rectangle and never from the interior.

2. Jump Point Search (JPS).

   JPS » Click here to view this embedded content. consists of two simple neighbour pruning rules that are applied recursively during search. Each rule considers the direction of travel to a given node from its parent (either a straight step or a diagonal step) in order to prune the set of local neighbours (tiles) around that node. The central idea is to avoid any neighbours that could be reached optimally from the parent of any given node. In this way we are able to identify and avoid, on-the-fly, large sets of symmetric path segments; such as those in Figure 1.

(a) A*

(b) A* + RSR

(c) A* + JPS

Figure 2: Search Effort. All nodes marked red must be expanded before the optimal path to the goal (marked in blue) is found. Notice that, in the case of A*, many nodes on the fringe of the search (i.e. on the edge of the red area) can only be reached by paths that cross large regions of empty space. These paths usually have many symmetric alternatives and considering them all can require a substantial number of node expansion operations. RSR and JPS can detect and eliminate such symmetries and both reach the goal much sooner.

2. Rectangular Symmetry Reduction

(This remainder of this section, and the next, give a mechanical overview of the algorithm and its properties. If you're impatient, or don't care about such things, you can skip ahead and check out some screenshots.)

RSR can be described in 3 simple steps. Steps 1 and 2 are applied offline; their objective is to identify and prune symmetry from the original grid map. The third step is an online node insertion procedure; its objective is to preserve optimality when searching for paths in the symmetry-reduced grid map.

RSR Step 1: Grid Decomposition

Decompose the grid map into a set of obstacle-free rectangles. The size of the rectangles can vary across a map, depending on the placement of the obstacles. Once the decomposition is complete, prune all nodes from the interior, but not the perimeter, of each empty rectangle.

RSR Step 2: Addition of Macro Edges

Add a series of macro edges that connect each node on the perimeter of a rectangle with other nodes from the perimeter. In a 4-connected map (shown here for simplicity) a single macro edge between nodes on opposite sides of each rectangle will suffice. If diagonal moves are allowed, a set of macro edges (as described in » Click here to view this embedded content.) will be needed instead.

RSR Step 3: Online Insertion

When the start or goal is located in the interior of an empty rectangle, we use a temporary node re-insertion procedure. In a 4-connected map (shown here for simplicity) we connect the temporary node, online, to the 4 nearest perimeter nodes. A similar operation, involving sets of edges from each perimeter side, is used when diagonal moves are allowed.

2.1 Properties and Performance

1. It preserves optimality.
2. It has a small memory overhead in practice.
3. Node insertion (Step 3) can be performed in constant time.
4. It can speed up A* search by anywhere from several factors to an order of magnitude.

Memory Requirements:
In the most straightforward implement of RSR we need to store the id of the parent rectangle for each of the n traversable nodes in the original grid. We also need to store the origin and dimensions of each rectangle (macro edges can be identified on-the-fly and do not need to be stored explicitly). This means that, in the worst case, we might need to store up to 5n integers. In practice however we can usually do much better. For example: there is little benefit in storing or assigning nodes to rectangles with few or no interior nodes (1x1, 2x1, 2x2, 3x2, 3x3 etc.). We can also avoid the parent id overhead altogether and only store the set of identified rectangles. The only downside is that, during insertion (Step 3 above), we now need to search for the parent rectangle of the start and goal -- instead of being able to identify it in constant time.

Performance:
We evaluated RSR on a number of benchmark grid map sets taken from Nathan Sturtevant's freely available pathfinding library, Hierarchical Open Graph. One of the map sets is from the game Baldur's Gate II: Shadows of Amn. The other two map sets (Rooms and Adaptive Depth) are both synthetic, though the latter could be described as semi-realistic. I will give only a summary of our findings; full results and discussion is available in the following papers: » Click here to view this embedded content. » Click here to view this embedded content..

In short: we observed that in most cases RSR can consistently speed up A* search by a factor of between 2-3 times (Baldur's Gate), 2-5 times (Adaptive Depth) and 5-9 times (Rooms). In some cases the gain can be much higher: up to 30 times.

We found that the extent of the speed gains will be dependent on the topography of the underlying grid map. On maps that feature large open areas or which can be naturally decomposed into rectangular regions, RSR is highly effective. When these conditions do not exist, the observed speed gains are more modest. This performance is competitive with, and often better than, Swamps » Click here to view this embedded content.; another state-of-the-art search space reduction technique. We did not identify a clear winner (each algorithm has different strengths) but did notice that the two methods are orthogonal and could be easily combined.

2.2 Screenshots

(a) A*

(b) A*

(c) A*

(d) A* + RSR

(e) A* + RSR

(f) A* + RSR

Figure 2: Search Effort. Comparative pathfinding examples from our experimental results. Images (a) to (c) are total nodes expanded by A* in order to find the optimal path to the goal (marked blue). Images (d) to (f) are total nodes expanded by A* + RSR. The respective domains are (from left to right): Baldur's Gate, Adaptive Depth and Rooms. Notice that A* + RSR ignores many symmetric path segments and typically reaches the goal with much less effort.

3. Jump Point Search

The remainder of this section, and the next, describe the mechanical details and algorithmic properties of Jump Point Search. If you don't care for such things, feel free to jump ahead and check out some screenshots.

JPS can be described in terms of two simple pruning rules which are applied recursively during search: one rule is specific to straight steps, the other for diagonal steps. The key intuition in both cases is to prune the set of immediate neighbours around a node by trying to prove that an optimal path (symmetric or otherwise) exists from the parent of the current node to each neighbour and that path does not involve visiting the current node. Figures 1 outlines the basic idea.

Figure 1: Neighbour Pruning. Node x is currently being expanded. The arrow indicates the direction of travel from its parent, either straight or diagonal. In both cases we can immediately prune all grey neighbours as these can be reached optimally from the parent of x without ever going through node x.

Figure 2: Forced Neighbours. Node x is currently being expanded. The arrow indicates the direction of travel from its parent, either straight or diagonal. Notice that when x is adjacent to an obstacle the highlighted neighbours cannot be pruned; any alternative optimal path, from the parent of x to each of these nodes, is blocked.

The details of the recursive pruning algorithm are reasonably straightforward: to ensure optimality we need only assign an ordering to how we process natural neighbours (straight steps before diagonal). I will not attempt to outline it further here; the full details are in the paper and my aim is only to provide a flavour for the work. Figures 3 gives two examples of the pruning algorithm in action. In the first case we identify a jump point by recursing straight; in the second case we identify a jump point by recursing diagonally.

(a) Jumping Straight

(b) Jumping Diagonally

Figure 3: Jumping Examples. Node x is currently being expanded. p(x) is its parent.

(a) We recursively apply the straight pruning rule and identify y as a jump point successor of x. This node is interesting because it has a neighbour z that cannot be reached optimally except by a path that visits x then y. The intermediate nodes are never explicitly generated or even evaluated.

(b) We recursively apply the diagonal pruning rule and identify y as a jump point successor of x. Notice that before each diagonal step we first recurse straight (dashed lines). Only if both straight recursions fail to identify a jump point do we step diagonally again. Node w, which is simply a forced neighbour of x, is generated as normal.

3.1 Properties and Performance

1. It is optimal.
2. It involves no pre-processing.
3. It requires no extra-memory overheads.
4. It can consistently speed up A* search by over 10 times; making it not only competitive with, but often better than, approximate techniques such as HPA* » Click here to view this embedded content..

We evaluated JPS on four map sets taken from Nathan Sturtevant's freely available pathfinding library, Hierarchical Open Graph. Two of the benchmarks are realistic, originating from popular BioWare video games Baldur's Gate II: Shadows of Amn and Dragon Age: Origins. The other two Adaptive Depth and Rooms are synthetic though the former could be described as semi-realistic. In each case we measured the relative speedup of A* + JPS vs. A* alone.

Briefly: JPS can speed up A* by a factor of between 3-15 times (Adaptive Depth), 2-30 times (Baldur's Gate), 3-26 times (Dragon Age) and 3-16 times (Rooms). In each case the lower figure represents average performance for short pathfinding problems and the higher figure for long pathfinding problems (i.e. the longer the optimal path to be found, the more benefit is derived from applying JPS).

What makes these results even more compelling is that in 3 of the 4 benchmarks A* + JPS was able to consistently outperform the well known HPA* algorithm » Click here to view this embedded content.. This is remarkable as A* + JPS is always performing optimal search while HPA* is only performing approximate search. On the remaining benchmark, Dragon Age, we found there was very little to differentiate the performance of the two algorithms.

Caveat emptor: It is important to highlight at this stage that A* + JPS only achieves these kids of speedups because each benchmark problem set contains a large number of symmetric path segments (usually manifested in the form of large open areas on the map). In such cases JPS can exploit the symmetry and ignore large parts of the search space. In the process A* both generates and expands a much smaller number of nodes and reaches the goal much sooner. When there is very little symmetry to exploit however we expect that our gains will be more modest.

3.2 Screenshots

Baldur's Gate Benchmark Example

(a) A*

(b) A* + RSR

(c) A* + JPS

Adaptive Depth Benchmark Example

(d) A*

(e) A* + RSR

(f) A* + JPS

Rooms Benchmark Example

(g) A*

(h) A* + RSR

(i) A* + JPS

Figure 4: Search Effort. Comparative pathfinding examples from our experimental results. Images in the first column show total nodes expanded by A* in order to find the optimal path to the goal (marked blue). Images in the middle and last columns are total nodes expanded by A* + RSR and A* + JPS respectively. Notice that A* + JPS ignores many symmetric path segments (more than A* + RSR even) and typically reaches the goal with much less effort.

4. Final Thoughts

Another exciting aspect of this work is the possiblities it opens for further research. For example: could we pre-process the map and go even faster? Or: are there analogous jumping rules that one could develop for weighted grids? What about other domains? Could we apply the lessons learned thus far to help solve other interesting search problems? The answers to the first two questions already appear to be positive; the third is something I want to explore in the near future. Regardless of how it all turns out, one thing is certain: it's an exciting time to be working on pathfinding!

References

Every year AiGameDev.com runs its Awards for Game AI, shining the spotlight on the best releases of the past year. There are six different awards, ranging from technology to design and of course overall game of the year. For each, we've included the community vote results as well as the editor's choice.

This year has seen an incredible set of games that raised the bar in many places, including better integration of the AI and gameplay, overall polish of the character behaviors, and applications of artificial intelligence to other areas of games. Of course, there were some catastrophes too, but we're not going to talk about those :-)

Anyway, without further ado...

Best AI in a AAA Game

Vote Winner
Batman: Arkham City

This year's winner of the community vote is Rocksteady's sequel to their highly acclaimed debut, ARKHAM ASYLUM. The game convincingly received more votes than any of the other nominees, beating out some solid competition in RAGE, RESISTANCE 3 and THE SIMS: MEDIEVAL. Congratulations to Rocksteady for a great game and winning the 2011 AiGameDev.com Award for Game AI!

ARKHAM CITY features some of the smoothest and most fluid animations seen in any game, in particular between the player and the endless hordes of brutes in the game as well as the interactions with the environment. Such smooth movement in combat obviously require AI for the NPCs, but increasingly animation systems are scaling-up significantly and using techniques refined by game AI developers over the decades.

Nominations

• RAGE
• RESISTANCE 3
• SIMS: MEDIEVAL

Editor's Pick
Resistance 3

In a year packed with shooter releases, each with more innovations in design and technology than previous years, our editor's pick almost had to be a shooter! The one that sums up 2011 best is RESISTANCE 3 for its polished combat design, varied enemies and challenging gameplay. The game won accolades from the press for not only being the best in the series, but for being the definitive shooter on PS3.

From an AI perspective, Insomniac's work is notable for iterating over the enemies in the game — and introducing new ones — that fit best with the desired gameplay. The team put AI hand in hand with combat design (in fact the two have become inseparable this year), a solid understanding of level design principles, and a high-level AI reminiscent of RTS games and AI directors that allows the designers to shape the gameplay. RESISTANCE 3 is also one of a growing number of AAA titles using the open source Recast library for navigation. Finally, the developer & publisher emphasized AI during the promotion of the game — so bonus points for that!

Congratulations to the RESISTANCE 3 team for their hard work on the game! An honorable mention should also go to RAGE (and Id Software) for similar reasons: varied enemies, polished combat, emphasizing the AI during the promotion of the game and robust animation and navigation technology. Impressive, particularly for the first title in a new franchise on a brand new engine!

Best Non-Player Characters

Vote Winner
Portal 2

How perfectly fitting is it for an artificial intelligence to win AiGameDev.com's Best Non-Player Character award? This year's clear first place for the vote of best NPC was PORTAL 2, which received your praise for its portrayals of GlaDOS and Wheatley in particular. With this sequel, Valve has taught game developers many valuable lessons, in particular that you don't need expensive motion capture animations to make a great character; all you need is world class writers instead!

While there isn't much AI behind the characters in PORTAL 2 as many of them obviously rely on scripts, it's inspiring to think about how such simple animation techniques can combine with well written dialog to portray rich characters. Hopefully, we'll be seeing these ingredients combined and made interactive in HALF-LIFE 3...

Nominations

• DRAGON AGE 2
• BATMAN: ARKHAM CITY
• UNCHARTED 3

Editor's Pick
Uncharted 3

While this iteration of the series felt like an incremental evolution of the principles established by UNCHARTED 2 (which also won this award two years ago), Naughty Dog has expertly refined and tuned its techniques for portraying game characters and moved further to the forefront of the games industry.

In particular, Nathan Drake's companions stand out in the game as genuine and interesting characters — thanks to a combination of great writing, acting, motion capture, animation and of course AI. The addition of the close combat system in UNCHARTED 3 also increases their levels of believability, not to mention the combinations of interactive animations and prepared cutscenes. UNCHARTED 3 also features one of the richest walk cycles ever seen in a game, in the way player avatar interacting with its environment and uses varied animations based on where the character is looking.

Congratulations to the Naughty Dog team for its inspirational work, and winning this award for the second time! An honorable mention also goes to BioWare for the characters in STAR WARS: THE OLD REPUBLIC, as an evolution of the technology in the DRAGON AGE franchise that won the community vote two years ago. As Kevin Dill pointed out, the gestures used during conversations are particularly impressive.

Design Innovation in Game AI

Vote Winner
Dark Spore

In a year mostly full of sequels, Dark Spore won the community's vote for innovative design, in particular it's AI Director. The topics of experience management and player profiling have become increasingly important recently, as more developers try to make their gameplay a bit less chaotic and closer to what the designer intends.

The details of the AI Director were shared by Dan Kline at the Paris Game/AI Conference 2011 last june, where he showed how the enemies in the game are spawned based on the player's state — among other things. The game also uses this approach to adjust difficulty levels based on the player's selection.

Nominations

• BASTION (The Narrator)
• RIFT (Enemy Spawns)
• SWARM (Group Behavior)

Editor's Pick
SWARM

One of the most interesting designs of the year comes from Hothead Games. SWARM is a fascinating merge of Lemmings and 'boids' with flocking behaviors, challenging you to control a group of Swarmites through hostile terrain. Your goal is to try to score points by voluntarily sacrificing your Swarmites, but preserving enough of them to reach the next checkpoint that replenishes your group's count.

What makes this game interesting from an AI perspective is the basic combination of group behaviors that lead to interesting, challenging and — most importantly — fun gameplay. You can tell your group to spread out, regroup, move in various directions, jump and use nearby items for example. The resulting behaviors are also very humorously executed, for example the Swarmites will pick up each other accidentally when you tell them to throw objects (e.g. explosives).

Best AI in an Independent Game

Vote Winner
Frozen Synapse

One of the most acclaimed and commercially succesful indie games of 2011 also won the community vote for the Best AI in an Independent Game. Frozen Synapse is a turn-based top-down tactical shooter with challenging gameplay and very deep mechanics. The game features AI bots to play against, which are relatively rare in even big-budget AAA games, so it's impressive to see them implemented to this degree of success in an independent game!

Nominations

• SWARM
• MEN AT WAR: ASSAULT SQUAD
• CARCASSONE (iPad)

AI Technology in a Supporting Role

Vote Winner
From Dust

The cellular automata in Ubisoft and Eric Chahi's god game FROM DUST won the community vote for AI in a supporting role. The game itself is a populous-style simulation where tribes inhabit a complex terrain, though in this case it's subject to the forces of nature! Rock, sand, soil, water, laval and plants make up this dynamic and ever changing world that looks and feels very real.

Under the hood is a complex simulation that specifies how each cell in the world gets updated, depending on the amounts of material nearby and their velocities — among many other things. Getting this to run on the PS3 in particular was a huge technical undertaking that involved meticulous accounting for every bit in the world's representation!

Nominations

• SPACE MARINE (Squad AI)
• SECTION 8: PREJUDICE (The Bots)
• MINECRAFT (Procedural Worlds)

Technical Innovation in Game AI

Vote Winner
Killzone 3

On the technical front, it's KILLZONE 3 that won the community award for technical innovation with its automatic annotation technology. Guerrilla Games worked closely with Mikko Mononen to integrate the open-source project Recast into its tools and export pipeline, in particular to provide better analysis of the terrain. This helped level designers place cover locations for the player in a much more consistent fashion, among other things.

Technically, this is achieved using voxelization under the hood, which allows for reliable processing and analysis of local space. Mikko demonstrated at the Game/AI Conference 2011 how this can be used to find not only cover, but jump links and potentially any interesting action that can be performed at the border of a navigation mesh.

Nominations

• FROM DUST (Cellular Automata)
• LEAGUE OF LEGENDS (Level Scripting with BTs)
• BULLETSTORM (Locomotion Planning)

Editor's Pick
Bulletstorm

One technique in particular that impressed me was the locomotion planning in Bulletstorm. The whole game is an impressive technical achievement in game AI programming, which outperforms the more established AAA shooter franchises built by bigger teams! The design of the game too is refreshingly innovative, though sales of the game didn't match the expectations of People Can Fly and Epic.

Under the hood, the locomotion is achieved in an animation-driven approach that's targetted to fit on a path. Compared to the traditional steering behaviors with reactive animation, this is not only much easier to put into place for AI characters but results in higher quality movement.

Your Games of the Year

What games had the biggest impact on your year? Which ones will you continue to play in 2012, recommend to friends, or keep on your shelf for further study of the AI?

Post a comment below or in the forums, and let everyone know what you think!

It's always cool to watch in-game visualizations, and as a developer building them can be very rewarding too! However, in the heat of the moment it's easy to forget or tell yourself you won't need to visualize *this* particular feature.

Below you'll find a tutorial video, recorded in AiGameDev's secret research lab, on the topic of visualizing gameplay and AI. This blog post will also go into more details with some great high-definition screenshots. Hopefully it will inspire you and convince you that visualizations are often a reliable investment!

The Case for (Better) Visualization

In practice, there are three major reasons why visualizations will pay off in your project:

1. Code Correctness — As you're implementing a feature, even if you have unit tests, it's great to have visualizations to make sure your assumptions are correct. Complex game worlds may have special cases that your tests didn't cover, and new levels may reveal those problems only later.
2. Identifying Bugs — Beyond just checking that your code actually works, the visualization helps you rule out certain problems while you're trying to isolate a bug. If you have a collection of visualizations you can easily spot the problem or have an idea of where to look.
3. Tweaking & Tuning — As you get towards the end of the project, visualizations are also particularly useful for helping make changes to the levels, the behaviors, the gameplay in ways that wouldn't be as obvious using the regular geometry.

In the rest of this post, you'll see five visualizations we used while building a game prototype that we call RUSHING BASES (based on British Bulldog, a tag-based game played in schools). Notice how most of these tools helped us both at the start of the project when building the infrastructure, and then while balancing the gameplay.

Example #1 — Grid Map

What Does it Show?

This particular demo is built based on 2D grids, so the map shows areas of the world that are accessible and those that are not. By default, cells that are blocked are shown in magenta, and the open cells are simply not drawn.

How Does it Work?

It's simply one large texture, of the resolution of the grid, which is applied onto a debug polygon stretched over the world. There's a Z-offset applied to make sure no Z-fighting occurs, and optionally you can setup the depth test to ignore the world geometry so the texture is visible everywhere on the screen.

Why did we need it?

• Helps understand the impact of decisions about the grid's resolution.
• Identifies blockages and narrow spaces to improve the level design.

Example #2 — Area Network

What Does it Show?

The fundamental representation of the game is based on groups of cells that we call areas. These form the basis of the pathfinder and the influence map, as you'll see below. The area network visualization shows areas both individually, and how they relate to each other.

How Does it Work?

There's an instance of a circle shape that's reused and drawn in multiple places, based on the center of each area. The circle is scaled based on the area size, and given a unique color based on the area ID. Connections are drawn as unique splines, though in the past I've used common arrows from each area to indicate connections — which is a bit more efficient to render but harder to visualize. The area labels are custom textures rendered by the underlying graphics engine, and overlaid onto the world with a Z-offset.

Why did we need it?

• Helps understand the trade-off between area map's precision and simplicity.
• Shows the actual graph that underlies the pathfinding and influence mapping.
• It looks really cool and it's great to show people that visit the office :-)

Example #3 — Hierarchical Graph

What Does it Show?

This is the high-level search graph that's actually used by the hierarchical pathfinder. It's calculated based on the areas, but has a very unique structure that's show specifically by this custom view. Only the edges of the high-level graph are drawn, though the nodes are implicitly obvious.

How Does it Work?

The graph is drawn as a set of edges, each represented as a narrow polygon. (Modern graphics drivers don't always support rendering lines, and this is typically done as a set of triangles.) The nodes in the graph each have labels, which are drawn as camera-facing billboards.

Why did we need it?

• Helps isolate pathfinding problems if there are problems.
• Shows all options of paths that could be used by the AI.
• Reveals missing paths and possible level design problems.

Example #4 — Influence Map

What Does it Show?

This visualization shows the influence map, which shows the cost of areas updated dynamically. Some areas are at risk (red, yellow) based on proximity to members of the opposing team, and other areas are marked as beneficial (blue, cyan) due to previously succesfull runs. This view shows both of those factors either combined or separately.

How Does it Work?

This implementation is done in the same way as the grid map, as a texture ovelaid onto the world. In this case though, the underlying texture needs to be updated on a regular basis as the influence map changes.

Why did we need it?

• Helps understand the tactical decisions made by the AI while running.
• Provides feedback for balancing and tuning those decisions as a designer.
• Displays long term statistics about levels so they can be used for balancing.

Example #5 — Navigation Paths

What Does it Show?

This view shows the final navigation path, after pathfinding and string-pulling, for all the actors in the world. It's drawn as a set of arrows joined together, each representing a segment in the final path. It's also possible to enable showing the history of previous paths used.

How Does it Work?

The lines and arrows are all rendered as narrow polygons, like previous views. The only difference in this case is that the paths must be updated on a regular basis when the navigation changes. There are conditions and optimizations in place to reduce the amount of work done due to dynamic changes.

Why did we need it?

• Shows path correctness at the low-level, helps identify various pathfinding bugs.
• Displays the decisions and path choices made by the AI on both teams.
• Reveals insights into the high-level behavior for design improvements and optimizations.
• Provides a way to view the selection of tactiac paths over time by drawing path history.

Conclusion

In our case for this game, the “Navigation Paths” provided by far the most useful representation since the game is very much about tactical pathfinding through an obstructed world. This visualization gave us benefits all the way from low-level code to design insights, as well as optimizations and behavior fixes.

In general, it's extremely useful to have visualizations of many different kind for a variety of purposes. As a rule of thumb, the more you work on a system in the codebase, the more time you should dedicate to implementing in-game representations for it. You'll thank yourself later!

Tutorial Video

In two weeks, we'll be releasing some exciting demos that have been in the pipeline for the past few months, and we thought it'd be a great opportunity to share some of the techniques we learned during development. This video tutorial in particular looks into some of the visualizations we built for one of our demos, called RUSHING BASES — including the area map, the hierarchical graph, the navigation view and the influence map.

NOTE: Last weekend we held a live masterclass about the chasing and evading behaviors that we built into the game, including AI with prediction and learning. You can access the replay as part of our launch of AiGameDev.com ULTIMATE!

Stay Tuned!

As well as this weekend's masterclass, we'll be releasing more tutorial videos about our other demo. If you liked this one and would like us to send you the next one once it's available, just sign-up to this mailing list:

You can also follow along over the next few weeks as we unveil a new part of the site by visiting the official launch page.