Aviso: este artículo es bastante largo, aunque no demasiado técnico, así que debería ser fácil de seguir.
Desde hace bastantes años siempre he tenido la idea de portar las reglas del Dungeons and Dragons (o algo similar) al ordenador, pero siempre he terminado fracasando por varios motivos:
- Son sistemas muy complicados.
- Están llenos de excepciones.
- Tienen que ser muy extensibles porque seguramente aparecerán nuevas reglas con el paso del tiempo.
Estos días he tenido bastante tiempo libre y he decido intentar por n-esima vez hacer un “mini-framework” que me permita implementar algo parecido a una simplificacón del sistema d20 para mis propios proyectos. El resto de este artículo va a tratar de los problemas que he encontrado para realizar esta implementación básica (aún le faltan muchas cosas). Al final de todo hay un link con el código fuente para él que le quiera echar un vistazo.
El primer problema que me he encontrado siempre al intentar hacer este tipo de sistemas es que los objetos tienen muchísimas propiedades. Por ejemplo un personaje tiene atributos, habilidades, dotes, conjuros, equipo, clases,… A pesar de agrupar en clases y usar todas las herramientas que proporciona la programación orientada a objetos siempre he terminado teniendo en cada clase un ejército de propiedades que se vuelve inmanejable.
Así que decidí atacar el problema de otra forma: cada clase tiene una tabla hash que representa sus propiedades. De esta forma cada clase puede tener “infinitas” propiedades y además las puedo definir cuando quiera. Si quiero una propiedad hago:
objeto.Set("Propiedad", valor);
Y si quiero obtener el valor hago:
object resultado = objeto.Get("Propiedad");
La verdad que casi cualquiera que vea esto pensará que esta aproximación tiene muchos problemas:
- Se usan strings para los nombres de las propiedades y es muy fácil equivocarse al escribirlos (confundir una mayúscula, una letra,…) y que el programa de un error o devuelva un valor erróneo. Depurar esto es un jaleo bastante serio.
- Hay que calcular hashes de strings todo el rato (una operación bastante lenta).
- No es tipada: tenemos objects por todos los lados que tenemos que castear al tipo correcto (lento y propenso a errores).
La verdad que yo mismo no estaba muy convencido de que esto fuera una buena idea hasta que me encontré este artículo de Steve Yegge donde habla del patrón prototype y de la programación basada en prototipos en vez de orientada a objetos.
El artículo, aún siendo largo, es bastante interesante y explica bastante bien que es y como se usan los prototipos. Resumiendo mucho: un prototipo es una tabla hash que contiene todas las propiedades y operaciones de un objeto (en vez de ser entidades independientes como en la programación orientada a objetos).
Dado que yo programo en C# y que este lenguaje no da soporte para prototipos (como por ejemplo IO), implementé las ideas del post de Steve en la clase Prototype. Esta clase contiene:
- Un campo parent que es el prototipo del que se “hereda”.
- Un campo properties que es el diccionario de propiedades.
- Una propiedad IsReadOnly que permite hacer al prototipo de solo lectura.
- Cuatro métodos (Get, Set, Contains y Remove) que permiten modificar la información del prototipo.
- Y un método Clone que permite crear un nuevo prototipo que herede del actual.
Lo único interesante de esta clase es que los métodos Get y Contains permiten buscar valores en el padre del prototipo. Es decir, parent cumple la función de la superclase en la programación orientada a objetos. Como podéis ver, esta implementación no es nada complicada y permite hacer cosas como:
Prototype guardia = new Prototype();
guardia.Set("Ataque", 10);
guardia.Set("Vida", 5);
Prototype alitar = guardia.Clone();
alitar.Set("Nombre", "Alitar");
alitar.Set("TieneMiedoALosDragones", true);
Como se puede ver, he definido un guardia prototipo y luego un guardia especial que he llamado Alitar y que tiene miedo a los dragones. Alitar se comportará como cualquier otro guardia, pero cuando vea un dragón huirá en vez de luchar (¿quizás también tendría que ponerle más inteligencia? :p).
Una vez resuelto el problema fácil, queda el difícil (y bastante más interesante): calcular lo que vale una variable en un RPG. Por ejemplo: ¿cuanto vale el bonificador de ataque cuerpo a cuerpo de un personaje? En el d20 este número depende de muchísimas cosas:
- La fuerza del personaje (o la destreza según que arma esté usando y si tiene las dotes adecuadas).
- El nivel de cada clase del personaje.
- Sus dotes.
- Conjuros.
- Otras habilidades o modificadores circunstanciales.
Básicamente calcular ciertos valores en un RPG es un lío increíble. Hace tiempo descubrí una herramienta llamada PCGen que es un generador de personajes para el sistema d20. Esta herramienta tiene un lenguaje de definición de reglas muy potente, por ejemplo:
BONUS:COMBAT|AC|Level / 2|TYPE=NaturalArmor.REPLACE
Esta línea significa un bonificador de combate a la armadura (AC) igual al nivel del personaje dividido entre dos, del tipo armadura natural que reemplaza a cualquier bonificador existente del mismo tipo. Este ejemplo es bastante básico, pero hay verdaderas virguerías definidas con él.
Así que realmente el segundo problema son dos subproblemas:
El primer subproblema es “sencillo” de resolver si uno no se complica mucho la vida. En mi caso decidí imponer a las expresiones la restricción de que las diferentes partes que la forman deberían estar separadas por un espacio. Esto me permite partir la expresión con una sola llamada a String.Split. Luego un simple parser recorre los pedazos de la expresión y los clasifica en cuatro tipos:
-
Números: 3, 5.7, 23434,…
-
Operadores: +, –, *, /, ^
-
Símbolos: (, )
-
Variables: cualquier otra cosa
Esto debería ser suficiente para definir cualquier tipo de operación matemática que pueda ser de utilidad. En el fichero ExpressionParser.cs se puede ver el código de este pequeño parser. Una cosa “curiosa” del código es que al final del parseo se ejecuta una función llamada ShuntingYard. Esta función implementa el algoritmo de Shunting-Yard inventado por Djikstra que permite pasar expresiones en formato infijo (2 + 3) a formato postfijo o notación polaca inversa (2 3 +).
¿Y por qué hacer semejante cosa? Porque la notación postfijo tiene una gran ventaja: es muy fácil de evaluar. Estoy seguro que hacerse un evaluador de expresiones en formato infijo no es demasiado difícil, pero en formato postfijo es trivial y el coste de transformar la expresión es muy bajo (y solo hay que pagarlo una vez).
Y por último hay que ver como buscar los modificadores que afectan a una variable y como calcular su valor. Imaginemos que tenemos un objeto Espada definido de esta forma:
Prototype arma = new Prototype();
arma.Set("Nombre", "Espada");
arma.Set("Dureza", 5);
Para obtener su dureza basta con escribir:
int dureza = arma.Get<int>("Dureza");
Ahora imaginemos que cojo a la Espada y la modifico añadiéndole otro prototypo que representa que está hecha de Mithril, lo que le da una dureza extra.
Para calcular su dureza ahora hay que buscar en sus modificadores pero también en los del objeto Mithril. En el siguiente diagrama se puede ver un ejemplo un poco más complicado:
Se puede ver que se ha formado una estructura en forma de árbol, así que para buscar los modificadores decidí utilizar una búsqueda en anchura: primero la raiz, luego los hijos, luego los hijos de los hijos,…
Pero ahora imaginemos que esa espada está en manos de un personaje que es de la clase bárbaro, y que los bárbaros hacen que todos los objetos en sus manos sean menos duros (porque tienden a romperlos).
Como se puede ver la dureza del arma ha sido modificada por un valor que no está en sus hijos, si no que está en otra parte del árbol. Así que hay que modificar un poco la búsqueda en anchura:
Pero sigamos imaginando: ahora el personaje también tiene una Armadura y esta a su vez es de Adamantio.
Está claro que si pregunto por la dureza de la Espada no debería influir para nada los modificadores a la dureza de la Armadura o del Adamantio. Para resolver este nuevo problema hay que añadir una nueva propiedad a los modificadores: visibilidad (global o local). Y hay que volver a cambiar la búsqueda en anchura:
-
Se guarda el nodo que inició la búsqueda (la Espada).
-
Se comienza la búsqueda desde la raíz (el Personaje).
-
Si el modificador está en un nodo fuera del subárbol definido por el nodo que inició la búsqueda, solo se aplicarán los modificadores globales. Si el modificador está definido en un nodo perteneciente al subárbol se aplicarán todos los tipos de modificadores.
La búsqueda se inició en el objeto Espada, así que fuera del subárbol que define (marcado en rojo) solo se aplican los modificadores marcados como global. Así conseguimos que se aplique el modificador de Bárbaro pero no el de Armadura o Adamantio.
Esta forma de buscar modificadores cubre todos los casos que se me han ocurrido. Seguro que hay situaciones que no resuelvo, pero no me pienso complicar más la vida (de momento y sin una buena razón).
Ya está la búsqueda de modificadores, ahora queda ver como calcular el valor de una variable. El valor de una variable es modificado por los objetos de tipo Modifier que a su vez contienen expresiones matemáticas en forma de objetos Expression. Estas expresiones pueden ser simples como hemos visto hasta ahora o depender de otras variables, por ejemplo:
Ahora la dureza de la Espada depende de su peso también. Para resolver esto la evaluación de variables se ejecutará de la siguiente manera:
-
Cuando se comienza a evaluar una variable se apunta en una tabla de variables calculadas con el valor de menos infinito.
-
Si esta variable tiene un modificador que contiene una variable, se consulta a la tabla de variables ya calculadas.
-
Si el valor de la variable es menos infinito hay una referencia circular (variable = variable) y el valor no se puede resolver. Excepción.
-
Si es otra cosa se devuelve el valor y se continúa evaluando la variable actual.
-
Si la variable no se encuentra en la tabla de variables ya calculadas se inicia una nueva evaluación para esa variable (vuelta al principio de este proceso).
-
Cuando se termina de calcular el valor de una variable se actualiza en la tabla.
La clase Evaluator es la que se encarga de la búsqueda de modificadores y evaluación de variables.
El código fuente de todo este jaleo se puede descargar desde este link (está bajo licencia MIT así que se puede hacer cualquier cosa con él). El zip contiene una solución de Visual Studio 2008 (C#) que está compuesta de dos proyectos:
-
GravityAge.Statecraft.Core: el código de los prototipos y la evaluación de variables. Está bastante comentado así que debería ser fácil de comprender si se ha entendido este artículo.
-
GravityAge.Statecraft.Tests: unas cuantas pruebas unitarias para comprobar que todo está más o menos bien (debería hacer más, pero de momento con estas me basta). Hay una prueba que no se pasa (comprobar que una expresión infijo está bien formada) pero no sé como hacer que el parser se de cuenta de eso sin complicarme la vida demasiado, así que dejo el test roto para que no se me olvide que algún día debería solucionarlo.