Citizens virtualization for large cities

[dymanoid]

In the vanilla game, the citizens get spawned randomly, regardless of time of the day. Furthermore, there are only a few movement reasons that cause a certain spawn: like e.g. illness (find hospital) or need for goods (go shopping). Entertainment and going to work are reasons that are throttled by the game depending on current number of spawned citizens and vehicles.

Since Real Time changes the going to work behavior, this movement reason gets a very high priority. The only throttled reason left is entertainment. However, the throttling only occurs while a citizen is at home. This is because whenever a citizen is not at home, there are time restrictions to be applied (e.g. everyone must leave parks until night time, the workers must leave workplaces according to their work shifts etc). The only unrestricted place to be is "at home".

For large cities (>65k), this introduces a new kind of problems. The spawned citizens throttling relies on the current number of spawned citizens. So, e.g. at 3 p.m., when almost all first shift workers are still at work (already despawned, because inside of buildings), the game allows to spawn lots of unemployed citizens (going e.g. to entertainment). At 6 p.m., when the first work shift ends, all the workers need to be spawned to get back home (or go shopping etc, according to their schedules). Since there is no throttling for citizens being at work, the number of spawned citizens quickly jumps to the maximum 65k. For very large cities, this even causes problems with citizens trying to leave their workplaces, because they cannot be spawned. So they have to wait at work for a "free slot".

This problem needs to be addressed somehow, but currently I have no ideas in which way.

[RenaKunisaki]

Doesn't the game already do that?

[dymanoid]

So here are the results of the discussions with Colossal Order.

Changing the internal data structures is unfortunately not possible anymore. This is the very game's core, so it would require a lot of changes in the code and retesting all the functionality. Frankly, such a change is just too overwhelming, so Colossal Order will not touch that part.

We also found no other possibilities to circumvent the issue. Colossal Order planned their game in such way that the simulation workload is evenly distributed across the whole game time. With Real Time, we are kind of going against the original game architecture.

So we are forced to implement workarounds. I think, the "smart teleporting" approach is probably the best way we can go in this case.

[RenaKunisaki]

That's unfortunate.

One thing I've thought of, but I don't remember if it was mentioned: batching citizen instances, and "fake" citizens.

Example: two people are walking along the same path and won't be branching off for a while. You replace them both with a single person, whose model is actually both of their models, so it still appears as two people. When clicking on that instance, or when they reach the point where they're going to diverge, then you respawn the actual people. Since it's mostly a visual trick, it could even be done depending on camera distance.

Another case is places like bus stops, where people stand around a lot. You could despawn them when they're just standing there, replacing them with an object that looks like them, and displays their info when clicked, but isn't actually a citizen instance. You still keep track of the actual person in a separate buffer, so that you can respawn/find them as needed (eg if player clicks on their vehicle and looks up their position).

[DaEgi01]

the idea with stations is pretty nice :) they look ridiculous when overcrowded anyway.

[tomvaneyck]

After reading the suggestions in this thread, I feel like the best solution to this problem may be a combination of smart teleporting and a distribution over the cims activities.

Smart teleporting I would make a change to the smart teleporting idea: instead of using a flag (which is not taking into account the amount of spawned cims when returning home) decide when leaving a place (home, work, shop ...) if the "busyness" allows to spawn, otherwise teleport.

One way to decide this is to use a chance of spawning, inversely proportional to the free spots left. This behavior is deterministic, because no cims will spawn when the spawn limit is reached as the the chance would equal zero. This behaviour is also fair, in the sense that every cim has an equal chance of being spawned.

Distribution accross work and other activities Like mentioned before, a higher chance of spawning commuting cims during rush hours delivers a more realistic expirience. However, in big cities, depending on the updating order of the simulation, cims with other destinations than work may take up precious spawn places. This may lead to an unrealistic distribution of traveling cims.

Having a distribution enforced by chances when spawning will make sure that during rush hour, for instance, 80% of traveling sims will be commuters. This distribution has to change based on time of day. This behaviour can also be considered deterministic for larger numbers of citizens, so this behaviour can be delayed untill the city has reached the amount of citizens equal to the limit of spawned cims.

Conclusion Because of the reactive nature of the smart teleporting to the current amount of spawned cims, the limit will not be exceeded. The chances used in this method will behave deterministically and will lead to a realistic distribution when use for high enough numbers of citizens. Still, a thousand citizens would already be enough for this to be true. This method will also not take a lot of extra computational time, because only simple chances are calculated, so I do not expect a real performance impact.

I really think this would work, but it is late and I have only quickly looked over the codebase. If I am wrong on some things, please correct me.

[dymanoid]

If we'd decide about teleporting "on both sides" (there and back), we could get undesirable side effects like e.g. ditched cars or improper public transport usage.

Imagine a cim gets spawned and drives to the work building. On return, there is no slot, and the cim gets teleported home. Now, the car is ditched at the work building - the cim won't find the car anymore.

Or, imagine the cim gets teleported to the work building. On return, there is a slot, and the cim gets spawned. Since there's no car, the cim will use public transport (or move on foot), preventing other cims to spawn which used their cars to get to work and thus causing those cims to be teleported home (producing more ditched cars).

Not that easy :)

[azabost]

I have no experience developing a C:S mod so you can treat my comment as a joke, but it bothers me so much I just have to ask 😄 Did you consider if this issue could be fixed by implementing a "carpooling" somehow? I.e. two cims living close to each other can travel together in a single car (or, technically, there can be a single cim-car travelling and the other teleporting with it). Or they could share a car so that the first cim drops off at his home and the second cim continues to his home. Sorry if I'm talking gibberish 😄

[matfax]

The real question is if C:SL2 will solve the performance issues and enroll a sophisticated and multithreaded crowd AI. It's definitely possible but will they invest in this topic or focus on other features? Updating to a newer Unity version won't fix the model. Transport Fever 2 is a new alternative to C:SL2 with regards to crowds and vehicle simulation and yet, they have the same issues as C:SL2 does and as Cities XL had. Don't go big, your fps drops otherwise. So I wouldn't be too optimistic about it. And it's completely unnecessary to recalculate everything each frame if you think about it. There are so many ways to circumvent it. Using adaptive schedulers being the most common one, I think. This can be further extended to a prioritization of different scheduled tasks in a functional way. There is no need to precisely calculate AI objects separately if you never look at them. Only calculate what's inside the view and approximate the remaining stuff over a whole second instead of each frame. Pathfinding can be approximated and generalized as well. This topic has been discussed for TMPE here. There's the same potential for public transport (not for personal vehicles) or even for crowds. If a certain group of objects is expected to behave similarly, you can save time by generalizing them.

[Sipke82]

One small idea I had with regard to teleporting and cars:

Today with the More Vehicles mod (amazing O-o ) we have the following limits: 64k vehicles 64k cims instances I'm my experience the cim instances limit get reached first.

So perhaps we can let the "car drivers" be teleported into their cars and from their cars to a in a building.

[pleaserespond]

I'm just a player mostly but would like to give my 2c. Obviously we have to accept the hardcoded 64k limit for simultaneous spawned agents, so the engine fundamentally cannot provide a fine-grained simulation of a large city. Having said that all we can do is provide compromises that keep the spirit of Real Time mod within the limits of the engine. Here are a few ideas I've had, I read the entire thread a few times so I'm fairly certain these weren't suggested, apologies if I'm repeating old suggestions.

1. Randomise the time cims leave. Yes, the cim has to be at work at 9, but really we all know that +/-15m is acceptable. By applying a jitter function to the spawn time we'll hit the spawn limit with different cim distributions each day, providing an overall traffic distribution that approximates the full load over several days. This is similar to the time zone idea, but without being hardcoded so your road network has to take every possible distribution.
2. Impromptu carpooling. If a cim wants to go from home to somewhere else, but can't spawn, find a different cim that is making a similar journey and teleport the bodyless cim to their destination when the carpool cim reaches theirs. For the return trip do the same. It's still possible there will be no carpool to take, but it's something.
3. Do not fully simulate cims not in cars. A cim taking public transport won't affect the road network, since the actual vehicle is already spawned. You could calculate which routes the cim would take and teleport them to their destination once the final leg of the journey is complete. If the cim decides to drive part of the way, make them wait either for a slot or for a carpool. This in effect is a shadow simulation for cims that walk or take public transport, since they don't participate as much in the road network.
4. If a cim waits too long for any option to be available (let's say 1 in-game hour), calculate roughly the expected time their trip would take and just teleport them. Not ideal, but the city must keep working.

[dymanoid]

Thanks for your suggestions! I can comment on some of them.

1. This is already happening. Real Time does randomize the time for the citizen schedules. Additionally, the game randomizes them even more. If Real Time says "this citizen would leave their home at 9:00 AM", the game might simulate that citizen e.g. only at 9:30 AM, so the citizen leaves later than planned. This is because the game simulates the citizens in chunks, so all them are distributed across the simulation cycle which is (depending on Real Time speed setting) something between 1 min. and 40 min. of the in-game time.
2. This was discussed above. It doesn't really help: the routes change (roads get changed by the player, vehicles can be despawned etc.), and searching for a similar route would mean a significant performance impact, especially in large cities. Knowing only the destination is not enough, because citizens choose different ways of travelling (on foot, public transport, bicycle, car).
3. I don't quite understand this point. Currently, citizens moving by public transport will not be spawned. They only get spawned when they exit the public transport vehicle, and we need to spawn them.
4. 1 hour is definitely too few, but this is actually the general idea of the teleporting. It will always be the last fallback solution (and maybe the only feasible solution...)

[pleaserespond]

My thinking was mostly about how to best choose who gets teleported when not enough slots are available. It's a kind of scheduling problem, except we have 65536 "cores" and processes are not preemptible and magically autocomplete if they don't run.

For 2, I don't think it will be that hard - you can keep track of every (start, end) points for the route of every vehicle on the road in a quadtree structure, so you can quickly answer queries like "is a vehicle making the journey from a point close to A to a point close to B right now". If yes, you can pretend the cim who wants to go from A to B actually carpooled with the existing vehicle and teleport them. Yes, this cim could have chosen a different route and yes, a simple geometric distance doesn't account for the fact that the cim might have to walk more than they're willing, but teleporting them now allows a different cim to spawn whose journey is entirely unaccounted for.

You don't even need to record which actual vehicle is making the trip, just a pair of (start, end) points and (start, end) times. You add each journey as it is completed - because we'll teleport the cim, we need the journey to be already complete - and delete ones that ended too long ago.

I think this option will be most useful for cims going to/from work or school - a lot of times several cims from one neighbourhood want to go to roughly the same workplace, so this allows them to be grouped in one vehicle.

For 3, I meant to prefer teleporting cims if their journey is entirely with public transport and walking, subject to how oversubscribed the system is. Or maybe I should have formulated it as "deprioritise spawning cims who will not drive when a free slot is available".

I see these as cases where teleporting the cim doesn't change the simulation too much, so the waiting time for teleporting the cim can be shorter than usual, which means few less cims waiting.

Edit: Or if possible, you could give each cim a spawn priority and lower the priority of cims who, if they were to be teleported, will not affect the traffic simulation too much.

[kittenchilly]

Would it be possible to have a teleporting system that calculates the average time it would take for someone to make it to a certain destination and just teleport them after that time is up? Or would that be too expensive? It would keep the general flow of the city, even if the citizens don't actually show up on the map.

[dostillevi]

After some long thought, I had an idea, but it depends on the data structures used by Cities: Skylines to store citizen data. My idea is to replace what I assume is a single addressable array of 65536 citizens with a set of 10 addressable arrays, 0-9. In order to store or retrieve citizen data, the first digit of the citizen ID would reference the array, while the remaining digits would specify the location within the array.

In order for this to be useful, the limitation of 65536 must exist only in the storage array, not in any formulas that query the array. Those formulas would look up with IDs that look like 100123 (for the 124th entry in the second array). Presumably there isn't a hard coded limit to prevent these variables from accepting a 6 digit numeric value.

[Evengard]

The limitation is actually in the ID - it can't take a number greater than 65535, aka it's an UInt16 (or ushort). I've actually analyzed a bit more - changing this to an Int32, while feasible (the inner structure of Array16 is actually using int, but casted down to ushort - actually the game when querying the Array16 buffer casts the ushort back to int), would be so hard that it would require rewriting almost half of the game logic. The instanceID is used in some rendering loops which are generated by using bit shifts, which would be broken too if we even manage somehow magically to swap all ushorts to ints. It's heavily tied to the renderBuffer which in it's turn limited to 1024 elements, and it uses that for the bit shift operations. We would need to increase this one too for that to work...

[sairam4123]

So, what's the plan, how will this get implemented? I'm working on a similar game and I'd like to learn more on this. Thanks!

My plan is to simulate around 100k+ citizens, efficiently.

[isaac-prog]

For larger cities, a huge handful of Cims are seen waiting around Outside connections for plane,bus,train,ferries for a extremely long time and they take up alot of those citizen agent instances. If there is a way to make them mass spawn roughly the same time as their intercity transport, it would definitely save lots of those citizen agent instance and optimised intercity transport to the fullest. (Basically, there must not be crowding at Outside connections)

This is commonly observed: Cims Carpool most of the time at outside connection highways when citizen instances are near maxed. Thus i wish to ask if 4 cims enter a vehicle, does the agent count reduce from 4 to 1, or increases to 5 (4cims+1car)? If its 1, teleport 3 of the cims to their destination.

[dymanoid]

Thus i wish to ask if 4 cims enter a vehicle, does the agent count reduce from 4 to 1, or increases to 5 (4cims+1car)?

When 4 cims enter a vehicle, the number of cim instances decreases by 4 (because all 4 instances despawn). The number of vehicles increases by 1 if the car is pocket-spawned at that moment; otherwise, the car instance status is changed from "parked" to "moving" and thus the number of vehicles remains the same.

[isaac-prog]

so...is there a solution for the outside connections mentioned above? :) the 65k limit is really ruining my experience :(

also, is there any ways to store any cims that are past the 65535 mark, i.e. the 65536th cim/vehicle/animal into a new type/set of array? sorry idk much about data structure.

curious, why didnt CO use uint32 or 64 instead of uint16?

this was suggested by RenaKunisaki earlier on which i think was overlooked : "Example: two people are walking along the same path and won't be branching off for a while. You replace them both with a single person, whose model is actually both of their models, so it still appears as two people. When clicking on that instance, or when they reach the point where they're going to diverge, then you respawn the actual people. Since it's mostly a visual trick, it could even be done depending on camera distance."

once cims agent active instances is near maxed out, they start to spawn batches of cims to travel to the same destination from outside connections(highway).

another note (my focus here are mostly directed to optimising active agents at outside connections): on rail, airplane and ships outside connections, there are always trucks spawning and upon realising that they arent spawned at they highway, they despawn. is there a way to totally stop them from spawning at these connections so as to reduce active cim agent count?

[algernon-A]

Work is currently underway on a project that will extend the available citizen instances beyond the 65K limit; when that happens (props already done, buildings next, citizens after that) I'll make sure that this mod is updated to use the extended manager, and then this issue will be resolved.

[Evengard]

@algernon-A

That sounds amazing! Where could we possibly track this project?

[algernon-A]

It's the Extended Managers Library. Citizen Instances are a little way off yet, but definitely on the list. Biggest issue (and workload!) so far is mod compatibility (in some cases requiring complete re-implementation of functionality). It gets easier once prop mods are converted/replaced....

[isaac-prog]

I would like to clarify if active vehicles is a subset of citizen instance or stored seperately. ie to say if have 16k active moving vehicles, does that mean it consumes 16k citizen instance or 0 citizen instance?

[algernon-A]

I would like to clarify if active vehicles is a subset of citizen instance or stored seperately. ie to say if have 16k active moving vehicles, does that mean it consumes 16k citizen instance or 0 citizen instance?

Missed this response - vehicle limits are separate to Citizen Instances. The More Vehicles mod already unlocks that particular limit by expanding it to the full 65K 16-bit limit.

[ruzbeh0]

Here is a possible workaround to this problem.

Instead of increasing the citizen istance limit, a solution would be to assign a weight to each citizen. The main idea is that the citizens are not a represention of the whole population but a sample of it. For example, each citizen instances could represent 2 citizens.

I haven't actually used the Real Time mod yet, but I had a city that was getting too big and I was able to implement this idea by using several other mods.

I used realistic population to reduce the number of households and jobs in each building by half, used another mod to reduced the capacity of transit vehicles by half, reduced the capacity of outside connections by half, and doubled my income to compensate for the lost in revenue. The game is showing that I now have about half of the popution that I did before, but in practice it represents the double of what is shown - but without passing the limit of citizen instances. The only thing I wasn't able to adjust is the number of vehicles on the roads, which need to be doubled. But since the vehicle limit is much higher than the citizen instance that shouldn't be a problem.

[isaac-prog]

i was wondering if it is possible to replace some 1 cim character with 2 cim characters, ie 1 red shirt guy with 1 red shirt guy and 1 blue shirt guy. so these 2 guys will go to the same destination, take the same path and so on, but the game treats them as only 1 cim character. i know this is more about creating a "2 cims citizen" asset in the citizen workshop, but wondering if this could at least make the city look more lively with "more" cims.

[dymanoid]

@isaac-prog Real Time doesn't restrict the number of spawned citizens. The problem is the opposite. In big cities and at certain times, Real Time needs to spawn more citizens than the game is able to do. So spawning 2 guys instead of one, as you suggest, will make the situation even worse than it is now.

[eberkain]

I admit i have not read this entire thing so this may have already been suggested. Can you make a virtual rideshare, so if there are 4 people that all want to leave work at the same time, you spawn one out and then save the other 3 in the background. The spawned cim then drives to the homes of the other cims in order and deposits them at their respective locations before driving him self home. In theory it could scale to any size if you dont restrict the people that can pile in one car, at the cost of making commutes longer.

You would have to despawn vehicles for anyone doing the rideshare just to be safe, but if you are hitting the citizen cap then you are probally hitting the vehicle cap anyhow.