Atualmente, estou fazendo uma pesquisa de busca de caminhos e minha simulação é a seguinte: Eu tenho uma cena 3D com um ponto inicial e final representado, sou capaz de criar malhas de navegação, waypoints e polígonos para ajudar na busca de caminhos.
Eu tentei um algoritmo A * e algumas de suas variantes e elas funcionam perfeitamente. No entanto, agora estou mais interessado em encontrar caminhos 'dinâmicos'. Por exemplo, ao encontrar um caminho do ponto A ao ponto B, se um novo obstáculo aparecer repentinamente, quero que meu algoritmo possa imediatamente planejar novamente um caminho e não começar a pesquisar do zero novamente.
Eu li algumas vezes o algoritmo D * e me perguntei se isso seria apropriado para o que eu precisava ou isso pareceria um exagero.
Então, minhas perguntas são basicamente: Qual algoritmo seria melhor para o Pathfinding dinâmico em tempo real? OU que combinação de técnicas eu poderia usar?
fonte
Respostas:
D * está bastante envolvido - não recomendo tentar implementá-lo. Mesmo quando os projetos são bem financiados e estão sendo desenvolvidos por pessoas inteligentes / experientes, o D * lite é usado, porque D * é uma dor para acertar.
Você pode estar interessado nesta apresentação, que inclui uma discussão sobre o caminho do Left 4 Dead:
http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf
Uma abordagem é usar uma pesquisa grosseira de nível A * para obter um caminho geral para um agente e, em seguida, fazer uma pesquisa fina no nível A * para o ambiente local de um agente. Dessa forma, você pode recompilar rapidamente a pesquisa A * dos detalhes do curso, se o terreno mudar e, em seguida, recompilar rapidamente a pesquisa A * de detalhes finos para um pequeno segmento do ambiente. Isto não é perfeito. Funciona desde que seus obstáculos não possam bloquear vários nós gráficos de detalhes do percurso, o que é bom para a maioria dos jogos. Esse é o método recomendado se você tiver menos de 100 agentes.
Se você deseja oferecer suporte a centenas ou milhares de agentes, pode implementar algo como multidões contínuas. Veja esta pesquisa: http://grail.cs.washington.edu/projects/crowd-flows/ Que discute um método puramente baseado em CPU que pode suportar milhares de atores em um ambiente dinâmico.
Se você deseja oferecer suporte a dezenas de milhares ou centenas de milhares de agentes, pode implementar algo como multidões contínuas, com assistência da GPU. Consulte aqui a pesquisa relevante: https://a248.e.akamai.net/f/674/9206/0/www2.ati.com/misc/siggraph_asia_08/GPUCrowdSimulation_SLIDES.pdf
Aqui está um vídeo demonstrando multidões contínuas em ação: http://www.youtube.com/watch?v=lGOvYyJ6r1c (pule para 4:10 para ver grandes obstáculos dinâmicos, como carros e semáforos, afetando centenas de pessoas andando pela cidade).
fonte
Você já observou comportamentos simples de direção?
http://www.red3d.com/cwr/steer/
Você pode usá-los para se desviar do seu caminho A *, a fim de evitar obstáculos locais, e depois voltar ao seu caminho assim que terminar.
Também é bastante fácil combinar vários comportamentos.
fonte
Como sua postagem está na parte "Desenvolvimento de jogos" da troca de pilhas, eis o que a maioria dos programadores de jogos responderia: Não se trata de busca dinâmica de caminhos em tempo real, trata-se de um caminho dinâmico em tempo real * a seguir *!
Em alguns casos de borda em que uma borda no gráfico de navegação está totalmente obstruída, o pathfinder deve recalcular outro caminho, mas na maioria das vezes você pode simplesmente orientar suas entidades em torno dos obstáculos, fazendo a previsão de posição e evitando na direção certa. Para a maioria dos jogos, seria muito pesado ter que prever ao longo do tempo a posição dos agentes dinâmicos, especialmente porque você não pode prever com precisão as ações dos jogadores ou as decisões dos agentes.
Portanto, meu conselho seria começar implementando o Steering Behaviors (http://red3d.com/cwr/steer/), lidar com casos em que o caminho se torna impossível e, em seguida, adicionar uma camada em cima dele para lidar com casos extremos que não são ' tratado pelas duas soluções anteriores.
Espero que isto ajude
fonte