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.
Update: Now that the game is out, I can say that Watch Dogs Legion works this way. Disposable cardboard cutout pedestrians are generated on demand to fill out the player's immediate vicinity, according to a "census system" that models the mix of demographics, professions, styles, etc. that we'd expect to see in each neighbourhood of London. If nothing happens to that person, they eventually walk out of the player's view and are forgotten entirely. But if something noteworthy happens to them or the player starts interacting with them, they can get "up-rezzed" to individual simulated agents who carry on existing and going about routines when the player isn't around, and can show up again later in the story. Check here for an interview with some of the developers explaining the workings of the system in more detail.
