Pathfinding enhancements

[metalgearsloth]

In no particular order:

• Support for different graphs via interface: i.e. current one (except improved) vs navmesh.
• Space pathfinding
• Support for actual hierarchical pathfinding. This will most likely be done via a medium + low coarseness pathfinding (medium being regions and low being tiles themselves). Probably not possible to do it via chunks given 1 half of a chunk may not be accessible to the other half. As the steering system is run it should be able to have the path refined further as it moves along and also listen to determine if it needs to re-path. This will also mean an AiSteeringSystem refactor is needed (which it is anyway)
• Pathfinding caching (probably just for medium paths). Currently nearby accessible regions are cached
• Make pathfinding regions rectangles (no more hashset storing every node) that just store width and height. Might still need to store our neighbours in a hashset.
• Use RSR (rectangular symmetry reduction) for pathfinding regions so only the exterior nodes are pushed to the frontier
• Caching for JPS jump points (haha pathfinder go brrt)
• Dynamically select which pathfinder to use at runtime (i.e. tile costs not needed then use JPS)
• Make the returned nodes structs and add additional metadata to it e.g. do we need to break a wall
• Node costs for stuff like walls that we can break
• Make pathfinding nodes structs and have additional metadata (e.g. is there a door) in a separate lookup
• Split PathfindingSystem into a pathfindingmanager (for actually dispatching pathfinding requests) and pathfindinggraph
• Parallel pathfinding while still using the existing time-sliced JobQueue
• The pathfinder should prune redundant tiles and the AiSteeringSystem shouldn't just pop them during collision avoidance

Pathfinders currently okay performance wise with small paths but if we want something to go across box-station the above will be needed to make it faster. This will also mean stuff like pathfinding graph updates will be faster.

[Ygg01]

This seems less like an issue, and more like a meta issue.

I.e. can be broken into tinier independent chunks - adding different interfaces, adding different algorithms, etc.

[metalgearsloth]

The problem is at least 2/3 of these are dependent on each other. If pathfinding nodes are made into structs suddenly most of these would need to be rewritten.

[metalgearsloth]

Will split up