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

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?

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 .

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.

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.