'Zoneamento' de áreas em um grande mapa de peças, bem como masmorras

10

Meu jogo é ter um mapa como o do Minecraft, da maneira que é pseudo-infinito e gerado aleatoriamente. E grande. Digamos que o usuário tenha explorado uma zona de 1000 x 1000 (2D aqui), ou seja, 1.000.000 de blocos.

Obviamente, não vou conseguir guardar tudo na memória. Também não quero ignorar tudo em um bloco de 10 ou qualquer raio - ambos não serão atualizados (todos os NPCs, talvez blocos reativos) e eu teria que trabalhar com posições estranhas como 1382,12918.

Portanto, se eu o dividisse em pedaços ou zonas ou qualquer coisa, por exemplo, blocos de 64x64, eu precisaria armazenar cada bloco e a posição do objeto como:

Pedaço a, b. Posicione x, y.

Mas e se eu quisesse masmorras e afins no meu mapa? Portanto, um único ladrilho que leva a uma masmorra de 40 andares, cada uma com uma área de 40x40. Não consigo armazenar exatamente aqueles no mesmo mapa.

E há o lado da memória; quanto eu poderia armazenar na memória ao mesmo tempo razoavelmente? Eu poderia fazer blocos por ID com bastante facilidade e ter a matriz 2D normal lá. Ou, novamente, existe uma solução mais eficaz do que ter um arquivo de dados dos tipos de bloco ? Então, para um 64x64 .. isso só será 20K ou o que for. Eu gostaria que, tanto quanto possível, o ambiente fosse carregado para a atualização mais realista. Mas não sei que tipo de limites posso atingir sem me tornar monopolizador de memória.

O Pato Comunista
fonte

Respostas:

9

Embora eu concorde com o sentimento: "não se preocupe, a menos que seja um problema comprovado", acho que vale a pena pensar desde o início: adaptar uma solução é muito mais doloroso. E sim, apenas atualizando blocos 'próximos' é o caminho a percorrer. Mas o armazenamento e a capacidade de endereçamento de itens no seu mundo de jogo de forma eficiente são muito importantes por razões de desempenho.

O que você realmente está pensando aqui é um conjunto de dados esparsos: algo em que os índices potenciais são grandes (ou ilimitados), mas apenas uma pequena proporção é realmente usada. O ponto principal é que você não sabe exatamente qual proporção será usada.

A solução padrão para um problema escasso de conjunto de dados é separar o índice / endereçamento do armazenamento de dados real. Portanto, se o objeto lado a lado for caro, armazene-o de forma compacta (por exemplo, uma matriz plana). Mas permita que ele seja indexado através de um objeto mais barato. Na sua forma mais simples, pode ser uma matriz 2D (ou 3D) que você pode indexar facilmente por coordenadas, mas cada item da matriz é simplesmente um índice. Você então usa esse índice para procurar o conteúdo real do bloco em uma matriz compacta e separada. Se o conteúdo do bloco ainda não existir, adicione-o ao final da matriz e armazene o índice na matriz 3D.

A solução fica mais complexa se você deseja oferecer suporte à exclusão de conteúdo (pois leva à fragmentação da matriz de conteúdo) e, se o conteúdo do seu bloco é barato, o peso extra do índice (índices de 32 ou 64 bits) provavelmente sobrecarregará as economias por não armazenar todos os blocos em potencial. Também é uma pesquisa extra, que prejudicará o desempenho do cache.

Você pode obter ainda mais eficiência de armazenamento introduzindo camadas extras de indireção. Digamos que você organize seus blocos em blocos, e os blocos têm uma granularidade de 64 x 64 x 64. Dado um bloco em 125, 1, 132, você sabe que ele pertence ao bloco (1,0,2). Portanto, você tem um mundo, que consiste em uma matriz de blocos compacta e uma matriz de índices de blocos (-1 se o bloco não existir). O conteúdo de cada bloco (se presente) é uma matriz de 64x64x64 de índices de bloco (-1 se o bloco ainda não existir) e uma matriz compacta de blocos usados. Dessa forma, você não queima uma quantidade enorme de índices de blocos para pedaços que nunca são usados. Seguindo esse tipo de abordagem e escolhendo números sensíveis para a granularidade de partes, você pode ampliar seu universo massivamente e manter seu uso de memória sob controle. Na verdade, se você criar seus pedaços 32x32x32,

Você também pode fazer truques sorrateiros, como usar a parte superior de seus índices de bloco ou bloco para significar algo especial. Portanto, se uma entrada na matriz de bloco tiver o bit superior definido, os 31 bits inferiores não significam um índice de bloco, em vez disso, significam um 'índice de distorção' ou algo semelhante, e você pode procurar isso em uma lista mantida separadamente para descobrir as coordenadas que ele leva.

MrCranky
fonte
Eu advertiria qualquer um que se deparar com essa pergunta no futuro: Embora nada neste post esteja incorreto, é honestamente horrível para um jogo como o Minecraft, que tem um mundo não escasso. (E MrCranky diz tanto.) Seu mundo só benefícios a partir desta se ele tem alguns poucos e muita nadas , não poucos algumas coisas e lotes de embalagens vazias .
1
Concordo sinceramente que a sobrecarga envolvida na manutenção de uma solução de armazenamento de conjunto de dados esparsa é bastante alta, portanto, você só faria isso se o equilíbrio estivesse claramente distorcido em direção à escassez. Os principais fatores aqui são: custo do item de dados e probabilidade do item de dados não ser utilizado. O Minecraft possui um enorme conjunto de dados em potencial (um grande número de blocos em cada direção). A proporção real do mundo potencial do jogo usado é pequena. Mesmo que você reivindique grandes quantidades dele enquanto se move pelo mundo, ainda é uma pequena fração dos itens de dados em potencial.
precisa saber é o seguinte
1
O que diferencia o Minecraft é que o custo por unidade é pequeno - talvez seja um único byte de armazenamento? Um valor indica 'nada lá', o restante são tipos de bloco e você pode facilmente ajustá-lo em um byte. Portanto, você não teria um índice para um único bloco, isso é uma loucura, o índice é muito maior do que apenas armazenar o valor real do bloco. Mas as regras esparsas do conjunto de dados ainda funcionam nos níveis mais altos. Cada pedaço (por exemplo, 64x64x64) é caro para armazenar (blocos de 256K); portanto, se você puder usar um único valor pequeno para indicar sua ausência ou seu endereço, se houver, você salvou um armazenamento massivo.
precisa saber é o seguinte
6

Por que você não pode armazenar um milhão de blocos na memória? Até meu telefone tem 256MB de RAM; um milhão de ladrilhos vazios será o que, 4-32MB?


fonte
Parecia um número tão grande para armazenar. Além disso, também vai demorar muito tempo para atualizá-los.
The Duck Comunista
2
É muito mais fácil ignorar um conjunto de blocos para atualizações do que lidar com algum tipo de solução de paginação em disco. Apenas .. ignore-os. Não atualize blocos a mais de X distância de um ator conhecido.
2
@TheCommunistDuck A única coisa que importa é a quantidade total de memória usada para armazenar os blocos, não o número de blocos.
23710 Justin Justin
1
Concordou com Kragen e Joe. Não se preocupe com o que parece muito - faça a matemática e resolva-a. É improvável que seja um problema.
Kylotan