Age of Empires pathfinding

Pathfinding in strategy games

Many people have been annoyed be the unsatisfactory pathing in AoE. However, there is not a better algorithm available yet (you can only find a better path by sacrificing more CPU time). Like many other games of its kind, AoE uses the A* algorithm for the pathfinding. This algorithm is very well described in a scientific paper written by F. Markus Jönsson. It is not too hard to understand the principle if you have a basic idea of graphs, but it shows how solving and implementing a seemingly simple problem can be very hard on a computer.

Pathfinding demo

Michael has sent my a link to a Path finding demo site:

"The PathDemo is rather cool. It has a little map editor that lets you define your pathing problem. You can then choose from range of different algorithms to solve it."

Weakness in the pathfinding algorithm in AoE

"The problem I have with AoE pathfinding is that sometimes a group of units get stuck. Maybe the units are deadlocked. i.e. The pathing problem is a group problem not a single unit problem. An example that I have seen several times looks something like this

                 G

          TTTTTTT
             UUUT
              UU

Where G is the goal, T is a tree area and U is a unit.

My guess to a solution to this is that all unit that are stuck and can move in another direction should do so randomly for a short random distance before re attempting a pathing solution to the goal. Where a unit is fully enclose it should transmit a "Im stuck message" to all of the adjacent units. The adjacent units should respond as if they themselves where stuck and passing on the message if they are fully enclosed. The short random distance is needed to allow the enclosed units a chance to perform a random move themselves.

I don't think AoE pathing is the best that pathing algorithms can provide."

Michael S.

Top	Back

Main - Downloads - FAQ - Forum - Interviews - Links - News - Rise of Rome - Scenarios - Strategies - Tips - Units