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

43

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 )

Rachel
fonte
Eu não acho que qualquer tipo de array funcionaria, já que as salas cresceram em qualquer direção ... Então, se você começar em [0,0] e mover para a esquerda? tentaria [-1, 0].
Paul Paul
@Paul Acrescente uma linha / coluna, mude todos os dados da matriz e depois mude todas as posições do jogador para corresponder à nova matriz do mapa. Lento e pode ser difícil, dependendo de quanto deve ser deslocado, mas possível. Ainda assim, a resposta do Bubblewrap é muito melhor.
Izkata
Provavelmente estou errado, mas isso não seria melhor no GameDev.SE?
Dynamic
1
@ Dinâmico Esta é uma questão de estrutura de dados, por isso se encaixa muito bem aqui.
Izkata

Respostas:

44

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)

Plástico bolha
fonte
2
Faça com que cada objeto da sala contenha informações de nordeste a sul-oeste para outros objetos da sala, para que você possa usar o dicionário / mapa de hash e as direções cardeais da sala para navegar pelo labirinto (às vezes você desejará encontrar com coordenadas absolutas e às vezes, você quer saber o que está ao norte do objeto X da sala).
1111 Neil
2
@Paul Acho que a idéia é criar um dicionário de salas e, ao criar uma nova Room, procure salas adjacentes no dicionário e adicione seus links ao Roomobjeto antes de adicionar novas salas aos lados restantes. Assim, a única vez que a consulta do dicionário iria ocorrer é quando a criação de um novo Roomobjeto, e não ao viajar entreRooms
Rachel
7
Não há motivo para armazenar links para outras salas dentro de um Roomobjeto. Se você estiver na sala (x,y)e quiser viajar para o norte, procure uma sala (x,y+1)no dicionário, criando-a se ela não existir. As pesquisas de dicionário são muito rápidas O(1),.
Karl Bielefeldt
3
@KarlBielefeldt: A sala @ (x,y+1)pode existir, mas não pode ser navegada pelo (x,y)norte. Ou seja, que uma borda não pode ir diretamente de (x,y)para (x,y+1).
Steven Evers
2
Vocês estão fazendo isso complicado. Isso é basicamente o mesmo que um array .. exceto que você o procura em um dicionário, em vez de um array bidimensional. Quaisquer problemas que você encontrar com uma matriz também estarão lá ... mas ele usaria uma matriz de qualquer maneira.
User606723
15

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 .

Steven Evers
fonte
1
Não tenho certeza se um gráfico é suficiente para descrever isso, pois N / E / S / W não faz parte do conceito de gráfico; há apenas conectado e possivelmente entrada / saída.
Edward Strange
3
@CrazyEddie: Lembre-se de que a estrutura de dados / a não se destina a mapear diretamente para qualquer domínio específico (de fato, esse é o benefício deles). Neste exemplo em particular, o gráfico seria direcional e as arestas podem ser anotadas trivialmente com uma enumeração.
Steven Evers
A anotação poderia impor trivialmente até mesmo o relacionamento leste-oeste, norte-sul. Isso eliminaria os problemas de ir para o oeste da sala A para a sala B e depois para o leste da sala B para a sala C (em vez da sala A) devido a um link incorreto.
Peter Smith
3
Digamos que queríamos implementar uma sala preenchida por um mago que se protege teleportando o jogador dez quadrados em uma direção aleatória. Encontrar esse ponto em uma estrutura de dados baseada em gráfico seria muito caro, especialmente se essa sala não existisse e você tivesse que gerar todas as salas vinculando essa sala a outra sala no gráfico (já que a estrutura não permitiria várias, seções mutuamente desconectadas da masmorra).
Mark Booth
2
@ MarkBooth mas depois mudamos os requisitos, não?
Joshua Drake
9

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.

Comunidade
fonte
1
Boa resposta, como sugere o Bubblewrap , um dicionário com uma tupla de posição como chave é uma estrutura razoável a ser usada para implementar uma matriz esparsa.
Mark Booth
2

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.

Paulo
fonte
1

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

Um gráfico do labirinto

Estes são frequentemente representados como um conjunto de estados Q , um estado inicial q 0Q 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 0 : 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.

kba
fonte
0

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.

Edward Strange
fonte
1
Você poderia expandir o que quer dizer com uma "lista vinculada de quatro vias"? A única coisa que pude encontrar foi um artigo do CodeProject, que se resume a ser uma lista de adjacências.
Steven Evers
0

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.

laaph
fonte
0

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.

Julian
fonte