Algoritmo para crear laberintos

[carles]

Hola gente, hacia bastante que no pasaba por aquí, pero PiXeL me mantiene al día de todo.


Hoy os traigo un algoritmo para que podáis crear laberintos. Me he basado en el código de esta página: http://mazesmith.sourceforge.net

Code Select Expand



Program maze;


import "mod_draw";
import "mod_key";
import "mod_map";
import "mod_math";
import "mod_proc";
import "mod_rand";
import "mod_screen";
import "mod_string";
import "mod_time";
import "mod_video";


Global
graficos[4]; //ids de los gráfico
ancho=7; //anchura del gráfico


ancho_pantalla=1024; //1024, 1280, 1920
alto_pantalla=768; //768, 720, 1080
bpp=16; //bits
end


BEGIN

set_fps(40,10);
set_mode(ancho_pantalla,alto_pantalla,bpp);
rand_seed(time());
crea_graficos();

CreateMaze(100,100,0,0,0);

loop
if(key(_esc)) exit(); end
frame;
end
END


//-------------------------------------
//Función que crea los tiles
//-------------------------------------
function crea_graficos();


begin
drawing_color(rgb(255,255,255));

//arriba
graficos[0]=new_map(ancho,ancho,bpp);
drawing_map(0,graficos[0]);
draw_line(0,0,ancho-1,0);

//derecha
graficos[1]=new_map(ancho,ancho,bpp);
drawing_map(0,graficos[1]);
draw_line(ancho-1,0,ancho-1,ancho-1);

//abajo
graficos[2]=new_map(ancho,ancho,bpp);
drawing_map(0,graficos[2]);
draw_line(0,ancho-1,ancho-1,ancho-1);

//izquierda
graficos[3]=new_map(ancho,ancho,bpp);
drawing_map(0,graficos[3]);
draw_line(0,0,0,ancho-1);

end


//-------------------------------------
//Función que crea un laberinto
//-------------------------------------
//rows: filas del laberinto, entero
//cols: columnas del laberinto, entero
//longitude: tendencia de los pasillos a ser rectos, %
//braid: porcentaje de conecxiones multiples (bucles), %
//bias: tendencia de los pasillos a ser verticales u horizntales, -4(vertical), -3, -2, -1, 0, 1, 2, 3, 4(horizontal)
//
//
//
//-------------------------------------
process CreateMaze(rows,cols,longitude,braid,bias);


PRIVATE
string biasA; //variable auxiliar
cellStack[10000]; //lista de celdas por las que va pasando
totalCells; //numero total de celdas (rows*cols)
string temp; //variable auxiliar, posibles direciones a las que se puede mover
a; //variable auxiliar
b; //variable auxiliar
currentCell; //celda actual
string dir; //dirección hacia donde se mueve el camino
dirA; //variable auxiliar
visited; //numero de celdas visitadas
borders[10000]; //cuenta los bordes de cada celda para poder detectar los finales de camino
marked[10000]; //marcas las celdas: 0 aun no se ha visitado, 1 celda visitada y 9 celda no disponible

top[10000]; //indica si la celda tiene borde superior
right[10000]; //indica si la celda tiene borde oriental
bottom[10000]; //indica si la celda tiene borde inferior
left[10000]; //indica si la celda tiene borde occidental

END


BEGIN
totalCells = (rows*cols);

//construimos paredes, ya las derrumbaremos luego
for(a=0;a<totalCells;a++)
top[a] = 1;
right[a]=1;
bottom[a]=1;
left[a]=1;
borders[a] = 4;
end


//inicio en celda aleatoria
currentCell = rand(0,totalCells-1);
visited=1;

marked[currentCell] = 1; //marcamos la celda de inicio como visitada


//-----------------------------------------
//aplicamos algoritmos


loop //mientras el recorrido no sea 0, no tiene sentido mejor poner un loop

temp = ""; //limpiamos temp
biasA = ""; //limpiamos biasA
dirA = 0;


//comprobamos hacia donde nos podemos mover

a = (currentCell-cols);//celda de arriba
if(marked[a]!=1 and a>=0)//comprueba si ha sido visitada y si no es la superior
temp+="1";
if(dir=="1") dirA = 1; end
if(bias<0 and rand(1,4)<(-1*bias)) biasA += "1"; end
end


a = (currentCell+1);//celda de la derecha
if(marked[a]!=1 and abs(currentCell/cols)==abs(a/cols) and a<totalCells)//comprueba si no es un lateral
temp+="2";
if(dir=="2") dirA = 1; end
if(bias>0 and rand(1,4)<bias) biasA += "2"; end
end


a = (currentCell+cols);//celda de abajo
if(marked[a]!=1 and a<totalCells)//comprueba si ha sido visitada y si no es la superior
temp+="3";
if(dir=="3") dirA = 1; end
if(bias<0 and rand(1,4)<(-1*bias)) biasA += "3"; end
end


a = (currentCell-1);//celda de la izquierda
if(marked[a]!=1 and abs(currentCell/cols)==abs(a/cols) and a>=0)//comprueba si no es un lateral
temp+="4";
if(dir=="4") dirA = 1; end
if(bias>0 and rand(1,4)<bias) biasA += "4"; end
end


if(temp!="") //si puede moverse
if(bias!=0 and biasA!="") //aplicamos bias
dir = biasA[rand(0,len(biasA)-1)] + "";
else
if(dirA==1 and longitude!=0) //aplicamos longitude
if(rand(1,100)>(longitude))
dir = temp[rand(0,len(temp)-1)] + "";
end
else //sino tiene bias ni longitude, la dirección es aleatoria
dir = temp[rand(0,len(temp)-1)] + "";
end
end


cellStack[b] = currentCell; //la añadimos a la lista
b++;
borders[currentCell]--;

switch (dir)
case "1":
top[currentCell] = 0;
currentCell = (currentCell-cols);
bottom[currentCell] = 0;
end
case "2":
right[currentCell] = 0;
currentCell++;
left[currentCell] = 0;
end
case "3":
bottom[currentCell] = 0;
currentCell = (currentCell+cols);
top[currentCell] = 0;
end
case "4":
left[currentCell] = 0;
currentCell--;
right[currentCell] = 0;
end
end

borders[currentCell]--; //descontamos una pared
marked[currentCell] = 1; //la marcamos como visitada
visited++;

else //si no puede moverse

//volvemos atras hasta que pueda
b--;
currentCell = cellStack[b];
end

//Si el número de celdas visitadas es igual al total finaliza el algoritmo
if(visited==totalCells) break; end


end
//Fin de aplicar algoritmos


//-----------------------------------------
//aplicamos la conexión multiple
//-----------------------------------------
if(braid>0)
for(a=0,currentCell=0; a<rows; a++)
for(b=0; b<cols; b++,currentCell++)
temp = "";
//comprobamos si es un final de linea
if(borders[currentCell]==3 and rand(0,99)<(braid))
//comprobamos donde podemos quitar una pared
if(b!=0 and left[currentCell]!=0) temp+="1"; end //izquierda
if(a!=0 and top[currentCell]!=0) temp+="2"; end //arriba
if(b!=cols-1 and right[currentCell]!=0) temp+="3"; end //derecha
if(a!=rows-1 and bottom[currentCell]!=0) temp+="4"; end //abajo
dir = temp[rand(0,len(temp)-1)] + "";

switch(dir)
case "1": //izquierda
left[currentCell] = 0;
right[currentCell-1] = 0;
end
case "2": //arriba
top[currentCell] = 0;
bottom[currentCell-cols] = 0;
end
case "3": //derecha
right[currentCell] = 0;
left[currentCell+1] = 0;
end
case "4": //abajo
bottom[currentCell] = 0;
top[currentCell+cols] = 0;
end
end
end
end
end
end
//-----------------------------------------
//Dibujado del laberinto
//-----------------------------------------
graph=new_map(cols*ancho,rows*ancho,bpp);


currentCell=0;

x=ancho_pantalla/2;
y=alto_pantalla/2;

for(b=0;b<rows;b++)
for(a=0;a<cols;a++)
if(top[currentCell]==1) map_put(file,graph,graficos[0],a*ancho+(ancho/2),b*ancho+(ancho/2)); end
if(right[currentCell]==1) map_put(file,graph,graficos[1],a*ancho+(ancho/2),b*ancho+(ancho/2)); end
if(bottom[currentCell]==1) map_put(file,graph,graficos[2],a*ancho+(ancho/2),b*ancho+(ancho/2)); end
if(left[currentCell]==1) map_put(file,graph,graficos[3],a*ancho+(ancho/2),b*ancho+(ancho/2)); end
currentCell++;
end
frame; //para que quede bonito
end
//return(graph);

loop
frame;
end

END


[panreyes]

Qué mamón xD


Pues que sepas que ya lo he integrado en el minijuego... :D

[Outlaw]

Gracias Carles! Es un excelente aporte! K++

[osk]

Brutal!!

[Drumpi]

¿Qué tipo de laberintos? Con paredes de 1 pixel de ancho o con paredes de un tile de ancho?
Yo intenté crear uno hace muchísimo tiempo, con paredes de 1 pixel de ancho, pero no sabía cómo evitar que el camino se cerrase sobre sí mismo, y lo abandoné. Lo mismo puedo usar este, pero claro, no sé si usarlo en Bennu o en Fenix, porque necesito una librería cuyo port tiene un bug grave que aun no se ha solucionado.

[carles]

¿Qué tipo de laberintos?

Depende de cómo lo configures, tienes 5 paramentros:
Los 2 primeros son la anchura y la altura.
el 3º es la tendecia de los caminos a seguir rectos, el valor de 0 a 100.
el 4º es el % de bucles que hay, con un 100% no hay finales de camino y el laberinto suele tener más de una solución.
y el 5º es la tendencia de los caminos a ser verticales(-4) o horizontales(4).

Con paredes de 1 pixel de ancho o con paredes de un tile de ancho?

Con paredes de 2 pixeles. El algoritmo guarda las paredes que tiene cada celda lo que provoca que la información este duplicada en celdas adyacentes.
no costaría mucho hacer el cambio a tiles, lo difícil era hacer el algoritmo.
puedes hacerlo al final usando los valores de las variables top[], left[], bottom[] y right[]  o modificar el algoritmo para que lo haga directamente: el mapa será como mínimo el doble de ancho y alto, y el movimiento tendrá que ser de 2 en 2 casillas.

Yo intenté crear uno hace muchísimo tiempo, con paredes de 1 pixel de ancho, pero no sabía cómo evitar que el camino se cerrase sobre sí mismo, y lo abandoné.

El algoritmo que he usado es el Growing tree, http://www.astrolog.org/labyrnth/algrithm.htm lo que hace es:
1-empezar en un lugar al azar,
2-ir de forma aleatoria derribando paredes,
3-va guardando el camino recorrido,
4-cuando se atasca retrocede hasta donde puede continuar,
5-volver al paso 2 hasta haber recorrido todo el espacio

[Drumpi]

Muchas gracias.
Sí, yo también lo intenté con 2 pixels de ancho, duplicando las paredes por cada casilla, así que eso no es problema.
Como dices, lo complicado es generar el laberinto, en concreto, el punto 4 de tu lista, porque no sabes cuánto debe retroceder. En mi algoritmo, incrementaba un paso por cada vez que se cerraba el camino, y lo ponía a cero si superaba el número de pasos los tiles nuevos sin que se cerrase, pero algo salía mal y claro, no es fácil debugear este tipo de algoritmos, con tanto random en medio :D