Algoritmo para verificar se dois voxels estão interconectados

11

Estou procurando um bom algoritmo para o seguinte problema: Dada uma grade 3D de voxels (que podem estar vazios ou preenchidos), se eu escolher dois voxels não adjacentes, quero saber se eles estão conectados um ao outro por outros voxels.

Por exemplo (para ilustrar a situação em 2D), em que # é um quadrado preenchido:

  1 2 3
a # # #
b # #
c # # #

Se eu escolher a3 e c3, quero determinar o mais rápido possível se eles estão conectados; se houver um caminho entre a3 e c3 através dos pixels preenchidos. (A situação real está em uma grade de voxel 3D, é claro.)

Analisei algoritmos de preenchimento de inundação e de localização de caminhos, mas não tenho certeza de qual escolher. Ambos fazem um trabalho desnecessário: o preenchimento de inundação tenta preencher todos os voxels, mas isso não é necessário. Os algoritmos de localização de caminhos geralmente se preocupam em encontrar o caminho mais curto, o que também não é necessário. Eu só preciso saber se há é um caminho.

Qual algoritmo devo usar?

Editar: com base nos comentários, acho que deve adicionar o seguinte: o conteúdo dos voxels não é conhecido antecipadamente e também o algoritmo é necessário para detectar se a remoção (esvaziamento) de um voxel faria com que o grupo de voxels quebrasse em dois ou mais grupos menores.

Bram Vaessen
fonte
No seu exemplo, um caminho válido de a3 para c3 seria o seguinte c3->c2->b2->a2->a3:?
isso é correto
Bram Vaessen

Respostas:

12

A * funcionaria muito bem. Encontrar o caminho é o que você deseja, encontrar o caminho mais curto é tão rápido (ou mais rápido) quanto encontrar qualquer caminho. Nesta situação, A * é provavelmente o mais adequado, dado que você tem um ponto de início e fim. isso significa que você tem a heurística adicionada para acelerar a pesquisa.

Com A *, normalmente o primeiro caminho encontrado é o mais curto, portanto, ele não está fazendo um trabalho extra depois que já encontrou um caminho.

insira a descrição da imagem aqui

Para algumas otimizações, confira minha resposta aqui .

MichaelHouse
fonte
Parece que ele realmente brotos para a frente até que ele atinge essa parede, em seguida, tipo de arrepios
GameDev-er
1
@ GameDev-er Sim, isso é por causa da heurística. Se não houvesse obstáculo, seria uma busca muito rápida, quase uma linha reta.
Michaelhouse
Com uma melhor classificação dos nós, isso expandiria o caminho mais próximo do nó final primeiro. Se você tiver uma estrutura de dados rápida para solicitar os nós, classifique-os por distância até o destino para o caminho mais direto.
Michaelhouse
9

Se você estiver preparado para fazer um pré-processamento e reduzir o custo de armazenamento, particionar voxels em grupos conectados no momento da criação fornece uma resposta óbvia para 'existe algum caminho'? Existe um caminho entre dois voxels se eles estiverem no mesmo grupo. Obviamente, o problema é que você precisa armazenar informações do grupo em algum lugar, e isso depende do layout dos dados. Se você estiver armazenando uma lista simples, basta dividi-la em várias listas, uma para cada grupo conectado espacialmente. Se você estiver organizando algum tipo de BVH, provavelmente poderá obter eficiências razoavelmente boas se puder dizer "todos os voxels neste nó e abaixo pertencem ao grupo X".

Como alternativa, você pode fazer um pré-particionamento espacial e armazenar um conjunto menor de voxels 'hub' para cada grupo conectado. Em seguida, você pode encontrar o caminho a partir dos voxels de origem e destino até o voxel de hub mais próximo, que deve ser muito mais curto / barato para calcular o caminho. Se você puder encontrar um caminho de um voxel para um voxel de hub, o voxel fará parte do grupo do voxel de hub. Com a seleção inteligente desses voxels de hub, você pode minimizar o número de percursos de caminho. Por exemplo, uma esfera pode ter apenas um hub voxel em seu centro, mas um grupo longo e fino pode ter um hub voxel a cada X voxels ao longo de seu comprimento. Se seus voxels de origem e de destino tiverem um extremo do comprimento, eles precisam apenas usar no máximo X voxels para encontrar um hub, e mesmo que exista um grande número de voxels entre o início e o final do comprimento,

Tudo depende de quão patológicos são seus grupos de voxel: se você espera um grande número de pequenos grupos desconectados, o aumento no custo de armazenamento superará em massa o desempenho atingido apenas pela descoberta de caminhos. Se você espera relativamente poucos grupos conectados, mas com topologias estranhas, a busca de caminhos ingênua pode ser extremamente cara e o custo de armazenamento e a busca mínima de caminhos são uma opção muito mais barata.

MrCranky
fonte
1
Esta é a resposta certa, mas para implementá-la com eficiência, ela não deve ser armazenada como uma lista. Adicione um ponteiro a cada voxel que aponte para seu "voxel representativo", que você define usando o algoritmo de união. Esse é o custo de armazenamento constante por voxel e basicamente linear no número de arestas para o custo computacional.
31413 Neil G
Ideias interessantes, mas há duas coisas que podem complicar a situação. A primeira é que o conteúdo da grade voxel não é conhecido antecipadamente; portanto, para criar voxels de hub, eu também precisaria de um algoritmo que possa determinar quais voxels devem ser hubs.
Bram Vaessen
1
O segundo problema é que o algoritmo é necessário logo após a remoção de um voxel, para determinar se o grupo que fez parte é dividido em grupos menores devido à remoção desse voxel.
Bram Vaessen 31/03
@BramVaessen Se você está procurando todas as relações de interconectividade aos pares - e, em particular, se os grupos 'se separam' -, isso é um assunto um pouco diferente do que a simples acessibilidade (embora a acessibilidade seja a maneira mais fácil de fazer isso); Gostaria de acrescentar mais detalhes especificamente sobre o que você procura na pergunta original, pois ela pode oferecer melhores respostas para o 'problema por trás da pergunta'.
Steven Stadnicki 12/03/2013
Para mantê-lo limpo, pedi o meu problema inicial em uma questão diferente aqui gamedev.stackexchange.com/questions/50953/...
Bram Vaessen
4

Eu não estou muito familiarizado com voxels, mas imagino que você possa obter um desempenho muito bom usando o melhor algoritmo de pesquisa como o A *. O problema com o uso de A * nesse caso é que a heurística que normalmente usaria foi projetada para priorizar a localização do caminho mais curto e não apenas 'qualquer caminho' o mais rápido possível.

Você pode ter alguma sorte usando uma heurística alternativa que expande menos nós, como

f (p) = g (p) + w (p) * h (p)

onde w> = 1. você diminui o valor de 'w' quanto mais se aproxima do objetivo, dando assim uma prioridade mais alta ao custo do caminho 'g', mais perto você fica do voxel que procura.

Eu espero que isso ajude!

Matthew R.
fonte