Pathfinding

Pathfinding

Discuss the source code and development of Spring Engine in general from a technical point of view. Patches go here too.

Moderator: Moderators

Post Reply
Sheekel
Posts: 1391
Joined: 19 Apr 2005, 19:23

Pathfinding

Post by Sheekel »

edit
Last edited by Sheekel on 04 Mar 2009, 03:42, edited 1 time in total.
Tobi
Spring Developer
Posts: 4598
Joined: 01 Jun 2005, 11:36

Re: Pathfinding

Post by Tobi »

AFAIK, it uses A* on 2 or 3 levels. Immediately when an order is given the path is planned on the highest level and only when the units reaches a particular subspace a path through that subspace is planned using a more fine grained A*.

Besides that there is a path cache which caches paths so when many units take approximately the same path it can reuse them.

Something in all this is also pregenerated (not sure what without checking code) and has to be regenerated everytime heightmap changes (only the part that changed..).

The A*'s itself use MoveMath and related classes in the engine to determine passability and movement speed of terrain, and hence cost to to travel it.

The blue/green/red lines are the A* "closed" set of nodes, I think, for the different granularity levels.
User avatar
AF
AI Developer
Posts: 20687
Joined: 14 Sep 2004, 11:32

Re: Pathfinding

Post by AF »

kman hasn't been seen on these forums in years, he may lurk, he may be in the IRC channel for all I know, but he was fond of diagrams, and somewhere on this server/machine there are a set of diagrams though I'm not sure if they explain springs path finding or rather how he wanted it to work but never got the time to implement.
Kloot
Spring Developer
Posts: 1867
Joined: 08 Oct 2006, 16:58

Re: Pathfinding

Post by Kloot »

Tobi wrote:
AFAIK, it uses A* on 2 or 3 levels. Immediately when an order is given the path is planned on the highest level ...
And, if the destination waypoint is within a (hardcoded) "detailed distance" from the unit's position, then it actually starts planning directly on the highest-res level, or on the second (medium-res) one if it's further away but still within another hardcoded "estimate distance" bound.
Something in all this is also pregenerated (not sure what without checking code)
The estimate paths at the low- and medium-res levels, which are converted (segment by segment as the unit moves towards its goal position) to medium- and high-res subpaths respectively. The estimator is also the only pathfinder component that uses (adds paths to and retrieves them from) the cache.
Sheekel
Posts: 1391
Joined: 19 Apr 2005, 19:23

Re: Pathfinding

Post by Sheekel »

edit
Post Reply

Return to “Engine”