gaming me

AI navigation in Left 4 Dead: Part I February 25, 2010

The other day my good friend (and great game designer) Bruno Palermo pointed me to this presentation that Mike Booth used last year at the Artificial Intelligence and Interactive Digital Entertainment Conference. I found it extremely interesting and useful. I didn’t know Valve made publication material available through their website!

I didn’t have the pleasure to watch it, but by the slides you can tell his presentation goes through a lot of cool stuff. So what I want to do is focus only in the AI for pathing and movement and try to get closer to an actual implementation of the system. See it as my version of the presentation. Is that possible? I think it is, let’s try (I didn’t think this through when writing, but if you are reading it is because it worked. Don’t worry and continue reading).

The most important thing is to remember that the goal is not the best possible behavior but instead the most realistic one. And an exact, perfect path or movement is not very realistic. So let’s begin.

To move the bots (let’s call them bots, right?), the system works in two phases: path finding and movement. One could think after path finding, moving is easy. Well, it isn’t. The L4D system computes the paths in a navigation mesh and the bots extract a rough direction from the path finding system, not an exact guide on how to get from point A to point B. That means it is up to the movement phase to figure out how to reach the next point in the path (jumping, climbing, crouching, whatever).

So the very first step towards the navigation AI is to generate or edit a navigation mesh for the map. I won’t get into specifics (googling navigation mesh should be a good start), but essentially the algorithm tracks “walkable” areas from the map and then grows rectangles in a way that best fits the areas. The result should be a graph-like structure with a bunch of bounding boxes representing areas where the bots can walk. If a bot can move between boxes, we add a bidirectional connection connecting them.

With the mesh properly generated (never at run-time, eh?), the path finding algorithm goes through the graph with a simple A* algorithm. After running A* in our walkable rectangles graph, we have an ordered list of rectangles in the path. At this point it is obvious things are already imprecise, which means the movement phase has to find the best way to go from one rectangle to the other.

The optimal approach, rejected by Booth because it looks robotic, is to look for the rectangle further away with a clear, direct path to it. Because the pathing system is not the only one acting on the bot at run-time (there’s also flocking, small obstacle avoidance, etc), this alternative also requires a lot of repathing: every time something obstructs the path to the target node, the system would have to compute a new path.

Instead, the navigation system uses what Booth calls Reactive Path Following. The decision is very local and sets as a target the unobstructed node further down the path in the direction the bot is facing. Booth mentions this makes the path fluid which wouldn’t be true unless some steering behavior were in place, so here’s my very high level interpretation of that algorithm:

// Rough example of the path update function.
void Bot::PathUpdate(f32 m_fDeltaTime)
{
	// unless the bot got too far from the path, we don't have to compute it
	// again. In this case, the realism of the algorithm helps performance!
	// Of course we also have to find a path if we don't have one yet.
	if (!HasPath() || (DistanceFromPath() > m_fMaxPathDistance))
	{
		m_lPathNodes = AStar::FindPath(
			m_pWorld->GetNavigationMesh(),
			m_vPosition,
			m_vTarget);
		m_iCurrentNode = 0;
	}

	// looking for the best node to track. Notice that the next node is local,
	// the decision is made every frame.
	Node* pNextNode = m_lPathNodes[m_iCurrentNode];
	for (s32 i = m_iCurrentNode; i < m_lPathNodes.GetSize(); ++i)
	{
		if (IsFacing(m_lPathNodes[i]) && IsClearPath(m_lPathNodes[i]))
		{
			pNextNode = m_lPathNodes[i];
		}
	}

	// assuming some complex heuristic might take place to decide which
	// priority each system gets, we don't update the member variables
	// directly. Instead, make requests informing the current system
	RequestMovement(
		ComputePathTranslation(m_fDeltaTime),
		ComputePathSteering(pNextNode, m_fDeltaTime),
		PATH_FOLLOWING);
}

Ok, that’s it for path finding and basic path following but there’s a lot more to cover. However, I haven’t posted for a really long time and it would take me another week to finish the whole subject. So let’s stop at this point and in the next post I’ll continue to object avoidance and ledge climbing.

See you space cowboys…