Localização de caminhos com movimento 2D, não baseado em grade, em terrenos uniformes

12

Estou procurando a melhor solução para encontrar caminhos no meu jogo. O mapa é basicamente baseado em grade, mas as entidades são posicionadas usando carros alegóricos e podem se mover em qualquer direção para qualquer ponto do mapa. O 'terreno' do meu jogo tem um custo de movimento uniforme, mas é claro que pode haver obstáculos que bloqueiam o caminho. A maioria dos obstáculos será estática e, embora existam outras entidades animadas no jogo, eu posso me safar por não considerá-las - é um jogo de estratégia isométrico no estilo de hospital temático , portanto, sem brigas.

A maioria dos artigos de localização de caminhos que eu vi cobrem movimento 3D ou 2D baseado em grade. Alguma sugestão para algo que possa cobrir meu caso de uso? Muito Obrigado.

tommaisey
fonte
Não há tempo para uma resposta adequada no momento, mas você pode querer analisar esta pergunta: stackoverflow.com/questions/4054701/… .
Christian

Respostas:

14

Isso é chamado de "problema de localização de caminho em qualquer ângulo". Você basicamente tem duas opções:

  1. Gere uma malha de navegação para o seu mapa e pesquise sobre ela usando A *

    Malha de navegação

  2. Pesquise sobre uma grade usando um algoritmo destinado especificamente à busca de caminhos em qualquer ângulo. Tradicionalmente, a maneira de fazer isso era a suavização de caminho A * + (interpolação linear, etc) , mas hoje em dia uma alternativa mais popular é o Theta * , que é mais fácil de implementar, roda mais rápido e produz melhores resultados do que o suavização de caminho.

    Teta * vs. suavização de caminho

Todos os métodos acima geram resultados quase ótimos. Se, por algum motivo, você precisar de ótimos resultados, este documento foi lançado há algumas semanas. Ainda não tive a chance de lê-lo, então não sei o quão eficiente é, nem quão difícil é sua implementação.

BlueRaja - Danny Pflughoeft
fonte
Ótimo, obrigado! Não preciso de resultados totalmente ideais, desde que estejam próximos.
tommaisey
1
Apenas pensei em adicionar este artigo aos que você listou. Parece uma versão mais sucinta do artigo que você vinculou, por um dos autores do artigo original. Eu acho que vou com Theta *, felicidades.
Tommaisey
Link não funciona. Atualize a resposta.
firelynx