Follow

I made a long-distance-route-plotter for 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?

i rewrote this thing in (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

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 :blobowo:

GUIs are hard™ and by that i mean i'm not good at UI Design

now with a Dark Theme™ (copied from gist.github.com/skyrpex/554701) and i'm totally not procrastinating updating the actual routing part (ed_lrr) to work with the GUI :blobowo:

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 gitlab.com/Earthnuker/ed_lrr/t

aaand downloading the JSON dumps from 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 :|

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

callbacks for preprocessing and route computation are fully implemented, i still need to hook up the UI and i also still need/want an application icon... maybe i'll cobble something together in (or ) @neauoire can Ronin export SVGs (or ICOs)?

flickering text in attached video Show more

@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

@cosine it doesn't need to be but i want it to be optimal :P

@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

Sign in to participate in the conversation
Cybrespace

cybrespace: 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