Como posso gerar uma malha de navegação para uma grade de blocos?

18

Na verdade, eu ainda não comecei a programar para este, mas queria ver como eu faria isso de qualquer maneira.

Digamos que eu tenha uma grade de peças, todas do mesmo tamanho, algumas que podem ser passadas e outras não. Como eu criaria uma malha de navegação de polígonos a partir dessa grade?

Minha idéia era tirar os ladrilhos não-atravessáveis ​​e estender as linhas a partir das bordas para fazer polígonos ... isso é tudo o que tenho até agora. Algum conselho?

Ross Hays
fonte
2
Tecnicamente, a grade é praticamente equivalente a uma malha de navegação. Eu suspeito que você esteja realmente pedindo uma maneira de otimizar a grade e unir os quadrados adjacentes.
Kylotan
@ Kylotan Sim, foi exatamente isso que eu quis dizer, apenas uma maneira de combinar polígonos adjacentes.
Ross Hays

Respostas:

28

Aqui está um dos métodos que eu inventei ao fazer navmesh para um jogo RTS. Observe que é homebrew, nenhuma ferramenta de terceiros foi usada, levei cerca de 3 semanas para implementar e corrigir:

  1. Use o algoritmo Marching Squares para converter blocos de obstáculos em contornos . Observe que as bordas do mapa também são um esboço e precisam ser incluídas.
  2. Reduza o número de pontos nos contornos usando o algoritmo Douglas-Peucker (linhas roxas na figura inferior)
  3. Alimente todos os pontos na triangulação de Delaunay (para obter triângulos uniformes)
  4. Adicione pontos adicionais em áreas vazias e ao longo das bordas do mapa (para obter uma navegação mais uniforme)
  5. Verifique os contornos dos obstáculos e os polígonos de flip produzidos por Delaunay para corresponder aos contornos. - Muitas vezes, o Delaunay pode colocar triângulos (cinza) incompatíveis com seus contornos (vermelho), então você precisa detectá-los e invertê-los. Juntando-os novamente em um polígono, divida-o ao longo dos contornos e triangule-o manualmente insira a descrição da imagem aqui
  6. Recorte os obstáculos para dentro - remova os polígonos que estão dentro dos obstáculos (rosa na figura acima)
  7. Preencha os dados de conectividade entre os triângulos e vértices restantes conforme necessário - essa é a sua navegação.

Resultado:

tilemap navmesh

Kromster diz apoio Monica
fonte
1

As malhas são normalmente implementadas como gráficos. Se você deseja implementar a localização de caminhos em um mapa com base em uma grade, faça o seguinte:

Crie um gráfico em que cada quadrado atravessável seja representado como um vértice. Cada par de quadrados transversais adjacentes representados como vértices terá uma aresta entre eles. E você terminou.

wolfdawn
fonte
11
Não é assim que os navmeshes são normalmente implementados. O objetivo de uma navmesh (e, imagino, a razão pela qual o solicitante chegou a fazer sua pergunta aqui) é otimizar o gráfico até um número mínimo necessário de polígonos (geralmente triângulos) que abrangem os espaços mais úteis para reduzir o número de etapas necessárias para encontrar um bom caminho e a pegada de memória necessária para definir a malha. Uma implementação bruta consumiria muito mais memória e desperdiçaria um tempo valioso de processamento de IA.
Gurgadurgen 9/07/2016
Você está certo. É claro que a dizimação (redução de polígono) é uma otimização razoável e desejada. É que quando você a pergunta do op, você está sentindo que ele só quer transformar uma grade em um gráfico.
wolfdawn