Some thoughts on autoroute

Suggestions
1

In my current game, using autoroute is a problem in a couple ways.

Here’s a portion of my map to highlight the issues:

image
image887×643 64 KB

The Jaabeb problem

I need civs and autoroute to path to Jabalpur (bottom right).
Which means I can’t block autoroute in Jaabeb.

But I also need them to path to Bega (bottom left), and autoroute prefers the BEB-JAA-BEF “shortcut” over the BEB-BEC-BED-BEE-BEF path, despite the fact that the “shortcut” is actually more distance to travel.
So I mil-restrict the JAA-BEF jumppoint. That solves the problem for civ traffic, and makes autoroute work fine with commercial fleets traveling between ZZZ and either of those places. It does make civ traffic directly between BEG and JAA/JAB use a much longer route than it could, but that’s a problem I’m willing to overlook at this point.
The problem is that I often need to move military fleets between ZZZ and BEG.
And obviously mil fleets don’t care about the “mil restricted” setting of a jumppoint.
So every time I give orders to a mil fleet to move through here, I have to remember not to use autoroute, because it will use the much longer “shortcut” via JAA.

Solutions?

a) Make autoroute find the shortest distance rather than the fewest hops (but there’s a lot of additional complexity here; see the Fibamar problem below).
b) Add a “restrict all” setting for jumppoints to restrict both commercial and mil traffic in the same way as the “military restricted” does now.
c) Add settings for jumppoints that explicitly (and only) block autoroute in the same way as the setting for systems.
d) Some elegant combination of the above.

The Fibamar problem

This one seems harder to provide a simple solution for.
The shortest path from my HW (Zzzyzzyvaa) to Fiad (top left) depends on where you are actually going in Fiad.
The route via Fechenheim (top center) to the FEC-FIA jp is 17.4bkm.
The route via Bega (bottom left) to the BEG-FIA jp is 23.7bkm.
So, the FEC route gets you to Fiad faster.
But here’s the JP layout in Fiad:

image
image315×444 2.74 KB

Crucially, the FIA-BEG jp (1) is much closer to the Fibamar jp (2) than is the FIA-FEC jp (3).
So much closer that the total route from ZZZ to FIB is much shorter via BEG (28.8bkm) than via FEC (36.8bkm), even though the route from ZZZ to nearly all locations in FIA itself is shorter the other way.

So, providing optimal pathing is not as simple as “don’t go through this system.”
Ideally, autoroute pathing would just use the shortest distance every time.
But the above example shows that autoroute can’t know the shortest distance to a given system until it knows where you are going after entering that sytem.
Possibly you could revise the autopathing logic to correct the entire order list every time a new destination is added.
For my example here, if I use autoroute to path from ZZZ to FIA, it would initially choose the route via FEC.
But if the next order I add is to transit to FIB, autoroute would realize that the BEG route is shorter, and would revise the entire order list to use that route.

But I wouldn’t want autoroute to redo the entire path if I had given some other order along the original route.
For example, suppose my original order list is to move from ZZZ to Febiana, transer MSP to a station there, then move to FIA.
If at this point I add a further order to move to FIB, autoroute should not revise the entire path from ZZZ to use the route via BEG, because that would eliminate my stop in FEB.
Succinctly: whenever a destination is selected via autoroute, the algorithm should find the shortest allowed path to that destination from the last destination in the order list that is not a JP or LP, and revise the order list to use that path.

But I don’t know, that sounds like it might be hard.
I’m not sure if it is worth the code complexity or not.
I’m sure other players encounter these same pathing issues, probably on average more than I do, since I tend to explore very slowly and my runs rarely last longer than 100 years.
In my current game I am in year 74 (TN start, default population) and I have just 63 known systems. (And a handful of those I learned about via espionage.)
From discord discussions I know there are plenty of players that play way past 100 years and push their exploration frontier much further than I do.

1 Like
2

Just make a order template that goes from ZZZ to BEG and another going BEG to ZZZ for your military to use?

1 Like
3

Thanks, but a single set of templates to handle ZZZ-BEG and BEG-ZZZ military traffic doesn’t solve the problems I outlined in my post. It’s merely a workaround for the first example I described, and only for fleets traveling to and from those two specific systems.

I use order templates extensively. Very, very extensively. But they aren’t the answer for this.
Part of the problem is LP usage. Templates lock in the entire path regardless of LP position at time of order execution. Dynamic LP usage in 3.0 should solve this problem.

But what I’m asking for is not just a way to manage the current examples that I used to highlight the problem. I’m asking for autoroute to be more useful overall, so that I don’t have to think about when I can or can’t use autoroute and when I have to use templates instead.

4

As implemented, blocking the whole system or blocking the entire jump point don’t always work well for the reasons you described.
I think a good solution would be a way to block auto-route from one JP to another in a given system. You’d open system view and block in-system routing from JP1 to JP3. Traffic would still use the system and use all the JPs, they’re just blocked from the JP1-JP3 path (which is maybe a 7 billion km journey across a super-system in this imaginary example).
In the meantime, we have the power to move/delete JPs and delete systems until auto-route provides the optimal route, if it bothers you.

5

I guess this should go into “suggestions” section, but what if we could specify a template rout, just as with template orders now, and than autoroute will use said template rout instead of plotting a new rout each time? Such set of predetermined routes will solve the issue without need for restricted systems/JPs workaround. Should CIVs be using it, or going their own ways on their own risk, is an open question though (I can clearly see commercial pilots doing whatever they want).

6

Good news:

image
image499×179 17.5 KB

2 Likes
7

Intriguing.

It would solve the problem.

I don’t like the idea of having to create a template for each pair of systems I want to override the autoroute logic for.

And remember to create new ones when I discover a new system. One pair for each of the systems that I need to overwrite autoroute to/from the new system.

And then update all of the affected templates every time a loop is created.

8

For the last point as someone who tries to minimize overlaps on the map it would just become part of my ritual for “oh shit, new loop who dis?” type situations.

9

Same.
But the scope of this new part would easily dwarf the rest of what I have to do when I get a new loop.

10

Why are you all trying to think of the most convoluted solutions, when the simplest shortest distance between two JP would do?

The algorithm already exists, too.

Just keep it simple.

11

Nobody is “trying to think of the most convoluted solutions.”
There are different ways to think about problems, and we are all offering our own thoughts, based on our own perspectives and experiences with the game.

Furthermore, only Steve knows the actual structure of the existing code, and that will be a significant factor on the amount of effort required to implement any given change. Therefore it seems eminently worthwhile to discuss multiple possible solutions, rather than just assume that some solution that seems the simplest in theory would actually be the solution that Steve prefers to implement.

1 Like
12

There is also the consideration that the solution that is often easy for us to contextualize isn’t necessarily the computationally easiest one to do so.

IIRC finding the shortest distance the “simple way” is in the NP hard class of problems so there’d be a performance cost to keeping it simple and not a small one either.

2 Likes
13

Also, the shortest route given orbital positions at the time of departure isn’t necessarily the shortest route once orbital movement and dynamic LP calculations are considered.

14

Fastest way to Alpha Centauri Starting from Earth?

image
image489×535 37.3 KB

image
image469×290 8.56 KB

image
image424×311 7.97 KB

Fastest from Earth to Alpha Centauri A I or B I?
Yep, via V1216 again.

image
image725×685 47.3 KB

15

It is also worth noting that, while a “slightly more expensive” algorithm may be fine for players making orders, the same logic would be used by AI pathfinding and a more expensive algorithm leads to considerably longer turn processing times. Especially since the AI fleets reevaluate their logic frequently while the player usually sets orders and leaves them alone unless something happens.

16

The only way to see it being viable is to have it be a player initiated process. Kind of like a “refresh pathing” button that does a one-time recalculation for everyone at the players behest.

Expensive, but would maybe curb the worst of the problem while not negatively affecting normal gameplay. I’m already used to saves taking a long time in the low minutes so maybe that would be an acceptable compromise.

This of course does not solve the LP problem as that is too dynamic for something like this to help with.

17

I think there may be a closed solution to this.

JP location is fixed. And orbital locations are “fixed” in so much as only the relative position along a fixed trajectory shifts in real time, so you can precompute a look up table for a fixed number of points. Either 8, maybe 16 increments along the path, or something more dynamic where it just calculates which JP is closest for what sections of the period.

That puts the computation at the time of system generation, and even if you really did it for every body in the system, rather than filtering out asteroids and comets, it would still have a small size on disk.

Doesn’t account for Lagrange Points, but pathfinding is always difficult.

18

Seems like the calculations to determine which of the precomputed points the body is currently closest to would be nearly as expensive as just computing the distance from JP for the body’s current location.

19

No, that should be same sort of math as looking up the day of the week from epoch. Which is very cheap.

20

I think a compromise system could solve both problems at once.

Instead of routing by number of systems, autoroute would use a JP-to-JP distance map, every jump point’s real-space distance to every other JP in its own system, updated whenever a new JP connection is discovered. Autoroute would then find the shortest total travel distance to the target, not the fewest systems crossed.

LPs complicate that math, since their position moves. Rather than fold them into the distance map itself, I’d handle them the same way 3.0’s Dynamic LP already does: while a fleet is in a system, check whether that system’s LP offers a shortcut right now. LPs wouldn’t factor into the overall route calculation, that stays based purely on the JP distance map.

That’s why I’m calling it a compromise. It won’t always be the true shortest route at any given moment, but it’s a clear improvement over the current fewest-systems approach, without the added complexity of solving for LP positions across a whole multi-hop route.

For updating routes mid-journey, it could reuse the same check timing as Dynamic LP orders, recalculating at the same intervals, both for LP shortcuts and for any new shortcuts the JP distance map has picked up.

1 Like