Pathfinding is based on number of systems. It checks adjacent systems, then the ones adjacent to those, etc., until it finds the destination.
I could base it on actual distance in kilometres, but that would be tricky and hit performance. Instead of checking the small subset of systems required to find a valid path, I would have to check all systems to ensure I found the best option.
Yep. As a software engineer myself, this did not escape my attention.
Its also not entirely correct unless I take into account orbital movement, because if a journey takes a few months then the shortest route right now may not be the correct one.
Quite true. However, orbits are periodic, and it is quite easy to calculate the minimum and maximum distance a planet can ever be from the jump points in the system. The distance between jump points never changes, so the variation only has to be taken into account for the segments at the beginning and the end of the route. If you find two routes where the ranges overlap, just flip a coin
Actually, when I say that it is quite easy, I mean that it is quite easy for circular orbits. I concede that it could be horrible for ellipses; ellipses are generally horrible. I suspect that it is easy (that there is a closed–form solution). If so then it will be a solved problem and probably a quick search will turn it up.
Probably you can take the solution for a circle and correct it using the cosine of the difference between the orientation of the ellipse and the bearing from the jump point to the center of the ellipse, plus an offset from the center of the ellipse to the focus. But I would look it up rather than doing the algebra myself.
All this is going to add a lot of performance overhead and movement is already the phase the takes the longest.
I could be wrong, but does the game actually recalculate these routes every tick or subtick? I suspect that it only calculates them when giving new orders to a fleet, either when the user uses the autorouting to order a ship to go to some other system, or when the AI gives a fleet new orders because it has completed the existing orders. Even with thousands of civilian ships there should only be a few that need new orders in any given tick.
And while it does seem like more work to search the whole graph rather than just a convenient subgraph, A* pathfinding on a graph with thousands of nodes should not be a big performance concern. That’s cheaper than A* pathing in an RTS, where units just have to get from one edge of the map to another. The original Starcraft had a map size of 256*256, meaning it was doing A* on a graph with 65,536 nodes, for example. I don’t recall the frame rate suffering when you gave your units orders…
Also, do you cache these routes at all? If not, then simply caching the fastest route the first time you compute it is easy enough. Invalidation needs to happen sometimes when you explore a jump point (or otherwise discover a new link between systems), but only when discovering a new link to a system you already knew about.
You can also cache the minimum and maximum distances between jump points and planets as well; you would only need to do those cosines once.
I think having a basic system that you can influence when you need to is better than a more complex system that slows the game down and isn't needed for the vast majority of the time anyway.
I don’t disagree with this philosophy.
However, I also believe that if we are clever then we can generally squeeze more work out of a computer than we would at first expect. If we are clever enough, we can have our cake and eat it too. In this specific instance, I think that we should be able to have nicer automatic route planning without slowing the game down.
