Determinando se a estrutura criada pelo jogador corresponde a um modelo em um jogo baseado em blocos 3D

8

Isenção de responsabilidade: essa é uma daquelas perguntas temidas no estilo Minecraft, mas acho que é mais uma questão de estruturas de dados e algoritmos

Eu sou realmente novo em estruturas de dados 3D e estou me perguntando qual a melhor maneira de armazenar e combinar uma estrutura de blocos 3D.

No momento, o jogador pode colocar blocos em qualquer espaço arbitrário e quando esses blocos correspondem a uma estrutura predefinida, um evento acontece. Atualmente, quando um jogador coloca um bloco, o jogo verifica recursivamente cada bloco adjacente para encontrar o bloco com a menor coordenada x, y, z e faz com que esse bloco seja o bloco raiz. Em seguida, verifica o restante dos blocos, com base no bloco raiz, para garantir que eles correspondam a um determinado modelo. O problema é que, à medida que o modelo fica mais complicado, o mesmo acontece com o meu código (terrivelmente ineficiente).

Eu estou pensando que a melhor maneira de fazer isso é armazenar algum tipo de matriz que define a estrutura e depois combinar com a matriz sempre que um jogador coloca um bloco. Já existem estruturas / algoritmos de dados que corresponderiam a esse tipo de problema?

WillP
fonte
11
Como exemplo, você está pensando em como modelar estruturas como um portal do Minecraft?
Deceleratedcaviar
11
@ Daniel Na verdade, acho que seria um bom exemplo. Embora, meu objetivo seria ter uma estrutura arbitrariamente grande / complexa. Os portais são bastante simples.
willp
11
Não é uma resposta, mas apenas um pensamento - se as estruturas se tornam arbitrariamente grandes e a lista de estruturas de destino (que você precisa procurar para encontrar uma correspondência) se torna incrivelmente grande, isso se torna um problema de reconhecimento de padrões, como o reconhecimento de texto ou fala. Então você se afasta da comparação da força bruta em direção a métodos estatísticos, como os Modelos Markov Ocultos treinados em suas estruturas de destino. Isso seria tão legal.
Pieter Müller
@Harikawashi Oh cara, isso seria muito legal. Mesmo que meu objetivo não seja algo astronomicamente grande, posso fazê-lo de qualquer maneira apenas para poder brincar com isso. Obrigado!
willp

Respostas:

10

Para ser honesto, eu pegaria a solução simples.

Faça uma matriz que defina a estrutura. Sempre que um bloco for alterado, tente aplicar essa matriz a todos os locais que possam ter criado a nova estrutura. Serão locais de largura * profundidade * altura, já que o jogador pode ter terminado qualquer ponto da estrutura, mas não deve ser muito ruim, porque a maioria desses locais sairá cedo quando a primeira verificação falhar.

Basicamente, você tem uma matriz 3d e a compara com outra matriz 3d, com várias compensações.

A partir daqui, há várias otimizações totalmente opcionais que você pode fazer. Por exemplo, se sua estrutura é extremamente esparsa - ou seja, o jogador está construindo uma torre alta com uma esfera no topo, mas você não se importa se a parte inferior da torre estiver cercada por árvores - você poderá transformá-la em uma lista de blocos em vez de uma matriz. (Eu geraria a lista a partir da matriz - a matriz será muito mais fácil de manter diretamente.)

Se você quiser ser super inteligente, divida a estrutura em tipos de bloco. Se você sabe que o jogador acabou de alterar o bloco 1,2,3 e você sabe que colocar a sua estrutura nas coordenadas 0,0,0 exigiria que o bloco 1,2,3 fosse obsidiano e o bloco 1,2,3 é madeira , você nem precisa tentar o bloco 1,2,3. Gere todas as compensações possíveis para a estrutura, uma vez que o jogador acabou de colocar um tipo específico de bloco. Então, quando o jogador colocar esse bloqueio, basta verificar as possíveis compensações pré-geradas.

Mas, falando sério, tudo isso é otimização. Basta fazer uma matriz e comparar sua matriz com o estilo mundial de força bruta. Supondo que você esteja criando algo Minecrafty, as pessoas realmente não colocam tantos blocos - alguns blocos a cada segundo, no máximo. A menos que você tenha centenas de estruturas enormes, poderá testar isso facilmente.

ZorbaTHut
fonte
3
Você está certo. A força bruta realmente não deve ser um grande problema de desempenho. Sinto como se tivesse caído na armadilha da otimização prematura. Obrigado pela sua compreensão.
WillP
0

Bem, você vem com um problema interessante. Sugiro algo como o seguinte: use seus blocos como pixels e faça uma detecção de colisão por / pixel, onde todos os blocos devem corresponder para retornar uma verdadeira colisão.

Isso funcionaria bem, no entanto, certifique-se de fazer isso somente quando objetos / blocos forem alterados. Portanto, eu recomendaria um sistema de eventos simples para passar uma alteração a um verificador de objetos, que certamente pode usar seu algoritmo. O que faria o que você deseja que esse objeto faça. Também recomendo verificar a altura e a largura, antes de executar o algoritmo, porque se não for alto o suficiente / for muito alto, obviamente não corresponderá.

Quanto a uma estrutura de dados, um vetor simples seria suficiente, ou talvez uma estrutura de dados personalizada.

Pergunta interessante.

Avlagrath
fonte