Map distance

[tobijon (OP)]

So I noticed that the distance in the overview map between different systems does not take into account connected rings. I have two rings in my map both of which have systems for which the indicated distance is incorrect because the second route discovered was shorter than the first. I don't know if this influences other decisions such as shipping routes, but I use those distances to determine which systems to explore next. Could it be implemented that whenever an existing system is discovered through a new jump point all the distances are recalculated, or use a function to find the shortest route in the map or something like that to take ring structures into account?

[Zap0]

Afaik reduced distances through alternate connections are calculated just fine. Keep in mind that the distances displayed are always from primary to primary.

[Froggiest1982]

Map is 3D represented on a 2D so you could get a loop of 50LY easily and other systems inside or a vertical loop of 5LY and systems between it across 50LY if you know what I mean.

I know that on custom map it is not implemented, however, that should be the general rule and I think everything could be easily explained that way.

[Zap0]

I looked at my map. Look at these screenshots, both from the same game, showing the same systems, except one empire knows a loop connection and the other doesn't. The connection to San Rafael is indeed displayed as shorter from La Tablada, but the conneciton to Bremen is... longer? There does seem to be something weird going on.

[tobijon (OP)]

As I said, there is a problem with it. I have a system which according to the map is 21.7 away, but if I click halfway it is 8 to go there and 9.6 to go back, that means the real distance can't be more than 17.6 and is lower than that since it's from primary to primary and not from jump points (the jump points in that system are close to each other). I also have a system which is 8.9 going there and 17.4 going back.

[Steve Walmsley]

I looked at my map. Look at these screenshots, both from the same game, showing the same systems, except one empire knows a loop connection and the other doesn't. The connection to San Rafael is indeed displayed as shorter from La Tablada, but the conneciton to Bremen is... longer? There does seem to be something weird going on.

It's because the search function stops when it finds the system. I could change it to search every potential route until there are no more systems to check (which I would also have to replicate for every fleet automatic route-check), but there would be a performance overhead. That is why I added the auto-route blocker option so you can force civilian traffic down a specific route.

[TheTalkingMeowth]

I looked at my map. Look at these screenshots, both from the same game, showing the same systems, except one empire knows a loop connection and the other doesn't. The connection to San Rafael is indeed displayed as shorter from La Tablada, but the conneciton to Bremen is... longer? There does seem to be something weird going on.

It's because the search function stops when it finds the system. I could change it to search every potential route until there are no more systems to check (which I would also have to replicate for every fleet automatic route-check), but there would be a performance overhead. That is why I added the auto-route blocker option so you can force civilian traffic down a specific route.

I'd be surprised if the path finding was that much of a runtime cost. Graph search is a very well studied problem, and there are nice algorithms for solving it. My PhD topic involves an extension of graph search, and we routinely search thousands of nodes in fractions of a second.

For solving the all to all problem (i.e, shortest path from any system to any other system), there are special algorithms that are faster than running individual pathfinding algorithms from each system to each other system. There are also algorithms that can "repair" existing solutions, so that slight changes to the graph (new connections, changing the starting location in a system that has two jump points going to the same system) can be solved very quickly.

Of course, all this requires you to spend the time to figure out which algorithms are appropriate and implement them/integrate them (I bet a lot of the basic ones are available). Leveraging them fully might also require a change to how pathfinding is handled at the root level.

[Migi]

I looked at my map. Look at these screenshots, both from the same game, showing the same systems, except one empire knows a loop connection and the other doesn't. The connection to San Rafael is indeed displayed as shorter from La Tablada, but the conneciton to Bremen is... longer? There does seem to be something weird going on.

It's because the search function stops when it finds the system. I could change it to search every potential route until there are no more systems to check (which I would also have to replicate for every fleet automatic route-check), but there would be a performance overhead. That is why I added the auto-route blocker option so you can force civilian traffic down a specific route.

I'd be surprised if the path finding was that much of a runtime cost. Graph search is a very well studied problem, and there are nice algorithms for solving it. My PhD topic involves an extension of graph search, and we routinely search thousands of nodes in fractions of a second.

For solving the all to all problem (i.e, shortest path from any system to any other system), there are special algorithms that are faster than running individual pathfinding algorithms from each system to each other system. There are also algorithms that can "repair" existing solutions, so that slight changes to the graph (new connections, changing the starting location in a system that has two jump points going to the same system) can be solved very quickly.

Of course, all this requires you to spend the time to figure out which algorithms are appropriate and implement them/integrate them (I bet a lot of the basic ones are available). Leveraging them fully might also require a change to how pathfinding is handled at the root level.

In my last game there was already a noticable time delay (1-5 seconds) between selecting a system and the new distances showing, there were ~100 systems explored.

[TheTalkingMeowth]

I looked at my map. Look at these screenshots, both from the same game, showing the same systems, except one empire knows a loop connection and the other doesn't. The connection to San Rafael is indeed displayed as shorter from La Tablada, but the conneciton to Bremen is... longer? There does seem to be something weird going on.

It's because the search function stops when it finds the system. I could change it to search every potential route until there are no more systems to check (which I would also have to replicate for every fleet automatic route-check), but there would be a performance overhead. That is why I added the auto-route blocker option so you can force civilian traffic down a specific route.

I'd be surprised if the path finding was that much of a runtime cost. Graph search is a very well studied problem, and there are nice algorithms for solving it. My PhD topic involves an extension of graph search, and we routinely search thousands of nodes in fractions of a second.

For solving the all to all problem (i.e, shortest path from any system to any other system), there are special algorithms that are faster than running individual pathfinding algorithms from each system to each other system. There are also algorithms that can "repair" existing solutions, so that slight changes to the graph (new connections, changing the starting location in a system that has two jump points going to the same system) can be solved very quickly.

Of course, all this requires you to spend the time to figure out which algorithms are appropriate and implement them/integrate them (I bet a lot of the basic ones are available). Leveraging them fully might also require a change to how pathfinding is handled at the root level.

In my last game there was already a noticable time delay (1-5 seconds) between selecting a system and the new distances showing, there were ~100 systems explored.

Mm, yeah I realized after posting that I should probably clarify.

Graph search is well studied to the point that this is absolutely a solveable problem. That does NOT mean that it is trivial to 1. select the correct algorithm 2. implement it efficiently enough. Just that, given sufficient programmer time, both 1 and 2 can be done.

[Steve Walmsley]

The current method takes the start system, then lists all known and accessible adjacent systems (accessible depending on survey, alien control, danger, jump capability, etc.). Each system is checked to see if it contains whatever the search needs (population, source of supply, unsurveyed bodies, etc.). If not, a list is created for a new set of adjacent systems, excluding those checked earlier in the search, and the process continues outwards.

There is no point having the updated distances on the galactic map if they aren't reflected in all other pathfinding checks. It's the overhead of all the other checks, rather than simply the distance, that adds the cost. The search still happens in a tiny fraction of a second, but during a single increment there can be a LOT of searches so a small decrease in performance can have a large impact.

[Migi]

The current method takes the start system, then lists all known and accessible adjacent systems (accessible depending on survey, alien control, danger, jump capability, etc.). Each system is checked to see if it contains whatever the search needs (population, source of supply, unsurveyed bodies, etc.). If not, a list is created for a new set of adjacent systems, excluding those checked earlier in the search, and the process continues outwards.

There is no point having the updated distances on the galactic map if they aren't reflected in all other pathfinding checks. It's the overhead of all the other checks, rather than simply the distance, that adds the cost. The search still happens in a tiny fraction of a second, but during a single increment there can be a LOT of searches so a small decrease in performance can have a large impact.

Would it be possible to store the distances in a cache table (assuming that's the right term) and re-calculate them whenever a fresh jump point is entered?
If the jump point leads to an existing system you would need to re-calculate all of the distances to catch changes.
But if it was a new system then you would only need to calculate the distances from that system to the existing systems.

[Steve Walmsley]

Would it be possible to store the distances in a cache table (assuming that's the right term) and re-calculate them whenever a fresh jump point is entered?
If the jump point leads to an existing system you would need to re-calculate all of the distances to catch changes.
But if it was a new system then you would only need to calculate the distances from that system to the existing systems.

No, because each fleet can potentially use a different route depending on its capabilities (jump capable vs not, avoiding danger vs not, avoiding alien vs not, etc.).

[db48x]

Would it be possible to store the distances in a cache table (assuming that's the right term) and re-calculate them whenever a fresh jump point is entered?
If the jump point leads to an existing system you would need to re-calculate all of the distances to catch changes.
But if it was a new system then you would only need to calculate the distances from that system to the existing systems.

No, because each fleet can potentially use a different route depending on its capabilities (jump capable vs not, avoiding danger vs not, avoiding alien vs not, etc.).

That doesn't make the memoization impossible, it just changes what information you use to look things up from the cache.

[TheTalkingMeowth]

Guys, open-ended suggestions won't help here. This has difficult implementation issues that Steve would need to work out, in code.

[TheTalkingMeowth]

In the interest of addressing my own concerns, I went ahead and implemented three pathfinding options in Python (see attached file, for Python3.6, no dependencies outside standard library).

First, the existing approach. This is known as breadth first search (BFS); it finds the path between two specific locations in the fewest number of jumps, though the resulting path is not necessarily the shortest. Implemented as find_path_bfs.

Second, a drop in replacement that would find the shortest path instead of the fewest jump path. This uses Uniform Cost Search (UCS, related to Dijkstra's algorithm). It is ALMOST identical to BFS. Implemented as find_path_uniform_cost, with special attention paid to show the parallels between UCS and BFS. Timings on the laptop I use to play Aurora indicate that UCS is on average about 25% slower than BFS for finding the path between a random pair of points. The tradeoff is that it finds the actual shortest path (on average, only 80% as far as BFS). I think on an actual Aurora jump network the slowdown would be smaller; my random network is way more connected than aurora networks, as evidenced by the really large distance improvement (most systems in an Aurora net have the same BFS and UCS distance).

Finally, one interesting possibility is to move away from the single-query path finding approach entirely. Instead of each ship calling find_path_bfs or find_path_ucs every time it wants to get from A to B, we can use a multi-query algorithm to "solve" the network. This algorithm would only need to be called if the network changes (new jump point, banned system, etc). Dedicated multi-query algorithms are MUCH faster than calling a single-query algorithm (like BFS or UCS) on every pair of jump points. In the attachment, I've implemented the Floyd-Warshall algorithm as solve_jump_net. Using this approach would be a much larger code change than switching from BFS to UCS would be. It also wouldn't necessarily be faster.

Also, there are other optimizations like using bidirectional search that could be used to speed up the single-query approach (for either UCS or BFS). I didn't implement any of them here.

To see the performance on your own machine, download the python file, navigate to the directory, and run python GraphSearch.txt in a command prompt. I had to change the extenstion to .txt from .py for upload; change it back if something complains. I didn't make this on my Windows partition; hopefully the end of line characters won't be too screwed up. Should not need any dependencies.

It will take a few minutes then print statistics to the command prompt.