Como posso gerar uma malha de navegação 2D em um ambiente dinâmico em tempo de execução?

9

Então, eu entendi como usar o A * para encontrar caminhos, e posso usá-lo em uma grade. No entanto, meu mundo de jogo é enorme e tenho muitos inimigos se movendo em direção ao jogador, que é um alvo em movimento, portanto, um sistema de grade é muito lento para encontrar caminhos. Preciso simplificar meu gráfico de nós usando uma malha de navegação.

Compreendo o conceito de "como" uma malha funciona (encontrar um caminho através de nós nos vértices e / ou nos centros das bordas dos polígonos).

Meu jogo usa obstáculos dinâmicos que são gerados proceduralmente em tempo de execução.

Não consigo entender como pegar um avião com vários obstáculos e dividir programaticamente a área que pode ser percorrida em polígonos para a malha de navegação, como na imagem a seguir.

malha de navegação

Por onde começo? Como sei quando um segmento da área passível de locomoção já está definido, ou pior, quando percebo que preciso subdividir uma área passível de locomoção definida anteriormente, pois o algoritmo "percorre" o mapa?

Estou usando javascript no nodejs, se isso importa.

Stephen
fonte
11
O particionamento dinâmico que você está tentando implementar depende das especificidades dos elementos do seu mapa. Seus elementos de obstáculos são inteiramente compostos por retângulos alinhados à grade, como mostra seu exemplo? Retângulos girados? Polígonos irregulares? Ou formas não poligonais com muitas curvas? Você tem dados de ponto / poli para a forma dos obstáculos? Se sim, são esses dados de forma em termos de triângulos, retângulos, polígonos exclusivamente convexos ou uma mistura de polígonos convexos e côncavos?
Matthew R
@ Matthew Meu mundo é composto por obstáculos convexos de polígonos, sem curvas e sem polígonos côncavos. Cada obstáculo é armazenado como um objeto de polígono com vértices representados por objetos de vetor.
Stephen
11
Pelo que vale a pena, estou trabalhando em uma solução baseada neste documento: gradworks.umi.com/3493710.pdf Se tiver êxito, publicarei minha solução.
Stephen
11
a malha de navegação não está lá para 100% dizer se você pode ir a algum lugar ou não, é apenas um esboço básico de áreas que podem ser percorridas, você ainda precisa fazer verificações de colisão contra objetos dinâmicos, editar: praticamente o que Ray disse
dreta
@ Stephen - Veja a resposta de comentários longos .
Matthew R

Respostas:

3

@ Stephen - Comentário Longo - Esse artigo parece valer a pena ser lido quando eu tiver algum tempo. Basicamente, o que eu sugeriria é algo semelhante ao algoritmo de Hertel-Mehlhorn mencionado no artigo (uma referência para esse algoritmo específico pode ser encontrada aqui http://www.bringyou.to/compgeom/ ) com a adição de subdividir os lados do mapa (fora dos limites da área de jogo) por algum tempo para reduzir as ocorrências de múltiplos pequenos triângulos formados nos cantos. Esses pequenos triângulos podem ser problemáticos, pois podem acabar sendo menores do que o que você está pré-formando. O Hertel-Mehlhorn é para a redução dos polígonos produzidos por uma partição triangular, se você estiver interessado aqui, é mais sobre triangulação:http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm .

Além disso, se você preferir não reinventar a roda, acho que esta biblioteca fará tudo o que você precisa: http://code.google.com/p/polypartition/ . Ele pré-forma as triangulações e reduções com uma de várias opções diferentes, incluindo a Hertel-Mehlhorn. É uma licença do MIT, o que significa que pode ser usada para projetos comerciais e de código fechado, se esse for um problema.

Se você decidir continuar trabalhando em sua própria implementação, eu adoraria ver o que você propõe.

Matthew R
fonte
11
Ótima resposta, @ Matthew. E você definitivamente deveria ler esse artigo! É fácil de seguir e explica uma ótima técnica (especialmente o Apêndice A, que fala sobre a descoberta / geração baseada em agente da malha). Estou codificando uma versão desse algoritmo para javascript, e está vindo bem. Vou postá-lo como resposta quando estiver pronto.
Stephen
@Stephen adoraria ver este trabalho
kevzettler
@Stephen Também estou procurando uma versão javascript
Apolo
6

Em vez de uma malha, você pode considerar apenas uma abordagem hierárquica de A *. A maior vantagem de uma malha é lidar com mundos de jogo que não estão alinhados à grade, em vez de reduzir a complexidade de uma grade.

Com uma abordagem hierárquica, você subdivide seu mundo repetidamente (como uma árvore quádrupla) e gera informações de conectividade entre os nós. Você pode gerar rapidamente um caminho entre grandes pedaços do mundo e usar apenas a grade de alta resolução para encontrar caminhos em um pedaço maior.

A abordagem hierárquica oferecerá melhor desempenho às ordens de magnitude, enquanto uma malha na melhor das hipóteses apenas fornecerá uma pequena melhoria linear.

A abordagem ingênua é apenas dividir seu mundo em X por X pedaços maiores alinhados à grade, gerar as informações de conectividade entre eles (por exemplo, existe um caminho entre o pedaço 2x1 de 3x1 a 2x2 e qual é a distância do caminho médio) .

Observe que nem sempre você pode encontrar caminhos ideais com essa abordagem em algumas circunstâncias particulares. A geração de camadas de pedaços de tamanho variável alivia o problema, mas, honestamente, geralmente é bem mais fácil evitar as marcas que estão surgindo nos caminhos do problema e confiar no fato de que o jogador dificilmente notará qualquer inimigo que esteja seguindo caminhos abaixo do ideal, exceto no degenerado dos casos.

Sean Middleditch
fonte
11
Devo explicar mais: meu jogo não está alinhado à grade. Eu estava construindo uma grade em uma área de 800 x 600 pixels, cada pixel sendo um espaço na grade (eu ainda estava descobrindo A *, então ainda não estava pensando no desempenho disso). Tenho obstáculos que não são tão simples quanto os da imagem de exemplo acima, estava apenas tentando ilustrar o problema. Obviamente, esse campo de jogo precisava ser revisto e, depois de algumas pesquisas, acho que uma malha de navegação seria o caminho certo a seguir.
Stephen
3

Eu acho que você pode estar complicando demais isso. Você provavelmente não precisa gerar malhas de navegação em tempo real. Em vez disso, tenha uma malha de navegação estática para o seu mundo base.

Percorrer obstáculos pode ser resolvido usando comportamentos de direção (use prevenção de obstáculos). Se, por acaso, seu obstáculo é tão grande que preenche ou bloqueia completamente a viagem de uma nav-poly para a próxima, então tenha uma maneira de verificar esse caso de aresta e recompute o caminho entre a poly em que você está atualmente e o um que você está bloqueado.

Ray Dey
fonte