[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.
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).
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.)
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.
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.
I agree with other answers that the A* algorithm (or variants) is used often, but in some old RTS games (eg: Command & Conquer / Warcraft 1) a simpler and faster approach is used.
It works this way : project an imaginary line-of-sight from the unit position to its destination. Most of the time, there is no obstacle between unit and target, and it can stop there since it already found the closest path.
If obstacles are found (eg: trees), the algorithm try to get around it by moving around the edges. To do this, the unit is rotated a certain number of degrees (eg: 45) until it can move again. It check two paths : left and right path (depending unit orientation when obstacle is encountered) and it take the shortest one. While moving around the edges, it try to move back towards the imaginary line-of-sight (which might not be possible because there are still obstacles).
Once unit is back to the imaginary line-of-sight, it resume path finding from there. More obstacles might be encountered and so on. It stops once target is reached.
It can result in a suboptimal path but on the other hand, it's really cheap to compute. In some extreme cases, unit might get lost (no path was found while there is at least one).
(from Warcraft 1 : peasant has to backtrack, resulting in suboptimal path)
Sources :
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.
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:
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.
Those older games probably did use grids and standard A* but maybe with additional optimisations such as jump search A* or simply tweaking the heuristic. There's also basic techniques that can be applied like staggering path requests across several frames or grouping path requests for groups of units.
More modern rts games like Starcraft2 may use navmesh or flowfields.
