A LGORITMOS DE G ENERACIÓN P ROCEDIMENTAL I MPLEMENTADOS
5.4 Generación de Rompecabezas
Los rompecabezas son el contenido más difícil de generar de manera procedimental en un videojuego. Cada tipo de rompecabezas requiere algoritmos diferentes, y los algoritmos han de tener en cuenta todo lo que un diseñador profesional emplearía para diseñar un rompecabezas.
Uno de los tipos de rompecabezas que se han explorado más es el Sokoban, y es el tipo de rompecabezas que se ha decidido generar por los motivos expuestos en el anterior capítulo.
5.4. Generación de Rompecabezas
Algoritmo 5.8:Generación de obstáculos
1 mientrasno se alcance el límite de obstáculos que se puedan romperhacer
2 escoger un tipo de obstáculo que se pueda romper aleatorio;
3 escoger una casilla aleatoria;
4 encontrar la casilla libre más cercana a la casilla escogida;
5 sise ha encontrado una casillaentonces
6 colocar el obstáculo en la casilla;
7 fin
8 fin
9 mientrasno se alcance el límite de obstáculos irrompibleshacer
10 escoger un tipo de obstáculo irrompible aleatorio;
11 escoger una casilla aleatoria;
12 encontrar la casilla libre más cercana a la casilla escogida que no limite la accesibilidad del resto de casillas;sise ha encontrado una casillaentonces
13 colocar el obstáculo en la casilla;
14 fin
15 fin
Algoritmo 5.9:Encontrar la casilla libre más cercana a una casilla dada que no limite la accesibilidad del resto de casillas
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á libre y colocar un obstáculo no limita la accesibilidad del resto de casillasentonces
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;
5. ALGORITMOS DEGENERACIÓNPROCEDIMENTALIMPLEMENTADOS
Algoritmo 5.10:Comprobar la accesibilidad del resto de casillas al colocar un obstáculo
1 inicializar una pila de casillas no visitadas;
2 inicializar una lista de casillas visitadas;
3 inicializar un contador de casillas libres o con obstáculos rompibles visitadas;
4 escoger una de las casilla con puertas de forma aleatoria;
5 añadir la casilla a la pila de casillas no visitadas;
6 mientrasla pila no esté vacíahacer
7 extraer la primera casilla de la pila;
8 añadir la casilla actual a la lista de casillas visitadas;
9 sila casilla está libre o tiene un obstáculo rompibleentonces
10 sumar uno al contador;
11 fin
12 para cadacasilla adyacente a la actualhacer
13 sila casilla no se encuentra en la pila de no visitadas ni en la lista de visitadasentonces
14 añadir la casilla a la pila de no visitadas;
15 fin
16 fin
17 fin
18 siel contador es igual al número total de casillas libres o con obstáculos rompibles entonces
19 devolververdadero;
20 en otro caso
21 devolverfalso;
22 fin
Para el juego se ha desarrollado un algoritmo que se pueda ejecutar en un tiempo mínimo. De esta manera el jugador no tiene que esperar demasiado tiempo a que se genere la mazmorra. Existen algoritmos más avanzados y con múchos más parámetros que permiten generar mejores rompecabezas, pero ninguno de ellos permite generar rompecabezas en un tiempo adecuado para el juego. [28] Veralgo.(5.11) en la página 39.
Este algoritmo se ejecuta una vez se han colocado los obstáculos. El algoritmo ge-nera rompecabezas empezando por colocar las cajas en la posición final y moviéndolas desde ahí. Esto permite evitar crear rompecabezas que no se puedan resolver, lo cual impediría al jugador progresar en el juego.
Las partes no triviales del algoritmo son la parte de colocar cajas y la parte de mover las cajas. Para colocar las cajas se utiliza el algoritmo de generación de obstáculos fijos, así que no es necesario un nuevo algoritmo. Sin embargo, para mover las cajas se necesitan tener varias cosas en cuenta:
• El jugador debe poder empujar la caja desde la dirección escogida.
• El jugador debe poder acceder al sitio desde el que se ha de empujar la caja.
• El jugador debe poder realizar el último movimiento.
5.4. Generación de Rompecabezas
Algoritmo 5.11:Generación de rompecabezas estilo Sokoban
1 escoger el número de cajas a colocar (según la dificultad);
2 mientrasno se alcance el límite de cajashacer
3 escoger una casilla de forma aleatoria;
4 encontrar la casilla libre más cercana a la casilla escogida;
5 sise ha encontrado una casillaentonces
6 colocar una caja en la casilla;
7 colocar una meta en la casilla;
8 fin
9 fin
10 escoger el número de movimientos a realizar (según la dificultad);
11 mientrasno se alcance el límite de movimientoshacer
12 para cadacajahacer
13 intentar mover la caja;
14 mientrasla caja se encuentra al lado de una puertahacer
15 intentar mover la caja;
16 fin
17 fin
18 fin
19 para cadacajahacer
20 sino se ha movidoentonces
21 eliminar caja;
22 eliminar meta de la casilla en la que estaba la caja;
23 fin
24 fin
• La caja no puede pasar por obstáculos.
El algoritmo para mover las cajas se ha hecho teniendo en cuenta los anteriores puntos. Veralgo.(5.12) en la página siguienteyalgo.(5.13) en la página 40.
Algoritmo 5.12:Movimiento de las cajas
1 para cadadirección posible en orden aleatoriohacer
2 sila caja puede moverse en la direcciónentonces
3 seleccionar la dirección;
4 fin
5 fin
6 sihay una dirección seleccionadaentonces
7 mover la caja en la dirección seleccionada;
8 guardar la posición desde la que hay que empujar la caja como siguiente casilla a alcanzar;
9 fin
Para comprobar si la posición desde la que hay que empujar la caja es accesible basta con comprobar que existe un camino desde la puerta a dicha posición sin pasar
5. ALGORITMOS DEGENERACIÓNPROCEDIMENTALIMPLEMENTADOS
Algoritmo 5.13:Comprobación de movimiento de la caja en una dirección
1 sihay obstáculos 2 casillas en la dirección escogidaentonces devolverfalso;
2 ;
3 sino existe un camino entre la siguiente casilla a alcanzar y la posición en la que se encontrará el jugador después de empujar la cajaentonces devolverfalso;
4 ;
5 sila casilla desde la que se ha de empujar la caja no se puede acceder desde la puertaentonces devolverfalso;
6 ;
7 devolververdadero;
por donde estaría la caja antes de empujarla. Esto se obtiene moviendo la caja a dicha posición y luego revirtiendo el cambio una vez se ha hecho la comprobación.
Comprobar si existe un camino entre 2 casillas requiere de un simple algoritmo de búsqueda en profundidad que esquive obstáculos.
5.4. Generación de Rompecabezas
Figura 5.2: Ejemplo de rompecabezas generado procedimentalmente. Las metas son puntos blancos.
C
APÍTULO6
C ONCLUSIONES
El desarrollo de un videojuego conGPCes increíblemente complejo, pero permite a pequeños desarrolladores incluir mucho más contenido en los juegos del que hubieran podido crear manualmente sinGPC.
Sin embargo la ventaja de los sistemas deGPCse esfuma si el diseñador no tiene control técnico o no sabe en que casos puede ser útil laGPCy en que casos puede ser contraproducente y generar contenido inútil o aburrido.
Realizar pequeñas variaciones en las estadísticas conGPCcomo puede ser variar el daño de un arma es la manera más sencilla de incluirGPCen un videojuego. A medida que se quiera aumentar el ámbito de actuación de los algoritmos es necesario más conocimiento técnico y de diseño. Realizar videojuegos completos conGPCes lo más complicado que se puede intentar. Los rompecabezas procedimentales tam-bién son uno de los ámbitos deGPCmás complejos, sobre todo si se quiere que los rompecabezas generados tengan la misma calidad que los creados a mano.
En definitiva, el desarrollador que quiera utilizarGPCen sus proyectos debe saber las limitaciones técnicas y la dificultad que tiene crear algoritmos para los sistemas más complejos deGPC.