8
\$\begingroup\$

My games usually start lagging quite easily when there are a couple hundred of boxes representing possible characters. While games like SimCity or even Anno have hundreds of characters.

I realized that those games don't update everything at every tic, the needs are handled in intervals and it's not a render problem, but all of those tiny creatures have individual path-finding etc.
I simply can't understand how they can pull that off for thousands of characters even on old machines. How do they do this?

This question was updated to refer to huge Numbers where individuals don't really count and are simply simulated for immersion and aesthetics.

(Related if referring to individual characters: How does Dwarf Fortress keep track of so many entities without losing performance?)

(Different question but maybe related?: Rendering hundreds of animated characters in Unity3D)

\$\endgroup\$
  • 2
    \$\begingroup\$ This doesn't actually look like a duplicate to me. While games like Dwarf Fortress do simulate the actions of every agent individually, once we get up to city-scale games as described in this question, that's no longer very practical. Instead, these sims usually operate at a more "chunked" level of population trends, filling in the details of individual people following those trends only when you look closely. Because of these differences in strategies, I think this is worth re-opening and answering separately from the linked question. \$\endgroup\$ – DMGregory Nov 21 '17 at 12:59
  • \$\begingroup\$ I made some changes to highlight the differences. How do I unlink the questions? \$\endgroup\$ – MisteriosM Nov 21 '17 at 13:15
  • \$\begingroup\$ Performance optimization is a very wide field. There is a million things you could do wrong performance-wise in your game. But without looking at your game and profiler output for it, it is hard to tell where your bottlenecks might be. We could now shoot in the dark and muse about memory locality, parallelization or advanced pathfinding algorithms for multiple agents, but it's hard to tell what you already know and what applies to your game. So I am afraid that this question is too broad. \$\endgroup\$ – Philipp Nov 21 '17 at 13:26
  • \$\begingroup\$ Have you tried object pooling yet? Instantiation is costly, activating and deactivating already instantiated objects isn't (as much) \$\endgroup\$ – user106170 Nov 21 '17 at 17:11
  • \$\begingroup\$ You could also use a particle emitter. Since they're really just visual representation of demographic data, they don't have to be smart or complex. \$\endgroup\$ – Stephan Nov 21 '17 at 20:06
12
\$\begingroup\$

Like so much of gamedev, the answer to how city sim games accomplish this seemingly-impossible feat is: they probably don't. They're just faking it well. ;)

Sims like these will typically operate on a "chunked" level, modelling groups of people, neighbourhoods, traffic corridors, or other city dynamics as a whole, rather than processing AI for every one of thousands or millions of residents.

There are a few ways we might approach this:

  • "Sparse" bottom-up: here we still simulate individual city residents, but not "too many" of them, and not every frame. You could think of this like a poll or census issued to a random sample of the people each week. You interpolate the results to come up with estimates of the wider virtual population - where they live, their vocation, income, demographics, etc.

    So for example, if you only simulate a hundred residents in your city, and 5 of them are students, then you can estimate that about 5% of your city's population is students, and model demand for schools accordingly.

    You might need to re-generate your random samples from your city's population distribution occasionally, to avoid excess clustering / sparseness (eg. if a neighbourhood becomes unpopular and all of your census residents move away, you want to note the exodus without leaving it completely devoid of representation in your sim!)

  • Top-down: Here you come up with a master formula that looks at your city and models its dynamics as a whole. In a style similar to macroeconomics, we neglect the details of individual agents, or consider them to be a kind of continuously divisible "fluid" of economic activity that flows according to principle-based laws.

    Rather than thinking about individual preferences and variability of people, your game rules might look more like differential equations relating amenity proximities and tax rates and productivities and property values and crime rates and and and...

  • Middle-out: Various hybrids between the two are possible - for instance, simulating each "faction," "industry," or demographic segment of the city as its own meta-person, making its own individual decisions, but spread out in a heatmap or wavefunction across the city rather than existing in any one body. Or chunking the city into neighbourhoods which each process their own smaller-scale rules in interaction with their neighbours.

Now, when the player zooms in close enough to see individual people, or looks at reports of statistics citing numbers of individuals - those are not necessarily the ground truth that's being used to run the sim. Rather, they can be an inferred product of it.

Let's say we zoom in on a particular city block. From our overall city sim, we know the rough population of this part of town, the types of activities that happen there, the times of day when it's active. So on demand, we can spawn an appropriate number of people of the appropriate demographics doing those kinds of activities there. Their AI can be dirt simple, maybe as little as playing an animation in place or following a waypoint to the nearest door/screen edge where they can de-spawn.

This means we usually won't need to do pathfinding for every agent. Instead, we can do one master flow-mapping pass on the whole road network, to identify the overall volume of different kinds of traffic along each segment. Then we can spawn enough vehicles of the right types in those segments to reflect that density. Once spawned, agents can just get by with local steering or pre-generated waypoints to get to a de-spawn point. Keeping spawn closets along each segment correctly balanced with the de-spawning rate lets us maintain any steady volume of traffic we want.

In this way, the people & vehicles the player sees are figments, like a souped-up particle system giving the impression of realistic clouds without actually computing full fluid dynamics on every molecule of vapour. ;) We arrange them as set dressing to communicate the state of the simulation, rather than to drive it.

For many games this will be enough. The player often is't able to select an individual agent to interrogate them about what they're doing there or where they're going, so it's hard to spot the seams and notice if an agent does something that doesn't make sense, like driving around the same block three times.

But if you need absolutely consistent agents in a densely populated environment, you can look into a neat technique called "Alibi Generation." This is a sophisticated sampling technique that lets you generate agents you'd expect to find in a given situation. Then, if the player tries to investigate one in more detail, you can retroactively sample more detail about what they're doing, in a way that's consistent with what the player has observed about them so far. The idea is that you still gain the lightweight benefits of "cardboard stand-in" people most of the time, but on the spot they can make up a plausible alibi to pass as fully-simulated agents.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.