Return to Answer

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 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. While moving around the edges, it try to move back towards the imaginary line-of-sight (which might not be possible because there is still an obstacle).

Once unit is back to the imaginary line-of-sight, it resume path finding from there. Another obstacle 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 :

• Command & Conquer https://github.com/electronicarts/CnC_Remastered_Collection
• Warcraft 1 : personal research

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 :

• Command & Conquer https://github.com/electronicarts/CnC_Remastered_Collection
• Warcraft 1 : personal research

I agree with other answers that the A* algorithm (or variants) is used often, but some old RTS games (eg: Warcraft) 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 the 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.

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

It can result in a suboptimal path but on the other hand, it's really cheap to compute.

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

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 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. While moving around the edges, it try to move back towards the imaginary line-of-sight (which might not be possible because there is still an obstacle).

Once unit is back to the imaginary line-of-sight, it resume path finding from there. Another obstacle 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 :

• Command & Conquer https://github.com/electronicarts/CnC_Remastered_Collection
• Warcraft 1 : personal research

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.

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.

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

I agree with other answers that the A* algorithm (or variants) is used often, but some old RTS games (eg: Warcraft) 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 the 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.

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

It can result in a suboptimal path but on the other hand, it's really cheap to compute.

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