2025-02-23
Crear un laberinto en C++
Hará tiempo, pensé en desarrollar un juego de laberintos estilo el Maze craze de la Atari 2600, y aunque no llegué a desarrollarlo si investigué como realizar un laberinto programado en C++.
Con motivo de los tutoriales anteriores busqué la información que creía perdida y me encontré con el código fuente que generaba el algoritmo en modo texto.
Código fuente
El programa consiste un array de dos dimensiones que conforma el laberinto, el cual inicialmente tiene todas sus celdas en valor 1. Esto significa que hay "pared" en ese lugar.
La idea es ir "cavando" en una dirección aleatoria comprobando si la posición seguida a la siguiente es tierra, eliminando la tierra que hay entre las dos.
Las direcciones en la que nos podemos mover son: arriba, abajo, izquierda o derecha, que se numeran como 0,2,4 y 6, ayudándonos de la función vecino que te devuelve la posición de este en el array con respecto a nuestra pieza.
Así que hacemos una búsqueda en profundidad, leyendo los vecinos/vecinos de una posición, guardándolas en un array. Elegimos entonces un vecino al azar y comprobamos si lo que hay entre ellos es tierra. Ahora continuamos cavando desde ese vecino. Cuando una pieza no encuentra vecinos para poder cavar, vuelve a la anterior y sigue eligiendo a otro vecino al azar. Así hasta que ya no queda nada más que cavar.
#include <stdio.h> #include <stdlib.h> #include <conio.h> #include <windows.h> #include "lista.h" // Datos del tablero. int *tablero; int w; int h; // Crea el tablero, recuerda que ha de tener un tamaño impar. creatablero(int x, int y) { randomize(); w = x%2==0 ? w=x+1 : w=x; h = y%2==0 ? h=y+1 : h=y; tablero = new int [w*h]; if (!tablero) return 0; for (int i=0; i<w*h; i++) tablero[i]=1; return 1; } // Muestra el tablero en pantalla. void vertablero() { int piezas[] = { ' ', 0xb0, 0xc9, 0xbb, 0xc8, 0xbc, 0xce, 0xba, 0xcd, 0xcc, 0xb9, 0xca, 0xcb, 0xba, 0xcd, 0xba, 0xcd }; clrscr(); for (int f=0; f<h; f++) { for (int c=0; c<w; c++) printf("%c", piezas [ tablero[f*w+c] ]); printf("\n"); } } // dado un valor de celda (z) devolvera su fila y su columna (f)(c) // si el valor de celda es mayor que el tamaño del tablero o es menor // que 0, devolverá valores de -1 para la fila y columna void celda(int z, int &f, int &c) { if ( z>w*h || z<0 ) { f = -1; c = -1; } else { f = z / w; c = z % w; } }; // Dado un valor de fila y columna (f)(c) devolvera su valor de celda int celda(int f, int c) { return (f*w)+c; } // Dada una celda z, devolverá la posición en el trablero de su vecino // indicado como un valor del 0 al 7. // // 7 0 1 // 6 Z 2 // 5 4 3 // // Si el valor esta fuera de los limites del mazo devolverá -1. int vecino(int v, int z) { int f, c; celda(z, f, c); // Obtenemos la fila y la columna de dicha celda. switch ( v ) { case 0: if ( f-1>=0 ) f--; break; case 1: if ( f-1>=0 && c+1<w) { f--; c++; } break; case 2: if ( c+1<w ) c++; break; case 3: if ( f+1<h && c+1<w ) { f++; c++; } break; case 4: if ( f+1<h ) f++; break; case 5: if ( f+1<h && c-1>=0 ) { f++; c--; } break; case 6: if ( c-1>=0 ) c--; break; case 7: if ( f-1>=0 && c-1>=0) { f--; c--; } break; default: return -1; }; if (celda(f,c)==z) return -1; return celda(f,c); } // Dada dos celdas (z) y (c) devolverá la posición del vecino que // existe entre ellas o -1 si no existe tal vecino int entre(int z, int c) { if ( vecino(0, vecino(0, z))==c ) return vecino(0,z); else if ( vecino(2, vecino(2, z))==c ) return vecino(2,z); else if ( vecino(4, vecino(4, z))==c ) return vecino(4,z); else if ( vecino(6, vecino(6, z))==c ) return vecino(6,z); else return -1; } // Crea el mazo. Recorre recursivamente el tablero buscando los vecinos // de cada posición y "cavando" entre ellos si hay una pared. void dfs(int z) { lista<int> vecinos; int i, v; tablero[z]=0; // lo marcamos como visitado, eliminamos el valor // Obtengo las posiciones de los vecinos segundos de dicha posición. for(i=0; i<7; i+=2 ) { v = vecino(i, vecino(i,z)) ; // Solo añadimos los vecinos válidos. if ( v!=-1 ) vecinos.anade(v); } while ( !vecinos.vacia() ) { // Cogemos un vecino de la lista y lo borramos. i = rand()%vecinos.total(); v = vecinos.datoen(i); vecinos.borra(i); // Si ese vecino de vecino es una pared eliminamos la // pared entre la celda actual y el vecino-vecino if ( tablero[v]==1 ) { tablero[entre(v,z)]=0; dfs(v); } } } // Esta función es para hacer que luzca más bonito el puzzle aunque no // necesaria. void traduce() { int z, t; int v0, v2, v4, v6; t = w*h; for (z=0; z<t; z++) { if ( tablero[z]!=0 ) { // Hallo los vecinos v0 = vecino(0,z)>=0 ? tablero[ vecino(0,z) ] : -1; v2 = vecino(2,z)>=0 ? tablero[ vecino(2,z) ] : -1; v4 = vecino(4,z)>=0 ? tablero[ vecino(4,z) ] : -1; v6 = vecino(6,z)>=0 ? tablero[ vecino(6,z) ] : -1; // y ahora compruebo que valor de casilla le corresponde */ if ( v0>0 && v2>0 && v4>0 && v6>0 ) tablero[z]=6; else if ( v0>0 && v2>0 && v4>0 ) tablero[z]=9; else if ( v0>0 && v4>0 && v6>0 ) tablero[z]=10; else if ( v0>0 && v2>0 && v6>0 ) tablero[z]=11; else if ( v2>0 && v4>0 && v6>0 ) tablero[z]=12; else if ( v2>0 && v4>0 ) tablero[z]=2; else if ( v4>0 && v6>0 ) tablero[z]=3; else if ( v0>0 && v2>0 ) tablero[z]=4; else if ( v0>0 && v6>0 ) tablero[z]=5; else if ( v0>0 && v4>0 ) tablero[z]=7; else if ( v2>0 && v6>0 ) tablero[z]=8; else if ( v4>0 ) tablero[z]=13; else if ( v2>0 ) tablero[z]=14; else if ( v0>0 ) tablero[z]=15; else if ( v6>0 ) tablero[z]=16; else tablero[z]=1; } } } void main() { randomize(); creatablero(rand()%80,rand()%25); vertablero(); printf("Pulse Enter para continuar...\n"); getchar(); dfs(celda(1,1)); vertablero(); printf("Pulse Enter para continuar...\n"); getchar(); traduce(); vertablero(); printf("Pulse Enter para continuar...\n"); getchar(); } )
El programa usa la librería lista.h que sirve para crear una lista de vecinos. La librería está en las referencias.
Aprovenchando los tutoriales anteriores y para hacer memoria también he creado el programa usando win32 y GDI.