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)
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)
ok, probably not R*-Trees are always O(log n) but KD-Trees are worst-case O(n)
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.