Localização de caminhos e prevenção de colisões no celular

8

Atualmente, estou desenvolvendo um jogo do tipo Diablo para plataforma móvel (iphone5 +).

Uma simples pesquisa A * encontrará o caminho, mas a prevenção de colisões ainda precisa ser levada em consideração.

Haverá cerca de 50 monstros ativos ao mesmo tempo, então o desempenho é muito importante.

Encontrei alguns métodos que podem funcionar.

  1. NavMesh + RVO

    A biblioteca de reformulação / desvio funciona bem por pathfindingparte, mas sua simulação de multidão rapidamente atinge o limite (mais de 5 ms para 30 agentes).

    Outra biblioteca RVO2 parece bem (menos de 2ms para 50 agentes), mas a biblioteca tem alguns problemas de licença.

  2. Campos de fluxo + mecanismo de física

    Muitos jogos RTS usam esse método, mas parece que é necessário um mecanismo de física para resolver colisões. Se muitos agentes não compartilham um objetivo comum, esse método pode custar mais do que a busca de caminhos A * tradicional.

  3. Comportamentos de direção + Mecanismo de física

    Comportamentos de direção incluem muitos conceitos, acho que simple avoidance behaviorpodem funcionar (apenas vire à esquerda / direita se houver algo na frente), mas o método ainda requer um mecanismo de física para trabalhar em conjunto.

Ainda não tenho certeza de qual usar, talvez exista outros métodos de busca de caminhos e prevenção de colisões.

O PS Halo:Spartan Strikeusa o Havok AI (baseado no RVO?), Mas eu não vi muitos inimigos naquele jogo, então me pergunto se o primeiro método (NavMesh + RVO) funcionará bem na plataforma móvel.

lostyzd
fonte
Sua GPU possui mais de 50 unidades de processamento; portanto, rodar uma estrela A na GPU para cada monstro deve funcionar tão rápido quanto em uma CPU comum para um agente.
Pieter Geerkens
@PieterGeerkens A parte pathfinding agora funciona bem em dispositivos móveis (menos de 0,1 ms por solicitação), mas a parte para evitar colisões não. Também temos muitas tarefas de renderização, então acho que a GPU não terá tempo livre para evitar colisões.
Lostyzd 16/07/2015

Respostas:

4

Essa é uma pergunta bem interessante, e vou tentar contribuir com o que puder.

Primeiro, acho que você precisa definir claramente os limites do jogo que está tentando criar e definir essas perguntas (algumas já podem ter sido respondidas).

  • A que distância está o monstro aggro?
  • Quantos monstros ao mesmo tempo é o seu alvo?
  • Como é organizado o seu terreno? É lado a lado?
  • Quanta prevenção de colisão você deseja?

Para citar uma resposta daqui em diante como o pathfinding é feito no starcraft 2:

Starcraft II usa uma triangulação restrita de Delaunay do terreno e dos edifícios do mapa para produzir uma malha naval; Um * com um filtro de funil é usado para percorrer essa malha, levando em consideração os raios da unidade; em seguida, são adicionadas camadas locais de direção e prevenção de colisões, incluindo um recurso cooperativo de "empurrar as unidades ociosas para fora do caminho", onde é possível deslocar uma unidade em vez de percorrê-la em certos casos. Além disso, as unidades que se deslocam em paralelo são ignoradas para fins de prevenção de colisões, pois é garantido que elas não afetam uma à outra; [...] o SC2 usa seis forças de direção: seguir, reunir, agrupar, separar, evitar e chegar.

Então, voltando às suas 3 proposições:

  1. NavMesh + RVO -> Se houver problemas de licença, não será uma opção. Pode ser a implementação mais fácil.
  2. Campos de fluxo + Mecanismo de física -> Depende honestamente, mas parece realmente computar intensivamente em um ambiente semi-dinâmico como você deseja
  3. Comportamentos de direção + Mecanismo de física -> O comportamento de direção me parece o caminho a percorrer. Dessa forma, você pode definir alguns comportamentos bastante agradáveis ​​para o seu jogo, dependendo, por exemplo, do tipo de monstro. E se adapta bem ao número da máfia. No entanto, eu ficaria longe da física para detectar colisões. É simples o comportamento de evitar, reduzindo a velocidade ou aumentando, girando, etc.

Algumas notas sobre os comportamentos de direção, você pode definir as forças de direção necessárias, com as áreas que deseja. Você precisa de pelo menos três para reunir-se / atrair / repulsar, mas provavelmente há mais interessantes.

Em seguida, tente encontrar uma biblioteca que faça o direcionamento dos comportamentos para ver se ela se adapta às suas necessidades (como essa ? Eu realmente não conheço nenhuma, mas ela existe).

Se a biblioteca não atender às suas necessidades, você poderá se divertir! Mas existem recursos e algoritmos suficientes para implementar você mesmo os comportamentos de flocagem. Exemplo 1 Exemplo 2

Se você optar por se implementar, saiba que há uma ótima otimização a ser feita, pois o escopo do seu agente é reduzido, por exemplo, pela sua localização no rebanho. De qualquer forma, deve ser incluído em alguns dos algoritmos.

Bem, isso é o melhor de meu conhecimento, não tenho certeza de qualquer maneira

Bluk
fonte
Obrigado por responder. O comportamento da direção funciona bem em uma cena densa? As demos neste tutorial têm muitas colisões e oscilações.
21715 lostyzd
1

Se os caminhos inimigos não forem muito dinâmicos (Dinâmico seria: todos os agentes estão atacando alvos diferentes e os caminhos para esses alvos devem ser atualizados a cada par de quadros)

Então eu faria uma combinação de campos de fluxo e comportamentos de direção se o desempenho for sua principal preocupação. Existem alguns assuntos mais complicados envolvidos, como particionar o espaço de seus agentes, para encontrar vizinhos é mais fácil, mas é sua melhor aposta para o desempenho. (removendo sua pesquisa A * e usando campos de fluxo para direcionar seus agentes)

Esses dois algoritmos combinados são geralmente considerados a solução mais otimizada para cenas densas de agentes com pouco caminho dinâmico.

Eu evitaria a física, não importa sua opção final, pois ela pode ficar pesada.

A colisão entre agentes pode quase inteiramente ser tratada pelos comportamentos de direção e os campos de fluxo reduzem o peso de 50 agentes calculando caminhos. No entanto, lembre-se de que os campos de fluxo ficam cada vez mais caros quanto maior o tamanho do mapa, menor o tamanho da grade e mais dinâmica a seleção de alvos.

Saevax
fonte
Eu gosto da ideia de campos de fluxo. Mas, tanto quanto eu sei, tanto a Aniquilação Planetária quanto a Starcraft usam a física para evitar colisões, então não tenho certeza se o campo de fluxo pode ser realizado sem o sistema de física.
21815 lostyzd
Eles podem, tudo que você precisa fazer é criar um comportamento de direção de campo de fluxo. Sua única função é verificar a localização atual da grade para seu vetor de fluxo. Tudo o que um campo de fluxo faz é direcionar seus agentes, os outros comportamentos de direção cuidam da colisão.
Saevax