The solution that Tomorrow Falls settled on relies on offline generation to determine which higher level paths are viable, allowing paths up to 8km long.
Mercuna’s navigation is based on similar principles, but allows annotation of the nav grid with friction, slope and modifier markup. Our maximum path length is 1-2km, but the grid can be regenerated quickly at runtime.