Pathfinding

[Sheekel]

edit

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

[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]

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]

edit