Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

[crossposted from stackoverflow]

In a game such as Warcraft 3 or Age of Empires, the ways that an AI opponent can move about the map seem almost limitless. The maps are huge and the position of other players is constantly changing.

How does the AI path-finding in games like these work? Standard graph-search methods (such as DFS, BFS or A*) seem impossible in such a setup.

share|improve this question
1  
Why would A* not work in this graph? –  user712092 Jul 30 '11 at 5:58
    
Related blog: ai-blog.net/archives/000152.html –  tenfour Apr 16 at 7:27
add comment

7 Answers

In most cases, using A* over a navigation mesh (commonly referred to as a "navmesh") is the pathfinding solution commercial RTSs use. There is a detailed explanation of how navmeshes work, why they are a better solution than waypoint systems, and links to implementation resources, here.

If you're planning on developing special game modes (point/node capture) or units that patrol, take cover, etc., you will probably want to implement a waypoint layer atop your navmesh, to control AI behavior (not pathfinding).

share|improve this answer
add comment

Check out the Flowfield algorithm used in Supreme Commander 2. It does a much better job than most RTS pathfinding systems do (skip ahead to 0:50 for a few examples.)

share|improve this answer
1  
that is a really cool demo but tells me nothing about the implementation itself –  ioSamurai Oct 30 '10 at 19:14
3  
They mentioned in one sentence - it's based on UW's crowd flow research, which you can find at grail.cs.washington.edu/projects/crowd-flows. –  user744 Oct 30 '10 at 20:20
    
The flowfield algorithm seems pretty interesting, and definitely seems to do a much better job of pathing than most algorithms, but I wish there was public documentation on how the system itself worked, not just how the system it's based on works. Naturally, there are a lot of questions developers should ask before implementing a core system like this, but, in this case, it seems the only way to answer those questions is to implement the system first. :( –  Ari Patrick Oct 31 '10 at 17:37
1  
@Kragen: You really only need two units before plain A* (especially waypointed) causes them to bump into each other over and over, and you need some kind of system to work around it. –  user744 Nov 1 '10 at 21:46
3  
Based on the video, Starcraft 2's pathfinding looks like this. Does SC2 use flowfield? –  Chris Bui Nov 8 '10 at 3:44
show 2 more comments

Many older games do use A*. The original Starcraft used A*; which led to some problems in dealing with collision. Starcraft 2's handles collision very well, using a swaming/flocking behavior to maintain fluid control of large groups. This gamedev article discusses how this might be being achieve.

share|improve this answer
add comment

I agree upon the other answers her already, but also, try to think of WoW/Warcraft3 as actual 2D worlds. They arent that different from tilebased, its just the tiles.

You could also think of how does a GPS find the best path? there a loads of algortimns for pathfinding through linked maps.

I think some of the first "Quake bots" scripts also might help you, as they were developed to work in "unknown areas" because we could design our own levels from scratch.

All in all, my personal way to deal with such a map, would be to think of it as the A* pathfinder. But first I would pre-calc every "tile point" and index all these with "nearest neighbour" etc. Then when an object needed to go from A to B then just lookup in B, see to what its connected and keep repeating until you reach the goal.

Depending on the type of game and landscape/scenario, different pre-scan tactics might be usefull too. Some games have very little obstracles and these can be "streight line" movement + some "how do I get around" for objects.

Hope this makes a little sense and perhaps gave you some thoughts to work with.

share|improve this answer
add comment

Most games do use some sort of Search Algorithm or A* to find paths on a map. The AI is tweaked in some aspects obviously for performance reasons.

You will notice this in Starcraft 2 where Zerglings obviously don't path well at all, it would be a CPU nightmare to do that for Zerglings. They just do there best to get from A to B and don't even attempt to find the best path. They will get as close as possible then bottle neck at the chokes or ramps.

share|improve this answer
add comment

I'm totally not experienced, but I think that a good solution is based on heuristics, not on a complete checking of the known map. Heuristics I can think of are locally based and experience based. Local controls can be based on local terrain check and obstacles, keeping moving toward the required direction. I think that most maps don't require complex maze-like movements, but are pretty connected. Another heuristic is to use previous known paths (explored by other units or explicitly by the user) to move units to known or near-known positions. But I'm talking about moving on big maps, not really in closed spaces like ZorbaTHut said. In crowded cases the algorithm may be more complex, requiring sorts of "prediction", coordination among units of the same team or just semaphore-like waiting strategies. Also, note that continuous or discrete terrain and unit size calculation are really important when working on this case.

I think heuristic algorithms are good because they usually provide a good solution on big spaces with a reasonable computation time (which does matter, when you're moving many units).

Sorry if this a generic answer: I worked with crowds, but the space was pretty peculiar and I can't explain exactly how the algorithm worked (was agent based, anyway, not globally defined). I hope you can get some useful ideas from my answer.

share|improve this answer
    
Mmmh I wonder what was wrong in what I said... Was too hard to put down a comment? –  AkiRoss Nov 3 '10 at 22:19
    
BTW, I'd like to highlight that A* uses heuristic approach. Thanks for the -2. –  AkiRoss Nov 3 '10 at 22:23
    
Your answer amounts to, "Ditch A* and its ilk and roll your own". That can be the beginning to a reasonable answer but you provide very little info other than the suggestion. It think the reason for down voting is you don't make it clear how difficult your solution would be to implement. I do not doubt that a super genius given unlimited time could hand code/tune a pathing algorithm for a given RTS that would be superior to A* on a navmesh. But "genius" and "unlimited" are very hard to come by. –  deft_code Nov 24 '10 at 18:10
    
Oh... Right. I thought that the guy wanted a generic answer, since he didn't ask how to make one, but how do they work in general. Anyway I'm not an expert as I said: I was just giving some info about the solutions I know about exploring large spaces in a general IA application. Thanks for your comment. –  AkiRoss Dec 1 '10 at 10:59
add comment

Map is a grid. Grid is a graph. A* works on graph, it is a graphs searching algorithm. A* should search few nodes of graph.

As has been mentioned they can use navigation mesh. But the A* (or something similar) will be on top of that mesh anyway, because polygons of this mesh are just nodes of a graph; A* will then search for path from one polygon to another polygon.

Not sure about Warcraft or commercial games, but there is also technique called Collaborative Diffusion and it is very simple; it is usually done on grid. There is also technique called Potential Fields, which is very similar to previous one if not the same.

You might also try:

  • whether some of these games have source code available
  • whether some of clones of these games have source available
  • whether SDK or editors don't hint something
  • ask employers of companies making these games, some of them might be willing to share
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.