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

Na verdade, não tenho certeza de que "labirinto" seja o termo correto. Basicamente, os usuários começam em um único Roomcom 4 portas (N, S, E e W). Eles podem ir em qualquer direção e cada sala subsequente contém outra sala com de 1 a 4 portas que vão para outras salas.

O "labirinto" deve ter tamanho ilimitado e crescer à medida que você move as salas. Há um número limitado de Roomsdisponíveis, no entanto, o número disponível é dinâmico e pode ser alterado.

Meu problema é que não tenho certeza da melhor estrutura de dados para esse tipo de padrão

Primeiro pensei em usar apenas uma série de Roomobjetos [X] [X] , mas prefiro evitar isso, já que a coisa deve crescer em qualquer direção, e apenas as salas "visitadas" devem ser construídas.

O outro pensamento era que cada Roomclasse contivesse 4 Roompropriedades vinculadas para N, S, E e W e apenas vinculasse à anterior Room, mas o problema com isso não sei como identificar se um usuário entra em uma sala que tem uma sala adjacente já "construída"

Por exemplo,

--- --- ----------
| | | |
   Início 5 4
| | | |
--- --- --- ---
--- --- ---------- --- ---
| | | | | |
| 1 2 3
| | | | | |
--- --- --- --- ----------

Se o usuário passar de Iniciar> 1> 2> 3> 4> 5, o Roomnº 5 precisará saber que W contém a sala inicial, S é a sala nº 2 e, nesse caso, não deve estar disponível, e N pode ser um novo Roomou uma parede (nada).

Talvez eu precise de uma mistura da matriz e das salas interligadas, ou talvez esteja apenas vendo isso da maneira errada.

Existe uma maneira melhor de construir a estrutura de dados para esse tipo de "labirinto"? Ou estou no caminho certo com o meu processo de pensamento atual e só estou perdendo algumas informações?

(Caso você esteja interessado, o projeto é um jogo muito semelhante ao Munchkin Quest )

Dê as coordenadas de cada sala (o início seria (0,0)) e armazene cada sala gerada em um dicionário / mapa de hash 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 locais onde já é determinado que não existe Sala. (ou, se isso não for possível, não tenho certeza, um dicionário / hasmap separado para coordenadas que não contêm uma sala)

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

Não sei ao certo 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 está aqui .

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

Algumas perguntas são feitas a essa estrutura:

1. existe um quarto em X, Y?
2. existe uma sala [N / S / E / W] do local vazio X, Y?

O problema com listas e gráficos simples

A dificuldade com 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).

Considerar:

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

Para encontrar a informação no possível local '?', Quando em 3, é necessário percorrer todo o caminho para chegar a 4. A resposta do link com informações adicionais sobre quantos nós salta (para que 3 seja vinculado a 4 com informações adicionais do 'salto 1') ainda requer caminhadas ao encontrar a adjacência de '*' de 6 ou A.

Simples, grandes, matrizes

Há um número limitado de quartos disponíveis

Se esse número não for grande, basta criar uma matriz 2N x 2N e deixá-la lá. Uma matriz de 100 x 100 é 'apenas' 10.000 ponteiros e 50 objetos. Índice diretamente na matriz.

Isso poderia ser reduzido para apenas NxN se as atividades fora dos limites mudassem a matriz para sempre estar dentro das restrições. Por exemplo, se for necessário adicionar uma sala que faça o underflow da matriz, faça com que a grade mude cada posição de um elemento para que não haja mais underflow. Nesse ponto, o tamanho do mundo para 50 salas seria 2500 ponteiros e 50 objetos.

Matrizes esparsas e matrizes

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

Minha abordagem preferida seria ter as salas como uma estrutura (ponteiros para salas adjacentes e coordenadas) e ter a sala também como ponteiro de uma tabela de hash com hash nas coordenadas. Nessa situação, para perguntar qual sala é [N / S / E / W] de uma sala nula, seria possível consultar a tabela de hash. Aliás, esse é o formato 'DOK' para armazenar uma matriz esparsa.

Que tal agora..

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

Além disso, se você criar uma abertura para outra sala, isso implica que as salas existem? Portanto, você criaria um link para uma sala vazia sem links para nenhuma sala. Você provavelmente também gostaria de verificar os novos quartos vizinhos. Se existir, e 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 a cada nova sala pelo menos uma porta não adjacente (para outra sala) para que o labirinto possa crescer nessa direção.

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

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

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

Os idiomas mais razoáveis ​​têm mapas e conjuntos.

Você pode considerar uma lista vinculada de quatro vias ...

Primeiro pensei em usar apenas um conjunto de objetos [X] [X] Room, mas prefiro evitar isso, já que a coisa deve crescer em qualquer direção, e apenas as salas "visitadas" devem ser construídas.

Você ainda pode usar um [] [] para isso. O crescimento dinâmico pode ser lento, principalmente ao adicionar no início, mas talvez não seja tão ruim assim. Você deve criar um perfil para verificar. Tentar manipular uma lista ou mapa vinculado pode ser realmente pior, e em um nível constante e não ocasional.

Você pode criar apenas salas visitadas implementando uma avaliação lenta. Um objeto pode estar no lugar que contém uma sala e não construir essa sala até que room()seja chamado nela. Depois, ele retorna o mesmo todas as vezes 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ê deseja ler o código BASIC (o livro é antigo), leia aqui:

http://www.atariarchives.org/adventure/chapter1.php

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 acessar, com 0 (eu usaria -1 hoje em dia) para indicar que você não pode vá por esse caminho. Por exemplo, você criaria 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 de qualquer outra forma que desejar gerenciar seus quartos. Para o estilo de matriz (ou vetores C ++), eu usaria esse código e as instruções conteriam o índice da sala à qual eles vinculam; para uma lista vinculada, você pode usar ponteiros para a próxima sala.

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

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

Defina o objeto da sua sala para armazenar coisas sobre a sala, não suas relações com outras salas. Então uma matriz 1D, lista etc pode crescer como você gosta.

Uma estrutura separada pode conter "acessibilidade" - quais salas são acessíveis a partir da sala em que estou. Depois, 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 burros de fácil compreensão e, em seguida, otimize os que são usados.