0AD Pathfinder Design [pdf] | Hacker News Reader

0AD Pathfinder Design [pdf]

github.com

78 pointsevolve2k18 comments

Open articleView on HN

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.

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)

Here's the visualisation of bidirectional A* http://qiao.github.io/PathFinding.js/visual/

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

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.

It's a rare thing, but always nice to see open source projects take the time to document their design rationale along the way.

I really recommend 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.

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.

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?

Yep! It's based pretty heavily off how AoE and later games do it.

Are those games open source or has it been possible to reverse engineer the algorithm, or ...?

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

Engineers have presented some of how their algorithms work at conferences and in other places.

Know of any video links to talks that you could share?

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

Really nice docu. Regarding A* sorry, but QTFPS is superior.

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.

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.

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

Regards

Reply on news.ycombinator.com