Alternativa ao array 2D em uma estrutura de mapa lado a lado

Depois de pesquisar por um longo tempo, estou surpreso que essa pergunta ainda não tenha sido feita. Em um jogo 2D de mapa lado a lado, como você lida com o mapa? Ficaria feliz em ter seu ponto de vista em qualquer idioma, embora eu esteja mais interessado em implementações de C ++.

Uma matriz 2D, um vetor 2D, uma classe manipulando uma lista vinculada com computação ad hoc para manipular coordenadas, um boost :: matrix ...? Que solução você usa e por quê?

Uma coisa que fiz para um mapa no estilo RPG - ou seja, casas nas quais você pode entrar, masmorras etc. - tem quatro estruturas principais: um mapa, uma área, uma zona e um ladrilho.

Uma peça é obviamente uma peça.
Uma Zona, ou um pedaço, ou qualquer outra coisa, é uma área de blocos X por Y. Isso tem uma matriz 2D.
Uma área é uma coleção de zonas. Cada área pode ter tamanhos de zona diferentes - o mundo superior pode usar uma zona de 32x32, enquanto uma casa pode ter uma zona de 10x20. Estes são armazenados em dicionários (para que eu possa ter Zona (-3, -2)).
Um mapa é uma coleção de áreas, todas ligadas entre si.

Eu senti que isso me permitia maior flexibilidade, em vez de ter um mapa enorme.

Vou explicar o que faço para um caso específico de mapas lado a lado: é para mapas efetivamente infinitos, onde o mundo é gerado sob demanda, mas você precisa salvar modificações nele:

Defino um tamanho de célula "N" e divido o mundo em quadrados / cubos "NxN" ou "NxNxN"

Uma célula terá uma chave exclusiva. Eu gero o meu usando hash ou usando diretamente a string formatada: "% i,% i,% i", x, y, z (onde x, y, z são as coordenadas mundiais do início da célula divididas por N)

O armazenamento dos índices de blocos em matrizes é simples, pois você sabe que possui blocos NxN ou NxNxN. Você também sabe quantos bits seu tipo de bloco ocupa. Basta usar uma matriz linear. Também facilita o carregamento e o salvamento / liberação das células.

Qualquer acessador apenas precisa gerar a chave da célula (para garantir que ela seja carregada / gerada e, em seguida, direcione o ponteiro para ela) e use um subíndice para procurar dentro dessa célula. para encontrar o valor do bloco nesse ponto específico.

Ao extrair a célula por sua chave, atualmente uso um mapa / dicionário, pois geralmente processo células inteiras de uma só vez (não gostaria de saber o quão ruim seria um acerto para fazer uma pesquisa de dicionário por bloco, eek).

Outro ponto, não mantenho mobs / players nos dados da célula. O material ativamente dinâmico precisa de seu próprio sistema.

A pergunta provavelmente não foi feita porque você não precisa de uma alternativa. Para mim, é:

Tile tiles[MAP_HEIGHT][MAP_WIDTH]; se o tamanho for fixo.

std::vector<Tile> tiles(MAP_HEIGHT*MAP_WIDTH); de outra forma.

Depende do estilo do jogo e do mapa honestamente. Para um mapa retangular relativamente pequeno, eu provavelmente ficaria com uma matriz 2D. Se o mapa tiver uma forma muito irregular (muitas lacunas vazias), um wrapper em torno de listas vinculadas que fornece a indexação O (1) provavelmente seria minha escolha.

Uma matriz indexada inteira fornece uma matriz 2147483647 ^ 2 2d. Isso é muito grande, mas excede o que você deseja carregar na memória. Se o mapa tiver que ser em grande escala, outra coisa a se considerar é dividir o mapa em partes. Cada pedaço tem tamanho fixo e contém uma sub-matriz de blocos que podem ser carregados / descarregados conforme necessário para manter a memória mais baixa.

Se é apenas um simples jogo lado a lado em uma grade como um jogo de estratégia baseado em turnos, algo assim:

struct Tile
{
    // Stores the first entity (enemy, NPC, item, etc) on the tile.
    int first_entity;
    ...
};

struct Entity
{
    // Stores the next entity on the same tile or
    // the next free entity index to reclaim if
    // this entity has been freed/removed.
    int next;
    ...
};

struct Row
{
    // Stores all the tiles on the row.
    vector<Tile> tiles;

    // Stores all the entities on the row.
    vector<Entity> entities;

    // Points to the first free entity index
    // to reclaim on insertion.
    int first_free;
};

struct Map
{
    // Stores all the rows in the map.
    vector<Row> rows;
};

Algumas pessoas podem se perguntar por que escolhi armazenar vetores separados para cada linha do mapa. É para melhorar a localização espacial à medida que percorremos as entidades que estão em um determinado bloco. Quando armazenamos um vetor separado por linha, todas as entidades dessa linha podem caber em L1 ou L2, enquanto elas podem nem mesmo caber em L3 se armazenarmos um contêiner de entidade para todas as entidades no mapa inteiro. Isso ainda tende a ser bastante barato comparado a, por exemplo, armazenar um vetor separado por bloco.

Para obter, digamos, o bloco em (102, 72), fazemos o seguinte:

Row& row = map.rows[72];
Tile& tile = row.tiles[102];

Para atravessar as entidades no bloco, fazemos:

int entity = tile.first_entity;
while (entity != -1)
{
    // Do something with the entity on the tile.
    ...

    // Advance to the next entity on the tile.
    entity = row.entities[entity].next;
}

Naturalmente, para que a implementação do tipo "contêiner separado por linha" seja a mais beneficiada, seus padrões de acesso ao bloco devem tentar processar todas as colunas de interesse de uma linha antes de passar para a próxima, sem fazer muito zigue-zague para frente e para trás de uma linha para outra. o próximo e voltar novamente.

A inserção de uma entidade em um bloco seria assim:

int Map::insert_entity(Entity ent, int col_idx, int row_idx)
{
     Row& row = rows[row_idx];

     int ent_idx = row.first_free;
     if (ent_idx != -1)
     {
          row.first_free = row.entities[ent_idx].next;
          row.entities[ent_idx] = ent;
     }
     else
     {
          ent_idx = static_cast<int>(row.entities.size());
          row.entities.push_back(ent);
     }

     Tile& tile = row.tiles[col_idx];
     row.entities[ent_idx].next = tile.first_entity;
     tile.first_entity = ent_idx;
     return ent_idx;
}

... e remoção:

void Map::remove_entity(int ent_idx, int col_idx, int row_idx)
{
     Row& row = rows[row_idx];
     Tile& tile = row.tiles[col_idx];
     if (tile.first_entity = ent_idx)
         tile.first_entity = row.entities[ent_idx].next;

     row.entities[ent_idx].next = row.first_free;
     row.first_free = ent_idx;
}

O principal motivo pelo qual eu gosto dessa solução é que evitamos armazenar muitos vetores (ex: um vetor por bloco: muitos para mapas grandes), mas não tão poucos que a iteração pelas entidades em um determinado bloco leva a passos épicos no endereço de memória falta de espaço e muita cache. Um vetor de entidade por linha atinge um bom equilíbrio lá.

Isso pressupõe que você tenha coisas como prédios e inimigos, itens e baús de tesouro e jogadores sobre os ladrilhos e que muito do tempo gasto na lógica do jogo esteja acessando as entidades que estão nesses ladrilhos, além de verificar quais entidades estão um dado bloco. Caso contrário, eu usaria uma abordagem de matriz 1D com um único vetor para todos os blocos, pois seria o mais eficiente para acessar apenas blocos. Você pode obter um bloco usando: tiles[row*num_cols+col]Use uma matriz unidimensional em caso de dúvida, pois ela permitirá percorrer as coisas em uma ordem seqüencial direta, sem loops aninhados e exigir apenas uma alocação de heap para alocar a coisa toda.

Em geral, a matriz dinâmica separada por linha é algo que eu descobri para reduzir muito as falhas de cache nos casos em que sua grade está armazenando elementos dentro dela. É claro que, se isso não acontecer, e sua grade for como uma imagem contendo pixels, não faz sentido usar uma matriz dinâmica separada por linha. Como um benchmark recente, onde eu otimizei algo semelhante a uma grade dessa maneira (antes de usar apenas uma matriz gigante para tudo; eu a otimizei para armazenar uma matriz dinâmica separada por linha depois de ver muitas falhas de cache no vtune):

Antes:

--------------------------------------------
- test_grid
--------------------------------------------
time passed for 'insert': {1.799000 secs}
mem use after 'insert': 479,508,224 bytes

8560 cells, 1000000 rects
finished test_grid: {1.919000 secs}

Depois de:

--------------------------------------------
- test_grid
--------------------------------------------
time passed for 'insert': {0.310000 secs}
mem use after 'insert': 410,546,720 bytes

8560 cells, 1000000 rects
finished test_grid: {0.361000 secs}

E eu usei o mesmo tipo de estratégia descrito acima. Como bônus, você também pode reduzir o uso de memória, porque os vetores que armazenam as entidades tendem a se ajustar melhor se você armazenar um por linha em vez de um para o mapa inteiro.

Observe que o teste acima para inserir um milhão de entidades na grade pode parecer demorado e com muita memória, mesmo após a otimização. Isso ocorre porque cada entidade que estou inserindo usa muitos blocos, com média de cerca de 100 blocos por entidade (tamanho médio de 10 x 10). Então, eu estou inserindo cada uma das milhões de entidades em uma média de 100 blocos de grade, o que torna mais a inserção de 100 milhões de entidades do que um mísero 1 milhão de entidades. É o teste de estresse de um caso patológico. Se eu apenas estiver inserindo um milhão de entidades que ocupam 1 bloco cada, posso fazê-lo em milissegundos e usando apenas 16 megabytes de memória.

No meu caso, muitas vezes preciso tornar os casos patológicos eficientes, pois trabalho em efeitos visuais em vez de jogos. Não sei dizer aos artistas: "Crie seu conteúdo dessa maneira para este mecanismo"já que o objetivo principal do VFX é permitir que os artistas criem o conteúdo da maneira que quiserem. Eles então o otimizam antes de exportar para seu mecanismo favorito, mas eu tenho que lidar com coisas não otimizadas, o que significa que muitas vezes preciso lidar com eficiência com os casos patológicos, como um octree precisando lidar com triângulos maciços que abrangem toda a cena desde os artistas criam esse conteúdo com frequência (com muito mais frequência do que se poderia esperar). De qualquer forma, esse teste acima está testando algo que nunca deveria acontecer e é por isso que leva quase um terço de segundo para inserir um milhão de entidades, mas no meu caso essas coisas "nunca devem acontecer" acontecem o tempo todo. Portanto, o caso patológico não é um caso raro para mim,

Como bônus adicional, isso também permite que você insira e remova entidades para várias linhas simultaneamente em paralelo usando multithreading sem bloqueio, já que agora você pode fazê-lo com segurança, pois cada linha possui um contêiner de entidade separado, desde que dois threads não estejam tentando insira / remova material para / da mesma linha simultaneamente.

Estou brincando com um mecanismo 3D onde o mundo é uma malha.

Estou importando alguns mapas 2D + conjuntos de peças que foram feitos anteriormente.

E quando eu faço, eu o converto em uma malha 3D e coloco todos os blocos em uma única textura.

Isso atrai substancialmente mais rápido.

Talvez eu mantivesse o mapa em uma matriz 1D de w * h se tivesse que manter seu conceito de bloco, mas minha resposta é que é libertador ir além do 2Dness.

E, se você tiver problemas de desempenho ao usar o desenho da GPU, manter a representação gráfica como uma textura única - com uma malha se tiver alturas variáveis ​​- pode realmente acelerar isso em comparação com o desenho de cada peça individualmente.