A * localização do caminho de malha de navegação

15

Então, eu tenho feito esse jogo java 2D de cima para baixo nesse quadro chamado Greenfoot e tenho trabalhado na IA para os caras com quem você vai lutar. Quero que eles sejam capazes de se mover pelo mundo de forma realista, para que logo percebi, entre outras coisas, que eu precisaria de algum tipo de busca de caminhos.

Eu fiz dois protótipos A *. Uma é baseada em grade e, em seguida, eu criei uma que funcione com pontos de referência. Agora, preciso descobrir uma maneira de passar de um "mapa" 2d dos obstáculos / edifícios a um gráfico de nós dos quais posso fazer um caminho. O pathfinding real parece bom, apenas minhas listas abertas e fechadas poderiam usar uma estrutura de dados mais eficiente, mas eu chegarei a isso se e quando precisar.

Pretendo usar uma malha de navegação por todas as razões descritas neste post no ai-blog.net . No entanto, o problema que enfrentei é que o que A * considera o caminho mais curto dos centros / bordas dos polígonos não é necessariamente o caminho mais curto se você viaja por qualquer parte do nó. Para ter uma idéia melhor, você pode ver a pergunta que fiz no stackoverflow .

Eu recebi uma boa resposta sobre um gráfico de visibilidade. Desde então, comprei o livro ( Geometria Computacional: Algoritmos e Aplicações ) e continuei lendo o tópico, mas ainda sou a favor de uma malha de navegação (consulte " Gerenciando a Complexidade " nas Notas sobre localização de caminhos do Amit ). (Como uma observação lateral, talvez eu possa usar o Theta * para converter vários waypoints em uma linha reta, se o primeiro e o último não forem obscurecidos. Ou sempre que eu voltar, verifique o waypoint antes da última para ver se consigo ir direto de isso para isso)

Então, basicamente, o que eu quero é uma malha de navegação em que, depois de inseri-lo em um algoritmo de funil (por exemplo, este do Digesting Duck ), obtenho o caminho mais curto verdadeiro, em vez de um que seja o caminho mais curto, seguindo apenas o nó, mas não o menor, já que você pode passar por alguns polígonos e pular nós / arestas.

Ah, e também quero saber como você sugere que você armazene as informações relativas aos polígonos. Para o exemplo de protótipo de waypoint que criei, tinha apenas cada nó como um objeto e armazenei uma lista de todos os outros nós para os quais você poderia viajar a partir desse nó, acho que isso não funcionará com polígonos? e como saber se um polígono é aberto / passável ou se é um objeto sólido? Como armazeno quais nós compõem o polígono?

Finalmente, para constar: eu quero programar isso sozinho do zero, mesmo que já haja outras soluções disponíveis e não pretendo (re) usar esse código em outra coisa que não seja este jogo, para que não importe que inevitavelmente, será de baixa qualidade.

raiva
fonte
Não tenho certeza, mas esses links podem ajudar: gamedev.stackexchange.com/questions/1327/… gamedev.stackexchange.com/questions/8087/… também havia outra pergunta sobre a localização de caminhos que não consigo encontrar agora , que recebeu uma recompensa e teve uma resposta muito boa.
Ali1S232
Sim, no segundo link, você pode ver minha principal preocupação, o algoritmo A * daria o caminho ao redor do fundo como o mais curto usando os pontos médios da borda, mas o caminho ao redor do topo do obstáculo é realmente o mais curto. Quero saber como posso obter A * para me dar o caminho em volta do topo, que depois endireitarei (por um algoritmo de funil, por exemplo) para obter o verdadeiro caminho mais curto, onde, como se ele me desse o caminho mais baixo, mesmo que eu o endireite, ainda está fazendo um desvio.
angrydust
Na verdade, acabei de ler o artigo em gamedev.stackexchange.com/questions/8087/… e parece funcionar encontrando uma rota com A *, calculando seu custo real com um algoritmo de funil modificado e depois encontrando outra rota e calculando sua custo real novamente e ver se é mais curto que o outro. Repete-se até saber que encontrou a rota mais curta. Isso realmente resolve o meu problema, no entanto, parece que será muito lento, pois você está repetindo tanto a correção quanto a localização de caminhos, o que seria bastante caro.
angrydust
Armazenamento de polígonos: armazene apenas os polígonos visíveis - ou associe uma tag a cada polígono (lembre-se de que cada polígono precisará ser uma lista circular de vértices); Da mesma forma que com os nós, você pode armazenar o ID do polígono de onde eles se originam - mas não preciso dizer isso: é um armazenamento de dados elementar. Finalmente, por que você se importa com o verdadeiro caminho mais curto? Seu jogo pode ficar lento ou você pode ter caminhos ligeiramente incorretos: escolha um. Obter o caminho mais curto verdadeiro REQUER uma pesquisa completa (pelo menos em um gráfico de nós).
Jonathan Dickinson
@ JonathanDickinson Eu sei que não preciso de um caminho que seja 100% preciso até o último pixel, e sei que posso usar A * para produzir caminhos que serão no máximo p admissíveis. A coisa está percorrendo um longo caminho com um obstáculo tão claramente, como na minha pergunta anterior sobre estouro de pilha ou em gamedev.stackexchange.com/questions/8087/… é simplesmente demais. Não posso deixar minha IA andar dessa maneira em torno de um obstáculo!
23911 Angrydust

Respostas:

14

Aconselho que, mesmo que você escreva todo o seu próprio código, faça o download do Recast e construa o aplicativo de amostra, pois possui visualizações que mostram a navmesh gerada e permite testar a localização de caminhos com um simples ponto e clicar em interface. Você pode aprender muito apenas brincando com isso.

Como você já percebeu, existem duas etapas para produzir um caminho de boa aparência - o localizador A * e, em seguida, o pós-processamento subsequente, que inclui o endireitamento do caminho (a eliminação de todas as curvas não é necessária para evitar obstáculos) e possivelmente também o adição de curvas nos pontos de viragem.

Encontrando o caminho

Você tem a parte A * dominada, o que é ótimo. Você também observou que A * nem sempre encontrará o caminho mais reto. É crucial entender que isso ocorre porque A * é um algoritmo para encontrar o caminho mais curto através de um gráfico (sendo um conceito matemático em que os nós não têm dimensão) quando você o aplica a uma malha, é necessário mapear os nós para elementos de malha de alguma forma.

A coisa mais óbvia a fazer é navegar do ponto central do polígono para o ponto central e basear o custo nessa distância, mas isso tem alguns problemas. Uma é que nem sempre encontrará o caminho geometricamente mais curto e a segunda é que, se você tentar seguir o caminho que calculou, notará que uma linha reta de um centro para o próximo pode cruzar um polígono que não é. faz parte do caminho (e pode não ser navegável). Não é uma maneira terrível de custar o percurso do gráfico durante a execução de A *, mas claramente não é adequado para nenhuma finalidade de percurso.

A próxima solução mais simples é executar A * de ponta a ponta através da malha. Você achará isso mais simples de pensar se imaginar que, em vez de um nó por polígono, você tem um por borda por polígono. Portanto, seu caminho vai do ponto inicial até a borda mais próxima, passa para a borda do polígono adjacente e depois para a borda seguinte no mesmo polígono e assim por diante. Isso produz o caminho mais curto com mais frequência e também tem a vantagem de ser percorrível se você não desejar executar uma etapa de endireitamento de caminho.

Endireitamento de caminho

O algoritmo usado no Detour (a biblioteca de navegação que acompanha a reformulação) é bastante simples. Você deve observar que ele apenas endireitará o caminho dentro dos limites dos polígonos encontrados durante a pesquisa A *. Como tal, se isso não encontrar o caminho mais restrito em torno de um obstáculo, você não o encontrará depois de executar esse algoritmo. Na prática, os navmeshes produzidos pela reformulação tendem a ter um único polígono pelo qual você pode passar ao navegar em um ponto de estrangulamento (o ponto mais próximo entre dois obstáculos) e, portanto, A * sempre produzirá uma lista de nós que estão tão próximos do obstáculo quanto possível. possível. Se você estiver usando blocos como navmesh, esse não será o caso e esse algoritmo muito simples inserirá curvas espúrias.

O algoritmo de endireitamento de caminho do desvio não tem complexidade O (n) porque, quando determina que precisa inserir uma curva, ele o insere no ponto em que apertou o funil pela última vez para a esquerda (ao virar à esquerda e vice-versa) e depois começa a rastrear os nós a partir desse ponto novamente.

Se você deseja corrigir o caminho fora dos polígonos que fazem parte da rota A *, as coisas ficam muito mais complexas. Você precisará implementar uma rotina de transmissão de raios que possa testar se dois pontos na sua navmesh podem se ver (você deve ter isso de qualquer maneira para poder ver se precisa usar A *). Você faz isso cruzando o segmento de linha formado por origem-> alvo com as arestas de conexão do polígono que contém a origem e testando as arestas de conexão do polígono que o move para dentro e assim por diante. Se você cruzar uma aresta não conectada (eu as chamo de arestas de borda), você encontrará um obstáculo.

Em seguida, você pode executar esse teste de conversão de raios sempre que o algoritmo de funil determinar que ele precisa inserir uma curva para ver se realmente funciona, mas acho que você precisará continuar executando esse teste em todos os nós até inserir uma curva (em ponto em que você pode reverter para o algoritmo de funil simples). Isso vai ficar caro, tornando o caminho endireitado aproximadamente O (n ^ 2).

Representando a navmesh

Você pode representar sua malha como uma matriz de classes de polígono. A classe de polígono pode ser tão simples quanto uma matriz de vértices e uma matriz de referências ao polígono adjacente para cada aresta, se houver uma. É claro que você provavelmente pode pensar em maneiras de armazenar isso de forma mais compacta. Como um vértice geralmente é compartilhado por vários polígonos, é normal ter uma grande matriz de vértices e, em seguida, cada índice de armazenamento de polígonos nessa matriz. Dependendo das características da sua navmesh, você pode ter um número médio de arestas de conexão que representam apenas 50% ou menos do número de arestas. Nesse caso, convém armazenar um link para outro polígono e o índice da aresta, em vez de armazenar um link para cada aresta. Também recomendo que você armazene o índice do polígono na matriz de polígonos do navmesh em vez de usar uma referência de classe.

U62
fonte
Acabei de ler brevemente isso, mas entendo que você nunca deve usar o quadrado da distância (ou não o quadrado) para A *: theory.stanford.edu/~amitp/GameProgramming/…
angrydust
Eu não estou realmente preocupado com como realmente executar o caminho de endireitamento do atm, o que me preocupa é o que você diz: "Você deve observar que ele apenas endireitará o caminho dentro dos limites dos polígonos encontrados durante a pesquisa A * Como tal, se isso não encontrar o caminho mais apertado em torno de um obstáculo, você também não encontrará um caminho apertado depois de executar esse algoritmo. "
angrydust
Quero ter uma malha de navegação em que A * sempre encontre o caminho que, uma vez corrigido, seja o mais curto, independentemente do custo de viajar por vértices / pontos médios. Compreendo que isso possa ser feito com os gráficos de visibilidade, mas quero usar uma navmesh porque possui muitos outros benefícios e porque a complexidade de um gráfico de visibilidade pode crescer muito rapidamente: theory.stanford.edu/~amitp/GameProgramming/…
angrydust
@theguywholikeslinux, você pode usar a distância euclidiana sqrt(x*x + y*y)- mas não a mais barata por nó x*x + y*y.
Jonathan Dickinson
@ JonathanDickinson Eu sei, daí o meu ponto.
23911 Angrydust