Fixing Pathfinding Once and For All
I normally do everything I can to avoid saying things that could be interpreted as a criticism of other games or developers in the industry.
But in this case, I had to make a bit of an exception.
I need to talk about some problems we face with pathfinding. In order to prove that these problems still exist, I felt the need to make this video … which will hopefully be taken in the humorous and lighthearted spirit in which it was intended
…视频连接已经无效了
All of these clips were recorded over the last week with the latest, most-recently-patched version of each game.
As you can see, we’re still a long way from having robust pathfinding across the board … and it’s even a problem in some million-unit-selling, AAA-quality titles.
It’s not necessarily a universal problem. Many modern games do have high-quality pathfinding, and pathfinding often works well in some of the games shown here.
But there are still too many games that do pathfinding the same way that games did in the 1990s.
(Note: The only reason you see lots of PC role-playing games here just comes down to convenience. These are the games I had installed at the time. The problem isn’t specific to any genre or platform by any stretch of the imagination; there are plenty of console games with similar issues.)
To the best of my knowledge, most of these games use waypoint graphs for pathfinding. I think that’s the reason for several of the pathfinding issues you see in this video, and many of the pathfinding problems we face in the industry as a whole.
I believe waypoint graphs are now obsolete. This article explains the limitations of the waypoint graph approach and lays out a five-point argument for a better approach.
There was a time when it made sense to use waypoints for pathfinding. Back in the 1980s and 1990s, we were working under serious technical constraints and we had to cut a lot of corners.
But we’re a multi-billion-dollar industry now. Our target platforms have multiple cores and ever-increasing amounts of memory, and we can afford to do pathfinding correctly.
There’s a saying among AI developers in the industry: “pathfinding is solved.” We have good approaches to every pathfinding problem modern games face. We just don’t always use them.
There’s no reason not to have pathfinding that works in every game, every time.
Hit the jump for a detailed explanation.
Why Waypoints Aren’t For Pathfinding
Let me show you what a typical waypoint graph looks like. Here’s a small piece of Stormwind City in World of WarCraft:
Figure 1. Part of Stormwind City in World of WarCraft
Here’s what a typical waypoint graph might look like in that area.
Figure 2. The same area annotated with a waypoint graph
There’s another way to do it, and it involves using convex polygons to describe where AI characters can travel. This representation gives AIs a lot more information about the world around them and supports much more intelligent decision-making.
Here’s what a navigation mesh looks like:
Figure 3. The same area annotated with a navigation mesh
Here, then are the five big reasons why waypoint networks fall short.
1. Some kinds of game worlds require a ridiculous number of waypoints.
Large, open areas usually require tons of waypoints sprinkled liberally throughout the game world to achieve adequate movement.
A navigation mesh, on the other hand, usually only requires a couple of big polygons for these kinds of areas … which you can pathfind through that much more quickly.
Here’s an example.
The image below shows a town in World of WarCraft called “Halaa.” This is a relatively large, mostly open area that NPCs need to be able to navigate through. I’ve edited out a few details, such as the flag and the fountain in town, for the sake of this example.
Figure 4. The town of Halaa in World of WarCraft, seen from above (slightly modified)
With a waypoint-based system, we need to place a lot of waypoints to get full coverage. Even then, our NPCs will end up doing a lot of zigzags during movement unless we specify a lot more waypoints than I’ve shown here.
Figure 5. Halaa with a waypoint graph
With a navigation mesh, on the other hand, we can describe the same area with a handful of convex polygons:
Figure 6. Halaa with a navigation mesh
The simplicity of the navigation mesh means we don’t have to search as many nodes when we call our pathfinding algorithm at runtime, and pathfinding will be faster as a result.
2. They make characters “zig-zag” as they move.
Waypoint graphs force your characters to stick to the graphs you create. This means that your characters are effectively on rails, and will almost never take the optimal path from A to B … because the most direct path will almost never match the graph.
That causes unnatural pathfinding artifacts — in particular, characters artificially “zig-zagging” left and right as they walk.
Here’s an example. Let’s say we want a character to walk from A to B:
Figure 7. Two points in Halaa
Here’s what the path would look like with the waypoint graph I showed you earlier.
Figure 8. Navigating from A to B using the waypoint graph
As you can see, our AIs will be turning a lot while they walk along the yellow path.
Ideally, after we created the path, we could somehow adjust it to make it smoother … perhaps by creating a Catmull-Rom spline along the path points.
The problem is, waypoint networks don’t have any information about anything outside the network, and that makes it impossible to do path-smoothing and adjustment safely and reliably.
How can you create a spline if the spline is outside of the waypoint graph, and actually following its curves might make you fall off a bridge?
You might think there has to be some simpler way to make a path. Unfortunately, with waypoint graphs, there isn’t. Again, if we deviate outside of the waypoint graph even a little bit, we could easily end up falling off a cliff or bumping into a wall. We just don’t have any way of knowing, since the graph doesn’t have any of that data.
So in order to stay safe, we have to take the most pessimistic view possible, and stay on the graph at all times.
The navigation mesh path, on the other hand, would look like this:
Figure 9. Navigating from A to B on the navigation mesh
Since we know where a character can safely walk, we can smooth out the path in any way we like, so long as the smoothing keeps the path on the navigation mesh.
(“Oh,” I hear you say, “but I can just add more links to my waypoint graph to smooth everything out! I’ll connect all the nodes in the whole town if I know an NPC can walk between them in a straight line.”
“But that gives you exponential explosion,” I reply … “You’re talking about 40 or 50 extra links in this example alone. The number of connections you’ll need between all the nodes approaches O(N^2) as the size of the area increases.”
“OK,” I hear you say, “In that case, I’ll just mark each area between any set of 3 mutually adjacent waypoints as ‘open’ so I know my AIs can walk anywhere in that area.”
“That makes a polygon … and you’ve just created a navigation mesh,” say I).
The fact that navigation meshes tell us exactly where our characters are allowed to travel means we can easily use splines to smooth our paths. All we need to do is make sure our splines stay inside the navigation mesh.
Going back to our Stormwind City example, here’s a waypoint path (red) and a smoothed path on a navigation mesh (blue).
Figure 10. A waypoint path (red) and a smoothed navigation mesh path (blue)
3. They don’t allow path correction. That makes robust dynamic obstacle avoidance difficult, if not impossible.
Waypoint graphs don’t have any data about anything outside the graph. They don’t know which areas characters can legally walk on even one inch outside the graph.
That makes it impossible for pathfinding systems to modify waypoint paths to deal with dynamic obstacles robustly.
Let’s imagine there’s a large, heavy crate on the bridge in Stormwind City.
With a waypoint graph, we’re screwed — if the crate overlaps the waypoint graph, we have no idea whether to go around it to the left or the right, or if our path is blocked completely and we need to take a major detour. We could always guess, but if we make the wrong guess, we’ll fall off the bridge and end up in the water.
Figure 11. A large, immovable crate on the bridge
With a navigation mesh, though, it’s a lot easier, since we know what areas we’re allowed to walk in. We do a bit of raycasting against the barrel and adjust our path around it, keeping our path (and ourselves) safely on the navigation mesh.
Figure 12. Navigating around the crate
Sure, you can address this in a waypoint graph, too, by dropping down tons and tons of waypoints until your waypoint graph is as thick as grass (and your pathfinding as slow as molasses).
I don’t know about you, but I’d rather run my A* search over one big polygon than several hundred waypoints.
4. They don’t work robustly for characters that move differently.
Waypoint graphs tend to work poorly for characters with different heights, widths, turn rates, and other pathfinding parameters. This means it’s usually impossible to use a single, unified waypoint graph for all the different types of units in your game.
When we think about AI pathfinding, we tend to think in terms of humans navigating around in a game world.
But AI systems need to control lots of different kinds of units — tanks, planes, ships, hovercraft, motorcycles, orcs, goblins, dragons, lumbering giants, flying and hovering creatures, and so on. In many cases, units need to do pathfinding differently depending on their size, shape, and movement capabilities. A good pathfinding representation should handle all of them.
Here’s an example. Let’s say we have a concrete bunker out in the desert with a few sandbags around it.
Figure 13. A bunker in the desert
If we have a human soldier, he can run along right next to the sandbags (the red arrow in the image below).
A Panzer tank, on the other hand, has to drive much farther away from the sandbags to avoid a collision (blue arrow).
Figure 14. The closest possible paths that a human soldier (red) and a tank (blue) can take around the sandbags
With a waypoint approach, you can’t handle this robustly with a single representation. You need to use totally separate waypoint networks for the tanks and the soldiers. Add a new “motorcycle” unit, and now you need a third network. And so on for every different type of unit that has different movement capabilities.
With a navigation mesh, on the other hand, it becomes much easier.
Figure 15. Part of a navigation mesh around the outside of the bunker
Notice the two light green edges emanating from the corner of the sandbags in the image above. Since we know that a soldier has a collision radius of 1 meter, and a Panzer tank has a radius of 5 meters, it becomes trivial for us to build two different paths using the same mesh. We just compute the path along the sandbags, and then push it either 1 meter or 5 meters away from the corner, respectively, depending on whether we’re doing pathfinding for a soldier or a tank.
Figure 16. Part of a navigation mesh around the outside of the bunker
Here’s another example. Let’s say we have a soldier on a motorcycle. Unlike human soldiers, motorcycles can’t turn on a dime while they’re moving.
In the example below, it’s obvious that the motorcycle rider can drive safely from his current position to the room at the top (red line), but cannot turn into the hallway on the right since the angle is too sharp (orange line). Whatever pathfinding representation we choose should be able to figure this out, too.
Figure 17. A motorcyclist can go into the room at the top (red) but not the room on the right (orange)
With a navigation mesh, this is relatively easy to do. We just test the turn angles and distances as we’re doing the pathfinding and reject any paths that require steep turns over short distances.
With a waypoint approach, on the other hand, it’s essentially impossible. At a minimum, we’d need a completely separate waypoint graph for soldiers on motorcycles, since we can’t use the same graph that soldiers on foot are using. Adding an entirely new graph like that for every unit with different pathfinding capabilities gets very cumbersome.
5. They don’t have enough data to support what your AI needs beyond pathfinding.
AI search spaces aren’t just for navigation. AIs need to be able to use the pathfinding data to tell them how to move in the world.
A game character needs to constantly query the pathfinding system and ask: is it OK if I move here? How about over here?
Games are increasingly moving to animation-driven movement systems that give animators control over the position of game characters. That means that in order to know what the results will be if we play animation X, we need to figure out where the character will be when X is finished, and whether that location is inside a wall, hanging over a cliff, or in some other location the level designers don’t want him to be.
Here’s an example. The swordsman below has four moves: a left strafe, a right strafe, a backstep, and a big flying leap into the air that sends him up 20 feet and then has him land 8 feet in front of where he started.
Figure 18. A swordsman with four animations that contain translation
In order to make sure my swordsman doesn’t end up slamming into a brick wall when he leaps or strafes or backsteps, I need to test the predicted end position of each of these animations against the navigation mesh.
Yes, it’s possible to use your collision system to do raycasting. That will often give you useful information, and for dynamic physics objects in the game world, it’s usually the only way for AIs to find out about them.
But raycasting can be expensive, and when you only care about the static game world and not the dynamic physics objects, it’s faster and easier to query a navigation mesh.
Although I can use raycasting to tell me if there’s a wall between me and point (X,Y,Z), the collision system can’t tell me if the swordsman will land in a position that the level designers actually want characters to walk in … only a navigation mesh can tell me that.
If you’re still not convinced after all of that, let me try to address any remaining concerns you might have by answering common questions about waypoint graphs and navigation meshes.
Q & A
But isn’t it slower to do pathfinding on a navigation mesh?
Not at all. A navigation mesh is a graph, just like a waypoint graph is, and the core pathfinding routines are very similar. The difference is that a navigation mesh has a polygon associated with each graph node.
The image below shows the graph connecting the nav mesh polygons.
Figure 19. An illustration of the graph (red) underlying a navigation mesh
Whenever you run the A* algorithm for pathfinding, you’re always running it on some kind of a graph, whether it’s a square grid, a waypoint graph, a navigation mesh, or what have you.
In most cases, navigation meshes have performance similar to waypoint graphs. In cases where they cover the same area with fewer nodes (such as Figure 6), a navigation mesh can actually be significantly faster.
But don’t navigation meshes take a lot more memory than waypoints?
If done correctly, no.
Navigation meshes are a very simple and compact representation. In general, a nav mesh will only require a tiny fraction of the memory required by the underlying rendering geometry for the static game world. A navigation mesh is much smaller than a collision mesh, since it cares about fewer surfaces (it ignores walls, ceilings, and other unwalkable surfaces) and uses a smaller number of much larger polygons to cover a given area.
A navigation mesh tends to use a few more points for each graph node than a waypoint graph in the worst case. And in some cases, such as the town in Figure 6, a navigation mesh can actually be smaller because it’s a simpler representation.
Most of the examples you showed were role-playing games. Why don’t I see the same kinds of problems in first-person shooters?
The problems are still there in many first-person shooters, but they’re harder to spot due to the nature of the gameplay.
– Most AIs don’t live long enough to let you spot the flaws in their pathfinding.
– AIs will usually stop and shoot the moment they have line-of-sight to you, so their paths are a lot shorter.
– In many single-player FPS games, AIs don’t move very much, and will attempt to snipe you from a relatively fixed position.
– A lot of modern FPS games provide AI sidekicks who will kill the enemy AIs so quickly they don’t have time to move very far.
Here’s an example from Half-Life 2. With a little bit of experimentation, it’s easy to see that the guard on the stairs is locked to a single, linear waypoint path that runs directly up and down the center of the stairs. The guard still ends up looking competent since he can shoot at you whenever he can see you.
…视频连接已经无效了
When you take away ranged weapons and force characters to use melee weapons — as with some of the Covenant soldiers in Halo, the Icarus stealth assassins in F.E.A.R., or the Metroids in a Metroid Prime game — waypoint graphs are suddenly a much less attractive option (which is part of the reason all three of those games used navigation meshes instead …)
Look, I understand everything you said, but designers need to be able to put down cover points, patrol paths, and so on. That’s just essential for creating the AI in our games.
Of course! You can still do that, even if you’re using a navigation mesh.
The key is to separate the two representations. You use one representation (a nav mesh) for the pathfinding and navigation, and another (designer-placed points) tell the AI how to use the world.
A navigation mesh doesn’t prevent you from doing any scripting. It simply provides extra information for your AIs for when they need to navigate more autonomously.
Here’s an example. We have a patrol path (purple) for some guards patrolling around town and a special marker for an old man who likes to fish in the moat a few times a day (red). The cover points (yellow) represent points where characters could take cover around corners in FPS-style magic duels between the mages and warlocks of Stormwind City.