Uma maneira de armazenar dados de mapa 2D potencialmente infinitos?

29

Eu tenho um jogo de plataformas 2D que atualmente pode lidar com pedaços de 100 por 100 peças, com as coordenadas do pedaço armazenadas como comprimentos, então esse é o único limite de mapas (maxlong * maxlong). Todas as posições da entidade, etc., são relevantes para o bloco e, portanto, não há limite.

O problema que estou tendo é como armazenar e acessar esses pedaços sem ter milhares de arquivos. Alguma idéia para um formato de arquivo de HD, de preferência rápido e de baixo custo, que não precise abrir tudo de uma vez?

Blam
fonte
2
Algumas estruturas de dados nas quais você pode procurar mais inspiração são matrizes esparsas e tabelas de página (multinível) .
Andrew Russell
Baixa prioridade: você poderia esclarecer se o tipo de dados "longo" é de 32 ou 64 bits?
Randolf Richardson
2
@ Randolf, dado que este é C #, presumivelmente ele quer dizer o C # longque é de 64 bits (o máximo é Int64.MaxValue).
Andrew Russell
Notch tem algumas coisas interessantes a dizer sobre os mapas infinitos em Minecraft em seu blog aqui: notch.tumblr.com/post/3746989361/terrain-generation-part-1
dlras2

Respostas:

17

Crie um formato de mapa personalizado para o seu jogo. É mais fácil do que você imagina. Basta usar a classe BinaryWriter. Primeiro escreva o cabeçalho em algumas polegadas ou uints. Informações a serem incluídas no cabeçalho:

  • A sequência mágica / número mágico do seu formato de arquivo.
  • O início / fim / tamanho dos pedaços descritos neste arquivo

e também (e aqui vem a parte crítica do desempenho

  • entradas que descrevem a posição inicial dentro do arquivo. Portanto, você não precisa procurar por pedaços específicos.

Com o método acima, você pode (e deve) criar um índice do conteúdo de seus arquivos, contendo algum tipo de descrição (um nome especificado pelo usuário para a região / bloco ou apenas as coordenadas) e, como segundo valor, a posição no arquivo.

Então, quando você deseja carregar um pedaço específico, basta pesquisar dentro do índice. Quando você tiver a posição, defina fileStream.Position = PositionOfChunkFromIndex e poderá carregá-la.

É tudo sobre o design do formato do arquivo, com o cabeçalho descrevendo o conteúdo do arquivo com mais eficiência.

Apenas salve os arquivos com uma extensão personalizada criada e pronto.

BÔNUS: Adicione a compactação BZip2 a regiões específicas do arquivo / todo o conteúdo (não o cabeçalho !!), para que você possa descompactar partes específicas do arquivo, para obter uma quantidade muito pequena de memória.

Riki
fonte
12
Vale ressaltar que, se você estiver modificando esse arquivo rapidamente, desejará um cabeçalho / índice de tamanho fixo ou externo, para poder adicionar pedaços ao arquivo sem precisar reescrever o arquivo. arquivo inteiro (devido à alteração das compensações).
Andrew Russell
Nesse ponto, você não está apenas implementando um banco de dados flatfile?
Ape-Inago
13

Encontrei um problema semelhante e decidi criar minha própria estrutura para lidar com os dados. Baseia-se livremente em um quadtree, mas tem capacidade de expansão infinita (pelo menos tão grande quanto uma Int) em todas as direções. Ele foi projetado para lidar com dados baseados em grade que se expandiam a partir de um ponto central, assim como o Minecraft faz agora. É espaço eficiente na memória e muito rápido.

Você pode especificar uma magnitude mínima para cada nó (uma magnitude de 7 seria 128x128) e, uma vez que qualquer nó tenha uma porcentagem especificada de seus subnós preenchidos, ele se achatará automaticamente em uma matriz bidimensional. Isso significa que uma porção muito densamente povoada (por exemplo, um continente completamente explorado) terá o desempenho de uma matriz (muito rápido), mas uma porção escassamente povoada (por exemplo, uma linha costeira que alguém percorreu para cima e para baixo, mas não explorou o interior) terá bom desempenho e pouco uso de memória.

Meu código pode ser encontrado aqui . O código está completo, testado (testes de unidade e carga) e bastante otimizado. No entanto, o funcionamento interno ainda não está muito bem documentado, mas todos os métodos públicos são, portanto, devem ser utilizáveis. Se alguém decidir experimentá-lo, sinta-se à vontade para entrar em contato comigo com perguntas ou comentários.

Ainda não o usei para armazenar dados em um arquivo, mas é um problema interessante e posso resolver isso a seguir.

dlras2
fonte
Então essa é basicamente uma árvore expansível, certo? o que estou perdendo?
kaoD
2
A maior melhoria em relação a uma árvore expansível é que ela 'nivela' certos nós da árvore que são fortemente preenchidos (padrão 70%) em matrizes 2D, em vez de mantê-los estruturados como árvores. Isso fornece a velocidade de uma pesquisa de matriz, sem o tamanho (infinito) de uma matriz infinita.
dlras2
Ambos nós foliares e internos, certo? Idéia interessante, pode dar bons resultados, vou tentar se precisar. Btw, +1 por fornecer o código e a resposta rápida! Ah, e unidade de teste feito também, eu (infelizmente) nunca faço isso em meus projetos pessoais :)
kaoD
Não realizamos nenhum teste de unidade no meu trabalho, então, infelizmente, é a minha maneira de me rebelar. Criei um aplicativo de demonstração para ele, que mostra como ele é preenchido e achatado, para que eu possa limpar isso nos próximos dias, para que seja apresentável, eu vou postar aqui também. Faz muito mais sentido quando você a vê.
dlras2
1
Eu perdi de vista, desculpe! Ainda gostaria de limpá-lo, mas estou refazendo lentamente parte do código entre a aula e a lição de casa, para que não demore um pouco. Por enquanto, a demo antiga e desagradável está aqui: j.mp/qIwKYt Por desagradável , quero dizer parcialmente que isso exige muita explicação; portanto, não esqueça de ler o README e fique à vontade para fazer perguntas aqui ou via email.
precisa saber é o seguinte
3

Você pode usar um banco de dados - o PostgreSQL possui alguns recursos especiais de indexação otimizados para esse tipo de dados, localizado pelas coordenadas X e Y. Você também pode especificar que os dados retornados estejam dentro de um determinado raio e não em uma área quadrada ou oblonga.

  PostgreSQL (código aberto e gratuito)
  http://www.postgresql.org/

Também existem outros bancos de dados e, para o lado do cliente, você pode encontrar certos tipos mais adequados para isso, pois eles podem ser executados de forma independente (iniciada pelo aplicativo cliente do jogo) ou podem ser incluídos como parte de uma biblioteca de códigos que você pode "apenas usar". A vantagem é que você não precisa criar um esquema de indexação porque a maioria dos mecanismos de banco de dados SQL já faz isso muito bem.

Uma vantagem da abordagem do banco de dados é que você pode diminuir seus blocos (ou se livrar completamente dos blocos e usar blocos diretamente), mas o uso de pelo menos pequenos grupos / grupos de vários blocos pode ser mais eficiente, dependendo do seu design), e use a consulta SQL para criar uma área maior do que a visível. Ao pré-carregar para sobrepor áreas não visíveis próximas, as peças podem ser preparadas antes que o jogador mova seu personagem, resultando em uma melhor experiência de jogo (espero que seja mais suave).

Percebi que alguns jogos mantêm um "cache" dos dados do mapa no disco rígido local após obtê-los pela primeira vez (isto é, sem dúvida, para reduzir a E / S da rede), como o Ashen Empires:

  Impérios Ashen (livre para jogar, bela implementação 2D)
  http://www.ashenempires.com/

Manter o controle dos registros de data e hora da "última atualização" com cada bloco / bloco também será útil, pois, onde os dados armazenados localmente estão disponíveis, a consulta SQL pode incluir uma cláusula "WHERE timestamp_column> $ local_timestamp" adicional para que somente blocos / blocos atualizados sejam recebidos. baixado (dois benefícios de economizar largura de banda como essa são custos mais baixos de conectividade e menos atraso para os jogadores, o que se tornará mais óbvio quando o jogo se tornar popular).

Uma captura de tela de Ashen Empires (alguns personagens estão em um banco local e, pela aparência desses ossos no chão, parece que alguns monstros-esqueleto devem ter entrado e provavelmente foram massacrados pelos guardas da cidade local):

insira a descrição da imagem aqui

Randolf Richardson
fonte
2

Não os armazene e acesse, armazene apenas as sementes aleatórias necessárias, bem como as mudanças do jogador no mapa. Em seguida, gere as partes necessárias no tempo de execução (execute o algoritmo de geração e aplique as alterações do player). Com o procedimento de geração correto e consistente, o mapa resultante sempre será o mesmo para a mesma semente inicial.

Teoricamente, você pode fazer um mapa literalmente infinito que será salvo em um arquivo muito pequeno dessa maneira.

código sh
fonte
@ Josh Petrie, obrigado pelas significativas e ótimas correções de estilo / linguagem no meu post. pena que eu não posso aprovar uma edição :-D
código sh
1

Existe alguma maneira de particionar pedaços (algum tipo de 'subcontinente / país' no seu mundo)? Então, talvez você possa ter algum tipo de arquivo de índice que permita encontrar rapidamente qual subarquivo / parte do arquivo maior você precisa carregar para ter um pedaço de memória ...

phtrivier
fonte
sempre há uma maneira de particionar pedaços. SEMPRE. estejam visíveis para o player / relevantes para o resto do sistema ou não, sempre há uma maneira de particionar dados do mundo em partes, geralmente de várias maneiras diferentes.
código sh
0

Você pode pegar a ideia do Minecraft. Originalmente, eles tinham um arquivo por bloco. Agora eles usam o formato MCRegion, que agrupa partes em áreas 32x32 e armazena uma por arquivo.

O Pato Comunista
fonte