I found that in #29, adding flight points to the current implementation of the directions feature slowed pathfinding to a crawl. Part of the problem may be that getting the vertex with the min distance to the currently-being-processed vertex in Dijkstra is an O(n) operation because we're using a for-loop instead of putting all the vertices in min-heap, which is O(log n) for worst case insert and delete.

I want to avoid implementing my own min heap implementation to save time, so I found this: https://github.com/Tieske/binaryheap.lua/blob/master/src/binaryheap.lua

Objectives:

• Check out the taxi branch, replace the min-finding for-loop with the priority queue, and see if it's faster.
• Try the taxi circuit optimization #29 (comment)
• Find out how the command table addon calculates victories without hanging up the entire game

I replaced it with a min heap, but the computation is still slow. In order to stop it from hanging the entire game for several seconds, I made one iteration of the while loop happen every time OnUpdate is called (once per frame). Since it's now limited to once a frame, the operation has become even slower.

Part of the problem might be that one iteration of the Dijkstra while loop takes longer than the duration of the frame, and we're performing some duplicate calculations or something. We should probably prevent it from running if there's already one currently happening.

Also getAdjacentNodes is orders of magnitude slower than the min heap operations, since it's an O(n) over all the edges and nodes in the datasets we're using worst case. Since we often only care about nodes in the same continent as the player for some of the loops, maybe we can pre-sort them into a dictionary table with continent as keys and nodes as values.

Part of the problem might be that one iteration of the Dijkstra while loop takes longer than the duration of the frame, and we're performing some duplicate calculations or something. We should probably prevent it from running if there's already one currently happening.

Tested this approach by setting a "calculating" flag if it's in the middle of calculating and unsetting it when it's done. Whenever the event callback fires, the flag is always unset.

I guess it makes sense. Before throttling Dijkstra to OnUpdate firing, it froze the entire game/main thread. Now each iteration of the loop, the game freezes (preventing OnUpdate from firing again), but for a really small amount of time so that it's not noticeable.

Conclusion: the flag is not useful and I should remove it.

Flight points added in 2.0