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)
the bi-directions BFS does not work because there are some types of stars (neutron stars and white dwarfs) that boost your jump range, so if i come from the goal node that would be a problem... or am i missin something?
poked some stuff, now it's stupid fast (after precomputing the BFS-graph for ~20 minutes and eating 8GB of RAM (for 30M star systems)) i also dramatically reduced the memory usage because i don't need to load all the systems into memory when i'm only interested in those along the computed route
next up: building an Index for the CSV files so i don't have to linear-search to get a system by its ID (and maybe sort the systems by name so i can binary-search for a name?)
this is getting really silly, runtime went from 2 hours (python) -> 20 minutes (rust) -> 50 seconds (rust+precompute) -> 15 seconds (rust+precompute+index)
maybe it'll be even faster when i switch the R*-Tree for a KD-Tree
ok, probably not R*-Trees are always O(log n) but KD-Trees are worst-case O(n)
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)
got Rust <-> Python inter-op working, i'll probably start building a GUI over the weekend and then start writing wrapper code for ED_LRR
PyQt -> Rust -> Python works (button handler calls a rust function that calls a python callback), i guess that means i can start cobbling together a GUI, yay
GUIs are hard™ and by that i mean i'm not good at UI Design
hmmmm, i'll also need an icon for this thing
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 :|
prettied the download progress up a bit
Next up: messing around with the multiprocessing module to move the call into Rust code into a separate process so it doesn't freeze the GUI (yay GIL!)
calling the route() function in a separate python process and getting progress reports back works :D, now i need to cobble that into the GUI
flickering text in attached video
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
Cybrespace is an instance of Mastodon, a social network based on open web protocols and free, open-source software. It is decentralized like e-mail.