Exploração espacial Deep – um jogo de mineração de asteróides

Recentemente, tenho trabalhado no Pathfinging para os NPCs no meu jogo, o que é algo que estou ansioso por um tempo agora, já que é um bom problema robusto para resolver. Pensei em escrever este publish sobre como fiz tudo.

Eu tinha alguns requisitos extras do meu caminho, devido à maneira como meu jogo joga:
– Deve lidar com um ambiente físico dinâmico (os objetos podem se mover livremente e são destrutíveis)
– tem caminhos que preferem manter a distância dos objetos, mas ainda se aproximam quando necessário
– Permitir envolver as fronteiras da área de jogo (estilo de asteróides)

Abordagem geral

Meu primeiro pensamento period que eu queria caminhos detalhados para que eles pudessem passar por arranjos confusos de objetos com bastante facilidade. Isso significaria um tempo de pesquisa mais longo, então a escolha simples do algoritmo de pesquisa é A*. E como preciso consultar o mundo para cada nó para ver se está bloqueado, pensei em usar o espaço particionando com as consultas para reduzir o número necessário para cada caminho.

Acabei mantendo esse plano e descobrindo as coisas mais detalhadas ao longo do caminho.

Consultas particionadas espaciais

Eu construí uma árvore de partição espacial, onde cada nó cobre uma área específica do jogo e, em seguida, cada uma das crianças desse nó cobre uma área específica da área de seus pais (com a raiz da árvore cobrindo toda a área do jogo). Faço isso a uma profundidade de 6 e, em seguida, os nós da folha compõem efetivamente a grade de navegação para a descoberta de caminhos.

Agora, quando verifico se um nó está bloqueado, ele primeiro verificará seus pais. Se seu pai não estiver bloqueado, nenhum de seus filhos será bloqueado. Se o pai estiver bloqueado, o nó filho precisará executar sua própria consulta para ver se sua própria área está bloqueada. Isso nos permite saber se grandes áreas do jogo não estão bloqueadas em muito poucas consultas, o que é útil porque essas consultas são caras.

A* pesquisa

A pesquisa actual é uma pesquisa bastante padrão. Cada nó tem 8 vizinhos, com nós na borda tendo vizinhos embrulhados, que são armazenados em cache junto com seu custo de travessia para uma pesquisa mais rápida.

Meio ambiente mudando em tempo actual

Como os objetos podem se movimentar no mundo dos jogos e até mesmo destruir deles, esse algoritmo precisava ser capaz de atualizar em tempo actual. O asteróide que não estava bloqueando o caminho há um segundo pode ter se movido, e o asteróide que estava bloqueando o caminho poderia ter sido explodido!

Minha solução simples para isso foi permitir que o algoritmo cache se cada nó que verificou foi bloqueado, mas invalidar esse cache de vez em quando (atualmente a cada 500ms está funcionando bem). Isso permite que o tempo construa uma imagem do mundo e permita que uma solicitação de busca de caminho use informações de uma solicitação anterior, mas também força o algoritmo a se manter atualizado no estado atual do mundo.

Idealmente, não invalidaríamos todo o cache, pois haverá seções do mundo dos jogos onde nada se moveu, mas realisticamente essa é uma abordagem simples que funciona bem o suficiente. Dizendo isso, tenho um plano de como fazer isso, caso seja necessário.

Aqui você pode ver a espalhamento e sendo atualizada em tempo actual. Cada quadrado azul representa um nó desbloqueado e a cor do pixel no nó representa a proximidade do objeto mais próximo.

Caminhos naturais

O caminho mais curto geralmente não parece pure ou seguro para esse assunto, então eu queria que o algoritmo prefira caminhos que estão mais longe dos objetos, mas ainda conseguem se aproximar quando necessário (passando por uma pequena lacuna, por exemplo).

Portanto, para cada solicitação de busca de caminho, é fornecida uma distância preferida dos objetos, que é usada para fornecer a cada nó uma classificação de proximidade. Essa classificação de proximidade é usada ao determinar o custo de travessia para um nó; portanto, os nós mais próximos dos objetos são simplesmente mais caros ao executar a pesquisa.

Atualmente, a classificação de proximidade tem um efeito exponencial; portanto, o caminho realmente tenta evitar ser tremendous próximo às coisas, mas não se importa de ser um pouco próximo, se necessário.

Aqui você pode ver o caminho mantendo a distância dos objetos até que seja forçado a se aproximar e entre eles. Você também pode ver melhor a partição do espaço aqui, com os quadrados azuis maiores representando áreas que exigiam apenas uma única consulta.

Caminhos embrulhados

Como a área do jogo permite embrulho de asteróides, eu queria que o Pathfinging também seja responsável por isso. Os NPCs não têm o mesmo tipo de mobilidade que o jogador é um pouco chocante, além de tornar o problema um pouco mais divertido de resolver.

Os caminhos embrulhados significam que todo nó de navegação realmente tem o mesmo número de vizinhos, o que é uma propriedade interessante e talvez incomum (a busca de caminho em um globo 3D provavelmente tem a mesma propriedade).

Produzir o caminho embrulhado não period na verdade a parte mais difícil, period simples o suficiente para dar aos nós da fronteira que os vizinhos do outro lado da grade. A parte mais difícil period fazer com que o NPC realmente siga o caminho, pois, sem qualquer manuseio especial, ele apenas atingia o nó em uma borda e depois se viraria e se movia diretamente em direção ao nó na outra borda, sem embrulhar.

Para corrigir isso, o tempo de embalagem ocorrer em um caminho, um nó adicional é adicionado fora da tela, que o NPC tenta seguir e depois acaba envolvendo. Havia também o problema de qual posição NPC você usa para seguir o caminho quando eles começam a embrulhar (um objeto tem várias posições quando está envolvido), mas a solução simples para isso period usar a posição NPC mais próxima da próxima etapa no caminho.

As fronteiras têm seu próprio custo de proximidade para manter os caminhos um pouco longe delas e também fazer de embrulhar um tipo de último recurso.

Aqui você pode ver o caminho se espalhando e descobrindo que o caminho mais curto em uma margem é envolver o pedido, em vez de percorrer os asteróides. Você também pode ver o tempo decorrido no canto, este é o tempo gasto no processamento do caminho a cada atualização, não o tempo whole de atualização.

Eficiência

Esse algoritmo está fazendo muito trabalho e pode acabar tomando vários milissegundos para os caminhos mais complicados (na minha máquina de qualquer maneira). Estou tentando muito manter o jogo o mais executado possível, por isso importa muito para mim que isso não diminua nada.

Minha abordagem foi a primeira referência e otimizar as coisas o máximo que pude, e depois dividir o processamento de uma única solicitação de caminho em vários ticks de jogos. Para dividir vários ticks, verifique o número de nós visitados e consultas mundiais após cada iteração da pesquisa A*, se uma delas estiver acima do limiar que eu defini, o loop sai e pega de onde parou no próximo tick.

Isso significa que há alguma assincronicidade quando uma entidade solicita um caminho e quando obtém o resultado. Como a espera está apenas nos milissegundos de um dígito, isso não é realmente perceptível para o jogador, especialmente porque apenas os NPCs estão fazendo pedidos de caminho e não para o jogador.

Esse tipo de problema de eficiência é algo que parece maduro para a multi-threading, mas o principal problema que tive aqui é que todo o estado mundial do jogo é realizado no tópico principal e em estruturas complicadas, portanto, copiar isso para um fio de caminho seria difícil e potencialmente lento. Eu poderia ter permitido que o thread de caminho para fazer solicitações de consulta ao encadeamento principal, mas temos mais lógica de sincronização para lidar. Portanto, para menos dores de cabeça, fiquei no fio principal e dividi o processamento entre os carrapatos.

Conclusão

A única parte desta solução que procurei outros exemplos foi a principal pesquisa, tudo o mais que trabalhei com o melhor da minha habilidade. Eu poderia dizer que a solução que eu queria tinha requisitos específicos que muitos exemplos on -line não atenderam, mas, com honestidade, eu nem parecia porque queria tentar isso sozinho. O que eu amo no Recreation Dev é pensar em problemas interessantes e fornecer (espero) uma boa solução. Talvez eu pudesse ter tido uma solução de trabalho mais rapidamente ao encontrar on -line de outra pessoa, mas eu não teria gostado tanto do processo.

Nos meus testes da minha solução, tem sido performante e produz caminhos que fazem sentido, e talvez mais importante pareçam bons para o jogador. Há aspectos que eu gostaria de analisar mais, como apenas invalidar as partes do cache de consulta onde o mundo mudou, mas, infelizmente, temos que passar para outros recursos eventualmente. Em seguida, eu realmente uso esse caminho ao criar comportamentos para alguns NPCs, então vamos ver como tudo acaba.