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.|
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.|
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.
|Once you find B, you still have to plan a sensible route to get there.|
- Examine the battlefield and find every place I could stand and get a shot at my target.
- Disregard ones that are already occupied by allies.
- 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.
- 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.|
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:
- How advantageous position is.
- How long it would take to get there.
- 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.
So what happens when a SOFTWARE engineer tries to review hardware? This. This happens.
A video discussing Megatexture technology. Why we needed it, what it was supposed to do, and why it maybe didn't totally work.
Video Compression Gone Wrong
How does image compression work, and why does it create those ugly spots all over some videos and not others?
Shamus Plays LOTRO
As someone who loves Tolkein lore and despises silly MMO quests, this game left me deeply conflicted.
Zenimax vs. Facebook
This series explores the troubled history of VR and the strange lawsuit between Zenimax publishing and Facebook.