Como determinar se uma sala 3D baseada em voxel é selada, eficientemente

10

Estou tendo alguns problemas para determinar com eficiência se salas grandes são seladas em salas 3D baseadas em voxel. Estou em um ponto em que tentei o máximo possível para resolver o problema sem pedir ajuda, mas não tentei o suficiente para desistir, por isso estou pedindo ajuda.

Para esclarecer, selado é que não há buracos na sala. Existem seladores de oxigênio, que verificam se a sala está selada e selam, dependendo do nível de entrada de oxigênio.

No momento, é assim que estou fazendo:

  • Começando no bloco acima do ladrilho do aferidor (a ventilação está na face superior do aferidor), faça um loop recursivo nas 6 direções adjacentes
  • Se o bloco adjacente for um bloco completo, sem vácuo, continue no loop
  • Se o bloco adjacente não estiver cheio, ou for um bloco de vácuo, verifique se os blocos adjacentes estão recursivamente.
  • Cada vez que um bloco é marcado, diminua um contador
  • Se a contagem chegar a zero, se o último bloco for adjacente a um bloco de vácuo, retorne que a área não está lacrada
  • Se a contagem chegar a zero e o último bloco não for um bloco de vácuo, ou o loop recursivo terminar (nenhum bloco de vácuo restante) antes que o contador seja zero, a área será selada.

Se a área não estiver selada, execute o loop novamente com algumas alterações:

  • Verificando blocos adjacentes em busca de ladrilhos de "ar respirável" em vez de ladrilhos de vácuo
  • Em vez de usar um contador decrescente, continue até que nenhum bloco adjacente de "ar respirável" seja encontrado.
  • Quando o loop terminar, defina cada bloco marcado como um bloco de vácuo.

Aqui está o código que estou usando: http://pastebin.com/NimyKncC

O problema:

Estou executando essa verificação a cada 3 segundos, às vezes um selador terá que percorrer centenas de blocos e, em um mundo grande com muitos seladores de oxigênio, esses vários loops recursivos a cada poucos segundos podem ser muito difíceis para a CPU.

Fiquei me perguntando se alguém com mais experiência em otimização pode me dar uma mão, ou pelo menos me indicar a direção certa. Muitíssimo obrigado.

NigelMan1010
fonte
Apenas verificar quando as coisas mudam seria um começo. Verificar a cada três segundos parece um exagero, pois você sabe quando os voxels mudam que podem quebrar o selo. Se um voxel que compõe uma sala selada for alterado, você pode marcar essa sala para ser verificada novamente, caso contrário, não se preocupe.
MichaelHouse
Como pode haver centenas de voxels alterados nesse período de 3 segundos, pensei que seria mais eficiente fazer isso periodicamente, em vez de verificar se algo mudou nas proximidades. Vou experimentar com isso embora.
precisa saber é o seguinte
Bem, se centenas de voxels puderem mudar em um período de 3 segundos, é provável que você tenha vários problemas com o desempenho. Comece a criar um perfil do seu código para encontrar ineficiências. Boa sorte!
MichaelHouse

Respostas:

3

A melhor solução dependerá de vários fatores, como o tamanho esperado da sala.

  1. Faça isso apenas quando algo estiver realmente mudando.

Abordagem 1:

Você pode usar um A * para encontrar um caminho da abertura para o ladrilho acima da abertura / da abertura ou para um ladrilho conhecido como vácuo. Se o caminho for encontrado, a sala não será lacrada. Isso não é tão diferente da sua abordagem atual, mas deve ser mais rápido. Uma vez encontrado, faça um "preenchimento de inundação" para definir os ladrilhos como vácuo.

Abordagem 2:

Talvez sua estrutura externa seja menos complacente - considerando que há uma superfície em que estão os cômodos, você não precisa se mover em todas as 6 direções; portanto, você deve viajar pela superfície, marcar cada ladrilho como vácuo que você viaja.

reiti.net
fonte
0

Ao fazer sua pesquisa recursiva, você não verifica o mesmo voxel várias vezes? Eu não sabia pela maneira como você descreveu seu algoritmo, mas você deve ter algum tipo de sinalizador para indicar se já expandiu recursivamente um voxel, para que não faça isso mais de uma vez.

E, como disse o Byte56, você também deve verificar se há vazamentos quando as coisas mudarem. Isso pode minimizar bastante a quantidade de trabalho que você faz, dependendo da frequência com que as alterações ocorrem. Você pode até conseguir armazenar em cache informações entre chamadas sucessivas ao algoritmo, o que pode banalizar a quantidade de computação que você faz após a primeira chamada.

Editar:

Eu olhei para alguns dos seus códigos. Parece que você está usando uma LinkedList para indicar se um voxel já foi verificado, como no meu primeiro parágrafo. Você pode obter melhores resultados se usar algo diferente de um LinkedList para isso. Talvez tente um HashSet ou algo assim? Isso deve reduzir a complexidade do seu método de verificação de O (n) para O (1).

Rumsey
fonte
Sim, estou adicionando-o a uma LinkedList chamada "marcada" e depois verificando se essa lista contém a posição antes de verificá-la. Eu pensei que verificar se algo mudou também seria extremamente intensivo em CPU, pois centenas de voxels poderiam ter mudado dentro desse período de três segundos. Vou ver como um hashset se compara à lista vinculada nessa situação, obrigado.
precisa saber é o seguinte