Quais heurísticas são usadas no NavMeshes?

Quais heurísticas os programadores usam no A * pathfinding para o NavMeshes?

NavMesh = Mesh de Navegação, é um tipo de busca de caminho que usa malhas em vez de waypoints.

path-finding Shawn Mclean
fonte

Esclareça sua pergunta. Não sei o que você quer dizer quando diz "NavMeshes" (em maiúscula como se fosse um Product Name ™). Você está pedindo algoritmos alternativos ao A * que produzam caminhos mais aproximados, mas em tempo mais rápido?

Ricket

@Ricket ai-blog.net/archives/000152.html

Shawn Mclean

Peguei, obrigado! Já ouvi falar deles, mas nunca fez nada com eles para que eu não reconhecer o nome condensada :)

Ricket

Respostas:

Faça sua escolha:

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Há uma carga de heurísticas descritas nesse link, para velocidade ou precisão. Sempre há uma troca, então eu diria que os desenvolvedores usariam a heurística mais precisa que causaria impacto mínimo no desempenho de seus jogos.

Ray Dey
fonte

Estes são para mapas de grade. As malhas de navegação que eu suponho usariam uma heurística diferente para passar de um poli para o outro. Provavelmente, alguma forma de heurística da geometria para selecionar o próximo melhor poli com base no tamanho da aresta ou algo assim.

Shawn Mclean

Concordado, mas as heurísticas são usadas para estimar o caminho mais curto para o destino absoluto final para ajudar no custo do próximo poli. Eles devem subestimar a distância para ser uma "heurística admissível". Uma malha de navegação ainda é um gráfico, assim como um mapa de grade é um gráfico. Então, eu acho que a maioria dessas heurísticas é aplicável, cabe ao desenvolvedor ver qual é a mais aplicável.

quer

Uma heurística muito, muito difícil (mas muito rápida) de usar é: (distância de Manhattan)

vec1 = start vector
vec2 = end vector

heuristic = abs(vec2.x - vec1.x) + abs(vec2.y - vec1.y))

Isso evita qualquer enraizamento quadrado, o que pode ser caro (distância de Pitágoras).

O Pato Comunista
fonte

Distância de Manhattan, não?

precisa

Eu pensei que era, então editei-o desde que eu pensei que não poderia ter sido.

The Duck Comunista

Você também pode usar o comprimento ao quadrado (distância de Pitágoras sem pegar a raiz quadrada). É rápido e muito provavelmente uma heurística melhor do que Manhattan distância (a menos que o seu personagem só pode mover horizontalmente e verticalmente)

bummzack

@bummzack: Por favor, leia a seção "Distância euclidiana ao quadrado" da página heurística de Amit. A distância ao quadrado não é uma heurística admissível e resultará em um caminho abaixo do ideal.

As distâncias quadradas são muito pequenas para distâncias curtas (A * perdem tempo) e muito grandes para longas distâncias (A * encontra caminhos piores). Existem boas razões para superestimar as distâncias heurísticas, mas evitar o sqrt não é uma delas. Use uma aproximação rápida do sqrt ou use uma distância diagonal ou, se o gráfico de navegação for explícito, calcule a distância euclidiana / pitagórica uma vez e armazene-a com a borda entre os nós.

Amitp