9 ms·

0AD Pathfinder Design [pdf]

78 points by evolve2k 11y ago

laarc 11y ago
As for an effective A* algorithm, bidirectional A* turns out to be both rugged and efficient. Basically, grab some graph paper. Put your left index finger on start. Right index finger on end. Move your fingers towards each other, avoiding obstacles as you go. Wherever they happen to meet, the path formed by the trail of both your fingers combined is the path to use. That's the general idea. It's important to trace from both simultaneously, otherwise you run into some degeneracies.
- karussell 11y ago
  Just as a side note: bidir A* is not that straight forward as you need a special finish condition to keep the algorithm optimal. (For games you probably don't need this but for tests and real world road routing it is important IMO)
- tanin 11y ago
  Here's the visualisation of bidirectional A* http://qiao.github.io/PathFinding.js/visual/ http://qiao.github.io/PathFinding.js/visual/
evolve2k 11y ago
Does anyone know if this is basically the same sort of Algorithm used in say the age of Age of Empires and Age of Mythology games?
- JoshuaJB 11y ago
  Yep! It's based pretty heavily off how AoE and later games do it.
  - pbhjpbhj 11y ago
    Are those games open source or has it been possible to reverse engineer the algorithm, or ...?
    - PeCaN 11y ago
      The original 0 A.D. pathfinder was based largely off reverse engineering the AoM one. [1] 1: http://wildfiregames.com/forum/index.php?showtopic=13042 http://wildfiregames.com/forum/index.php?showtopic=13042
    - JoshuaJB 11y ago
      Engineers have presented some of how their algorithms work at conferences and in other places.
      - evolve2k 11y ago
        Know of any video links to talks that you could share?
nomercy400 11y ago
I like how this article gives some insights on how to go from A* to a practical AI pathfinder. You always hear about 'use A* for pathfinding', only to get yourself stuck in the actual wiring the A* algorithm into your application.
- marshray 11y ago
  It's a rare thing, but always nice to see open source projects take the time to document their design rationale along the way.
- seivan 11y ago
  I really recommend http://www.amazon.com/Programming-Example-Wordware-Developers-Library/dp/1556220782 http://www.amazon.com/Programming-Example-Wordware-Developer.... I don't recall if it contained a segment of Behaviour Trees at this moment, but read up on BTs and replace any section containing FSM with that.
  - douche 11y ago
    Really an excellent book. I've been through a bunch, but I think that is still the best general-purpose, entry-level game AI book on the market.
keerthiko 11y ago
> The long-range pathfinder can be simpler and more efficient if it has a grid representation of the map. > (Since our maps are large and open [] and must support dynamic generation [] and dynamic modification [], a grid is likely better than a nav mesh) Can someone explain why this is the case? I feel like using a grid will result in them generating the equivalent of a fresh nav mesh every time they want to pathfind, as opposed to using a cached navmesh (generated when terrain is loaded) which they can modify in place every time a dynamic event occurs (building placed).
socceroos 11y ago
As an aside, 0AD is quite impressive as a 'golden-days' RTS. I've had lots of fun in it with my friends.
lunchTime42 11y ago
Really nice docu. Regarding A* sorry, but QTFPS is superior. https://github.com/spring/spring/tree/9bec15418279f1ecd87a5586d5f4ae44f8fee0ad/rts/Sim/Path/QTPFS https://github.com/spring/spring/tree/9bec15418279f1ecd87a55... Always fascinating is the actual Edge-Case Handling (UnitsStuck). Setting Collission off and sending Units back shortest path can yield unexpected results there.
- evolve2k 11y ago
  For those of us who know little about all of this can you explain in simple terms the different approaches and why you think one might be better.
  - lunchTime42 11y ago
    Well you use a Quadtree for path-finding. That gives you some advantages- regarding a) Resolution, (Long stretches of open terrain can be handled in one entry) b) Memory needed (Quadtrees are always just resolved as deep as needed and can be placed cache friendly in mem) c) Ask kloot. https://www.youtube.com/user/Kleaut https://www.youtube.com/user/Kleaut Regards

78 points by evolve2k 11y ago

laarc 11y ago

As for an effective A* algorithm, bidirectional A* turns out to be both rugged and efficient. Basically, grab some graph paper. Put your left index finger on start. Right index finger on end. Move your fingers towards each other, avoiding obstacles as you go. Wherever they happen to meet, the path formed by the trail of both your fingers combined is the path to use. That's the general idea. It's important to trace from both simultaneously, otherwise you run into some degeneracies.

karussell 11y ago
Just as a side note: bidir A* is not that straight forward as you need a special finish condition to keep the algorithm optimal. (For games you probably don't need this but for tests and real world road routing it is important IMO)
tanin 11y ago
Here's the visualisation of bidirectional A* http://qiao.github.io/PathFinding.js/visual/ http://qiao.github.io/PathFinding.js/visual/

evolve2k 11y ago

Does anyone know if this is basically the same sort of Algorithm used in say the age of Age of Empires and Age of Mythology games?

JoshuaJB 11y ago
Yep! It's based pretty heavily off how AoE and later games do it.
- pbhjpbhj 11y ago
  Are those games open source or has it been possible to reverse engineer the algorithm, or ...?
  - PeCaN 11y ago
    The original 0 A.D. pathfinder was based largely off reverse engineering the AoM one. [1] 1: http://wildfiregames.com/forum/index.php?showtopic=13042 http://wildfiregames.com/forum/index.php?showtopic=13042
  - JoshuaJB 11y ago
    Engineers have presented some of how their algorithms work at conferences and in other places.
    - evolve2k 11y ago
      Know of any video links to talks that you could share?

nomercy400 11y ago

I like how this article gives some insights on how to go from A* to a practical AI pathfinder. You always hear about 'use A* for pathfinding', only to get yourself stuck in the actual wiring the A* algorithm into your application.

marshray 11y ago
It's a rare thing, but always nice to see open source projects take the time to document their design rationale along the way.
seivan 11y ago
I really recommend http://www.amazon.com/Programming-Example-Wordware-Developers-Library/dp/1556220782 http://www.amazon.com/Programming-Example-Wordware-Developer.... I don't recall if it contained a segment of Behaviour Trees at this moment, but read up on BTs and replace any section containing FSM with that.
- douche 11y ago
  Really an excellent book. I've been through a bunch, but I think that is still the best general-purpose, entry-level game AI book on the market.

keerthiko 11y ago

> The long-range pathfinder can be simpler and more efficient if it has a grid representation of the map. > (Since our maps are large and open [] and must support dynamic generation [] and dynamic modification [], a grid is likely better than a nav mesh) Can someone explain why this is the case? I feel like using a grid will result in them generating the equivalent of a fresh nav mesh every time they want to pathfind, as opposed to using a cached navmesh (generated when terrain is loaded) which they can modify in place every time a dynamic event occurs (building placed).

socceroos 11y ago

As an aside, 0AD is quite impressive as a 'golden-days' RTS. I've had lots of fun in it with my friends.

lunchTime42 11y ago

Really nice docu. Regarding A* sorry, but QTFPS is superior. https://github.com/spring/spring/tree/9bec15418279f1ecd87a5586d5f4ae44f8fee0ad/rts/Sim/Path/QTPFS https://github.com/spring/spring/tree/9bec15418279f1ecd87a55... Always fascinating is the actual Edge-Case Handling (UnitsStuck). Setting Collission off and sending Units back shortest path can yield unexpected results there.

evolve2k 11y ago
For those of us who know little about all of this can you explain in simple terms the different approaches and why you think one might be better.
- lunchTime42 11y ago
  Well you use a Quadtree for path-finding. That gives you some advantages- regarding a) Resolution, (Long stretches of open terrain can be handled in one entry) b) Memory needed (Quadtrees are always just resolved as deep as needed and can be placed cache friendly in mem) c) Ask kloot. https://www.youtube.com/user/Kleaut https://www.youtube.com/user/Kleaut Regards