Skip to content

Pathfinding improvement tracking issue

During Sunday's meeting, zesterer mentioned a few issues with pathfinding:

  • Performance issues with A* in 3 dimensions, resulting in birds not flying as often as they could
  • Pathfinding for climbing not being stamina-aware and conservatively not checking some climbing routes, resulting in NPCs not being able to path up small hills/steps
  • Path following not being momentum-aware, resulting in wolves/fast creatures overshooting corners on ledges/tightropes

Possible fixes for performance:

  1. Implementing a metric-space aware pathfinding algorithm like RRT/RRT* (Algorithms 3 and 6 of https://arxiv.org/pdf/1105.1186.pdf) and Informed RRT* (https://arxiv.org/pdf/1404.2334.pdf).

This can be done progressively (i.e. implementing RRT first, then extending it to RRT*, then extending it to Informed RRT*) in separate MRs.

The {Nearest, Near, Steer, CollisionFree} tests in Section 3.1 of the RRT paper can be accepted as closures similar to how common::astar::Astar::poll accepts {heuristic, neighbors, transition, satisfied} (and there may be overlap in what AStar and RRT accept as input).

The RRT implementation should probably use a similar iters/poll design as AStar, so that common::path can experiment with interleaving the searches

RRT's Steer callback looks like it can be used as another degree of freedom for behavior tweaks (in addition to the heuristic available in RRT* and beyond):

  • making birds steer up to a given altitude until they're near the target, then swoop down.
  • humanoid NPCs using gliders
  1. Incorporating some of the tweaks in https://en.wikipedia.org/wiki/Any-angle_path_planning#A*-based (e.g. Block A*) to the current AStar implementation

Might be fewer changes than implementing full Informed RRT*, but less potential performance/tweakability gains.

Possible fix for climbing (applicable to any of the algorithms with a heuristic):

  • Maintain a running total of stamina to reach each node as well as distance to each node
  • Introduce a penalty term in the heuristic proportional to the stamina cost to reach that node, with a discontinuity if the total is greater than the maximum stamina
  • Introduce "rest nodes" on flat terrain that don't change the position, reset the stamina cost, and increase the distance (to represent time passing and avoid potential issues with negative-cost edges)

Possible fix for wolves on tightropes:

  • Implementing a PID controller (https://en.wikipedia.org/wiki/PID_controller) to allow fast entities to predict overshooting and slow down ahead of time
  • It looks like this might currently be informally approximated by path::TraversalConfig::slow_factor