Algoritmo de generación de laberintos en el desierto
Hola hamijos! Estoy trabajando en un algoritmo de generación de laberintos en el desierto (sea lo que sea eso) y me lo he pasado tan bien creándolo que no he podido resistirme a compartirlo con vosotros.
Aún está muy verde y se podría seguir puliendo y ampliando hasta la saciedad, pero para mis propósitos malignos me sirve perfectamente. Lo libero al mundo por si a alguien le es útil, os apetece dar ideas para mejorarlo, o para reiros de mí. Al gusto.
Características de un laberinto en el desierto
A nivel de Game Design, el reto de este laberinto no es solo resolverlo (de hecho, es bastante fácil de recorrer del inicio a la salida) si no sobrevivir a él.
Para ello, hay que sobrevivir al cansancio, a la sed y a los enemigos. Moverse una casilla en el laberinto cuesta 1 hora, y eso aumenta la sed y el cansancio (no entraré en detalles de diseño ya que lo que importa aquí es la generación en sí), y derrotar enemigos consume munición y energía/sed. Además, hay un tiempo límite de horas para resolver el laberinto.
Así que este laberinto no solo presenta muros si no una serie de tipos de terreno:
Normal - Arena pura y dura
Dunas - Arena difícil de atravesar (cuesta el doble de horas)
Cactus - Se puede pinchar para obtener algo de agua
Pozo - Inviertiendo unas horas en cavarlo puedes conseguir agua en abundancia
Sombra - Para descansar (no se puede descansar bajo el sol o mueres)
Restos de batalla - Para rapiñar recursos (munición y agua)
Abismo - No transitable (paredes del laberinto)
Patrulla - Enemigo de bajo nivel
Campamento - Enemigo de alto nivel
Código (sintaxis GML)
Al iniciar el nivel lo único que hago es...
//set stage
terrain = p5_generate_terrain(30,30);
A esta función le pasamos el ancho y el alto en casillas que queremos que tenga el laberinto.
Después, esta función se pone manos a la obra para devolvernos un laberinto montado en un array de 2 dimensiones.
///p5_generate_terrain(wide,height);
//generates the desert map
//wide x height
var wide = argument0;
var height = argument1;
var t = 0; //var for holding the entire terrain information
//generation
for(var i = 0;i<height;i++){
for(var j = 0;j<wide;j++){
t[i,j] = p5_get_square();
}
}
//fix terrain depending on setting rules
t = p5_terrain_check(t);
//generated terrain
return t;
Básicamente un bucle anidado que va rellenando las casillas con tipos de terrenos.
Así es como se crea una casilla:
///p5_get_square();
//type of terrain rate
var normal = 11;
var dune = 10;
var cactus = 10;
var water = 6;
var shadow = 14;
var scavenge = 7;
var abyss = 20;
var patrol = 13;
var camp = 13;
//set scale of success 0-15, 15-25, 25-34...
dune+=normal;
cactus+=dune;
water+=cactus;
shadow+=water;
scavenge+=shadow;
abyss+=scavenge;
patrol+=abyss;
camp+=patrol;
var type = 'normal';
//random terrain selection
var square = irandom(camp);//select the higher value for the roll
//normal
if(square<normal){
type = 'normal';
}else
//dune
if(square<dune){
type = 'dune';
}else
//cactus
if(square<cactus){
type = 'cactus';
}else
//water
if(square<water){
type = 'water';
}else
//shadow
if(square<shadow){
type = 'shadow';
}else
//scavenge
if(square<scavenge){
type = 'scavenge';
}else
//abyss
if(square<abyss){
type = 'abyss';
}else
//patrol
if(square<patrol){
type = 'patrol';
}else
//camp
if(square<camp){
type = 'camp';
}
//return terrain type (string)
return type;
Este código lo que hace es tirar un dado y devolver un tipo de terreno al azar, pero la frecuencia en la que aparece cada tipo de casilla está delimitada al principio con ese puñado de variables.
Si os fijáis, no es un sistema porcentual (al menos sobre 100), si no que son valores relativos entre ellos, por eso se suman todos, y se utiliza el valor más alto para determinar "las caras del dado" que usaremos para decidir como rellenamos esa casilla.
Así que si ahora pusiéramos Cactus = 50, aumentaríamos notablemente la cantidad de cactus en este desierto.
Una vez tenemos el terreno "crudo", completamente aleatorio, empezamos a pasarlo por una serie de filtros o reglas que van a asegurarse de que el laberinto esté bien equilibrado y sea resoluble -en la medida de lo posible, este es el punto más mejorable de mi algoritmo-
Sin enrollarme mucho... los pocos arreglos que hago son:
Añadir un punto de inicio y una meta en cuadrantes opuestos en el mapa de forma aleatoria.
Que el punto de inicio esté rodeado de terreno "normal" para no empezar con sorpresas alrededor.
Que la meta sea accesible y no esté rodeada de abismo.
Que los recursos naturales no se aglomeren comprobando que no haya ninguno repetido en una zona de 9 casillas en torno al mismo.
Que no haya más de 50% de "densidad" de abismo por cada fila para no cortar el mapa de una forma intransitable.
Ahora mismo, estoy exportando estos mapas de 2 dimensiones en CSV para comparar y nivelar el game design y conseguir un poco a prueba y error la mejor experiencia posible al jugarlo. Google Drive se encarga de darle color en una hoja de cálculo con estilos para saborear bien el mapita xD
Ejemplos generados con el algoritmo del ritmo
Leyenda:
-sta: inicio
-violeta brillante: meta
-amarillo claro/fuerte: terreno normal/ terreno con dunas
-rojo claro/fuerte: enemigo ligero/enemigo fuerte
-verde: cactus
-azul: pozo de agua
-gris: sombra para descansar
-negro: abismo/pared
-morado oscuro: restos para carroñar
Tocando la proporción de terrenos y especificando el tamaño del laberinto en cuestión de segundos podemos testear muchos laberintos diferentes 
Mapa 30x30 - Difícil
Mapa 30x30 - Difícil (inicio/meta invertidos)
Mapa 25x25 - Fácil
¡Gracias!
Eso es todo, espero no haberos aburrido, y los consejos sobre como mejorarlo serán bienvenidísimos!
