Real-Time Videogame AI

Nov 24, 2009

Smart is Not What People Think

“The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.”

Edsger Dijkstra

There are a lot of films, novels, and comics about artificial intelligence. These present AI as a problem solving, self-preserving intelligence eager to assert its dominion over people.

There are a lot of non-fiction books, internet references, and university classes on artificial intelligence. These present AI as a pattern-matching, data-mining adaptive algorithm used to process mountains of messy, complex information.

AI in real-time videogames is not about trying to program intelligence. It isn’t about making the best decisions, thinking through complex problems, or adaptive learning.

AI in real-time videogames is about creating the impression of intelligence. Generally speaking, the appearance of intelligence is all that we’re going for – it’s functionally pretty similar in such narrow domains, and infinitely more within reach than creating “real” intelligence.

What are the qualities that we can appeal to, in order to create the impression of intelligence during gameplay?

Smart is Unpredictable

If the “smartest” opening is move A, that move had better not be the opening every time, or the player will just be conditioned to react to that opening move every time. So long as one strategy works repeatedly, what the player is up against doesn’t come across as intelligent, just mechanical.

The moment that pattern is broken, or that expectation is violated, the player will project intelligence onto the previously robotic computer entity. “Why did it switch to move B?” The real answer to this question doesn’t matter – whether the program looks deeply into the player’s eyes and reads his or her mind, or simply has a random 20% chance of doing something random – the important thing is that the player is forced to stay alert instead of always leaning on a memorized strategy. (Guess which of those two strategies is the most cost and time effective solution? Mind reading, or inserting a line that reads if((rand()%10)<2)... ) The 1997 game Trespasser, based in the Jurassic Park universe, attempted to create AI that “thought” based on needs around the ecosystem, but the end result was monsters wiggling around looking confused until they charged sideways at the player. By comparison, listen to a young person or non-technical player spending a few minutes in front of Ms. Pac-Man, and before long they’ll blame the mostly random ghosts for all sorts of devious schemes.

Keep it simple. Throwing in a good dose of randomness at a high level for the enemies is often just as effective at creating the illusion of intelligence for the player as a more contrived system of reasoning that would take longer to develop.

Smart has Priorities

Heuristics – “fuzzy logic” is another term for this – is a way to simplify complex decisions involving many considerations into a decision about decisions.

The concept here is a powerful one, but simple once introduced. Instead of building a massive tangle of if-else conditional statements and boolean logic to determine an AI character’s next move, the goal is to encapsulate what information derived from those variables means.

It’s a form of divide and conquer. To use a business metaphor: how does a top-level executive make informed decisions? By asking each of their advisors and expert employees to offer distilled summaries of the issues they each believe are most important. In the same way, rather than trying to deal with countless variables all in the same part of code, we want to distill groups of variables into meaningful measures that we can base the high level decisions upon.

Short Break for Examples

In Burn 2, a real-time PC game involving up to 10 fast-moving AI ships thrusting in a variable gravity environment with procedurally-generated fully destructible terrain (in other words, very little absolute certainty), each AI has a few values that they evaluate independently each frame, and behaviors are determined by which of these values exceeds a priority threshold:

  1. Is the ship above minimum safety altitude to avoid ground collision?
  2. Is the ship below maximum altitude to ensure room for evasive maneuvers?
  3. How imminent is collision with a mountain (laterally) if nothing changes?
  4. Is the nearest enemy in firing range? Am I facing them to immediately begin firing?
  5. How close is enemy fire? Is one facing me which may be firing, and if so, am I facing them (to fire back) or facing away (to thrust away to safety)?
  6. Am I about to collide with an enemy? If so, do I have more health than the enemy? (Collision causes equal amounts of damage to both ships involved)
  7. Is my current target low to the ground, with little distance on each side, implying they are entrenched for cover? If so, switch to bombing patterns…

In Ghosts in the Machine, a real-time PC game involving 3-5 high speed projectiles ricocheting between 4 independent players (3 of which are AI), the AI keeps track of the following information for decision making:

  1. Is a ball heading toward my goal? (forget any other objectives, and protect the goal)
  2. Which players currently have a clear shot at my goal, and a ball to fire? (block that angle)
  3. Which players do I currently have a clear shot on, and if I have a ball to fire, are they blocking the gap?
  4. Is another player currently swamped with lots of incoming projectiles, that would be too overwhelmed to block if I fired now? (fire on them immediately!)
  5. Which player has caused my base the most damage? (aggressively hassle that player, to knock them out)
  6. Which player has won the most rounds? (target them, so that it won’t come down to one on one against them later)

Smart has Personality

By changing which of the above is a priority for each AI player, I was able to produce personality differences between each of the AI figures (defensive, aggressive, and retaliatory), and by shifting a value between their impatience (premature firing) vs their sound decision making (higher threshold for likelihood of successful shot before firing), I was able to vary any of the 3 personality types from easy/dumb to hard/intelligent.

(Side note: Burn 2 was based on the classic game Gravitar, and Ghosts in the Machine was based on the classic game Warlords. To learn more about the design of Ghosts in the Machine, check out this PDF presentation on its design I put together shortly after its completion in 2007.)

Smart Acts Decisively

Moods – or “finite state machines” – can encapsulate a sense of memory, reaction, decisiveness, and thus: intelligence. The way this works is that each character keeps a number tracking its state of mind. Is the enemy wandering, alerted, angry, or retreating? Is the enemy grouping together, spreading out, hunting for a health pack, or battling to the death on a kamikaze charge?

Smart Groups Have Emergent Teamwork

For an interactive demonstration of mixing randomness and determinism in AI that can be played quickly online, check out my experimental project BeeDifferent. Experiment with the slider below the game to see how enemies which all behave optimally are trivially outsmarted, enemies which all behave randomly are easily outsmarted, but by using an even mix of the two, the effect is the have some spread out as mines while others force the player to run through said mines.

Smart is Verbose

Telegraphing the enemy’s current state, and/or the transition into that state change, also goes a long way in creating the illusion of intelligence (though this shouldn’t be too repetitive). The enemies turning red with anger in Bubble Bobble declares their current mood clearly, Metal Gear Solid bad guys get exclamation points over their heads, and enemies in No One Lives Forever and Thief (both of which were widely praised in their time for their otherwise normal AI, thanks to this single reason) announced things along the lines of “I can’t find her!”, “I know you’re here!”, and asking their comrades things like, “Did you hear something?”

Smart Builds Upon Smart

Big games – whether a First Person Shooter, Third Person Adventure, or Real-Time Strategy – invite some other AI needs like pathfinding. FPS and TPA games often include hand-placed nodes in the world giving AI clues for where doors are, where the center of hallways/rooms are, and where the best cover points are to kneel behind. RTS games can involve a bit of clustering (basics of facial recognition algorithms) to assess areas of defensive weakness. Basic vector geometry and dot products can be used to ascertain line of sight between characters (including trivially checking a character’s facing), and trig (especially atan2) are useful in finding angles to shoot in, look at, run toward, or flee from.

Puzzle games are obviously a whole different can of worms, depending entirely upon the game’s structure.

All that said, much of the real-time AI in most games still tracks back to (a.) creating the illusion of impatience and intelligence by being unpredictable (b.) reducing groups of variables into easily prioritized decision points (c.) committing decisively to display a range of possible behaviors and (d.) unsubtle announcements of the current behavior or moments of mood switching.

Smart Code is Simple

On the technical side, the AI “mood” (finite state machines) can be tracked simply by keeping two more integers per enemy. The numbers are used by setting one of the integers to an enumerated value corresponding to behavior #1 vs behavior #4 (etc.), and the other tracks how long the current behavior should continue before being reassessed. For example:

enum {
  MOOD_WANDER, // same as "#define MOOD_WANDER 0"
  MOOD_CHASE, // same as "#define MOOD_CHASE 1"
  MOOD_MIMIC,
  MOOD_FLEE,
  MOOD_NUM // useful for randomizing mood
};

/* the larger the first number (200), the more decisive
the enemy seems; the larger the second number (150),
the less predictable the enemy seems */

#define NEW_MOOD_TIME (200+(rand()%150))

class Badguy_typ {
  // skipping class variables definition here for brevity

  int aiMood;
  int cyclesTilMoodReconsidered;

  Badguy_typ() {
    aiMood = MOOD_WANDER; // begin unalerted
    cyclesTilMoodReconsidered = NEW_MOOD_TIME;
    // other character initialization goes here
  }

  void Move() {
    if(--cyclesTilMoodReconsidered <= 0) {
      aiMood = (rand() % MOOD_NUM); // random new mood
      cyclesTilMoodReconsidered = NEW_MOOD_TIME;
    }

    /* cyclesTilMoodReconsidered is only intended as
    timeout, so that left on their own, unprovoked,
    enemies will seem unstable, curious, and impatient,
    like they have minds of their own. */

    /* Within the switch statement below, it's fine to switch
    aiMood and reset cyclesTilMoodReconsidered even if it
    isn't time for a mood change yet. For example, if the
    enemy is within a certain range from the player,
    especially if line of sight is established, switch
    "aiMood = MOOD_CHASE;" */

    switch(aiMood) {
      case MOOD_WANDER:
        // code for enemy that's wandering aimlessly
        break;
      case MOOD_CHASE:
        // code for enemy aggressively going after the player
        break;
      case MOOD_MIMIC:
        /* code for enemy that's copying the player's movements.
        This is simple but distracting. It gives a false sense of
        security suggesting the player is in control, but can turn
        aggressive unpredictably or upon getting in close. */
        break;
      case MOOD_FLEE:
        // code for enemy getting away from the player
        break;
    }
  }

  // skipping other class methods for brevity
}

The above code snippet pretty well describes the AI for most of my first PC games, including Pac-Deli, and Swarm. It's not going to appear intelligent in a one-on-one fight, but when the player is up against 3-8 enemies operating independently in this fashion, the player begins to interpret the emergent patterns of their mostly random (unpredictable!) behavior as teamwork, plotting, and strategy. In Pac-Deli I gave each ghost color a significant bias toward 1 of the 4 behaviors - half the time using their "personality" and half the time switching to a completely random choice - and this created the impression that one was more confused, one was more aggressive, one was intent on being tricky.

We're Not Trying to Beat Kasparov

Ultimately, it's ok if the AI isn't the smartest thing on earth. If the player outsmarts it, they'll feel like a champ. You don't need to prove to players that a computer can process and respond to information faster than they can.

As Ian Davis, the founder of Mad Doc Games told me, "The goal of videogame AI should be to put up a fair, convincing fight, and eventually lose."

(Originally posted as GameDevLessons.com Vol. 8 Sec. 2)



Learn and practice team game development with Gamkedo Club.
Membership worldwide. Professional support. Proven process.




Subscribe by e-mail to receive weekly updates with Gamkedo.Community interviews and YouTube training videos for game developers!



3 Comments

  1. […] Vol 8 Int – Game AI […]

  2. […] design – the bottom-up thinking that leads to levels designed as grid tile arrangements, enemy/obstacle AI as simple patterns, and non-human/non-character for player control (tank, spaceship, yellow […]

All contents Copyright ©2017 Chris DeLeon.

Site production by Ryan Burrell.