Wormhole Pathfinding (Starflight GPS)

[JernejL]

Looks good - first thought when i saw this was to just add wormholes to search node graph with a lower node cost and a non-grid output coord.. - i guess that should work just ok with A* and looks like it's what you made, too.

[klausvdl]

Looks good - first thought when i saw this was to just add wormholes to search node graph with a lower node cost and a non-grid output coord.. - i guess that should work just ok with A* and looks like it's what you made, too.

Thanks! You're guessing right, except that this is not quite A*.

Actually before I implemented the above solution I had found a discussion about A* and wormhole tunnels. As you know in A*, when picking a new node, you have to "estimate" the node's distance to the destination. And the proposal was to not take the distance from the new node but the distance from the wormhole tunnel's other end node to the destination.
This sounds quite reasonable. But I wasn't sure about mixing up distances and fuel costs, and so I stayed with Dijkstra (which is fast and robust in any case).

[JernejL]

a* and djikstra are highly similar and to my knowledge only differ in node weight calculations, so the approach to just skip areas would work equally well for both.

There's not a lot of examples and libraries for pascal in area of pathfinding and autonomous navigation, it is good to see other posting their work here.

[SilverWarior]

a* and djikstra are highly similar and to my knowledge only differ in node weight calculations

Actually A* is an extension of Djikstra algorithm.
Main difference between A* and Djikstra is that Djikstra spreads outward evenly from starting node while A* tries to predict the distance to finish node and this spreads out first across the nodes that are in general direction of the destination node. This generally means that A* needs to traverse through lesser number of nodes in comparison to Djikstra. But since in A* you need to calculate predicted distance toward destination node while this isn't needed in Djikstra it means that A* isn't better in all scenarios. in fact in certain scenarios it could be quite a bit slower in comparison to Djikstra.

[JernejL]

You are absolutely correct in this, and to work around the issue of potentially slow path calculations in my game, i have put pathfinding into its own job-thread - hopefully this will work ok, so far i have no issues with this.

[SilverWarior]

You are absolutely correct in this, and to work around the issue of potentially slow path calculations in my game, i have put pathfinding into its own job-thread - hopefully this will work ok

Moving pathfinding into separate thread is a good idea. Even better one is to allow pathfinding to run in multiple threads where each thread is calculating path between different staring and destination node. Offcourse you need to implement your pathfinding algorithm so that each thread ha its own temporary data (opene and scaned nodes) so that threads don't interfere with each other.


Another thing for making pathfinding much faster is to implement heuristics approach. Using heuristics you can greatly reduce the number of nodes scanned. But the problem with heuristics pathfinding is that its implementation laregly depens on how your world is defined. This is one of the reasons why not many people decide to go this way. Well not until non-heuristics pahtfinding algorithms manages to work fast enough.