Como lidar com um grande número de captadores em um jogo MMO

26

Como jogos como Minecraft, ou realmente qualquer jogo MMO que tenha captadores, lida com eles?

Digamos que o terreno gera 3 gotas de "sujeira" toda vez que você cavar o referido terreno. Digamos que cada item tenha uma animação de rotação calculada em todos os quadros. Se o número de captadores no mundo for muito alto, isso seria uma sobrecarga maciça inútil no cálculo de quadros para um cliente em um determinado servidor, pois é provável que muitos desses itens de captadores estejam a anos-luz de distância de você.

Então, o que eu pensei é que você precisa "fazer coisas" apenas com os captadores próximos ao player local, mas isso ainda implica que todos os quadros que eu tenho que verificar se algum outro item de captador está perto o suficiente para começar a animar.

Minha pergunta real é: como outros MMOs resolveram esse problema?

Alakanu
fonte
9
Além disso, no contexto do Minecraft, depois que um certo número de itens estiver próximo o suficiente (3 ou mais do mesmo item no mesmo espaço de bloco), o servidor substituirá as 3 instâncias por uma instância agrupada que contenha o tipo de bloco ( minecraft:dirt) e uma contagem (30), de modo que, quando o jogador estiver perto o suficiente para buscá-la, basta adicionar o máximo possível da contagem ao inventário do jogador. Se o jogador só tem espaço para 6 itens e uma pilha de 30 está no chão, o jogador vai pegar a 6, ea pilha na contagem do solo é reduzida a 24.
Zymus
6
@Zymus Vale a pena notar que, na verdade, diminuiu o desempenho do tick para números moderados de itens descartados, porque eles estão constantemente procurando itens próximos.
precisa saber é o seguinte

Respostas:

48

Simplesmente carregando apenas as partes do mundo na memória próximas ao player. Qualquer outra coisa está suspensa no disco rígido. Quando há um objeto minúsculo a cerca de dois quilômetros de distância, o jogador não pode vê-lo e não pode interagir com ele. Portanto, não há motivo para atualizá-lo ou enviá-lo à GPU para renderização. Quanto menor o objeto e seu alcance de interação, menor o alcance ao redor do player em que você precisa carregá-lo.

Quanto a descobrir o que há de mais próximo do player: isso se resume principalmente em armazenar o mundo em uma estrutura de dados otimizada para pesquisa espacial. Bons candidatos a esses são hash espacial e árvores multidimensionais .

Philipp
fonte
Obrigado pela resposta rápida. Eu estava pensando em usar o Unity, pois acho que ele usa algum tipo de particionamento espacial para verificar os coletores de gatilhos, então eu criaria um colisor de círculo grande em torno do meu personagem e cada item dentro dele seria "animado". Essa é uma maneira de implementar sua resposta? Corrija-me se eu estiver errado, felicidades!
Alakanu
2
@Alakanu Ele pode ser usado se você deseja que os objetos sejam visíveis a longas distâncias, mas apenas realizam certos comportamentos intensos de computação quando estão próximos ao player (e apenas girar algo em torno do eixo y não deve ser muito caro). Mas o desafio real ao implementar um jogo de mundo aberto no Unity é instanciar e destruir objetos de jogo de maneira inteligente enquanto o jogador se move pelo mundo (ou melhor ainda: use o pool de objetos em vez de instanciar e destruir).
Philipp
Sim, o pool de objetos é obrigatório nessa situação :) Ok, muito obrigado!
Alakanu
3
@Alakanu Você pode conferir o conceito "Loaded Chunks" do Minecraft para obter mais informações sobre como essa resposta se aplica a esse jogo.
T. Sar - Restabelece Monica
11
Isso não é verdade apenas para captadores. Qualquer objeto que esteja muito longe do player pode ser tratado dessa maneira. Às vezes, até objetos próximos ao player. Imagine uma casa com um interior completo, mas não há necessidade de renderizar até você realmente entrar na casa.
Zibelas
22

Você tem duas coisas muito diferentes para gerenciar:

  1. O servidor deve gerenciar o mundo inteiro, de maneira autorizada. Para isso, é necessária a comunicação com N clientes (onde N é "maciço").

  2. O cliente poderia , em princípio, conhecer o mundo inteiro, mas não precisa . Para o cliente, basta saber o que está próximo do jogador. Supondo, por exemplo, um particionamento bastante grosseiro do tipo grade, seria necessário conhecer apenas a célula do jogador e as 26 células ao redor do jogador (ou 8 células, caso você tenha uma grade 2D). Uma grade um pouco mais fina é melhor, mas você entendeu.

Agora, muitos captadores, o que é "muito"? Você pode cavar talvez 5 coisas por segundo, ou seja, duas dúzias de números que precisam ser atualizados no servidor, e o servidor pode ter que transmiti-los para outro jogador cuja área de interesse se sobreponha ao seu celular. Para um computador, essa é uma quantidade bastante ridícula de dados e uma quantidade negligenciável de computação. Pode se tornar um desafio quando houver centenas / milhares de jogadores na mesma célula (então a sua participação é muito grossa).

O servidor não precisa saber nem se importar com a rotação dos captadores ou com esses detalhes. Por quê?

Na verdade, o cliente também não se importa, já que isso é apenas um colírio para os olhos que o cliente pode inventar rapidamente.

O que é necessário do ponto de vista do servidor é saber que você estava cavando (30, 40, 50) no nó em que está, e decide que isso gera, por exemplo, três objetos do tipo 5 ou um objeto do tipo 7 com uma contagem de 3. Isso é tudo o que importa, e é tudo o que diz a você. Também incluirá essas informações nos dados enviados a alguém que move sua área de interesse pela célula da grade posteriormente (supondo que ainda esteja lá).

O cliente é informado de três objetos gerados lá, blá, blá. Agora, se o cliente exibe um mapa de arte ASCII onde agora existe um 'D' ou se mostra uma pilha rotativa de sujeira, é tudo a mesma coisa. Se as pilhas têm rotações diferentes ou se apenas as próximas ao seu jogador giram, também são iguais. São apenas coisas exibidas no monitor, não afetam mais ninguém.

Portanto, no caso concreto em que você deseja girar apenas pilhas de terra próximas, basta verificar o alcance de todos os objetos que conhece. Como o conjunto de dados não é grande, até a força bruta de tudo funcionará.

Você pode (e deve), dependendo do tamanho do seu particionamento, podar trivialmente as células da grade que estão muito distantes.

Você pode, é claro, subdividir mais o seu celular e usar algo super inteligente. Use uma kd-Tree, se quiser, mas não espere ganhos enormes. Você pode remover coisas com Manhattan distace, ou pode classificá-las em uma pequena grade de sua preferência ... mas por quê?

Uma verificação de distância (distância realmente ao quadrado, mas é a mesma para você) são meras duas multiplicações e uma adição (otimizada para MUL, MADD, na verdade, apenas duas operações), seguida por uma ramificação ou movimento condicional. Isso é tão rápido quanto qualquer outra operação que não remove células inteiras da grade por vez. Na verdade, isso é algo que você pode fazer na GPU ...

Vendo como você terá algumas centenas ou, no máximo, alguns milhares de verificações de distância na mesma posição (a distância ao quadrado funciona bem), você realmente não terá muita dificuldade em fazer esse cálculo, ainda mais porque é um cache - iteração amigável sobre a memória contígua e, com movimentos condicionais, é muito barato. Algo como (pseudocódigo) rot = r[i] + 1; r[i] = ((dx*dx+dy*dy) < DIST_SQ) ? rot : r[i];. Essa é uma iteração em uma matriz de algumas centenas de valores por quadro. O computador não se importava com isso, são cargas e armazenamentos contíguos, ALU simples, sem ramificações e apenas alguns milhares de iterações.

Isso (muitos para um) não é a mesma classe de problema (muitos para muitos) que no servidor. Realmente, o cliente não é o problema.

Damon
fonte
Sinto muito, pensei que estava claro que estava falando de um cliente quando comecei a falar em framerate.
Alakanu
11
Mas o cliente nunca é o problema. O cliente é muito pouco massivo e muito local, precisa saber muito menos que o servidor. Idealmente, o cliente conhece o nó de particionamento espacial (seja o que for, digamos, a grade) em que o jogador está e os que estão imediatamente ao redor, e é isso. As atualizações são, portanto, muito modestas, a menos que mil jogadores estejam próximos um do outro. Normalmente, você só precisa de deltas para um ou dois objetos e o conteúdo de um novo nó de grade depois de avançar em uma direção por mais da metade da largura de um nó. Tudo o resto: não é problema seu.
Damon
11
O ponto é que ser inteligente demais pode ser uma ideia extremamente estúpida. Seu mundo já está necessariamente dividido espacialmente, com um número gerenciável de objetos em cada nó. As CPUs modernas (e as GPUs ainda mais) são boas no processamento seqüencial de grandes quantidades de dados de SoA. Eles não gostam de ramificações incoerentes e gostam ainda menos de acesso incoerente à memória - o que é exatamente o que "apenas o processo próximo" faz. Para números gerenciáveis ​​(algumas centenas, milhares), "processar tudo" em uma célula é perfeitamente adequado e provavelmente a melhor coisa que você pode fazer.
Damon
11
@Alakanu Parece-me uma resposta detalhada e completa à sua pergunta. Se você acha que não é uma resposta, ou você a entendeu mal ou sua pergunta é tão obscura que ela foi mal interpretada por Damon, eu e todas as pessoas que aprovamos esta resposta.
precisa saber é o seguinte
2
@Alakanu Você realmente gasta uma quantidade enorme de tempo reclamando com as pessoas que estão tentando ajudá-lo. Boa sorte com isso.
precisa saber é o seguinte
2

O @ T.Sar escreve em um comentário que você deve procurar no conceito "pedaço carregado" do Minecrafts para obter mais informações. Se o fizer, saiba que isso é bastante complicado no Minecraft devido ao fato de as pessoas construírem máquinas no jogo.

Uma versão muito simplificada segue:

O mundo está dividido em regiões quadradas (pedaços). No Minecraft, há também uma divisão de altura, mas a maioria dos mmos não precisa disso.

O cliente do jogo se preocupa apenas com as regiões próximas ao jogador. Isso é muito mais simples do que desenhar um círculo ao redor do player, mas perfeitamente bom o suficiente.

No Minecraft, as regiões são blocos de 16x16 e o ​​cliente conhece regiões de 9x9, 4 regiões em cada direção. (4 regiões leste + região está em + 4 regiões oeste = 9 regiões no total. Mesmo norte / sul)

Não há nada mágico nesses números, use o que fizer sentido no seu jogo.

O cliente apenas anima coisas dentro desta área. O servidor apenas calcula coisas como monstros errantes em regiões próximas a algum jogador.

Quando um jogador anda dentro de uma região, nada de especial acontece; quando eles cruzam a fronteira da região, a "borda da animação" é empurrada uma região. O cliente precisa perguntar ao servidor sobre as regiões que ele vê agora.

Não há nada errado em ter vários limites de animação aninhados. Por exemplo, item animado cai em uma área 3x3, monstros errantes em uma área 5x5 e apenas mostra a paisagem em uma área 9x9.

O servidor mantém uma "versão congelada" de regiões que nenhum jogador vê. Se isso exigir muita memória, você poderá descarregá-las depois de um tempo. Quando um jogador chega em seguida, a região é recarregada sem que o item caia. Você precisa ser mais rápido da próxima vez, Jogador 1.

Stig Hemmer
fonte
A distância de desenho é ajustável, mas, neste caso, 8 blocos são 9x9 e são uma decisão do lado do cliente; ele pode informar o servidor para acelerar as coisas (para que o servidor não envie dados que o cliente não renderizará). Além disso ... Doom e Quake não resolveram esse problema de renderizar apenas o que faz sentido?
SparK 7/11
Sobre o cancelamento da retirada dos itens descartados ... no minecraft, o item apenas "envelhece" quando há um jogador por perto. Assim, você pode "salvar" um item descartado em um pedaço descarregado e obtê-lo mais tarde.
SparK 7/11