Cómo codificar su propio generador de mapas de mazmorras de procedimiento utilizando el algoritmo de paseo aleatorio

A medida que la tecnología evoluciona y el contenido del juego se genera más algorítmicamente, no es difícil imaginar la creación de una simulación realista con experiencias únicas para cada jugador.

Los avances tecnológicos, la paciencia y las habilidades refinadas nos llevarán allí, pero el primer paso es comprender la generación de contenido procesal.

Aunque existen muchas soluciones listas para usar para la generación de mapas, este tutorial le enseñará a hacer su propio generador de mapas de mazmorras bidimensional desde cero utilizando JavaScript.

Hay muchos tipos de mapas bidimensionales, y todos tienen las siguientes características:

1. Áreas accesibles e inaccesibles (túneles y paredes).

2. Una ruta conectada que el jugador puede navegar.

El algoritmo en este tutorial proviene del algoritmo de caminata aleatoria, una de las soluciones más simples para la generación de mapas.

Después de hacer un mapa de muros en forma de cuadrícula, este algoritmo comienza desde un lugar aleatorio en el mapa. Sigue haciendo túneles y tomando turnos aleatorios para completar el número deseado de túneles.

Para ver una demostración, abra el proyecto CodePen a continuación, haga clic en el mapa para crear un nuevo mapa y cambie los siguientes valores:

  1. Dimensiones: el ancho y la altura del mapa.
  2. MaxTunnels: la mayor cantidad de giros que puede tomar el algoritmo al hacer el mapa.
  3. MaxLength: la mayor longitud de cada túnel que el algoritmo elegirá antes de hacer un giro horizontal o vertical.

Nota: cuanto más grande sea el maxTurn en comparación con las dimensiones, más denso será el mapa. Cuanto más grande sea el maxLength en comparación con las dimensiones, más "túnel-y" se verá.

A continuación, veamos el algoritmo de generación de mapas para ver cómo:

  1. Hace un mapa bidimensional de paredes
  2. Elige un punto de partida aleatorio en el mapa
  3. Mientras que el número de túneles no es cero
  4. Elige una longitud aleatoria de la longitud máxima permitida
  5. Elige una dirección aleatoria para girar (derecha, izquierda, arriba, abajo)
  6. Dibuja un túnel en esa dirección mientras evita los bordes del mapa.
  7. Disminuye el número de túneles y repite el ciclo while
  8. Devuelve el mapa con los cambios.

Este ciclo continúa hasta que el número de túneles es cero.

El algoritmo en código

Dado que el mapa consta de celdas de túnel y pared, podríamos describirlo como ceros y unos en una matriz bidimensional como la siguiente:

mapa = [[1,1,1,1,0],
       [1,0,0,0,0]
       [1,0,1,1,1]
       [1,0,0,0,1]
       [1,1,1,0,1]]

Como cada celda está en una matriz bidimensional, podemos acceder a su valor conociendo su fila y columna, como map [row] [column].

Antes de escribir el algoritmo, necesita una función auxiliar que tome un carácter y una dimensión como argumentos y devuelva una matriz bidimensional.

createArray (num, dimensiones) {
    var matriz = [];
    para (var i = 0; i 

Para implementar el algoritmo de paseo aleatorio, establezca las dimensiones del mapa (ancho y alto), la variable maxTunnels y la variable maxLength.

createMap () {
 dejar dimensiones = 5,
 maxTunnels = 3,
 maxLength = 3;

Luego, haga una matriz bidimensional utilizando la función auxiliar predefinida (matriz bidimensional de unos).

let map = createArray (1, dimensiones);

Configure una columna aleatoria y una fila aleatoria para crear un punto de partida aleatorio para el primer túnel.

let currentRow = Math.floor (Math.random () * dimensiones),
    currentColumn = Math.floor (Math.random () * dimensiones);

Para evitar la complejidad de los giros diagonales, el algoritmo necesita especificar las direcciones horizontal y vertical. Cada celda se encuentra en una matriz bidimensional y podría identificarse con su fila y columna. Debido a esto, las direcciones podrían definirse como restas y / o adiciones a los números de columna y fila.

Por ejemplo, para ir a una celda alrededor de la celda [2] [2], puede realizar las siguientes operaciones:

  • para subir, resta 1 de su fila [1] [2]
  • para bajar, agregue 1 a su fila [3] [2]
  • para ir a la derecha, agregue 1 a su columna [2] [3]
  • para ir a la izquierda, reste 1 de su columna [2] [1]

El siguiente mapa ilustra estas operaciones:

Mostrando las indicaciones en el mapa.

Ahora, establezca la variable de direcciones en los siguientes valores que el algoritmo elegirá antes de crear cada túnel:

dejar direcciones = [[-1, 0], [1, 0], [0, -1], [0, 1]];

Finalmente, inicie la variable randomDirection para mantener un valor aleatorio de la matriz de direcciones, y establezca la variable lastDirection en una matriz vacía que contendrá el valor anterior de randomDirection.

Nota: la matriz lastDirection está vacía en el primer bucle porque no hay un valor anterior de randomDirection.

deje lastDirection = [],
    randomDirection;

A continuación, asegúrese de que maxTunnel no sea cero y que se hayan recibido las dimensiones y los valores maxLength. Continúa buscando direcciones aleatorias hasta que encuentres una que no sea inversa o idéntica a lastDirection. Este bucle do while ayuda a evitar sobrescribir el túnel recientemente dibujado o dibujar dos túneles uno al lado del otro.

Por ejemplo, si su último giro es [0, 1], el bucle do while evita que la función avance hasta que randomDirection se establezca en un valor que no sea [0, 1] o el opuesto [0, -1].

hacer {
randomDirection = direction [Math.floor (Math.random () * directions.length)];
} while ((randomDirection [0] === -lastDirection [0] &&
          randomDirection [1] === -lastDirection [1]) ||
         (randomDirection [0] === lastDirection [0] &&
          randomDirection [1] === lastDirection [1]));

En el bucle do while, hay dos condiciones principales que se dividen por un || (O) signo. La primera parte de la condición también consta de dos condiciones. El primero verifica si el primer elemento de randomDirection es el reverso del primer elemento de lastDirection. El segundo comprueba si el segundo elemento de randomDirection es el reverso del segundo elemento de lastTurn.

Para ilustrar, si lastDirection es [0,1] y randomDirection es [0, -1], la primera parte de la condición verifica si randomDirection [0] === - lastDirection [0]), lo que equivale a 0 == = - 0, y es cierto.

Luego, comprueba si (randomDirection [1] === - lastDirection [1]) que equivale a (-1 === -1) y también es cierto. Dado que ambas condiciones son verdaderas, el algoritmo vuelve a buscar otra dirección aleatoria.

La segunda parte de la condición verifica si el primer y el segundo valor de ambas matrices son iguales.

Después de elegir randomDirection que satisfaga las condiciones, establezca una variable para elegir aleatoriamente una longitud de maxLength. Establezca la variable tunnelLength en cero para el servidor como un iterador.

let randomLength = Math.ceil (Math.random () * maxLength),
    tunnelLength = 0;

Haga un túnel girando el valor de las celdas de uno a cero mientras el tunnelLength es más pequeño que randomLength. Si dentro del bucle el túnel golpea los bordes del mapa, el bucle debería romperse.

while (tunnelLength 

De lo contrario, establezca la celda actual del mapa en cero usando currentRow y currentColumn. Agregue los valores en la matriz randomDirection configurando currentRow y currentColumn donde deben estar en la próxima iteración del bucle. Ahora, incremente el iterador tunnelLength.

más{
  map [currentRow] [currentColumn] = 0;
  currentRow + = randomDirection [0];
  currentColumn + = randomDirection [1];
  tunnelLength ++;
 }
}

Después de que el bucle haga un túnel o se rompa golpeando un borde del mapa, verifique si el túnel tiene al menos una cuadra de largo. Si es así, establezca lastDirection en randomDirection y disminuya maxTunnels y regrese para hacer otro túnel con otra randomDirection.

if (tunnelLength) {
 lastDirection = randomDirection;
 maxTunnels--;
}

Esta instrucción IF evita el bucle for que golpeó el borde del mapa y no hizo un túnel de al menos una celda para disminuir el maxTunnel y cambiar la última dirección. Cuando eso sucede, el algoritmo busca otra dirección aleatoria para continuar.

Cuando termina de dibujar túneles y maxTunnels es cero, devuelve el mapa resultante con todos sus giros y túneles.

}
 mapa de retorno;
};

Puede ver el algoritmo completo en el siguiente fragmento:

Felicitaciones por leer este tutorial. Ahora está bien equipado para hacer su propio generador de mapas o mejorar esta versión. Vea el proyecto en CodePen y en GitHub como una aplicación de reacción.

No olvides compartir tus proyectos en la sección de comentarios. Si te gustó este proyecto, por favor dame algunas palmadas y sígueme para obtener tutoriales similares.

Un agradecimiento especial a Tom (@ moT01 en Gitter) por escribir este artículo.