Estructura de datos y generación de laberinto - Segunda Propuesta

[sebadgc]

Vamos a pensar la forma de generar un laberinto a la inversa, en vez de crear n caminos interconectados entre sí que pueden tener un destino o no, vamos a partir de una grilla de MxN que esté completamente cubierta de cuadrículas y el proceso es ir removiendo "paredes".

(Como nota al pie, y lo cuento porque tengo un background de química, lo mismo sucede con redes cristalinas, piezoeléctricos o materiales de ese estilo donde uno puede pensar al electrón moviéndose dentro de una red, pero también los mismos resultados se obtienen, y otros más también, pensando a un "hueco con carga positiva" que se desplaza en dirección opuesta).

Se me ocurren necesarios definir algunos conceptos:

1. Dos conjuntos: INICIAL y VISITADOS. En primera instancia, todos los puntos del laberinto pertenecen al conjunto INICIAL, que refiere a la totalidad de las paredes graficadas. Se puede pensar como si se viera al laberinto desde arriba y todo estuviera lleno de paredes. El conjunto visitados refiere a los casilleros que ya han sido considerados en la formación del laberinto y no volverán a ser tomados en cuenta.
2. Un tercer conjunto de FRONTERA que refiere a los casilleros de la red vecinos a casilleros visitados.

Supongamos un laberinto de 6x6, se inicia con todos los casilleros dentro de INICIAL, en esa grilla, se elige un casillero al azar como inicio:

Una vez que se tiene el casillero, se elimina del conjunto INICIAL (I) y se pasa al conjunto VISITADOS (V), de esta manera surgen elementos del tercer grupo FRONTERA (F), que son aquellos adyacentes al casillero inicial:

De este grupo se elige uno al azar y se lo conecta con el casillero anterior eliminando la pared que los separaba. Al mismo tiempo se lo mueve al conjunto de casilleros visitados, lo que esto genera nuevas fronteras:

Este proceso se realiza consecutivamente (y concomitantemente) hasta convertir a todas los elementos de la matriz en visitados:

Una vez que queda armado el laberinto se definen 2 posiciones (que se pueden tomar de extremos opuestos o siguiendo cualquier criterio arbitrario que uno quiera) y se los abre para indicar el principio y el fin.

Consideraciones:

• Se me ocurre que para esto necesitamos definir y trabajar con los vértices del laberinto a generar, para tener un control sobre las paredes que hay entre cada casillero:

• Para más orden y definir conceptos se puede definir cada escalón iterativo como:

Estado inicial: I = NxM - F = {} - V = {}

1. Se inicia el sistema tomando un elemento del conjunto I y llevándolo a V.
2. Se actualiza el conjunto F con todos los elementos de I que bordeen a V.
3. Se toma un elemento de F, f, al azar y se buscan todos los elementos de V conectados. se elige uno al azar, v, y se divide la pared entre ambos. (También se podría hacer el proceso análogo tomando un elemento de V al azar, pero no esta garantizado que todo v posea un f lindante, mientras que si necesariamente todo f tendrá un v, por ser condición necesaria para pertenecer a F. En ese caso, si v no tiene f se tomaría otro v, pero es agregar condicionales innecesariamente en mi opinión).
4. Se pasa el elemento f a V.

La condición de salida de este loop seria que la dimensión de V sea NxM, o que todos los casilleros se encuentren visitados.

Yendo a una idea más computacional quedaría algo del estilo: i = get_random_square(I) move_to_V(i)

while( dim(V) < NxM):       F.update()       f = get_random_square(F)       sub_V = get_neighbour_squares(f)       v = get_random_square(sub_V)       split_walls(f,v)       move_to_V(f)

[OldOwl83]

Buenísima la idea, Sebas. Me encanta y me parece super simplificadora la idea de trabajar sobre la base de tres conjuntos entre los cuales se desplazan las casillas del tablero inicial. Sin embargo, levanto un warning sobre la última consideración, porque me parece que trae aparejado un desafío importante, que justamente tiene que ver con la estructura de datos con la que representaríamos este concepto. Lo que yo veo es que no alcanza con mover las casillas de un conjunto a otro, sino que además habría que conservar cierta "memoria" respecto de qué casilleros fueron "fronteras" cuáles, para después poder establecer las paredes. Por ejemplo, pienso en la transición entre el esquema 9 y el 10. Ahí, la casilla (3, 4) pasa al conjunto de los visitados, pero eso no me permite determinar si la pared la comparte con la casilla (3, 5) o (4, 4). Es decir, hay que llevar un cierto registro de la secuencia como avanza la limpieza de paredes. Este problema es el que yo quise resolver con el concepto de "trayecto". Sin embargo, me parece que tu idea tiene mucho potencial y te animo a seguir desarrollándola.

¡Vamos equipo! :heart:

[sebadgc]

Gracias por la devolución, Mauro. Me parece que va por ese lado, independientemente de la resolución, es un plan más fácil de agarrar con las manos en general. Después probaremos otras propuestas que puedan ser más performantes o que devuelvan distintos resultados de laberintos. También me da la sensación, al menos viendo los dibujos, que van a quedar caminos largos sin muchas vueltas.

Ahora edito la propuesta para incluir los puntos que tocaste en tu observación.

[sebadgc]

Mauro, ahí completé un poco la idea con el proceso un poco más explicado. En este caso, el proceso 2 es el que tiene en cuenta el concepto que vos definís de "memoria". Al tomar un f se busca un v conectado y en ese mismo momento se divide la pared que los une. Intuyo que este puede ser el proceso limitante, entender bien qué constituye una pared, como "eliminarla" y como trasladar eso gráficamente a remover la linea entre esos puntos.

[OldOwl83]

Está clarísima la solución y me parece que el paso 3 conserva el espíritu de simpleza del resto del planteo. ¡Me parece muy prometedora!

Sin embargo, recordemos que la idea de este proyecto era ejercitarse en POO; por eso insisto en que faltaría definir la estructura de datos con que se va a representar este objeto (o sea, en definitiva, el conjunto de sus atributos, que deberían reflejar el estatus de cada posición, las relaciones entre ellas, la posibilidad de pasar de una a otra, etc.). Aclaro esto porque todavía veo al pseudo-código que planteás al final muy apegado al paradigma imperativo.

Capaz que no hace falta plantear la composición del objeto acá, sino desarrollarla directamente en el código (yo hice un pequeño esbozo en la issue, que después me dio fiaca seguir, y avancé desde el código). Pero es en este punto donde tuve las dificultades; por eso lo planteo.