9
\$\begingroup\$

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)
  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!

\$\endgroup\$
  • 2
    \$\begingroup\$ Using a profiler should help identify which bit of the code has the problem. It could be the way you find the affected buildings, or maybe the //do stuff. As a side note big games likes City Skylines tackle these issues by using spatial data structures like quad-trees, so all spatial queries are far faster than going trough an array with a for loop. In your case for instance you could have a dependency graph of all buildings and by following that graph could know immediately what affects what without iterations. \$\endgroup\$ – Exaila May 4 '17 at 9:19
  • \$\begingroup\$ Thanks for the detailed information. I like the idea of dependencies! I will have a look at that one! \$\endgroup\$ – Yheeky May 4 '17 at 14:40
  • \$\begingroup\$ Your advice was great! I just used the VS profiler which showed me, that I had a pathfinding function for each affected building to check if the junction connection is still valid. Of course that´s expensive as hell! It´s only about 5 FPS but better than nothing. I´ll get rid of that and assign buildings to road tiles so I do not need to do this pathfinding check over and over again. Thanks a lot! No I only need to fix the buildings in radius issue which is the bigger one. \$\endgroup\$ – Yheeky May 4 '17 at 17:58
  • \$\begingroup\$ I am glad you found it useful :D \$\endgroup\$ – Exaila May 8 '17 at 11:14
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ This explains why SimCity on the SNES takes a while for power to re/connect, I guess it happens with its other area-wide effects too. \$\endgroup\$ – lozzajp May 4 '17 at 12:23
  • \$\begingroup\$ Thanks for your useful comment! I also think that holding more information in memory could speed up my game. I also like the idea of splitting the TileMap into regions but I don't know if this approach is good enough to get rid of my initial problem long-dated. I´ve a question concerning the delayed updating. Lets assume I have a function which makes my FPS drops from 60 to 45. What´s the best approach to split the calculations to handle the perfect amount the CPU is able to handle? \$\endgroup\$ – Yheeky May 4 '17 at 14:49
  • \$\begingroup\$ @Yheeky There is no universally applicable solution for this, because it is highly situation-dependent which calculations you can delay, which you can't and what's a sensible unit of computation. \$\endgroup\$ – Philipp May 4 '17 at 17:09
  • \$\begingroup\$ The way I tried to delay these calculations was to create a queue with items which has a "CurrentlyUpdating" flag. Only this item having this flag set to true was handled. When the calculation has been completed the item was removed from the list and the next item was handled. This should work, right? But what kind of method could be used if you know that one calculation itself would bring your FPS down? \$\endgroup\$ – Yheeky May 5 '17 at 7:26
  • 1
    \$\begingroup\$ @Yheeky As I said, there is no universally applicable solution. What I would usually try (in that order): 1. See if you can optimize that computation by using more appropriate algorithms and/or data structures. 2. See if you can divide it into sub-tasks you can delay individually. 3. See if you can do it in a separate threat. 4. Get rid of the game-mechanic which needs that computation and see if you can replace it with something less computationally expensive. \$\endgroup\$ – Philipp May 5 '17 at 10:11
3
\$\begingroup\$

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>)

\$\endgroup\$
  • \$\begingroup\$ Good point! I guess I tried using a Distinct() on that one using MoreLINQ but I agree that this might be faster than check duplicates. \$\endgroup\$ – Yheeky May 4 '17 at 14:51

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.