Efficiently updating building effect radius coverage

Question

I've already searched for answers but I was not able to figure out the best approach for handling expensive functions/calculations.

In my current game (a 2d tile-based city building) the user is able to place buildings, build roads etc. All of the buildings need a connection to a junction the user has to place at the border of the map. If a building is not connected to this junction, a "Not connected to road" sign will popup above the affected building (otherwise it has to be removed). Most of the buildings have a radius and might be related to each others as well (e.g. a fire department can help all houses within a radius of 30 tiles). That is what I also need to update/check when the road connection changes.

Yesterday I ran into a big performance issue. Lets have a look at the following scenario:

A user can of course also erase buildings and roads. So if a user now breaks the connection right after the junction I need to update many buildings at the same time. I think one of the first advice would be to avoid nested loops (which definitely is a big reason in this scenario) but I have to check...

1. if a building is still connected to the junction in case that a road tile has been removed (I do that only for affected buildings by that road). (Might be a smaller issue in this scenario)

   (Asked separately as Efficiently determining which buildings are connected by roads)

2. the list of radius tiles and get buildings within radius (nested loops - big issue!).

   // Go through all buildings affected by erasing this road tile.
   foreach(var affectedBuilding in affectedBuildings) {
       // Get buildings within radius.
       foreach(var radiusTile in affectedBuilding.RadiusTiles) {
           // Get all buildings on Map within this radius (which is technially another foreach).
           var buildingsInRadius = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);  
   
           // Do stuff.
       }
   }
   

This all breaks down my FPS from 60 to almost 10 for one second.

So would could I do. My ideas would be:

• Not using the main thread (Update function) for this one but another thread. I might run into problems of locking when I start using multithreading.
• Using a queue to handle a lot of calculations (what would be the best approach in this case?)
• Keep more information in my objects (buildings) to avoid more calculations (e.g. buildings in radius).

Using the last approach I could remove one nesting in form this foreach instead:

// Go through all buildings affected by erasing this road tile.
foreach(var affectedBuilding in affectedBuildings) {
    // Go through buildings within radius.
    foreach(var buildingInRadius in affectedBuilding.BuildingsInRadius) {
        // Do stuff.
    }
}

But I don't know if this is enough. Games like Cities Skylines have to handle way much more buildings if the player has a big map. How do they handle those things?! There might be a updating queue since not all the buildings do update at the same time.

I'm looking forward to your ideas and comments!

Thanks a lot!

Answer 1

Caching building coverage

The idea of caching the information which buildings are in range of an effector-building (which you can cache either from the effector or in the affected) is definitely a good idea. Buildings (usually) don't move, so there is little reason to redo these expensive calculations. "What does this building affect" and "what affects this building" is something you only need to check when a building is created or removed.

This is a classic exchange of CPU cycles for memory.

Handling coverage information by region

If it turns out you are using too much memory to keep track of this information, see if you can handle such information by map regions. Divide your map into square regions of n*n tiles. If a region is fully covered by a fire department, all buildings in that region are covered too. So you only need to store coverage information by region, not by individual building. If a region is only partially covered, you need to fall back to handling by-building connections in that region. So the update-function for your buildings would first check "Is the region this building is in covered by a fire department?" and if not "Is this building individually covered by a fire department?". This also speeds up updates, because when a fire department is removed, you no longer need to update the coverage states of 2000 buildings, you only need to update 100 buildings and 25 regions.

Delayed updating

Another optimization you can do is not updating everything immediately and not updating everything at the same time.

Whether or not a building is still connected to the road network isn't something you need to check every single frame (By the way, you might also find some ways to optimize this specifically by looking a bit into graph theory). It would be completely sufficient if buildings only check for that periodically every few seconds after the building was built (AND if there was a change to the road network). The same applies to building range effects. It is perfectly acceptable if a building only checks every few hundred frames "Is at least one of the fire departments which affect me still active?"

So you could have your update-loop only do these expensive calculations for a few hundred buildings at a time for every update. You might want to give preferences to buildings which are currently on the screen, so the players get immediate feedback for their actions.

Regarding Multithreading

City builders tend to be on the more computationally expensive side, especially if you want to allow players to build really large and if you want to have a high simulation complexity. So in the long run it might not be wrong to think about what computations in your game can be handled asynchronous.

Answer 2

1. Duplicate work.

Your affectedBuildings are presumably close to each other, so the different radii will overlap. Flag the buildings that need to be updated, then update them.

var toBeUpdated = new HashSet<Tiles>();
foreach(var affectedBuilding in affectedBuildings) {
    foreach(var radiusTile in affectedBuilding.RadiusTiles) {
         toBeUpdated.Add(radiusTile);

}
foreach (var tile in toBeUpdated)
{
    var buildingsInTile = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);
    // Do stuff.
}

2. Unsuitable Datastructures.

var buildingsInTile = TileMap.Buildings.Where(b => b.TileIndex == radiusTile.TileIndex);

should clearly be

var buildingsInRadius = tile.Buildings;

where Buildings is an IEnumerable with constant iteration time (e.g. a List<Building>)