Stellaris

An in-depth discussion of the pop system, its impact on performance, and possible solutions.

TL;DR: The pop-based performance problems probably stem from treating pops as "agents" – as individuals. By treating them as numbers instead, more pops won't equal slower game.

In 3.0, Paradox introduces some changes to pop growth. One of them was to introduce an empire-wide growth penalty for each pop grown. This, in large part, was done to reduce the overall number of pops in the late game as a performance increasing measure. However, it has brought with it some weird effects like it being virtually impossible to fill an Ecumenopolis (not to mention Ring Worlds) because they show up too late so by the time you get one you have enough pops that they grow at a glacial 1 pop per 3 years per planet.

The goal of this post is to explore how we could change the pop system so that a large number of pops is no longer a performance problem. Because of this, I will be using numbers and assumptions as if this new growth limit did not exist. This also makes the analysis easier, as planets are now entirely independent of each other in growth rate.


A high-level analysis of the current system

Since I don't work at Paradox and don't have access to the source code for Stellaris nor profiler results (and I'm not about to go off trying to profile a compiled binary – decompiling manually as I go), all I have to go on is descriptions of the system. I will therefore provide only a high-level analysis using asymptotic notation. I'm sure Paradox profile their builds a fair bit, so they'll know if I'm focusing on the right areas or not with this.

Pops and jobs – runtime analysis

TL;DR: The month tick gets slower the more pops there are – probably O(n2) and Ω(n√n).

We know that every month tick every pop essentially looks around and says "is there a better job I could be doing?" This is the root of all (performance) evil.

How this (probably) works is that every pop on a planet has to look through every job on a planet and determine:
a. Can I switch to this job,
b. how much would I produce in this job, and
c. should I switch to this job.

A is a simple filter and a good pruning step (robots can't do specialist jobs so there's no point checking, and specialists can't do worker jobs without first bing unemployed and demoting, etc). B is a simple calculation, just adding some bonuses to a base production. C is a little more involved, but likely involves a comparison with the current holders of those jobs to see if this pop would do it better.

This gives us a runtime estimate of O(n*k*j) per planet, where n is the number of pops on a planet, k is the number of different jobs, and j is the number of pops holding each job (so technically an array of numbers). You might have noticed we're essentially ignoring step a here, but that would be maybe roughly a factor of 1/2 to k, and since we're using asymptotic notation we can ignore constants. Similarly there's probably a constant of (<1)*j as we'd stop early once we decided to switch, but this would go away in a stable economy. Looking closer at j we notice it's really n/k, as the number of pops holding a job is on average equal to the number of working pops divided by the number of different jobs they can take. Since we're doing this for every job it doesn't matter if we add the real k different numbers or the average k times. This gives us a total runtime of O(n*k*n/k) = O(n2)

That isn't great. If we give up some guarantees and/or are clever we can reduce the need to check every pop it's up against. By instead assigning pops based on their traits directly (essentially in this case "filling jobs with pops" rather than "choosing a job for every pop") we can reduce this to a per-planet estimate of O(n*k), which is significantly faster since k rarely passes about 10 while n can be >100. By compromising even more and partially pre-sorting the jobs list before going down the list of pops we can get that to maybe something like O(n*lg(k)), but since k never goes much beyond 10 (and lg(10) is about 3) that doesn't really win us that much.

The absolute best you could do so long as you have discrete pops treated like "agents" is O(n), in which every pop only considers one job and chooses that one (or uses some pre-programmed priority list based on its traits, where jobs are struck off as they are filled).

I can't give a definitive answer, but my guess is that the runtime of this would be O(n2) and Ω(nk) (that means essentially "at least n*k but at most n2).

If we want to, we can try to express this purely in terms of n. The number of different jobs on a planet tends to grow somewhat related to the population. At first you only have 1 or 2 pops and 1 job (colonist). At 3 or 4 pops you might add a roboticist, etc. In the late game (which is what we're really interested in here) you start to reach about 10-11 jobs and 100+ pops. Overall, the square root of n is a decent approximation. That gives O(n2) and Ω(n√n). This can be off, though, if you build diverse planets or your planets grow beyond ~200, so remember that Ω(nk) is the real estimate, even if Ω(n√n) will be usually off by less than 50% in the late game.

Read more:  Stellaris needs luxury resources - here's some ideas.

The problem

The size of the calculation thus increases with the number of pops present on a planet. This is the root of the problem. As the game progresses and more pops are born this gets slower and slower quite quickly. Thankfully, the n2 applies per planet. Each planet can be calculated independently (potentially in parallel, although that is it's own technical discussion), as pops don't consider jobs on other planets. This is bad news for something we want to happen quickly (like the month tick), and it makes sense that Paradox wanted to reduce the total number of pops to better performance.

It is likely that there is a certain "stickiness" to pops that have a job already in order to decrease the load. Not all pops will reevaluate every tick, potentially only when something significant changes on the planet. This would improve performance quite a bit (though not asymptotically).


A proposal: ditch discrete pops

TL;DR: Turn the pops into statistical units, and don't treat each of them as an "agent".

Our goal here is to disentangle pop count and runtime, to allow pop growth to continue without impacting performance. To do this, we need to treat pops as a number rather than a set of individuals. This way the number can grow without it taking any longer to calculate anything (on modern computers, multiplying 2 64 bit numbers is very fast, on the order of a few clock cycles plus memory overhead, and depends not at all on the size of the number as long as it is less than on the order of 264 or 18 billion billion).

Pops as collections of people

TL;DR: 1 pop = 1 billion people (/robot/drone/weird plant thing)

If we convert current-day pops to "people" at a rate of, say, 1 to 1 billion (which is a common metric thrown around) we can now treat them as numbers rather than individuals. Each species type now has a set number of people associates with it (a planet might have 12,385,472 humans and 35,862,512 blorg, though we can still represent this as 12.4 human pops and 35.9 blorg pops).

All numbers carry over mostly unchanged. City districts provide 6 housing, Industrial districts provide 2 housing, 1 artisan job, and 1 metallurgist job. Presentation-wise, you can still refer to these as units of housing (and a billion individuals as 1 "pop"). Each species grows at a proportional rate to the overall planet growth, modified by the species' growth speed, and immigration is distributed reasonably based on migrant sources and their population distribution (this can be efficiently pre-calculated per planet, as each planet would calculate its global immigration push. For extra performance and multi-threading potential, you could use last month's immigration push so there's no need to wait for that number for other planets; it takes at least a month to migrate anyway).

Jobs and species traits – pop specialisation

TL;DR: more specialisation = pops choose jobs better.

At this point we can introduce a new concept: pop specialisation. This isn't necessary for the idea to work, but it showed up naturally and seemed like a cool mechanic so I went with it. Specialisation is the degree to which pops will "specialise" to the jobs they are most suited to.

Specialisation goes from 0 to 1 (or 0% to 100%, if you want). At 0 specialisation, we essentially assume that species evenly distribute over all jobs (or at least all jobs available to them). So this means if 10% of your pops are Industrious, you get a total of +1.5% mineral output from jobs. At 100 specialisation, we assume every species works at something they are good at if possible. Thus, your mineral output boost is determined by the number of Industrious pops you have divided by the number of miner jobs you have. So for 15 Industrious pops and 50 miner jobs your total would be +4.5%. At values between 0 and 100 the value changes linearly between the two. The formula is bonus*((1-specialisation)*ratio_of_total_pops + specialisation*pops/jobs), where specialisation is between 0 and 1. Note that jobs is the number of filled jobs; this bonus is only calculated after we've decided how many of each job to fill.

Today's system (at least in theory) is roughly equivalent to setting specialisation to 100, which is a reasonable choice to make, but to me it seems like it might be an interesting mechanic. Authoritarians might get ways to force specialisation (through a sort of command economy lore), while egalitarians might be able to encourage their pops to specialise (after all, in a meritocracy there is strong incentive to do what you're good at). Increasing your specialisation would be a reasonable boost, but not crazy. The more specialised your planet is (say, a mining planet with 80+% miner jobs) the less of an impact it would actually make (think of it as very few pops being "swapped" from administration to mining if there aren't really that many administrators to begin with).

Read more:  Update and DLC Idea

As an example of a highly specialised planet, I found a planet in a save with 54 pops on it and 32 miner jobs. Let's say a good half the pops are Industrious. At 0 specialisation that would mean a +7.5% minerals from jobs total. At 100 specialisation it would be 0.15*27/32=+12.7% minerals, for a total of about 5% additive modifier. Nice, but not essential.

The same planet also has 2 entertainers, and 13% of the population is traditional. At 0 specialisation this gives +1.3% unity from jobs. However, at 100 specialisation, this gives the full +10% unity, as there are more than enough traditional pops to cover the jobs. Perhaps fittingly, specialisation is more impactful for more specialised jobs like Entertainers/Culture workers.

A runtime analysis of the new system

TL;DR: In this system the runtime does not depend on pop count, only on the species variety and job variety.

Our goal was to decouple runtime from pop count, allowing empires and planets to grow without that causing higher calculation strain and late-game slowdown. So, how did we do?

Let's go over what needs to happen at every month tick. We need to:
1. Grow our pops
2. Distribute pops to free jobs
3. Calculate species job bonuses
4. Calculate total jobs production
5. Calculate total pop upkeep
6. Calculate immigration push for next tick

1 is a simple numeric operation performed on each species on a planet.

2 would probably be a once-per-job-type calculation (it's almost a fractional knapsack problem, but assigning a "value" to each job type is hard/undesirable; you probably want a more even distribution, filling niche jobs like roboticist early), with the ability to set priorities to favour some jobs over others (for instance, screw clerks). Since we don't actually care which pops take which jobs (as that is covered by step 3), we can ignore the different species and focus only on the total population. The calculation is thus a per-job and not a nested loop of species and jobs. The only hitch is strata: the total population must be segmented by strata (from the previous month) and jobs filled from own strata first and then from the strata below. Too many pops in a strata leads to unemployment and gradual demotion as before.

We've discussed 3 in some detail above. The operations described are performed once per trait, though in practice this might be faster or easier to calculate per species type. This is, however, both independent of the number of pops.

4 is (since we already have the per-resource bonuses from step 3) a per-job calculation. Base*bonus*pops.

5 is either a single multiplication or a sum of a per-species multiplication, depending on if we've already calculated the upkeep modifiers together with the job modifiers above.

6 is also a once-per-species calculation.

This leaves us with a runtime of O(s+k+s+k+s+s)=O(4s+2k)=O(s+k), where s is the number of species types and k is the number of job types. So we did it! This is completely independent of the actual population of the planet, depending only on the variety of pops and jobs. Loading a save (and remember that the numbers should stay roughly the same), a planet of 120 pops has about 30 different species (some AI took xeno-compatibility, and I have a fair few migration treaties) and 10 different jobs.

We can expect a galaxy to start out with no more than 45 species or so (30 empires, 5 FE, and some empires with mechanist or syncretic evolution plus some primitives that get invaded/infiltrated/etc), but this can grow over the course of the game as robot templates are created and gene modding takes place. There is a real risk that the number of different species variations and half-species can balloon to higher than the pop count is currently, especially when there is no minimum cutoff number. In the save I've been using as a reference, my empire has in total 111 different species. Not all of them exist on every planet, but without a minimum cutoff of 1 full pop they likely would. The galaxy in total has some 380 different species – only 45 of which are actually half-species – which is significantly more than there currently tend to be pops (and enough that it would be a nightmare to try to keep track of or visualise). This would likely need curtailing somewhat.

However, even with 380 species, a runtime of O(s+k) is still faster than one of O(n2) or even O(nk) assuming s is not asymptotically larger than n. As a sanity check (although this is not how asymptotic notation works, we only care about the broad strokes, remember we ignored the 4*s and 2*k), 100 pops and 11 jobs gives 1002 = 10,000 and 100*11 = 1,100, while 380 species gives 380+11 = 391. If something is done to rein in the proliferation of species types, s should be a fair bit smaller than n.

This system is also likely possible to optimise in practice, though I haven't gone to deeply into that. You might not redistribute jobs until the total population changes by too much (or, perhaps, only when it reaches one new whole pop if you don't allow partial pops to work) or the number of jobs change, and those calculations might even be done asynchronously during the month (though that carries a myriad of other challenges like "will it be done in time" or "what if multiple changes happen close together" etc). The point of this post is, however, the high level analysis.

Read more:  Determined Exterminators: An EZ-mode Domination-style Guide

Similarly, the number of species actually included in the calculations can be minimised by keeping track of species with <1 pop only for purposes of pop growth. Don't count them in the pop total or iterate over them in any other step. They only become "real" when their growth puts them above 1 pop. This should keep species variety more in line with the current game, where a planet of some 120 pops has probably at most around 40 species – and is guaranteed ta have fewer than 120.


Side effects

Pops are integral to Stellaris, so this overhaul would touch many many systems. Pop demotion would probably be continuous (x% demoted each month), which actually gives a (to me at least) pleasing half-life curve as some people hold out longer on their savings or whatever. Resettlement either needs to work on a "immediately resettle multiples of 1 billion people" like today or change to a "resettle x people per month" system. However, keeping 1 billion people as "1 pop" keeps the amount of actual thematic rework manageable.

This requires we take a position on partial pops. If a planet has 42.65 billion people, what do we do with the 650 million? Do they get to work, filling a "job" partially? or are they essentially "left over", and excluded from working? And by explicitly tying pops to people, what is our position on children/elderly/the infirm? The numbers used in the calculations are all the people capable of work, but displaying a total number of "people" feels somewhat wrong if that is only counting the working population. It is possible to sidestep the issue by referring to the "billion" as "pops", and allowing "pop" to be a fractional quantity (so instead of 13,562,870 people you'd have 13.562870 pops – rounded to 13.6 when displaying of course).


Conclusion

This was mostly an exercise in thinking about game mechanics and runtime efficiency together. It is, I believe, far beyond the scope of any mod, as it would require changes to the game engine. If anyone from Paradox is reading this, you're free to run with this idea or, if appropriate, not run with this idea. I know how code works, but I don't know how your code works, and one or more points might be incorrect, technically infeasible, or simply unwanted from a game design perspective.

While my solution is asymptotically faster than the current system, that doesn't mean it's necessarily actually faster in practice. It'll be faster eventually as n grows, but that turnover point might not come until each planet has 1000 or 10k pops – which is far beyond what they currently have. It also presents issues with species variety, which can grow to unfeasible levels, but we covered some possible solutions to that.

I have, however, described an alternative to the current pop mechanics which (I think) should decouple performance from pop numbers, allowing the galactic population to grow unfettered without that in itself crippling performance. I know pops are not the only source of late-game performance issues (the AI presumably also takes more time as their empires grow larger and their fleets more numerous etc), and my proposal requires broad gameplay changes – though I have tried to emulate the essence of the current mechanics which I do quite like.


Acknowledgements

I'd like to thank u/Lucky-Surround-1756 and u/xXPalpatineXx, in conversation with whom this idea was born, as well as Paradox for making this damn game.

I'd also like to thank Vicky 2, for reasons that should be obvious (also just for existing in general). Come to think of it, this is kind of my sneaky attempt to, in lieu of Vicky 3, get PDS to create Vicky In Space.

EDIT: I just realised how long this took me; I should be studying lol. I guess as a comp sci student this is relevant-ish at least.

EDIT 2: If anything here is wildly off base (especially my assumptions about the current system) I would absolutely love to be corrected! I find this stuff fascinating – hence the *checks notes* *pauses* 3300 word post about it, so any light shed is wonderful! If I had my way, every dev diary would have a section for the techs to discuss cool behind-the-scenes stuff like Factorio often does.

Source

Similar Guides


More about Stellaris

Post: "An in-depth discussion of the pop system, its impact on performance, and possible solutions." specifically for the game Stellaris. Other useful information about this game:





Top 20 NEW Medieval Games of 2021

Swords, dragons, knights, castles - if you love any of this stuff, you might like these games throughout 2021.



10 NEW Shooter Games of 2021 With Over The Top Action

We've been keeping our eye on these crazy action oriented first and third person shooter games releasing this year. What's on your personal list? Let us know!



Top 10 NEW Survival Games of 2021

Survival video games are still going strong in 2021. Here's everything to look forward to on PC, PS5, Xbox Series X, Nintendo Switch, and beyond.



You Might Also Like

Leave a Reply

Your email address will not be published. Required fields are marked *