Citizens virtualization for large cities #165
Comments
|
i guess this is where teleporting comes in in the original game behavior. |
|
Perhaps reduce the allowance of unemployed workers to be spawned, so it's actually less busy during certain times of the day and especially at night.... |
|
@DaEgi01, I see no difference between d) and e). Since the citizens are invisible, they don't walk, don't use public transport, don't drive. So there's no point in simulating their movement at all - just plain CPU load without any benefits. @Sipke82, this doesn't help unfortunately. If there are 100k first shift workers that want to get home at 6 p.m., even completely disabed spawning of unemployed ones doesn't solve the problem. The high number of citizen instances you observe at night can be explained: the dummy traffic, the shopping at night citizens, and the extended first shift workers are active at that time. |
|
Possible solution - smart teleporting:
Advantages:
Disadvantages:
|
|
nah .. e) is much more complex in my mind than that. |
|
Okay, now I get it. This is impossible with the current game's implementation, since you'd need to run all the instances simulation using the whole citizens buffer. Movement only is not enough because of public transport, collisions, etc etc. Even if that'd be technically possible, you'd need a monster overclocked machine to be able to run a, say, 400k city - the simulation is single-threaded (okay, with exception of path finding). |
|
i wonder ... isn't smart teleporting what the game already does in a similar way? |
|
No, the vanilla game only teleports citizens in exceptional cases (e.g. when they are "confused", evacuating while instance limits reached, or in some invalid state like "at work" with no work building assigned - this occurs sometimes due to bugs in the game). Otherwise, the citizens just stay in the buildings until there's a next possibility to move. |
|
Another idea: track the number of citizens that are not at home. (This number is not equal to the number of spawned citizens.) When the number of not-at-home citizens reaches the 65k threshold, no further citizens can leave their homes (regardless of their schedules). Advantages:
Disadvantages:
|
|
This last solution, if it is simple to do, can be tested. I guess it also produces jams that are too long in time from 6pm |
|
@benzoll37, both unemployment and jobs assignment have nothing to do with this issue. It's only about spawned citizens. |
|
i like option a:) from egi the most.... but i guess it will be impossible to increase the cim/vehicle limit. So basically, the game does not get more challenging past 65k cities, from a simulation game perspective.. in fact i think it will become less challenging, because the traffic (cims+vehicles) is will be more spread out over a larger area, and thus less congestion.... |
|
that is exactly the case @Sipke82 |
|
I just took a look at the current implementation of CitizenManager. It is possible to tweek the limit of 65536 maximal citizen instances, but quiet hacky.( It used a type named Array16 to store all possible instances, which could only take 16bit indices) ps. Besides the limit of spawned citizen instances, there's also a limit for citizens living in the city, which is 524k. Don't think this would make trouble though |
|
Perhaps equally important the vehicle limit and the parked cars limit. |
|
@Sipke82 Technically, it's the same as Citizen instance limit, and can be modified. Just... loads of methods need to be patched. It'll be easy if we just modify the dll file, but it's bad for realeasing it as mod in the workshop PS. Performance can be improved if we move the simulationStep function into multiple threads. Current implementation already uses a dedicated thread for this job, basic thread safty is already been made, so it might be not that difficult to move it onto multiple threads |
|
@liiir1985, I don't think it's even possible to increase the instances limits. Currently, there are many methods that do use hard-coded upper bounds while processing the arrays. How do you want to solve this? Please don't suggest the Harmony's "transpiler magic". Messing around with the IL code during run-time is the worst thing one could imagine. I know, some modders do use thins technique. But they maybe don't realize the danger of that approach. Citizens limit is 1m by the way. One more word about the multi-threading: the game doesn't support this, sorry. The current implementation has no built-in parallelism support, with a single exception for the path-finding thread. |
|
@dymanoid It's actually a constant value which got compiled into IL code. yes, the only way to do it is to messing around the il code, but in a more clever manner. What makes the whole thing problematic is the definition of m_instances as an Array16, and all related indices used ushort, this may make the whole thing impossible through runtime patching The game doesn't support multi-threading, yes. But the calculation of the AI and all the simulation stuff(Logic is seprated from rendering) is already on another thread, rather than main thread. And synchronization lock also exists(See SimulationManager, which will start a new Thread for all the simulation stuff), So basically we can modify the SimulationStep function of SimulationManager, to make the for loop multithreaded, or at least, to make the citzen/viehcle simulation multi threaded. The current implementation is very friendly to the new ECS system introduced in Unity 2018, really hope the developer could make use of it, so simulating millions of Citizens would become reasonable |
|
OK, I took a deeper look at the current implementation, 16bit instanceID is everywhere, it's impossible to patch all of these methods including parameter definition/ field definition. |
|
@liiir1985, that is exactly what I was talking about. |
|
@dymanoid How about share riding? Will it solve the problem in some degrees? If the Citizen cannot be spawned, then call another citizen which has a viehcle to pick him up, then they move together. Maybe it's somehow more realistic than just teleporting the citizen directly |
|
This would need a comprehensive search mechanism which will drastically drop the simulation performance. The citizens will still need to be spawned to get into car and later to move from the car to the building. If we don't spawn them and let them ride "virtually", then why bothering at all? It's still like teleporting them directly to the target. |
|
Let them ride virtually will still produce traffic to the area where this citizen lives, so maybe it will make the streets look more busy? |
|
Traffic flow is calculated "by-car", not "by-citizen". |
|
I know it's calculated by car. What I mean is, maybe it won't be any car driving by otherwise, and now some one needs to pick him up, so it looks like a "spawned" car is driving by. |
|
Doesn't the game already do that? |
|
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. |
|
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). |
|
the idea with stations is pretty nice :) |
|
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 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 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 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. |
|
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 :) |
|
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 😄 |
|
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. |
|
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: So perhaps we can let the "car drivers" be teleported into their cars and from their cars to a in a building. |
|
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.
|
|
Thanks for your suggestions! I can comment on some of them.
|
|
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. |
|
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. |
|
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. |
|
The limitation is actually in the ID - it can't take a number greater than 65535, aka it's an UInt16 (or ushort). |
|
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. My plan is to simulate around 100k+ citizens, efficiently. |
|
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. |
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. |
|
so...is there a solution for the outside connections mentioned above? :) 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): |
|
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. |
|
That sounds amazing! Where could we possibly track this project? |
|
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.... |
|
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. |
|
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. |
|
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. |
|
@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. |
|
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. |
and others
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.
The text was updated successfully, but these errors were encountered: