Como um jogo pode lidar com todos os personagens de uma só vez?

31

Esta pergunta é apenas para obter conhecimento sobre como um jogo pode lidar com tantos personagens ao mesmo tempo. Eu sou novo no jogo, então peço perdão antecipadamente.

Exemplo

Estou criando um jogo de defesa de torre no qual existem 15 slots de torre onde são construídas torres e cada torre ejeta projéteis a uma certa velocidade; digamos que a cada segundo, 2 projéteis são criados por cada uma das torres e há inimigos marchando no campo de batalha, digamos 70 (cada um com 10 tipos de atributos como HP, mana etc.), que mudam à medida que se movem pela campo de batalha).

Sumário

Contagem de torres = 15
projéteis criados por cada torre por segundo = 2
Número total de projéteis criados por segundo = 30
unidades no campo de batalha Contagem = 70

Agora, o jogo lida com esses 30 projéteis e 70 unidades , manipulando-os em 100 threads diferentes (o que é demais para um PC) ou 1 thread que move todos eles, reduz seu valor, etc. (que será meio lento , Eu acho que)?

Eu não tenho idéia disso, então alguém pode me orientar sobre como isso vai funcionar?

Nação do desenvolvedor
fonte
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
MichaelHouse
Adicionando às outras respostas ... um exemplo de alguns jogos massivos. Skyrim teve a maior parte da atualização da lógica do jogo em um único segmento. A maneira como ele administra isso tão bem é que os NPCs distantes (NPCs que estão a quilômetros de distância) são aproximados de acordo com o cronograma. A maioria dos MMOs atualiza a lógica do jogo em um único encadeamento, MAS cada parte do mapa existe em um encadeamento de servidor ou encadeamento diferente.
usar o seguinte

Respostas:

77

Agora, como o jogo lida com esses 30 projéteis e 70 unidades, manipulando-os em 100 threads diferentes

Não, nunca faça isso. Nunca crie um novo encadeamento por recurso, isso não é dimensionado na rede, nem na atualização de entidades. (Alguém se lembra das vezes em que você tinha um thread para leitura por soquete em java?)

1 thread que move todos eles reduz seu valor etc?

Sim, para iniciantes, este é o caminho a percorrer. Os "grandes motores" dividem algum trabalho entre os segmentos, mas isso não é necessário para iniciar um jogo simples como um jogo de defesa de torre. Provavelmente, ainda há mais trabalho a fazer em todos os ticks, que você também fará neste thread. Ah, sim, e a renderização, é claro.

(o que será meio lento, eu acho)

Bem ... Qual é a sua definição de lento ? Para 100 entidades, não deve demorar mais de meio milissegundo, provavelmente até menos, dependendo da qualidade do código e do idioma com o qual você está trabalhando. E mesmo que demore dois milissegundos completos, ainda é bom o suficiente para atingir os 60 tps (ticks por segundo, sem falar de quadros neste caso).

tkausl
fonte
34
Mais ou menos meio microssegundo, a menos que você esteja fazendo algo estranho. Mas o mais importante, dividir o trabalho em vários threads vai tornar tudo pior , não melhor. Sem mencionar que o multithreading é extremamente difícil.
Luaan
13
+1 A maioria dos mecanismos de jogos modernos processa milhares ou mesmo dezenas de milhares de polígonos em tempo real, o que é muito mais intenso do que rastrear o movimento de meros 100 objetos na memória.
Phyrfox
1
"Um jogo simples como um jogo de defesa de torre." Hmm ... você já jogou Defense Grid: The Awakening , ou sua sequência?
Mason Wheeler
4
"Nunca criar uma nova thread por recursos, isso não escala na rede ..." Ahem algumas arquiteturas muito escaláveis fazer precisamente isso!
NPSF3000 16/04
2
@BarafuAlbino: Que coisa estranha de se dizer. Existem várias razões válidas para criar mais threads do que os núcleos disponíveis. É uma troca de complexidade / desempenho / etc, como qualquer outra decisão de design.
Dietrich Epp
39

A regra número um do multithreading é: Não use-a, a menos que você precise paralelizar em vários núcleos da CPU para obter desempenho ou capacidade de resposta. Um requisito "x e y deve ocorrer simultaneamente do ponto de vista do usuário" ainda não é motivo suficiente para usar o multithreading.

Por quê?

Multithreading é difícil. Você não tem controle sobre quando cada thread é executado, o que pode resultar em todos os tipos de problemas impossíveis de reproduzir ("condições de corrida"). Existem métodos para evitar isso (bloqueios de sincronização, seções críticas), mas eles vêm com seu próprio conjunto de problemas ("deadlocks").

Geralmente, jogos que lidam com um número tão baixo de objetos, como apenas algumas centenas (sim, isso não é muito no desenvolvimento de jogos), geralmente os processam de maneira serial, cada tick lógico, usando um forloop comum .

Até as CPUs de smartphones relativamente mais fracas podem executar bilhões de instruções por segundo. Isso significa que, mesmo quando a lógica de atualização de seus objetos é complexa e requer cerca de 1.000 instruções por objeto e tick, e você está buscando um generoso 100 ticks por segundo, você tem capacidade de CPU suficiente para dezenas de milhares de objetos. Sim, este é um cálculo de volta ao envelope, simplificado demais, mas dá uma idéia.

Além disso, o senso comum no desenvolvimento de jogos é que as lógicas dos jogos raramente são o gargalo de um jogo. A parte de desempenho crítico é quase sempre os gráficos. Sim, mesmo para jogos 2D.

Philipp
fonte
1
"A regra número um do multithreading é: não a use, a menos que você precise paralelizar vários núcleos da CPU para obter desempenho ou capacidade de resposta." Pode ser verdade para o desenvolvimento de jogos (mas até duvido disso). Ao trabalhar com sistemas em tempo real, o principal motivo para adicionar encadeamentos é atender aos prazos e pela simplicidade lógica.
Sam
6
Os prazos do @Sam Meeting em sistemas em tempo real são um caso em que você precisa de multithreading para capacidade de resposta. Mas mesmo aí a simplicidade lógica que você aparentemente alcança através do encadeamento é muitas vezes traiçoeira, porque cria complexidade oculta na forma de impasses, condições de corrida e falta de recursos.
Philipp
Infelizmente, muitas vezes eu vi a lógica do jogo afundar o jogo inteiro, se houver problemas na busca de caminhos.
Loren Pechtel
1
@LorenPechtel Também já vi isso. Mas geralmente era solucionável por não fazer cálculos de caminho desnecessários (como recalcular todos os caminhos em cada marca), armazenando em cache os caminhos solicitados com freqüência, usando a localização de caminhos em várias camadas e usando algoritmos de busca de caminhos mais adequados. Isso é algo em que um programador qualificado geralmente pode encontrar muito potencial de otimização.
Philipp
1
@LorenPechtel Por exemplo, em um jogo de defesa, você pode usar o fato de que normalmente existem apenas alguns pontos de destino. Assim, você pode executar o algoritmo de Dijkstra para cada destino para calcular um mapa de direção que guia todas as unidades. Mesmo em um ambiente dinâmico em que você precisa recalcular esses mapas a cada quadro, isso ainda deve ser acessível.
CodesInChaos
26

As outras respostas lidaram com o encadeamento e o poder dos computadores modernos. Para resolver a questão maior, o que você está tentando fazer aqui é evitar situações "n ao quadrado".

Por exemplo, se você tem 1000 projéteis e 1000 inimigos, a solução ingênua é apenas checá-los todos um contra o outro.

Isso significa que você acaba com p * e = 1.000 * 1.000 = 1.000.000 de cheques diferentes! Este é O (n ^ 2).

Por outro lado, se você organizar melhor seus dados, poderá evitar muito disso.

Por exemplo, se você listar em cada quadrado da grade quais inimigos estão nesse quadrado, poderá percorrer seus 1000 projéteis e verificar o quadrado na grade. Agora você só precisa verificar cada projétil contra o quadrado, este é O (n). Em vez de um milhão de verificações em cada quadro, você só precisa de mil.

Pensar em organizar seus dados e processá-los com eficiência, devido a essa organização, é a maior otimização individual que você pode fazer.

Tim B
fonte
1
Como alternativa para armazenar toda a grade na memória apenas para rastrear alguns elementos, você também pode usar árvores b, uma para cada eixo, para pesquisar rapidamente possíveis candidatos a colisões, etc. Alguns mecanismos até fazem isso por você "automaticamente "; você especifica regiões atingidas e solicita uma lista de colisões, e a biblioteca a fornece. Essa é uma das muitas razões pelas quais os desenvolvedores devem usar um mecanismo em vez de escrever do zero (quando possível, é claro).
Phyrfox
@phyrfox Certamente, existem várias maneiras diferentes de fazê-lo - dependendo do seu caso de uso, o melhor será variar substancialmente.
Tim B
17

Não crie threads por recurso / objeto, mas por seção da lógica do seu programa. Por exemplo:

  1. Thread para atualizar unidades e projéteis - thread lógico
  2. Thread para renderizar a tela - thread da GUI
  3. Thread para rede (por exemplo, multiplayer) - thread IO

A vantagem disso é que sua GUI (por exemplo, botões) não necessariamente fica paralisada se sua lógica é lenta. O usuário ainda pode pausar e salvar o jogo. Também é bom para preparar seu jogo para multiplayer, agora que você separa o gráfico da lógica.

Tomáš Zato - Restabelecer Monica
fonte
1
Para iniciantes, eu não recomendaria o uso de threads gráficos e lógicos separados, pois, a menos que você copie os dados necessários, a renderização do estado do jogo exige acesso de leitura ao estado do jogo, para que você não possa modificar o estado do jogo enquanto o desenha.
CodesInChaos
1
Não desenhar com muita frequência (por exemplo, mais de 50 vezes por segundo) é meio importante e essa pergunta era sobre desempenho. A divisão do programa é a coisa mais simples a ser feita para obter um benefício real de desempenho. É verdade que isso requer algum conhecimento sobre threads, mas adquirir esse conhecimento vale a pena.
Tomáš Zato - Reinstate Monica
Dividir um programa em vários threads é uma das coisas mais difíceis para um programador. Os bugs mais irritantes decorrem de multi-threading e é uma quantidade enorme de problemas e, na maioria das vezes, não vale a pena - Primeira regra: verifique se você tem um problema de desempenho, depois otimize. E otimize exatamente onde está o gargalo. Talvez um único thread externo para um determinado algoritmo complexo. Mas mesmo assim, você tem que pensar como a sua lógica do jogo vai avançar quando esse algoritmo leva 3 segundos para terminar ...
Falco
@Falco Você está supervisionando as vantagens de longo prazo desse modelo - tanto para o projeto quanto para a experiência do programador. Sua alegação de que é o pensamento mais difícil não pode realmente ser abordada, isso é apenas uma opinião. Para mim, o design da GUI é muito mais aterrorizante. Todas as linguagens evoluídas (C ++, Java) têm modelos de multithreading bastante claros. E se você realmente não tem certeza, pode usar o modelo de ator que não sofre de bugs de multithreading para iniciantes. Você sabe que há uma razão pela qual a maioria dos aplicativos é projetada como propus, mas fique à vontade para discutir mais sobre isso.
Tomáš Zato - Reinstate Monica
4

Até os Space Invaders gerenciavam dezenas de objetos em interação. Enquanto a decodificação de um quadro do vídeo HD H264 envolve centenas de milhões de operações aritméticas. Você tem muito poder de processamento disponível.

Dito isto, você ainda pode torná-lo lento se o desperdiçar. O problema não é tanto o número de objetos quanto o número de testes de colisão realizados; a abordagem simples de verificar cada objeto um contra o outro compara o número de cálculos necessários. Testar 1001 objetos para colisões dessa maneira exigiria um milhão de comparações. Frequentemente, isso é resolvido, por exemplo, não verificando projéteis quanto à colisão entre si.

pjc50
fonte
2
Não tenho certeza se Space Invaders é a melhor comparação a se fazer. A razão pela qual ela começa devagar e acelera à medida que você mata inimigos não é porque foi projetada dessa maneira, mas porque o hardware não suportava a renderização de tantos inimigos ao mesmo tempo. en.wikipedia.org/wiki/Space_Invaders#Hardware
Mike Kellogg
E cada objeto mantém uma lista de todos os objetos próximos o suficiente para colidir com eles no próximo segundo, atualizados uma vez por segundo ou sempre que mudam de direção?
usar o seguinte código
Depende do que você está modelando. As soluções de particionamento espacial são outra abordagem comum: particionar o mundo em regiões (por exemplo, BSP, que você pode fazer de qualquer maneira para fins de renderização, ou quadtree), então você só pode colidir com objetos na mesma região.
Pjc50
3

Vou discordar de algumas das outras respostas aqui. Threads lógicos separados não são apenas uma boa idéia, mas são extremamente benéficos para a velocidade de processamento - se sua lógica for facilmente separável .

Sua pergunta é um bom exemplo de lógica que provavelmente é separável se você puder adicionar alguma lógica adicional sobre ela. Por exemplo, você pode executar vários encadeamentos de detecção de ocorrências bloqueando os encadeamentos em regiões específicas do espaço ou modificando os objetos envolvidos.

Você provavelmente NÃO deseja um encadeamento para cada colisão possível, apenas porque isso provavelmente atrapalha o agendador; também há um custo associado à criação e destruição de threads. É melhor criar um certo número de threads em torno dos núcleos do sistema (ou utilizar uma métrica como a antiga #cores * 2 + 4), depois reutilizá-los quando o processo terminar.

Nem toda lógica é facilmente separável, no entanto. Às vezes, suas operações podem alcançar todos os dados do jogo de uma só vez, o que tornaria o encadeamento inútil (de fato, prejudicial, porque você precisaria adicionar verificações para evitar problemas de encadeamento). Além disso, se vários estágios da lógica são altamente dependentes um do outro que ocorrem em ordens específicas, você terá que controlar a execução dos encadeamentos de forma a garantir que não dê resultados dependentes da ordem. No entanto, esse problema não é eliminado pelo não uso de threads, apenas os exacerbam.

A maioria dos jogos não faz isso simplesmente porque é mais complexo do que o desenvolvedor médio de jogos está disposto / capaz de lidar com o que geralmente não é o gargalo em primeiro lugar. A grande maioria dos jogos é limitada por GPU, não por CPU. Embora melhorar a velocidade da CPU possa ajudar em geral, geralmente não é o foco.

Dito isto, os mecanismos de física geralmente empregam vários threads, e eu posso citar vários jogos que eu acho que teriam se beneficiado de vários threads lógicos (os jogos Paradox RTS como HOI3 e outros, por exemplo).

Concordo com outras postagens de que você provavelmente não precisaria empregar tópicos neste exemplo específico, mesmo que isso fosse benéfico. O encadeamento deve ser reservado para casos em que você possui carga excessiva de CPU que não pode ser otimizada por outros métodos. É um empreendimento enorme e afetará a estrutura fundamental de um motor; não é algo que você possa aderir após o fato.


fonte
2

Penso que as outras respostas perdem uma parte importante da questão, concentrando-se demais na parte de segmentação da pergunta.

Um computador não lida com todos os objetos em um jogo de uma só vez. Ele lida com eles em sequência.

Um jogo de computador progride em intervalos de tempo discretos. Dependendo do jogo e da velocidade do PC, essas etapas geralmente são de 30 a 60 etapas por segundo, ou a quantidade de etapas que o PC pode calcular.

Em uma dessas etapas, um computador calcula o que cada um dos objetos do jogo fará durante essa etapa e os atualiza de acordo, um após o outro. Pode até fazê-lo em paralelo, usando threads para ser mais rápido, mas como veremos em breve a velocidade não é uma preocupação.

Uma CPU média deve ser 2 GHz ou mais rápida, o que significa 10 9 ciclos de relógio por segundo. Se calcularmos 60 Timesteps por segundo, que as folhas 10 9 ciclos / 60 ciclos de clock = 16666666 relógio pelo tempo da etapa. Com 70 unidades, ainda temos cerca de 2.400.000 ciclos de relógio por unidade restante. Se tivéssemos que otimizar, poderíamos atualizar cada unidade em menos de 240 ciclos, dependendo da complexidade da lógica do jogo. Como você pode ver, nosso computador é cerca de 10.000 vezes mais rápido do que o necessário para esta tarefa.

Pedro
fonte
0

Disclaimer: Meu tipo de jogo favorito de todos os tempos é baseado em texto e eu o escrevo como programador de longa data de um antigo MUD.

Eu acho que uma pergunta importante que você precisa se perguntar é: Você precisa de threads? Entendo que um jogo gráfico provavelmente tenha mais uso de MTs, mas acho que também depende da mecânica do jogo. (Também pode valer a pena considerar que, com GPUs, CPUs e todos os outros recursos que temos hoje, são muito mais poderosos, o que torna suas preocupações com os recursos tão problemáticas quanto lhe parecem; de fato, 100 objetos são praticamente zero). Também depende de como você define 'todos os caracteres de uma vez'. Você quer dizer exatamente ao mesmo tempo? Você não terá isso, como Peter justamente aponta, de modo que tudo de uma vez é irrelevante no sentido literal; só aparece assim.

Supondo que você siga os tópicos: você definitivamente não deve considerar 100 tópicos (e eu nem vou falar se é demais para sua CPU ou não; refiro-me apenas às complicações e à praticidade).

Mas lembre-se disso: o encadeamento múltiplo não é fácil (como salienta Philipp) e tem muitos problemas. Outros têm muito mais experiência (muito) do que eu com o MT, mas eu diria que eles também sugerem a mesma coisa (mesmo que sejam mais capazes do que eu seria - especialmente sem prática da minha parte).

Alguns argumentam que discordam que os threads não são benéficos e outros argumentam que cada objeto deve ter um thread. Mas (e novamente isso é todo o texto, mas mesmo que você considere mais de um tópico, você não precisa - e não deve - considerá-lo para cada objeto), como Philipp aponta que os jogos tendem a percorrer as listas. Mas, no entanto, não é apenas (como ele sugere, embora eu saiba que ele está apenas respondendo aos seus parâmetros de tão poucos objetos) para tão poucos objetos. No MUD, sou programador, pois temos o seguinte (e essa não é toda a atividade que acontece em tempo real, portanto, lembre-se disso também):

(O número de instâncias varia, é claro - mais alto e mais baixo)

Móveis (NPC ou seja, não personagem do jogador): 2614; protótipos: 1360 Objetos: 4457; protótipos: 2281 Quartos: 7983; protótipos: 7983. Cada quarto geralmente tem sua própria instância, mas também temos quartos dinâmicos, ou seja, quartos dentro de um quarto; ou quartos dentro de um móvel, por exemplo, o estômago de um dragão; ou salas em objetos, por exemplo, você insere um objeto mágico). Lembre-se de que essas salas dinâmicas existem por objeto / sala / móvel que realmente as definiu. Sim, isso é muito parecido com a ideia de World of Warcraft (eu não a jogo, mas um amigo me fez jogar quando eu tinha uma máquina Windows, por um tempo) de instâncias, exceto a que tivemos muito antes de World of Warcraft sequer existir.

Scripts: 868 (atualmente) (por incrível que pareça, nosso comando de estatísticas não mostra quantos protótipos temos, por isso acrescentarei). Tudo isso é realizado em áreas / zonas e temos 103 delas. Também temos procedimentos especiais que são processados ​​em momentos diferentes. Também temos outros eventos. Então também temos conectores conectados. Os celulares se movimentam, realizam atividades diferentes (além do combate), interagem com os jogadores e assim por diante. (O mesmo acontece com outros tipos de entidades).

Como lidamos com tudo isso sem demora?

  • soquetes: select (), filas (entrada, saída, eventos, outras coisas), buffers (entrada, saída, outras coisas), etc. Eles são pesquisados ​​10 vezes por segundo.

  • personagens, objetos, salas, combate, tudo: tudo em um loop central em diferentes pulsos.

Nós também (minha implementação baseada na discussão entre o fundador / outro programador e eu) temos extensos testes de rastreamento de lista vinculada e de validade de ponteiro e temos recursos livres mais do que suficientes se realmente precisarmos dele. Tudo isso (exceto que expandimos o mundo) existia anos atrás, quando havia menos RAM, energia da CPU, espaço no disco rígido, etc. E, de fato, mesmo assim, não tivemos problemas. Nos loops descritos (os scripts causam isso, assim como a área redefine / repovoa como outras coisas) monstros, objetos (itens) e outras coisas estão sendo criados, liberados e assim por diante. As conexões também são aceitas, pesquisadas e tudo o mais que você esperaria.


fonte