Planejamento de caminho para volumes em jogos

Como você planejaria um volume para um jogo?

Por exemplo, um cubo de 1 km com túneis e cavernas. Além disso, o terreno é destrutível.

Você tem modos de andar e voar.

Eu o separaria em fases. Crie um volume do espaço aberto. Encontre um caminho que leve em consideração a destruição dinâmica.

O desempenho é uma grande preocupação e a capacidade de encontrar caminhos usados ​​em pouco tempo.

Exemplo concreto: garimpa algo profundo no solo de maneira eficiente.

O chão é destruível. "Cavernas" são fáceis de cavar áreas. Mineração é como voar. Precisa ver com sensores. O conjunto de dados é enorme. Precisa construir um caminho de transporte para o destino. Pode ser multi-agente.

A busca dinâmica de caminhos, para ter um desempenho razoável, requer um algoritmo especificamente adequado a isso, como D * (Dynamic A *).

Além disso, você poderá encontrar uma maneira de executar a busca hierárquica de caminhos. Dessa forma, você tem um caminho mais simples em uma resolução mais baixa e subcaminhos mais complexos em resoluções mais altas. Ao substituir qualquer subgrafo de caminho de resolução mais alta no gráfico mestre de resolução mais baixa, você pode elaborar seu caminho para a resolução que desejar.

O pathfinding de resolução mais baixa é obviamente ótimo, pois você pode fazer o pathfinding mínimo até entrar em outra sub-região e, em seguida, executar um pathfinding mais aprofundado no nível de subdivisão dessa região.

Quanto ao algoritmo real usado para executar o tunelamento em seu espaço 3D, o maior problema em potencial que você enfrentará é entrar em áreas "sem saída" 3D das quais você não pode sair sem cruzar outra passagem (segmento gráfico). Veja meu monólogo recente sobre incorporamentos de gráficos planares aqui .

Se por um terreno destrutível você quer dizer grandes mudanças no enorme ambiente multinível, isso será difícil, especialmente para as unidades de caminhada. Seria sensato dividir as unidades voadora e ambulante desde o início, para que eles tenham gráficos separados.

Não posso dizer que conheço uma solução definitiva para as unidades de caminhada. Dependendo da quantidade de agentes, possíveis alterações no terreno e resolução do nó do cubo, você pode ou não usar o D *. Em essência, D * é uma força bruta A *. Como Nick sugeriu, forçar brutal apenas um passo à frente pode resultar em muitos "becos sem saída", pois sem todo o caminho, você não será capaz de dizer imediatamente se o próximo nó está correto ou não. Além disso, você terá que pensar no cache do caminho e em sua invalidação parcial, para que não precise usar força bruta constantemente por agente. No geral, não será fácil e pode se tornar muito pesado para a CPU.

Indo com A *, o caso mais simples seria limitar ao mínimo a destruição de seu terreno e fugir com a busca hierárquica de caminhos, como A * "grosso" e alguma forma de prevenção local. Eu acho que não é uma opção, então você pode tentar converter o chão e as paredes do seu cubo em uma malha de navegação e alterá-lo parte por parte. O cálculo do Navmesh não é rápido, é claro, mas existe um espaço para várias otimizações para evitar o recálculo completo da referida malha após uma mudança de terreno. A idéia geral é executar atualizações de malha local, para que apenas as regiões afetadas de uma malha de navegação sejam alteradas quando ocorrer a destruição do terreno. Isso poderia ser feito usando a adaptação da construção do diagrama de Voronoi, mas não é uma "área resolvida". Também não será fácil, pois você precisará acelerar o recálculo da malha de navegação,

O gráfico para unidades aéreas é muito mais simples. Basicamente, você terá que encontrar todo o "espaço aéreo" e convertê-lo no gráfico. Como suas cavernas são dinâmicas, a escolha mais óbvia é basear esse gráfico na octree de um cubo. Use os centróides foliares octree (ponto no meio do cubo foliar) como base para o cálculo dos nós e filtre todos os centróides nas posições obviamente inválidas. Verifique os centróides resultantes para remover todos os inacessíveis de seus vizinhos. Isso será muito rápido, portanto, suas principais preocupações permanecem no caminho do caminho.

Eu tenho uma implementação de código aberto do pathfinding em uma grade 3D como parte do SDK do jogo voxel. É uma implementação do algoritmo A * destinada exatamente a ambientes estilo minecraft e terrenos voxel.

Não é um algoritmo dinâmico, como sugeriram outras pessoas, por isso não posso ajudá-lo. Eu acho que depende da dinâmica do seu mundo. Ele também pode usar algumas melhorias de desempenho, pois atualmente pode levar alguns segundos para encontrar um caminho com talvez 100 voxels, mas você pode executá-lo em uma versão com amostragem reduzida do seu volume (por favor, tome cuidado durante a redução da amostra como válida caminhos podem ser criados / perdidos).

Você pode vê-lo em ação aqui http://www.youtube.com/watch?v=C8y0OzL0zpM (embora esse não seja o meu jogo) e obtenha a fonte em http://www.thermite3d.org .

Se seu mundo já é construído a partir de blocos discretos, faz sentido usá-los como base para sua navegação.

Desbravadores são desbravadores fáceis e rápidos, um pouco mais difíceis. O caminho a seguir e responder às mudanças no mundo é a verdadeira maldade.

Há algumas perguntas que podem ajudá-lo a diminuir a solução em potencial: - que tipo de NPCs você está tentando simular? - quanto tempo você está procurando? - quão precisos caminhos você precisa?

Se você tem caminhos curtos e está bem com a qualidade "melhor que a direção", as grades locais [1] são uma boa escolha. Eles são super rápidos, você pode fazê-lo funcionar em 2D e 3D. Você pode obter dados da grade local diretamente dos dados do volume, para que o gráfico de navegação fique sincronizado com as alterações dinâmicas facilmente.

O problema com as redes locais é que, se você tiver mínimos locais em seu mundo maiores que sua rede local, o agente poderá ficar preso. É possível fazer truques como adicionar migalhas de pão em locais onde você detecta mínimos locais e tenta evitar esses locais ao pesquisar.

Se você precisar de caminhos longos, sugiro algum tipo de esquema hierárquico. O HPA * deve fornecer boas idéias sobre como criar nós esparsos na grade em um mundo. As grades locais podem resolver a localização do caminho entre os nós de alto nível. Ao fazer alterações no mundo, você também precisará alterar localmente os nós grossos. Você também pode usar os nós para detectar mudanças dinâmicas no mundo do jogo e replanejar o caminho.

Se você tem um mundo dinâmico, a busca de caminhos se torna estatística. Não há mais garantias se o agente encontrar o caminho. Acompanhar as mudanças no mundo é realmente difícil e replanejar quando algo dá errado é lento.

Eskil monta com essa idéia no Love MMO, e seu localizador de caminhos é apenas uma amostra aleatória com a função utilidade (assim como sua seleção de ações :)). Eu recomendaria fazer isso primeiro se ele se adequar ao seu estilo de jogo.

[1] http://digestingduck.blogspot.com/2010/03/local-navigation-grids.html

Você deseja adotar uma malha de navegação ou, se o mundo estiver particularmente barulhento na vertical, e não apenas nas plataformas, ou se o modo de vôo for mais do que apenas pular ou pairar, você poderá usar volumes de navegação.

O desvio é uma biblioteca de localização de caminhos que permite atualizar a malha de navegação ao vivo. Eu nunca usei, não sei como funciona na sua escala. Um sistema hierárquico parece ser uma boa ideia.

Uma boa leitura quando você pensa em escrever sua própria é uma pesquisa recente sobre quebra de simetria . Vale a pena ler atentamente!

É preciso considerar se o nevoeiro de guerra deve afetar as decisões de busca de caminhos. Pode ser que, se for solicitada a mudança para uma nova área, uma unidade deve se mover em linha reta até encontrar obstáculos, ou pode ser que a unidade faça uma rota com conhecimento completo do mapa. Essa é uma escolha de jogo.

Leitura divertida: Fixando o Pathfinding de uma vez por todas