Como devo construir a estrutura de dados para um “labirinto” dinâmico e ilimitado?

Dê as coordenadas de cada sala (o início seria (0,0)) e armazene cada sala gerada em um dicionário / hashmap por coordenadas.

É trivial determinar as coordenadas adjacentes para cada sala, que você pode usar para verificar se uma sala já existe. Você pode inserir valores nulos para representar localizações onde já está determinado que não existe nenhum espaço. (ou se isso não for possível, não tenho certeza atm, um dicionário / hasmap separado para coordenadas que não contenham um Room)

Na maioria dos casos, o que você está descrevendo parece um gráfico. Dados alguns dos seus requisitos (o aspecto crescente), eu provavelmente escolheria uma lista de adjacências como a implementação (a outra opção comum seria uma matriz adjacente ).

Não tenho certeza de qual idioma você está usando, mas um bom tutorial / explicação com detalhes de implementação para um gráfico implementado com uma lista de adjacências no .NET é aqui .

Algumas reflexões sobre a implementação (pensei em Carcassonne, que tem vários outros aspectos desafiadores na construção da matriz - foi até mesmo uma pergunta da entrevista que uma vez me foi feita).

Há algumas perguntas que são feitas sobre essa estrutura:

1. há uma sala no X, Y?
2. há uma sala [N / S / E / W] do local vazio X, Y?

O problema com listas e gráficos simples

A dificuldade com as listas simples é que é preciso percorrer a estrutura para testar se algo pode ser colocado em um determinado local. O sistema precisa de uma maneira de acessar um local arbitrário O (1).

Considere:

1 2 3 ? 4
5 . . * 6
7 8 9 A B

Para encontrar a informação a possível localização '?', quando em 3, tem que andar todo o caminho para chegar a 4. A resposta de link com informações extras em quantos nós salta (de modo que 3 seria ligado a 4 com uma informação extra 'salto 1') ainda requer caminhadas ao encontrar a adjacência de '*' de 6 ou A.

Matrizes simples e grandes

There is a limited number of Rooms available

Se este for um número não grande, basta criar uma matriz 2N x 2N e deixar lá. Um array de 100 x 100 é 'somente' 10.000 ponteiros e 50 objetos. Indexar diretamente na matriz.

Isso poderia ser reduzido para apenas NxN se atividades fora dos limites mudassem a matriz para sempre estar dentro das restrições. Por exemplo, se fosse adicionada uma sala que preenchesse a matriz, fizesse com que a grade deslocasse todos os elementos de uma posição para que não houvesse mais underflow. Neste ponto, o tamanho do mundo para 50 quartos seria de 2500 ponteiros e 50 objetos.

Matrizes e matrizes esparsas

Para melhor criar isso, procure em um array esparso no qual a maioria dos elementos são 0 ou nulo. Para duas dimensões, isso é conhecido como uma matriz esparsa . Muitas linguagens de programação possuem várias bibliotecas para trabalhar com essa estrutura. Se a biblioteca restringir a números inteiros, pode-se usar esse inteiro como um índice em uma matriz fixa de salas.

Minha abordagem preferida seria ter os quartos como uma estrutura (ponteiros para salas adjacentes e coordenadas) e ter o quarto também um ponteiro de uma tabela de hash que é coordenada em hash. Nessa situação, para perguntar qual sala é [N / S / E / W] de uma sala nula, uma consulta a tabela de hash. Este, aliás, é o formato 'DOK' para armazenar uma matriz esparsa.

Que tal isso ...

Dê a cada célula um link para cada um de seus vizinhos. Dê a cada célula algum tipo de nome (isto é, "0/0", "-10/0" (Suponha que você comece em 0,0)). Adicione um HashSet com todos os nomes nele. Ao tentar mover para outra célula, apenas verifique se o vizinho ainda não existe no HashSet.

Além disso, se você criar uma abertura para outra sala, isso significa que as salas existem? Então você criaria um link para uma sala vazia sem links para qualquer sala. Você provavelmente também gostaria de verificar os vizinhos novos quartos. Se existir um, e se abrir para o seu novo quarto, adicione uma porta a esse quarto.

   Empty   
   (0,1)        

---    ---            ----------
|        |            |        |
    0,0       1,0        2,0       Empty
|        |            |        |   (3,0)
---    --- ---------- ---    ---
|        | |        | |        |
|   0,-1      1,-1       2,-1      Empty
|        | |        | |        |   (3,-1)
---    --- ---    --- ----------

   Empty     Empty   
  (0,-2)    (1,-2)

HashSet = {0 | 0, 1 | 0, 2 | 0, 3 | 0, 0 | -1, 1 | -1 ....} 1,0: W = 0,0 / porta; 1,0: N = 1,1 / Vazio; E = 2,0 / porta; S = 1, -1 / parede

Você também precisa garantir que cada quarto novo seja entregue a pelo menos uma porta não adjacente (para outra sala) para que o labirinto possa crescer nessa direção.

O que você está criando parece muito com um gráfico.

Estes são frequentemente representados como um conjunto de estados Q , um estado inicial q ₀ em Q , e algumas transições Δ . Então, sugiro que você armazene assim.

• Um conjunto Q : {s, 1, 2, 3, 5, 6}
• Um estado inicial q ₀ : s
• Um mapa de relações de transição Δ : {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

As linguagens mais razoáveis têm mapas e conjuntos.

Você pode considerar uma lista encadeada de 4 vias ...

I first thought about just using a [X][X] array of Room objects, but I'd really rather avoid that since the thing is supposed to grow in any direction, and only rooms that are "visited" should be built.

Você ainda pode usar um [] [] para isso. O crescimento dinâmico pode ser lento, especialmente ao adicionar no começo, mas talvez não seja tão ruim assim. Você deve perfil para verificar. Tentar manipular alguma lista ou mapa vinculado pode, na verdade, ser pior, e em um nível constante, em vez de ocasional.

Você pode criar apenas salas visitadas implementando a avaliação lenta. Um objeto pode estar no lugar que contém uma sala e não constrói essa sala até que room() seja chamado. Então apenas retorna o mesmo toda vez depois disso. Não é difícil de fazer.

Eu aprendi a fazer isso através do livro "Criando Jogos de Aventura no Seu Computador". Se você está disposto a cavar através do código BASIC (o livro é tão antigo), leia aqui:

link

Para o atalho, o que eles fazem é ter uma matriz de salas, com um elemento em cada matriz sendo um ponteiro para outra sala que você pode ir, com 0 (eu usaria -1 estes dias) para indicar que você não pode ir por esse caminho. Por exemplo, você faria uma estrutura de sala (ou classe ou o que você tem)

room {
 int north_dir;
 int south_dir;
 int west_dir;
 int east_dir;
 // All other variables and code you care about being attached to the rooms here
}

Em seguida, você pode ter uma matriz ou uma estrutura de lista vinculada ou qualquer outra que você queira gerenciar suas salas. Para o estilo de matriz (ou vetores de C ++), eu usaria esse código e as direções manteriam o índice da sala à qual eles vinculam; para uma lista vinculada, você poderia usar ponteiros para a próxima sala.

Como outros já disseram, se você precisar gerar novas salas dinamicamente quando as pessoas entrarem, você também pode fazer isso.

Não tente resolver todos os problemas com uma estrutura.

Defina seu objeto de sala para armazenar coisas sobre a sala, não suas relações com outras salas. Em seguida, uma matriz 1D, lista, etc, pode crescer como quiser.

Uma estrutura separada pode conter "acessibilidade" - quais salas são acessíveis a partir da sala em que estou. Em seguida, decida se a acessibilidade transitiva precisa ser um cálculo rápido ou não. Você pode querer um cálculo de força bruta e um cache.

Evite a otimização antecipada. Use estruturas realmente simples e algoritmos estúpidos facilmente compreendidos e otimize os que são usados.