Algoritmo para mapa 2D procesal con caminos conectados

Problema a resolver: genera un mapa de mazmorra 2D aleatorio para un juego basado en fichas donde todas las habitaciones están conectadas.

Estoy buscando mejores soluciones que las que tengo actualmente.

Mi solución actual es que ejecuto dos algoritmos. El primero genera la mazmorra con sus habitaciones. El segundo asegúrese de que todas las habitaciones estén conectadas. Tengo curiosidad por saber qué otras soluciones pueden existir. Más rápido y / o más fácil, etc. La velocidad no es realmente una preocupación, pero si la velocidad se puede obtener sin costo real, bueno, eso es algo bueno. Más importante es que yo, y otros que leen, pueden aprender diferentes formas de abordar y resolver el problema.

A continuación están mi implementación actual. Las habitaciones actualmente no tienen salidas o salidas en ninguna de las 2, 3 o 4 direcciones.

Generando las salas de mazmorras

Configuración: establece la sala actual en la sala superior izquierda.

1. Obtenga un tipo de habitación válido para la habitación (donde el tipo de habitación válido es un tipo sin salidas de la mazmorra y que tiene salidas que coinciden con las salidas de la habitación de arriba y la habitación de la izquierda. Solo necesita marcar arriba y izquierda debido al paso 2 a continuación).
2. Baja la habitación y avanza la coordenada x un paso. Si la coordenada x excede el ancho de la mazmorra, establece la coordenada x en 0 y avanza la coordenada y un paso. Si la coordenada y excede la altura de la mazmorra, hemos terminado.
3. Repita desde el n. ° 1.

Luego verifico para ver si todas las habitaciones están conectadas. Si no están todas conectadas, ejecuto un segundo algoritmo que, de una manera no sexy pero definitivamente lo suficientemente buena en términos de diseño de mazmorras, recorre las habitaciones y las cambia para que todo termine estar conectado

Verificando si todas las habitaciones están conectadas

Configuración: cree un mapa 2D de enteros que representen rutas e inicialice las entradas a un valor "no procesado" (aún no atravesado), -1. Establezca un entero de índice de ruta de inicio que haga un seguimiento de la ruta actual en 1. Establezca la habitación actual en la habitación superior izquierda agregándola a una pila de habitaciones para verificar.

1. Si la pila contiene habitaciones para verificar, al abrirla establezca el índice de ruta de la habitación en el índice de ruta actual. Si la pila no contiene ninguna habitación, aumente el índice de ruta e intente obtener una habitación avanzando columna por columna, fila por fila, hasta obtener una habitación que aún no se haya procesado. Si no se puede encontrar espacio, hemos terminado.
2. Verifique si la habitación tiene una salida a la izquierda. Si ha agregado el espacio izquierdo a la pila si aún no está allí.
3. Repita el paso 2 para las direcciones hacia abajo, hacia la derecha y hacia arriba (ya que estamos usando una pila que significa que las habitaciones están atravesadas en el sentido de las agujas del reloj, comenzando con la dirección hacia arriba).
4. Repita desde el paso 1.
5. Si el recuento de índices de ruta es mayor que uno, hay habitaciones desconectadas.

Si hay habitaciones desconectadas, las agrupo por su índice de ruta, obtengo el índice de la ruta más grande y conecto todas las demás habitaciones a esas habitaciones. Este es un trabajo en progreso, pero mi plan (actual, "brutal") es revisar cada habitación en un grupo de habitaciones (excepto la primera) para ver si hay una ruta horizontal o vertical hacia el grupo de habitaciones biggeset, y si es así, cree una ruta horizontal / vertical inyectando / actualizando las habitaciones intermedias. Enjuague y repita. Feo, sí, pero es algo que no será notable en términos de patrón visual, por lo que funciona en ese sentido.

Uno de los mejores y más usados ​​algoritmos que he visto por ahí es generar mazmorras usando Particionamiento de espacio binario.

La mejor explicación general que he leído es la que se encuentra en The Chronicles of Doryen (adjunta al final para fines de respaldo) porque explica el procedimiento sin entrar en el código, dejando así la implementación al lector.

Se pueden encontrar otros dos tutoriales sobre el mismo tema, con código, en

• Cómo usar árboles BSP para generar mapas de juego
• Generación de mazmorras usando árboles BSP

Construyendo el árbol BSP

Comenzamos con una mazmorra rectangular llena de celdas de pared. Vamos a dividir esta mazmorra de forma recursiva hasta que cada sub-mazmorra tenga aproximadamente el tamaño de una habitación. La división de mazmorras usa esta operación:

• Elija una dirección aleatoria: división horizontal o vertical
• Elija una posición aleatoria (x para vertical, y para horizontal)
• Divide la mazmorra en dos sub-mazmorras

Ahora tenemos dos sub-mazmorras A y B. Podemos aplicar la misma operación a ambas.

Al elegir la posición de división, debemos tener cuidado de no estar demasiado cerca del borde de la mazmorra. Debemos poder colocar una habitación dentro de cada sub-mazmorra generada. Repetimos hasta que las sub-mazmorras más bajas tengan aproximadamente el tamaño de las habitaciones que queremos generar.

Construyendo el calabozo

Ahora creamos una habitación con un tamaño aleatorio en cada hoja del árbol. Por supuesto, la habitación debe estar contenida dentro de la sub-mazmorra correspondiente. Gracias al árbol BSP, no podemos tener dos habitaciones superpuestas.

Para construir corredores, recorremos todas las hojas del árbol, conectando cada hoja con su hermana. Si las dos habitaciones tienen paredes cara a cara, podemos usar un pasillo recto. De lo contrario, debemos usar un corredor en forma de Z

Ahora subimos un nivel en el árbol y repetimos el proceso para las subregiones padre. Ahora, podemos conectar dos subregiones con un enlace, ya sea entre dos habitaciones, o un corredor y una habitación o dos corredores.

Repetimos el proceso hasta que hayamos conectado las dos primeras mazmorras A y B

El método BSP es aparentemente el método más popular para generar mazmorras, pero no es el único.

Para completar, explicaré el generador que funcionó para mí . Tengo que admitir que no recuerdo dónde leí sobre esto, así que solo diré que no es mi invento (un viejo artículo de Jamis Buck me suena muy familiar).

Un laberinto con habitaciones.

La idea básica es que una mazmorra es un laberinto con habitaciones, más o menos. Entonces, el primer paso para este algoritmo es generar un laberinto :

El siguiente paso es hacerlo escaso (eliminar puntos muertos):

El paso número 3 es agregar algunos bucles (hacer que no sea perfecto ), pero omitiré la imagen porque apenas se nota (no necesitaba un laberinto perfecto, así que tomé algunos atajos en el algoritmo de generación de laberinto, por lo que ya tenía bucles en este punto).

Luego, para el paso 4, necesitamos eliminar las células aisladas:

En este punto, hemos terminado con los corredores y estamos listos para agregar habitaciones. Para eso hacemos lo siguiente:

1. Generar un conjunto de habitaciones (ancho y alto)
2. Para cada habitación iteramos a través de todas las ubicaciones posibles y decidimos la mejor ubicación.
   • La mejor ubicación se calcula agregando un peso a las condiciones (como la adyacencia a un corredor).
3. Colocamos las habitaciones.

Hasta ahora, nuestra mazmorra se verá así:

El último paso es agregar decoraciones.

Algunas reflexiones finales

• Usé una versión simplificada del algoritmo de Eller .
• Diferentes algoritmos de laberinto pueden dar como resultado diferentes texturas. Es posible que prefiera otro algoritmo. Por ejemplo, la siguiente imagen muestra diferentes texturas resultantes del "árbol binario" (diagonal diagonal) y una variación de los algoritmos de "división recursiva" (corredores largos):