Pathfinding and Bypasses

[The Founder]

One of the things that was pointed out in DD #149 was that one of the big performance bottlenecks with the game is pathfinding, particular with Bypasses (Gateways, Wormholes, L-Gates).
And it really is a hard problem. Harder the real-life pathfinding even. Because the RL guys do not have to deal with Teleporters being strewn all over the map!
I thought a thread seperate from all other performance discussion would be helpfull.

Here a bit of already mentioend background information:
"There was other topics, which pointed out that L-Gates and overall wormholes and other gates are also a major player for performance loss, because of the path finding.
Were you also able into looking this one? Is the patch also addressing this?"

We haven't worked on that (yet). Unfortunately this is a problem for which we don't have a good solution yet.
Our issue is that we have a cache that contains the distance from any system to any other system, and when you add/remove bypasses or systems we need to recalculate this cache. This is further compounded by the fact not everyone has the same access to every bypass.
We have the "basic" cache which is only for hyperlan distances, and then we have a cache patch that adds distance through gateways accessible to that country. This country specific cache needs to be emptied whenever a bypass gets added, and towards the end game, every country starts building gateways, leading to mass cache invalidations and reconstructions.
Add to that that, invariable, the pathfinding itself becomes more complicated because you get many more ways to reach the same point.
Until we find a genius idea, i'm not sure we can do much to improve that. I've suggested removing gateways/wormholes/l-gates but for some reason nobody likes it when i suggest we remove features. Go figure!

Ooh i really love this pathfinder rant going on, but just to raise the level a bit:
- Each fleet has different stances that need to be considered if a system is a valid point or not.
- Each system may or may not give you access to pass by ftl inhibitors and your diplo standing with that empire.
- Each wormhole has an requirement that they have to been explored.

Side note: The underlying hyperlane distance cache is ofc just a upper triangle since distance is bidirectional so space wise it should be n(n - 1)/2, still to big to be in L1 cache for huge galaxies O;P

It is worth noting that the game knows 4 kinds of bypasses:
A the restore and buildable gateways
B wormholes
C the L-Gate
D Mod created Bypass Networks. It was overread by many, but the L-Gate introduction added mod support to the bypass System. You can create your own network with your own rules.

The A and D networks are the big issues.
Class B is not much of an issue. It is little more then a Hyperlane you can not scan through. While you need a tech, eventually everyone will get that tech. Indeed non-Default Empires often ignore the need for Wormhole tech. The default State will be that everyone has access to every Wormhole. That time when you do not is really the exception, rather then the rule.

Class C can be a bit harder, but IIRC only up to 10 L-Gate Systems can spawn and all pathing has to happen through the L-Cluster Terminus System.
So that would be the equivalent of <10 extra Hyperlanes being added to the map (one from each L-Gate Sytem to the Terminus). Not a big addition given the literally hundreds of stars in the bigger galaxies.

Class A will just add geometrically increasing amounts of connections to a select few System. While that makes it easier to reach anywhere with a few jumps, it also massively increases the number of possible paths to check from that System. Most Systems have 2-4 Hyperlance connections.
What it does is (pathfinding wise) is add a Hyperlane connection between this System and every other System with a Gateway.
If there are already 10 Gateways active, adding one to a system will add the equivalent of 10 new hyperlane connections to the Sytem. Bringing the total to 12-14. And a 10th Additional Hyperlane to all the other Systems with Active Gateways. At only 11 Gateways, we already talk about 55 effective additional Hyperlane conections.
At 20 Gateways, it is 380 effective additional Hyperlane conections. And the 21st gateway would add 20 paths to the newly minted gateway System.
And 20 Gateways would not be a lot in a 1000 Star Galaxy.

And with D you have no idea how it would affect pathfinding, because the rules are unclear.
And it is not even only one D. There can be many D-class networks.

Possible Solution:
Part of the reason I started this, is to talk about a possible solution I came up with.

First, we have the static network.
That would first include the Hyperlanes. But it will also include the B and C class networks eventually.
B Class are a pretty clear addition to the static list. As I said, eventually everyone will be able to pass them. So having the ability to use them is basically the default state. If you really can not afford the check, you could even just have 2 static networks - one for those with the tech and one for those without it.
C Class is true for the same reason. Once Activated, the network is "open source". And the extra paths are marginal (<10 to the Terminus System, 1 for <10 Systems).
D Class I will ignore for now.

The thing is that we do not (nessearily) need to know wich path through the gateway network is the fastest. We only need to know if the path through any 2 gateways is faster then using hyperlanes. So you would calculate two paths:
a) a path using only the static network
b) a path from the start and end points to the nearest useable A Class Gateway respectively. The distance between any 2 gateway Systems is 0 or 1 jump.
And then you just pick wichever path is shorter.

A advancement would be to calculate both in paralell. If you do that, you would not even need to calculate each of them to it's end. If one finishes, the other can stop the moment it would end up with a longer path.
If you know that the Static Network can get you there in 7 Jumps, once your gateway path reaches at least 8 jumps it is pointless to even look at it anymore.

Now the big issues is that this can not support D Class networks as they are now. They either have to be removed or at least be reduced only allow Networks similar to B and C Class. Stuff that can be integrated into the Static Network.

 

[苏白@夢璃花]

Maybe get rid of gateways/wormholes, and buff star base and late game sublight travel speed, so we can actually stall the enemy until reinforcement arrive. We also have jump driver for tactical choose, so I think it should solve the path find problem

 

[Black_Shade]

Maybe get rid of gateways/wormholes, and buff star base and late game sublight travel speed, so we can actually stall the enemy until reinforcement arrive. We also have jump driver for tactical choose, so I think it should solve the path find problem

You'd have to dramatically increase in system speed and cooldown between jumps. At least a factor of 5 times faster fleet movement. Even on smaller galaxies it takes 20 years for a fleet to traverse from one side to the other. Removing gateways would honestly just make me stop playing, the fleet speeds are beyond ridiculously slow and it's why the midgame in Stellaris is such a drag.

 

[BlackUmbrellas]

Maybe get rid of gateways/wormholes, and buff star base and late game sublight travel speed, so we can actually stall the enemy until reinforcement arrive. We also have jump driver for tactical choose, so I think it should solve the path find problem

I'd strongly disagree with gutting wormholes and gateways. If the issue is path-finding, there are probably other solutions.

Maybe instead of being a "default path-finding option", they could operate like Jump Drives? That is to say, they have to be intentionally used, possibly incurring some cost or debuff while doing so?

 

[Olterin]

Maybe instead of being a "default path-finding option", they could operate like Jump Drives? That is to say, they have to be intentionally used, possibly incurring some cost or debuff while doing so?

This wouldn't exactly help that much, since every AI fleet that moves ever would still have to calculate (or have access to) the possible gateway distance to then decide to use it or not. Unless you want to stop the AI from using gates entirely?

 

[The Founder]

Maybe get rid of gateways/wormholes, and buff star base and late game sublight travel speed, so we can actually stall the enemy until reinforcement arrive. We also have jump driver for tactical choose, so I think it should solve the path find problem

"I've suggested removing gateways/wormholes/l-gates but for some reason nobody likes it when i suggest we remove features. Go figure!" - Moah

Wormholes are the last part that needs cutting. You have to go out of your way to make Wormholes a problem.
L-Gates are close second.
I already explained why in the opening post.
It is really only the modable Bypasses that are a problem.

I'd strongly disagree with gutting wormholes and gateways. If the issue is path-finding, there are probably other solutions.

Maybe instead of being a "default path-finding option", they could operate like Jump Drives? That is to say, they have to be intentionally used, possibly incurring some cost or debuff while doing so?

That would cut down AI useability and player useability. And I am unsure if that would even be a benefit, as you just turned "has connection to node" it into a "node is inside area" check.
The greatest saving might be in reducing the need for Gateways to cover ground. But you would still capture just about as many gateways from everyone else.

The only useable way would boil down to reinventing the old Womrhole Stations/drive System. And they cut that out because pathfinding there is even harder.

 

[BlackUmbrellas]

This wouldn't exactly help that much, since every AI fleet that moves ever would still have to calculate (or have access to) the possible gateway distance to then decide to use it or not. Unless you want to stop the AI from using gates entirely?

That would cut down AI useability and player useability. And I am unsure if that would even be a benefit, as you just turned "has connection to node" it into a "node is inside area" check.
The greatest saving might be in reducing the need for Gateways to cover ground. But you would still capture just about as many gateways from everyone else.

The only useable way would boil down to reinventing the old Womrhole Stations/drive System. And they cut that out because pathfinding there is even harder.

Let me clarify.

Currently, you can direct a fleet to go to a gateway and get a little dropdown menu of valid destinations to tell them to go to.

I am suggesting this be the only way they work- unless you specifically tell a fleet to use a gateway, they ignore them (the same way that you have to specifically tell a fleet to jump).

AFAIK, the AI has some sort of logic for when it decides to use the Jump Drive as opposed to normal pathfinding, and Jump Drives don't cause the same pathfinding lag.

So if you made Gateways work the same way Jump Drives do- by which I mean they need to be activated, might have an associated energy cost or fleet debuff, and are normally not taken into account for pathfinding- they could be integrated into the AI's behaviour without needing to involve all these extraneous pathfinding checks.

 

[DreadLindwyrm]

Let me clarify.

Currently, you can direct a fleet to go to a gateway and get a little dropdown menu of valid destinations to tell them to go to.

I am suggesting this be the only way they work- unless you specifically tell a fleet to use a gateway, they ignore them (the same way that you have to specifically tell a fleet to jump).

AFAIK, the AI has some sort of logic for when it decides to use the Jump Drive as opposed to normal pathfinding, and Jump Drives don't cause the same pathfinding lag.

So if you made Gateways work the same way Jump Drives do- by which I mean they need to be activated, might have an associated energy cost or fleet debuff, and are normally not taken into account for pathfinding- they could be integrated into the AI's behaviour without needing to involve all these extraneous pathfinding checks.

I do not like that idea - I *like* having fleets select the most efficient way to use gateways to cross the galaxy without having to individually direct my fleets through gateways. Even more so when my muster point is not with my shipyards, and I could have dozens of small fleets trying to reinforce my main fleets and either using the gateways or taking *years* to cross the galaxy by normal means.

Even more so when the AI can afford to individually direct fleets, but I, as a player, don't have the time or finely divided attention to do this to multiple dozens of individual ships at once.
Especially if I'm using gateways to attack two sides of an empire at once, or to attack two or more members of an alliance at the same time.

 

[Marconius]

I actually think fleet stances might be the biggest issue. Border access and gate statuses don't change that often, so those could be cached; but if you have your fleet set on evasive, they will avoid enemy fleets, meaning they need to check where enemy fleets are (which changes constantly) AND where they have vision (which also might change), which means maintaining a cache becomes pretty much pointless. There's no real way to get around this with the current evasive stance, because whenever a fleet sees a system they suddenly realize they cannot enter, they MUST calculate a new path.

I think ignoring this, you only have to deal with relatively static things, being border access, tech, gates being opened, etc. These change relatively rarely, so they could be cached... except as the devs point out, they need to be cached for EVERY empire, whenever ANY empire changes their border status, or changes the gateway network; which near the end of the game becomes fairly frequent overall.

The way I'd approach the problem (and they may already be doing this) is I'd add 'clusters' of stars that all create sort of a zoomed-out pathfinding network with a lot fewer nodes, including gateways and wormholes; do a 'rough' pathfinding first, which could be more easily cached, then when the fleet is actually inside the cluster, do fully dymanic, not-cached pathfinding, which can properly respond to enemy fleet positions and such. This might lead to some weird situations where an enemy fleet blocking a chokepoint would get in the way of really long paths, basically resulting in a fleet making it all the way there and then going "oh crap, I can't go this way!" with no path around the blockage locally; on the other hand, since enemy fleets do move, in many cases an enemy fleet in the way of a long path might be long gone by the time the fleet actually gets there. This setup would actually be in line with the new sector implementation too, where each sector is 4 jumps from a capital; navigation could similarly be broken down to 'local' within 4 jumps, and 'global' which is based on pre-generated (or periodically updated) clusters with a diameter of ~4 jumps.


EDIT:
As an additional note, all the tiny reinforcement fleets are probably putting a MASSIVE strain on the pathfinding system as well. Most empires have 1-4 major fleets, but then dozens of tiny one-ship reinforcements, which all require their own pathfinding. If anything, maybe changing the way reinforcements work might be a major improvement to performance?

 

[The Founder]

The way I'd approach the problem (and they may already be doing this) is I'd add 'clusters' of stars that all create sort of a zoomed-out pathfinding network with a lot fewer nodes, including gateways and wormholes; do a 'rough' pathfinding first, which could be more easily cached, then when the fleet is actually inside the cluster, do fully dymanic, not-cached pathfinding, which can properly respond to enemy fleet positions and such.

I thought about this approach. I can not remember where I first saw it, but it did cross my mind. Maybe it was in a Dev Diary to Planetary Annihilation?

But once again, gateways will end up just meaning that every cluster is connected to every other (via the gateway network), negating any possible gain.

As an additional note, all the tiny reinforcement fleets are probably putting a MASSIVE strain on the pathfinding system as well. Most empires have 1-4 major fleets, but then dozens of tiny one-ship reinforcements, which all require their own pathfinding. If anything, maybe changing the way reinforcements work might be a major improvement to performance?

That is what the caching is for. And paths only need to be re-evaluated once the caches are cleaned and rebuild.

Let me clarify.

Currently, you can direct a fleet to go to a gateway and get a little dropdown menu of valid destinations to tell them to go to.

I am suggesting this be the only way they work- unless you specifically tell a fleet to use a gateway, they ignore them (the same way that you have to specifically tell a fleet to jump).

AFAIK, the AI has some sort of logic for when it decides to use the Jump Drive as opposed to normal pathfinding, and Jump Drives don't cause the same pathfinding lag.

So if you made Gateways work the same way Jump Drives do- by which I mean they need to be activated, might have an associated energy cost or fleet debuff, and are normally not taken into account for pathfinding- they could be integrated into the AI's behaviour without needing to involve all these extraneous pathfinding checks.

How does this mathematically work out for a saving, without ending up with a AI totally inept at using them?
Where do you manage to reduce the actuall Pathfind and network creation load during this?
What are you sacrificing for it?

 

[Marconius]

I thought about this approach. I can not remember where I first saw it, but it did cross my mind. Maybe it was in a Dev Diary to Planetary Annihilation?

But once again, gateways will end up just meaning that every cluster is connected to every other (via the gateway network), negating any possible gain.

Not quite true: you still don't have a gateway in every SYSTEM, so what would happen is on the first step the fleet would just go to a gate and jump to whatever cluster they want to go to; in the small-scale local space gates aren't an issue. This is still a massive improvement over having to calculate multiple paths through multiple gates to determine the exact shortest route between two specific systems.

 

[OwlOfSpace]

I do not like that idea - I *like* having fleets select the most efficient way to use gateways to cross the galaxy without having to individually direct my fleets through gateways. Even more so when my muster point is not with my shipyards, and I could have dozens of small fleets trying to reinforce my main fleets and either using the gateways or taking *years* to cross the galaxy by normal means.

Agreed 1000%, I would rather lose some performance over such convenience in late-game with Gateways.

The way I'd approach the problem (and they may already be doing this) is I'd add 'clusters' of stars that all create sort of a zoomed-out pathfinding network with a lot fewer nodes, including gateways and wormholes; do a 'rough' pathfinding first, which could be more easily cached, then when the fleet is actually inside the cluster, do fully dymanic, not-cached pathfinding, which can properly respond to enemy fleet positions and such. This might lead to some weird situations where an enemy fleet blocking a chokepoint would get in the way of really long paths, basically resulting in a fleet making it all the way there and then going "oh crap, I can't go this way!" with no path around the blockage locally; on the other hand, since enemy fleets do move, in many cases an enemy fleet in the way of a long path might be long gone by the time the fleet actually gets there. This setup would actually be in line with the new sector implementation too, where each sector is 4 jumps from a capital; navigation could similarly be broken down to 'local' within 4 jumps, and 'global' which is based on pre-generated (or periodically updated) clusters with a diameter of ~4 jumps.

Clusters were how the new galaxy creation was going to be, but dropped for unknown reason(s). But yeah, I think they really should go back and re-consider that as it will make the maps much easier for players and AI to read while creating a lot more interesting chokepoints for strategic values.

 

[Eelectrica]

+1 for gateways. I'll cop a bit of slow down if that's the deal.
I love having my ship yard centres deep in the empire with gateways for rapid deployment.

 

[Bankipriel]

Great breakdown of the situation.

I think I might be okay with the removal of gate networks if a more comprehensive & scaled set of jump-drive technologies were introduced----namely, the eventual possibility for jump-drives that function at any distance within one's own empire & with no cooldown.

The gates are cool and all, but if we had more powerful jump drives, they would be irrelevant and a waste of influence. Keep the massive cooldown and damage penalty for jumping around enemy systems, which seems like a pretty good balance of utility/cost right now, but let them function ad infinitum within our own space.

If there's just no way to make gates function well due to the rapid scaling complexity of pathing, maybe the best option really is to get rid of them and provide an alternative means of rapid transit through end-game technology---something that *doesn't* require insane pathing calculations.

If an alternative means of end-game rapid transit were provided, I would *gladly* give up gates in order to once again enjoy 1000 star games with x1 planets & max empires.

 

[f98alda]

If, as Marconius said, reinforcement fleets are a big issue, couldn't we have an "experimental subspace navigation"-type option for reinforcing (that is, remove the ship from the map and let it magically join the fleet some time later)?

 

[The Founder]

I thought off some more ideas that will preserve a lot of properties of the network, while trying to limit or avoid the whole compelxity thing.

Option 2: Point to point gateways.
Another idea, is a rather old one. I think it dates back to the early days of the FTL rework. You turn gateways into semi-permanent point-to-point connections. A bit like wormholes, except one endpoint is build and the other is selected by the gateway owner.
Rather then each Gateway linking to every other Gateway, each gateway only links to one, freely selectable endpoint System - but only within a Empires borders.
Such a "channel" would not be traversable by enemies, but would also vanish if the System is occupied (or suffers anything else that would cancel the gateway access).
If you add soemthing like a channel creation time, we would be unlikely to move it too close to the enemy for risk of loosing our beachhead.

We usually get more Gateways not because we want more gateways, but because we want to move the nearest endpoit of the network closer to "where it needs to be". Or because we capture Gateways. But when we do that, we usually do not want to keep the previous gateway connections.

The basic ideas of not being able to go into enemy space and not being attackable via it would be maintained.
While still cutting down on the geometrical increase part of it effectively.
The only reason we can not mod it in right now, is that we can not add a proper UI or teach the AI to use it.

Option 3: Restoration vs Activation
This idea would add a 3rd state to each Gateway, for a total of:
Ruined, Restored, Activated.
But you could propably cut Ruined out with this.

A Empire can have any number of Restored Networks in their borders, but only a limited amount of active gateways. And only active networks can be pathed through.
The maximum of active networks might be a function of Empire size, similar to Station Cap. That way bigger empires could afford slightly more Active networks, without going current-day crazy with them. It would also solve the issue of conquering gateways - unless you got capacity left or a willing to turn a existing one inactive, it would be just a piece of metal in space.

Option 4: Galactic Gateway Limit
Under this, gateways could not be constructed everywhere. Only certain "gateway Sytems" allow the construction of those stations (or have a station to reactivate).
Systems could be "tagged" for Gateway ability, similar to how you tag Systems for Precursor Anomalies currently.
System with few connections (like dead ends) should propably be prefered. That would keep the base-branching factor of those Systems low.

Pro:
- You could limit and shape the Gateway network during Galaxy creation
- You could keep most code
- Gateaways would become part of the "Stellar Geography". Currently they are mostly a way to bypass it, but with that they would become
- A example for this should be modable

Con:
- Being unable to built them exactly where we want, players might be prone to actually (re)build more gateways then they need. Just in hopes of getting that "perfect" distance
- A feasible number of gatways for a large galaxy might still be more then pathfinding can handle. So unless you get some performance out of the suddenly predictable nature, I do not see it improoving majorly

 

[The Founder]

If, as Marconius said, reinforcement fleets are a big issue, couldn't we have an "experimental subspace navigation"-type option for reinforcing (that is, remove the ship from the map and let it magically join the fleet some time later)?

I am not so sure reinforcements are actually an issue. The devs said the actually pathfinding happens on a cached map. A case of pre-computing the travelcost between any 2 nodes.
The big issue is cache invalidation and rebuilding, as all the stuff (gateways, occupation of FTL inhibitors) keeps changing regulary in the late game. If it is a reinforcement or main fleet that does, does not really mater for this.

That being said, it might be usefull to use the whole "MIA" approach for other reasons. Like not loosing units to recaptured outposts all the time.
It would require a major rework, as it currently picks a endpoint that is fixed - but the fleet would have a moving endpoint.

 

[DreadLindwyrm]

I
We usually get more Gateways not because we want more gateways, but because we want to move the nearest endpoit of the network closer to "where it needs to be". Or because we capture Gateways. But when we do that, we usually do not want to keep the previous gateway connections.

That might be how you use them, but I *usually* build gateways on, or by my shipyards and on my main sources of trade (so that everything is covered by a trade depot).
I *always* want to keep my existing gateways because I've built them for a purpose additional to moving things close to the frontlines.

A Empire can have any number of Restored Networks in their borders, but only a limited amount of active gateways. And only active networks can be pathed through.
The maximum of active networks might be a function of Empire size, similar to Station Cap. That way bigger empires could afford slightly more Active networks, without going current-day crazy with them. It would also solve the issue of conquering gateways - unless you got capacity left or a willing to turn a existing one inactive, it would be just a piece of metal in space.

This would depends on how many active gateways you can have, but I tend to want a lot of gateways, again for trade network purposes, and to unify my shipyards.
Limiting this is, for me, a step backwards.

It also has the potential to make it difficult to sensibly reinforce an ally via their gateways.

 

[BeauNiddle]

I thought off some more ideas that will preserve a lot of properties of the network, while trying to limit or avoid the whole compelxity thing.

The complexity is not the number of nodes it's the fact the nodes can deactivate due to closed borders. A static map that never changes is trivial to deal with.

Your solution just added even more ways the nodes can deactivate and thus increased the issue.

The only real solution is to have gateways only work within an empire and to never allow you to use an allies / neutral gateway. But that negates half the point of gateways.

A solution that only ever adds improvements is much easier to deal with than ones that drop connections. The dropped connections are an issue because the only way to deal with it is to go back to the base static map and then add all gateways all over again.

 

[Dëzaël]

Option 2: Point to point gateways.

I thought of this while reading the thread. This is the solution I find should have the better efficiency/practicality ratio.

but only within a Empires borders.

However I thought that it might be possible to ask another empire via diplomacy to open a channel by dedicating one of their gates or building a new one. To keep the ally side of their interest, and allow for strikes further in the galaxy. Maybe also adding a cost to reconfigure a pair of gates, to not go crazy with cheapo "one gate to rule them all" building cost cutting strategies, and recaching each time again. Influence cost maybe.