T reba ll F ina l de G rau
GRAU D’ENGINYERIA INFORMÀTICA
Generación Procedimental de Contenido en Videojuegos
JAIME BEA PÉREZ-ZUBIZARRETA
Tutor
José María Buades Rubio
Escola Politècnica Superior
Universitat de les Illes Balears
Í NDICE GENERAL
Índice general i
Índice de figuras iii
Acrónimos v
Resumen vii
1 Introducción 1
1.1 Contexto . . . 1
1.2 Ventajas y Desventajas . . . 1
1.3 Objetivos . . . 2
2 Generación Procedimental de Contenido 3 2.1 Historia . . . 3
2.1.1 1978 - Beneath Apple Manor . . . 3
2.1.2 1980 - Rogue . . . 4
2.1.3 1984 - Elite. . . 4
2.1.4 1991 - Sid Meier’s Civilization. . . 6
2.1.5 1997 - Diablo . . . 6
2.1.6 2006 - Slaves to Armok: God of Blood Chapter II: Dwarf Fortress 7 2.1.7 2008 - Spelunky . . . 7
2.1.8 2009 - Minecraft . . . 8
2.1.9 2017 - LEGO Worlds . . . 8
2.2 Generación Procedimental de Contenido . . . 9
2.2.1 Generadores de Números Aleatorios . . . 9
2.2.2 Mapas . . . 12
2.2.3 Objetos y propiedades . . . 15
2.2.4 Rompecabezas y minijuegos . . . 17
3 Motores de Videojuegos y Frameworks 19 3.1 Introducción . . . 19
3.2 Ejemplos de Motores y Frameworks . . . 19
3.2.1 Unity . . . 19
3.2.2 Unreal Engine. . . 21
3.2.3 Monogame . . . 21
3.2.4 LibGDX . . . 21
ii ÍNDICE GENERAL
3.3 Motor escogido . . . 22
4 El Videojuego 23 4.1 El Diseño . . . 23
4.1.1 Objetivo . . . 23
4.1.2 Jugabilidad . . . 23
4.1.3 Controles . . . 27
4.2 El Motor . . . 27
4.2.1 Modelo. . . 27
4.2.2 Vista . . . 28
4.2.3 Control. . . 29
5 Algoritmos de Generación Procedimental Implementados 31 5.1 Generación de la Estructura de la Mazmorra . . . 31
5.2 Generación del Contenido de la Mazmorra . . . 31
5.2.1 Habitación Inicial . . . 34
5.2.2 Habitación Normal. . . 34
5.2.3 Habitación con Rompecabezas . . . 35
5.2.4 Habitación Final . . . 35
5.3 Generación de Obstáculos . . . 36
5.4 Generación de Rompecabezas. . . 36
6 Conclusiones 43 A Anexos 45 A.1 Timetable . . . 45
A.2 Videojuego de Ejemplo . . . 45
Bibliografía 47
Í NDICE DE FIGURAS
2.1 Captura del videojuego Beneath Apple Manor. [1] . . . 4
2.2 Captura del videojuego Rogue. [2] . . . 5
2.3 Captura del videojuego Elite. [3] . . . 5
2.4 Captura del videojuego Sid Meier’s Civilization. [4] . . . 6
2.5 Captura del videojuego Slaves to Armok: God of Blood Chapter II: Dwarf Fortress. [5] . . . 7
2.6 Captura del videojuego Spelunky. [6] . . . 8
2.7 Captura del videojuego LEGO Worlds. [7] . . . 9
2.8 Ejemplo de ruido generado mediante el algoritmo de Perlin en 2D. Los valores oscilan entre 0 (negro) y 1 (blanco). [8] . . . 11
2.9 Ejemplo de paisaje de Minecraft. . . 13
2.10 Diagrama de Whittaker. Minecraft utiliza una versión modificada para gene- rar biomas. [9] . . . 13
2.11 Ejemplo de generación de una isla con rios mediante grafos de Voronoi. [10] 14 2.12 Ejemplo de generación de una isla con carreteras mediante grafos de Voro- noi. [11] . . . 15
2.13 Ejemplo de mazmorra dividida mediante un árbol binario. [12] . . . 16
2.14 Mazmorra de Diablo. [13] . . . 16
2.15 Objetos generados mediante Generación Procedimental de Contenido (GPC) en Diablo. [14] . . . 17
2.16 Nivel de Road Not Taken. [15] . . . 17
3.1 Diagrama de un motor de videojuegos 3D completo. [16] . . . 20
4.1 Ejemplo de una habitación normal con obstáculos y enemigos. . . 25
4.2 Imágen del videojuego Soko-Ban. [17] . . . 26
4.3 Diagrama de clases del modelo de datos del videojuego. . . 28
4.4 Diagrama de actividad de las pantallas del juego.. . . 29
5.1 Ejemplo de una mazmorra generada. Rojo: habitaciones normales. Blanco: habitación inicial. Negro: habitación final. Rosa: habitación con rompeca- bezas. Azul: puerta abierta. Amarillo: puerta cerrada. . . 32
5.2 Ejemplo de rompecabezas generado procedimentalmente. Las metas son puntos blancos. . . 41
A.1 Timetable del trabajo. . . 45
A CRÓNIMOS
TFG Trabajo Final de Grado
GPC Generación Procedimental de Contenido RPG Role Playing Game
MVC Modelo Vista Controlador ECS Entidad Componente Sistema
R ESUMEN
El proyecto a realizar consiste en una combinación de investigación a cerca de la Generación Procedimental de Contenido (GPC) y el desarrollo e implementación de algunos algoritmos deGPCen un videojuego. El objetivo del proyecto es aprender cómo algunos videojuegos han implementadoGPCe intentar implementar algunos algoritmos en un videojuego original.
Inicialmente se expondrá una pequeña historia de laGPCy se hablará de algu- nos algoritmos deGPCconocidos como la generación del terreno en Minecraft o la generación de armas en Diablo.
En los capítulos siguientes se expondrá el videojuego que se ha desarrollado, junta- mente con detalles de los algoritmos deGPCque han sido utilizados y un manual de usuario para que cualquier persona pueda probarlo.
C
APÍTULO1
I NTRODUCCIÓN
1.1 Contexto
En los últimos años, la industria de los videojuegos ha crecido de manera muy nota- ble. Las grandes desarrolladoras de videojuegos cada vez gastan más dinero en sus proyectos, aumentando así la cantidad de contenido que tiene el juego. Este aumento en la cantidad de contenido ha causado que las pequeñas desarrolladoras no puedan competir con las grandes en cuanto a contenido se refiere.
Para poder competir, las pequeñas desarrolladoras han tenido que cambiar su enfoque. En lugar de vender juegos basados en contenido creado manualmente, han pasado a enfocarse en crear juegos con mecánicas originales o elementos que les permitan diferenciarse claramente de las grandes superproducciones.
Esto ha permitido el resurgimiento de las pequeñas desarrolladoras como parte importante de la industria, recibiendo el apodo deindies. Hay que tener en cuenta que aunque el apodo parezca implicar independencia normalmente no lo son. El término se utiliza explícitamente para pequeñas desarrolladoras, normalmente con menos de 20 trabajadores.
Uno de los trucos que han permitido a los juegos indie competir en cuanto a contenido con las grandes superproducciones es la Generación Procedimental de Contenido (GPC). En esto es en lo que se enfoca este trabajo, describiendo algunas de las formas más utilizadas de generación procedimental y aplicando algunas de ellas en la creación de un videojuego.
1.2 Ventajas y Desventajas
LaGPCes un concepto que consiste en hacer que el ordenador realice de forma auto- mática el trabajo que tradicionalmente haría un diseñador de videojuegos. Esto tiene ciertas ventajas. A continuación se enumeran algunas de ellas:
1. INTRODUCCIÓN
• Se necesitan menos diseñadores. Siguen necesitándose diseñadores que dise- ñen los algoritmos deGPC, pero una vez hacho esto el contenido lo crea los algoritmos.
• Se puede crear contenido mientras el jugador está jugando. Esto es algo que un diseñador humano no podría realizar a no ser que el juego esté constantemente conectado a la red, puesto que no se puede incluir un diseñador con cada copia del juego.
• Se puede crear contenido único para cada jugador. Esto es irrealizable con dise- ñadores humanos.
• Se puede crear contenido infinito. Esto es también irrealizable con diseñadores humanos.
Sin embargo no todo son ventajas, y una mala utilización de las técnicas deGPC puede reducir la calidad de un videojuego notablemente. Algunas de las desventajas son:
• Es necesario un diseñador que pueda diseñar los algoritmos deGPC. Esto im- plica que el diseñador ha de tener conocimientos elevados de programación y matemáticas para poder entender lo que se está haciendo.
• El contenido generado medianteGPC suele tener una calidad generalmente inferior a lo que podría crear un diseñador humano.
• Los procesos deGPCpueden llegar a ser increíblemente lentos.
1.3 Objetivos
Para la realización de este Trabajo Final de Grado (TFG) se estableció como objetivos el aprendizaje de diferentes técnicas deGPCy la creación de un videojuego implemen- tando algunas de las técnicas aprendidas diseñando diversos algoritmos deGPC.
C
APÍTULO2
G ENERACIÓN P ROCEDIMENTAL DE
C ONTENIDO
2.1 Historia
LaGPClleva usándose desde los inicios de la industria, aunque no siempre se ha usado por los mismos motivos.
En los años 70 y 80 los videojuegos estaban muy limitados por la memoria dispo- nible en los ordenadores, por lo que introducir mucho contenido creado a mano en un videojuego era prácticamente imposible. Aquellos diseñadores que querían me- ter mucho contenido en su juego se vieron obligados a utilizarGPC, que les permitía crear el contenido mientras el juego se estaba jugando, evitando así las limitaciones de memoria.
A partir de los años 90 laGPCse siguió utilizando por los mismos motivos, aunque con menos frecuencia. Los diseñadores de videojuegos ya habían descubierto los problemas que tenía laGPCe intentaron evitarla en lo posible, con una serie de notables excepciones en videojuegos que aún hoy se consideran clásicos.
Con el resurgimiento de los indies laGPCvolvió una vez más a ser utilizada con frecuencia. Sin embargo ya no se utiliza por limitaciones en el hardware, sino que se utiliza para introducir más contenido en los juegos y competir con las grandes superproducciones. Desde entonces laGPCse ha extendido a todo tipo de juegos, grandes y pequeños, aprovechando las ventajas que ofrece en cuanto a rejugabilidad y creación automática de contenido.
2.1.1 1978 - Beneath Apple Manor
El primer juego comercial del que se tiene constancia que aplicó por primera vez técni- cas deGPCfue Beneath Apple Manor. El videojuego se desarrolla en unas mazmorras laberínticas de múltiples pisos de profundidad. El objetivo del juego es alcanzar una manzana dorada que se encuentra en el piso más profundo, pero para conseguir eso el
2. GENERACIÓNPROCEDIMENTAL DECONTENIDO
Figura 2.1: Captura del videojuego Beneath Apple Manor. [1]
jugador tiene que luchar contra fantasmas y otros monstruos que se encontrará en su camino. [18]
El juego se desarrolla por turnos, donde el jugador puede moverse o atacar en una de cuatro direcciones y los enemigos hacen lo mismo. LaGPCse emplea para generar habitaciones y pasillos, así como monstruos y tesoros. El algoritmo utiliza una serie de reglas que impiden que se creen en la medida de lo posible malas configuraciones.
2.1.2 1980 - Rogue
Rogue, a pesar de ser posterior a Beneath Apple Manor, tuvo mucha más repercusión en el mundo de los videojuegos. De hecho los videojuegos con reglas similares (muerte permanente, mundos generados procedimentalmente, movimiento por turnos, etc.) se clasifican en el género de losRoguelike. El término ha sufrido un mal uso, sobre todo por el desconocimiento general de la población sobre el juego original, y ahora sigue una definición mucho más laxa, únicamente incluyendo la muerte permanente y la GPCcomo nexo de unión entre los juegos del género.
El juego utiliza laGPCde la misma manera que Beneath Apple Manor, aunque en este caso las reglas son algo más estrictas y evita algunos problemas del anterior juego, como pasillos que se cruzan. [19]
2.1.3 1984 - Elite
Elite es un juego de comercio espacial. Es considerado como uno de los videojuegos más importantes de la historia debido a su innovador uso de los gráficos 3D y una
2.1. Historia
Figura 2.2: Captura del videojuego Rogue. [2]
Figura 2.3: Captura del videojuego Elite. [3]
2. GENERACIÓNPROCEDIMENTAL DECONTENIDO
Figura 2.4: Captura del videojuego Sid Meier’s Civilization. [4]
jugabilidad que permite amplia libertad al jugador. Se le considera el primer videojuego de mundo abierto. Ha inspirado múltiples juegos tales como EVE online, GTA y No Man’s Sky.
El juego genera los planetas y sistemas planetarios medianteGPC, incluyendo su nombre y su historia. Esto permitía crear universos que en la época en la que se creó hubieran sido imposibles por la cantidad de memoria disponible.
2.1.4 1991 - Sid Meier’s Civilization
Sid Meier’s Civilization, acortadoCiv, es un juego de estrategia en el cual el jugador escoge un imperio que controlar e intenta dominar el mundo. Tuvo un gran éxito gracias a la gran complejidad de sus sistemas y a la inteligencia artificial que tomaba la personalidad de cada líder. Hoy en día se siguen creando secuelas al juego original.
El juego utilizaGPCpara generar los mundos en los que se desarrolla el juego, colocando casillas de montaña, bosque o agua de forma lógica.
2.1.5 1997 - Diablo
Diablo es un Role Playing Game (RPG) con niveles generados medianteGPC. Recoge muchas de las cualidades de los Roguelike, pero elimina la jugabilidad por turnos a favor de acción en tiempo real.
Las mazmorras se crean medianteGPC, así como las propiedades de las armas y armaduras que te vas encontrando. Esto permite aumentar de forma considerable la rejugabilidad. El sistema de colores para indicar la rareza de las armas se utilizó por primera vez en este juego, y a partir de entonces ese mismo sistema se ha utilizado en una gran cantidad deRPG.
2.1. Historia
Figura 2.5: Captura del videojuego Slaves to Armok: God of Blood Chapter II: Dwarf Fortress. [5]
2.1.6 2006 - Slaves to Armok: God of Blood Chapter II: Dwarf Fortress Slaves to Armok: God of Blood Chapter II: Dwarf Fortress, también conocido como Dwarf Fortress, es un juego de simulación con una gran cantidad de sistemas inter- conectados. El jugador puede elegir entre controlar un personaje y jugar al estilo de los Roguelike de los años 80 o bien controlar un fuerte de enanos, dándoles órdenes y construyendo poco a poco un fuerte habitable. El juego no es conocido por gran parte del publico, pero ha introducido en la industra toda una revolución en cuanto a lo que se puede hacer conGPC.
LaGPCse utiliza para crear un mundo con historia, héroes, leyendas y personajes históricos, todo ello simulado desde el día de la creación hasta el año que el jugador haya escogido como punto de partida de su mundo. La profundidad del juego es abrumadora, y la curva de aprendizaje es muy elevada, lo que ha limitado el juego a ser únicamente jugado por los jugadores más experimentados.
2.1.7 2008 - Spelunky
Spelunky fue uno de los juegos que iniciaron el retorno de los indies al frente de la industria de los vidueojuegos. El juego recoge muchas cualidades del género Roguelike y lo mezcla con el género de plataformas, añadiendo acción. La dificultad del juego es muy elevada. Un jugador normal no pasará del primer nivel hasta que no lo haya intentado varias veces.
Utiliza laGPCpara generar los niveles, de manera que el jugador no puede apren- derse el nivel de memoria para poder pasárselo.
2. GENERACIÓNPROCEDIMENTAL DECONTENIDO
Figura 2.6: Captura del videojuego Spelunky. [6]
2.1.8 2009 - Minecraft
En el año 2009, inspirado por Dwarf Fortress y otros juegos similares, Markus "Notch"Persson crea Minecraft y lanza una versión temprana del juego a la venta. Gracias a que sim- plifica algunas de las cosas interesantes de Dwarf Fortress para hacerlas accesibles a todo tipo de jugadores el juego se vuelve un fenómeno instantáneo, y año tras año gana popularidad hasta convertirse en uno de los videojuegos más vendidos de la historia, vendiendo más de 100 millones de copias.
El juego se basa en la exploración de un mundo en 3D repleto de enemigos total- mente editable. Gracias a que el mundo está hecho de bloques permite libertad total a la hora de editar el mundo a medida del jugador.
UtilizaGPCpara generar los bloques de los que está hecho el mundo. El juego coloca los bloques de manera que parezca un paisaje natural, generando biomas como desiertos o junglas según la humedad y la temperatura.
2.1.9 2017 - LEGO Worlds
LEGO Worlds es un juego de exploración en el que el jugador puede crear su propio mundo a partir de objetos que va encontrando en su viaje. Muchas de sus características se basan en juegos como Minecraft y GTA, llevadas al mundo de LEGO y accesible para todos los públicos.
UtilizaGPCpara generar una infinidad de mundos que el jugador puede visitar. Los mundos se generan a partir de una definición de bioma al estilo de Minecraft. Además de esto también genera misiones que el jugador puede completar para desbloquear ciertos objetos.
2.2. Generación Procedimental de Contenido
Figura 2.7: Captura del videojuego LEGO Worlds. [7]
2.2 Generación Procedimental de Contenido
Los algoritmos deGPCse diseñan manualmente para cada juego, por lo que no existen esquemas genéricos. Sin embargo si que se pueden clasificar según lo que se intente generar.
2.2.1 Generadores de Números Aleatorios
La gran mayoría de algoritmos deGPCdependen de un generador de números aleato- rios. Los generadores de números aleatorios permiten introducir variabilidad en los algoritmos para que el contenido que generen sea diferente cada vez.
No existe manera de generar números completamente aleatorios en un ordenador convencional, pero si existen aproximaciones que devuelven números pseudoaleato- rios.
Generador Congruencial Lineal
El generador congruencial lineal es el algoritmo de generación de números aleatorios más utilizado paraGPC, gracias a su bajo coste computacional. [20]
El sistema genera números en un rango determinado de manera que los números generados sigan una distribución uniforme. La combinación de múltiples generadores congruenciales lineales y operaciones sobre ellos permiten crear el resto de sistemas de generación de números.
Los números generados se generan a partir de un número semilla,X0, y la siguiente fórmula:
Xn+1=(a Xn+c) m´odm (2.1)
Dondea(multiplicador),c(incremento) ym(módulo) son parámetros que pueden variar entre implementaciones. El valor demmarca el tope máximo del periodo del
2. GENERACIÓNPROCEDIMENTAL DECONTENIDO
generador, por lo que normalmente se utiliza el valor más alto posible. El teorema de Hull-Dobel marca además tres requisitos para que el periodo sea máximo (igual am):
1. mychan de ser coprimos.
2. a−1 ha de ser divisible por todos los factores primos dem.
3. Simes divisible entre 4,a−1 también ha de ser divisible entre 4.
Si además de esto se eliminan los bits más significativos del número obtenido se obtiene un generador mucho mejor. Esto se debe a que los bits más significativos tienen periodos menores.
La implementación de Java (java.util.Random) utiliza los siguientes valores:
• m=248
• a=25214903917
• c=11
• Resultado: bits 47 a 16 (32 bits).
Generador de Ruido
La generación de ruido permite generar números que además de estar basados en una semilla se generan a partir de coordenadas pasadas por parámetro. Dichas coordenadas pueden ser coordenadas 1D, 2D, 3D o incluson-dimensionales.
Los generadores de ruido utilizan generadores congruenciales lineales para dar cierta aleatoriedad al resultado y luego este se modifica según las coordenadas. Al gene- rar los números mediante este sistema se puede limitar la variación entre coordenadas adyacentes, haciéndolo especialmente útil a la hora de generar contenido con aspecto natural, ya sea generación de paisajes o de texturas.
El generador de ruido Perlin es la función de ruido más conocida, y una de las primeras que se crearon. Fue desarrollado por Ken Perlin para la películaTron(1982) y ha sido utilizado de manera notable en múltiples proyectos tanto cinematográficos como en videojuegos. [21]
A continuación se detalla una implementación del algoritmo de Perlin para 2 di- mensiones: [22]
// I n t e r p o l a c i ó n l i n e a l e n t r e a y b
// El p e s o w ha de e s t a r en el r a n g o [0.0 , 1 . 0 ] f l o a t l e r p (f l o a t a , f l o a t b , f l o a t w ) {
r e t u r n ( 1 . 0 - w ) * a + w * b ; }
// C o m p u t a r el p r o d u c t o e s c a l a r de los v e c t o r e s g r a d i e n t e y d i s t a n c i a .
f l o a t d o t G r i d G r a d i e n t (int vx , int vy , f l o a t x , f l o a t y ) {
2.2. Generación Procedimental de Contenido
Figura 2.8: Ejemplo de ruido generado mediante el algoritmo de Perlin en 2D. Los valores oscilan entre 0 (negro) y 1 (blanco). [8]
// V e c t o r e s g r a d i e n t e s p r e c o m p u t a d o s ( a l e a t o r i o s ) en c a d a v é r t i c e
e x t e r n f l o a t G r a d i e n t [ I Y M A X ][ I X M A X ] [ 2 ] ;
// C o m p u t a r el v e c t o r d i s t a n c i a f l o a t dx = x - (f l o a t) vx ;
f l o a t dy = y - (f l o a t) vy ;
// C o m p u t a r el p r o d u c t o e s c a l a r e n t r e el v e c t o r d i s t a n c i a y el v e c t o r g r a d i e n t e
r e t u r n ( dx * G r a d i e n t [ iy ][ ix ] [ 0 ] + dy * G r a d i e n t [ iy ][ ix ] [ 1 ] ) ;
}
// C o m p u t a r r u i d o P e r l i n en las c o o r d e n a d a s x , y
2. GENERACIÓNPROCEDIMENTAL DECONTENIDO
f l o a t p e r l i n (f l o a t x , f l o a t y ) {
// D e t e r m i n a r los l í m i t e s de la c e l d a int x0 = f l o o r ( x ) ;
int x1 = x0 + 1;
int y0 = f l o o r ( y ) ; int y1 = y0 + 1;
// D e t e r m i n a r la p o s i c i ó n d e n t r o de la c e l d a f l o a t sx = x - (f l o a t) x0 ;
f l o a t sy = y - (f l o a t) y0 ;
// C a l c u l a r los v a l o r e s de i n f l u e n c i a e i n t e r p o l a r
f l o a t n0 = d o t G r i d G r a d i e n t ( x0 , y0 , x , y ) ; f l o a t n1 = d o t G r i d G r a d i e n t ( x1 , y0 , x , y ) ; f l o a t n2 = d o t G r i d G r a d i e n t ( x0 , y1 , x , y ) ; f l o a t n3 = d o t G r i d G r a d i e n t ( x1 , y1 , x , y ) ; f l o a t ix0 = l e r p ( n0 , n1 , sx ) ;
f l o a t ix1 = l e r p ( n2 , n3 , sx ) ; f l o a t v a l u e = l e r p ( ix0 , ix1 , sy ) ;
r e t u r n v a l u e ; }
2.2.2 Mapas
La generación de mapas y paisajes es una de las formas deGPCmás utilizadas. La capacidad de crear infinitos niveles diferentes o mundos infinitos es uno de los usos más potentes deGPC. Existen varias maneras de generar mapas, por lo que se pueden subdividir aún más según el tipo de mapa que se quiera generar.
Terreno natural
El terreno natural es relativamente fácil de generar utilizando una combinación de generadores de ruido y generadores de números aleatorios. La dificultad se encuentra a la hora de ajustar los parámetros para obtener el terreno que se tenga en mente.
Uno de los juegos más conocidos que contiene un generador de terreno natural es Minecraft. Minecraft utiliza ruido Perlin 2D para generar un mapa de alturas inicial y luego añade ruido Perlin 3D para generar terreno más irregular y generar las cuevas.
[23]
Para que no todo el paisaje sea hierba, minecraft introduce biomas como desiertos y tundras, aumentando así la variedad. La forma en que lo hace es mediante un diagrama de Whittaker modificado. [24]
Otra manera de generar terreno de manera natural en 2D es mediante grafos de Voronoi. Colocando puntos aleatorios en un plano y creando polígonos de Voronoi alrededor de ellos se pueden conseguir zonas con la que se pueden trabajar de muchas maneras diferentes. [25]
2.2. Generación Procedimental de Contenido
Figura 2.9: Ejemplo de paisaje de Minecraft.
Figura 2.10: Diagrama de Whittaker. Minecraft utiliza una versión modificada para generar biomas. [9]
2. GENERACIÓNPROCEDIMENTAL DECONTENIDO
Figura 2.11: Ejemplo de generación de una isla con rios mediante grafos de Voronoi.
[10]
Por ejemplo se podrían utilizar las aristas para construir ríos o conectar los centros de los polígonos para construir caminos.
Mazmorras
La generación de mazmorras es utilizada principalmente en juegosRPGy Roguelikes.
Existen múltiples maneras de generar mazmorras, pero se utilizan principalmente 2 formas diferentes: dividiendo un espacio o construyendo la mazmorra a piezas.
Rogue crea las mazmorras dividiendo una cuadrícula utilizando la estructura de un árbol binario. En cada nivel del árbol se escoge una dirección de corte y un valor de forma aleatoria, y luego se subdividen las zonas recursivamente hasta llegar a un límite.
Una vez hecho esto se crean habitaciones en cada una de las zonas y se unen mediante pasillos siguiendo la estructura del árbol binario. [26]
Diablo, por el otro lado, crea sus mazmorras uniendo habitaciones prediseñadas poco a poco. Un generador de números aleatorios escoge la habitación que colocar, teniendo siempre en cuenta las restricciones que los desarrolladores le han dado...
2.2. Generación Procedimental de Contenido
Figura 2.12: Ejemplo de generación de una isla con carreteras mediante grafos de Voronoi. [11]
Normalmente se suelen añadir restricciones a las mazmorras para crear ciertas habitaciones bajo ciertas condiciones. Por ejemplo se puede crear una habitación que sea la única manera de llegar al resto de la mazmorra y añadir algún tipo de desafío especial en ella, como un enemigo más fuerte.
2.2.3 Objetos y propiedades
Se pueden crear variaciones de objetos y propiedades utilizandoGPC. La implementa- ción es muy fácil, basta con poner un generador de números aleatorios que nos genere un valor en un rango y tenemos una propiedad generada procedimentalmente. A esto normalmente se le añade un valor de rareza con una distribución no uniforme que nos permite hacer mejores o peores armas con probabilidades diferentes de encontrar cada nivel de rareza.
Diablo fue el primero en introducir la rareza en las armas y asignare un color a cada nivel de rareza. Esa distinción por colores se ha mantenido hasta el día de hoy.
2. GENERACIÓNPROCEDIMENTAL DECONTENIDO
Figura 2.13: Ejemplo de mazmorra dividida mediante un árbol binario. [12]
Figura 2.14: Mazmorra de Diablo. [13]
2.2. Generación Procedimental de Contenido
Figura 2.15: Objetos generados medianteGPCen Diablo. [14]
Figura 2.16: Nivel de Road Not Taken. [15]
2.2.4 Rompecabezas y minijuegos
También existen algoritmos daGPCque permiten la generación de pequeños minijue- gos o rompecabezas. Estos algoritmos pueden llegar a ser muy complejos, dependiendo del tipo de juego a generar.
No existen demasiados juegos conocidos que implementen algoritmos de este tipo.
Uno de ellos es Road Not Taken. Road Not Taken es un juego de rompecabezas en el que el jugador va juntando objetos para combinarlos. El juego se encarga de generar objetos que se puedan combinar para completar cada nivel, asegurándose de que el jugador no se pueda quedar bloqueado.
C
APÍTULO3
M OTORES DE V IDEOJUEGOS Y F RAMEWORKS
Los motores de videojuegos son la tecnología básica sobre la que se cimientan los juegos.
Un motor de videojuegos ofrece una gran cantidad de herramientas que aumentan la productividad de los equipos de desarrollo.
3.1 Introducción
Los motores de videojuegos normalmente están creados para un tipo de juego en concreto, ya sea juegos de plataformas 2D o juegos de acción multijugador 3D. Existen una serie de motores de videojuegos que son más genéricos en los tipos de juegos que se pueden crear, pero aún así destacan en cierto tipo de juego.
Los frameworks son puntos de partida básicos con librerias opcionales desde los que se puede crear un motor. Se encuentran a mitad de camino entre librerias de ayuda y motores completos, y ofrecen mucha más flexibilidad que estos últimos. Cuando el género del videojuego a realizar no se adecúa a ningún motor la mejor opción para la productividad es escoger un framework.
3.2 Ejemplos de Motores y Frameworks
3.2.1 Unity
Unity es el motor de videojuegos más conocido. Es muy fácil de aprender y tiene la ventaja de tener una gran cantidad de contenido extra y plugins creados por la comunidad. Algunas de las cosas que le diferencian del resto de motores son:
• Scripting con C#, JavaScript o Boo
• Puede utilizarse para proyectos 2D y 3D, con gran cantidad de prestaciones para cada tipo de proyecto.
3. MOTORES DEVIDEOJUEGOS YFRAMEWORKS
Figura 3.1: Diagrama de un motor de videojuegos 3D completo. [16]
3.2. Ejemplos de Motores y Frameworks
• Multiplataforma. Se puede exportar el proyecto para diferentes plataformas con un solo clic.
• Dispone de múltiples precios para distintos tipos de desarrolladores, incluyendo una versión gratuita siempre que no se supere un límite de ingresos.
Su desventaja principal es que ofrece acceso al código fuente a no ser que se pague por dicho acceso, por lo que se vuelve complicado editar el motor a medida.
3.2.2 Unreal Engine
Unreal Engine es uno de los motores más potentes del mercado y el que ofrece más prestaciones gratuitas de todos ellos. Ofrece, entre otras cosas:
• Acceso completo y libertad de modificación del código fuente.
• Programación en C++ o programación visual mediante Blueprints, un lenguaje visual creado específicamente para Unreal Engine.
• Multiplataforma. Se puede exportar el proyecto para diferentes plataformas con un solo clic.
• Gran fadilidad a la hora de crear juegos multijugador online.
• El coste del motor depende de tus ingresos.
Su desventaja principal es la falta de herramientas para la creación de juegos 2D.
Aunque es posible, lleva más trabajo del que debería y gasta excesivos recursos.
3.2.3 Monogame
Monogame es un framework para crear videojuegos en C#. Existe una gran cantidad de librerías y se pueden desarrollar vudeojuegos profesionales rápidamente. Al igual que los motores anteriores, Monogame también es multiplataforma.
Al contrario que los motores anteriormente expuestos, Monogame no dispone de editor de niveles de ningún tipo y el desarrollo depente de lo que decida el programador.
Esto permite crear cualquier género de videojuego, ya sea 2D o 3D.
Una de las principales desventajas de Monogame es que la documentación es muy mejorable. Aparte de esto, exportar videojuegos a Android requiere de configuración extra.
3.2.4 LibGDX
LibGDX es un framework muy parecido a Monogame pero ofrece las librerías en Java en lugar de en C#. La documentación es bastante mejor que Monogame y ofrece básicamente las mismas prestaciones.
La mayor desventaja es que el desarrollo para iOS requiere de programas especiales de terceros.
3. MOTORES DEVIDEOJUEGOS YFRAMEWORKS
3.3 Motor escogido
A la hora de escoger el motor se ha tenido en cuenta el tipo de juego a desarrollar.
El videojuego completo se explica más adelante, pero a continuación se enumeran algunas de las cosas que son relevantes a la hora de escoger un motor:
1. Vista 2D.
2. Movimiento en forma de cuadrícula.
3. Generación procedimental de mapas.
LaGPCno viene incluida en ninguna clase de motor de videojuegos porque es diferente para cada juego, por lo que no existe una implementación que le pudiera servir a varios. Por ese motivo utilizar un motor de código abierto o un framework es la mejor opción.
Debido a esto, en lugar de escoger un motor completo se ha escogido el framework LibGDX. Esto se debe a que la vista 2D y la generación procedimental de mapas de Unity y Unreal Engine no son suficientemente buenas. Además, los motores que permiten desarrollar fácilmente videojuegos de este estilo, como GameMaker o Corona2D, son de pago. Las razones por la que se ha escogido LibGDX en lugar de Monogame son las siguientes:
• Mayor facilidad de desarrollo para Android.
• Mayor y mejor documentación.
• Mayor conocimiento del lenguaje de programación Java.
Sin embargo esto significa que será necesario crear un motor.
C
APÍTULO4
E L V IDEOJUEGO
A partir del framework LibGDX se ha creado un videojuego. El trabajo realizado incluye el diseño del videojuego, la creación de un motor que soporte el juego y la implemen- tación de varios algoritmos deGPC. En este capítulo se detallarán las dos primeras partes.
4.1 El Diseño
La idea principal del juego es intentar traer la jugabilidad de los juegos Roguelike de los años 80 exactamente como se recuerda, mejorando los aspectos deficientes y mejorando la interacción para que el usuario pueda jugar en cualquier momento en su smartphone sin necesidad de ser un experto.
4.1.1 Objetivo
El jugador es un héroe de fantasía que ha decidido su destino e intentará salvar al mundo de los villanos que lo pueblan. En la taberna escogerá un adversario adecuado para su nivel y embarcará en una misión por las mazmorras para eliminarle.
Una vez haya alcanzado la máxima reputación, el héroe se retirará y será recordado en las leyendas.
4.1.2 Jugabilidad
El juego está basado en el combate y la resolución de rompecabezas. Para ayudar en la tarea el jugador tiene acceso a un máximo de 4 armas. Dichas armas se pueden comprar en la tienda, a la cual se puede acceder desde la taberna. El dinero necesario para comprar las armas se consigue eliminando a los enemigos en las mazmorras.
4. ELVIDEOJUEGO
Estructura de la Mazmorra
Las mazmorras consisten de una serie de habitaciones que el jugador debe atravesar. El número de habitaciones depende de la dificultad de la misión. La mazmorra está dise- ñada de tal manera que para pasársela sea necesario atravesar todas las habitaciones.
Cada una de las habitaciones contiene obstáculos y enemigos. Para poder continuar el jugador debe eliminar a todos los enemigos de la habitación. Los obstáculos pueden ser destruidos con el arma adecuada, y están diseñados para que nunca impidan el progreso del jugador por la mazmorra.
Existen los siguientes tipos de habitación:
• Habitación inical: Es la habitación en la que comienza el jugador. No tiene obs- táculos ni enemigos.
• Habitación del jefe: Es la habitación en la que se encuentra el jefe final. La puerta de acceso a la habitación está cerrada con una cerradura especial que solo se puede abrir con una llave especial que se consigue al recorrer toda la mazmorra.
• Habitación normal: Componen la mayoría de las habitaciones y contienen tanto obstáculos como enemigos. Las puertas de la habitación que estén cerradas y no tengan candado se abrirán al eliminar todos los enemigos de la habitación.
• Habitacion con rompecabezas: Las habitaciones que no tengan salida tienen un rompecabezas. Al completar el rompecabezas se descubre un cofre con una llave que permite abrir una puerta cerrada con cerrojo. La última llave de la mazmorra es la llave de la habitación del jefe.
Combate
El combate ocupa la mayor parte del tiempo, siendo por tanto la parte más importante del juego. Cada habitación normal contiene uno o más enemigos, que pueden ser de diferentes tipos. Puesto que esto se trata de un videojuego de ejemplo sólo se ha implementado un tipo de enemigo, puesto que el diseño no debe ocupar demasiado tiempo.
El enemigo implementado se va moviendo lentamente en la dirección del jugador, y si se encuentra suficientemente cerca, cargará un ataque que dañará al jugador en el próximo turno a no ser que este se mueva. Tiene 2 puntos de vida, lo que significa que debe recibir dos ataques del jugador para ser eliminado. Su ataque hace 2 puntos de daño.
El jefe funciona de la misma manera, aunque tiene 10 puntos de vida y sus ataques causan 5 puntos de daño.
El jugador tiene 5 puntos de vida, lo que significa que es capaz de resistir 3 ataques de los enemigos básicos o 1 del jefe. Si el jugador pierde todos sus puntos de vida, el juego acaba. El jugador puede entonces decidir si empezar una nueva aventura o parar por el momento.
4.1. El Diseño
Figura 4.1: Ejemplo de una habitación normal con obstáculos y enemigos.
4. ELVIDEOJUEGO
Figura 4.2: Imágen del videojuego Soko-Ban. [17]
Rompecabezas
Los rompecabezas son pequeños desafíos para el jugador que debe superar para conti- nuar. Se encuentran en habitaciones que no tienen más que una puerta y ofrecen una llave como recompensa por solucionarse.
Como se trata de un videojuego de ejemplo solo se ha incluido un tipo de rompeca- bezas. El tipo de rompecabezas escogido es Sokoban, ya que sus sencillas reglas y la dificultad que puede llegar a alcanzar son perfectos para intentar generar niveles de manera procedimental.
Sokoban fue inventado por Hiroyuki Imabayashi en el año 1981, y el primer juego fue publicado por Thinking Rabbit en el año 1982. [27] A partir de este se han realizado innumerables clones y secuelas.
Las reglas de Sokoban son muy sencillas:
• El jugador se encuentra en un tablero de casillas cuadradas y se puede mover en 4 direcciones: arriba, abajo, a la izquierda y a la derecha.
• El tablero contiene paredes y cajas. Las paredes no se pueden mover, mientras que las cajas se pueden empujar si existe una casilla libre en el lado contrario desde el que se intenta empujar. No se puede estirar de ellas.
• Algunas de las casillas son casillas meta. Las casillas meta no impiden ni al jugador ni a las cajas moverse. Para completar el rompecabezas todas las cajas deben situarse encima de casillas meta.
4.2. El Motor
Ya que el juego se juega en una cuadrícula adecuar este tipo de rompecabezas es trivial, puesto que basta con incluir un control sobre las casillas meta que nos permita saber si se ha resuelto.
4.1.3 Controles
Al empezar una partida, el jugador será llevado directamente a la taberna. En la taberna podrá entrar en la primera misión o bien ir a la tienda, donde podrá comprar nuevas armas.
Puesto que el juego ha sido pensado para dispositivos móviles, los controles deben de ser muy simples. De hecho solamente existen dos acciones posibles dentro de una mazmorra:
• Movimiento: deslizar el dedo en la dirección deseada (arriba, abajo, izquierda o derecha)
• Atacar: seleccionar un arma de la barra inferior y deslizar el dedo en la dirección deseada.
Para cambiar de habitación basta con moverse a la puerta adecuada y el jugador será trasladado a la habitación adyacente. Para abrir puertas cerradas con llave basta con moverse hacia ellas.
4.2 El Motor
El motor se ha diseñado para facilitar la creación de un videojuego por turnos y permitir la creación de contenido medianteGPC. En lugar de utilizar el patrón Entidad Compo- nente Sistema (ECS) como es común en los motores de videojuegos se ha optado por el patrón Modelo Vista Controlador (MVC) modificado para permitir mayor interacción entre control y modelo. Aunque esto hace que el código sea más difícil de mantener, permite desarrollar videojuegos con mayor velocidad.
4.2.1 Modelo
El modelo de datos está basado en una jerarquía de objetos profunda que tiene su raíz en la clase entidad. A partir de la clase entidad se derivan todos los objetos del juego, como enemigos, puertas, paredes y el propio jugador. Estas entidades van asociadas a una única habitación, que a su vez están asociadas a una mazmorra.
Las entidades se subdividen en los siguientes tipos básicos:
• Ítems (llaves, armas, etc.)
• Efectos (disparos, partículas, etc.)
• Obstáculos y seres (cajas, enemigos, el jugador, etc.)
• Terreno (puertas, paredes, metas, etc.)
4. ELVIDEOJUEGO
Figura 4.3: Diagrama de clases del modelo de datos del videojuego.
Las habitaciones disponen las entidades en una cuadrícula. Es posible que haya varias entidades en la misma casilla, pero no todas las entidades pueden compartir casilla. Además de la entidades las habitaciones también tienen conexiones con otras habitaciones.
Las conexiones son objetos que conectan 2 habitaciones y actúan como aristas de un grafo, mientras que las habitaciones actúan como vértices. La mazmorra tiene acceso a ambos para poder realizar cómputos sobre el grafo comprendido por estos objetos.
4.2.2 Vista
La vista se separa en múltiples pantallas. Cada pantalla está pensada para ofrecer interacción con el jugador con un objetivo específico. Las pantallas son las siguientes:
• Pantalla de carga: Se encarga de ofrecer al usuario una forma de saber como va el proceso de carga de recursos mediante una barra de progreso. Una vez ha cargado pasa al menú principal.
• Menú principal: En el menú principal el jugador puede escoger entre crear una nueva partida o continuar con la partida anterior.
• Taberna: Al empezar una nueva partida o si al continuar no se estaba en una mazmorra se accede directamente a la pantalla de la taberna, donde el jugador ha de escoger la misión que quiere realizar.
• Pantalla de juego: Una vez escogida la misión se accederá directamente a la maz- morra. La pantalla de juego se encarga de ofrecer al usuario toda la información necesaria para jugar, como su vida, sus armas y la cuadrícula de la habitación en
4.2. El Motor
Figura 4.4: Diagrama de actividad de las pantallas del juego.
la que se encuentra. Para evitar un exceso de interfaces, esta parte se ha conecta- do directamente con el modelo de datos, de manera que cada entidad se encarga de dibujarse a si misma.
4.2.3 Control
El control está separado en múltiples clases:
• Control del juego
• Control de la generación de mazmorras
4. ELVIDEOJUEGO
• Control de serialización y guardado de datos
La clase de control del juego se encarga de controlar los turnos y distribuir el control entre las diferentes entidades de la habitación actual. También se encarga de distribuir el control a la generación de mazmorras y guardado de datos cuando es necesario. Para evitar una clase monolítica con el control de los turnos de todas las entidades del juego, la parte del control correspondiente a las acciones que ha de realizar cada entidad se ha delegado a las entidades. Esto hace que el modelo y el control se encuentren entrelazados, pero permite un desarrollo más rápido y mayor facilidad a la hora de leer el código, a costa de posibles problemas de coordinación entre las entidades.
La clase de generación de mazmorras incluye todos los algoritmos deGPC, los cuales se explicarán en el próximo capítulo, y se encarga de controlar la generación desde principio a fin. El control del juego se encarga de pasarle el control cuando el jugador se dispone a entrar en una nueva mazmorra.
La clase de serialización y guardado de datos se encarga de serializar el estado actual del juego y guardarlo en un archivo cada vez que sea necesario. Los algoritmos se han desarrollado intentando que sean invisibles para el jugador, es decir, que no se pause el juego a la hora de guardar. Para conseguir esto el guardado se realiza cuando el jugador pulsa el botón atrás o sale de la partida. Para que no se guarden estados a medias (por ejemplo a mitad de un movimiento) se utiliza un buffer en memoria para guardar el estado al principio de cada turno. Este buffer está pensado para que solo haga falta rehacer la serialización de la habitación actual (única en la que puede pasar algo), reduciendo así la cantidad de datos a serializar en cada turno.
C
APÍTULO5
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
6 fin
7 generar obstáculos fijos;
8 generar obstáculos rompibles;
9 generar enemigos;
Algoritmo 5.4:Generación de enemigos
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;
5.3 Generación de Obstáculos
Dependiendo de las armas que tenga el jugador en su poder, algunos obstáculos pueden romperse o no. Por tanto hay que tener en cuenta si el obstáculo se puede romper o no a la hora de colocarlos para evitar que el jugador se bloquee. Como el jugador no puede conseguir nuevas armas en una mazmorra, se puede diseñar la mazmorra teniendo en cuenta las armas del jugador a la hora de generarla.
Por tanto hay 2 tipos de obstáculos: aquellos que el jugador puede romper y aquellos que no puede romper (fijos). La clasificación de cada obstáculo se decide al principio de la generación dependiendo de las armas que tenga el jugador.
Los obstáculos que se pueden romper son los más fáciles de generar. Basta con colocarlos en posiciones aleatorias de la habitación (que estén libres).
Los obstáculos fijos son más complejos. Han de cumplir los siguientes requisitos:
• El jugador debe poder acceder a todas las puertas de la habitación.
• El jugador debe poder acceder a todos los espacios libres de la habitación.
El algoritmo que se ha creado permite asegurarse de que al colocar el obstáculo no se cierre ningún camino. Veralgo.(5.8) en la página siguiente,algo.(5.9) en la página siguienteyalgo.(5.10) en la página 38.
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.
A
PÉNDICEA
A NEXOS
A.1 Timetable
Más abajo se ofrece un timetable aproximado con el tiempo que ha ocupado cada parte del trabajo. Las horas se han medido separadas por diferentes tareas y por semana de trabajo. Los valores se han redondeado al entero más próximo.
A.2 Videojuego de Ejemplo
El juego se puede descargar desde Google Play buscando "GPC UIB".
Figura A.1: Timetable del trabajo.
