Of course that still leaves cases where the pathfinder will fail to choose the shortest route.
You missed my point, or I didn’t explain it effectively.
You seem to be aware that what you're proposing doesn't address the cases where stabilized lagrange points cause a different set of systems to have a shorter route than when only direct JP to JP travel is considered. But when it is pointed out to you, your tone is dismissive.
You could have just as easily been explicit in saying that the LP cases would still be unaddressed, but that you still consider your proposal an improvement in that you believe (if I am reading it correctly) there would be fewer edge cases and that it would improve overall performance.
Yes, the full quote says that explicitly:
Of course that still leaves cases where the pathfinder will fail to choose the shortest route. However, it is an improvement because those cases will be rarer and they will involve smaller distances in trip length. And there will be compensating improvements elsewhere.
I have only debated the statement by Droll:
The effective travel distance does potentially change thanks to the aforementioned lagrange movement. But if you are simply concerned with the absolute distance between two JPs, that is static. Since we are talking about pathfinding still the former is more important than the latter for our purposes.
I did not intend to be dismissive of this, only to state that the pathfinder requires the distances between JPs, whether or not it also considers LPs, and that these can be cached. As I considered the LP step to be self–evident, and as the cache I mentioned didn’t have anything to do with it, I didn’t happen to mention it specifically. My explanation would have been better if I had.
Dealing with LPs correctly is actually much harder than it looks, just as finding the correct path from a JP to a planet is harder than it looks. I’ve posted elsewhere about my own explorations into a pathfinder that finds a very precise solution to the problem, so that fleets never have to play catch–up to planets. Here’s a demo video:
http://db48x.net/Aurora/four%20different%20ways%20of%20plotting%20a%20course%20in%20Aurora-2021-08-07_18.33.48.webmThe code I wrote for this finds not just the correct direction for the fleet to fly, but precisely how long it will take to reach the destination. If properly integrated into the long–distance pathfinder, it would enable the pathfinder to find exact solutions for segments that go to LPs as well as planets, and it would enable that pathfinder to calculate the precise trip length and the fuel required to complete it. It is fully generalizable to nested orbits, elliptical orbits, hyperbolic orbits, etc.
Of course it has drawbacks. My specific implementation is fairly fast, but suffers from numeric stability in some cases. The time it can take is only roughly bounded; it can take over a second to find a solution in those cases. The problem cases are primarily those where the JP is close to the orbit of the destination planet. The demo video cleverly avoids showing of cases where it performs poorly. I consider my implementation to be fairly good for the single week–end of effort put into it, but it clearly needs more research.
By combining this type of in–system solver with a full–featured long–distance pathfinder, the game would have perfect navigation: every fleet could plan its entire route perfectly, and know ahead of time whether it has enough fuel. The AI could benefit greatly from that. So could the player, as a matter of fact!
The downside is that this would be significantly slower than the existing pathfinder, and I’m not as confident that caching would eliminate the problem (because the cache would never have useful information about segments that target a moving destination, and every route has at least one of those.)
However, I have suggested a lesser solution that ignores the difficulties of LPs, as well as the difficulty of the final segment of a long–distance route where the fleet is flying from a JP to a planet. If the pathfinder ignores those, then the pathfinder will never take up excessive CPU time and will generate routes that in practice rarely surprise the player. Today virtually every game encounters situations involving loops in the system graph, where the path finder is very likely to produce the wrong solution. The solution I have suggested solves that common case while leaving the less common cases involving LP shortcuts unsolved. However, it does so in a way that leaves open the possibility of future improvements in that direction.
I think that this solution, plus judicious caching, would be not slow the game down at all, and that we would all enjoy the benefits.
I cannot guarantee that Steve would find it enjoyable to write the code, however. That’s merely a matter of taste.
