Comment améliorer les performances pour des fonctions coûteuses dans 2D City Builder

J'ai déjà cherché des réponses mais je n'ai pas pu trouver la meilleure approche pour gérer des fonctions / calculs coûteux.

Dans mon jeu actuel (un bâtiment de ville basé sur des tuiles 2D), l'utilisateur est capable de placer des bâtiments, de construire des routes, etc. Tous les bâtiments ont besoin d'une connexion à une jonction que l'utilisateur doit placer à la frontière de la carte. Si un bâtiment n'est pas connecté à cette jonction, un panneau "Non connecté à la route" apparaîtra au-dessus du bâtiment affecté (sinon il doit être supprimé). La plupart des bâtiments ont un rayon et peuvent également être liés les uns aux autres (par exemple, un service d'incendie peut aider toutes les maisons dans un rayon de 30 carreaux). C'est ce dont j'ai également besoin pour mettre à jour / vérifier lorsque la connexion routière change.

Hier, je suis tombé sur un gros problème de performance. Jetons un œil au scénario suivant: Un utilisateur peut bien sûr également effacer des bâtiments et des routes. Donc, si un utilisateur rompt maintenant la connexion juste après la jonction, je dois mettre à jour de nombreux bâtiments en même temps . Je pense que l'un des premiers conseils serait d'éviter les boucles imbriquées (ce qui est certainement une grande raison dans ce scénario) mais je dois vérifier ...

1. si un bâtiment est toujours connecté à la jonction dans le cas où une tuile route a été retirée (je le fais uniquement pour les bâtiments affectés par cette route). (Cela pourrait être un problème plus petit dans ce scénario)

2. la liste des tuiles de rayon et obtenez les bâtiments dans le rayon (boucles imbriquées - gros problème!) .

   // 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.
       }
   }

Tout cela fait passer mon FPS de 60 à presque 10 pendant une seconde.

Je pourrais aussi le faire. Mes idées seraient:

• Ne pas utiliser le thread principal (fonction de mise à jour) pour celui-ci mais un autre thread. Je peux rencontrer des problèmes de verrouillage lorsque je commence à utiliser le multithreading.
• Utiliser une file d'attente pour gérer de nombreux calculs (quelle serait la meilleure approche dans ce cas?)
• Conservez plus d'informations dans mes objets (bâtiments) pour éviter plus de calculs (par exemple, les bâtiments dans le rayon).

En utilisant la dernière approche, j'ai pu supprimer une imbrication sous cette forme à la place:

// 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.
    }
}

Mais je ne sais pas si cela suffit. Des jeux comme Cities Skylines doivent gérer beaucoup plus de bâtiments si le joueur a une grande carte. Comment gèrent-ils ces choses?! Il peut y avoir une file d'attente de mise à jour car tous les bâtiments ne sont pas mis à jour en même temps.

J'attends vos idées et commentaires avec impatience!

Merci beaucoup!

Mise en cache de la couverture du bâtiment

L'idée de mettre en cache les informations sur les bâtiments à portée d'un bâtiment effecteur (que vous pouvez mettre en cache à partir de l'effecteur ou dans la zone affectée) est certainement une bonne idée. Les bâtiments (généralement) ne bougent pas, il n'y a donc pas de raison de refaire ces calculs coûteux. "Qu'est-ce que ce bâtiment affecte" et "ce qui affecte ce bâtiment" est quelque chose que vous devez vérifier uniquement lorsqu'un bâtiment est créé ou supprimé.

Il s'agit d'un échange classique de cycles CPU pour la mémoire.

Traitement des informations de couverture par région

S'il s'avère que vous utilisez trop de mémoire pour garder une trace de ces informations, voyez si vous pouvez gérer ces informations par régions de carte. Divisez votre carte en régions carrées de n*ncarrelage. Si une région est entièrement couverte par un service d'incendie, tous les bâtiments de cette région sont également couverts. Il vous suffit donc de stocker les informations de couverture par région et non par bâtiment individuel. Si une région n'est que partiellement couverte, vous devez vous replier sur la gestion des connexions par construction dans cette région. Ainsi, la fonction de mise à jour de vos bâtiments vérifierait d'abord "La région dans laquelle ce bâtiment est couvert par un service d'incendie?" et sinon "Ce bâtiment est-il couvert individuellement par un service d'incendie?". Cela accélère également les mises à jour, car lorsqu'un service d'incendie est supprimé, vous n'avez plus besoin de mettre à jour les états de couverture de 2000 bâtiments, vous n'avez qu'à mettre à jour 100 bâtiments et 25 régions.

Mise à jour retardée

Une autre optimisation que vous pouvez faire est de ne pas tout mettre à jour immédiatement et de ne pas tout mettre à jour en même temps.

La question de savoir si un bâtiment est toujours connecté au réseau routier n'est pas quelque chose que vous devez vérifier chaque cadre (en passant, vous pouvez également trouver des moyens d'optimiser cela spécifiquement en examinant un peu la théorie des graphes). Il serait tout à fait suffisant que les bâtiments ne vérifient que périodiquement toutes les quelques secondes après la construction du bâtiment (ET s'il y avait un changement dans le réseau routier). La même chose s'applique aux effets de portée du bâtiment. Il est parfaitement acceptable qu'un bâtiment ne vérifie que toutes les quelques centaines de cadres "Est-ce qu'au moins l'un des services d'incendie qui m'affectent est toujours actif?"

Ainsi, votre boucle de mise à jour pourrait uniquement effectuer ces calculs coûteux pour quelques centaines de bâtiments à la fois pour chaque mise à jour. Vous voudrez peut-être donner des préférences aux bâtiments qui sont actuellement à l'écran, afin que les joueurs reçoivent un retour immédiat de leurs actions.

Concernant le multithreading

Les constructeurs de villes ont tendance à être plus coûteux en calcul, surtout si vous voulez permettre aux joueurs de construire de très grandes dimensions et si vous voulez avoir une complexité de simulation élevée. Donc, à long terme, il n'est peut-être pas faux de penser aux calculs de votre jeu qui peuvent être traités de manière asynchrone.

1. Travail en double .

Vous affectedBuildingsêtes probablement proches les uns des autres, de sorte que les différents rayons se chevauchent. Marquez les bâtiments à mettre à jour, puis mettez-les à jour.

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. Infrastructures inadaptées.

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

devrait clairement être

var buildingsInRadius = tile.Buildings;

où Buildings est un IEnumerabletemps d'itération constant (par exemple a List<Building>)