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

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)

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 .

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.

¿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.

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 q₀ ∈ 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 q₀ : 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.

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.

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.

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.