Plotting routes, why so long?
- Thread starter S~P
- Start date
Quite simply, there are just too many systems for their algorithm to do the 'fastest route' calculation on.
Really there are lots of things they need to do here:
1) another 'good enough' route that does not try to be the 'fastest' but which calculates quickly.
2) Making the route finder algorithm homour the filters that you have in place. That would not only make it much more useful (I don't really use it anywhere because of this design stupidity), but would make it much faster near to the core.
3) Let you build routes incramentally: build a route of, say 100LY, then extend it from that 'waypoint' for another 100LY, and keep going. This lets you plan routes that go through 'interesting systems', without having to do every jump manually (which is what I tend to do).
4) Probably a few more I could come up with if I could be bothered.
Really there are lots of things they need to do here:
1) another 'good enough' route that does not try to be the 'fastest' but which calculates quickly.
2) Making the route finder algorithm homour the filters that you have in place. That would not only make it much more useful (I don't really use it anywhere because of this design stupidity), but would make it much faster near to the core.
3) Let you build routes incramentally: build a route of, say 100LY, then extend it from that 'waypoint' for another 100LY, and keep going. This lets you plan routes that go through 'interesting systems', without having to do every jump manually (which is what I tend to do).
4) Probably a few more I could come up with if I could be bothered.
The algorithm needs more work, even when it is less dense space. I can be surrounded by scoopable stars, as soon as I plot even a moderate 500Ly route, the algorithm comes up with L, T and Y stars, so I end up plotting my own 2-3 jumps each time.
I agree wholeheartedly with points 1,2 and 3 from AnnuverScotinExile.
I agree wholeheartedly with points 1,2 and 3 from AnnuverScotinExile.
Its very easy to demand that. Turns out in practice this is really hard to do algorithmically. If you look at Dijkstra's Algorithm you will quickly realize that identifying the shortest path is actually far easier than finding the second shortest path ... or just a "good path" in general ... Because if you do an arbitrary search it is neither clear how to avoid/deal with dead ends, nor if a path you might have found is any "good" at all.
In general making routing faster has limits when the graph grows large, especially when the graph is not static (the weights of the edges keep changing depending on your ship's loadout and cargo), which makes it impractical to efficiently apply optimizations such as Contraction Hierarchies. What one realistically can do, is make adjustments to the pathfinding of Dijkstra's Algorithm. What I suspect they have already done is replace it with A* search (which really just adds a heuristic to Dijkstra's algorithm). Other options would be to use more efficient data structures (for example a Fibonacci Heap) or for example try a multi-threaded Bi-Directional Dijkstra / A* variant.
But yeah.. turns out this problem is complicated from a theoretical perspective and probably nothing they just neglected to solve because they are lazy
Last edited:
