Carlos, Rey Emperador es un juego de estrategia ambientado en la epoca de Carlos V. Ademas de la simulacion del reino y de como las pol ticas utilizadas afectan a la delidad del pueblo, el juego presenta al usuario eventos historicos (reales o inventados para el juego) que debe intentar solucionar y cuyo resultado afecta a los siguientes sucesos en el juego. Para aumentar la rejugabilidad evitando caer en partidas repetidas con la misma sucesion de eventos, se han extendido los grafos de dependencias utilizados en otros juegos.
La generacion de contenido para videojuegos supone un gran porcentaje del tiempo invertido por el equipo de desarrollo. Una vez que este pasa a la etapa de produccion, desarrolladores, disen~adores y artistas se concentran en construir los niveles, personajes y comportamientos que haran que experiencia de juego sea lo mas larga posible.
Con los an~os, los disen~adores de juegos han ideado distintas formas de alargar las horas de juego de un t tulo eliminando la necesidad de construir niveles nuevos. Es lo que se conoce como rejugabilidad, o lo que es lo mismo, intentar que el usuario juege mas de una vez a cada nivel.
Existen dos mecanismos muy simples utilizados tradicionalmente. El primero es hacer que el comportamiento del juego (y por lo tanto los niveles a los que se enfrenta el usuario) tengan una componente aleatoria (piensese por ejemplo en el Tetris). Otro es proporcionar distintos niveles de di cultad, con la esperanza de que el jugador que termina el juego en un nivel facil vuelva a intentar completarlo en un nivel de di cultad mas complicado.
Otro mecanismo muy utilizado es poblar los niveles de coleccionables que el jugador debe intentar recoger pero que no comprometen el avance del jugador pues podra completar el juego sin recogerlos todos. El mero hecho de comprobar que a pesar de terminar el juego no se han recogido todos los objetos hace que muchos usuarios intenten los niveles de nuevo hasta conseguirlos todos. Esta estrategia tiene tanto exito que las distintas plataformas de juegos manejan ? Financiado por el Ministerio de Educacion y Ciencia (TIN2014-55006-R) sistemas de logros que, a modo de medallas virtuales, permiten a un jugador mostrar los exitos conseguidos en los distinto t tulos.
En el mundo de la narracion interactiva y de los juegos de aventuras es habitual encontrarse con juegos que ofrecen mas de un nal de forma que las acciones realizadas por el jugador en momentos concretos del juego determinan cual sera el camino de sucesos que seguira el juego. Este camino de sucesos pre jado puede ser ademas adornado con eventos aleatorios que el juego introduce para hacer de cada partida una experiencia unica.
Sin embargo, esta aleatoriedad puede estar ren~ida con la historia que el disen~ador quiere contar en ese camino de sucesos. Esto es especialmente delicado en juegos basados en hechos historicos reales.
En este art culo presentamos nuestra experiencia en el desarrollo del juego Carlos, Rey Emperador disponible para plataformas moviles (Android e iOS) y el modo en el que, utilizando una extension de los grafos de dependencias, logramos incrementar la rejugabilidad garantizando que el resultado nal del camino de sucesos que percibira el usuario se adhiere a lo ideado por el disen~ador.
La siguiente seccion describe como los grafos de dependencia han sido utilizados en juegos. La seccion 3 explica los retos que planteo la implementacion de Carlos, Rey Emperador y la extension de los grafos de dependencia que la hizo posible. La siguiente seccion explica los mecanismos de ejecucion necesarios para esos grafos extendidos. Tras ella, la seccion 5 entra un poco mas en detalle en la implementacion de los grafos y su uso en Carlos, Rey Emperador. La ultima seccion presenta unas pequen~as conclusiones. 2
Los grafos han demostrado ser una estructura de datos muy util en el mundo de los videojuegos. Los desarrolladores de juegos tiene entre su vocabulario conceptos como maquinas de estados, busqueda de caminos, A* o arboles de comportamiento, por mencionar algunos ejemplos.
Los grafos han sido estudiados intensivamente y categorizados segun sus propiedades. Los conocidos como DAG (del ingles, grafo dirigido ac clico, directed acyclic graph) son grafos cuyas aristas son dirigidas (tiene un origen y un destino) y no tienen ciclos.
Desde los an~os 60 se estan utilizando DAG como grafos de dependencias, siendo los diagramas PERT el ejemplo protot pico. En ellos cada nodo representa una tarea y una arista (dirigida) indica que la tarea asociada al nodo origen debe terminarse antes de que pueda comenzar la del destino. Para que el grafo de dependencias tenga sentido, este no debe contener ciclos (de ah que sea un DAG) pues en otro caso una tarea no podr a empezar hasta que ella misma no estuviera terminada.
Los grafos de dependencias se han utilizado en juegos como herramienta de disen~o. Su uso es muy natural en juegos de aventuras como la m tica serie Monkey Island, Grim Fandango o The Day of the Tentacle. En ellos, cada uno de los nodos representa un puzzle que debe ser resuelto por el jugador lo que abre la puerta (por disen~o) a que pueda abordar los siguientes puzzles. Las dependencias suelen darse debido a que resolver un puzzle proporciona un objeto o un conocimiento necesario para poder terminar otro.
Aunque un DAG general puede tener varios nodos sin dependencias, lo normal es que en estos juegos exista un unico nodo \ra z"1 que simboliza el principio del juego. De forma equivalente, los nodos terminales son puzzles resueltos que no abren otros puzzles; en ausencia de varios nales, unicamente hay uno de esos nodos que simboliza el juego completo.
Cuando existe un unico recorrido en orden topologico del DAG2 el usuario
percibira un juego completamente lineal y la rejugabilidad se vera comprometida.
Lo normal, sin embargo, es que existan puzzles que puedan completarse en orden
arbitario, lo que da como resultado distintos ordenes topologicos. Por poner un
ejemplo, en el grafo de dependencias de un juego como The Day of the Tentacle
(con un unico principio y un unico nal), el numero de recorridos topologicos
distintos supera los miles de millones [
Para an~adir variabilidad se pueden an~adir distintos nales al grafo. El alcance, no obstante, es limitado. Por un lado, tener varios nales requiere un gran esfuerzo de generacion de contenidos. Por otro lado, el hecho de que el jugador pueda seguir avanzando por las distintas ramas o historias alternativas hace que en la practica un usuario pueda explorar en una unica partida practicamente la totalidad del juego. Eso es debido a que tal y como hemos descrito el DAG, este no tiene nodos disyuntivos que bloqueen el acceso a algunos de los vertices sucesores y den acceso a otros. 3
Los grafos de dependencias son tambien utiles en otros juegos no tan centrados en puzzles marcando el progreso del juego y determinando su nal. Pensamos por ejemplo en juegos de simulacion o estrategia en donde el objetivo principal del juego no es resolver todos los retos presentados sino terminar con una serie de recursos o puntos.
En estos juegos de estrategia, a la parte de simulacion se le une la aparicion de situaciones que el usuario debe resolver. Estas situaciones o retos pueden haber sido jadas de antemano por el disen~ador para aparecer en ese momento concreto del juego o pueden formar parte de un conjunto de eventos que el motor dispara de forma aleatoria. 1 En el sentido de no tener dependencias, no en el sentido de nodo especial en arboles. 2 El recorrido topologico es aquel que visita todos los nodos del grafo de tal forma que todas las dependencias de un nodo han sido visitadas antes que el propio nodo.
En el caso del juego Carlos, Rey Emperador desarrollado por los autores, quer amos que esa parte de eventos tuviera gran peso desde el punto de vista del disen~o. En concreto, entre los objetivos que ten amos en mente estaban: { Que cada partida jugada correspondiera con una epoca historica concreta de la vida del rey Carlos V. { Que la simulacion, por lo tanto, comenzara en unas fechas historicas dadas. { Que cada partida fuera distinta, presentando al jugador situaciones o sucesos distintos en cada una de ellas. { Que, a pesar de esa necesaria aleatoreidad, cada partida no incurriera en contradicciones al presentar situaciones incoherentes con el momento historico, estado de la simulacion o sucesos ocurridos anteriormente en la partida. { Que algunos de los eventos tuvieran rigor historico (es decir, fueran eventos reales acaecidos en las fechas en las que se encontrara la simulacion). { Que el disen~ador pudiera crear otros eventos inventados asignandoles unas fechas historicas plausibles en los que podr an haber ocurrido.
La plausibilidad historica en la aleatoriedad recuerda a los grafos de dependencia de la seccion anterior. Igual que en un juego como The Day of the Tentacle primero hay que encontrar el laboratorio del Dr. Fred antes de conseguir el sello que te permitira mucho despues enviar una carta, en un juego como Carlos, Rey Emperador el jugador tiene primero que conseguir el beneplacito de su madre, la reina Juana, antes de conseguir que su hermano Fernando le reconozca como el verdadero sucesor. Y si el juego no decide activar el reto del beneplacito de Juana no debe despues disparar el de la delidad del hermano.
Sin embargo, los grafos de dependencias descritos no permiten implementar todos los puntos anteriores. Para hacerlo posible, planteamos una extension de los mismos consistente en enriquecer la informacion de los nodos y de nir dos tipos de dependencias distintas entre ellos.
Antes de entrar en detalle sobre la extension, debemos destacar el cambio en tanto en el uso del grafo de dependencias como en la interpretacion que le daremos a los nodos.
En primer lugar, el grafo de dependencias descrito en la seccion anterior era fundamentalmente una herramienta de disen~o. Las dependencias entre los distintos puzzles se daban porque al resolver un puzzle se habr a la posibilidad de resolver el siguiente. Por ejemplo, cuando el jugador consigue entrar en el laboratorio del Dr. Fred antes mencionado, podra encontrar oculto en el el sello que an~adira a su inventario. Pero durante la ejecucion del juego no existe el grafo de dependencias expl citamente. El juego no necesariamente conoce que nodos (puzzles) han sido ya resueltos, cuales estan \abiertos" y pueden ser solucionados y cuales siguen bloqueados. Como veremos mas adelante, el uso de los grafos que proponemos mantiene en memoria que nodos estan siendo ejecutados en cada momento y monitorizan su terminacion.
En segundo lugar, en esos grafos un nodo representa un puzzle que el jugador tiene que superar para avanzar. El puzzle esta ah esperando a ser resuelto por el jugador y seguira estando hasta que este lo complete. En el caso de juegos de estrategia o simulacion en los que se aplica nuestra extension, los nodos representan eventos o retos que presentaremos al jugador, como tener que conseguir el beneplacito de su madre. No son puzzles que esten disponibles en cualquier momento, sino retos que se disparan en momentos concretos y que el jugador debe resolver en un espacio limitado de tiempo antes de desaparecer. 3.1
En los grafos de dependencias descritos anteriormente cada uno de los nodopuzzle ten an un unico tipo de dependencia (o precondicion): aquella relacionada con la nalizacion de otros nodo-puzzles del propio grafo.
Sin embargo, la naturaleza del propio nodo puede imponer unas condiciones adicionales. La primera extension a los grafos de dependencia, pues, consiste en an~adir informacion adicional a los nodos con las condiciones externas al grafo que deben cumplirse para que un nodo pueda activarse.
Esas precondiciones del nodo dependen del estado de la simulacion. En el caso de juegos con una fuerte componente historica, son especialmente importantes las precondiciones temporales que pueden limitar las fechas en las que puede activarse el nodo. De esta forma, existiran nodos con todas todas las dependencias satisfechas (todos los nodos de los que depende han sido completados) pero que no puede ser seleccionada porque su fecha de activacion ya ha expirado (o aun no se ha llegado a ella). 3.2
En juegos de tipo puzzle como los mencionados en la seccion anterior, no se distingue entre puzzle no resuelto y puzzle no intentado. Es decir, los puzzles no se consumen al ser intentados y no resueltos, sino que el jugador tiene la opcion de intentar superarlo una y otra vez. Por ejemplo, si un puzzle consiste en conseguir abrir una puerta (y para eso hay que encontrar distintos objetos por el escenario), la puerta o bien esta abierta (puzzle resuelto) o bien esta cerrada (puzzle aun no resuelto); pero no hay un estado en el que el jugador ha intentado abrir la puerta y al no conseguirlo la ha bloqueado para siempre.
La extension que proponemos permite especi car dos resultados a un nodo: completado con exito y terminado con fracaso. Las aristas que unen los distintos nodos del DAG, pues, estan etiquetadas con el tipo de resultado necesario del nodo origen para activar esa arista/dependencia. 3.3
Dado que los grafos de dependencia tradicionales no se hacen expl citos durante la ejecucion, el resultado de la consecucion de un puzzle no se encuentra almacenado en la informacion asociada al nodo del puzzle.
En nuestro caso los nodos s se almacenan en memoria y por tanto el responsable de su ejecucion puede ser el que aplique sobre la simulacion el resultado de completar con exito o fracaso ese nodo.
La ejecucion del grafo puede separarse en dos: la parte encargada de gestionar que nodos son seleccionables en cada momento (nodos abiertos a partir de ahora) y la que se encarga de poner a ejecutar esos nodos disponibles.
Si, como en el caso de Carlos, Rey Emperador, los nodos tienen restricciones temporales, la gestion de los nodos abiertos debe tener en cuenta tanto las dependencias del propio grafo como esas restricciones. 4.1
El encargado del seguimiento del grafo (o tracker ) mantiene, ademas de la informacion del grafo: { Fecha actual de la simulacion. { Lista con los nodos abiertos, entendiendo estos los que tienen todas sus dependencias satisfechas (los nodos de los que dependen han tenido el resultado necesario) y ademas se cumplen sus restricciones temporales (la fecha de la simulacion permite su activacion). { Cola de prioridad con los nodos cuyas dependencias se han satisfecho pero cuya fecha m nima de activacion aun no ha llegado. Estan ordenados por la fecha mas baja en la que se pueden activar. { Informacion sobre el numero de dependencias pendientes de satisfacerse de los nodos que aun no se han abierto. En el arranque coincide con el grado de entrada de cada vertice del grafo y despues se va actualizando cuando se van completando los nodos.
La gestion de la simulacion es responsable de noti car al tracker del cambio de fechas para que este actualice sus nodos abiertos. El algoritmo que actualiza los nodos aparece en la gura 1.
Para ganar algo de e ciencia en la implementacion se podr a utilizar tambien una cola de prioridad para los nodos abiertos ordenando esta vez por la fecha del nal del intervalo. No se recomienda esta opcion porque di culta la implementacion de otras partes del tracker. Una de ellas es la retirada de los nodos abiertos cuando este es informado de que el juego ha activado uno de los nodos y se lo ha presentado al usuario.
Cuando el usuario completa (ya sea con exito o fracaso) el evento asociado a uno de los nodos activados, el tracker debe actualizar los nodos abiertos. Para eso decrementa el numero de dependencias de los nodos adyacentes y si alguno queda sin dependencias lo an~ade a las listas correspondientes. El algoritmo que aparece en la gura 2 se encarga de actualizar el tracker cuando el jugador completa con exito un nodo. La version de completar un nodo con fracaso es equivalente.
La ultima responsabilidad del tracker es dar al ejecutor la lista de nodos que pueden ser ejecutados en un momento dado. En un grafo libre de precondiciones en los nodos, esa lista coincide con la de los nodos abiertos pues contiene f 7 9 11 13 15 17 19 21 g 1 // Date c u r r e n t D a t e ;
// L i s t <Node> openNodes ; 3 // P r i o r i t y Q u e u e <Node> w i t h o u t D e p e n d e n c i e s ; 5 void advance ( int days ) c u r r e n t D a t e += days ; // Quitamos l o s e x p i r a d o s f o r e a c h ( Node n : openNodes ) i f ( n . NotAfter < c u r r e n t D a t e )
openNodes . remove ( n ) ; // An~adimos l o s nodos s i n d e p e n d e n c i a s // cuya f e c h a s e acaba de a l c a n z a r while ( ! w i t h o u t D e p e n d e n c i e s . empty ( ) &&
w i t h o u t D e p e n d e n c i e s . f i r s t ( ) . NotBefore <= c u r r e n t D a t e ) f openNodes . Add( w i t h o u t D e p e n d e n c i e s . f i r s t ( ) ) ; w i t h o u t D e p e n d e n c i e s . p o p F i r s t ( ) ; todos los vertices cuyas dependencias ya se han satisfecho y ademas cumplen las restricciones temporales. Sin embargo, si los nodos han sido extendidos con precondiciones relacionadas con el estado de la simulacion, el tracker ltrara la lista antes de devolverla. 4.2
Entendemos por ejecutor al elemento responsable de disparar los eventos y presentarlos al usuario. Es el el responsable de decidir, de entre todos los nodos disponibles, cuales pone a ejecutar.
Su implementacion esta muy ligada al juego y de hecho puede tener sentido utilizar ejecutores distintos en el mismo juego.
Sea como sea, la implementacion del ejecutor utilizara el tracker explicado anteriormente. Regularmente le pedira cuales son los nodos que pueden poner a ejecutarse y decidira si lanza alguno o no. Si lanza uno, sera el el responsable de vigilar su progreso y comprobar si este se completa con exito o fracaso para actualizar el tracker interno.
Es en el ejecutor donde reside la capacidad de construir partidas distintas y fomentar la rejugabilidad. En un extremo tenemos ejecutores que activan todos los nodos abiertos; en el otro extremo tenemos aquellos que no activan ninguno.
Las dos alternativas hacen que todas las partidas sean iguales. f o r e a c h ( Edge e : graph . Edges ( n ) ) f i f ( e . I s S u c c e s s ) f g
Node v = e . t a r g e t ( ) ; numDependencies [ v] ; i f ( numDependencies [ v ] == 0 )
w i t h o u t D e p e n d e n c i e s . add ( v ) ; g // Abrimos t o d o s l o s nuevos que hayan p o d i d o a p a r e c e r // r e u t i l i z a n d o e l metodo a n t e r i o r , simulando que no // han pasado d a s .
advance ( 0 ) ; f 3 5 7 9 11 13 15 17 g Idealmente, las implementaciones deben permitir con gurar la probabilidad de seleccion de un nuevo evento, limitar el numero de eventos activos en cada momento y otros parametros. Si el juego lo requiere, se pueden tener nodos de ejecucion obligatoria que el ejecutor debe activar siempre, una vez satisfechas sus dependencias y precondiciones y cuya existencia debera tener en cuenta el ejecutor. Estos sucesos pueden penalizar la rejugabilidad al aparecer en todas las partidas pero son indispensables para la construccion de las fases de tutorial. 5 Implementacion en Carlos Rey Emperador La extension de los grafos de dependencias la hemos puesto en practica en el juego Carlos, Rey Emperador. Es un juego de estrategia en el que el jugador hace las veces de Carlos V, decidiendo pol ticas, estableciendo alianzas y entrando en guerra con reinos vecinos entre otras cosas.
Durante cada partida, que se juega en un periodo concreto de la vida del monarca, al jugador se le van presentando distintas situaciones o retos que debe ir superando, que se corresponden con los nodos del grafo descrito anteriormente.
La gura 3 muestra una captura del juego en el momento en el que se muestra el reto en el que se pide al usuario que debe conseguir el beneplacito de su madre. Se ve tambien el resultado del nodo tanto si es completado con exito como con fracaso.
Para la implementacion del juego se utilizo Unity. Para permitir a los disen~adores crear los eventos y el grafo, se hizo una pequen~a adaptacion del editor que permit a, en una primera fase, de nir los eventos o sucesos posibles ( gura 4).
Las propiedades con gurables son fundamentalmente: { Descripcion del evento: incluye el texto a presentar al usuario, tipo de evento (para utilizarlo en el interfaz), etc. { Intervalo de fechas en el que es aplicable. { Precondiciones: en ellas se incluyen cosas como \el jugador debe tener en su reino los territorios X e Y". En la implementacion, ademas, es aqu donde ponemos las dependencias del grafo (nodos que han debido completarse con exito o fracaso), para evitar tener que dibujar el grafo expl citamente. { Descripcion de la ejecucion: que cosas tiene que hacer el jugador para completar el evento y algunos otros parametros. { Resultado del nodo: que ocurre en la simulacion cuando el reto se completa, ya sea correctamente o no. Cabe mencionar que aqu no se incluye que nodos se \abren" al terminar con el reto, pues las aristas se guardan como precondiciones en los nodos destino de las mismas.
En la produccion del juego se conto con una historiadora experta en la epoca de Carlos que superviso la creacion de la coleccion con los casi 400 eventos tanto historicos reales como inventados para el juego.
Con esos eventos creados, el disen~ador despues seleccionaba el subconjunto que deb a utilizarse para cada una de las partidas/misiones. En la gura 5 aparece una vista parcial de la de nicion de las propiedades de una partida. Como se aprecia, desde el editor de Unity se puede con gurar los parametros del ejecutor, que incluye el tiempo m nimo y maximo que se puede esperar para lanzar un nuevo suceso, el numero maximo de eventos lanzados simultaneamente y la probabilidad de lanzar un nuevo evento.
Los grafos son una herramienta muy util en el desarrollo de videojuegos, para representar, implicita o expl citamente, informacion de muy diferente naturaleza. Los grafos dirigidos ac clicos (DAG) son utiles para almacenar informacion de dependencias, de ah que surjan de manera natural en los juegos de aventura, entre los que se encuentran las sagas clasicas de la desaparecida LucasArts.
En ellos, sin embargo, no se representa de manera natural la posibilidad de que el jugador pueda fallar de manera irreversible un determinado puzzle (nodo), o que estos tengan precondiciones adicionales a las modelizadas por el propio DAG.
En los juegos de estrategia estas necesidades se hacen mas patentes si los eventos que ocurren durante un nivel para retar al jugador se almacenan tambien usando un DAG. Por ejemplo, la puesta en marcha de un evento puede tener sentido unicamente si antes se produjeron otros, y el usuario los completo con exito. Ademas, si se quiere aumentar la rejugabilidad, es importante que diferentes partidas tengan diferentes eventos, y el juego debera garantizar la coherencia de todos ellos en funcion de sus restricciones.
El metodo de generar contenido para el juego teniendo en cuenta que ciertos
eventos han de haberse producido anteriormente es una forma incompleta de
plani cacion que conecta nuestro trabajo con investigacion en narracion
interactiva [
En este art culo hemos descrito el modo en el que se representaron los eventos en el juego Carlos, Rey Emperador usando un DAG, y como se utilizo en ejecucion para mantener el control de los eventos a lanzar. En todo momento se tuvo presente la necesidad de asegurar la coherencia, la plausabilidad historica y un rendimiento optimo, especialmente importante en el desarrollo de juegos para dispositivos moviles.