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

43

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

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

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

Primero pensé en usar una matriz [X] [X] de Roomobjetos, pero realmente preferiría evitar eso ya que se supone que la cosa debe crecer en cualquier dirección, y solo se deben construir habitaciones que se "visiten".

El otro pensamiento era que cada Roomclase contuviera 4 Roompropiedades vinculadas para N, S, E y W, y solo se vinculara a la anterior Room, pero el problema con eso es que no sé cómo identificar si un usuario entra en una sala que tiene una habitación adyacente ya "construida"

Por ejemplo,

--- --- ----------
El | El | El | El |
   Inicio 5 4
El | El | El | El |
--- --- --- ---
--- --- ---------- --- ---
El | El | El | El | El | El |
El | 1 2 3
El | El | El | El | El | El |
--- --- --- --- ----------

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 sala # 2 y en este caso no debería estar disponible, y N puede ser un nuevo Roomo una pared (nada).

Tal vez necesito una mezcla de la matriz y las habitaciones vinculadas, o tal vez solo estoy mirando esto de la manera incorrecta.

¿Existe 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 solo me faltan algunos datos?

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

Rachel
fuente
No creo que funcione ningún tipo de matriz ya que las habitaciones crecerían en cualquier dirección ... ¿Entonces si comienzas en [0,0] y te mueves a la izquierda? intentaría [-1, 0].
Paul
@Paul Agregue una fila / columna, cambie todos los datos de la matriz, luego cambie todas las posiciones del jugador para que coincida con la nueva matriz del mapa. Lento y puede ser difícil dependiendo de cuánto se debe cambiar, pero es posible. Aún así, la respuesta de Bubblewrap es mucho mejor.
Izkata
Probablemente me equivoque, pero ¿no sería mejor en GameDev.SE?
Dinámico
1
@ Dinámico Esta es una pregunta de estructura de datos, por lo que encaja perfectamente aquí.
Izkata

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 Habitación. (o si eso no es posible, no estoy seguro de cajero automático, un diccionario / hasmap separado para coordenadas que no contienen una habitación)

Plástico de burbujas
fuente
2
Haga que cada objeto de la sala contenga información de noreste a sur-oeste con respecto a otros objetos de la sala, para que pueda usar el diccionario / hashmap así como las direcciones cardinales de la sala para navegar por el laberinto (a veces querrá encontrar con coordenadas absolutas y a veces querrás saber qué hay al norte del objeto Room X).
Neil
2
@Paul Creo que la idea es crear un diccionario de habitaciones, y cuando construyas una nueva Room, busca habitaciones adyacentes en el diccionario y agrega sus enlaces al Roomobjeto antes de agregar nuevas habitaciones a los lados restantes. Entonces, el único momento en que se realizaría la búsqueda en el diccionario es cuando se crea un nuevo Roomobjeto, no cuando se viaja entreRooms
Rachel
77
No hay ninguna razón para almacenar enlaces a otras habitaciones dentro de un Roomobjeto. Si está en la habitación (x,y)y quiere viajar al norte, busque habitación (x,y+1)en el diccionario, creándola si no existe. Búsquedas en diccionarios son muy rápidos, O(1).
Karl Bielefeldt
3
@KarlBielefeldt: La sala @ (x,y+1)puede existir, pero no se puede navegar desde el (x,y)norte. Es decir, que un borde puede no ir directamente de (x,y)a (x,y+1).
Steven Evers
2
Ustedes están haciendo esto complicado. Esto es básicamente lo mismo que una matriz ... excepto que lo está buscando en un diccionario en lugar de una matriz bidimensional. Cualquier problema que encuentres con una matriz también estará allí ... pero él iba a usar una matriz de todos modos.
user606723
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 creciente) probablemente elegiría una lista de adyacencia como implementación (la otra opción común sería una matriz de adyacencia ).

No estoy seguro de qué idioma se 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 está aquí .

Steven Evers
fuente
1
No estoy seguro de que un gráfico sea suficiente para describir esto ya que N / E / S / W no son realmente parte del concepto de gráfico; solo hay conectado y posiblemente entrada / salida.
Edward Strange
3
@CrazyEddie: Tenga en cuenta que la estructura de datos / a no está destinada a mapearse directamente a ningún dominio en particular (de hecho, ese es su beneficio). En este ejemplo particular, el gráfico sería direccional y los bordes se pueden anotar trivialmente con una enumeración.
Steven Evers
La Anotación podría hacer cumplir trivialmente la relación este-oeste, norte-sur incluso. Esto eliminaría los problemas de ir al oeste de la habitación A a la habitación B y luego ir al este de la habitación B a la habitación C (en lugar de la habitación A) debido a un mal enlace.
Peter Smith
3
Digamos que queríamos implementar una sala poblada por un mago que se proteja teletransportando al jugador diez casillas en una dirección aleatoria. Encontrar ese punto en una estructura de datos basada en gráficos sería muy costoso, especialmente si esa habitación no existiera y tuvieras que generar todas las habitaciones que vinculan esa habitación con otra habitación en el gráfico (ya que la estructura no permitiría múltiples, secciones de mazmorra mutuamente desconectadas).
Mark Booth
2
@ MarkBooth pero luego hemos cambiado los requisitos, ¿no?
Joshua Drake
9

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

Hay algunas preguntas que se hacen de esta estructura:

  1. ¿hay una habitación en X, Y?
  2. ¿hay una habitación [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).

Considerar:

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

Para encontrar la información de la posible ubicación '?', Cuando a las 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 (para que 3 esté vinculado a 4 con una información adicional de 'salto 1') todavía requiere caminatas al encontrar la adyacencia de '*' de 6 o A.

Matrices simples y grandes

Hay un número limitado de habitaciones disponibles.

Si este no es un número grande, simplemente cree una matriz de 2N x 2N y déjelo allí. 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 los límites desplazaran la matriz para estar siempre dentro de las restricciones. Por ejemplo, si se agregara una habitación que desbordaría la matriz, haga que la cuadrícula desplace cada elemento una posición para que ya no haya desbordamiento. En este punto, el tamaño del mundo para 50 habitaciones sería de 2500 punteros y 50 objetos.

Matrices dispersas y matrices

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 enteros, uno podría usar este entero como un índice en una matriz fija de habitaciones.

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

Comunidad
fuente
1
Buena respuesta, como sugiere Bubblewrap , sin embargo, un diccionario con una tupla de posición como clave es una estructura razonable para implementar una matriz dispersa.
Mark Booth
2

Qué tal esto..

Dele a cada celda un enlace a cada uno de sus vecinos. Dé a cada celda algún tipo de nombre (es decir, "0/0", "-10/0" (Suponga que comienza en 0,0)). Agregue un HashSet con todos los nombres en él. Mientras intenta pasar a otra celda, simplemente verifique que el vecino no exista en el HashSet.

Además, si crea una apertura a otra habitación, ¿eso implica que las habitaciones existen? Por lo tanto, crearía un enlace a una habitación vacía sin enlaces a ninguna habitación. Probablemente también desee comprobar las nuevas habitaciones vecinas. Si existe, y se abriría a su nueva habitación, agregue una puerta a esa habitación.

   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 / Pared

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.

Paul
fuente
1

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

Una gráfica del laberinto.

A menudo se representan como un conjunto de estados Q , un estado inicial q 0Q y algunas transiciones Δ . Entonces, te sugiero que lo guardes así.

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

Los idiomas más razonables tienen mapas y conjuntos.

kba
fuente
0

Podría considerar una lista vinculada de 4 vías ...

Primero pensé en usar una matriz [X] [X] de objetos Room, pero realmente prefiero evitar eso, ya que se supone que la cosa debe crecer en cualquier dirección, y solo se deben construir habitaciones que se "visiten".

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 hacer un perfil para verificar. Intentar manipular alguna lista o mapa vinculado podría ser realmente peor, y en un nivel constante en lugar de ocasional.

Puede construir solo salas visitadas mediante la implementación de una evaluación diferida. Puede haber un objeto en su lugar que contenga una habitación, y no construye esa habitación hasta que room()se le llame. Luego, solo devuelve el mismo cada vez después de eso. No es difícil de hacer.

Edward extraño
fuente
1
¿Podría ampliar lo que quiere decir con una "lista vinculada de 4 vías"? Lo único que pude encontrar fue un artículo de CodeProject, que se reduce a una lista de adyacencia.
Steven Evers
0

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

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

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

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 vinculada o, de lo contrario, desea administrar sus habitaciones. Para el estilo de matriz (o vectores C ++) usaría ese código y las direcciones contendrían el índice de la habitación a la que se vinculan; para una lista vinculada, puede usar punteros a la siguiente habitación.

Como han dicho otros, si necesita generar dinámicamente nuevas habitaciones cuando las personas ingresan a ellas, también puede hacerlo.

laaph
fuente
0

No intente resolver todos los problemas con una estructura.

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

Una estructura separada puede contener "accesibilidad": qué habitaciones son accesibles desde la habitación 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é.

Evite la optimización temprana. Utilice estructuras realmente simples y algoritmos tontos de fácil comprensión, luego optimice los que se utilizan.

Julian
fuente