AI Follies: Pathing

By Shamus Posted Thursday Aug 20, 2009

Filed under: Programming 54 comments

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.
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.
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.
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.
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.

 


From The Archives:
 

54 thoughts on “AI Follies: Pathing

  1. bbot says:

    Typo in first image description: “Toady” -> “Today”

  2. gamercow says:

    Outstanding analysis, and it shows you just how much processing the human brain does any given second.

  3. Benjamin Orchard says:

    I will tell you that Warcraft 3 STILL had the same pathing issues as Starcraft when it came to blockades. Apparently this is difficult to solve.

    Despite that, I still think Blizzard does a good job with it’s AI in comparison to some of the other games out there.

    My frustration is when I design levels. I’ll build 2 levels, and one will result in an AI that can’t compete with human players AT ALL, and another will result in an AI that will trounce me almost immediately.

    And I can’t tell you what the difference is. Some of that is my problem as a level designer in Warcraft 3, but some of that is the AI.

  4. bbot says:

    L4D is a source engined game, and thus uses the “waypoint” model, which it calls “nav meshes”. The mesh editor is fairly smart about Just Doing what you want it to do using nav_mark_walkable elements, but the mapper still has to manually designate ladders, elevators, finale events, and suchlike. Whenever you see infected jumping to climb over a fence or jumping down from above, that was manually graphed by the mapper.

    The valve documentation on L4D nav meshing is here.

  5. Typo the second – Under point 3 of “Finding B” you’ve said rach not reach.

    Pathing is always difficult. Blizzard did a lot better with the warcraft 3 AI pathing.

  6. Hirvox says:

    Supreme Commander 2 is trying to solve the blockade problem by processing units as groups: If you order 10 units to go to point B, the a->b path is calculated only once. Of course, if there is a chokepoint in the way, this might lead into the units moving in a line (and getting shot one-by-one by the defenders) instead of regrouping after the chokepoint.

  7. Factoid says:

    My understanding is that many of these “which is better when” questions fall within the realm of “fuzzy math” which is why those two courses are usually required in any kind of AI curriculum.

    For those unfamiliar with the concept Fuzzy Math helps us describe concepts that have different answers when beginning with different starting conditions.

    The most basic representation of this is “do you feel warm or cold”. The answer to that usually depends on the current temperature, a person’s tolerance for heat and cold, their preferences and what previous temperatures they’ve recently been exposed to.

    A 40 degree day feels very cold in July, but it’s downright toasty in January (in cold northern climates, that is).

    So if yesterday was 40 and today is 60, today will feel warm, and yesterday will have been cold. But if today is 60 and yesterday was 80, today will feel quite cold in comparison.

    Fuzzy math is all about finding a set of values you can traverse to answer that initial question “is it warm or cold”.

  8. Maddi says:

    @bbot: Judging from the picture in your link I’d say its navigation mesh rather than Waypoint net which is a bit better since it does not directly tell the ai where to walk, but where it can walk. I recently read an article about the differences but don’t have a link handy atm.

  9. Mr. Son says:

    There’s a great article here on pathfinding and a better solution to waypoints, if you want to read someone else’s thoughts on the matter.

    In case my link is borked, here’s the address:
    http://www.ai-blog.net/archives/000152.html

  10. Neil says:

    Oh, Unreal Tournament navigaion points. That brings back memories. Mostly ones of cheating.

  11. Henebry says:

    Mr. Son: thanks for the link. Interesting to discover just how different that writer’s account sounds when contrasted with Shamus. A professional working in the industry, he’s writing to provide a system that he regards as the solution to AI pathfinding. Shamus, by contrast, regards AI as a problem that hasn’t been solved.

  12. Peter H. Coffin says:

    What probably would help the footlocker and kitchen counter situations is to use waypoints, but weight the paths between them, which includes some assortment of factors like distance, difficulty, time, hazard, and the path to destination is the least sum of the weights of the paths. Your entire simplification gets kind of tied to limiting the number of waypoints, and one loses a little flexibilty by not being able to stop between waypoints, but if you’ve got the cycles to rerun the pathfinding while moving, you can fix the Starcraft problem in the caption by having the moving unit change how it’s getting to the top once the blocking unit has moved away from the chokepoint.

    1. Shamus says:

      Peter H. Coffin: Re-calculating the path (which is done sometimes in some games) can help, but can make an even bigger mess. If you’ve got a line of (say) tanks waiting to go up the ramp, the first one slows down, which makes all the others re-route. The second wants to back off, but the third is blocking him. The third breaks to one side, heading for the alternate route, and the fourth keeps rolling forward, not having bumped into the logjam yet. Number two is then free to come down the ramp one continues up the ramp, four comes forward and bumps into two, who is again stuck. Now you’ve got a clear ramp, a guy blocking it trying to go down, a guy bumping into him going up, and #3 off to the side, now turning around because the path opened up again for a second.

      And a player shouting at the computer: WHAT ARE YOU IDIOTS DOING!?!?!

      1. Shamus says:

        Addendum: You can re-create the above madness in Starcraft by selecting some tanks, clustering them, and then repeatedly right-clicking at the top of a ramp. It’s interesting the different sorts of stupidity you can get by changing the speed at which you click. (Try once a second, try once every three.)

        Disclaimer: I remember doing this a couple of years ago. No idea if this still works, post patch, or even if I had the latest patch at the time. Still, I doubt they overhauled the pathing.

        EDIT: DUH. It should just work fine if you don’t patch it first. Stupid brain.

  13. MelTorefas says:

    You wrote “Back in the day, Unreal Tournament way a waypoint game…” The “way” should be “was” there. I only point this out because it was kind of confusing reading through this sentence at first.

    Another great AI article. Are you planning to continue these much longer? I’m loving them. :)

    Ramps in Starcraft were SUCH a pain in the ass. But to me they pale in comparison to the vehicle pathing problems in Dawn of War. In that game, infantry units are trained and given orders as squads, not individually. When vehicles and infantry squads are going the same way, the vehicles generally move faster (realisticly), and when one is coming a squad will move out of the way to let it pass (also realistic).

    The problem comes when this happens in a narrow area, even one that wouldn’t count as a chokepoint for the infantry alone. The infantry squad members scatter to the sides to let the vehicle pass. But there’s just BARELY not enough room for it to get by. The vehicle comes to a stop, causing the infantry squad to begin moving forward again… except the one or two members who are “caught” on the vehicle. With one squad and one vehicle you can end up with most the squad off fighting, and a single member trapped BEHIND the vehicle, which in turn is somehow unable to begin moving forward because the infantryman is “too close” and can’t move to get far enough away.

    With multiple squads and vehicles, you get a giant retarded nightmare traffic jam of death.

  14. Drew says:

    Let’s not forget that a really clever AI would recognize that sometimes the best movement option would be to stay still, since it would recognize that the player was likely to move into a compromising position. The simple example is a player and an NPC on opposite sides of a wall, with a doorway in the middle. If the NPC runs into that doorway where the player is no doubt aiming, he’s toast. On the other hand, if he knows the player wants to eventually come through the door, he can frustrate the heck out of him by simply holding his ground. Now, if he hears allies attack the player on the other side of the wall, the risk/reward situation changes, and he may be best served to charge through that doorway, assuming the player is otherwise occupied and therefore likely to be a good target.

    It ain’t easy.

  15. LintMan says:

    I’ve spent some time thinking about the “Zax” problem and ramp clogs, also. Or even when you select a cluster of units in an RTS and send them somewhere and they can’t get out of each other’s way. I think part of the solution would be to institue some level of “communication” between AI entities.

    So when one unit is being blocked by another (allied) unit, it “asks” that unit to move. The blocking unit would take the request and generally try to get out of the way, or if it too was blocked, would pass its own request to its blocker. If some blocking unit was unable/unwilling to move, it would pass back a rejection message, and the blockee would know to go around.

    Of course, there’d need to be some level of priority handling of who should yield to who, and also a bunch of situational logic about what “get out of the way” means in that circumstance, and whether that is acceptable according to its orders. But overall, even a partial implementation of this would help out a lot, I think.

  16. Johannes says:

    How about having some engine ‘compile’ level metadata into the level? This way, you can make your algorithm as advanced as you’d like, because the generated path info will not be calculated in real time but is stored in a set of what-have-you-nodes on disk. You could include some kind of on-the-fly metadata as you’re developing & testing the level, and make it a big compile job whenever you’re finished (or want to test the AI).

    Now I haven’t been designing levels since Doom, which required something called BSP to be compiled from the ‘level source’ (as did Quake). How are levels modeled nowadays? If some kind of BSP like structure is still required, compiling ‘AI navigation metadata’ probably wouldn’t add too much overhead anyways.

    Just thinkin’. And no, not willing to write a program to prove my point. ;)

  17. Lochiel says:

    Shamus: It seems that an assumption AI writers are making is that the AI Pathing can find the optimal solution in all cases. But its been my experience with players that it takes a very very skilled player to always find the optimal solution.

  18. Deoxy says:

    “Optimal” is, in many cases, impossible to know for sure, since it depends on the behaviour of other actors in the area (from both teams), so we’re not really after “optimal”… we’re after “reasonable”.

    Another good article, Shamus.

  19. KarmaDoor says:

    As a clarification, the system in Unreal Tournament is refered to as pathnodes. That helps to disambiguate it from waypoint which, in gaming, usually refers to either a place the player’s character will start back at when killed or points that allow the player to teleport between them.

    And now for an insanely good “A.I.” tech demo :
    AMD’s The Froblins

  20. KarmaDoor says:

    *sigh*
    Of course I didn’t get the link to start the video at 6 minutes, 49 seconds. I wish YouTube would just add the specific features in as opposed to having to hack a URL together.

    This might work :
    Froblins A.I. excerpt.

  21. Matt K says:

    Another good one I’ve loving this series. The sad part is that I can actually place which level each UT screen shot is taken from (but I only own that one and played the hell out of it for years).

    For the footlocker scenario, perhaps having some adding in some sort of “DON’T STEP/CLIMB HERE” would work so it would add a mesh design but only as a negative limitation.

  22. Scott M says:

    “I tell my Ultralisks (blue things) to go up the ramp.”

    Well there’s your real problem. Ultralisks? Just use three queens to broodling the tanks and you’ve got a relatively undefended base to deal with.

    But I digress. Very interesting series–keep it up!

  23. The Stranger says:

    For some reason, the bit about footlockers and other “social” obstacles (social in that we’re phsically capable of going over/under them but the societal norm is to go around) inspired me to nitpick. For me, at least, all of that would go out the window if I found myself in a gunfight. In that scenario, I’m going to jump over beds, under tables, whatever gets the job done. A bot running around to the other side of the waist-high deck and up the two steps to reach an opponent he could reach almost instantly by just jumping onto the deck is going to look almost as silly as the one that crawls under the table to get a beer out of the refrigerator.

    So now your AI, in addition to everything that’s already been mentioned, needs to consider its level of alertness in its pathing decisions – one set of behaviors when it’s just going about its daily business, and another set when it’s in a combat situation.

    I’m very glad I’m not a programmer.

    1. WJS says:

      That’s all trivial. I’m pretty sure Shamus is out of his area here; a lot of what he presents as insurmountable problems are in fact very easy to solve. In this case, all it takes is keeping track of if a bot is in a hurry or not, and having two pathing costs for obstacles; one for “unhurried” which would only jump, climb, or vault if it would save a lot of time, and one for “hurried” which would rate obstacles based strictly on how much they would slow it down by. Plug these costs into a standard pathing algorithm, such as A* (almost 50 years old now), and your bot will behave in a sane manner.

  24. Carra says:

    Well, only a few programmers are AI programmers. Most do simpler stuff ;)

    I was thinking about a backtracking algorithm to do the first maze.
    -Pick a random direction and go to it. Scratch that pick.
    -Repeat
    -If there is no way to go to on a tile, go back one ore more steps until you do have another choice. Pick that one and continue.
    Should find a route if there is one.

    I’ve always found AI to be a fascinating subject. And yes, these problems do not have a best solution. I have dabbled a bit with genetic algorithms which are a good way to find a “good” solution (shortest path among x places for example). Any of these being used in AI?

  25. Tacoma says:

    As for hopping over obstructions instead of going around, I think most people use this: the AI chooses a number of possible paths. It assigns each path a quickness value. If the AI is averse to crawling over things, it will assign a higher walking penalty to crawling over a footlocker than to the sum of the distance walking around it. A zombie would have no aversion to climbing, while a diplomat certainly does. Yet if there is no other way around, or the way is very far (low fence vs. walking all the way to the gate) he will hop the fence.

    The good AI will then note where his enemies are, and assign them danger radii and danger levels. A path that crosses through a danger radius will be assigned a danger penalty to the quickness rating. An enemy with high radius but low danger (a man throwing rocks) will interfere slightly with a lot of paths, while an enemy with low radius but high danger (a swordsman or zombie) will create a bubble of no-pathing around itself but in total will affect few paths.

    Cover deforms danger radii by reducing the danger level (for weapons that can penetrate that barrier) or blocking the radius (a wall).

    As for the starcraft blockage frustration, how do we humans cope with this? We wait a few moments and if the dude isn’t moving, we might go around. But if going around means a huge detour we’re more likely to wait.

    So a smart AI would have to weigh the difference between the detour path and the probability that the tank in front will move soon. If that tank has stopped and is mired in the soil, or it’s been destroyed and there’s a hulk there now, the chances of it moving become slim and any detour becomes attractive. But if it’s just halted for a moment and begins moving immediately, the detour selection routine shouldn’t have gotten past its pause yet. People need to take a moment to make up their minds, and AI should too.

    1. WJS says:

      That’s pretty much exactly how pathing over irregular terrain is done. Your “quickness” number is typically known as the “cost” of a node, which makes sense because the things we’re trying to stop the bot from doing (climbing over things) would probably be quicker than going the long way around, so “quickness” doesn’t make much sense.

  26. UTAlan says:

    Shamus – This is not related to this post, but…did you know that the HOME link in the top nav doesn’t take you to the home page, but reloads the current page? Just thought I’d point that out in case you were unaware.

  27. bbot says:

    This reminds me:

    One of the commentary nodes in Portal was how the physics engine and AI aiming algorithms had to be extensively modified to deal with the player putting holes in walls, and even then Portal only implemented a subset of Narbonic Drop’s features, in that you couldn’t place portals through portals, and instead the portal orb would smack into the invisible wall.

    And Portal only had stationary enemies, with classic robotic long range aiming skills. No wonder Episode 3’s taking so long.

  28. bbot says:

    @8:

    Yes, it is slightly more flexible than a pure waypoint system, but it still is hand-generated and pre-compiled. It is not the fully general AI pathing system described by Shamus.

  29. Rob Maguire says:

    I’ve worked a bit with pathing AI while configuring bots in the nineties, and making Neverwinter Nights campaigns in the, er, zeroies…

    I hated every minute of it. I’m glad there are better programmers than me who can tolerate that sort of stuff. I tip my hat to you.

    As for risk analysis, don’t many of the modern game engines send detailed death statistics to the server, which is compiled into maps? I know Valve releases these for both single- and multi-player, and the CryEngine 3 tech demo made it out to be a major selling point to publishers, at least. Couldn’t the AI use these as their risk analysis? Simply avoid red zones excepting short sprints to grab items, and not even have to recognize cover anymore (the safe side of good cover will be green).

    It’s instantly up-to-date with any new map exploits found, shows points where the AI needs to be manually tweaked (assuming the map differentiates between AI and players), and is a form of DRM that might actually work – you have to log into the official servers to get good AI.

    Of course, player-made maps would be a problem. Meh.

  30. Blake says:

    Mr Son:
    That article on AI-Blog was quite interesting. Certainly allows a good level of abstraction.
    It also looks like it’d be easy to extend for say the jumping over desks issue by being able to define certain polys with an extra penalty (probably showing up as a different colour in the editor) where you could say ‘this poly takes 3X the normal time to cross’. This would allow the AI to easily determine optimal path while working within the A* system.
    You also then specify if those have no extra penalty for flying creatures to stop those trying to go around.
    Could also fix the “zombie would have no aversion to climbing, while a diplomat certainly does” issue Tacoma mentioned by having the diplomats AI ignore all polys with a cost greater than X.

  31. Tuck says:

    I found the enemy soldier AI in Crysis to be quite fun (and somewhat intelligent, if a little too farsighted in some places).

    In a thick jungle situation they were very good at sneaking around, using cover, lobbing grenades to where they THOUGHT you were (invisibility gets them completely confused), etc.

    On the beaches they liked to hide behind big rocks, but you could generally pick them off from quite a distance when they moved around.

    Their pathfinding in all those situations was very good. From what I understand of the engine it’s generalised and somewhat procedural, and even when you can completely change some environments (knock down trees across roads, blow up buildings, etc) they still manage to act intelligently.

  32. thegrinner says:

    I wonder if anyone’s considered using the various hotspot player location maps to dynamically establish a waypoint grid? Say every location that gets a certain amount of travel density in radius r receives a waypoint. Not perfect, but a lot less work on the hands of the coders and I would think it would seem more humanlike after a while.

    Of course, I’m sure I’m forgetting or missing something about how it works.

  33. equinox216 says:

    My initial thought on solving the “Jerks on a Ramp” scenario would be to make units selected in a group not just have their orders delivered to the group and then implemented individually, but to think of their orders as a group. Give them their own little L4D director, as it were. At its most basic, the director wouldn’t step in until it recognized a common pathing trouble hotspot like the dreaded bottleneck (ramp, valley, etc.) was coming up because of the player’s selected destination, and then would coordinate the orderly procession through that point.

    Through reading this post series, it’s really become clear how many traditional AI “solutions” through the years have been single-layer, and could be greatly improved by a second layer of management AI. Simultaneously neat and sad.

  34. equinox216 says:

    Actually, now that I think about it, I just finished playing a game that demonstrated a deep need for that kind of group pathing manager: Little King’s Story (on Wii), which I can best describe as “Chibi Overlord”.

    There were three ‘formations’ which your citizens would follow you in: attack, guard, and evade. Attack involved ranks behind you, that would swing around in some really silly ways to make SURE they would stay behind you. Guard was a polar graph scatterplot, basically a mobile surrounding spiral centered on you. And Evade was follow-the-leader. You NEEDED Evade, simply so you wouldn’t orphan citizens against buildings or objects (a fate from which there was no return unless you doubled back and gave them a straight A-B path), or lose them off a short unclimbable drop or have them fail to recognize a narrow ramp as ‘time to bunch up’. There was a very VERY minimal bunching reaction, that ended up being totally insufficient for anything it was apparently there to help with.

  35. Maldeus says:

    This is unrelated to the actual post, but I’m glad to see the Overlord/Pikmin mechanic taking off. It’s pretty fun to play with.

  36. Martin Annadale says:

    Good series of articles. I’ve always found AI fascinating. My favorite two villains of all time are HAL9000 and Shodan. But anyway…

    The pathing AI in Starcraft was a bit off, but many fans of the game (including me) will tell you it is one of the things that gave the game such a steep skill-curve (which is a good thing for a e-sport). Player A with modest to good strategy skills will do what you did and simply send the two ultralisks up the ramp. Your strategy was sound, getting them up there and within the “safe” range of the siege tanks is their best bet. But due to the rather limited ai, one ultraliks takes the long route, and chances are you either lose 1 or both and the attack is either a failure or just not efficient.
    Player B’s been playing Starcraft a lot more and manually guides up both ultralisks with many clicks of the mouse. Siege tanks are devoured and the Swarm take over another planet. All for the glory of the Queen of Blades of course.

    Basically it creates a situation similar to what you described a while (or a long time) ago about the skill curve in first person shooters. Where the less skilled player loses and doesn’t even understand why. This can be frustrating for the newer player, but its basically essential to have this quality in any game that is to played competitively.

    And I’m not saying I want Starcraft 2’s AI to suck as well. My hope is that the AI will be much improved, but that they’ll add other layers to give the game that “I don’t know why I lost” edge.

    1. WJS says:

      If any of that was true, we’d see competitive Dwarf Fortress.
      – Steep learning curve
      – Requires stupid micro-management
      – You lose and have no idea why
      Frustrating your players for no good reason is a bad thing, and there’s no justification for the assertion that it’s somehow “essential” in a competitive game.

  37. Martin –

    fair enough, but some of us just want to play games for fun. And then this kind of stuff frustrates the hell out of us…

  38. Greg says:

    There’s also the whole field of battlefield prediction they’d need to manage. You touch on it talking about the danger or taking ages to reach a spot and the battle being over by the time you get there – but to be truely effective an AI needs to analyse each node for how useful it will be by the time it gets there – not only on the basis of whether the battle will be over, but also whether any of the other actors will move. When one of thsoe actors is a player and not an AI it can cheat and know the behaviour of.

  39. equinox216 says:

    Maldeus@37: Yeah, and in Little King’s case, it was adorable (even if the gameplay wasn’t all that great). While I liked the Overlord goblins, my wife wasn’t fond of them. Said they looked like plucked chickens.

  40. decius says:

    For the footlocker/desk/fence issue, why not assign ‘polite’ penalties to stepping on things, vaulting objects, and other rare behaviors. When in normal movement, actors will tend to avoid those actions (except when the alternative is longer than the penalty), but when under fire, they will ignore the penalty and dive over the desk to take cover behind it.

    Still, recognizing that crouched behind the desk is a good position to throw grenades is a problem for one more experienced than I.

  41. Inquisitor says:

    Here’s how I would do it. Start off with the first pathfinding option. However, weigh each possible path based on the amount of “effort” it would take to get there. For example, moving across a flat plane takes less effort than climbing a hill or taking some stairs or hopping over a counter or ducking under something. The more effort it would require, the higher this weight is. Then, it chooses the path with the least weight. Maybe you could also have it consider things like, “can the player see me right now?” and if it’s an enemy, it might take the sneakier/less dangerous path where it thinks you can’t see it. You could use similar logic for other treats, like giving a wild animal a wide berth.

  42. Joel D says:

    I have a minor issue with some of your images – when you use the word “duh” with an arrow, it makes me think “this is the obvious, correct route, duh”. If you used “durr”, I’d be a lot less confused.

  43. wererogue says:

    For “geometry analysis” see “navmesh” – basically, you precompute a mesh which is only used for pathfinding. Then, you remove areas which have impassable objects – like your footlockers and kitchen islands.

  44. guy says:

    here’s a nice video showing off the halflife 2 AI using a top-down camera.

    http://www.youtube.com/watch?v=uWYlMC8z0G8

    Probably the most impressive part as a technical aspect is towards the end, when the Combine forces take cover next to a car, which is now a valid cover position and wasn’t previously. So the AI does in fact calculate cover on the fly.

    Ironically the top video in the related links section is a video of someone taking advantage of the spawn-in animation and claiming that as poor AI.

  45. me says:

    After extensive studies (graphing the worn out places in the dorm carpet) I have determined that people use the absolute lowest energy path when they are unstressed. When in danger I presume this would change to the quickest.

  46. mystran says:

    Replying to old post (sorry), but Q3A actually uses sort of best-of-both-worlds pathing, where there’s a compiler which analyzes a map, essentially inserting waypoints automatically (into a separate navigation file) such that bots can reach any interesting place (basically anything with items IIRC). So you end up with something that, as far as I understand, is essentially waypoint planning, attractors (to reach a waypoint) and some additional rules like here is a sensible place to jump down, this jump pad takes you there, here you can rocketjump to reach that platform (though at least in QuakeLive there’s a cvar to set whether bots attempt to rocket jump at all; not sure about the original), etc.

    There’s reasonable amount of info about the Q3 AAS AI on the web, if anyone wants to know more about it.

  47. Blue_Pie_Ninja says:

    ” expected to to the “smart” thing”

    I’m pretty sure its meant to be “expected to be the “smart” thing” when you talk about the zombies.

  48. WJS says:

    I know Shamus sometimes reads comments on old posts, so I’ll post this here.
    I don’t know if you’re making it seem harder than it is for dramatic effect, or if you’ve stepped outside your area of expertise here (graphics, IIRC?), but a lot of this stuff is pretty simple really. The queueing problem I’ll give you, but the rest seems pretty trivial. Pathfinding is an area of continuing research, sure, but the basics have been solidly understood since before either of us were born. It’s not a matter of how to do it, it’s how to do it best. For example, if your gamespace is a twisty maze, Dijkstra’s algorithm would probably do just fine. If it’s an open plain with a few obstacles then A* would be considerably faster (although Dijkstra would get there in the end).

    The problem under “Finding B” is trivial to solve too; simply give exposed areas a higher cost than areas behind cover will naturally cause your bot to take the safe route, and you can change how much more expensive to make exposed areas based on it’s health. You could vary it based on how strong the player’s weapon is too – there’s a lot of potential complexity here, sure, but it’s tweaking, rather than problem solving.

    If you already know all this and this was just for dramatic effect, I’m sorry if I sound condescending, but given how interesting this subject is, I felt I had to take that risk.

    1. Daemian Lucifer says:

      Its only that trivial when you are dealing with simple nodes connected with simple paths and you are just trying to get a dot through them.But in a video game,its much more complex.What is a node in a fully rendered 3d corridor with bunch of clutter in it?Will the ai be afraid of puddles or try to get through walls?Doing it best does not mean simply optimizing the algorithm to use fewer resources,it means connecting it with your collision detection code,and running it an optimal number of times between frames,and meshing it together with other ai routines(fight or flight,player detection,etc).The more complex your environment,the more complex path finding becomes.

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply to Benjamin Orchard Cancel reply

Your email address will not be published.