20 julio, 2006

Me encanta que los planes salgan bien

Dado que este es un foro centrado, de momento, principalmente en diseño, voy a intentar explicar una de las tecnologías de moda dentro del campo de la IA, desde el punto de vista de cómo lo puede percibir un diseñador. Me estoy refiriendo a los sistemas de Planificación Automática.

Para empezar, un poco de historia, y algunas referencias. La planificación como tecnología de inteligencia artificial existe desde los años 70 (el primer planificador se llamaba STRIPS), aunque apenas se hablaba de ello en el ámbito de juegos hasta que Jeff Orkin, coordinador del grupo de investigación sobre planificación y objetivos de la IGDA, decidió usarla para desarrollar la IA de F.E.A.R. (presentaciones aquí). Ahora mismo, promesas de una IA más dinámica, más flexible y, sencillamente, más inteligente, junto con el santo grial de menos trabajo para el diseñador, hacen que se haya puesto de moda muy rápidamente.

La forma de trabajar con un NPC con planificador es ligeramente distinta a la que se ve hoy en día. Probablemente el diseñador esté acostumbrado a definir con bastante precisión el comportamiento de un NPC: no sólo qué va a hacer, sino también cómo va a hacerlo. O sea, no le dirá: "Cuando el jugador aparezca por esa puerta, atácale sin usar granadas". Probablemente sea algo más como: "Cuando el jugador aparezca por esa puerta, dispara sin moverte durante 10 segundos o hasta que te acierten, y luego cúbrete, mantente dentro y fuera de cobertura hasta llegar al 10% de tu salud, y por fin cargas frontalmente". No hay nada de malo en hacer esta especificación, pero hay que tener en cuenta que es frágil frente a situaciones inesperadas (si no hay cobertura, ¿que hace el NPC? ¿disparar descubierto sin moverse?) y, dado que hay que rehacer la especificación para cada escenario posible, el coste de incorporar nuevas mecánicas es alto para el programador (si de repente queremos añadir que el NPC ruede por el suelo para esquivar, habrá que retocar todos los escenarios). En los desarrollos actuales estamos acostumbrados a estos problemas.

El sistema de planificación automática trata de aliviar la complejidad de organización y selección de comportamientos que se encuentran los NPCs. Especialmente si hablamos de NPCs bastante autónomos, la posibilidad de elaborar sus propios planes permite al NPC incorporar nuevos elementos que se añadan al juego posteriormente con mayor facilidad, a la vez que le proporciona la capacidad de reaccionar mejor ante situaciones inesperadas que si lo hiciera con un comportamiento "enlatado".

Para entender mejor la diferencia de la planificación con el enfoque tradicional, hay que hablar un poquito de la estructura típica de la IA de un juego. La complejidad de los diseños actuales hace que la IA tenga que dividirse jerárquicamente. Se empieza implementando acciones muy básicas, como pueden ser moverse o disparar, que a menudo son idénticas a las que ejecuta el jugador con el controlador. Luego se crea un nivel jerárquico por encima, que contiene un conjunto de comportamientos sencillos que añaden algo de funcionalidad, como la búsqueda de caminos, o el apuntado al disparar. En un siguiente nivel se utilizan estos comportamientos sencillos para montar otros más complejos, que seleccionarán cuáles de estos comportamientos sencillos tienen sentido en cada momento, en función de criterios de alto nivel. Así, podríamos implementar una táctica de combate que hiciera circle-strafe, moviéndonos alrededor del enemigo mientras le intentamos apuntar continuamente. El último nivel será el que elija la táctica idónea, siguiendo las guías que el diseñador haya dado para la personalidad del NPC o para una misión concreta.

Dentro de esta organización, tradicionalmente los programadores implementan tantos comportamientos de alto nivel como los diseñadores van identificando. Para cada comportamiento se hace una implementación distinta, única, típicamente usando técnicas bien conocidas como máquinas de estado o lenguajes de script. En ambos casos el NPC sigue un guión pre-escrito y rígido. Si nuestro NPC tiene la orden de hacer circle-strafe, eso será exactamente lo que hará, tal y como esté programado. La capacidad expresiva y de reacción de los NPCs viene directamente limitada por la capacidad de producción del equipo, tanto en términos de diseñadores identificando situaciones como, especialmente, de programadores implementando comportamientos para gestionarlas.

El sistema de planificación automática pretende cambiar todo esto. Cuando se identifica un nuevo escenario, en lugar de forzar la implementación de un nuevo comportamiento de alto nivel, basta con explicarle al NPC qué es lo que tiene que conseguir en este escenario, cual es su objetivo. El NPC, usando la planificación, "programará" un comportamiento de alto nivel capaz de cumplir ese objetivo sobre la marcha, decidiendo cuáles de los comportamientos de bajo nivel necesita utilizar. Así, en lugar de programar un circle-strafe, le diríamos al NPC que su objetivo es mantener a su enemigo en el punto de mira, mientras evita los ataques de éste (el objetivo para un comportamiento de más alto nivel sería incluso más genérico). Con este objetivo, en una zona abierta quizás el NPC acabe optando por algo similar a un circle-strafe, pero si se encuentra en un área donde se puede hacer uso efectivo de la cobertura, tal vez prefiera esta opción. Con este planteamiento, añadir un nuevo elemento es como darle al NPC una nueva herramienta con la que intentar llegar al objetivo marcado. Lo mismo se aplica si queremos restringirle el uso de un elemento. Además, con un buen planificador, el NPC será capaz de reaccionar ante imprevistos, y construir un nuevo plan que le lleve al objetivo.

Todo esto que parece magia, es en realidad conceptualmente relativamente simple. El truco consiste en etiquetar todos los comportamientos disponibles con sus requisitos y sus efectos. Los requisitos son condiciones que se tienen que cumplir para poder ejecutar el comportamiento con éxito. Si queremos disparar, tenemos que tener un arma cargada equipada, y necesitamos algún enemigo visible. El efecto es el resultado que se espera después de ejecutar el comportamiento. Así, tras disparar el arma es de esperar que el enemigo esté muerto, o tras lanzar el comportamiento de búsqueda de enemigos el resultado será tener un enemigo a la vista. Con esta información adicional, el NPC puede intentar encadenar inteligentemente comportamientos para conseguir el resultado final que el objetivo le indica. Así, si queremos que nuestro NPC intente matar al jugador, primero deberá recoger y equipar un arma, luego buscar al jugador y finalmente dispararle. El trabajo de construir la secuencia de comportamientos es completamente automático (aunque normalmente se puede regular mediante parámetros, que indican las "preferencias" del NPC).

Llegados a este punto quizás os preguntéis porqué no estamos todos usando planificadores automáticos y olvidando el pasado. La primera razón es que todavía es una tecnología relativamente nueva en el marco de videojuegos, así que por un lado hay algunas dudas sobre lo bien que se comportará con problemas suficientemente complejos, no está claro el coste de implementar el motor de planificación, y no todos los programadores están suficientemente formados en su uso. Desde el punto de vista de diseño, comparando directamente un planificador con un sistema tradicional, el planificador exige un mayor esfuerzo de abstracción inicial, ya que hay que dividir los comportamientos de los NPCs en pequeñas acciones que se puedan combinar bien, y especificar cómo se encadenan. Luego, al definir cómo se quiere que se comporte el NPC, en lugar de hacerlo explicándoselo a un programador hay que explicarselo al NPC, hablando su "lenguaje", sobre qué condiciones se tienen que cumplir en el mundo. Es posible además que el diseñador pierda algo de control "fino" sobre cómo se va a comportar el NPC. Los planificadores funcionan mejor cuando se les da autonomía para explorar opciones, y es en estos casos cuando rinden mayores beneficios. Si se quiere un control detallado sobre las acciones del NPC, habrá que implementarlo explícitamente, y no se ganará nada por tener el planificador. El resultado final que el jugador percibirá no tiene porqué ser distinto según el método que se elija. Depende más de hasta dónde llegue la capacidad de producción del equipo que de la tecnología usada.

Al final, la metodología tradicional resulta más eficiente cuando no hay excesiva variedad de acciones. A medida que la cantidad de acciones aumenta, es cuando el planificador sí puede brillar, ya que implementarlo tiene un coste inicial mayor, pues hace falta código extra dedicado a buscar la secuencia correcta de comportamientos sencillos (el motor de planificación), y todos los comportamientos tienen que llevar información adicional. Con el estado actual de los juegos, estamos en el límite del compromiso entre la complejidad del planificador y la del sistema tradicional con la cantidad de combinaciones que encontramos habitualmente. En cualquier caso, es bueno irse preparando, por si acaso.


Mostrar/ocultar resto...

10 Comments:

At 20/7/06 15:17, Blogger javi said...

Muy interesante el artículo. Conoces algún juego en el que se hayan aplicado este tipo de técnicas?

 
At 20/7/06 15:19, Blogger javi said...

además de FEAR, claro :p

 
At 20/7/06 18:57, Blogger sgarces said...

No, la verdad es que aparte de FEAR, no sé de ningún otro juego comercial que use planificación. La gran mayoría están basados en máquinas de estados jerárquicas.

Lo que sí es cierto es que, ahora que está de moda, es posible que empecemos a verlo. Recuerdo incluso haber leído que en el AIIDE del año pasado se hablaba mucho de planificación para construir historias de manera emergente, asi que, quien sabe...

 
At 21/7/06 14:13, Blogger javi said...

Con respecto a las FSM hay un artículo muy interesante en aidepot, traducido en vidaartificial: http://vidaartificial.com/index.php?title=Maquinas_de_Estados_Finitos_(ai-depot.com)

Habla a un nivel de programación, pero expica muy bien las FSM jerarquicas.

Por si alguien no lo conoce.

 
At 22/7/06 11:21, Blogger Saül said...

Gracias Sergio por la información. Es un tema interesante.

Nosotros en el Fallen Lords teníamos dos tipos de enemigos especialmente "inteligentes" (con respeto al resto): los hechiceros y los maestros. Para programar su IA utilizamos máquinas de estado jerárquicas mediante LUA, que permitió que Carlos (programador) y yo trabajásemos "codo con codo" utilizando un lenguaje que ambos comprendíamos (LUA) y con una gestión más o menos simple pero efectivista. La verdad es que el resultado fué bastante "católico".

Os explico el comportamiento jerárquico para que me digáis, más o menos, cómo se "traduciría" eso en el sistema de planificación que comentáis. ¡Así aprendo un poco!

Cada 5 segundos el Hechicero decide qué magia es más adecuada en ese momento. Hay magias de 2 tipos, defensivas y ofensivas, por lo que cuando "piensa" qué magia hacer primero mira su vida restante. Si le queda -20% hace una defensiva, si le queda +80% hace una ofensiva. En el resto de rangos decide aleatoriamente si defensiva/ofensiva.

Si selecciona ofensiva: mira cuántos enemigos y aliados tiene en su campo de visión.

Si hay más enemigos: Si hay 1 solo seleccionará aleatoriamente entre una de las magias ofensivas "concentradas". Si hay +1 enemigo seleccionará aleatoriamente una de las magias ofensivas "expandidas". Evidentemente, esta aleatoriedad no es total, las magias más "cool" tienen una probabilidad más baja de aparecer.

Si hay más aliados: mira la vida restante de estos. Si es baja, selecciona aleatoriamente una de las magias de curación para estos aliados. Si es alta, una invocación de más aliados (hasta un límite, a partir del cual irá a "primera fila" a atacar al enemigo).

Si selecciona defensiva: elige aleatoriamente entre las magias defensivas que tiene: invocar a demonios e irse corriendo unos metros, teletransportarse a un lugar lejano y curarse, crear un area de paralización alrededor suyo, etc.

Si no está en combate, primero se curará a él mismo. Después buscará enemigos a los que aniquilar y, definitivamente, aliados a los que curar.

Este sistema, pese a parecer un poco "básico" nos sirvió para que la gente creyese que los hechiceros eran realmente inteligentes. El factor "Random" ayudó bastante a que su comportamiento pareciera más o menos real. Además, cuando los utilizamos de "monstruos finales", al estar totalmente implementados en LUA, yo pude variar "manualmente" su comportamiento para esas escenas concretas sin prácticamente costes extras de programación.

Hasta aquí una visión "por encima" de su comportamiento en estructura jerárquica. Continúo con lo que creo que sería la de planificación:

Objetivos principales
- Ganar la batalla matando a todos los enemigos del bando contrario
- Mantenerse vivo hasta el final
- Entender que tener aliados es mejor que ir solo

Herramientas
- curarse a sí mismo
- curar aliados / generar aliados
- atacar al enemigo de forma concentrada (mucho daño pero a uno solo)
- atacar al enemigo de forma expandida (menos daño pero a muchos soldados)
- esquivar los ataques del enemigo
- parapetarse detrás de un grupo de aliados para "asistirlos"
- ...

Sería esto aproximadamente? Gracias de adelantado ;)

 
At 22/7/06 20:16, Blogger sgarces said...

Hmmmm. A ver que se me ocurre.

Como objetivos podrías tener una lista de este estilo:
- Mantenerse vivo
- Rodearse de aliados
- Matar/dañar grupo de enemigos
- Matar/dañar 1 enemigo

En vez de "Rodearse de aliados" podríamos tener dos separados: "Crear aliados" y "Curar aliados", pero creo que eso se puede gestionar automáticamente (con un pre-requisito para la accion de curar aliados que mire a ver si los aliados tienen salud baja). He separado matar 1 enemigo y un grupo porque parece que las acciones para lograr uno y otro son muy distintas, entonces es más facil organizarlo así.
Cada 5 segundos, el hechicero tiene que arbitrar entre estos objetivos, y seleccionar uno de ellos. Para hacerlo, mirará su vida, como haceis vosotros, y evaluará el número de aliados a su alrededor y si tiene acceso a grupos de enemigos o no.

Una vez elegido el objetivo, consultará su lista de acciones y tratará de buscar una secuencia que le funcione. Acciones serían:
- Magia ofensiva para 1 enemigo I
- Magia ofensiva para 1 enemigo II
- Magia ofensiva para 1 enemigo III
- Magia ofensiva para grupos I
- Magia ofensiva para grupos II
- Magia defensiva I
- Magia defensiva II
- Magia defensiva III
- Crear aliados
- Curar aliados
- etc

En la definición de acciones se pondría cualquier pre-requisito que necesitaran (p.ej. si necesita un objeto para hacer una magia, o necesita x puntos de maná). Las acciones no se clasifican, potencialmente cualquiera podría ser usada para alcanzar el objetivo. Es posible prohibir acciones, simplemente eliminándolas de la lista. A la hora de montar la secuencia, se hace una búsqueda. Incluir una acción en el resultado tiene un coste. Este coste se define (p.ej. como un número fijo, o un valor calculado por la propia clase donde se implementa la acción) y representa las preferencias del hechicero, que tipos de magias prefiere usar (que tendrán menor coste).

Para incluir la aleatoriedad, se podría hacer que una parte del coste se calcule aleatoriamente, en un rango de valores, o incluso algún sistema de aleatoriedad filtrada, donde la probabilidad de usar una magia varíe con el tiempo (sea más probable su uso cuanto más tiempo hace que no se ha usado).

En definitiva, el resultado final sería exactamente el mismo, pero tendríais algo más de facilidad a la hora de incluir acciones, especialmente si son acciones polivalentes, que pueden ser usadas en contextos diversos. Por otra parte, el sistema es algo más complicado de entender, y menos estructurado que la HFSM. Yo no creo que optara por el sistema de planificación, ya que no parece muy frecuente encadenar más de 1 o 2 acciones. La HFSM es clara y funciona bien.

¿Como lo ves?

 
At 22/7/06 20:18, Blogger sgarces said...

Bien pensado, matar 1 enemigo y un grupo se podría combinar en un solo objetivo, y usar una pre-condicion para las magias de grupo que pida que haya varios enemigos juntos, o algo asi.

 
At 22/7/06 22:28, Blogger Saül said...

Veo que las ventajas, en este caso concreto, no son demasiado claras, quizás debido a la simplicidad del comportamiento que he descrito, dado que no se necesitan "combinaciones de acciones" sino evaluaciones prácticamente aisladas cada X tiempo. Imagino que si se hubiera pretendido que el NPC entendiera la gestión del maná, nuestro sistema hubiera sido demasiado básico y la gestión se hubiera complicado. De aquí que Carlos y yo decidiéramos que los "random" vendrían a "aparentar" esta gestión y eran más que suficientes (para nuestro juego). Este mismo sistema de random nos permitía también dar la aparencia de que el NPC no seleccionaba siempre las mismas soluciones cuando se enfrentaba a un caso concreto. ¿Cómo evitarías esto con el sistema que comentas? Quiero decir, el que se vea "el plumero" del bot. ¿Con un random también?

 
At 23/7/06 00:33, Blogger sgarces said...

Poniendome el sombrero de programador de IA, lo que planteas es un problema de toma de decisiones. Un agente "racional", siempre toma decisiones eligiendo la opción de mayor "utilidad", o sea, la que mejores resultados vaya a dar. Toda la lógica de razonamiento pretende hacer una evaluación de la utilidad de cada una de las opciones, típicamente un número, y elegir la mejor.

Si el random funciona, es porque las opciones están próximas en utilidad, y el agente parecerá racional elija la que elija. Si separas más las opciones, de manera que cada una sea más clara dependiendo de la situación (el estado de la batalla), entonces podrás escribir una lógica de cálculo de utilidad más precisa (menos dependiente del random). En este caso, es posible que se vea al hechicero actuar como un robot, pero si las situaciones son variadas y las evaluaciones del hechicero suficientemente precisas, entonces parecerá racional, no necesariamente predecible.

Vale, me he ido un poco por la tangente. Volviendo al planificador, si quieres mantener el random como elemento que añada variedad, lo puedes hacer simplemente haciendo aleatorio el coste de seleccionar una de las acciones disponibles. A la hora de construir el plan, si el hechicero tiene varias acciones que puede utilizar, elegirá la de coste menor. Si el coste es aleatorio, el sistema es equivalente a la HFSM.

Como bien dices, en este caso la ventaja es poco interesante. Si, por ejemplo, el hechicero tuviera que moverse a una posición (quizás por el rango de un hechizo), o estar en algún estado especial (si pudiera transformarse), o seleccionar un arma concreta para lanzar un hechizo (todo esto me lo estoy inventando sobre la marcha), entonces el planificador sería más útil. No sólo permitiría encadenar acciones automáticamente (no tendrías que acercar al hechicero en la implementación de un hechizo de ataque con rango limitado, habría una acción para ello), sino que además podría elegir la secuencia más valiosa, la lista de acciones cuya utilidad fuera mejor. Así, si el coste de moverse o de cambiar de arma fuera alto, probablemente preferiría usar un hechizo que no necesite esto, a menos que cambiar de estado o posición permitiera ejecutar un hechizo muy potente o ventajoso.

¿Tiene más o menos sentido?

 
At 25/7/06 15:35, Blogger Saül said...

Sí, tiene mucho sentido. Gracias por la aclaración. La clave está en "porque las opciones están próximas en utilidad". Está claro que a mayor complejidad de acciones/reacciones posibles, mayor "sofisticación" se le requerirá a la IA para que los costes necesarios para producir esas reacciones "planificando" sean menores que hacerlos "a la HSFM".

 

Publicar un comentario en la entrada

Links to this post:

Crear un enlace

<< Home