Stellaris Dev Diary #149 - Technical improvements

[Guraan]

Thanks. I wrote the paper for my bachelors degree in graph theory a couple years ago and had little use for it recently, this rant is lot's of fun to me. I wish I could look into this in depth. Just for the fun and educational value, I doubt that I could produce anything that's actually helpful.

Well we are not really finished tbh O;P

That's (but not only) why that "lookup tables" are separated:

Its the minimum way to travel, and it is heavily used from scripts both in generation and later on O

 

[Guraan]

Go back to what hapends with a pathfinder like the a* without any optimal heuristics? and since we are lock-step we need 1 and the same solution

 

[Guraan]

Plus L-gates, gateways and wormholes may not be used at all (IIRC, gateways and wormholes could be switched off via sliders on galaxy generation options screen, Ls wouldn't appear w/o Distant Stars and mods could add their own set of junctions that would require own patch table), so patch tables are addition to the core table.

And there we have 2 more gold stars O

It would find shortest routes from the start system to all others, as it expands through shortest of available (but not yet used) lanes. Is that how you calculating basic table?

Yes but would it be an a*? or would we just call it a BFS?

Edit: And no thats not how we calc the basic table, would take too long time

 

[Guraan]

well sure, but not BFS as BFS, thats why its called a* O;P

Edit: difference between "pure" BFS->Dijkstra->a* is still very small

 

[Guraan]

When this update goes through, will it require Mojave for Macs? I know that this may seem like a dumb question, but some newer titles (looking at you Imperator) require OS 10.14. I personally am very squeamish about updating, as I have heard that I will have trouble with my 32-bit apps, and I hope that this will not force me.

that is actually quite fun to read, since apple is dropping the 32bit O not sure what macosx sdk we are compiling against but i do not think we changed anything there

 

[Moah]

Please don't remove them. Removing a feature is by far the worst thing a developer can do. This was the exact reason I almost stopped supporting Stellaris; FTL features got removed.

That'll teach me making jokes, I guess.

With all things considered, the move to 64-bit and all, will save games from 2.2 still work in 2.3 or not?

As always, we try to preserve compatibility, but can't guarantee anything.

 

[Moah]

@Guraan
Could you get a significant boost by ditching the necessity to calculate optimal routes for long distances? If we're sending fleets half across the galaxy most people won't even notice if the calculated routes was a couple jumps longer then an optimal one. To use a real world map as example, if you wanted to go from Stockholm to Berlin, according to google maps you're using a route through Jönköping. But if we came up with one through Göteborg instead it wouldn't be too bad. Only local routes, for example within a cluster would need to be optimal.

We have thought about doing "clusters" pathfinding, but haven't had time to look into them.

 

[Guraan]

@Guraan
Could you get a significant boost by ditching the necessity to calculate optimal routes for long distances? If we're sending fleets half across the galaxy most people won't even notice if the calculated routes was a couple jumps longer then an optimal one. To use a real world map as example, if you wanted to go from Stockholm to Berlin, according to google maps you're using a route through Jönköping. But if we came up with one through Göteborg instead it wouldn't be too bad. Only local routes, for example within a cluster would need to be optimal.

In some cases yes we can get away with it, not sure if it will boost performance in large since it will just be in a few cases we do a full pathfind, its just alot of them lol

yes it is. To be honest still don't know why you need all distances for jour pathfinging algorithm.
I understands that distances are needed for AI to strategize: what systems are of interest, how far is enemy fleet etc.

Well first of all, you underestimate the amount of systems that want to know the distance between them and X, yes we cheat here usually and do not care about hyperlanes/wormsholes at all.

but for pathfinding all you need is a data structure with all connections and distances. It could be different data structure (simplified), that is updated less comon than "distance cache" which could be then updated with less priority.

Nah, you need to check if a connection or node is valid for that jump (in these cases), that check is usually more expensive in reality than the constant C is in theoretical computer science due to mem lookups and other cache misses lol

 

[Guraan]

That's not what I meant. From what I understood from the previous dev comments it's not the pathfinding itself that's taking it's toll but frequent and rather expensive cache invalidations.
but if the cache would consist of clusters which would receive independent invalidations they would be cheaper to recalculate. With the possible drawback that t he global picture would nolonger be guaranteed to be optimal.

Nah, i do not c the pathfinding as a major culprit in performance right now, there is some conditions that will recalc it excessively but there we also have some logic for doing a lazy recalc from script.

To stick with my example, if your optimal route goes through the Jönköping clustet and some system ob the route becomes blocked you can either do a detour within the cluster or avoid it completely by going via Göteborg.
But wich one of those is actually best is not that important if they are at least close enough. What matters is that you on!y invalidate part of the cache.

Yes i love the comparison, but the problem still remains.for a 1000 star system a optimal heuristics might be worse than none at all.

If we assume a galaxy size <= ~1000 and number of empires <50 than static per-empire distance matrix will take
2 bytes per distance in jumps * 2 bytes per star id of the next jump * 1000^2 (number of stars in galaxy) * 50 (empires) ~ 200 Mb. Totally worth it to store them if this is actually a bottleneck, isn't it?

Distance is actually 4bytes (do not ask me why). Storing them is no prob, doing a lookup in that huge ass table "might" give some expensive cache misses on the other hand.