.png){kind=avatar}
An unstable sort algorithm is one that gives non-deterministic ordering of equal elements.
Likewise an unstable path finding algorithm is one that gives non-deterministic routes when encountering equal cost nodes.
I assume Stellaris uses A* for its pathing, in which case, the open list should be changed from an unstable queue to a stable queue, thereby making the search stable.
Without this, we end up with stuff like this;
Collinear trade routes taking different paths:
and this;
Trade route & patrol route following different paths:
When this occurs (and it occurs frequently), it's a micromanagement nightmare.
If you can't, or won't, make the search stable, then rethink the trade route system.
(Though ideally you should do both)
1) Explicitly assign fleets to patrol a trade route, so they don't have to be manually routed & so their path is guaranteed to match that of the trade route.
2) Make trade stations only route to the nearest friendly trade station that's closer to the homeworld, not to the homeworld directly.
This should:
- simplify your code (collating all trade routes that pass through a system will now be implicit),
- improve the interface (no more massive amounts of duplication in the 'Trade Capitals' window.
- improve performance (shorter routes, less rerouting calculations when network topology changes)
- avoid infuriating bugs like the ones above
Likewise an unstable path finding algorithm is one that gives non-deterministic routes when encountering equal cost nodes.
I assume Stellaris uses A* for its pathing, in which case, the open list should be changed from an unstable queue to a stable queue, thereby making the search stable.
Without this, we end up with stuff like this;
Collinear trade routes taking different paths:
and this;
Trade route & patrol route following different paths:
When this occurs (and it occurs frequently), it's a micromanagement nightmare.
If you can't, or won't, make the search stable, then rethink the trade route system.
(Though ideally you should do both)
1) Explicitly assign fleets to patrol a trade route, so they don't have to be manually routed & so their path is guaranteed to match that of the trade route.
2) Make trade stations only route to the nearest friendly trade station that's closer to the homeworld, not to the homeworld directly.
This should:
- simplify your code (collating all trade routes that pass through a system will now be implicit),
- improve the interface (no more massive amounts of duplication in the 'Trade Capitals' window.
- improve performance (shorter routes, less rerouting calculations when network topology changes)
- avoid infuriating bugs like the ones above
