What’s going on with the path finding?

[100thMonkey]

I had stopped playing for a while, and now started a new game with v.1.0.5.8 beta. And I've just encountered something strange, that I had seen before but swept under the rug... until now.

I want to retrofit my fleet, which is on manual, and currently at my capital (Maredon 1), in the Maredon system. If I click on the selection panel retrofit button, the AI wants to send it first to the Kareda system, and then to the Murkdor system, where it will be retrofitted:

Retrofit path.png (247.25 KiB) Viewed 1495 times

Why this circumvoluted trajectory?

If instead of retrofitting I click somewhere near the Murkdor system, with the same fleet being selected, I get the following straight line trajectory:

Move path.png (227.63 KiB) Viewed 1495 times

So again, why all the detours for the retrofit? Not only is the straight line more efficient (time and fuel wise), but it should also be simpler for the AI.

Am I missing something?

[arvcran2]

Have you selected the individual ships to find the shortest jump range?

It could be that the pathfinding uses the lowest common denominator jump range. The logic is different for moving to a Galactic coordinate, not sure what it does with jump ranges.

[100thMonkey]

Have you selected the individual ships to find the shortest jump range?

It could be that the pathfinding uses the lowest common denominator jump range. The logic is different for moving to a Galactic coordinate, not sure what it does with jump ranges.

No, I didn't try the individual ships. Two points:

- What do you mean by "uses the lowest common denominator jump range"?
- Going to a colony for a retrofit IS moving. Finding the best place to retrofit is a whole other thing, requiring a different "logic". But finding the shortest path between where the fleet is and where it's going shouldn't be different for simply moving versus for retrofitting. The starting point and the destination are the same in both cases, it's only WHY the fleet is going there that changes.

[Thineboot]

[...]
Am I missing something?

Looking at your images there is only one thing that comes to my mind: if you still have the save switch to top view. Will the starting location be displayed as if it is within the upper right nebula? If so, the pathfinding may also only check the top view at which point the escape the nebula routine may kick in. In that case Kareda seems to be the shortest route within the nebula and everything afterwards is a result of this first decision the algorithm makes. And in this case it seems to be obvious, that it's a faulty decision based on a faulty assumption the fleet is in a nebula while it's beneath it. But all this is based on assumptions on how the perspective may change...

[arvcran2]

- What do you mean by "uses the lowest common denominator jump range"?

If there are different hyperdrives having different jump ranges, I suspect the fleet will choose the shortest of the set as the standard maximum jump range for the fleet.

I assumed that there is no nebula in the direct path from A to B.

From what I underestand, the AI, by default, will opt to path via systems. So if it cannot reach destination 'B'', it tries to find the series of jumps that gets it there by jumping to systems. What you did was avoid jumping to the 'in range of jump system of path chosen' and jumped in jump range to a Galactic coordinate.

I think that explains it?

[100thMonkey]

- What do you mean by "uses the lowest common denominator jump range"?

If there are different hyperdrives having different jump ranges, I suspect the fleet will choose the shortest of the set as the standard maximum jump range for the fleet.

I assumed that there is no nebula in the direct path from A to B.

From what I underestand, the AI, by default, will opt to path via systems. So if it cannot reach destination 'B'', it tries to find the series of jumps that gets it there by jumping to systems. What you did was avoid jumping to the 'in range of jump system of path chosen' and jumped in jump range to a Galactic coordinate.

I think that explains it?

I did some other tests, and it looks as if the "weird way" (to paraphrase Frank Herbert in Dune) occurs only when the destination is in a system. I moved my fleet in deep space, and from there, ordered it to go to the colony where the retrofit was to be done, and the path was a straight line!

So, as you wrote, it seems that in those situations at least, the AI will opt to path via systems.

But why?

Why that decision? It reminds me of the infamous Microsoft's "it's not a bug, it's a 'feature'"...

So maybe it's not a "bug" per say, but it still doesn't make sense to me!!! If the game is able to figure out a direct path when the destination is a "galactic" coordinates, why can't it do the same when the destination is a planet in a system?!?

Why lose all that time and fuel for those detours? Why was the decision made that the AI would opt to path via systems instead of via straight lines? Code performance, at the expense of in-game loss of fuel and time? Or was it something else?

Also, in the past, when I looked at Stellaris and saw that space travel was limited to space lines, that stopped me in my tracks from exploring Stellaris any further. After having tasted DW:U and its unlimited space travel, space lines are way too constraining for me, and tactically uninteresting as well. But this looks to me as a step in the space lines direction. I know we're not there yet, but...

[100thMonkey]

If the going through systems is because of the jump ranges, what happen to those jump ranges when going in a straight line into deep space, for a longer distance than the shortest jump range in the fleet?

[arvcran2]

If the going through systems is because of the jump ranges, what happen to those jump ranges when going in a straight line into deep space, for a longer distance than the shortest jump range in the fleet?

Indeed. I don't know the history of the decision making that progressed to the jumping to systems paradigm. But as you say there is an apparent loop hole. The ships should only be able to jump to maximum jump range ... from there they can make a subsequent jump.

Perhaps there is a bug? I have not tested this recently.

[Thineboot]

The shortest jump range is correct but no ship in that fleet has a jump range that is shorter than their fuel range - there is no orange dash circle.

As for pathfinding weirdness check out [1.0.5.6] [1.0.4.8] Nebula and Pathfinding...

[100thMonkey]

If the going through systems is because of the jump ranges, what happen to those jump ranges when going in a straight line into deep space, for a longer distance than the shortest jump range in the fleet?

Indeed. I don't know the history of the decision making that progressed to the jumping to systems paradigm. But as you say there is an apparent loop hole. The ships should only be able to jump to maximum jump range ... from there they can make a subsequent jump.

Perhaps there is a bug? I have not tested this recently.

I did let the fleet go toward the destination in a straight line (starting in deep space), and it went thought without any (apparent) stop.

If it is a bug, and it is fixed at one point, I hope it will be in the direction of keeping the possibility of going in a straight line, with stops on the way if necessary. And, ideally (from my perspective), the "requirement" to go through systems would be ditched.

The shortest jump range is correct but no ship in that fleet has a jump range that is shorter than their fuel range - there is nor orange dash circle.

As for pathfinding weirdness check out [1.0.5.6] [1.0.4.8] Nebula and Pathfinding...

As I understand it, the jump ranges isn't shown for fleets (only the fuel range, which shows in the screenshot). I don't understand why, since it does for the fuel range (presumably, showing the fuel range of the ships in the fleet that have the shortest fuel range). If that's the case, then why not show the jump range for the ships that have the shortest jump range in the fleet?

And thanks for the link: I'm going to read that for sure.

[Thineboot]

You're right, fleets have no jump line, just an approximated fuel line. Makes some sense as the ships don't have to be at the same location. Still, it would be nice to see where a bunch of ships could meet in one jump... it's just not a circle the same way the fleet fuel range isn't their fuel range either - just test it with a fleet of various different ships. But projecting a circle is easier. Again, I'd understand if it where based on performance limitations but we're talking about one selected fleet in a single player game. If it's not possible to calculate accurate numbers without breaking the game... so it's possible, someone has to find time to write the code and since there are not many programmers...

[100thMonkey]

The shortest jump range is correct but no ship in that fleet has a jump range that is shorter than their fuel range - there is no orange dash circle.

As for pathfinding weirdness check out [1.0.5.6] [1.0.4.8] Nebula and Pathfinding...

While reading that thread, I remembered something. For Civilization IV, Firaxis had made a lot of the code available to modders. Not only data file (XML or others), but actual source code. That allowed for incredible mods for that game. But if I remember correctly, one of the thing they didn't made available was the pathfinding code. Which suggests to me that it's something that is not easy to do, and even less to do well.

So it's probably difficult for Elliot, the lone coder as far as I know, to solve that problem and work on everything else at the same time.

I like the idea of jump ranges increasing with higher tech tiers, slowing space travel because of the required stops. But why not allowing straight line travel, even when starting from and/or going to a system, with stops on jump range limits, followed by restarts and stops, until the destination is reached? It seems to me that it might even be simpler to code than what has been coded for the existing "going through systems" paths... Yes, that code is already done, but from my perspective, it's kind of broken (because of the detours it imposes, resulting in much longer travels requiring way more fuel)...

[Jorgen_CAB]

Technically... ships don't need to jump to systems. But for some reason this is how the AI is made to calculate their jumps instead of just (for the most part), jump in a straight line to wherever they are going at max jump range and then jump again if they need to.

Not sure why they made the decision this is how the AI does it, when there technically is no reason to?

I'm 100% sure pathfinding would even be easier if fleets or ships in general could just jump to the most efficient place and then to its destination from any point in space. But I digress...

[100thMonkey]

Not sure why they made the decision this is how the AI does it, when there technically is no reason to?

Well, maybe there is a reason, technical or otherwise. But if there's one (other than a "non-optimal decision" ), I'd like to know what it is. It might make that game/AI behavior a little bit less annoying.

[rxnnxs]

Maybe it happens because in the System Planets or Moons are between the direct jump line?
The direct jump would be faster Systemwise, but the normal travelling time around the other planets or the sun (that blockades the direct jump line) takes more time than to jump three times, but then directly closer to the station where the ships are retrofitted.


P.S.:
It is anyway a bit weird - regarding jumping and then travelling with normal speed.. but I have also no idea how to do it better.

[Thineboot]

There would be a simple explanation. While we obviously lack the technical explanation in 2022, you could say that navigation in DW2 depends on gravity wells to work precisely. Yes, you can ignore them and just jump into the void like Escape from here but navigation doesn't work that way.

Therefore, the primary goals for a successful jump within the parameters of hyperdrive must be a large enough mass for long distances such as interstellar travel. Suns would guarantee successful jumps while targeting asteroids from outside the system precisely would become a game of chances.
Jumps within systems would work similar but the shorter the distance of the jump itself the less the actual deviation at the end point would be. Same formula with hyperdrive accuracy being a cone. Distance and mass - all those orbs have a diameter, so their mass can be calculated at game start or within game editor, same could be used for whole systems to simplify calculations for interplanetary jumps - would be the parameters.
Thus navigation in empty space could be done but accuracy would become a logistical nightmare no sane captain would order except for emergency jumps like the Escape from here order.



As for pathfinding, if you reduce calculation for interstellar travel to systems instead of 3D coordinates - there are no point to point jumps, it'll always be an estimated jump no matter which hyperdrive you're using, the possible paths shrink dramatically. Since any jump, that doesn't end in deep space, uses orbs as mid points I assume this is how it's done anyway in DW2.

Most of the time nebulas are involved when paths become miscalculated. Nebulas don't have to be big. There are tiny ones, too. I've seen nebulas with the diameter of five suns only visible when zooming in very closely resulting in jumps around the corner because of that.

[Jorgen_CAB]

It is super easy to create an in game roleplay reason for why they jump between systems. The issue is that technically it is shorter and faster NOT to do it. If you micromanage fleets you can just jump into space as that is faster if you need more than one jump to get to places. The reason you generally don't do it is that it is simply micro intensive, but you will on occasions do it, especially if range is an issue.

[Thineboot]

Agreed, but not even that is always true, see Re: [1.0.5.6] [1.0.4.8] Nebula and Pathfinding...

[100thMonkey]

I've posted a bug report of another instance of bad pathfinding I've just encountered :
https://www.matrixgames.com/forums/view ... 6&t=386671

[OrnluWolfjarl]

I've noticed this too. I think it DOES NOT ONLY have to do with nebula. Ships will randomly insert star systems in their routes. The algorithm for this is behaving very weirdly.

Note that there's a known bug, where if you add a star system using the editor, then it messes the pathfinding of all ships in the galaxy, which will frequently attempt to travel outside the galaxy for whatever reason, no matter where you point them to go to.

I think map generation probably has something to do with this.