¿Cómo debo construir la estructura de datos para un “laberinto” dinámico de tamaño ilimitado?

43

No estoy realmente seguro de que "laberinto" sea el término correcto. Básicamente, los usuarios comienzan en un solo Room que tiene 4 puertas (N, S, E y W). Pueden ir en cualquier dirección, y cada habitación subsiguiente contiene otra habitación con entre 1 y 4 puertas que van a otras habitaciones.

Se supone que el "laberinto" tiene un tamaño ilimitado y que crece a medida que mueves habitaciones. Hay un número limitado de Rooms disponible, sin embargo, el número disponible es dinámico y puede cambiar.

Mi problema es que no estoy seguro de cuál es la mejor estructura de datos para este tipo de patrón

La primera vez que pensé fue en usar una matriz [X] [X] de objetos Room , pero realmente preferiría evitar eso ya que se supone que la cosa crece en cualquier dirección, y solo las habitaciones que están "visitadas" debe ser construido.

La otra idea era que cada clase Room contuviera 4 propiedades Room vinculadas para N, S, E y W, y solo un enlace al Room anterior, pero no tengo el problema. saber cómo identificar si un usuario ingresa a una habitación que tiene una habitación adyacente ya "construida"

Por ejemplo,

---    ---            ----------
|        |            |        |
   Start        5          4
|        |            |        |
---    ---            ---    ---
---    --- ---------- ---    ---
|        | |        | |        |
|    1          2          3
|        | |        | |        |
---    --- ---    --- ----------

Si el usuario se mueve desde Inicio > 1 > 2 > 3 > 4 > 5, entonces Room # 5 necesita saber que W contiene la sala de inicio, S es la habitación # 2 y en este caso no debería estar disponible, y N puede ser un nuevo Room o una pared (nada).

Tal vez necesito una combinación de la matriz y las habitaciones vinculadas, o tal vez lo esté viendo de forma incorrecta.

¿Hay una mejor manera de construir la estructura de datos para este tipo de "laberinto"? ¿O estoy en el camino correcto con mi proceso de pensamiento actual y me estoy perdiendo algunos datos?

(En caso de que estés interesado, el proyecto es un juego muy similar a Munchkin Quest )

    
pregunta Rachel 11.05.2012 - 16:37

8 respuestas

44

Proporcione las coordenadas de cada sala (el inicio sería (0,0)) y almacene cada sala generada en un diccionario / hashmap por coordenadas.

Es trivial determinar las coordenadas adyacentes para cada habitación, que puede usar para verificar si ya existe una habitación. Puede insertar valores nulos para representar ubicaciones en las que ya se determina que no existe una sala. (o si eso no es posible, no estoy seguro de un cajero automático, un diccionario / hasmap separados para coordenadas que no contienen una habitación)

    
respondido por el Bubblewrap 11.05.2012 - 16:46
15

En la mayoría de los casos, lo que estás describiendo suena como un gráfico. Dados algunos de sus requisitos (el aspecto en crecimiento) probablemente elegiría una lista de adyacencias como la implementación (la otra opción común sería una matriz de adyacencia ).

No estoy seguro de qué idioma está utilizando, pero un buen tutorial / explicación con detalles de implementación para un gráfico implementado con una lista de adyacencia en .NET es here .

    
respondido por el Steven Evers 11.05.2012 - 16:49
9

Un par de reflexiones sobre la implementación (he pensado en Carcassonne, que tiene una serie de otros aspectos desafiantes para construir la matriz; incluso fue una pregunta de entrevista que una vez se me hizo).

Hay algunas preguntas que se hacen de esta estructura:

  1. ¿hay una habitación en X, Y?
  2. ¿hay una sala [N / S / E / W] de la ubicación vacía X, Y?

El problema con listas y gráficos simples

La dificultad con las listas simples es que uno tiene que caminar por la estructura para probar si se puede colocar algo en un lugar determinado. El sistema necesita una forma de acceder a una ubicación arbitraria O (1).

Considera:

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

Para encontrar la información, la posible ubicación '?', cuando está en 3, uno tiene que caminar todo el camino para llegar a 4. La respuesta del enlace con información adicional sobre cuántos nodos salta (de modo que 3 serían vinculado a 4 con una información adicional de 'salto 1') todavía requiere caminatas al encontrar la adyacencia de '*' de 6 o A.

Arreglos simples, grandes

  

Hay un número limitado de habitaciones disponibles

Si este no es un número grande, solo crea una matriz 2N x 2N y déjala ahí. Una matriz de 100 x 100 es 'solo' 10,000 punteros y 50 objetos. Indice directamente en la matriz.

Esto podría reducirse a solo NxN si las actividades fuera de límites cambiaran la matriz para estar siempre dentro de las restricciones. Por ejemplo, si se agregara una sala que se desbordaría a la matriz, haga que la cuadrícula desplace cada elemento una posición para que ya no haya subdesbordamiento. En este punto, el tamaño del mundo para 50 habitaciones sería de 2500 punteros y 50 objetos.

Matrices y matrices dispersas

Para crear esto de manera más óptima, busque en una matriz dispersa en la que la mayoría De los elementos son 0 o nulos. Para dos dimensiones, esto se conoce como una matriz dispersa . Muchos lenguajes de programación tienen varias bibliotecas para trabajar con esta estructura. Si la biblioteca se restringe a números enteros, uno podría usar este número entero como un índice en una matriz fija de habitaciones.

Mi enfoque preferido sería tener las habitaciones como una estructura (apuntadores a habitaciones adyacentes y coordenadas) y tener la habitación también como un puntero de una tabla hash que está hash en coordenadas. En esta situación, para preguntar qué sala es [N / S / E / W] de una sala nula, uno consultaría la tabla hash. Esto, por cierto, es el formato 'DOK' para almacenar una matriz dispersa.

    
respondido por el user40980 11.05.2012 - 19:19
2

¿Qué te parece esto?

Dé a cada celda un enlace a cada uno de sus vecinos. Asigne a cada celda algún tipo de nombre (es decir, "0/0", "-10/0" (suponga que comienza en 0,0)). Agrega un HashSet con todos los nombres en él. Cuando intentes moverte a otra celda, solo verifica que el vecino no exista en el HashSet.

Además, si creas una apertura a otra habitación, ¿eso implica que las habitaciones existen? Así que crearías un enlace a una habitación vacía sin enlaces a ninguna habitación. Probablemente también querrás revisar los nuevos cuartos vecinos. Si existe una, y se abriría a su nueva sala, agregue una puerta a esa sala.

   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 / Puerta; 1,0: N = 1,1 / Vacío; E = 2,0 / Puerta; S = 1, -1 / Muro

También deberías asegurarte de dar a cada habitación nueva al menos una puerta no adyacente (a otra habitación) para que el laberinto pueda crecer en esa dirección.

    
respondido por el Paul 11.05.2012 - 19:08
1

Lo que estás diseñando se parece mucho a un gráfico.

Estos a menudo se representan como un conjunto de estados Q , un estado inicial q0 Q , y algunas transiciones Δ . Por lo tanto, te sugiero que lo guardes así.

  • Un conjunto Q : {s, 1, 2, 3, 5, 6}
  • Un estado inicial q0 : s
  • Un mapa de relaciones de transición Δ : {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

La mayoría de los idiomas razonables tienen mapas y conjuntos.

    
respondido por el kba 12.05.2012 - 01:51
0

Podrías considerar una lista enlazada de 4 vías ...

  

La primera vez que pensé fue en usar una [X] [X] matriz de objetos de Habitación, pero realmente preferiría evitar eso, ya que se supone que la cosa debe crecer en cualquier dirección, y solo las habitaciones "visitadas" deberían estar construido.

Todavía puedes usar un [] [] para eso. El crecimiento dinámico puede ser lento, especialmente cuando se agrega al principio, pero tal vez no sea tan malo. Debes perfil para comprobar. Tratar de manipular algunas listas o mapas vinculados podría ser peor, y en un nivel constante en lugar de ocasional.

Puedes construir solo las salas visitadas implementando una evaluación perezosa. Un objeto puede estar en el lugar que contiene una sala y no construir esa sala hasta que se llame a room() . Entonces solo vuelve el mismo cada vez después de eso. No es difícil de hacer.

    
respondido por el Crazy Eddie 11.05.2012 - 17:29
0

Aprendí a hacer esto a través del libro "Cómo crear juegos de aventura en tu computadora". Si está dispuesto a escarbar a través del código BÁSICO (el libro es tan antiguo), lea aquí:

enlace

Para el acceso directo, lo que hacen es tener una serie de habitaciones, con un elemento en cada matriz que apunta a otra habitación a la que puede ir, con 0 (utilizaría -1 en estos días) para indicar que no puedo ir por ese camino Por ejemplo, harías una estructura de sala (o clase o lo que sea)

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
}

Entonces, podría tener una matriz o una estructura de lista enlazada, o como quiera que quiera administrar sus habitaciones. Para el estilo de matriz (o vectores C ++) usaría ese código y las instrucciones mantendrían el índice de la sala a la que se vinculan; para una lista enlazada, puede usar punteros a la siguiente sala.

Como han dicho otros, si necesita generar nuevas salas de forma dinámica cuando las personas ingresan a ellas, también puede hacerlo.

    
respondido por el laaph 12.05.2012 - 03:07
0

No intentes resolver todos los problemas con una estructura.

Defina el objeto de su habitación para almacenar cosas sobre la habitación, no sus relaciones con otras habitaciones. Luego, una matriz 1D, una lista, etc. puede crecer a su gusto.

Una estructura separada puede contener "accesibilidad": a qué salas se puede acceder desde la sala en la que estoy. Luego, decida si la accesibilidad transitiva debe ser un cálculo rápido o no. Es posible que desee un cálculo de fuerza bruta y un caché.

Evita la optimización temprana. Use estructuras realmente simples y algoritmos fáciles de entender y luego optimice los que se utilizan.

    
respondido por el Julian 12.05.2012 - 09:40

Lea otras preguntas en las etiquetas