I just noticed this:
I think this is significant.
Why do you need a priority queue? BFS (implemented non-recursively) does not need any sort of priority or any function calls, just an ordinary queue… and the trick I showed earlier using arrays means you eliminate any “shuffling” associated with a conventional array. The thing is, if you are using a heap, you are making a function call on each loop iteration to do the adding or removing. That typically involves pushing a whole bunch of stuff on the call stack, jumping to the library routine for the add/remove operation on the heap, and then popping the results of the operation back off the call stack. By comparison indexing into an array to store or access an element is “heaps” faster (sorry for the pun )
If you are going for performance, I would recommend implementing the whole shortest-path routine all in one subroutine, with no library calls. BFS is not that complicated, and shouldn’t be more than a couple of pages.
I would strongly recommend using an array for the queue (using a heap without function calls would be a nightmare), and like I showed earlier, avoid shuffling all the values in the array each time you dequeue from it.
Similarly I’d check that all large data structures (like where you store which systems have jump-gates to which other systems etc) are either accessed via global variables or passed into the subroutine by reference, and the return results again, should be passed by reference if they are, or could be, of any decent size.
But there is one other thing I want to make sure of, is that you aren’t doing something like the following:
path_to_closest_station = undefined
for each station that buys blue loot
path = find_shortest_path(current_location, station)
if ((path_to_closest_station is undefined) or (length(path) < length(path_to_closest_station))
path_to_closest_station = path
The point is you should be looking for multiple destinations at the same time.
any_blue_loot_station = ( station1, station2, station3 ... )
path_to_closest_station = find_shortest_path(current_location, any_blue_loot_station);
The reason I mention it is because when you gave your example of computing “Tsuguwa <-> Zemalu” it made it sound like you are just computing point-to-point paths, when I think you should be computing Tsuguwa -> nearest blue loot station.
Hopefully some of this is relevant, and I’m not just trying to explain things that you are already doing