Un laberinto puede ser pensado como una cuadrícula de posiciones, entre las cuales puede haber o no paredes. Un objeto que lo represente debería tener para cada posición la información suficiente para saber si un elemento dentro de esa posición (un personaje, una bolita, etc.) puede desplazarse o no hacia las posiciones contiguas.
Por otra parte, diferentes conjuntos de posiciones estarían agrupados por "trayectos", y el laberinto en general sería un superconjunto de trayectos, uno y sólo uno de los cuales tendría una "entrada" y una "salida" exteriores; éste se identificaría con la "solución" del laberinto.
Para construir aleatoriamente ese conjunto de trayectos (que debería incluir la totalidad de las posiciones de la cuadrícula), se podría comenzar por trazar el trayecto principal, o "solución", eligiendo al azar una posición de la columna izquierda (la "entrada"), y asociarla con alguna de las posiciones contiguas al azar; y lo mismo con ésta, y así sucesivamente -siempre y cuando la nueva posición elegida no esté ya ocupada-, hasta que alcance una posición de la columna extrema derecha que conecte aleatoriamente con el exterior.
En esta representación, el número principal de cada posición indica el ID del trayecto al que pertenece (el 1 sería siempre la "solución"), mientras que el subíndice refiere al orden dentro de la secuencia de posiciones del "trayecto".
Una vez que tenemos definido un "trayecto", se escoge una posición al azar dentro de ese "trayecto", y se la toma como primera posición de un nuevo "trayecto".
Aquí, la posición (3, 8) fue elegida para comenzar el "trayecto" 2, y la (8, 10) para comenzar el 3. Nótese que los conjuntos de posiciones que llamamos "trayectos" no son mutuamente excluyentes; y por tanto una posición puede pertenecer a varios. Sin embargo, la condición será que una misma posición sólo puede tener un subíndice mayor a 1 para un solo "trayecto", mientras que para el resto será un punto de partida.
Otra observación es que el "trayecto" 3 comenzó desde una posición del "trayecto" 2, pero lo podría haber hecho desde una del 1; de modo que cada vez que se inicia un trayecto, se debe elegir aleatoriamente el "trayecto" previo dentro del cual se tomará su "salida".
Finalmente, la metodología que propongo -de manera preliminar- para cerrar un trayecto es la condición de que el mismo quede encerrado y no haya posiciones contiguas para elegir. Con esto, se busca que el laberinto quede dominado por "trayectos" largos; haciendo más difícil de identificar la solución.
Como muestra esta imagen, a medida que la construcción avanza, cada vez será más difícil para el motor encontrar aleatoriamente "trayectos" y posiciones desde los cuales comenzar un nuevo "trayecto"; por lo que convendría pensar un mecanismo bajo el cual, en cierto momento, cambie la estrategia, escaneando las posiciones que quedaron sueltas y ligarlas a un "trayecto" posible.
El resultado final podría tener la siguiente forma:
Posible estructura de datos
Para representar la anterior concepción de un laberinto, se me ocurren dos objetos básicos:
Position: contiene los datos de cada casilla particular, y por tanto tendría dos propiedades principales, "path" y "order".
Maze: agrupa y diferencia el conjunto de todas las posiciones contenidas por el laberinto; identificándolas con un par ordenado según su ubicación en la cuadrícula. Su propiedad principal podría ser un diccionario cuyas keys serían tuplas de dos enteros expresando la coordenada de cada posición; mientras que sus values serían objetos Position. Otra posibilidad sería integrar esas posiciones en una matriz bidimensional -o lista de listas- y trabajar sus coordenadas con los índices de esa matriz.
Descripción general
Un laberinto puede ser pensado como una cuadrícula de posiciones, entre las cuales puede haber o no paredes. Un objeto que lo represente debería tener para cada posición la información suficiente para saber si un elemento dentro de esa posición (un personaje, una bolita, etc.) puede desplazarse o no hacia las posiciones contiguas.
Por otra parte, diferentes conjuntos de posiciones estarían agrupados por "trayectos", y el laberinto en general sería un superconjunto de trayectos, uno y sólo uno de los cuales tendría una "entrada" y una "salida" exteriores; éste se identificaría con la "solución" del laberinto. Para construir aleatoriamente ese conjunto de trayectos (que debería incluir la totalidad de las posiciones de la cuadrícula), se podría comenzar por trazar el trayecto principal, o "solución", eligiendo al azar una posición de la columna izquierda (la "entrada"), y asociarla con alguna de las posiciones contiguas al azar; y lo mismo con ésta, y así sucesivamente -siempre y cuando la nueva posición elegida no esté ya ocupada-, hasta que alcance una posición de la columna extrema derecha que conecte aleatoriamente con el exterior.
En esta representación, el número principal de cada posición indica el ID del trayecto al que pertenece (el 1 sería siempre la "solución"), mientras que el subíndice refiere al orden dentro de la secuencia de posiciones del "trayecto". Una vez que tenemos definido un "trayecto", se escoge una posición al azar dentro de ese "trayecto", y se la toma como primera posición de un nuevo "trayecto".
Aquí, la posición (3, 8) fue elegida para comenzar el "trayecto" 2, y la (8, 10) para comenzar el 3. Nótese que los conjuntos de posiciones que llamamos "trayectos" no son mutuamente excluyentes; y por tanto una posición puede pertenecer a varios. Sin embargo, la condición será que una misma posición sólo puede tener un subíndice mayor a 1 para un solo "trayecto", mientras que para el resto será un punto de partida. Otra observación es que el "trayecto" 3 comenzó desde una posición del "trayecto" 2, pero lo podría haber hecho desde una del 1; de modo que cada vez que se inicia un trayecto, se debe elegir aleatoriamente el "trayecto" previo dentro del cual se tomará su "salida". Finalmente, la metodología que propongo -de manera preliminar- para cerrar un trayecto es la condición de que el mismo quede encerrado y no haya posiciones contiguas para elegir. Con esto, se busca que el laberinto quede dominado por "trayectos" largos; haciendo más difícil de identificar la solución.
Como muestra esta imagen, a medida que la construcción avanza, cada vez será más difícil para el motor encontrar aleatoriamente "trayectos" y posiciones desde los cuales comenzar un nuevo "trayecto"; por lo que convendría pensar un mecanismo bajo el cual, en cierto momento, cambie la estrategia, escaneando las posiciones que quedaron sueltas y ligarlas a un "trayecto" posible. El resultado final podría tener la siguiente forma:
Posible estructura de datos
Para representar la anterior concepción de un laberinto, se me ocurren dos objetos básicos: