Un Framework para Máquinas de Estados Finitos

En esta sección echaremos un vistazo a la implementación de una máquina de estados finitos desde una perspectiva más amplia. Investigaremos como una FSM puede implementarse, y echaremos un vistazo a un framework que puede facilitarnos múltiples FSMs en un entorno simulado en tiempo real.

Una única FSM por ella misma es de poca utilidad; por ello necesitamos investigar implementaciones desde un punto de vista más amplio para entender dónde una FSM puede encajar. Analizaremos porciones del framework de FSM del juego Quake, en un intento de entender como hacer uso de esta técnica en el mundo real.

Una forma posible de implementar una FSM es tener un controlador de algún tipo que actúe como una caja switch (caja de cambios). Cuando el hilo de ejecución busca ejecutar el código de la FSM, se le indica un controlador de algún tipo que evalúa o determina el estado actual normalmente a través de un comando switch (case) o if-then-else. Una vez determinado el estado actual, se ejecuta el código de ese estado, sus acciones y las posibles transiciones de estado para la próxima vez que se ejecute el FSM. El controlador puede ser un sencillo comando switch evaluando un integer, pero en otra implementación podría verse al controlador realizando algunos pre-procesos sobra las entradas y los activadores de transiciones de estado por adelantado.

Figura 3.1: Una implementación de FSM donde el controlador actúa como una máquina de cambios para determinar que estado ejecutar. La linea roja denota un hilo a ejecutar.

La implementación que los programadores de id Software han elegido puede considerarse que prácticamente tiene un toque de programación Orientada a Objetos (OO), aunque la implementación no es OO. Tal y como mencionamos antes el mundo del juego está poblado por entidades y como tales una estructura genérica de entidad es usada como su base. Cada entidad en la colección de entidades obtiene cierto tiempo de ejecución al llamar a su función "think". La entidad es ejecutada por el código del juego de una forma que podría describirse como polimórfica. Las entidades tienen un interface común (porque todas tienen la misma estructura de datos), este interface consiste en punteros a funciones las cuales son usadas para ejecutar código específico y código no-específico de entidad según la acción recibe o envía eventos a la FSM.

Un ejemplo; la mayoría de entidades son afectadas por el daño. El daño puede ser infligido por muchas cosas como los misiles, por ejemplo. Cuando un activador de daño es transmitido a otra entidad, se llama a su puntero a la función pain (daño), activando así una transición de estado de la entidad afectada, posiblemente un estado de muerte o contra ataque. El punto clave: El daño infligido es una entrada a la FSM, que puede actuar como un activador para la transición de estados.

En esencia se usa la misma técnica de la caja switch descrita en la figura 3.1, donde la estructura de datos base de las entidades proveen punteros a funciones que actúan como "switchers". Cuando se le da a una entidad una oportunidad de ejecutar su estado, se llama a su puntero a la función "think". Si se había recibido previamente una entrada de daño, la entidad podría tener una transición de estados a su "estado muerto". Cuando se ejecuta el hilo de ejecución, el código "estado muerto" del objeto es ejecutado (a través de una llamada polimórfica de la función think de la entidad), eliminando la instancia de la entidad del mundo del juego.

En lugar de seguir con las explicaciones teóricas echaremos un vistazo a un ejemplo práctico del juego Quake. Un perro es un monstruo simple que desea atacar al jugador o a cualquier monstruo que le haga enfadar, actuando de forma muy parecida a la anterior vista en el monstruo Shambler.

Figura 3.2: Representación de Estados Finitos de estados, acciones, transiciones y entradas para un monstruo Perro en el juego Quake.

La figura 3.2 muestra los cuatro estados principales del monstruo Perro de Quake. Las acciones principales están sobreimpresas en cada uno de estos estados. Algunos se enlazan directamente con funciones, otros se enlazan con cadenas de funciones o llamadas a funciones. La representación claramente muestra los cinco principales eventos de entrada con bordes oscuros que son llamados como salidas de otra máquina de estados finitos. Hay dos tipos de acciones mostrados, el fondo gris representa código especifico del perro, y el blanco código del framework usado por todos los monstruos.

La figura es un diagrama bueno como herramienta para mostrar que código especifico del monstruo necesita ser escrito y donde encaja en el framework. No es una representación completa, por ejemplo, en referencia al código ejecutado tras la generación del monstruo, existen otras acciones "nadar" y "volar" usadas por algunos monstruos que pueden nadar y volar a diferencia de nuestro perro que sólo camina. También existe un tercer sub-estado de ataque llamado "ataque deslizado" que no es relevante en el caso de nuestro perro.

Aunque el diseño de un FSM en papel puede parecer muy directo y fácil de implementar se puede ver que cuando llega el momento de la implementación de la mayoría de ellos, como los monstruos de un juego, es fácil y probablemente necesario difuminar los límites de los estados. En la figura 3.2 no vemos funciones bien definidas representado los estados como deberíamos esperar, en su lugar las funciones son compartidas por diferentes estados y FSMs. En este ejemplo está claro que las acciones centrales han sido descompuestas y su funcionalidad abstraída para ser incorporadas en el framework para ser usadas por todos los monstruos del juego. Es una buena aproximación para una ejecución rápida, fácil mantenimiento y reutilización de código, pero pobre debido al moderado nivel de complejidad (debe tomarse tiempo para trazar el camino de ejecución).

La máquina obtiene su tiempo de ejecución a través de su función think (pensar). Evalúa entradas a partir de sus entradas del mundo del juego, pero puede recibir eventos específicos como entrada a través de la salida de acciones realizadas por otras FSMs. Esto incluye las acciones tocar, usar, dañar y morir. Estos eventos puede activar cambios de estado de la máquina afectada, por ejemplo, como se puede ver en la Figura 3.2 un evento de entrada tocar es una colisión determinada por el juego según avanza en el tiempo la física del juego. Al recibir la entrada en el ejemplo anterior, y si el monstruo perro tiene especificada una función válida "tocar" (que puede no ser siempre el caso), ejecutará el código en esa función y posiblemente tendrá una transición a su sub-estado de atacar con misiles o a su estado atacar para una reevaluación de sus sub-estados de ataque.

Está claro que una FSM en este dominio es muy útil como mecanismo de control y cuando es usada en una gran escala como hemos visto, es muy potente. Este ejemplo muestra un framework de FSM que puede proveer la habilidad para un sistema multi-agente sencillo, en el cual cada sistema FSM puede ser considerado como un agente (inteligente; usa técnicas de AI, autónomo; actúa independientemente). Las FSMs tienen funciones sensor implementadas específicamente para manejar los eventos esperados, y también tiene funciones de efectos que pueden simplificar la ejecución de acciones en el mundo del juego.

Visita Artificial Intelligence Depot.