Como fazer o caminho de starcraft?

Eu tenho tentado descobrir como implementar algo como a busca de caminhos no Starcraft 2. Não estou procurando todos os recursos sofisticados, como flocagem, filas etc. Na verdade, eu gosto de como no Starcraft 1 as unidades interferem entre si. de outros. Mas eu quero um localizador de caminho melhor do que o usado no Starcraft 1.

Nas pesquisas do Google que fiz, as várias respostas têm algo a ver com A * em uma malha de navegação e / ou lidar com algum tipo de "gráfico de visibilidade". Mas recebi respostas um tanto conflitantes ou pouco claras sobre o que devo fazer.

Uma coisa sobre a qual li tem algo a ver com A * sobre os vértices de uma malha de triângulo (a malha de navegação). E então, de alguma forma, "endireitando o caminho", que eu não sei fazer. Mas isso não garante a otimização, certo?

Outra pergunta que eu tive é como o caminho do starcraft 2 lida com o fato de que as unidades são discos com um raio finito e não apontam ao lidar com cantos? E como lidar com obstáculos dinâmicos, como unidades inativas ou mesmo outras unidades móveis.

Estou procurando algumas explicações detalhadas e não as visões gerais genéricas de alto nível, típicas dos resultados de pesquisa.

Se isso importa, eu já vi as anotações de Amit sobre localização de caminhos . Já ouvi falar, mas não li, de Geometria Computacional: Algoritmos e Aplicações . E um post de blog sobre uma apresentação de navegação de IA na GDC 2011 mencionou que Starcraft 2 usa uma triangulação delaunay restrita para uma malha de navegação. Embora a postagem do blog mencione Boids steering e "horizon analysis", ela não menciona exatamente como a busca de caminho principal é feita na navmesh.

Se você possui o Starcraft 2 instalado, abra o editor de mapas e alterne o caminho . Você poderá ver como a malha nav é construída ao colocar edifícios e outros obstáculos ao redor.

Na verdade, eu gosto de como no Starcraft 1 as unidades interferem umas com as outras. Mas eu quero um localizador de caminho melhor do que o usado no Starcraft 1.

Não deveria ser um problema - a busca de caminhos de Starcraft 1 era boba. Esta postagem de blog de um dos programadores fala sobre isso.

Uma coisa sobre a qual li tem algo a ver com A * sobre os vértices de uma malha de triângulo (a malha de navegação). E então, de alguma forma, "endireitando o caminho", que eu não sei fazer. Mas isso não garante a otimização, certo?

Trata-se de tornar a IA não mais burra que a ideal. Suas unidades terminam com movimento em zigue-zague entre os nós, se você não aplicar um pouco de suavização.

Ao planejar o caminho, você terá um estágio de aprimoramento no qual examinará os nós que sua unidade precisa percorrer para atingir seu objetivo e, em seguida, começará a remover nós em excesso no meio do caminho que não precisamos. siga, ou seja, podemos ir diretamente do nó A para o nó C a B sem colisões estáticas, portanto ignore B completamente.

Isso acaba endireitando o caminho.

Estou procurando algumas explicações detalhadas e não as visões gerais genéricas de alto nível, típicas dos resultados de pesquisa.

Se você quiser uma explicação sólida, isso já está bem abordado nos livros (inclusive no código do jogo em funcionamento). Portanto, se você tiver algum dinheiro para gastar, consulte Programar AI de jogo por exemplo e / ou Inteligência artificial para jogos . Ambos discutem esses tópicos em grande profundidade.