Caminho da "linha de visão" através da malha de navegação

9

Quero calcular a linha de visão em uma malha de navegação.

Considere a imagem abaixo: a linha amarela é o resultado de apenas A * e a linha vermelha é o resultado do algoritmo de uma linha de visão "que usa a linha amarela como entrada. Agora, a unidade pode se mover diretamente sem" zigue-zague ".

O que é um algoritmo para calcular essa "linha de visão"?

insira a descrição da imagem aqui

Yannick Lange
fonte

Respostas:

6

Você está procurando um algoritmo de funil.

Aqui você é simples

http://digestingduck.blogspot.com.es/2010/03/simple-stupid-fupidnel-algorithm.html

Basicamente, o algoritmo identifica arestas como portais e constrói um funil que é testado em relação ao vértice das arestas para verificar se estão dentro ou não do funil.

Na etapa A, o funil é construído com a posição inicial e o portal cruzado pela linha amarela.

Na etapa B, o próximo portal é verificado, o vértice superior fica dentro do funil e, portanto, a linha superior do funil passa por ele. Mas o vértice inferior está fora do funil porque a linha vermelha está embaixo da linha verde; portanto, a linha inferior não passará por ele, continuará passando pelo vértice inferior do portal anterior.

Como você pode verificar, o funil será menor e menor até a etapa F, onde não é possível construir o funil, porque a linha vermelha cria um funil ruim, portanto o vértice superior é escolhido como novo ponto de partida e um novo funil seria ser construído se o ponto final não estiver nessa malha.

insira a descrição da imagem aqui

Perceba que esse tipo de algoritmo também permite uma solução simples para o problema do tamanho do modelo, porque você pode considerar que os portais são menores pelo raio de 2x do seu modelo.

insira a descrição da imagem aqui

Blau
fonte
6

Existe uma técnica simples que pode ser usada com caminhos gerados usando essa ideia de linha de visão. Basicamente, você deseja percorrer o caminho e, em cada nó, "olhe para trás" dois antes do último para ver se está visível. Se o nó anterior ao último estiver visível, é possível remover o último nó (já que você tem uma linha de visão entre o nó atual e o nó anterior, o último nó, sendo um nó intermediário, não é necessário).

insira a descrição da imagem aqui

Um artigo do Gamasutra tem o seguinte exemplo de pseudo-código:

checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next

Esse algoritmo é o que você deseja, onde a Walkablefunção é essencialmente uma função de linha de visão, mas é ligeiramente aprimorada para incluir também situações em que o caminho é visível, mas não pode ser percorrido (por exemplo, fossas, armadilhas, zonas restritas).

MichaelHouse
fonte
Entendo o que você está dizendo, mas ainda não sei como calcular a linha de visão. Você poderia descrever o que estaria na função Walkable usando uma malha de navegação em triângulo?
Yannick Lange
Essa resposta é de cerca de grade com base pathing, e é inútil em um cenário de malha de navegação
Blau