Gerenciar um grande número de atores independentes em tempo real

8

Estou trabalhando em um jogo de estratégia em tempo real em larga escala - idealmente com milhares de unidades ativas ao mesmo tempo - mas estou tendo problemas para gerenciar todas as unidades de uma só vez, sem que isso se torne espantosamente lento. O problema é que leva um tempo para atualizar as posições e estados de tudo a cada passo. Você conhece algum padrão / metodologia / dicas de design para mitigar isso?

Slubb
fonte
11
embora sua pergunta possa parecer muito diferente, você pode usar o mesmo algoritmo explicado aqui . não é necessário usar o processamento parralel nesse algoritmo; com apenas um, você obterá um aumento de alto desempenho.
Ali1S232
Paralelamente à atualização não ajudará se, por exemplo, você tiver dois núcleos e a atualização da metade deles já demorar muito, mas se você tiver vários núcleos disponíveis e ainda não os estiver usando, isso deverá ajudar. Idealmente, você desejará uma solução que não exija a atualização de todas as unidades a cada etapa do tempo, ou uma maneira de simplificar a atualização para que você possa. Qual é o tamanho dessa etapa do tempo? É independente dos quadros de desenho, certo?
Blecki 31/07/11
4
A primeira coisa que você pode fazer é reconhecer que sua velocidade não tem nada a ver com a quantidade de atores independentes. Tem a ver com o que esses atores estão fazendo . Eu posso ter cem mil atores independentes atualizando> 60fps se tudo o que eles estão fazendo é if not dead position += 1ou um ator atualizando <1fps se estiver entrando em um loop infinito. Alguns de seus algoritmos - algumas partes do que essas unidades estão fazendo - são muito caros do jeito que você os faz e isso é tudo. Provavelmente, existem várias causas possíveis e várias estratégias possíveis para cada uma.
Doppelgreener

Respostas:

4

Há duas coisas distintas a serem consideradas ao medir e otimizar o desempenho de um sistema de entidades em grande escala.

No nível baixo, você tem a representação física de suas entidades, que tende a se resumir ao uso de layouts de armazenamento eficientes como SoA (estruturas de matrizes) para reduzir o custo de iterar e atualizar todas as entidades ativas.

No nível superior, você tem lógica de tomada de decisão, lógica geral de jogo, IA e busca de caminhos. Essas são todas as tarefas que têm em comum que elas não precisam ser executadas na mesma taxa de atualização que a sua renderização.

Como você obteria um tempo de quadro desigual se adotar a abordagem ingênua de executar essas tarefas a cada N quadros, tende a ser benéfico amortizar o custo em vários quadros.

Se a tarefa for de natureza incremental, você poderá executar parte do algoritmo a cada quadro e usar resultados parciais em suas atualizações.

Se a tarefa for amplamente monolítica, mas separável por entidade, você poderá executá-la para um subconjunto de suas entidades de jogo por quadro, alternando entre elas de maneira alternada. Isso tem o benefício de reduzir a complexidade de coisas como busca de caminhos e IA, pois você não tem todo mundo tentando agir ao mesmo tempo.

No RTS tático em grande escala em que trabalhei, nos concentramos em ter estruturas de dados robustas para consultar a representação de baixo nível nos algoritmos de alto nível, para encontrar os vizinhos das entidades do jogo. O processo de atualização de baixo nível agiu de acordo com as intenções fornecidas pela simulação de alto nível de atualização lenta e, no final, resumiu-se a uma simulação de partículas barata, chegando a milhares.

Lars Viklund
fonte
+1. Penso exatamente, principalmente reduzindo a lógica a grupos gerenciados que são processados ​​apenas a cada poucos ciclos, com todos esses grupos potencialmente escalonados para processamento uniforme.
Engenheiro
1

pelo que me lembro, você sempre terá menos de 10.000 unidades por jogo. não há nenhum jogo que me lembre com mais que esse número, embora o império da terra possa chegar a 14.000 através de um hack, mas ninguém jamais chegará a esse ponto. portanto, apenas ter uma matriz estática de 10.000 objetos parece ser mais do que o necessário.

como você sabe, iterar mais de 10000 objetos não é grande coisa, mas pode consumir muito tempo se o seu algoritmo for mais lento que O (n). por exemplo, se você tentar verificar a cada dois objetos para detecção de colisão, levará O (n ^ 2) tempo, o que significa muito tempo. então você tem que quebrar seus algoritmos de alguma forma. vamos revisar um algoritmo de amostra para tudo o que posso pensar agora:

  1. detecção de colisão: para cada algoritmo de detecção de colisão, é necessário verificar a cada dois objetos, mas você pode eliminar algumas verificações iniciando os loops. como sugeri nos comentários, você pode usar o mesmo algoritmo fornecido para esta pergunta . não há necessidade de usar vários threads ou qualquer coisa, mesmo com um thread e 4 regiões, você reduzirá suas verificações de n * (n-1) para 4 * (n / 4) ((n-1) / 4), e otimizando o número de regiões, você pode obter resultados ainda melhores. Eu acho que usando as melhores regiões numéricas você pode até chegar a O (n log (n)).

  2. você precisa gerar um caminho para cada objeto em movimento. o sistema usual que eu vi até agora é uma coisa muito simples: sempre que o jogador comanda as unidades para se moverem para algum lugar, o computador calcula seu caminho; depois disso, a cada ciclo, se o objeto pode se mover, ele se move, se não puder, pula esse ciclo. não há nada de especial. embora você também possa alterar os algoritmos fornecidos aqui para reduzir as chamadas de localização de caminhos e ter a busca de caminhos em tempo real para cada grupo de unidades, mas isso realmente não é necessário.

  3. você precisa verificar se alguma bala ou bomba ou coisa semelhante atinge uma das unidades: você pode usar as mesmas regiões que criou para detecção de colisão aqui.

  4. para selecionar unidades, você também pode usar as mesmas regiões.

em geral, eu sugeriria usar uma matriz estática (ou uma matriz dinâmica com tamanho reservado) de 10.000 ou 20.000, no máximo. depois use algo em torno de 10 ou 15 loops, cada um repetindo todas as unidades. essa é uma grande variedade real, contendo todas as unidades de todos os jogadores. para que cada índice tenha ambos os dados sobre o proprietário e o tipo da unidade. você também cria outras matrizes para cada jogador. em cada índice dessa matriz secundária, você precisará armazenar ponteiros para objetos na matriz principal.

se você tiver outras perguntas, coloque comentários para adicioná-los à minha resposta.

Ali1S232
fonte
Lembro-me de ter mais de 40.000 em Empires Dawn of the Modern World :). Pena que o renderizador pudesse manter apenas cerca de 1000 na tela antes de começarem a desaparecer, mas o resto do jogo funcionou bem :).
Deceleratedcaviar
@daniel: isso não é grande coisa, os generais não têm nenhuma limitação na contagem de unidades. Eu estava apenas dando uma medida do bom número de unidades para basear meus cálculos matemáticos. 40000 e 10000 não são muito diferentes um do outro.
Ali1S232