News for hackers. Stuff that matters.
Re:0AD Pathfinder Design [pdf] by laarc on Sunday December 06, 2015 @01:39AM (#10684599)
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.

Re:0AD Pathfinder Design [pdf] by karussell on Sunday December 06, 2015 @04:22PM (#10686682)
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)
Re:0AD Pathfinder Design [pdf] by tanin on Monday December 07, 2015 @02:38AM (#10688327)
Here's the visualisation of bidirectional A* http://qiao.github.io/PathFinding.js/visual/
Re:0AD Pathfinder Design [pdf] by keerthiko on Sunday December 06, 2015 @04:56PM (#10686831)
> 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).

Re:0AD Pathfinder Design [pdf] by nomercy400 on Sunday December 06, 2015 @04:12PM (#10686646)
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.
Re:0AD Pathfinder Design [pdf] by marshray on Sunday December 06, 2015 @04:38PM (#10686752)
It's a rare thing, but always nice to see open source projects take the time to document their design rationale along the way.
Re:0AD Pathfinder Design [pdf] by seivan on Monday December 07, 2015 @01:13AM (#10688165)
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.
Re:0AD Pathfinder Design [pdf] by douche on Monday December 07, 2015 @07:35PM (#10693956)
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.
Re:0AD Pathfinder Design [pdf] by evolve2k on Sunday December 06, 2015 @07:17AM (#10685069)
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?
Re:0AD Pathfinder Design [pdf] by JoshuaJB on Sunday December 06, 2015 @04:02PM (#10686591)
Yep! It's based pretty heavily off how AoE and later games do it.
Re:0AD Pathfinder Design [pdf] by pbhjpbhj on Sunday December 06, 2015 @04:12PM (#10686643)
Are those games open source or has it been possible to reverse engineer the algorithm, or ...?
Re:0AD Pathfinder Design [pdf] by PeCaN on Sunday December 06, 2015 @06:46PM (#10687259)
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

Re:0AD Pathfinder Design [pdf] by JoshuaJB on Sunday December 06, 2015 @07:54PM (#10687476)
Engineers have presented some of how their algorithms work at conferences and in other places.
Re:0AD Pathfinder Design [pdf] by evolve2k on Monday December 07, 2015 @06:46AM (#10688823)
Know of any video links to talks that you could share?
Re:0AD Pathfinder Design [pdf] by socceroos on Sunday December 06, 2015 @05:33PM (#10686977)
As an aside, 0AD is quite impressive as a 'golden-days' RTS. I've had lots of fun in it with my friends.
Re:0AD Pathfinder Design [pdf] by lunchTime42 on Monday December 07, 2015 @06:14AM (#10688742)
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.

Re:0AD Pathfinder Design [pdf] by evolve2k on Monday December 07, 2015 @06:44AM (#10688816)
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.
Re:0AD Pathfinder Design [pdf] by lunchTime42 on Monday December 07, 2015 @08:09AM (#10689172)
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