I made a long-distance-route-plotter for #EliteDangerous currently it's using BFS to compute the route, which is quite slow (almost 40 minutes for a route accross the galaxy, checks visits 73% of the 27M systems in EDSM), i tried using a priority queue with the distance to the goal as the priority but that returned a sub-optimal route) and i can't do bi-directional BFS because of how the search is currently implemented (KD-Tree -> get neares neighbors in radius , queue those)
i rewrote this thing in #Rust (using an R-Tree instead of a KD-Tree because i couldn't find any KD-Tree crates that suited my needs) and now it's fast as hecc, 18 minutes for a route across the galaxy (the python version took 48 minutes), bad news is that it uses 9GB of RAM
next up: a GUI using Python+PyQt+PyO3, because there are no decent Qt bindings for Rust and i've got some experience with PyQt (and PySide) and after that maybe a Web GUI + task queue so i can offer this thing as a webapp (if my brother is OK with hosting it on our homeserver, it *does* eat 6GB of RAM)
now with a Dark Theme™ (copied from https://gist.github.com/skyrpex/5547015) and i'm totally not procrastinating updating the actual routing part (ed_lrr) to work with the GUI
pushed the current code to a new branch on gitlab in case anyone want to look at it https://gitlab.com/Earthnuker/ed_lrr/tree/pyqt_gui
aaand downloading the JSON dumps from #EDSM works (i moved the downloading code from rust to python because running it in rust with a callback to python froze the GUI (probably because GIL)), next up: trying to get callbacks to work anyways because i need the for the preprocessing and route computation part :|
flickering text in attached video Show more
testing some optimization ideas to skip stars outside of an ... ellipsoid? of configurable "radius" with the start and goal systems in the foci (focuses?), N is the tunable (tuneamble?) parameter, R is the "radius" of the ellipsoid, and the percentage shows what percentage of the total systems would be search, i still need to properly test this because i'm not sure if it's actually faster (it should be though, because it focuses the BFS without too much loss of accuracy)
@Earthnuker Damn that’s cool, it’s a shame about the RAM usage but in fairness you are computing a route through a galaxy. 9GB is nothing compared to finding a viable path across tens of thousands of light years.
@drisc yeah, i mean the current list from EDSM contains ~18 million star systems and i keep a HashMap from system_id -> coordinates in RAM for faster lookups when reconstructing the route, so the RAM usage is not really surprising, i could in theory precompute a KD-Tree and store it as a binary-heap on disk but that would slow down the route computation by a lot because disks are slow
@Earthnuker Sometimes I like to think about how to explain current software problems to someone from 20 years ago.
“Using a language that is designed to replace C++, I’m computing a route through a simulated galaxy in a video game which allows players to travel hundreds of thousands of light years, using consumer grade hardware in around 15 minutes.”
They would think you mad and possibly be green with envy as well.
@neauoire hmmmm, i looked at the code and apparently it can only export as PNG, which makes sense because everything gets drawn to a canvas
@cosine i did try A* but that gave me a suboptimal path, and Dijkstra on an unweighted graph is just BFS, currently trying out bi-directional BFS but that's a lot slower for some reason
@Earthnuker ah damn. cause that's the primary purpose of A* is that it's lossy but faster IIRC. but it's all about your priorities i guess
ｃｙｂｒｅｓｐａｃｅ: the social hub of the information superhighway
jack in to the mastodon fediverse today and surf the dataflow through our cybrepunk, slightly glitchy web portal