Recentemente, tenho investigado o Anya Algoritmo de busca de caminho. Anya é um algoritmo best de qualquer ângulo.
No entanto, funciona apenas com pontos discretos na grade. Aqui está um trecho do jornal “Pathing de qualquer ângulo best na prática” pelo inventor do algoritmo (Daniel Harabor):
Finalmente, o problema de qualquer ângulo de ângulo é aquele que requer como entrada de um par de pontos discretos, S e T, e pede um caminho de qualquernânia que os conecte. O ponto S designa a localização da fonte (equivalente, início), enquanto o ponto T designa o native do destino (equivalente, objetivo).
Isso confirma o que vejo no código de exemplo fornecido. Eu implementei uma GUI para mostrar alguns problemas. As células cinzentas escuras representam células bloqueadas. As células brancas representam células camocáveis. A posição inicial é exibida em verde e a posição de destino é exibida em vermelho.
Para este aplicativo, truquei os locais decimais das coordenadas X e Y das posições de origem e alvo. A lógica é que as posições de n.00 até n.999 estão dentro da célula n; portanto, devo respeitar se a célula n é bloqueada ou acessível. (Se houver uma alternativa melhor ao truncamento, me avise!)
No primeiro exemplo, apenas o caminho encontrado por Anya, que leva diretamente de (2,2) a (4,2), é desenhado. Para obter o caminho actual que o agente deve seguir, conecto a posição inicial e a posição de destino ao caminho calculado.
Obviamente, esse não é o caminho best. Aqui, ainda se pode aplicar os princípios de suavização do caminho relativamente padrão, por exemplo, em vez de começar com o primeiro ponto encontrado, executar verificações da linha de visão da posição inicial da unidade até os múltiplos pontos do primeiro segmento do caminho e selecionar o ponto mais distante que ainda tem uma linha de visão para a posição inicial. Fazer isso (dependendo da quantidade de verificações de linha de visão) pode levar a um caminho melhorado, como mostrado aqui:
Portanto, neste caso, um bom caminho pode ser encontrado. Mas esse não é o caso de todas as entradas.
Considere o próximo exemplo: aqui as posições de início e alvo da unidade estão mais na parte inferior da célula. Aqui, obviamente, o caminho ao redor do lado inferior do obstáculo levaria ao caminho mais curto. No entanto, como as coordenadas X e Y da posição inicial ainda são truncadas para os mesmos valores discretos X e Y. Assim, Anya recebe os mesmos dados de entrada do exemplo anterior e, consequentemente, encontre o mesmo caminho.
Infelizmente, a suavização de verificação da linha de visão não pode ajudar aqui para encontrar o caminho mais curto, pois o caminho retornado por Anya atravessa o obstáculo do lado errado (em vez de baixo).
Portanto, minha pergunta é como posso resolver esse problema enquanto ainda usa o algoritmo Anya Pathfining. (e não mudar para Navmeshes) pensando nisso, outros algoritmos de busca de caminho baseados em grade não teriam o mesmo problema? Existem soluções reais e eficientes para outros algoritmos?
Ou esse é um dos casos, que a maioria das pessoas apenas vive com o caminho quase best? O que parece estranho de aceitar, ao aplicar especificamente um algoritmo best de qualquer ângulo de ângulo.
Editar Em relação ao arredondamento proposto pelo engenheiro:
É claro que eu pensei em arredondar para o canto mais próximo. No entanto, ao tentar isso com o código de amostra fornecido pelo autor, em alguns casos, nenhum caminho poderia ser encontrado, embora estivesse claro que existe um caminho válido. No entanto, após sua sugestão, analisei isso novamente e parece que isso é mais uma limitação com o código de amostra do que com o algoritmo e pode ser corrigido.
O verdadeiro problema é que o arredondamento não resolve completamente o problema, mas apenas o reduz. Veja o seguinte exemplo:
Aqui, a posição inicial é arredondada no canto inferior direito da respectiva célula e a posição da meta é arredondada no canto superior esquerdo da respectiva célula.
Portanto, da perspectiva de Anya, o comprimento dos caminhos para atingir a posição do alvo é o mesmo, independentemente de o caminho seguir abaixo ou acima do obstáculo. Aqui é ilustrado o caminho encontrado por Anya:
Considerando que, ao considerar as posições reais de início e alvo, fica claro que o caminho deve percorrer o obstáculo.
Portanto, ainda estou procurando uma solução para esse problema. A solução provavelmente requer adaptar o algoritmo Anya para considerar as posições exatas de início e alvo. No entanto, ainda não tenho certeza de como isso é melhor feito.