Sector Map Auto Route Issues

[Web-eWorks]

I'd like to preface this by thanking @The-EG for writing the route planner in the first case, and @fluffyfreak for making it possible to route a 25,000ly path; it's because of his work that I'm not making this issue about routing a 200ly path.

Go to Sagittarius A* (-3125, 0, 0) and click Auto Route. The game will then freeze for about five minutes as it considers 187,597 stars for a total of at least 17,000,000,000 (seventeen billion!) star iterations. Once it unfreezes, you'll be getting about 1-5 FPS as the sector map then tries to draw 7,000+ links.

In short, we have three problems:

Route planning is not asynchronous: plotting a 25,000ly course will take a very long time by UI interaction scales. Even if it's only a few seconds, that's far too long to be blocking the main thread for. This will probably be one of the easier problems to resolve, as we can simply create a new SectorCache and ensure the sector generation code is properly thread-safe. Communication back to the UI will be more difficult but not impossible.

The route planning algorithm is too slow: Planning a route is an O(N^2) operation, which is a problem when your N is 188,000 stars. This is caused by two things:

• The broadphase is not as tight as it should be; it generates far more sectors than it will ever need and does radius tests that ultimately don't even matter. To make matters worse, this particular route is actually the best case for the broadphase - a diagonal route causes the broadphase to be three orders of magnitude more expensive. The ideal goal here is to switch to the Bresenham line algorithm to cull entire sectors before they're ever generated.
• We do somewhere between 17,000,000,000 and 35,000,000,000 iterations, even with the best-case broadphase algorithm. Nodes are unordered in the active set, and we iterate through every single star in the "tube" of stars the broadphase selects regardless of where we are in the tube; to make matters worse, only the stars we've picked for a path are removed from the active set, meaning that we're looking at true N-squared complexity cost. The loop also uses actual vector lengths for all comparisons when squared-length comparisons are possible, so we incur the cost of several square roots per iteration. I have a few ideas of how to fix this, mostly involving writing the active set in a semi-ordered fashion from the broadphase and shrinking the active set as we move along the "tube" towards the target system.
• The planner uses a "conservative" algorithm, looking for the shortest individual links regardless of overall route time; while this is intentional (and correct) due to game mechanics, we will likely be visiting the hyperjump times, ranges, and fuel consumption algorithms soon as part of a greater rebalance. It would be useful to have a "greedy" algorithm that plots a long-distance route that finds an optimal set of jumps based on fuel consumption, time cost, and distance travelled. Additionally, a greedy algorithm enables larger iteration steps over the set of nodes, which means we can drop nodes from the active set faster.

Drawing the route is too slow:

• We must clip the list of routes on the Lua side before they're ever submitted to ImGui, as iterating and drawing a 7,000 jump list (although possible thanks to @Gliese852's hard work on caching jump data and performance) is responsible for 5/8ths of the entire 220ms frame time.
• Likewise, the sector map view on the C++ side does not do any clipping of interstellar links in a route, so it's drawing all 7,000 links each frame, with a two-vertex buffer upload and draw call for every single link. This is madness and is responsible for most of the remaining frame time, at 2/8ths of the total.

None of these are insurmountable problems, not are they particularly pressing to the average user (numerous elements of the game discourage long trips across the galaxy, none more than the time it takes to scroll to SagA* and the difficulty in locating where it's supposed to be without reading the system definition file) but I would like to see them fixed nonetheless!

In terms of priority, I'd like to fix the various rendering and culling issues with the SectorMap first as part of a greater push to drawing system labels in PiGui and improve the overall rendering. Clipping the list of jumps on the Lua side should also be somewhat trivial as they're all a fixed size.

[The-EG]

Good stuff. I think some of this was brought up when we first put it together, but never really addressed, so it's good to have something written down at the very least.

In regards to the routing algorithm, it's Dijkstra's shortest path. I had never even heard of it before Impaktor mentioned it and the implementation I did was basically what was described on the wikipedia page. In other words, I think the algorithm does quite well, but I wouldn't be shocked if there are better ways to implement it (vectorization would be really cool). And, I'd always love to hear about alternatives.

In terms of conservative/greediness, there's actually a few ways to look at it.

Currently the cost considered is the time each jump takes. This could easily be flipped to fuel, which I think would result in the much fewer jumps but end up taking much longer (in game time). I would expect this option to be of most interest to someone wanting to make an insanely long route, as fuel is probably more important than time.

But, that still isn't a greedy algorithm. To get the absolute least number of jumps would probably be another question all together.

[Zireael07]

Why Dijkstra and not A? You can run A from both ends (bi-directional A*), which should probably give you better performance especially on long routes.

[The-EG]

Why Dijkstra and not A? You can run A from both ends (bi-directional A*), which should probably give you better performance especially on long routes.

In short, it was good enough at the time. I don't think we were really concerned with mapping out huge routes back then; I'm actually a bit impressed it actually worked at all from Sol to SagA*. And, I don't recall any alternatives being suggested at the time either.

That's why I mentioned it...if we are going to be overhauling the sectorview and optimizing things, it's a good time to revisit the routing algorithm as well.

Edit: skimming over some info I found on Google, it also sounds like Dijkstra is considered to be a special case of A*. I'd have to actually sit and read through it all to understand the exact differences, but I have to wonder what the actual difference in the end would be.

[Web-eWorks]

Personally, I don't really care which variant of graph traversal we use - Djikstra's and A* are both equally bad when you're iterating over 100,000 nodes that you will never be able to reach, or that you've already visited. The problem with our current setup is that we do expensive, unvectorized math just to reject 95% of our "sea of nodes" with every iteration; we don't have issues like obstacle traversal that require backtracking, and while our hyperspace distance algorithm is a bit weird, it still generates relatively-linear paths towards the destination.

[fluffyfreak]

The method SectorView::DrawRouteLines is very far from optimal, so I can quickly improve that.

[Gliese852]

My version. Set the size. (e.g. 50 ly) if the distance between the ends is less than this size, we count as usual. if more, we take the middle, take the closest system to it, and thus divide the route into two segments. Repeat recursively with segments.