A LGORITMOS DE G ENERACIÓN P ROCEDIMENTAL I MPLEMENTADOS
5.2 Generación del Contenido de la Mazmorra
A LGORITMOS DE G ENERACIÓN P ROCEDIMENTAL I MPLEMENTADOS
En el videojuego se han implementado una serie de algoritmos deGPC. En este capítulo se explicarán los diferentes algoritmos que se han utilizado en el juego.
5.1 Generación de la Estructura de la Mazmorra
Las mazmorras constan de una serie de habitaciones. Como en la pantalla solo puede haber una habitación a la vez, se puede crear la mazmorra tomando las habitaciones y sus conexiones como un grafo, sin tener en cuenta el tamaño de las habitaciones.
Para crear el contenido de las habitaciones es necesario tener la mazmorra total-mente construida, por lo que hay que dividir la generación de la mazmorra en dos partes: generación de la estructura y generación del contenido.
La generación de la estructura de la mazmorra únicamente se encarga de delimitar el número de habitaciones, sus posiciones y las habitaciones a las que están conectadas.
Veralgo.(5.1) en la página 33.
Al final del algoritmo se aprovecha para colocar puertas y paredes, puesto que son necesarias para ciertos algoritmos posteriores.
Una vez generada la estructura ya es posible generar el contenido.
5.2 Generación del Contenido de la Mazmorra
Una parte de la generación del contenido de la mazmorra es generar llaves y cerrar puertas con candados. Para que funcione correctamente es necesario tener en cuenta lo siguiente:
• Al menos una llave ha de ser accesible en cualquier momento.
• La última llave que se consiga ha de ser la llave de la habitación final.
5. ALGORITMOS DEGENERACIÓNPROCEDIMENTALIMPLEMENTADOS
Figura 5.1: Ejemplo de una mazmorra generada. Rojo: habitaciones normales. Blanco:
habitación inicial. Negro: habitación final. Rosa: habitación con rompecabezas. Azul:
puerta abierta. Amarillo: puerta cerrada.
5.2. Generación del Contenido de la Mazmorra
Algoritmo 5.1:Generación de la estructura de la mazmorra
1 inicializar una estructura de datos en forma de cola;
2 crear la habitación inicial y añadirla a la cola;
3 mientrasla cola no esté vacíahacer
4 extraer la primera habitación de la pila;
5 seleccionar un número aleatorio de habitaciones a generar;
6 mientrasno se alcance el número de habitaciones a generarhacer
7 crear una nueva habitación;
8 conectar la nueva habitación a la habitación actual;
9 añadir la nueva habitación a la pila;
10 fin
11 fin
12 colocar las paredes y puertas de todas las habitaciones;
• Cualquier llave funciona en cualquier puerta excepto la final.
La mejor manera de cumplir con todo mientras se genera el contenido es realizar un recorrido en profundidad de la habitaciones de la mazmorra, empezando por la habitación inicial. Veralgo.(5.2).
Algoritmo 5.2:Generación del contenido de la mazmorra
1 inicializar una estructura de datos en forma de pila;
2 obtener la habitación inicial y añadirla a la pila;
3 mientrasla pila no esté vacíahacer
4 extraer la primera habitación de la pila;
5 añadir todas las habitaciones contiguas no visitadas a la pila;
6 sila habitación no tiene salidaentonces
7 sise trata de la primera habitaciónentonces
8 generar la habitación inicial;
9 si no, sise trata de la última habitaciónentonces
10 generar la habitación final;
11 en otro caso
12 generar una habitación con rompecabezas;
13 generar una llave y añadirla al contador de llaves sin usar;
14 fin
15 en otro caso
16 generar una habitación normal;
17 fin
18 fin
El hecho de que el recorrido sea en profundidad permite asegurar que el jugador no se quede atascado, ya que siempre podrá acceder a una llave.
La habitación final necesita una llave especial. Como el orden en el que se van a coger las llaves no se puede conocer, la mejor manera de asegurarse que la última llave
5. ALGORITMOS DEGENERACIÓNPROCEDIMENTALIMPLEMENTADOS
que se consiga sea la del hagitación final es que cuando el jugador vaya a coger la última llave, esta llave se convierta en la llave de la habitación final.
A continuación se detalla cómo se genera cada tipo de habitación.
5.2.1 Habitación Inicial
La habitación inicial es muy sencilla ya que está completamente vacía, excepto por el jugador. Lo único que hay que hacer es colocar el jugador en el centro de la habitación.
5.2.2 Habitación Normal
Las habitaciones normales tienen dos tipos de contenido diferenciados: enemigos y obstáculos.
La generación de enemigos se realiza buscando espacios libres y alejados de las puertas. Esto evita que los enemigos no ocupen la misma casilla que otra entidad y que el jugador no se encuentre con uno nada mas entrar a la habitación. Veralgo.(5.3), al-go.(5.4)yalgo.(5.5) en la página siguiente
Algoritmo 5.3:Generación de una habitación normal
1 siquedan llaves sin utilizarentonces
2 escoger una puerta abierta de manera aleatoria;sise ha encontrado una puertaentonces
3 cerrar la puerta;
4 reducir el contador de llaves;
5 fin
1 mientrasno se haya alcanzado el límite de enemigoshacer
2 escoger una casilla aleatoria;
3 encontrar la casilla libre más cercana a la casilla escogida;
4 sise ha encontrado una casillaentonces
5 colocar un enemigo en la casilla;
6 fin
7 fin
La generación de obstáculos es más compleja, aunque sigue el mismo principio. Se detallará más adelante.
5.2.3 Habitación con Rompecabezas
Las habitaciones de rompecabezas no contienen enemigos pero si contienen obstácu-los y objetos que sirven para solucionar un rompecabezas. Veralgo.(5.6).
5.2. Generación del Contenido de la Mazmorra
Algoritmo 5.5:Encontrar la casilla libre más cercana a una casilla dada
1 inicializar una cola de casillas no visitadas;
2 inicializar una lista de casillas visitadas;
3 añadir la casilla dada a la cola de no visistadas;
4 mientrasla cola de no visitadas no esté vacíahacer
5 extraer la primera casilla de la cola;
6 añadir la casilla a la lista de visitadas;
7 sila casilla está libreentonces
8 devolverla casilla actual;
9 en otro caso
10 para cadacasilla adyacente a la actualhacer
11 sila casilla no se encuentra en la cola de no visitadas ni en la lista de visitadasentonces
12 añadir la casilla a la cola de no visitadas;
13 fin
14 fin
15 fin
16 fin
17 devolverninguna casilla;
Algoritmo 5.6:Generación de una habitación con rompecabezas
1 siquedan llaves sin utilizarentonces
2 escoger una puerta abierta de manera aleatoria;
3 sise ha encontrado una puertaentonces
4 cerrar la puerta;
5 reducir el contador de llaves;
6 fin
7 fin
8 generar obstáculos fijos;
9 generar obstáculos rompibles;
10 generar rompecabezas;
5. ALGORITMOS DEGENERACIÓNPROCEDIMENTALIMPLEMENTADOS
Más adelante se explicará en más detalle cómo se genera el rompecabezas, puesto que es bastante más complejo que la generación de enemigos.
5.2.4 Habitación Final
La habitación del jefe se genera de una manera similar a las habitaciones normales, aunque en lugar de generar múltiples enemigos se genera un único enemigo jefe.
Veralgo.(5.7).
Algoritmo 5.7:Generación de una habitación final
1 cerrar la puerta con cerradura especial;
2 generar obstáculos fijos;
3 generar obstáculos rompibles;
4 colocar el jefe;
