For we it works bit weird now. When I check "Fastest routes", map is calculating routes to ALL stars in radius which takes some time (especially for systems ~100 LY away). Why? Wouldnt that be easier to just click on star/destination and THEN map will calculate route to this star? Which should take few seconds max.
[Suggestion] Planning Routes
- Thread starter Theev
- Start date
I might be wrong, but I think, from an algorithmic standpoint, you don't get any improvement at all, even after knowing your target destination. At first, I thought, well, how about you construct a line between where you are and the destination, so you get a plane that's perpendicular to that line, separating stars which get you further away and those that get you closer. That should run at double speed, right?
Then, if you think about it, if you have a system of stars that look like a C-shape, where the ends are too far to make the jump directly, you have to first move further away to get closer, so the method above doesn't give you a jump solution, where one is available.
To exhaustively search for an optimal path, I believe there's no way around actually pathfinding every single star in range.
The following discussion will get a bit more mathematical. What I think Elite is doing is (or at least, what I would do is):
1. Define the bounds of your points, hence the limit of ~70Ly, otherwise you would encompass every single star and you would still be looking for more. When do you stop? You need a finite bound.
2. Define a graph based on these points. This is a fully-connected graph. Each star within your selected bound is a node.
3a. If you're looking for the economical path, the weight in between graph nodes is a function f(d) = fuel cost, where d is the distance between the stars. If this f(d) exceeds your max fuel per jump, delete this link (set to infinite in the graph's adjacency matrix)
3b. If you're looking for the path with smallest number of jumps, do the same as above, but the weight this time is 1 for each surviving link.
4. Run Dijkstra's shortest path algorithm.
Then, if you think about it, if you have a system of stars that look like a C-shape, where the ends are too far to make the jump directly, you have to first move further away to get closer, so the method above doesn't give you a jump solution, where one is available.
To exhaustively search for an optimal path, I believe there's no way around actually pathfinding every single star in range.
The following discussion will get a bit more mathematical. What I think Elite is doing is (or at least, what I would do is):
1. Define the bounds of your points, hence the limit of ~70Ly, otherwise you would encompass every single star and you would still be looking for more. When do you stop? You need a finite bound.
2. Define a graph based on these points. This is a fully-connected graph. Each star within your selected bound is a node.
3a. If you're looking for the economical path, the weight in between graph nodes is a function f(d) = fuel cost, where d is the distance between the stars. If this f(d) exceeds your max fuel per jump, delete this link (set to infinite in the graph's adjacency matrix)
3b. If you're looking for the path with smallest number of jumps, do the same as above, but the weight this time is 1 for each surviving link.
4. Run Dijkstra's shortest path algorithm.
Last edited:
Solution: go get yourself a snack while you wait...