Hello again
Talking to the fuel rats some days ago motivated me enough to finally finish this project so that it can be presented to the community.
I play on PS4 and thus can not contribute in a good way to EDSM (yes, I use the console updater and that was one of last years great moments when I learned about it).
The above post was just some roleplaying within non-official lore.
This post is a bit more technical and I try to explain how the software which allows me to find a path in low star density regions works.
Just in case: the program can be found on GitHub under it's name
gap_jumper.
My original problem had several aspects.
- Wanting to cross from Outer Arm Vacuus to the Perseus Arm with as little "flying backwards" as possible. (I totally failed this task when I circumnavigated the galaxy.)
- Low on Jumponium and thus fear of getting stranded
- The amazing edastro.com shows clearly that travelers have crossed this gap. However, the resolution is not good enough to figure out which stars these are and the map is two dimensional anyway. No criticism! I love edastro and it helped me a lot to find my way around the galaxy .
- In addition comes that I could not find detailed information about possible crossings (with some exceptions) at EDSM (or other sources). But this is important to estimate how much Jumponium is actually needed if a given route is traveled.
- All the programs I could find here seemed not to be suitable to the task at hand (or for an operating system I don't have). But I may be wrong at this.
Solution:
The
EDSM database has the names and coordinates of all reported systems. Thus I should be able to find a way between a given start- and endpoint.
And this is what my program is about.
So, how does it work?
Well, first of all the approximate start- and end-coordinates are used to define the line between these two.
This line is the center of a cylinder with 500 lightyears diameter (adjustable). The program then finds all (reported) systems within this cylinder. This takes some time.
I provide two mechanisms. One that uses the EDSM API. While I loved programming that. However, it will send a lot of requests and is in the end slower than using method two.
Method two requires to download the "systemsWithCoordinates.json" database and will work on that file. It still needs some time to go through the many million reported systems to find those relevant.
A big thank you to zibadian from the Fuel Rats (I think) for discussing during the above mentioned chat some methods in connection with my program and for making me aware of the EDSM API. I wish I could have stayed longer but I had to go quite suddenly.
Anyway, after finding the systems in the region of interest, the pathfinding algorithm starts. This is what the rest of this post is about.
So, I haven't studied computer science, but naturally I first thought of
Dijkstra's algorithm to find the shortest path.
I had a nice implementation (and I didn't care about running time) but then I realized that I was not able to implement boosted jumps in case ALL possible distances at a given location were longer than the regular jump range. Or well, I had ideas how to do it, but all of them were not at all elegant, required at all times information about the whole state of the system of possible stars to jump to or would have needed re-calculation of everything. That was unsatisfactory.
This task was (for me) so difficult because I wanted to use boosted jumps just as a very last measure. So I wanted to punish boosting since Jumponium is so rare.
Fortunately am I a physicist. So after two days of thinking (not in sum, since I also have to do other stuff) how to make Dijkstra's algorithm work I thought about a very different approach. And this approach was electrical current!
An electrical current ALWAYS finds a way through a network of conductors AND it will always find the way of least resistance.
What does that mean for our case?
Well, jumps that require boosting are equivalent to having a higher resistance. And the higher boost grade is needed, the higher the resistance. A current will take the path with the higher resistance but JUST if it can NOT find another way. The latter may mean going backwards, but this was totally acceptable for me since saving Jumponium had the highest priority.
Thus, an electrical current inherently "punishes" passages with higher resistance.
So, I came up with the idea of probes (being the current) traveling from station to station (being the network of conductors). In the code I call them Jumpers and Nodes.
All systems have one station and all stations are EMPTY in the beginning. The exception: the station at the start-coordinates contains a probe. The process of finding a path from start to end is now the following.
The program has a global parameter which tells if a jump from one station to another took place. This is the "resistance of the galaxy".
Each station that contains a probe checks if the stations within regular jump range are empty. If this is the case, a probe is send to these stations. One such jump is enough to set the global paramter to True. If no jump took place in the whole cylinder of all considered stars this parameter is set to False. The latter can happen if stations contain no probe to send or all other stations are out of reach.
In the False case the "resistance" of the distances between the systems changes. This allows all stations to use probes with a higher jump range, meaning: all stations within grade 1 boosted jump range are now considered.
If a station within grade 1 boosted jump range is found, the global parameter is set to True, and the next jumps will be with regular jump range again.
If still not a single station could send out a probe with grade 1 boosted jump range the same process starts again, but considering now systems which need a grade 2 boosted jump to reach; and so on.
This algorithm does several things I wanted it to do.
1.: It uses boosted jumps JUST if in NONE of the stations that contain jumpers can send a probe with a regular jump.
2.: It does not necessarily find the route with the least amount of jumps (shortest route), but it does find a route close to it. The reason is that if a probe can be send to a system at the edge of the regular jump range, than this is done. A probe does NOT need to visit all systems in between. Thus, the algorithm is by itself close to the best solution. I think it is a
greedy algorithm but I'm not sure and I would not really know what kind of "greediness" it is.
3.: It goes backwards and up and down if necessary. Something the regular ED plotting algorithm seems not to do. This can be seen e.g. in the "loop" in
Hugo's High Road
Some more comments.
- Instead of using Jumponium are of course first jumps on fumes considered.
- I have implemented a function which considers the available fuel and would not allow a jump to an unscoopable star if this would strand the probe there. However, this function is not really active, because the information if a system contains a scoopable star or not is not available for all stars. Thus I consider all stars as scoopable.
- For the just discussed case I have implemented a feature which checks for nearby scoopable stars and would tell the user to do a detour to fill up the tank. However, I've never seen this to be triggered since I didn't run into the case described. I constructed some weird test-cases in which it worked but this feature is to be considered as … well, experimental.
- The order of stations to send out a probe is random. Thus, by running the algorithm several times more efficient routes can be found. And this confuses me because it shouldn't. I can just explain it the algorithm being greedy and thus not always finding the global minimum. I tested and tested and checked the code but could not find the source why it does that. Thus my only explanation was that sometimes (due to the random order of stations when to send a probe) a series of fortunate events allows the algorithm to find the globaly best path. If anybody of the readers points me to the (logical) error in my code I will be really thankful.
- However, the algorithm is rather close to the optimum already (as greedy algorithms are in general). I ran several thousand tests for some routes and the routes found durig the first twenty tries were very close to the most efficient route found e.g. at try 666.
- Saving grade 3 Jumponinum is considered as much more important than to save grade 2 Jumponinum which is much more important than to save grade 1 Jumponinum. Thus it is entirely possible that the program comes up with a route which uses more grade 1 boosts but less grade 2 or grade 3 boosts. However, during tests that never happened.
- If the used databases is downloaded the location of the file needs to be provided in the code.
- The code is not very efficient, but I don't care. The main time consuming process is looking up the information in said databases.
- VERY IMPORTANT: DON'T USE THE PROGRAM IN REGIONS WITH HIGH STAR DENSITY! Or well, use it as you wish, but this will take forever and it will gobble up your memory.
I don't provide a GUI and all the necessary parameters need to be changed in the code. Because so far it is just me who actually uses the program. But if other commanders show interest, I may program a GUI. I may even provide an executable for a non-GNU/Linux operating system. However, if you run the code directly (it is written in python3) it should already work under all operating systems.
Eidt: 2020-01-21: I p've provided a GUI and an executable that runs under windows.
This is free software (like in freedom of speech) and the code is published under the GPL version 3. It is also free of charge (like in free beer).
So if anybody wants to implement it into their existing programs, feel free to do as you wish (as long as you obey the license -- don't jail my babies!)
If you have suggestions how to make things better, or if you have an idea how to get boosting into Dijkstra's algorithm, I would really like to read about it.
And if anybody is interested in a discussion, I would like to read your opinions regarding the following:
- Will this take away some dangers of exploration? Will this break the spirit of exploration? If yes, why then having a Galactic Mapping Project?
- Is this considered cheating? If yes, why then having a Galactic Mapping Project?
Fly save commanders