Aquí os traigo mi primer tutorial en C++, el generador de laberintos (Maze Generator).

La idea de este primer tutorial es construir un laberinto aleatorio, con forma cuadrada o rectangular, sin entrada ni salida definida, pero en el que se puedan recorrer la totalidad de sus casillas.



Lo primero de todo, podéis encontrar el código en el siguiente link, descargarlo echarle un vistazo, jugar con él y modificarlo libremente: github.com - Maze Generator

Para simplificar la generación del laberinto utilizaremos "std::vector", un array que puede cambiar su tamaño (aquí lo hará cada vez que lancemos el programa).
¿Por qué? Pues porque con una fórmula muy sencilla podemos pasar de columna y fila al índice que ocupa esa casilla en el array.

¿Y cuál es esa fórmula tan sencilla?
índice = columna + fila * nº de columnas

Por si acaso surge alguna duda, primero se hace la multiplicación y luego se suma la columna.
Vamos a poner un ejemplo, para un laberinto de 2 x 2, 2 filas y 2 columnas, tendríamos:
col fila nºcol índice
0  0  2  0
1  0  2  1
0  1  2  2
1  1  2  3

¿Veis? ¡Está chupado! Seguimos.

Entonces vamos a tener un array pero, ¿de qué? ¿Enteros? ¿Booleanos? ¿O necesitamos algo más complejo?
Efectivamente necesitamos definir la clase "Tile" (casilla), que por supuesto tendrá dos variables que indicarán la columna y la fila donde se encuentra.
También necesitaremos saber si ha sido visitada o no por nuestro algoritmo, para evitar que se utilice en más de una ocasión.

Hasta aquí todo es sencillo, pero ahora viene otra idea feliz con su respectiva pregunta.
Los muros del laberinto, ¿son casillas? Podrían serlo, pero en este tutorial no.
En este tutorial van a ser un array de cuatro booleanos que indicarán si cada casilla tiene muro (true) o no tiene muro (false) en cada una de las cuatro posiciones/direcciones: arriba, derecha, abajo e izquierda.

Si los muros fueran casillas habría que hacer ciertas cosas ligeramente diferente, así que de momento nos olvidamos.

La inicialización del laberinto es sencilla, todas las casillas aún no han sido visitadas salvo la primera casilla (0,0). Además todas las casillas tendrán todos sus muros levantados y la posición (columna, fila) que ocupa cada una de ellas.

Y este sería el grueso del algoritmo:
void Maze::generateMaze() {
 int currentIndex = 0;
 do {
  int nextIndex = checkNeighbours(grid[currentIndex]);
  if (nextIndex > -1) {
   removeWalls(grid[currentIndex], grid[nextIndex]);
   visited.push(currentIndex);
   grid[nextIndex].setVisited(true);
   currentIndex = nextIndex;
  } else {
   currentIndex = visited.top();
   visited.pop();
  }
 } while (!visited.empty());
}

Paso a explicarlo.
Mientras haya casillas disponibles en el "stack" (pila) de casillas visitadas que tienen "vecinos" que aún no han sido visitados, vamos a ir realizando una serie de acciones.
Primero buscaremos un "vecino" aleatorio (checkNeighbours <- quizás no es el nombre más apropiado) que no haya sido visitado con respecto a la casilla en la que nos encontremos en este momento (currentIndex).

Si existe un vecino que no haya sido visitado, entonces hay que quitar los muros, sí, en plural, los muros, el de la casilla actual (currentIndex) y la casilla donde nos vamos a mover (nextIndex).
Ejemplo: si nos vamos a mover a la casilla que se encuentra a la derecha lo que tendremos que hacer es quitar el muro derecho de la casilla actual y el muro izquierdo de la siguiente casilla. Esto se hace en "removeWalls".
Lo siguiente es añadir la casilla actual a la pila de casillas visitadas pero que tienen vecinos que aún no han sido visitados.
Ponemos la casilla siguiente como visitada y decimos que la casilla actual ahora es la casilla siguiente.

La otra opción, si no existe un vecino que no haya sido visitado, descartamos la casilla actual sobrescribiéndola con la última casilla de la pila.

Un par de apuntes más:

• checkNeighbours

En esta función hay algo importante y es que el laberinto tiene su origen en la esquina arriba izquierda para que a la hora de mostrarlo por pantalla se corresponda con la librería "CImg" y la forma que tiene de mostrar imágenes.


• removeWalls

En esta función también se tiene en cuenta lo mismo que en la anterior, el origen del laberinto.
Se restan las columnas de la casilla actual y la nueva casilla, si la resta da -1 la nueva casilla está a la derecha, si da 1 está a la izquierda.
También se restan las filas, si la resta da -1 la nueva casilla está debajo, si da 1 está encima.

Y ahora sí, eso sería todo, gl & hf.