T w e n t y S i d e d

Pathing (or path finding) is the process of getting some AI controlled entity to move from A to B. It used to be that when people said “AI” they meant “pathing”. The two terms were synonymous, because pathing was the only intelligent thing you needed the game to do. We’ve come a long way and we need a lot more from our AI than just a trip planner, but the need for pathing is still there and it’s still a challenge.

Getting From A to B

Green: Optimal route. Red: The area you would cover if you were to use the “stick to the right or left wall” logic of navigation. Woefully inadequate by today’s standards.

We’ve needed AI entities to navigate a complex environment for well over twenty years so this is not new territory. It’s not trivial to write code to do this, but it’s a fundamental task and there is an expectation that any system you write should be able to do at least this.

While most game enviroments aren’t quite as complex as a real maze, they might as well be. They still have places where you can’t use a simple attractor. (An attractor would be where the AI will simply run towards the goal.) There will be room layouts or topography where you need to go south a bit if your ultimate goal is to the north. Solving this is, in practice, the same thing as finding an optimal route through a maze.

There are a couple of approaches to navigation:

1) Geometry analysis. The program has to analyze the geometry in the room, deciding what areas are passable and what the sensible routes are. This can get to be really complicated. Remember that AI doesn’t understand “furniture” vs. “hallways”. It’s all just “shapes” to the AI. It sees the shortest-distance path across the room requires it to go up a step, then down a step. Except, that “step” is actually a footlocker, and people usually walk around those. Humans can skip the two-step flight of stairs and hop up onto a deck or porch, but we usually take the stairs. On the other hand, we’ll hop over a low fence or wall on the edge of a field rather than go around. But I won’t jump over a similar-sized “wall” if it’s actually the countertop island in the middle of the kitchen, or the dining room table. If I walk around the yard, I walk on the level parts, and avoid the awkward feeling of traveling horizontally across the face of a hill. I’ll generally avoid walking in paces where I have to duck, and I walk around desks rather than crawl under them. It becomes very hard to make the AI choose the right thing without a few hints from the level designer about whether this bit of geometry is a thing to be walked around, through, climbed over, or avoided. Which brings us to…

The waypoint-based pathing in Unreal Tournament. The level designer has placed nodes (the little apple or peach icons) around the level, and they were then analyzed and linked by the software to construct this system of routes around the level. When the game is played, AI’s will travel along these routes.

2) Waypoints. These are invisible markers set around the level by the designer that define the possible routes. Generally, every bend or every intersection will have a waypoint. The AI can stand at one waypoint and look for another, or plan a trip through several waypoints. This turns navigation into something very much like a Google Maps-type trip planner. Waypoint-based navigation is much less work for the programmer, but it’s more work for the level designers (who must place them) and it makes the AI a little more rigid and mechanical. Waypoint-based bad guys tend to follow the routes tightly, which makes them very predictable and exploitable. If you can reach a spot where the level designer didn’t think to put a waypoint you can confuse the AI, possibly exploiting it and unmasking its stupidity. You can fix this by having the AI leave these “rails” as needed, but the more they leave the rails the more generalized geometry analysis skills it will have. If you want them to be really flexible and adaptable, you’ll basically end up writing both systems.

Generalized systems are much harder to author. (At least, I think they would be. It might not be so bad for general “deathmatch” arenas, but the more realistically cluttered the environment is, the harder this will be. I’m still curious how they handle the “footlocker” problem in some of these games.) But it has the advantage is that your level designers don’t end up wrangling with AI and can focus on design. Back in the day, Unreal Tournament way a waypoint game and Quake III Arena was a generalized game. I don’t know that I could say the bots in one were better than the other at getting around.

I’m pretty sure Left 4 Dead uses a generalized system and it seems to work really well. The zombies climb all over the insanely complex debris-strewn topography with ease. Then again, they can get away with climbing over furniture. They can take the direct-line route and aren’t expected to to the “smart” thing when crossing the room.

Finding B

Once you find B, you still have to plan a sensible route to get there.

It’s no good being able to go from A to B if B itself isn’t a useful location. If this AI is trying engage the enemy in melee combat, figuring out B is fairly straightforward: B is the position of the player. Now go hit him. But if the AI is trying to shoot the player, then this is a complex question. In an open field, there will be hundreds of possible vantage points from which you could shoot at the player, but only a few will make any sense. Now instead of trying to reach the player, you must:

1. Examine the battlefield and find every place I could stand and get a shot at my target.
2. Disregard ones that are already occupied by allies.
3. Now rate all of the points according to the criteria: How long it will take to reach the point, how much cover the point provides, and how dangerous the route is to reach it.
4. Note that there probably isn’t a “best” one. It’s all a bunch of tradeoffs, with the importance of each attribute varying on the situation. (For example, if the AI is low on health it should rate dangerous routes very low.) Good luck with that.

Before Half-Life 2 came out there was a preview gameplay demo floating around the net. One of the most sublime moments in that video for me was the point there the player blocked a door with some furniture and the Metrocops ran to a nearby window to get a clear shot at the player. Another moment that amazed me once I had the game was where the Strider fights the player in a parking garage. The Strider is brilliant at moving to the right spot and then crouching to the right level to be able to get a clear shot. Both of these are complex problems to solve, and the game handles it very well.

Making things worse: If the AI needs to lob projectiles at the player rather than simply shoot them. This is a great way to induce weeping and gnashing of teeth for your AI programmer. Now the pathing needs to make sure that B is a location with enough overhead space to allow for any of the useful firing parabolas. I have yet to see a game do this properly. Generally, the projectiles simply pass through obstacles or (more commonly) the bad guy will stand there like an idiot and mindlessly heave projectiles into the obstruction.

Dealing with Blockades

The classic Starcraft frustration. I tell my Ultralisks (blue things) to go up the ramp. The first one gets hung up for just an instant as it brushes a marine aside. But! As soon as it stops, the second one sees the route up the ramp is blocked and immediately heads for the alternate path, taking a needless pounding from the units above along the way. If #2 had just waited for a moment, the two could have gone up the ramp together. The very worst was trying to get three or four siege tanks up a single ramp, which would result in a horrifying mess.

Two enemy soldiers want to shoot the player, who is hiding in a building. Soldier A kicks open the door, stops in the doorway, and begins shooting. Now, Soldier B is standing behind him, still outside. What should he do? Stand in line waiting for his turn? Abandon his teammate and use a longer alternate route? The answer, annoyingly, is “it depends”.

When an AI needs to pass through a choke point which is blocked, the resulting decision is infuriatingly difficult and complex. It has to be able to appraise how long this traffic jam is going to last. A second? Several minutes? Has the guy in the doorway just stopped for a moment or is he pinned down by gunfire? (Or worse, does he want to retreat out of the room, and now you’re in the way, and the two of you are now stuck like the Zax.)

Once you have some sort of guess as to how long the logjam is going to last, you’ll have to weigh it against the time it will take to run the alternate route, which is itself a bit of annoying guesswork and approximations.

Putting it all together

This is where things go wrong. The AI looks at the battlefield and sees six locations where it can shoot at the player. Each location needs to be weighted according to these criteria:

1. How advantageous position is.
2. How long it would take to get there.
3. How risky the trip to that location will be. (This is very subjective. A momentary dash over open ground is okay, but prolonged exposure in the open should be regarded as suicide.)

All three of these variables are very hard to judge, and harder still to balance against each other. (For example, a healthy AI can afford a little risk, while a severely injured AI needs to take into account that any further injury will probably be lethal.) It’s no good heading along a safe route to reach an optimal vantage point if the battle will be over by the time you get there. It’s stupid to bolt for a great location if you’re just going to get cut down on the way. It’s not good risking life and limb for a position that will only be slightly better than your current location from a tactical standpoint.

Shamus Young is a programmer, an author, and nearly a composer. He works on this site full time. If you'd like to support him, you can do so via Patreon or PayPal.