Posted by: TheTalkingMeowth
« on: January 04, 2021, 10:21:18 PM »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.
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.