Old web: Generador de Laberintos en Visual C# 2008

Basado en los códigos de Mike Gold 

https://www.c-sharpcorner.com/article/generating-maze-using-C-Sharp-and-net/

https://www.c-sharpcorner.com/article/eater-game-ii-the-stone-maze/ 

y el algoritmo de backtracking para generar un laberinto https://professor-l.github.io/mazes/ 

Este algoritmo de Python usa el pseudocódigo de una web que ya no existe pero que es la que usé para aprender la técnica https://gist.github.com/fitzterra/9491696 

Primero debía saber cómo "pintar" el laberinto, por ello busqué el evento "Paint" en el formulario (la ventanita) en el código de Mike:

El truco está en los objetos "g" y "e". El evento "Paint" se dispara al crear la ventana o maximizarla. Este evento recibe un objeto "e" del tipo PaintEventArgs con el cual creamos el objeto "g" del tipo "Graphics". Es con este objeto con el que se va a pintar el laberinto.

El código mostrado llama al método "Draw" ("TheMaze" es un objeto de la clase "Maze", creada por Mike e incluida en su código). 

El método "Draw" llama a otro método "Draw" en otra clase creada por Mike llamada "Cell". Nos vamos para allá:

He aquí el código para pintar o dibujar el laberinto. Todo se reduce a dibujar líneas con el método "DrawLine" del objeto "g". 

Yo empecé por dibujar una grilla, con todas las celdas del laberinto. Haría mi laberinto "tumbando paredes" en la grilla.

Como no entendí nada del código de Mike, y como ya estaba perdiendo mucho tiempo intentando entenderlo, supe que debía crear mi propio código. El método "Draw" de la clase "Cell" de Mike me dio otra pista: él declara cuatro paredes, entonces yo también debía crear cuatro paredes (y deduje que serían cuatro paredes por celda). Lo hice mediante esta estructura:

Luego creo una matriz de estructuras tipo "celda". Las paredes vienen determinadas por sus puntos cardinales. En un principio pensé hacerlos de tipo booleanos (true: hay pared, false: no hay pared) pero al seguir programando vi que era necesario declarar un tercer valor para los bordes. Un borde le dice al programa que no debe buscar celdas más allá porque no las hay, además de no tumbar esa pared.

Hice mi generador de laberintos un poco al estilo de Mike: creé una clase aparte llamada "Maze" con un método llamado "DibujarLab" que se llama desde el evento "Paint" del formulario. Y ahí se acaban las similitudes.

Y mi código se puede bajar de aquí :)

La variable "padd" determina el tamaño de las celdas que conforman el laberinto.

Acerca de la variable "PrimeraVez": Si su valor es falso, evitará crear una nueva matriz "celda" al minimizar y maximizar el formulario (en el evento "Load", "PrimeraVez" debe ser true), pero su valor se puede dejar como verdadero si se desea generar un nuevo laberinto cuando se minimiza y maximiza la ventana.

Para generar números aleatorios: Se tiene que usar la clase Random que viene con el .Net. Yo creé un objeto llamado "currentCelda" y es a partir de este objeto que se escoge la celda inicial y la celda siguiente (de las cuatro inicialmente disponibles) por donde se empezará a "tumbar paredes". Si se crea otro objeto aleatorio Random para escoger la celda siguiente (en el método "cogerCelda"), el laberinto no queda bien.

El método "cogerCelda" es donde se escoge la celda siguiente, la pared entre la celda actual y la siguiente es la que se tumbará. En realidad este método no sabe si hay 1,2,3 ó 4 celdas siguientes intactas. Sólo sabe que hay al menos una. "cogerCelda" es como el juego del bingo: no se detendré hasta que haya un ganador, es decir: no saldrá del bucle "while" hasta que el número aleatorio coincida con una celda con todas sus paredes intactas. Según su valor devuelto, se sabrá si se debe tumbar una pared Norte, Sur, Este u Oeste y cuál será la siguiente celda por donde se continuará tumbando paredes.

A la hora de dibujar el laberinto consideré el primer índice de la matriz "celda" como las filas, y el segundo como las columnas. Así a la coordenada "x" le corresponde el segundo índice (ubicación horizontal), y a la coordenada "y" el primer índice (ubicación vertical). El método DrawLine necesita estas coordenadas para determinar los puntos inicial y final de las líneas que dibujará. Es fácil confundirse. A mí me pasó.

Ahora un pantallazo de cómo queda el laberinto:

Bastante bonito, y fácil una vez entendido cómo funciona el algoritmo para generarlo. Así, que...

¿Por qué no hacerlo triangular?

Esta vez el número de columnas va aumentado a medida que el laberinto "crece". Por ello, en lugar de crear una matriz cuadrada, declaré lo que en inglés se llama "jagged array". Se trata de una matriz que puede tener distinto número de columnas por cada fila. La cantidad de columnas por fila está dada por esta fórmula, muy fácil de deducir en realidad:

n° de columnas = (2*n° de filas) + 1

El compilador prioriza multiplicaciones y divisiones por encima de sumas y restas, por lo que los paréntesis pueden omitirse. 

A la hora de generar la matriz "celda" sólo se tienen tres paredes por celda, por ello esta vez la estructura "celda" sólo tiene tres "puntos cardinales": L1, L2 y piso (lado derecho, lado izquierdo y piso). Dependiendo de su ubicación, las celdas podían tener el piso arriba o abajo, mientras que L1 y L2 no cambian su ubicación. 

Lo más difícil fue dibujar las celdas en el lugar que les corresponde pues el laberinto es triangular, mientras que el sistema de coordenadas en la ventana es rectangular. Para facilitarme las cosas, primero dibujé las celdas en un sentido, y luego las que están en el otro, así al final sólo se debe juntar todo (por ello hay dos bucles dentro del bucle principal en el método "DibujarLab"):

Tomé como origen de coordenadas el vértice superior del triángulo, ubicado en la coordenada=(ancho aproximado de la ventana /2, 0). Éste se va dibujando desde arriba y desde la izquierda. Ya con las celdas en su lugar y la orientación correcta (todos los índices empiezan desde cero) se puede aplicar el algoritmo para generar el laberinto. La base o "piso" de cada triangulito mide 2*padd (al igual que en el laberinto rectangular, la variable "padd" determina el tamaño de las celdas que conforman el laberinto).

El resultado es éste:

El código puede bajarse de aquí.

Por alguna razón siempre me sale que la última fila tiene una pared recta. No sé porqué, pero no importa, porque si se hace que el bucle principal (al que le corresponde la variable "i") en el método DibujarLab vaya de 0 hasta menos de "pisos-1" en lugar de "pisos":

Queda así:

"pisos" es la variable que determina el número máximo de filas que tendrá la matriz que genera el laberinto triangular.