• We have updated our Community Code of Conduct. Please read through the new rules for the forum that are an integral part of Paradox Interactive’s User Agreement.

Stellaris Dev Diary #149 - Technical improvements

Hi everyone, this is Moah. I’m the tech lead on Stellaris and today I’m here to talk about the free 2.3 "Wolfe" update that will be arriving together with Ancient Relics, and what it brings to the table in terms of tech.

Stellaris is going 64 bits.
People have been clamoring for this for a while now, and various factors have led us to finally do this for this patch. I should temper your expectations though: while many have claimed that this would be a miracle cure for all their issues with Stellaris, the reality is somewhat more tame.

What does it mean?
The one solid benefit is that Stellaris is no longer limited to 4gb of memory, and won’t crash anymore in situations where it was reaching that limit. For people who play on huge galaxies, with many empires, many mods or well into 3000s, this will be a boon.

In terms of performance, though, it doesn’t change much. Without drowning you in technical details, let’s just say that some things go faster because you handle more data at once, some things go slower because you have more data to handle. In the end, our measurements have shown no perceptible difference.

Finally, the last effect of switching to 64 bits is that the game will no longer playable on 32 bits computers or OSes. We don’t think this will affect many people, but there you have it.


What about Performance?
I know that’s everyone’s favourite question, so let’s do our best to talk about it. First, let me dispel some notions floating around in various forums: Stellaris does use multithreading, and we’re always on the lookout for new things to thread. In fact between 2.2.0 and 2.2.7, a huge effort was made to thread jobs and pops, and it’s one of the main drivers of performance improvement between these version.

Pops and jobs are indeed what’s consuming most of our CPU time nowadays. We’ve improved on that by reducing the amount of jobs each pop evaluate. We’ve also found other areas where we were doing too much work, and cut on:
  • Ships calculating their daily regeneration when they’re at full health
  • Off-screen icons being updated
  • Uninhabitable planets doing the same evaluations as populated planets
Why do these seemingly pointless things happen? Well, we generally focus on getting gameplay up and working quickly so that our content designers can iterate quickly, and sometimes things fall through the cracks. Some of these systems are also quite complex and the scale of the new code is not so easily apparent. Sometimes, not limiting the number of targets is good enough because you’re not doing much but then, months later, someone adds more calculations or the number of objects explodes for unrelated reasons, and suddenly you’ve got a performance issue.

Modifiers
One thing that sets Stellaris apart from other PDS title is how much we use (or abuse) modifiers. Everything is a modifier. Modifiers are modified by other modifiers themselves modified by other modifiers, and sometimes by themselves. It’s quite hard to follow, and leads to every value being able to change at any time without your noticing.

“Why don’t you just compute jobs when a new one appears?” has often been asked around these parts. Well, a short answer to that is it’s really hard to know when a new job appears. You can get jobs from any modifier to: country, planet, pops. Each of these can get modifiers from ethics, traditions, perks, events, buildings, jobs, country, planets, pop, technology, etc.

Until now we were trying to calculate modifiers manually, forced to follow the chain in its entirety: when you recompute a country modifier, you then calculate their planets modifiers, and then each planet would recalculate their pops modifiers. Some of our freezes were just that tangled ball of yarn trying to sort itself out.

NexRiPkna2utTqAzF9H0DEjOCwHVsI4EejYO-vMQMh6QwUB-_uP7dXmpjkwXzOOKoiwDqkSzd9tlLmN3DlFN2R06A62od6XxWm8xh99XRDfRFRP3vVj42GBIaDaXSK7jjyKdS39b

This is our modifier flow charts. It’s not quite up to date, but gives you an idea of the complexity of the system (Unpolished because it’s a dev tool, and not made for the article).

No More!
For 2.3 “Wolfe” we have switched to a system of modifier nodes, where each node register what node they follow, and is recalculated when used, following the chain itself. We have modifiers that are more up to date, and calculated only when needed. This also reduces the number of pointless recalculations.

This system has shown remarkable promise, and cut the number of “big freezes” happening around the game (notably after loading, for example). It has some issues, but as we continue working with it, it’ll get better and help both with performance and our programmers’ sanity.

So, what’s the verdict?
In our tests, 2.3 “Wolfe” is between 10% and 30% faster than 2.2.7 right now. Hopefully it’ll stay that way until release, but the nature of the beast is that some of these optimizations break things and fixing the issues negate them, so we can’t promise anything.

IuIGuQ4cXPvjCEMWG_AowiNIFXhzpsPIcphmCVJD79vQqVMqUeZCqCoVfDlWDNZ3YNkAScYAJh2ebft947YsqoOhG7A_4pNBWxjZ6L9se5lkEEImNYZ4uOpTMWj-amEiwSYdirpd


Measurements provided by @sabrenity , using detailed info from the beta build. It’s worth noting the “SHIPS_SERIAL” purple line has since been eliminated.

AI
Another forum favorite, we have done some improvements to the AI. First, with @Glavius ’s permission, we’ve used his job weights to improve general AI job distribution. We’ve also done the usual pass of polish and improvements, and of course taught the AI how to use all our new features.


What else is new?
We’re also getting a new crash reporter that will send your crash report as soon as they happen rather than next time you start the game. We’ve improved our non-steam network stack for connectivity issues, etc.


All right, enough of my yammering. This has turned into a GRRM length novel, and even though there are many more areas we could cover, we’ll just turn this for your perusal.
 
Last edited:
  • 1
Reactions:
pathfinding algorithms
Pathfinding in arbitrary environment is.. just pain. Look at the zoo of Internet routing protocols. So many solutions, so few problems solved. With all the money invested in it.

I'm clearly not as good at algorithms as Spartakus, but I definitely believe that the root issue is one of technical debt. If they're still using a code base that has not been updated since removal of the other propulsion systems, their pathfinding is likely using structures that were not optimized for starlanes.
Hyperlane travel existed in Stellaris from the very start. The issue is about arbitrariness of whole system - nodes, connections, sets of connections and restrictions - anything could be added or removed during gameplay, at any time. It all must reliably be handled via backend code (aka "hardcode"), to support modifiability of Stellaris.
 
Yikes! OK, but don't you still have a huge improvement by using a table for each of these networks? In an n-sized galaxy you only need n-sized tables for each network as opposed to an n*(n-1) sized table to cache all distances. And even in small galaxies the number of stars should be a lot bigger then the number of Gateway networks. So even if you're having M-Gates, O-Gates and Y-Gates it doesn't make a big difference.

Of course I don't really understand how your cache patch works or how moddable gateway networks really are, so I'm propably talking a bit to much out of my A-Gate here.

In the base game setup, where wormholes and L-Gates are hardcoded, and always allow two-way transit, couldn't those be treated as hidden hyperlanes in the first table? Since the distance is 0 between all "normal" gateways, you'd only need a single n-by-1 table with the distance/path to the nearest gateway from each system.

I mean that precludes the possibility of additional gateway networks with their own distinct rules, but that seems like a big simplification.
 
Pathfinding in arbitrary environment is.. just pain. Look at the zoo of Internet routing protocols. So many solutions, so few problems solved. With all the money invested in it.

Heh. It all depends on what you're trying to do. The issue here is not optimal pathfinding per se, but doing so given a certain (to us unknown) time budget. Probably in ms.

Hyperlane travel existed in Stellaris from the very start. The issue is about arbitrariness of whole system - nodes, connections, sets of connections and restrictions - anything could be added or removed during gameplay, at any time. It all must reliably be handled via backend code (aka "hardcode"), to support modifiability of Stellaris.

Sure. I'm not denying that. I'm simply pointing out that the code base behind pathfinding originally had to support 3 different systems, with varying levels of difficulty. That means that they couldn't optimize the code for hyperlanes. Now, if they wanted to, they could. But we have no idea about the amount of technical debt needed to overcome in order to optimize it. At least hyperlanes aren't as difficult as warp drive...
 
If you're going to be working on job weights anyways, it would be nice if we could designate individual jobs as essential instead of having to mark one (and only one) entire chunk of jobs as high priority. For example, if I need some amenities then I'd like to mark two or three clerk jobs as essential, not all 20.

Also, the priority function seems to be treated as a very slight suggestion. If I need to micromanage then I'd like it if my efforts were treated with a lot more weight.
 
Wormholes are practically Hyperlanes you need to open. To be more precise, Wormholes like Hyperlanes and unlike gates connect exactly two systems. and you can't block access. I'm not sure how exactly the existing Hyperlane table works, but I think wormholes could be treated like hyperlanes and thus be included.

No, the more complicated issue is closing borders and your access to a gateway being blocked by another empire. This could really result in a need to throw away both tables. I'm afraid I can't make any realistic asumption on wether or not this is an improvement without knowing how the existing code works, what it is used for and what causes it to update currently.

Edit: and yes, all L-Gate connect to the L-cluster, from where you could again reach any other L-Gate, so its like Gateways A -> L-Gate + L-Gate -> B
For what its worth, I've always thought the difference between a hyperlane-only game and a non-hyperlane-only game was that the former galaxy can be thought of as a planar graph and the latter a non-planar graph. This was made even simpler with 2.0 (may WHD rest in peace). Why natural wormholes aren't treated as hyperlanes, I don't know since hyperlanes also can be non-traversable.

I don't have Distant Stars, so I can't comment about L-Gates, but normal Gates certainly mess things up since that static non-planar graph is now mutable.
 
If the system is hidden from the galaxy map, players won't be able to select it to travel to. You could then setup a flag on the system to block AI empires from traveling to it until the event chain is completed. This might also better "regionalize" the precursor event chains much in the same way that fallen empires are placed on the map.
Most event chains that create a system create it close to the players who finished the chain, though.

I'm clearly not as good at algorithms as Spartakus, but I definitely believe that the root issue is one of technical debt. If they're still using a code base that has not been updated since removal of the other propulsion systems, their pathfinding is likely using structures that were not optimized for starlanes.
We did rewrite and optimise it for the new system.
 
Are you saying that it is possible to mod different types of Gateways, so that they are not interchangeable? The same approach could be used, but you would have n! different checks to make by Spartakus's algorithm where n is the number of different types of Gateways.
And then you're back to a good ol' A* I think.
 
Does this mean that the minimum system requirements will change?

I'm using a dual core cpu and 4 gbs ram and so far I run the game just fine, will this update make it worse for me?

P.S. I am running a 64 bits windows!
 
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
 
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
Is this implying that wormholes are being treated as hyperlanes?
 
Is this implying that wormholes are being treated as hyperlanes?
Its a jump to another node just as anything else ofc, just other restrictions if you can use it or not O;)
 
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.

I'm not sure I'd classify it as a rant, but it is certainly something of interest to many of us.

Also, isn't 'lane explored' in the case of wormholes just another case of 'can I use this hyperlane'?

Can't we use sector creation in maps to help this, though? As I recall, the starmap generation algorithm was changed between 2.0 and 2.2 to create natural sectors (in graph terms, cliques or near-cliques), and then these are connected. If this is true, then the graph can simplify to larger nodes (groups of stars) and the pathfinding simplified to get to the right natural sector, then to the star inside of that sector. Gateways again complicate this, but the complication is less.

I just keep recalling my algorithms professor's comment that the general case of many graph problems is NP-Complete, but no real problem is ever the general case. There's always something you can do to simplify. I'm not faulting the devs here; the caveat with never dealing with general cases is that each case has a unique solution.

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

True enough. And thank goodness that hyperlanes are bidirectional... directed cyclic graphs are the worst. ;)
 
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

I am sorry, I never wanted to start a rant.
from what you say, these rules further restricts nodes that are accessible which should speed up the algorithm (less nodes, faster calculations)
slow down might be bcs of accessing those additional data (rules, which nodes to eliminate from the graph).
I still don't know why you need a cache with all distances for all stars and why pathfinding is not calculated on the fly.
can you explain it?
 
Last edited:
I am sorry, I never wanted to start a rant.
from what you say, these rules further restricts nodes that are accessible which should speed up the algorithm (less nodes, faster calculations)
slow down might be bcs of accessing those additional data (rules, which nodes to eliminate from the graph).
I still don't know why you need a cache with all distances for all stars and why pathfinding is not calculated on the fly.
can explain it?

Generally speaking, caching frequently-accessed values is a way of increasing space complexity (your memory footprint) to decrease time complexity (the speed of the algorithm). In simple terms, looking something up is almost always faster than running an algorithm.

Let's say I have a lookup table that is good for 20% of my values. Also, let's say that my algorithm takes 5ms to run, and the lookup takes 1ms to run. The lookup table has saved me 0.8 ms on average, 20% of my calls are answered by the lookup (0.2 * 1ms) and 80% of my calls are answered by the algorithm (0.8 * 5ms), summed to 4.2ms as the expected value.
 
I'm not sure I'd classify it as a rant, but it is certainly something of interest to many of us.
Matter of perspective, there is a few previous threads about both pathfinder and 64bit here at the stellaris forum.

Also, isn't 'lane explored' in the case of wormholes just another case of 'can I use this hyperlane'?
Yes they are, its the `can i use` that becomes a vital factor, but treat them as the same for now O;)

True enough. And thank goodness that hyperlanes are bidirectional... directed cyclic graphs are the worst. ;)
Lol yes they are, but i can think of alot of fun things to do if they where lol

I am sorry, I never wanted to start a rant.
never be sorry to start good "rants" O;P

I am sorry, I never wanted to start a rant.
from what you say, these rules further restricts nodes that are accessible which should speed up the algorithm (less nodes, faster calculations)
slow down might be bcs of accessing those additional data (rules, which nodes to eliminate from the graph).
In theory yes, in practice you will have to account for the cpu cache misses that nowdays is a vital factor. (the rules are quite complex and gives alot of overhead even that those is cached)

I still don't know why you need a cache with all distances for all stars and why pathfinding is not calculated on the fly.
can you explain it?
Hehehehe will answer that question day after tomorrow, it would spoil a bit of the challenge O;)
 
Last edited:
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!
Maybe get rid gateways/wormholes, and buff star base and late game sublight travel speed, so we can actually stall the enemy until reinforcement arrive. We can also keep jump driver to have tactical choose, I think it should solve the path find problem
 
Last edited:
I am sorry, I never wanted to start a rant.
from what you say, these rules further restricts nodes that are accessible which should speed up the algorithm (less nodes, faster calculations)
slow down might be bcs of accessing those additional data (rules, which nodes to eliminate from the graph).
I still don't know why you need a cache with all distances for all stars and why pathfinding is not calculated on the fly.
can you explain it?
If you just needed a single path for a single fleet you would indeed be right that calculating on the fly would be fastest. However, my best guess is that we need dozens, by the late game hundreds of paths to be calculated, possibly every tick. On for every seperate fleet or civilian ship. So an algorithm that takes several milliseconds is out of the question, we'Re aiming for microseconds. Hence lookup-tables.

Generally speaking, caching frequently-accessed values is a way of increasing space complexity (your memory footprint) to decrease time complexity (the speed of the algorithm). In simple terms, looking something up is almost always faster than running an algorithm.

Let's say I have a lookup table that is good for 20% of my values. Also, let's say that my algorithm takes 5ms to run, and the lookup takes 1ms to run. The lookup table has saved me 0.8 ms on average, 20% of my calls are answered by the lookup (0.2 * 1ms) and 80% of my calls are answered by the algorithm (0.8 * 5ms), summed to 4.2ms as the expected value.
Problem is, that the tables need to be up to date, so you've got an overhead for keeping the tables fresh.
 
Generally speaking, caching frequently-accessed values is a way of increasing space complexity (your memory footprint) to decrease time complexity (the speed of the algorithm). In simple terms, looking something up is almost always faster than running an algorithm.

Let's say I have a lookup table that is good for 20% of my values. Also, let's say that my algorithm takes 5ms to run, and the lookup takes 1ms to run. The lookup table has saved me 0.8 ms on average, 20% of my calls are answered by the lookup (0.2 * 1ms) and 80% of my calls are answered by the algorithm (0.8 * 5ms), summed to 4.2ms as the expected value.
Ok, but ...
this cache (all distances) is recalculated each time new node is added (so for each distance pathfinding algorithms multiplied by huge number), and in later game it is frequent, so some time gained at first is lost later (and you can feel the slow down in late game)

Additionally if the cache consist of only distances from any star to any star how this data is useful??
it is not a path through selected stars (nodes) only distance.
It is not every path through every node bcs it is "bad idea" ? or not.
and even if it is a path through some nodes, even if there are multiple paths from A>B, some of nodes on those paths could be restricted for this fleet
so no viable paths
then you calculate from scratch.
or maybe it is resolved differently

shouldn't cache consist of distances only for node connections (hyperlanes and wormholes) ? and then used by pathfinding?
 
Maybe get rid gateways/wormholes/l-gates, and buff star base and late game sublight travel speed, so we can actually stall the enemy when your main fleet go to war
No, thank you. They're fine, and can be improved.

I think this would also raise a level of outrage, maybe not as high as 2.0, but still a noticable amount. Especially since L-Gates were one of the selling points for Distant stars, and Wormholes/Gateways were a sort of mid/lategame compromise for getting rid of Warp/Wormhole. You don't want to strip even more out.