AI Systems of L4D

From Valve Developer Community
Jump to: navigation, search

To do: This article is currently incomplete: see discussion page.

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 prioritise 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 behaviour 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" (eg. 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 Behaviour 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 contruction 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 behaviour. Are there any ways to reduce the jaggedness of the path and create a more fluid motion?

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

The next image is a possible solution: optimise the number of points on the path to utilise 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 - optimising 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 optimised 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 travelled 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 behaviour - 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. optimised path following.

Comparing reactive path following to the previously mentioned, highly optimised path following we can see that the resultant path is reasonably close to the optimised 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 stages:

Approaching a surface.

1. Approach

The NPC periodically tests for objects immediately in front of it as it follows its path.
Calculating vertical space.

2. Find Ceiling

After an obstacle has been detected, a hull trace is used to determine the vertical space above the NPC.
Scanning vertical space.

3. Find Ledge

The vertical space is then scanned by a series of hull traces until the first complete, unobstructed trace is found.
Finding ledge height.

4. Find Ledge Height

A downwards hull trace from this position finds the exact height of the ledge to be climbed.
Finding the edge of the ledge.

5. Find Ledge Forward Edge

A final series of hull traces step backwards until the forward edge of the ledge is located.
Performing the climb.

6. Perform Climb

The closest match is picked from dozens of motion-captured animations of different height increments.

Behaviours and Decision Making

A L4D actor's behavioural system.

The behavioural system of an actor in Left 4 Dead can be visualised 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 recognised set of entities.

Intention

Maintains and manages a system of concurrent behaviours (HFSM+Stack):

  • Behaviour: contains and manages a system of Actions
  • Actions: The building blocks of intentional actions. An Action can contain a child Action, which executes concurrently.

External links