Path planning is a key part of the Artificial Intelligence (AI) in games. It's how units move to where you click in Starcraft. It's how enemies in Mass Effect run around cover to get to you. It's the magic that makes computer-controlled characters move towards goals efficiently while avoiding obstacles and hazards.
Getting started with proper pathfinding behavior can be daunting. The internet is filled with descriptions of the classic "A* algorithm" for grid-based navigation. But modern 3d games often involve complex environments, right? How do programmers make characters move around in those? Why don't characters zig-zag their way towards you in games with good AI?
In this tutorial, we'll take a look at making characters navigate the world using Navigation Meshes, which are used in lots of the best games available today. That technology is part of what Valve and Unreal use in their game engines.
The first part of any pathfinding AI is figuring out how to represent the game world in a way that is useful for navigation. Some of the most common representations are
The most important thing to realize about all of these representations is that they are just graphs. The first thing you thought of when I said "graph" was probably a bar or line graph.
That's not what I mean here. In game AI (and in mathematics), graphs are a series of nodes connected by edges. The simplest way to think of these terms in the context of pathfinding AI is that each node in a graph represents a possible place a character could be and each edge indicates that it is possible for the character to move between the nodes it connects. Each edge has an associated cost, which represents the effort it takes for a character to move from one node to the next. When we talk about pathfinding, we're really talking about finding a path between two nodes in a graph, ideally minimizing the cost of the path.
Waypoint representations of space are easy to create and think about, but they are not very good for pathfinding. Although they use very little memory, they result in inefficient, unrealistic paths.
The main idea behind waypoint systems is to place a small number of nodes and edges in the game world so that characters can find their way around static obstacles. Unfortunately, if characters always stay on paths between waypoints, their behavior will be unrealistically constrained. However, if they leave the waypoint network, they can get stuck easily.
If you look for an intruductory tutorial on path planning, chances are you'll find one that uses a grid. Grids work really well for small environments, especially for games in which characters move on a grid already. More complex environments require finer grids, which can take up an infeasible amount of memory for large worlds.
You might have seen a representation of a grid like this:
What you might not have realized is that a grid like this is just a more compact way to represent a very dense graph:
Grids don't seem to be used much for large, modern games. However, cutting-edge AI researchers are finding uses for them for very localized navigation in conjunction with other techniques such as navigation meshes.
Navigation meshes are an efficient way to represent walkable regions in a game world. A common implementation relies on connected convex polygons.
Just like in the grid representation, each polygon is a node and each edge shared by two polygons represents a connection between nodes.
Great! We can represent space: now what? How will that help our characters get where we want them to go? The answer is: search. The A* (pronounced "A-star") algorithm is an efficient way of finding the cheapest path between two points on a graph.
There are many great explanations available online, so I won't go into a lot of detail, but the main idea behind A* is to maintain a frontier of unexplored nodes a character could visit at any point in time and to explore the one most likely to be part of the least costly path to the goal first. To do this, it uses a heuristic function that estimates the cost from a node to the goal. The simplest type of heuristic that works for A* simply returns the distance between the node and the goal. Here's an example A* implementation:
Now what? We have some optimal path in an abstract graph. How does that help our characters move? The answer to that question depends a lot on the specifics of the game you're making. In some games, you can probably get away with mapping the graph directly to physical space. In most cases, though, you need to smooth the resulting path somehow. In Left 4 Dead, characters move between portal midpoints and smooth their path by moving towards a visible node that is part of the optimal A* path but is several steps ahead.
We can do better, though. If we are using a grid or navigation mesh, we can implement a smoothing technique known as the Simple Stupid Funnel Algorithm, a practical path smoothing technique developed by the lead AI programmer from the original Crysis, based on a PHD thesis on pathfinding.
This algorithm is all about smoothing paths by finding corners on the minimum distance path of a navigation mesh without leaving the walkable area. The result is the same as if the A* path were a string being pulled until it was taut.
The algorithm proceeds as follows:
You can find the defacto C implementation of the funnel algorithm here. However, you'll probably have to adapt it to fit your project because it is highly implementation-dependent.
A key part of writing your own implementation depends on understanding how to tell if the funnel is crossing itself. One of the easiest and most efficient ways to do this involves the cross product. In 2d, we can use the sign of the non-zero component of the cross product to tell us the order of the points in a triangle. In most 3d game environments, we can simply disregard the third dimension for the sake of path smoothing, since most characters don't need to walk on ceilings or perfectly vertical walls.
We took an A* path and smoothed it, but the characters still move unnaturally! This is where steering behavior comes into play. Real people don't make point turns when they go around corners (or at least most people don't, anyway...), why should your characters? The smoothed A* path is a great guide for environment navigation, but it doesn't need to be followed exactly. One of the simplest things you can do is to implement a path following behavior that tells characters to generally stay within range of the smoothed path and to steer back towards it if they are getting off-track. You can combine multiple behaviors together to get even better results.
That's it for now! If you're interested in exploring pathfinding even further, I highly reccomend the following: