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)

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
Follow

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

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.