Skip to main content
1 of 4
tigrou
  • 3.2k
  • 1
  • 27
  • 43

While I agree with other answers the A* algorithm (or variants) is often used, old RTS games (eg: Warcraft) tends to use a simpler and faster approach.

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, and it can stop there since it already found closest path.

If an obstacle is found (eg: some trees), the algorithm try to get around it by moving around the edges. It check two paths : left and right path (depending unit orientation when obstacle is encountered) and it take the shortest one.

enter image description here

Once unit is back to the imaginary line to the target, it simply move towards destination again (until another obstacle is found and so on).

This can lead to a suboptimal path (eg: not the shortest one) but on the other hand, it's cheap to compute.

enter image description here

(from Warcraft 1 : peon get lost and has to go back)

tigrou
  • 3.2k
  • 1
  • 27
  • 43