HomeWildfire Games

Optimisations to vertex pathfinder - relax optimality, sort unaligned edges

Description

Optimisations to vertex pathfinder - relax optimality, sort unaligned edges

Two changes to the vertex pathfinder that should generally improve performance:

  • Sort unaligned edges by distance like we did aligned edges. This isn't very scientific, but the idea is generally sound, and empirically it seems to do OK.
  • Relax the optimality by using a weighted heuristic, with weight 4/3 or 5/3 depending on the number of obstacles around. In the worst cases, A* will return paths that are this many times less optimal, but search should be faster in general (and sometimes much faster).

Both of these optimisations might increase the constant-cost slightly, but should decrease the worst-case runtimes.

Differential Revision: https://code.wildfiregames.com/D5034