1
\$\begingroup\$

In simulation games like Sim City and Factorio, there are numerous interaction between tiny objects that needs to be animated. e.g. random people walking on the sidewalk, then waits for a bus, then board the bus; tiny cars waiting in line for each other at the traffic junction; thousands of items on a convey belt and the robotic arm needs to wait for an item to arrive in front of it to pick it up; conveyor belt sections transferring items from one to another.

I expect the collision detection check for every tiny object independently will eat a lot of CPU; what technique can I use in such a game to avoid the heavy computation and make it look like it's realistic?

\$\endgroup\$
6
\$\begingroup\$

More often than not: it's all for show.

In Stone Librande's GDC 2013 talk "Simulating a City, One Page at a Time" he illustrates this with the original SimCity, where even on those primitive computers we had back then you could see individual cars driving around all the roads!

Or could you? (See ~18 minutes in) enter image description here

As this close-up on the intersection shows, the game isn't actually simulating individual cars driving all around town. It just has a "traffic level" associated with each road tile, and it selects an animated frame to show for each tile independently, using its traffic level. This causes seams where a high-traffic road borders a low-traffic road, where cars can apparently appear out of or vanish into nowhere.

Most of the sophistication we've gained since then is in hiding those seams. ;)

In modern city games, we still generally don't simulate hundreds to millions of commuters each with their own origin and destination to pathfind to. Instead we have designated spawn & despawn points out of the view of the player - just off the screen, around the corner, down an alley or in a garage. Every so often (on a timer or based on current density / budgets), we spawn a vehicle appropriate to the neighbourhood we're in. It might be given a pre-destined despawn point, in which case it doesn't even have to navigate unless disturbed - we're more or less just tweening it between waypoints until it's safely out of sight and can despawn again. Since we're tweening all the cars within a compatible range of speeds, they don't need to sense each other to avoid collision - it's all orchestrated. Only at intersections do we need to decide whether to keep this car going the same direction, or turn to fill a road segment that's too low on traffic, or to get out of view so we can despawn it.

Try following a car in most city games - you'll find their paths don't necessarily make sense globally - they might circle a block or take unnecessary detours - they just need to look plausible locally, to create the right set dressing for the scene.

One notable exception here is SimCity 2013, which as Stone was explaining actually simulates some number of individual agents, not just tiles of map. So a truck might actually contain a resource that it's transporting from a production site to a consumption site. I don't know whether this accounts for all of their traffic, or if it's a minority and they still fill in extra purposeless vehicles for set dressing.

But even here we get benefits from orchestration. The truck has its origin and destination pre-set: it's not changing its mind about where to go based on each other car it passes on the way. As soon as we have the beginning and endpoint, we can choose the route all these deliveries will take, and only re-path when the road network is changed. Our path is just a sequence of turns, and between the turns the truck is essentially an item in a queue belonging to a road segment, allowing us to space the vehicles out along the available lane space without individual collision checks. So ticking all the traffic forward one step can still be vastly lighter-weight than simulating hundreds or thousands of autonomous vehicles driven by decision-making AI characters.

Similarly, the people walking down the sidewalk and waiting at the bus stop aren't individually jostling for positions and running avoidance routines: they're assigned lanes and slots and then just animate to the orchestrated position for their next pre-ordained action.

Taking the example of conveyor belts in Factorio, the tile grid gives us a similar degree of predictability. While the sprites of the various objects may be quite detailed, the game state is just grids of numbers like tile type, content ID, power, exit time. We can plow through this grid doing minimal updates: oh, this conveyor's exit time is the current time tick? Clear its content ID and assign it one tile over. We don't need to do detailed polygonal collision detection every frame, just check whether the adjacent tile has contentID == 0. The actual animation of the objects moving on the conveyors is again, just for display: we can tween it from one side of the tile to the other based on currentTime - exitTime and the conveyor's direction, for only the tiles drawn in the current view.

So, that's as close to a recipe as we can get:

  1. Find out what actually matters to your sim. It's probably not "is this millimetre of this object touching that millimetre of that object" but something much more discretely chunked.

  2. Simulate the actions that matter at the coarsest level. eg. the conveyors deciding when an object switches from one tile to another, or the truck progressing discretely through the list of road segments in its pre-planned path.

  3. Animate the visible execution of those actions only where the player can see it. eg. the object moving predictably along the conveyor. This is cheap, because you're basically just tweening or moving along a spline - no fancy collision logic or AI decision-making happens here.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Wow, the idea of tessellating and looping animation within single tile is indeed very smart. Thank you! \$\endgroup\$ – Jake May 28 '19 at 15:17

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.