Como melhorar o desempenho de funções caras no 2d city builder

Já procurei respostas, mas não consegui descobrir a melhor abordagem para lidar com funções / cálculos caros.

No meu jogo atual (um edifício da cidade com base em blocos 2D), o usuário pode colocar edifícios, construir estradas etc. Todos os edifícios precisam de uma conexão com um cruzamento que o usuário deve colocar na borda do mapa. Se um edifício não estiver conectado a esta junção, um sinal de "Não conectado à estrada" aparecerá acima do edifício afetado (caso contrário, ele deverá ser removido). A maioria dos edifícios tem um raio e também pode estar relacionada (por exemplo, um corpo de bombeiros pode ajudar todas as casas em um raio de 30 peças). É isso que também preciso atualizar / verificar quando a conexão rodoviária muda.

Ontem, tive um grande problema de desempenho. Vamos dar uma olhada no seguinte cenário: É claro que um usuário também pode apagar prédios e estradas. Portanto, se um usuário agora interromper a conexão logo após o cruzamento , preciso atualizar muitos edifícios ao mesmo tempo . Acho que um dos primeiros conselhos seria evitar loops aninhados (o que definitivamente é um grande motivo nesse cenário), mas tenho que verificar ...

1. se um prédio ainda estiver conectado à junção no caso de uma placa de estrada ter sido removida (eu faço isso apenas para edifícios afetados por essa estrada). (Pode ser um problema menor nesse cenário)

2. a lista de ladrilhos de raio e obtenha edifícios dentro do raio (loops aninhados - grande problema!) .

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

Isso tudo divide meu FPS de 60 para quase 10 por um segundo.

Eu também poderia fazer. Minhas idéias seriam:

• Não usando o thread principal (função Atualizar) para este, mas outro thread. Eu posso ter problemas de bloqueio quando começar a usar o multithreading.
• Usando uma fila para lidar com muitos cálculos (qual seria a melhor abordagem nesse caso?)
• Mantenha mais informações em meus objetos (edifícios) para evitar mais cálculos (por exemplo, edifícios no raio).

Usando a última abordagem, eu poderia remover um aninhamento no formulário a seguir:

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

Mas não sei se isso é suficiente. Jogos como Cities Skylines precisam lidar com muito mais construções se o jogador tiver um mapa grande. Como eles lidam com essas coisas ?! Pode haver uma fila de atualização, pois nem todos os edifícios são atualizados ao mesmo tempo.

Estou ansioso por suas idéias e comentários!

Muito obrigado!

Armazenando em cache a cobertura do edifício

A idéia de armazenar em cache as informações de quais edifícios estão ao alcance de um edifício efetor (que você pode armazenar em cache do efetor ou do afetado) é definitivamente uma boa idéia. Os edifícios (geralmente) não se movem, então há poucas razões para refazer esses cálculos caros. "O que esse prédio afeta" e "o que afeta esse prédio" é algo que você só precisa verificar quando um prédio é criado ou removido.

Essa é uma troca clássica de ciclos de CPU por memória.

Manipulação de informações de cobertura por região

Se você estiver usando muita memória para acompanhar essas informações, veja se consegue lidar com essas informações por regiões do mapa. Divida seu mapa em regiões quadradas de n*nazulejos. Se uma região é totalmente coberta por um corpo de bombeiros, todos os edifícios nessa região também são cobertos. Portanto, você só precisa armazenar informações de cobertura por região, não por edifício individual. Se uma região for apenas parcialmente coberta, você precisará voltar a lidar com conexões construindo nessa região. Portanto, a função de atualização de seus prédios verifica primeiro "A região em que este prédio está coberto por um corpo de bombeiros?" e se não "Este edifício é coberto individualmente por um corpo de bombeiros?". Isso também acelera as atualizações, porque quando um corpo de bombeiros é removido, você não precisa mais atualizar os estados de cobertura de 2.000 prédios, precisa apenas atualizar 100 prédios e 25 regiões.

Atualização atrasada

Outra otimização que você pode fazer é não atualizar tudo imediatamente e não atualizar tudo ao mesmo tempo.

Se um edifício ainda está conectado à rede viária, não é algo que você precisa verificar em cada quadro (a propósito, você também pode encontrar algumas maneiras de otimizar isso especificamente, analisando um pouco a teoria dos grafos). Seria completamente suficiente se os edifícios verificassem isso periodicamente a cada poucos segundos após a construção do prédio (E se houvesse uma alteração na rede viária). O mesmo se aplica à construção de efeitos de alcance. É perfeitamente aceitável se um edifício verificar apenas algumas centenas de quadros "Pelo menos um dos bombeiros que me afeta ainda está ativo?"

Assim, você pode ter seu loop de atualização apenas fazendo esses cálculos caros para algumas centenas de edifícios por vez para cada atualização. Você pode querer dar preferências aos edifícios que estão atualmente na tela, para que os jogadores recebam feedback imediato por suas ações.

Sobre Multithreading

Os construtores de cidades tendem a ser do lado mais computacionalmente caro, especialmente se você deseja permitir que os jogadores construam realmente grandes e se deseja ter uma alta complexidade de simulação. Portanto, a longo prazo, pode não ser errado pensar em quais cálculos no seu jogo podem ser manipulados de forma assíncrona.

1. Trabalho duplicado .

Você affectedBuildingsprovavelmente está próximo um do outro, de modo que os diferentes raios se sobrepõem. Sinalize os edifícios que precisam ser atualizados e atualize-os.

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. Estruturas de dados inadequadas.

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

deve ser claramente

var buildingsInRadius = tile.Buildings;

em que Buildings é um IEnumerabletempo de iteração constante (por exemplo, a List<Building>)