Planejamento de caminho para volumes em jogos

7

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.

Fogo
fonte
11
Existe um nevoeiro de guerra e deve afetar a busca de caminhos?
Vai
Há uma linha de visão, embora você possa conectar sensores.
Fogo
Você está trabalhando no design de níveis - projete um nível, configurando os túneis e cavernas (iniciais, pré-danificados) semanas antes do jogo ser jogado? Ou você está trabalhando na busca de caminhos - programando agentes controlados por computador para que, durante o jogo, eles se movam "razoavelmente", em vez de fazer coisas idiotas, como caminhar contra paredes, cair de penhascos etc.?
David Cary
Ninguém vai passar semanas projetando a geologia do cubo de 1 km. A questão não é gerar geologia processualmente. Trata-se do planejamento de caminhos para agentes em um sistema interno de cavernas e túneis. Isso significa não se perder ou inverter entre os caminhos.
Fogo

Respostas:

3

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 .

Engenheiro
fonte
HPA * é um pouco mais eficiente.
Fogo
Investiguei mapas probabilísticos de estradas enquanto eles estavam usando em problemas de navegação por robôs.
Fogo
2
Você também pode usar um preenchimento de inundação baseado no Cellular Automaton para restringir suas cavernas e túneis até um subconjunto de espaços muito menor. Isso pode ser executado novamente na deformação da paisagem, em segundo plano, se o seu mapa for grande o suficiente para que haja um atraso nisso ou se a deformação do mapa for uma constante. (ao contrário de algo como minecraft ou anão fortaleza) Depois de ter esse caminho de subconjunto, você precisa apenas de um caminho para ele, depois ao longo e depois a partir dele. Ideal é se todos os espaços abertos tiverem linha de visão para o caminho do subconjunto.
DampeS8N
1

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.

EnoughTea
fonte
Ambos os modos de vôo e caminhada podem provar a partir da navmesh. Então eles podem gerar suas próprias representações. Não faço ideia de como alternar entre os modos.
Fogo
Nos mapas probabilísticos, um método é construir diagramas de voroni. Mas depende da sua amostragem cobrindo os espaços.
Fogo
1

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 .

David Williams
fonte
Especifiquei especificamente 1 km em cubo para descartar os algos de localização de 100 voxel.
Fogo
... representações esparsas de voxel podem funcionar nessa escala? ;)
Será
Voxels esparsos significa que apenas o casco é verificado. Mas nos preocupamos apenas com o caminho aberto.
Fogo
depende se você estiver iterando os voxels ou as lacunas. Eu estava apenas me cansando da sua impaciência em cada resposta. Este fórum não faz perguntas profundas sobre o progresso da arte, assim como você gostaria.
Será
Estou bastante satisfeito com todas as respostas. Stackexchange poderia ser muito pior.
Fogo
1

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

user9780
fonte
0

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

Vai
fonte
Recastar / Desviar voxeliza o terreno em uma malha de navegação, mas gera apenas polígonos planares. Portanto, é útil apenas para modos de solo. Você pode abusar do planejamento dinâmico para realizar o replanejamento.
Fogo
Mikko aferido hpa * e achei que fosse 4-5 vezes mais rápido do que de Detour A *, e usa 10-20 vezes menos memória (nós gráfico).
Fogo
alguém em algum lugar provavelmente fez o volume de navegação licenciado por BSD lib com a localização de caminhos G-HPA * -JPS. @ Fire você está tão bem ler sobre isso, tem um link para isso?
Vai
Na verdade, a versão generalizada do HPA * acima modifica a reformulação / desvio e é lançada sob uma licença gratuita não viral. Mas ele lida apenas com polígonos planares. Eu começaria por aí.
Fogo