 <\/td><\/tr> | ||||
| 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.<\/td><\/tr><\/table>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<\/em> this. <\/p>\n 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.<\/p>\n There are a couple of approaches to navigation:<\/p>\n 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<\/strong> 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…<\/p>\n 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.<\/p>\n 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.<\/p>\n Finding B<\/strong><\/p>\n 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.<\/p>\n Making things worse: If the AI needs to lob<\/em> projectiles at the player rather than simply shoot<\/em> 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. <\/p>\n Dealing with Blockades<\/strong><\/p>\n |
<\/td><\/tr>
<\/td><\/tr>
<\/td><\/tr>