Los arboles de comportamiento son la tecnolog a mas utilizada en videojuegos comerciales para programar el comportamiento de los personajes no controlados por el jugador, aunando una gran expresividad, con cierta facilidad de uso que permite la colaboracion entre programadores y disen~adores de videojuegos. En este art culo describimos un nuevo tipo de nodos en los BTs que representan consultas que devuelven sub-arboles en tiempo de ejecucion y explicamos como se pueden integrar en Behavior Bricks, un sistema que hemos desarrollado para la creacion y ejecucion de BTs.
La creacion de comportamientos para personajes con controlados por el
jugador (en ingles NPC, Non Playable Characters ) involucra, entre otros, a los
disen~adores y los programadores de inteligencia arti cial (o usando las siglas
inglesas, AI). Los disen~adores son los encargados de idear y describir las reglas
del juego (>Como se juega? y >A que se juega?) con el objetivo de que este sea
divertido, mientras que los programadores son los encargados de llevar esas ideas
a cabo. De entre todas las tareas de disen~o, la especi cacion del comportamiento
de los NPCs en una parte vital ya que afecta directamente a cuestiones como la
di cultad o las mecanicas de juego [
En este contexto con requisitos tan volatiles, es crucial minimizar en lo posible los problemas derivados de la comunicacion entre programador y disen~ador, intentando darle al disen~ador las herramientas necesarias para que sea el mismo el que implemente los comportamientos, haciendo que el programador intervenga lo menos posible. Un editor visual que le ayude a programar comportamientos de ? Financiado por el Ministerio de Educacion y Ciencia (TIN2014-55006-R) forma gra ca, sobre un modelo de ejecucion facil de comprender puede ayudar a esta tarea. Tradicionalmente se han utilizado muchas tecnicas que intentan presentar la logica de estos comportamientos de una forma mas simple para el disen~ador o para programadores menos cuali cados. Desde utilizar lenguajes de script, mas sencillos de entender, para extender los comportamientos, hasta utilizar modelos de ejecucion como las maquinas de estado o arboles de comportamiento que pueden ser representados gra camente y ademas manejan conceptos mas cercanos a la forma de pensar de un disen~ador. En los ultimos an~os, uno de los modelos mas utilizados son los llamados arboles de comportamiento (o en ingles Behavior Trees o BTs) por su versatilidad sobre otras tecnicas como describiremos en la seccion 2. Tanto esta tecnica como las tradicionales maquinas de estado, utilizan un conjunto de tareas primitivas de bajo nivel que son las que interactuan con el entorno del NPC realmente, ya que el ejecutor simplemente decide cuales de todas ellas debe ejecutar en un instante concreto. El problema surge cuando el juego va creciendo y se van creando nuevas tareas primitivas que van afectando a mas NPCs, por lo que an~adir una nueva forma de realizar una tarea, puede implicar modi car el comportamiento de varios tipos de NPCs. O en un caso aun mas extremo, que ni siquiera el disen~ador sepa expresar, usando las herramientas, que es lo que debe hacer el NPC o como debe hacerlo. En estos casos, se necesita un proceso iterativo de prueba y error que implica una modi cacion de la especi cacion tanto en el lado del disen~ador, que debe cambiar su disen~o teorico del comportamiento, como en el del programador, que debe cambiar la implementacion de dichos comportamientos, an~adir nuevas tareas primitivas, etc.
En este art culo se describe una extension de los BTs que facilita el proceso iterativo de disen~o del comportamiento. Madiante tecnicas de razonamiento basado en casos (Case-based reasoning, CBR), permite a los disen~adores crear comportamientos aportandoles ejemplos. Estos ejemplos pueden generarse bien interactivamente entrenando al NPC, o bien a partir de diferentes implementaciones de la tarea a aprender, usandolas en diferentes contextos. La decision de cual de las posibles alternativas se ejecutara, se relega al momento de ejecucion. Ademas de asistir al disen~ador, esta tecnica permite crear comportamientos menos previsibles desde el punto de vista del jugador, lo que incrementa la sensacion de que los NPCs tienen un comportamiento mas humano y menos predecible. Adicionalmente, este nuevo modelo de ejecucion diferido soporta otras caracter sticas como permitir que los comportamientos soporten nuevas formas de resolver una tarea sin modi car su estructura o crear comportamientos que vayan aprendiendo con el tiempo la mejor forma de resolver una tarea.
El resto del art culo se estructura de la siguiente manera: en la seccion 2 se describe que son los arboles de comportamiento, en la seccion 3 se revisa el trabajo relacionado, en la seccion 4 se explica que es Behavior Bricks, nuestra herramienta de creacion de comportamientos, en la seccion 5 mostramos nuestra propuesta de extension de BT y Behavior Bricks y nalmente en la seccion 6 describimos las conclusiones y trabajo futuro.
Los BTs [
Estas tareas pueden usarse en los nodos hoja de los BTs o bien en ciertos nodos intermedios especiales que toman decisiones de control.
Cuando la ejecucion de un nodo termina, este noti ca a su nodo padre si la ejecucion de la tarea tuvo exito (Success) o no (Failure). Los nodos intermedios utilizaran esta informacion proveniente de sus nodos hijo para tomar la decision de cuales ser an los siguientes nodos a ejecutar (dependiendo del tipo de nodo intermedio). Algunos de los nodos intermedios mas utilizados son los siguientes: { Secuencia: ejecuta una lista de comportamientos hijo del nodo en el orden que se han de nido. Cuando el comportamiento que esta ejecutandose actualmente termina con exito, se ejecuta el siguiente. Si termina con fallo, el tambien lo hace. Devolvera Success si todos se han ejecutado con exito. { Selector: tiene una lista de comportamientos hijo y los ejecuta en orden hasta encontrar uno que tiene exito. Si no encuentra ninguno, termina con fallo. El orden de los hijos del selector proporciona el orden en el que se evaluan los comportamientos. { Parallel: ejecuta a la vez todos sus comportamientos hijo. Esta ejecucion no debe necesariamente ser paralela (en varios nucleos), sino que puede realizarse entrelazada; lo importante es que ocurre simultaneamente dentro de la misma iteracion del bucle de juego. Los nodos parallel pueden tener como pol tica de nalizacion la del nodo secuencia (acabar si todos los hijos lo hacen), o la de los selectores (acabar si uno de sus nodos hijos lo hace). { Selector con prioridad: los nodos selector llevan incorporada una cierta prioridad en el orden de ejecucion, pero no re-evaluan nodos que ya han terminado. El selector con prioridad (priority selector) se diferencia del selector normal en que las acciones con mas prioridad siempre intentan ejecutarse primero en cada iteracion. Si una accion con mayor prioridad que otra que ya se estaba ejecutando puede ejecutarse, se interrumpe la accion que se estaba ejecutando anteriormente. { Decoradores: son nodos especiales que solo tienen un hijo y que permiten modi car el comportamiento o el resultado de ese hijo. Algunos ejemplos son decoradores que repiten la ejecucion del hijo un numero de veces determinado, los que invierten el resultado del hijo (de exito a fracaso y viceversa) o aquellos que poseen una condicion adicional de forma que se ejecutara o no el hijo en base a si se cumple esa condicion. 3
El Razonamiento basado en casos (en ingles Case-based reasoning, CBR) [
La idea de extender los BTs con nodos terminales que no ejecutan una tarea
concreta sino un conjunto de posibles tareas, aplazando la decision de cual
ejecutar al momento de ser ejecutada, ya se ha explorado en trabajos previos con
la inclusion de nodos consulta [
Estos trabajos previos se basaban en la idea de que la informacion semantica que permit a seleccionar el BT a ejecutar, proviene de una descripcion semantica de dicho problema mediante una ontolog a. Esta informacion semantica describe el contexto idoneo en el que se debe utilizar dicho comportamiento. Esta informacion ha de ser introducida por el disen~ador, lo cual es poco exible y requiere de un trabajo extra por su parte que es, ademas, propenso a errores. Esta nueva aproximacion pretende proporcionar mecanismos para que la generacion de esa informacion semantica y los valores correctos de la misma, se aprendan automaticamente. De esta forma se simpli can las tareas que el disen~ador o los programadores deben realizar para mantener una ontolog a actualizada.
Tambien otros autores han utilizado otras tecnicas de aprendizaje automatico
con otros enfoques para intentar seleccionar el BT que mejor resolv a un
problema usando algoritmos geneticos [
Behavior Bricks1 es una herramienta cuya nalidad es el desarrollo de comportamientos inteligentes para videojuegos. Permite la incorporacion de tareas primitivas desarrolladas por los programadores para ser usadas en arboles de comportamiento, construidos por los disen~adores a traves de un editor visual integrado, lo que permite la colaboracion entre ambos, minimizando problemas de comunicacion y permitiendo que ambos trabajen en paralelo.
En Behavior Bricks se de ne como tarea primitiva al m nimo fragmento de codigo ejecutable por un comportamiento, que son las acciones y condiciones de los BTs. Estas primitivas se de nen mediante un nombre (unico en toda la coleccion) que determina la semantica de la accion o condicion y opcionalmente, una lista de parametros de entrada (Y tambien de salida en el caso de las acciones). Estas primitivas deben ser escritas por los programadores en C#.
Las acciones primitivas constituyen los \ladrillos" basicos para la creacion de comportamientos por parte de los disen~adores. La posibilidad de parametrizar estas primitivas las dota de generalidad, lo que permite que un estudio de videojuegos pueda, con el tiempo, construirse una biblioteca de acciones y condiciones reutilizables entre proyectos. Para permitir la comunicacion entre las diferentes tareas, los parametros de entrada y salida de las mismas leen y escriben de un espacio de memoria compartido al que denominamos la pizarra del comportamiento. Estos parametros se deben asociar a las variables de la pizarra en el disen~o del comportamiento, permitiendo interrelacionarlas. La informacion almacenada en estas pizarras es lo que denominamos contexto del comportamiento.
Al igual que las primitivas, los comportamientos construidos por los disen~adores tambien pueden tener parametros de entrada y de salida. Esto permite que dichos comportamientos puedan ser reutilizados en otros BTs como tareas primitivas.
La extension que proponemos en este trabajo surge de forma natural gracias a esta ultima caracter stica: si los BTs ya construidos pueden colocarse en otros BTs mas generales como nodos hoja, podemos ver esos BTs como de niciones de tareas primitivas implementadas con arboles en lugar de directamente en codigo. La tarea implementada con ese BT puede ser un nuevo tipo de tarea primitiva que pasa a estar disponible en la coleccion o una implementacion distinta de una tarea primitiva ya existente.
Por lo tanto, dada una tarea, podemos tener un conjunto de posibles implementaciones de dicha tarea que podemos utilizar. Para poder hacer esta asociacion, los parametros de entrada y de salida de la tarea a implementar y el comportamiento que la implementa deben coincidir en numero y tipo.
Behavior Bricks se compone de dos partes: el motor de ejecucion de comportamientos y el editor de esos comportamientos. Aunque el motor de ejecucion es aseptico y puede ser utilizado en cualquier juego que sea capaz de ejecutar codigo en C#, el editor esta hecho como plug-in para Unity3D 2.
La gura 1 muestra el aspecto del editor. que esta implementado usando
UHotDraw [
Las acciones primitivas en Behavior Bricks son implementadas por los programadores usando C#. Para proporcionar tanto le nombre, como los parametros de entrada y salida se usa atributos de C#. Las acciones se implementan heredando de una superclase con un conjunto de metodos que deben ser sobrescritos y que son invocados por el interprete durante el ciclo de vida de la accion. De ellos, el mas importante es OnUpdate(), llamado en cada iteracion del ciclo del juego, y que debe devolver si la accion ha terminado ya (con exito o fracaso) o debe seguir siendo ejecutada en la proxima iteracion.
Las condiciones evaluan el estado del mundo permitiendo determinar si se cumplen ciertas reglas. Al igual que las acciones, las condiciones primitivas son tambien implementadas por los programadores utilizando los mismos mecanismos (atributos de C# y herencia). En este caso, el metodo sobrescrito sera Check(), que devolvera un valor booleano. 4.3
En la industria hay cierto recelo a la hora de permitir a los disen~adores crear comportamientos, incluso si disponen de una herramienta que les facilite la
tarea, soliendo encargarse principalmente de supervisar el comportamiento [
Entre los profesionales dedicados al disen~o de videojuegos existen algunos con un per l mas tecnico y otros que practicamente no tienen conocimientos informaticos. Los disen~adores no tecnicos podr an tener problemas para crear un comportamiento completo usando el editor, por lo que nuestra metodolog a propone dividir los comportamientos generales en comportamientos a bajo nivel y comportamientos a alto nivel.
Cuando pensamos en un comportamiento a alto nivel lo hacemos viendo
dicho comportamiento como una descripcion simple del comportamiento
general de un NPC, similar a lo que los disen~adores suelen hacer en los primeros
prototipos del juego [
Para clari car estos conceptos, la gura 2 muestra un esquema del reparto de responsabilidades que de ne nuestra metodolog a de uso de Behavior Bricks. 5
En el proceso de creacion del comportamiento, asumimos que el disen~ador sabe
como debe comportarse el NPC, pero vamos a suponer que estamos en un
estado temprano de desarrollo del juego en el que los comportamientos de los
NPCs aun no estan claros. Incluso con la separacion de tareas descrita en
nuestra metodolog a, la comunicacion entre programador y disen~ador debe ser uida
y constante en estos primeros compases. Imaginemos que nuestra biblioteca de
tareas primitivas por sucesivos proyectos desarrollados, empieza a ser de un
gran taman~o y esta llena de comportamientos similares pero que tiene distintos
matices de implementacion. >Cual de ellos debe usar el disen~ador?
Primeramente puede que ni siquiera lo tenga claro; puede incluso que el programador
este ocupado haciendo otras tareas y el disen~ador no disponga de conocimientos
su cientes como para crear comportamientos a bajo nivel que se adapten a sus
necesidades.>Que alternativas tiene el disen~ador en este contexto? Puede esperar
a que esas tareas a bajo nivel sean implementadas, puede intentar ir probando
todas las tareas similares que encuentre en la biblioteca o aventurarse a
implementar una nueva tarea por s solo. Nosotros proponemos una extension de
Behavior Bricks y de los BTs en general, basada en la idea de incorporar un nuevo
nodo hoja denominado Query Node, descrito en [
A modo de ejemplo, imaginemos que el disen~ador dispone de multitud de
implementaciones diferentes de la accion Attack. Por ejemplo: puede atacar cuerpo
a cuerpo, desde lejos, puede intentar rodear al enemigo antes de atacarle, o
puede autodestruirse si ve que sus posibilidades de victoria son escasas. >Cual
es la mas adecuada? En [
Por un lado, no todos los comportamientos son utilizables en todos los NPCs. Tampoco el disen~ador quiere que sus NPCs puedan atacar de todas las formas implementadas posibles. As que debe haber algun tipo de prerrequisito para poder usar una tarea o un comportamiento.
En la de nicion de las tareas primitivas an~adimos un nuevo metodo: bool CheckPrerequisites() que informa al comportamiento que lo ejecuta de las restricciones de dicha tarea. Imaginemos por ejemplo en el caso de la accion Attack, que para poder usar el ataque a distancia, el NPC debe disponer de un arma a distancia, o solo ciertos enemigos de cierto nivel son capaces de rodear antes de atacar o que para poder autodestruirse, el NPC debe tener una bomba. Este mecanismo permite de forma sencilla para el programador de la accion describir que restricciones de uso son las que precisa dicha accion. Estas restricciones pueden ser supervisadas por el disen~ador e incluso an~adir nuevas restricciones adicionales de disen~o en el nodo Query, (por ejemplo que la accion a ejecutar sea del nivel adecuado para el NPC o dependiendo de la di cultad del juego) usando una condicion previamente programada que el nodo chequea para cada posible comportamiento a elegir. No es necesario de nir los prerrequisitos de los comportamientos complejos creados por los disen~adores ya que estos se pueden inferir de las tareas primitivas y otros subcomportamientos que utilicen los comportamientos seleccionados por el nodo Query, simplemente chequeando todos lo prerrequisitos de todas las tareas que contenga el comportamiento.
As pues, cuando el nodo Query se ejecute, debera buscar en la base de casos aquellos que implementen la tarea a ejecutar que ha sido establecida en tiempo de disen~o y de entre ellos, preseleccionar aquellos que son ejecutables cumpliendo por un lado sus prerrequisitos y por otro lado la condicion de nida en el nodo Query. De todos estos candidatos se debe seleccionar cual es el mas adecuado. Si no hay ningun comportamiento recuperado, entonces se ejecutara la tarea primitiva establecida. 5.1
Cuando el nodo Query ha seleccionado el conjunto de posibles comportamientos a ejecutar, debe decidir cual de ellos ejecuta. Para ello el algoritmo recurre a una base de casos donde recupera cual de los candidatos a ejecutar se utilizo en unas circunstancias similares a las actuales. Para ello debemos guardar en esta base de casos la accion ejecutada y el contexto del arbol de comportamiento que la ejecuto (su pizarra o parte de ella). La informacion almacenada en la base de casos tendra entonces una lista de atributos con su valor en el momento de ejecutar el comportamiento. Utilizando una medida de similitud entre los parametros almacenados y los de la pizarra del comportamiento, seleccionaremos el comportamiento que se ejecuto en un contexto mas parecido al nuestro.
El problema aqu es hacer la correspondencia entre los parametros almacenados en las trazas de la base de casos y el estado del contexto del Query Node, ya que se necesita hacer una correspondencia semantica entre el nombre del atributo almacenado en la base de casos y el nombre del atributo de la pizarra del comportamiento que ejecuta el nodo Query. As que para poder hacer esta correspondencia, necesitamos etiquetar los parametros con una etiqueta semantica comun para todos los comportamientos. Estas etiquetas semanticas son creadas por los disen~adores en forma de una simple lista o relacionandolas por sinonimos mediante un tesauro si queremos una semantica mas rica. De esta forma, en vez de almacenar los nombres de la pizarra del comportamiento que genera la traza para la base de casos, se almacena su valor semantico. En la tabla 1 podemos ver la pizarra del comportamiento que ejecuta el nodo Query Attack.
En la tabla 2 podemos ver un ejemplo de una base de casos para la accion Attack con diferentes valores semanticos de los atributos y el resultado de similitud con el contexto actual mediante una distancia eucl dea simple como ejemplo ilustrativo de como realizar dicha recuperacion. Los marcados con guion no estan almacenados para el caso concreto ya que no son relevantes. En este ejemplo, nos quedar amos con la distancia m nima que determina la mayor similitud con el contexto actual, que en este caso es el comportamiento AttackToDistance.
Para disminuir posibles errores al seleccionar el comportamiento a ejecutar
se pueden seleccionar los K comportamientos mas similares (KNN, del ingles
k-Nearest Neighbors algorithm ) [
Al seleccionar la accion en base a la similitud, el disen~ador no puede garantizar como se va a comportar el NPC por lo que pueden surgir comportamientos emergentes que van a ofrecer una cierta impredicibilidad en el comportamiento del NPC, que puede ser interesante desde el punto de vista del jugador y su percepcion de la experiencia jugable pero que no es siempre del agrado de los disen~adores que normalmente pre eren mantener el control del juego. Por lo que hay que intentar mantener dichos comportamientos emergentes bajo control para que el NPC no realice comportamientos sin sentido o alejados de la idea que el disen~ador tiene del juego. 5.2
Para generar la base de casos, de nimos un nuevo decorador llamado Record que se asigna al nodo del arbol que queremos sustituir por el nodo Query posteriormente y que utilizaremos para almacenar las trazas. Este arbol generado por el disen~ador generara trazas guardando los atributos del comportamiento que el disen~ador seleccione. Las trazas se guardaran en una base de casos que puede ser alimentada con diferentes implementaciones del sub-arbol a aprender.
Otra alternativa para generar la base de casos es establecer un nuevo tipo de nodo terminal que denominamos InteractiveRecord. Este nodo permite ejecutar los comportamientos a peticion de un usuario, asignando cada comportamiento a ejecutar a un control. De esta forma, cuando el NPC decida ejecutar la accion a aprender, avisara el disen~ador para que este pulse el control asociado al comportamiento correspondiente que el considere mejor en ese momento, de forma que ensen~a al NPC como debe comportarse. Dado que el disen~ador puede equivocarse al ejecutar el comportamiento, se puede asignar a cada una de los comportamientos a ejecutar una funcion de valoracion que determine como de buenas han sido estas trazas, pudiendo hacer una seleccion de la base de casos descartando aquellas decisiones erroneas del disen~ador ejecutando el juego. Modi cando ligeramente el comportamiento del nodo Query, podemos permitir aprendizaje durante el juego, dotando el NPC de la capacidad de adaptarse al comportamiento del jugador y aprender nuevas estrategias. El NPC puede partir de una base de casos con gurada por el disen~ador, pero que se ira modi cando en base a lo que el NPC vaya aprendiendo durante el tiempo de juego con el jugador. Para ello, el nodo Query dispone de un parametro que determina la probabilidad de seleccionar un comportamiento de la base de casos o uno al alzar de entre los disponibles. La probabilidad de elegir uno u otro puede ir variando en funcion de multiples aspectos como la diversidad de comportamientos existente en la base de casos o los resultados obtenidos por el NPC. Si el NPC detecta que sus estrategias no consiguen vencer al jugador, este puede incrementar la probabilidad de elegir nuevas formas de implementar un comportamiento, dandole mas probabilidad de elegir uno de forma aleatoria. Las trazas en este aprendizaje inline deben de estar puntuadas para saber si el comportamiento que se ha seleccionado ha cumplido su objetivo (por ejemplo para la tarea de atacar, si ha dan~ado al jugador y cuanto dan~o le ha hecho). Cuando el nodo Query seleccione un comportamiento de la base de casos, seleccionara de entre los K mas parecidos, aquel que tenga una valoracion mas alta.
Con gurando este parametro de \aleatoriedad" podemos generar comportamientos mas emergentes y mas sorprendentes para el jugador, lo que ayuda a reducir la sensacion de IA scriptada (repetitiva) ya que el NPC puede cambiar de estrategia si detecta que la elegida no es e caz. 6
Con esta extension de los BTs permitimos a los disen~adores un mayor grado de autonom a, pudiendo prescindir en muchas ocasiones del programador para implementar comportamientos a bajo nivel as como ayudar al disen~ador a que pueda entrenar al NPC de forma interactiva, lo que le facilita la tarea de crear comportamientos, incluso si no dispone de conocimientos de programacion. Esto le permite desarrollar comportamientos a bajo nivel que segun nuestra metodolog a, deber an ser realizados por disen~adores tecnicos o programadores. Hay que tener en cuenta que el aprendizaje automatico requiere de una implicacion activa del disen~ador en el mismo por lo que puede resultar tedioso llevarla a cabo.
Como trabajo futuro queremos poner en practica estas tecnicas y validarlas experimentalmente para ver como funcionan y que aceptacion tienen entre los disen~adores y si realmente simpli can la creacion de comportamientos complejos, as como testear la capacidad de aprendizaje del NPC con la tecnica de aprendizaje disen~ada y poder aprender comportamientos de arriba a abajo, es decir ir aprendiendo comportamientos de bajo nivel y posteriormente, usando los nodos Query ya aprendidos, aprender comportamientos de mas alto nivel hasta permitir aprender el comportamiento completo del NPC.
Ademas queremos estudiar que funciones de similitud obtienen mejores resultados en la recuperacion as como que algoritmos de seleccion de atributos podemos utilizar para simpli car la base de casos, as como estudiar la posibilidad de simular la ejecucion de los comportamientos en la fase de seleccion de comportamientos candidatos a ser ejecutados, de forma especulativa para que solo se tenga en cuenta los preresquisitos de las acciones que realmente se ejecutaran en el contexto del Query Node que las ejecuta.