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?

Show thread

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

Show thread

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

Show thread

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?)

Show thread

this is getting really silly, runtime went from 2 hours (python) -> 20 minutes (rust) -> 50 seconds (rust+precompute) -> 15 seconds (rust+precompute+index)

Show thread

maybe it'll be even faster when i switch the R*-Tree for a KD-Tree

Show thread

ok, probably not R*-Trees are always O(log n) but KD-Trees are worst-case O(n)

Show thread

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)

Show thread

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

Show thread

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:

Show thread

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:

Show thread

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

Show thread

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!)

Show thread

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

Show thread

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)?

Show thread

flickering text in attached video 

Show thread

@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 is an instance of Mastodon, a social network based on open web protocols and free, open-source software. It is decentralized like e-mail.