AI Systems of L4D

From Valve Developer Community
Jump to: navigation, search

This article was based off the presentation "The AI Systems of Left 4 Dead" by Valve's Mike Booth. The original PDF file can be found here: [1]

Goals of the L4D AI

We all know that Left 4 Dead is a great game to play, and a lot of this is down to the way the AI (artificial intelligence) is programmed. How, for instance, would a survivor bot know to prioritize helping a team mate who is incapacitated instead of healing themselves? Why do you never see zombies spawning out of thin air in front of you? These decisions have been made around the four following goals that the Left 4 Dead AI was designed to achieve:


  • Deliver robust behavior performances - essentially, a survivor bot or infected should always be able to make a decision (ideally a realistic one) in a given situation.
  • Provide competent human-player proxies - if less than four players are present in a campaign then the remaining spaces will be filled with bots, so these bots should be both competent enough to complement the human players while not being "overly competent" (e.g. consistently deadly accurate).
  • Promote replayability - make the game interesting to play and keep it interesting after the second, fifth, tenth and even twentieth re-plays.
  • Generate dramatic game pacing - ties into the above; to help keep gameplay interesting and avoid both combat fatigue and lack-of-combat boredom, tune the game pacing relating to how "stressed" the players are.

Delivering Robust Behavior Performances

Paths

Navigation Meshes

Arguably the most important component of allowing an NPC to move around the world is the navigation mesh: this stores all the information about where NPCs are allowed to go, which areas connect onto any given sector and the routes that can be taken, which areas can see which other areas, how far it is to go until the survivors reach the final safe room, what type of area the survivors are standing on (checkpoint, for example), and much more.

A possible route calculated using the navigation mesh.

However, due to the construction of the navigation mesh, any path that is calculated between sectors is very rough. Consider the image to the right: any common infected, for example, running along this path would constantly have to turn left and right as they met the points on the sectors, creating very unrealistic running behavior. Are there any ways to reduce the jaggedness of the path and create a more fluid motion?

The same path but after having optimized the route into resultant vectors.

The next image is a possible solution: optimize the number of points on the path to utilize the least amount possible and take the shortest route to the target destination.

Advantages

  • Creates minimal and direct path - you're not going to get where you want to go any quicker than with this path.

Disadvantages

  • Non-trivial CPU cost at path build time - optimizing the path to this extent takes up an inconvenient amount of processing time; using this method for 20+ infected at once would be unwieldy and costly.
  • Paths are recomputed often in the game - yet more non-trivial CPU usage which could be avoided.
  • Following path directly looks robotic - similar to the previous scenario, this optimized path still has sharp corners and would look less fluid than desired.
"Reactive path following" looks ahead to points further down the path.

"Reactive path following", seen to the right, involves moving towards a "look-ahead" point along the path; this point changes as the movement progresses. The result is a much smoother and more realistic path traveled by the NPC.

Different stages of reactive path following.

Advantages

  • (Re-)pathing is cheap - this pathing method is much less taxing on the CPU than the previous method.
  • Local avoidance handles small physics props, other bots, corners, etc. - if an NPC comes into contact with a physics prop, for example, on their path, they automatically avoid it.
  • Superposes well with mob flocking behavior - this version of pathfinding fits well with the way the mobs of infected "flock" towards the survivors.
  • Resultant motion is fluid - much better than following a robotic straight-line path.

Disadvantages

  • Can avoid off path too much, requiring re-path - if the NPC skirts too far around an obstacle they may run into a different area altogether, requiring a re-path to the destination.
Reactive vs. optimized path following.

Comparing reactive path following to the previously mentioned, highly optimized path following we can see that the resultant path is reasonably close to the optimized path, and so will be fairly efficient to follow. Reactive path following is used by all actors in Left 4 Dead.

Climbing

Another design goal of Left 4 Dead was never to allow the survivors to reach an area where an infected could not attack them. For this reason, the common infected are able to rapidly climb. This uses an algorithmic technique similar to that of local object avoidance, and solves the major issues of navigating both complex geometry and movable physics props.

The climbing process follows 6 steps:

  1. Approach: The NPC periodically tests for objects immediately in front of it as it follows its path.
  2. Find Ceiling: After an obstacle has been detected, a hull trace is used to determine the vertical space above the NPC.
  3. Find Ledge: The vertical space is then scanned by a series of hull traces until the first complete, unobstructed trace is found.
  4. Find Ledge Height: A downwards hull trace from this position finds the exact height of the ledge to be climbed.
  5. Find Ledge Forward Edge: A final series of hull traces step backwards until the forward edge of the ledge is located.
  6. Perform Climb: The closest match is picked from dozens of motion-captured animations of different height increments.

Behaviors and Decision Making

A L4D actor's behavioral system.

The behavioral system of an actor in Left 4 Dead can be visualized like on the right, and divided into four sections:

Locomotion

In charge of moving the actor to a new position in the environment (collision resolution, etc.).

Body

In charge of the state of animation.

Vision

In charge of line-of-sight, field of view and "Am I able to see X?" queries, and maintains recognized set of entities.

Intention

Maintains and manages a system of concurrent behaviors (HFSM+Stack):
  • Behavior: contains and manages a system of Actions
  • Actions: The building blocks of intentional actions. An Action can contain a child Action, which executes concurrently.

Encapsulation of Action processing

These are 5 AI events used in L4D. These are also used for bots like in TF2.

  • OnStart
  • Executed when the Action is transtioned into
  • Can return an immediate transition
  • Update
  • Does the “work” of the Action
  • Update can return a transition to a new Action
  • OnEnd
  • Is executed when the Action is transitioned out of
  • OnSuspend
  • Executed when Action has been put on hold for another Action
  • Can return a transition
  • OnResume
  • Executed when Action resumes after being suspended
  • Can return a transition (perhaps Action is no longer valid)

External links