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)

@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

Follow

@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

Β· Web Β· 0 Β· 0 Β· 1
Sign in to participate in the conversation
ACP πŸŽ‰πŸ°

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!