Trabalhando com muitos cubos. Melhorando a performance?

12

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.

Joel
fonte
Você quer dizer Minecraft? Ou seja, voxel?
The Duck Comunista
4
Você já olhou para as octrees? pt.wikipedia.org/wiki/Octree
bummzack
1
Você já tentou criar um perfil do seu jogo? Pode mostrar algumas áreas principais onde mais tempo está sendo gasto. Pode não ser o que você pensa que é.
Deceleratedcaviar
2
Em vez de desenhar todas as 6 faces de cada cubo, você só pode desenhar as faces que não estão em contato com nada
David Ashmore
1
@ David: Sim, ou ele pode parar de fazer uma única chamada por cubo primeiro e depois se preocupar com polígonos individuais mais tarde.
Olhovsky

Respostas:

20

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

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.

deceleratedcaviar
fonte
Eu diria que entendi, mas infelizmente não. As caixas de colisão dos blocos não estão se movendo, apenas a caixa de colisão do jogador. E eu tenho um método agora que (sem percorrer todos os blocos) retorna todos os blocos que estão dentro de um raio de 5 blocos do jogador. Desculpe pelo aborrecimento, mas algum esclarecimento? A propósito, para simplificar, você poderia assumir que o mundo é 64 x 64 x 64?
Joel
E eu ainda estou ficando em torno 5fps :(
Joel
Reescrevi minha resposta, deixe-me saber se isso ajudou.
Deceleratedcaviar
Então, refino os blocos em que o jogador poderia estar, usando essa técnica de octree. Tenho certeza de que entendi. Mas você está sugerindo que eu use minha detecção de colisão depois de reduzi-la a apenas uma pequena seleção de blocos ou você tem algum outro método?
Joel
2
A menos que o jogador seja muito grande em relação ao tamanho dos cubos, verificar a colisão ao redor do jogador é provavelmente o caminho mais rápido. Se o jogador não ocupa mais espaço do que um cubo, por exemplo, ele precisa verificar apenas 27 cubos ao redor, para encontrar uma colisão. Isso não requer uma árvore, pois você pode indexar diretamente nesses locais de cubo, supondo que ele armazene os cubos em uma matriz na qual ele pode indexar, com um slot alocado para cada local de cubo possível.
Olhovsky
13

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 #.

CiscoIPPhone
fonte
2
+1, concordo totalmente. Você não deveria estar olhando para algoritmos, mas sim para criar um perfil do seu código. Meu palpite é que não tem nada a ver com o fato de você estar percorrendo os blocos (não são muitos), é o que você está fazendo com cada bloco. Por fim, sim, você precisa ter um método melhor que a força bruta, mas se não conseguir lidar com uma iteração simples em cubos de 48x32x48, precisará repensar o que está fazendo com cada cubo, não como está fazendo um loop.
Tim Holt
4
@ Tim: A menos que seu jogador seja grande o suficiente para ocupar um espaço de 48x32x48, ele não deve estar iterando em qualquer lugar próximo a tantos cubos. Se ele estiver iterando através de 73000 cubos por quadro, posso dizer-lhe sem fazer nenhum perfil, que vale a pena corrigir isso, se por nenhum outro motivo, além de aprender a evitar dezenas de milhares de vezes mais iterações do que são necessários. Não é isso que eu chamaria de otimização micro ou prematura.
Olhovsky
Meu jogador é menor que o tamanho de 1 cubo, que pode ser maior em algum momento (mas não muito)
Joel
Randomman159: Então você só precisa testar contra os 27 cubos ao redor para encontrar colisão. Veja minha resposta.
Olhovsky
6

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.

Olhovsky
fonte
Ou você pode ter uma 'caixa delimitadora' que circunda o jogador e, em seguida, basta verificar com quais objetos ele está colidindo para determinar com quais objetos o jogador deve colidir. Um bom mecanismo de física poderá fazer todas as otimizações para você; também permitirá que mais do que apenas 'blocos' colidam.
Deceleratedcaviar
Pessoalmente, eu não gostaria de confiar na ampla fase de um mecanismo de física para testar contra 73000 cubos para mim, quando eu poderia escrever apenas duas dúzias de linhas de código para testar eficientemente a colisão para mim. Além disso, ele provavelmente não tem um mecanismo de física para explorar neste momento.
Olhovsky
1

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

Loren Pechtel
fonte
-1

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.

BMW
fonte
O problema aqui é mais complicado, porque você tem apenas 2 coordenadas para o mouse, para testar com o mundo 3D. Se a vista estivesse de cima para baixo, você poderia encontrar 2 dos 3 índices corretos para a posição do mouse e, em seguida, fazer um loop para a altura, começando de cima - mais perto da câmera e encontrando a primeira ocorrência de um bloco.
Markus von Broady