Trabalhando com muitos cubos. Melhorando a performance?

Edit: Para resumir a pergunta, eu tenho um mundo baseado em voxel (estilo Minecraft (Graças ao Pato Comunista)) que está sofrendo de baixo desempenho. Eu não sou positivo sobre a fonte, mas gostaria de qualquer conselho possível sobre como se livrar dela.

Estou trabalhando em um projeto em que um mundo consiste em uma grande quantidade de cubos (eu daria um número, mas são mundos definidos pelo usuário). Meu teste é de cerca de (48 x 32 x 48) blocos.

Basicamente, esses blocos não fazem nada por si mesmos. Eles apenas sentam lá.

Eles começam a ser usados ​​quando se trata de interação do jogador.

Preciso verificar com quais cubos o mouse do usuário interage (passe o mouse, clique etc.) e para detectar colisões à medida que o jogador se move.

Agora eu tinha uma grande quantidade de atraso no começo, percorrendo todos os blocos.

Eu consegui diminuir esse atraso, percorrendo todos os blocos e descobrindo quais blocos estão dentro de um intervalo específico do personagem e, em seguida, percorrendo esses blocos apenas para a detecção de colisão, etc.

No entanto, eu ainda estou indo a 2fps deprimente.

Alguém tem alguma outra idéia de como eu poderia diminuir esse atraso?

Btw, eu estou usando XNA (C #) e sim, é 3d.

Parece que você está procurando aprender sobre Árvores!

E estou falando sério, se atualmente você está fazendo um loop sobre uma matriz de todos os seus cubos, então deve realmente analisar várias estruturas de dados espaciais. Nesse caso, a melhor maneira de repensar o mundo do seu cubo é como uma árvore.

Antes de abordarmos as razões, vamos pensar sobre o nosso problema. Estamos procurando uma solução em que, pelo menor custo possível, possamos recuperar uma lista de cubos próximos com os quais o jogador esteja colidindo. Essa lista deve ser tão pequena, mas precisa quanto possível.

Agora, para determinar esta zona, precisamos mapear o espaço de coordenadas do nosso jogador para o espaço de coordenadas do mapa do cubo; isto é, precisamos mapear a posição do ponto flutuante do player para um índice discreto da matriz multidimensional de cubos (pode ser uma notação de exemplo world[31][31][31], ou seja, o meio exato para uma matriz multidimensional 64 * 64 * 64).

Poderíamos simplesmente calcular os blocos adjacentes usando essa mesma indexação discreta, talvez amostrando apenas os cubos próximos, mas isso ainda exige um recálculo constante e não permite objetos que não sejam discretos no posicionamento (ou seja, não podem ser mapeados para o cubo mapa).

A situação ideal é um conjunto de baldes que contêm nossos conjuntos de cubos para seções específicas do nosso mapa de cubos, divididos igualmente para que, em vez de recalcular a área circundante, simplesmente nos movemos para dentro e para fora deles. zonas . Para qualquer cálculo não trivial, manter nossos dados assim poderia eliminar a iteração de todos os cubos e apenas desses conjuntos individuais que estão próximos.

A questão é: como implementamos isso?

Para o mundo 64 * 64 * 64, imagine-o dividido em 8 * 8 * 8 zonas . Isso significa que, no seu mundo, você terá 8 zonas por eixo (X, Y, Z). Cada um desses zonas conterá 8 cubos, facilmente recuperáveis ​​por esse novo índice simplificado.

Se você precisar executar uma operação em um conjunto de cubos próximos, em vez de iterar todos os cubos do seu mundo, basta iterar sobre esses zonas , dividindo o número máximo de iterações do original 64 * 64 * 64 (262144) para apenas 520 (8 * 8 * 8 + 8).

Agora zoom deste mundo de zonas, e colocar as zonas em maiores super-zonas ; em que cada superzona contém 2 * 2 * 2 zonas regulares . Como seu mundo atualmente contém 512 (8 * 8 * 8) zonas , podemos quebrar as 8 * 8 * 8 zonas em 64 (4 * 4 * 4) super-zonas dividindo 8 zonas por 2 zonas por super-zone . Aplicando a mesma lógica de cima, isso quebraria as iterações máximas de 512 a 8 para encontrar a superzona ; e, no máximo, 64 para encontrar a zona de prosseguimento(total máximo de 72)! Você pode ver como isso já está poupando muitas iterações (262144: 72).

Tenho certeza que você pode ver agora como as árvores são úteis. Cada zona é um ramo da árvore, com cada superzona como um ramo anterior. Você está simplesmente atravessando a árvore para encontrar o que precisa; usando conjuntos menores de dados para minimizar o custo geral.

O diagrama abaixo deve ajudá-lo a visualizar o conceito. (imagem da Wikipedia: Octrees ):

Aviso Legal:

Em uma configuração ideal como acima, onde seu mundo voxel já está disposto em uma matriz multidimensional de tamanho fixo, você pode simplesmente consultar a posição do jogador e indexar os blocos ao redor com um custo de O (1)! (Veja a explicação de Olhovskys). Mas isso se torna mais difícil quando você começa a considerar que seu mundo raramente tem tamanho fixo em um jogo de voxel; e você pode precisar a sua estrutura de dados para ser capaz de carregar todo super-zonas do disco rígido para a memória. Ao contrário de uma matriz multidimensional de tamanho fixo, as árvores prontamente permitem isso sem muito tempo gasto em algoritmos combinatórios.

Concordo com a resposta de Daniels, em que iterar por grandes quantidades de caixas é a causa mais provável e que, ao usar o particionamento espacial, você pode acelerar o jogo muito - mas o problema também pode estar em outro lugar e você pode estar perdendo seu tempo .

Para aumentar significativamente a velocidade do seu jogo, você precisa criar um perfil do seu código. Identifique onde está o gargalo, isso permitirá que você faça as maiores melhorias.

Existem várias maneiras de criar um perfil do seu código, você pode criar sua própria classe de análise de desempenho (que pode fazer uso da classe Stopwatch (MSDN) ) ou usar o PIX para ter uma idéia geral de quão ocupada a CPU / GPU está .

Você também pode colocar marcadores de eventos PIX em seu código, que serão exibidos como regiões coloridas nas leituras do PIX. Não há uma interface C # oficial para essas funções, mas esse thread mostra como você pode criar uma interface C #.

Se o seu player é grande em relação ao tamanho dos cubos, provavelmente você deseja uma octree ou outra estrutura de partição espacial, como sugeriram outras.

No entanto, se o seu player é pequeno em relação ao tamanho dos cubos, provavelmente a maneira mais rápida de detectar colisão com os cubos é fazer uma pesquisa linear simples da área ao redor do player.

Como seu player é menor que 1 cubo, você só precisa testar a colisão contra os 27 cubos vizinhos, no máximo.

Isso pressupõe que você armazene os cubos em uma matriz na qual possa indexar, com um slot na matriz para cada cubo.

Como outros já apontaram, você precisa criar um perfil do seu código para ver o que está realmente atrasando você.

Se eu tivesse que adivinhar, eu diria que você provavelmente está fazendo um call para cada cubo, o que seria seu gargalo de longe. Para consertar isso, você deve procurar instâncias geométricas.

Mais uma sugestão para acelerar as coisas: seus bloqueios são aproximadamente fixos - isso significa que não há como um jogador colidir com a maioria deles. Adicione um booleano aos blocos indicando se eles estão expostos ou não. (Isso pode ser recalculado observando os vizinhos.) Um bloco que não está exposto não precisa ser verificado quanto a colisões.

É óbvio que o Minecraft faz algo parecido com isso - eu bati em um pedaço não carregado uma vez que me deu uma visão do mundo - eu podia ver através do solo sólido, tudo o que apareceu foram os espaços abertos (o lado oposto do era uma superfície exposta e, portanto, renderizada.)

Eu tive esse problema com meu mecanismo voxel.

Solução: (Muito mais simples que octrees) Em vez de percorrer todos os blocos, use uma equação para determinar a posição do bloco na matriz de blocos.

BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;

Então, se você deseja ver se existe um bloco:

Blocks[BlockIndex].Type > -1;

Ou, no entanto, você determina se o bloco existe.