La teoría de los autómatas es una sección de las matemáticas discretas que estudia modelos de convertidores de información discretos. Estos convertidores son tanto dispositivos reales (computadoras, organismos vivos) como imaginarios (teorías axiomáticas, máquinas matemáticas). En esencia, una máquina de estados finitos puede describirse como un dispositivo METRO , que tiene canales de entrada y salida, mientras que en cada uno de los momentos de tiempo discretos, llamados momentos de reloj, se encuentra en uno de los estados finales.

En el canal de entrada en cualquier momento t =1, 2, ... al dispositivo METRO Llegan las señales de entrada (de algún conjunto finito de señales). La ley del cambio de estado al siguiente momento se establece dependiendo de la señal de entrada y el estado del dispositivo en el momento actual. La señal de salida depende del estado y de la señal de entrada en el momento actual (Fig. 1).

La máquina de estados es un modelo matemático de dispositivos reales de procesamiento de información discretos.

máquina estatal llamado el sistema A= (X , q , Y ,  ,  ), Dónde X , q , Y son conjuntos finitos arbitrarios no vacíos, y  Y  - funciones, de las cuales:

un montón de X ={a 1 , ..., a metro ) se llama alfabeto de entrada , y sus elementos son señales de entrada , sus secuencias están en Frases memorables ;

un montón de q ={q 1 , ..., q norte ) se llama muchos estados autómata y sus elementos - estados ;

un montón de Y ={b 1 , ..., b pag ) se llama alfabeto de salida , sus elementos son señales de salida , sus secuencias son palabras de salida ;

función  : X  q q llamado función de transición ;

función  :X  q Y llamado función de salida .

De este modo,  (X , q )q ,  (X , q )Y para  X X , q q .

Un dispositivo imaginario está asociado a la máquina de estados, que funciona de la siguiente manera. Puede estar en un estado del conjunto. q , recibir señales del televisor X y emitir señales desde un conjunto Y .

2. Métodos para definir un autómata finito.

Hay varias formas equivalentes de definir autómatas abstractos, tres de las cuales son: tabular , geométrico Y funcional .

2.1 Asignación de mesas de la máquina

De la definición de un autómata se deduce que siempre se puede definir mediante una tabla con dos entradas que contengan t líneas y PAG columnas, donde en la intersección de la columna q y lineas A los valores de la función valen  (a i , q j ),  (a i , q j ).

q a	q 1		q j		q norte
a 1	(a 1 , q 1),  (a 1 , q 1)		(a 1 , q j ),  (a 1 , q j )		(a 1 , q norte ),  (a 1 , q norte )
a i	(a i , q 1),  (a i , q 1)		(a i , q j ),  (a i , q j )		(a i , q norte ),  (a i , q norte )
a metro	(a metro , q 1),  (a metro , q 1)		(a metro , q j ),  (a metro , q j )		(a metro , q norte ),  (a metro , q norte )

2.2. Definición de un autómata mediante un diagrama de Moore

Otra forma de especificar una máquina de estados finitos es gráfica, es decir, mediante un gráfico. El autómata se representa como un gráfico dirigido etiquetado. GRAMO(q , D ) con muchos vértices q y muchos arcos D ={(q j ,  (a i , q j ))| q j q , a i X ), mientras que el arco ( q j ,  (a i , q j )) está etiquetado con un par ( a i ,  (a i , q j )). Así, con este método, los estados del autómata se representan mediante círculos, en los que se ingresan los símbolos de los estados. q j (j = 1, …, norte ). De cada círculo se realiza. t flechas (bordes dirigidos) uno a uno correspondientes a los caracteres del alfabeto de entrada X ={a 1 , ..., a metro ). Flecha correspondiente a la letra. a i X y saliendo del circulo q j q , el par ( a i ,  (a i , q j )), y esta flecha conduce a un círculo correspondiente a  (a i , q j ).

El dibujo resultante se llama gráfico de autómata o, diagrama de moore . Para autómatas no muy complejos, este método es más ilustrativo que tabular.

En este artículo, el término "máquina de estados" se refiere a un algoritmo que puede estar en uno de un pequeño número de estados. "Estado" es una condición determinada que define una relación determinada de las señales de entrada y salida, así como las señales de entrada y los estados posteriores. El lector inteligente notará inmediatamente que las máquinas de estados descritas en este artículo son máquinas Mealy. Una máquina de Mealy es una máquina de estados finitos donde las salidas son funciones del estado actual y la entrada, en contraste con la máquina de Moore donde las salidas son solo funciones del estado. En ambos casos, el estado posterior es función del estado actual y de la señal de entrada.

Consideremos un ejemplo de una máquina de estados finitos simple. Imagine que en una cadena de texto necesita reconocer la secuencia de caracteres "//". La Figura 1 muestra cómo se hace esto usando una máquina de estados. La primera aparición de la barra no produce una señal de salida, pero hace que el autómata entre en el segundo estado. Si el autómata no encuentra una barra en el segundo estado, regresa al primero, ya que necesita 2 barras seguidas. Si se encuentra la segunda barra, el autómata emite una señal de "listo".

Descubra lo que necesita el cliente.

Dibujar un diagrama de transición de estado

Codifique el "esqueleto" de la máquina de estados sin detallar las operaciones de transición.

Asegúrese de que las transiciones funcionen correctamente.

Especifique los detalles de las transiciones.

Tomar una prueba.

Ejemplo de máquina de estados

Consideremos un ejemplo más interesante de una máquina de estados finitos: un programa que controla la retracción y extensión del tren de aterrizaje de un avión. Aunque en la mayoría de los aviones este procedimiento se realiza mediante un mecanismo de control electrohidráulico (simplemente porque no hay computadora a bordo), en algunos casos, como en los vehículos aéreos no tripulados, vale la pena utilizar el control por software.

Primero, tratemos con el equipo. El tren de aterrizaje de la aeronave consta del tren de aterrizaje delantero, el tren de aterrizaje principal izquierdo y el tren de aterrizaje principal derecho. Son accionados por un mecanismo hidráulico. Una bomba hidráulica accionada eléctricamente suministra presión al actuador de potencia. Usando el software, la bomba se enciende o apaga. La computadora ajusta la posición de la válvula direccional: "abajo" o "arriba" para permitir que la presión suba o baje el chasis. Cada una de las patas del tren de aterrizaje tiene un interruptor de límite: uno de ellos se cierra si el tren de aterrizaje está levantado, el otro, si está fijado en la posición "abajo". Para determinar si la aeronave está en tierra, el interruptor de límite en el tren de morro se cierra si el peso de la aeronave está en el tren de morro. Los controles del piloto constan de un brazo superior/inferior del tren de aterrizaje y tres luces (una para cada pierna) que se pueden apagar, verde (posición abajo) o roja (posición de transición).

Y pasemos ahora al desarrollo de una máquina de estados finitos. El primer paso y el más difícil es comprender las expectativas reales del cliente. Una de las ventajas de una máquina de estados es que obliga al programador a pensar en todos los casos posibles y, como resultado, a recibir toda la información requerida del cliente. ¿Por qué considero que esta es la etapa más difícil? ¿Y cuántas veces te han dado una descripción de tarea como esta: no retraer el tren de aterrizaje si el avión está en tierra?

Por supuesto, esto es importante, pero el cliente cree que aquí termina todo. ¿Qué pasa con otros casos? ¿Es suficiente retraer el tren de aterrizaje en el momento en que el avión despega del suelo? ¿Qué pasa si el avión rebota sobre un bache en la pista? ¿Qué pasa si el piloto mueve la palanca de cambios a la posición "arriba" durante el estacionamiento y, como resultado, comienza a despegar? ¿Debería elevarse el chasis en este caso?

Uno de los beneficios de pensar en términos de una máquina de estados es que se puede dibujar rápidamente un diagrama de transición de estados en un tablero de proyección, justo en frente del cliente, y seguir el proceso con él. Se acepta la siguiente designación de transición de estado: "el evento que causó la transición" / "señal de salida como resultado de la transición". Si hubiéramos desarrollado solo lo que el cliente pidió originalmente (“no retraer el tren de aterrizaje si el avión está en tierra”), entonces habríamos recibido la máquina que se muestra en la Figura 2.

Al elaborar un diagrama de transición de estados (o cualquier otro algoritmo), tenga en cuenta lo siguiente:

Las computadoras son muy rápidas en comparación con el hardware mecánico.

Es posible que el ingeniero mecánico que explica lo que hay que hacer no sepa tanto sobre computadoras y algoritmos como usted. ¡Y esto también es un punto positivo, de lo contrario no te necesitarían!

¿Cómo se comportará su programa si se rompe una pieza mecánica o eléctrica?

En la Figura 3 se muestra una máquina de estados basada en lo que el cliente realmente quiere. Aquí queremos evitar que el tren de aterrizaje del avión se retraiga hasta que esté definitivamente en el aire. Para ello, después de abrir el interruptor de aterrizaje, la máquina espera unos segundos. También queremos responder al flanco ascendente de la palanca del piloto en lugar del nivel, lo que evitará problemas si alguien mueve la palanca mientras el avión está estacionado. Replegar o extender el tren de aterrizaje tarda unos segundos, y debemos estar preparados para la situación de que el piloto, durante esta operación, cambie de opinión y mueva la palanca en sentido contrario. Tenga en cuenta también que si el avión vuelve a aterrizar mientras estamos en el estado "Esperando despegue", el cronómetro se reiniciará y la retracción solo se producirá si el avión ha estado en el aire durante 2 segundos.

Implementación de la máquina de estados

El Listado 1 es mi implementación de la máquina de estados que se muestra en la Figura 3. Analicemos algunos de los detalles del código.

/*listado 1*/

enumeración typedef(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) Tipo_estado;

/*Esta matriz contiene punteros a funciones que se llamarán en ciertos estados*/

vacío(*state_table)() = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

Estado_tipo estado_actual;

InicializarLdgGearSM();

/* El corazón del autómata es este bucle sin fin. Función correspondiente

Estado actual, llamado una vez por iteración */

mientras (1) {

tabla_estado();

DecrementTimer();

vacío InicializarLdgGearSM( vacío )

estado_actual = GEAR_DOWN;

/*Detener el hardware, apagar las luces, etc.*/

vacío Marcha abajo( vacío )

/* Pasa al estado de espera si el avión

No en tierra y se recibió orden de levantar el chasis */

si((gear_lever == ARRIBA) && (prev_gear_lever == ABAJO) && (squat_switch == ARRIBA)) (

estado_actual = WTG_FOR_TKOFF;

prev_gear_lever = palanca_de cambios;

vacío Engranaje elevado( vacío )

si((nosegear_is_up == HECHO) && (leftgear_is_up == HECHO) && (rtgear_is_up == HECHO)) (

estado_actual = GEAR_UP;

/*Si el piloto ha cambiado de opinión, pasa al estado tren de aterrizaje bajado*/

si(palanca_de_cambios == ABAJO) (

curr_state = BAJAR_GEAR;

vacío Prepararse( vacío )

/*si el piloto movió la palanca a la posición "abajo",

Pasa al estado de "bajar el tren de aterrizaje" */

si(palanca_de_cambios == ABAJO) (

curr_state = BAJAR_GEAR;

vacío WtgParaDespegue( vacío )

/* Esperar antes de levantar el chasis. */

si(Temporizador<= 0.0) {

curr_state = LEVANTAR_ENGRANAJE;

/*Si volvemos a tocarnos o el piloto cambia de opinión, empezamos de nuevo*/

si((squat_switch == ABAJO) || (palanca de cambios == ABAJO)) (

estado_actual = GEAR_DOWN;

/* No quiero exigirle que mueva la palanca nuevamente

Esto fue sólo un rebote.*/

prev_gear_lever = ABAJO;

vacío Engranaje de descenso( vacío )

si(palanca_de_cambios == ARRIBA) (

curr_state = LEVANTAR_ENGRANAJE;

si((nosegear_is_down == HECHO) && (leftgear_is_down == HECHO) &&(rtgear_is_down == HECHO)) (

estado_actual = GEAR_DOWN;

En primer lugar, puede observar que la funcionalidad de cada estado se implementa mediante una función C independiente. Por supuesto, sería posible implementar un autómata usando una declaración de cambio con un caso separado para cada estado, pero esto puede llevar a una función muy larga (10-20 líneas de código por 1 estado para cada uno de los 20-30 estados). ). También puede provocar errores si cambia el código en las etapas finales de la prueba. Puede que nunca hayas olvidado la declaración de pausa al final de un caso, pero yo he tenido casos así. El código de un estado nunca entrará en el código de otro si tiene una función separada para cada estado.

Para evitar el uso de una declaración de cambio, utilizo una matriz de punteros a las funciones de estado y declaro que la variable utilizada como índice de la matriz es de tipo enum.

Para simplificar, el hardware de E/S responsable de leer el estado de los interruptores, encender y apagar bombas, etc., se representa como variables simples. Se supone que estas variables son "direcciones mágicas" asociadas al equipo por medios invisibles.

Otra cosa obvia es que en este punto el código no juega un papel especial. Simplemente pasa de un estado a otro. Este es un paso intermedio importante y no debe ignorarse. Por cierto, sería bueno agregar declaraciones impresas entre directivas de compilación condicionales (#ifdef DEBUG .. #endif) que imprimirían el estado actual y los valores de las señales de entrada.

La clave del éxito radica en el código que provoca la transición de estado, es decir. determina que se ha producido una entrada.

Si el código pasa correctamente por todos los estados, el siguiente paso es escribir el "relleno" del código, es decir, exactamente lo que produce la señal de salida. Recuerde que cada transición tiene una señal de entrada (el evento que la desencadenó) y una señal de salida (dispositivo de E/S de hardware, como en nuestro ejemplo). A menudo resulta útil capturar esto en forma de una tabla de transición de estados.

En la tabla de transición de estado, hay una fila por transición de estado.

Al codificar una máquina de estados, intente mantenerla sólida: una fuerte correspondencia entre los requisitos del cliente y el código. Puede ser necesario ocultar detalles de hardware en otra capa funcional, por ejemplo, para que el código de máquina de estados se parezca lo más posible a una tabla de transición de estados y a un diagrama de transición de estados. Esta simetría ayuda a prevenir errores y explica por qué las máquinas de estados son una parte tan importante del arsenal del programador integrado. Por supuesto, podría lograr el mismo efecto con casillas de verificación y un número infinito de declaraciones if anidadas, pero sería muy difícil rastrear el código y compararlo con los deseos del cliente.

El fragmento de código del Listado 2 amplía la función RaisingGear(). Tenga en cuenta que el código de la función RaisingGear() tiende a reflejar las 2 filas de la tabla de transición para el estado Raising Gear.

vacío Engranaje elevado( vacío )

/*Después de que todos los interruptores estén activados, vaya al estado "chasis activado"*/

si((nosegear_is_up == HECHO) && (leftgear_is_up == HECHO) && (rtgear_is_up == HECHO)) (

motor_bomba=APAGADO;

gear_lights = EXTINGUIR;

estado_actual = GEAR_UP;

/*Si el piloto cambia de opinión, inicia la retracción del tren de aterrizaje*/

si(palanca_de_cambios == ABAJO) (

dirección_bomba = ABAJO;

curr_state = GEAR_LOWERING;

Recuerde evitar estados ocultos. El estado oculto aparece cuando, por pereza, intentas agregar un subestado condicional en lugar de agregar un estado concreto. Por ejemplo, si su código procesa la misma entrada de diferentes maneras (es decir, inicia diferentes transiciones de estado) según el modo, entonces es un estado oculto. En este caso, me preguntaría si este estado no debería dividirse en dos. El uso de estados ocultos niega todos los beneficios de utilizar una máquina de estados.

Como práctica, puede extender la máquina de estado que acabamos de ver agregando un tiempo de espera al ciclo de retracción o extensión del chasis, como El ingeniero mecánico no quiere que la bomba hidráulica funcione más de 60 segundos. Si el ciclo finaliza, el piloto debe ser alertado mediante el encendido de las luces verde y roja y debe poder mover la palanca nuevamente para volver a intentarlo. También puedes preguntarle a un hipotético ingeniero mecánico cómo le afecta a la bomba invertir el sentido mientras está funcionando, porque sucede en 2 casos cuando el piloto cambia de opinión. Eso sí, el mecánico dirá que es negativo. Entonces, ¿cómo cambiaría la máquina de estado para detener la bomba rápidamente al cambiar de dirección?

Pruebas de máquina de estados

La belleza de codificar algoritmos como máquinas de estados finitos es que el plan de prueba se escribe casi automáticamente. Todo lo que tienes que hacer es pasar por cada transición de estado. Normalmente hago esto con un marcador en la mano, tachando las flechas en el diagrama de transición de estado a medida que pasan la prueba. Esta es una buena manera de evitar los "estados ocultos": se pasan por alto con más frecuencia en las pruebas que los estados concretos.

Esto requiere mucha paciencia y mucho café, ya que incluso una máquina de estados de tamaño mediano puede tener hasta 100 transiciones diferentes. Por cierto, la cantidad de saltos es una excelente manera de medir la complejidad de un sistema. Esto último está determinado por los requisitos del cliente y la máquina de estados hace evidente el alcance de las pruebas. Con un enfoque menos organizado, la cantidad de pruebas necesarias puede ser igual de impresionante, pero usted simplemente no se da cuenta.

Es muy conveniente utilizar declaraciones impresas en el código que muestren el estado actual, los valores de las señales de entrada y salida. Esto permite observar fácilmente lo que expresa la “Regla de Oro de las Pruebas de Software”: probar que el programa hace lo que está destinado a hacer, y también que no hace nada extra. En otras palabras, ¿solo está obteniendo los resultados que espera y qué más está sucediendo además de eso? ¿Existen transiciones de estado "duras", es decir? ¿Estados que pasan aleatoriamente, solo para una iteración del ciclo? ¿Las salidas cambian cuando no esperas que lo hagan? Idealmente, la salida de su printfs debería parecerse mucho a una tabla de transición de estado.

Finalmente, y esto se aplica a cualquier software integrado, no sólo al software basado en máquinas de estado, tenga mucho cuidado cuando ejecute el software por primera vez en hardware real. Es muy fácil equivocarse con la polaridad: "Vaya, pensé que '1' significaba subir el chasis y '0' significaba bajarlo". En muchos casos, mi asistente de hardware utilizó un "interruptor de gallina" temporal para proteger componentes valiosos hasta que estuvo seguro de que mi software estaba moviendo las cosas en la dirección correcta.

lanzamiento

Cuando se cumplan todos los requisitos del cliente, puedo lanzar una máquina de estado de esta complejidad en un par de días. Casi siempre los autómatas hacen lo que quiero. Lo más difícil es, por supuesto, entender exactamente lo que quiere el cliente y asegurarse de que él mismo sepa lo que quiere. ¡Esto último lleva mucho más tiempo!

Martín Gómez es programador del Laboratorio de Física Aplicada de la Universidad Johns Hopkins. Se dedica al desarrollo de software para el vuelo de naves espaciales de investigación. Ha trabajado en el campo del desarrollo de sistemas integrados durante 17 años. Martin tiene una Licenciatura en Ingeniería Aeroespacial y una Maestría en Ingeniería Eléctrica de la Universidad de Cornell.

El artículo analiza máquinas de estados simples y su implementación en C++ utilizando construcciones de conmutadores, tablas de tiempo de ejecución y la biblioteca Boost Statechart.

Introducción

En términos generales, una máquina de estados finitos (Finite State Machine), a los ojos del usuario, es una caja negra a la que puedes transferir algo y recibir algo desde allí. Esta es una abstracción muy conveniente que le permite ocultar un algoritmo complejo; además, las máquinas de estado son muy eficientes.

Los autómatas finitos se representan como diagramas que constan de estados y transiciones. Déjame explicarte con un ejemplo sencillo:

Como probablemente habrás adivinado, este es un diagrama del estado de una bombilla. El estado inicial se indica con un círculo negro, las transiciones con flechas, algunas flechas están firmadas: estos son eventos después de los cuales la máquina cambia a otro estado. Entonces, inmediatamente desde el estado inicial, llegamos al estado luz apagada- la lámpara no está encendida. Si pulsa el botón, la máquina cambiará de estado y seguirá la flecha marcada presionar el botón, al Estado luces encendidas- la lámpara está encendida. Puede volver a pasar de este estado mediante la flecha, después de presionar el botón, al estado luz apagada.

Las tablas de salto también se utilizan mucho:

Aplicación práctica de las máquinas.

Las máquinas de estados se utilizan ampliamente en programación. Por ejemplo, es muy conveniente imaginar el funcionamiento del dispositivo en forma de máquina automática. Esto hará que el código sea más simple y fácil de experimentar y mantener.

Además, los autómatas finitos se utilizan para escribir todo tipo de analizadores y analizadores de texto, con la ayuda de ellos puede buscar subcadenas de manera efectiva, las expresiones regulares también se traducen en un autómata finito.

Por ejemplo, implementaremos un autómata para contar números y palabras en un texto. Para empezar, acordemos que un número será una secuencia de dígitos del 0 al 9 de longitud arbitraria, rodeados por espacios en blanco (espacio, tabulación, salto de línea). Una palabra se considerará una secuencia de longitud arbitraria que consta de letras y también está rodeada de espacios en blanco.

Considere un diagrama:

Del estado inicial llegamos al estado comenzar. Verificamos el carácter actual, y si es una letra, vamos al estado Palabra a lo largo de la flecha marcada como carta. Este estado supone que en el momento en que estamos considerando una palabra, el análisis de otros símbolos confirmará esta suposición o la refutará. Entonces, considere el siguiente carácter, si es una letra, entonces el estado no cambia (observe la flecha circular marcada como carta). Si el carácter no es una letra, sino que corresponde a un espacio, entonces esto significa que la suposición fue correcta y encontramos la palabra (nos movemos a lo largo de la flecha Espacio en un estado comenzar). Si el símbolo no es ni una letra ni un espacio, entonces cometimos un error en la suposición y la secuencia que estamos considerando no es una palabra (seguimos la flecha desconocido en un estado Saltar).

Capaz Saltar Nos quedamos hasta que se encuentra un personaje espacial. Una vez encontrado el hueco, seguimos la flecha. Espacio en un estado comenzar. Esto es necesario para omitir por completo la línea que no coincide con nuestro patrón de búsqueda.

Después de la transición al estado comenzar, el ciclo de búsqueda se repite desde el principio. La rama de reconocimiento de números es similar a la rama de reconocimiento de palabras.

Autómata usando instrucciones de interruptor

El primero son los posibles estados:

Después de eso, iteramos sobre la cadena, deslizando el carácter actual en el autómata. El autómata en sí es una declaración de cambio que primero realiza una transición a la sección del estado actual. Dentro de la sección hay una construcción if-else que, dependiendo del evento (carácter entrante), cambia el estado actual:

const size_t longitud = texto.longitud () ; for (size_t i = 0 ; i != length; ++ i) ( const char current = text[ i] ; switch (estado) ( case State_Start: if (std:: isdigit (current) ) ( state = State_Number; ) else if (std:: isalpha (actual)) (estado = State_Word;) break; case State_Number: if (std:: isspace (actual)) (

Aquí miramos el diagrama: el estado actual. número, evento Espacio(se encontró un carácter de espacio), lo que significa que se encontró un número:

NúmeroEncontrado(); estado = Estado_Inicio; ) else if (! std:: isdigit (actual) ) ( estado = State_Skip; ) break ; case State_Word: if (std:: isspace (actual) ) ( FoundWord() ; estado = State_Start; ) else if (! std:: isalpha (actual) ) ( state = State_Skip; ) break ; caso State_Skip: if (std:: isspace (actual)) (estado = State_Start;) break; ) )

Resultado:

Alta eficiencia

Facilidad de implementación para algoritmos simples

- difícil de mantener

Interpretación en tiempo de ejecución

La idea de este enfoque es simple: necesita crear una tabla de transición, completarla y luego, cuando ocurra un evento, encontrar el siguiente estado en la tabla y realizar la transición:

enumerar eventos (espacio_evento, dígito_evento, letra_evento, evento_desconocido); void ProcessEvent (evento de eventos); ... estructura Transición (Estados BaseState_; Eventos Event_; Estados TargetState_;); void AddTransition(Estados del Estado, Evento de Eventos, Estados al Estado); ... typedef estándar::vector< transition>Tabla de transición; Transiciones de tabla de transición_; Estados CurrentState_;

Completando la tabla:

AddTransition(Estado_Inicio, Evento_Dígito, Estado_Número); AddTransition(Estado_Inicio, Evento_Letra, Estado_Palabra); AddTransition(Número_Estado, Espacio_Evento, Inicio_Estado); AddTransition(Número_Estado, Letra_Evento, Omisión_Estado); AddTransition(Número_Estado, Evento_Desconocido, Omisión_Estado); AddTransition(State_Word, Event_Space, State_Start); AddTransition(State_Word, Event_Digit, State_Skip); AddTransition(State_Word, Event_Unknown, State_Skip); AddTransition(State_Skip, Event_Space, State_Start);

Resultó bastante claro. La compensación por la claridad será un funcionamiento más lento de la máquina, lo que, dicho sea de paso, muchas veces no importa.

Para que el autómata, ante la ocurrencia de ciertos eventos, pueda notificar algún código, puede agregar a la estructura información sobre la transición ( transición) puntero de función ( acción) que se llamará:

typedef void (DynamicMachine:: * Acción) () ; struct Transition (Estados BaseState_; Eventos Event_; Estados TargetState_; Acción Acción_;); ... void AddTransition(Estados del Estado, Evento de Eventos, Estados al Estado, Acción de Acción); ... AddTransition (State_Number, Event_Space, State_Start y DynamicMachine:: FoundNumber);

Resultado:

Flexibilidad y visibilidad

Más fácil de mantener

- Menos rendimiento en comparación con los bloques de interruptores

Interpretación del tiempo de ejecución. Optimización de velocidad

¿Se puede combinar la visibilidad con la velocidad? Es poco probable que un autómata sea tan eficiente como un autómata basado en bloques de interruptores, pero es posible cerrar la brecha. Para hacer esto, es necesario construir una matriz a partir de la tabla, de modo que para obtener información sobre la transición no realice una búsqueda, sino que seleccione por el número de estado y evento:

El resultado se logra a expensas del consumo de memoria.

Resultado:

Flexibilidad, visibilidad

Eficaz

- Consumo de memoria (probablemente insignificante)

Impulsar el diagrama de estado

Discutimos varias formas de implementar una máquina de estados usted mismo. Para variar, propongo considerar una biblioteca para construir autómatas de Boost. Esta biblioteca es muy poderosa, las características propuestas le permiten construir máquinas de estados finitos muy complejas. Lo veremos bastante brevemente.

Así que primero definamos los eventos:

Eventos de espacio de nombres (estructura Dígito: impulso::estado::evento< Digit>( ) ; Carta de estructura: impulso::estado::evento< Letter>( ) ; Espacio de estructura: impulso::estado::evento< Space>( ) ; structUnknown: impulso::estado::evento< Unknown> { } ; }

La máquina en sí (tenga en cuenta que el segundo parámetro de la plantilla es el estado inicial):

Estructura Máquina: impulso::statechart::state_machine< Machine, States:: Start > { } ;

Y los propios estados. Dentro de los estados, es necesario definir un tipo que describa las transiciones ( reacciones), y si hay varias transiciones, inclúyalas en la lista de tipos boost::mpl::list. Segundo parámetro de plantilla estado_simple– tipo que describe el coche. Las transiciones se describen mediante los parámetros de la plantilla de transición, el par Evento - Próximo estado:

Estados del espacio de nombres ( estructura Inicio : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> reacción; ) ; Número de estructura: impulso::statechart::simple_state< Number, Machine>( impulso de typedef::mpl::lista< boost:: statechart :: transition < Events:: Space , States:: Start >, impulso::estado::transición< Events:: Letter , States:: Skip >, impulso::estado::transición< Events:: Unknown , States:: Skip >> reacción; ) ; estructura Palabra: impulso::statechart::simple_state< Word, Machine>( impulso de typedef::mpl::lista< boost:: statechart :: transition < Events:: Space , States:: Start >, impulso::estado::transición< Events:: Digit , States:: Skip >, impulso::estado::transición< Events:: Unknown , States:: Skip >> reacción; ) ; Saltar estructura: impulso::statechart::simple_state< Skip, Machine>( impulso de typedef::statechart::transición< Events:: Space , States:: Start >reacciones; ) ; )

La máquina está construida, solo queda inicializarla y puedes usar:

Máquina máquina; máquina.iniciar(); ...máquina .process_event(Eventos::Espacio() );

Resultado:

Flexibilidad, capacidad de ampliación

- Eficiencia

Actuación

Escribí un programa de prueba para comprobar la velocidad de los autómatas construidos. A través de las máquinas, pasé el texto con un tamaño de ~ 17 MB. Aquí están los resultados de la carrera:

Cargando texto Longitud del texto: 17605548 bytes 0,19 s Ejecutando BoostMachine Palabras: 998002, números: 6816 0,73 s Ejecutando DynamicMachine Palabras: 998002, números: 6816 0,56 s Ejecutando FastDynamicMachine Palabras: 998002, números: 6816 0,29 s Ejecutando SimpleMa chi ne Palabras: 998002, números : 6816 0,20s

Lo que queda sin revisar

Quedaron descubiertas algunas implementaciones más de autómatas finitos (recomiendo http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml y http://www.rsdn.ru/article/alg/FiniteStateMachine.xml), generadores que construyen autómatas a partir de descripciones, la biblioteca Meta State Machine de Boost versión 1.44.0, así como descripciones formales de máquinas de estados. El lector curioso puede familiarizarse con todo lo anterior.

Una máquina de estados es un modelo abstracto que contiene un número finito de estados de algo. Se utiliza para representar y controlar el flujo de ejecución de cualquier comando. La máquina de estados es ideal para implementar inteligencia artificial en juegos, obteniendo una solución clara sin escribir código engorroso y complejo. En este artículo, cubriremos la teoría y también aprenderemos cómo usar una máquina de estados simple y basada en pilas.

Ya hemos publicado una serie de artículos sobre cómo escribir inteligencia artificial utilizando una máquina de estados. Si aún no has leído esta serie, puedes hacerlo ahora:

¿Qué es una máquina de estados finitos?

Una máquina de estados finitos (o simplemente FSM - Máquina de estados finitos) es un modelo computacional basado en una máquina de estados hipotética. Sólo un estado puede estar activo a la vez. Por tanto, para realizar cualquier acción, la máquina debe cambiar de estado.

Las máquinas de estados se suelen utilizar para organizar y representar el flujo de ejecución de algo. Esto es especialmente útil al implementar IA en juegos. Por ejemplo, para escribir el "cerebro" del enemigo: cada estado representa algún tipo de acción (atacar, esquivar, etc.).

Un autómata finito se puede representar como un gráfico, cuyos vértices son los estados y las aristas son las transiciones entre ellos. Cada borde tiene una etiqueta que indica cuándo debe ocurrir la transición. Por ejemplo, en la imagen de arriba, puedes ver que el autómata cambiará el estado de "deambular" al estado "atacar" siempre que el jugador esté cerca.

Estados de programación y sus transiciones.

La implementación de una máquina de estados finitos comienza con la identificación de sus estados y las transiciones entre ellos. Imagine una máquina de estados que describe las acciones de una hormiga que lleva hojas a un hormiguero:

El punto de partida es el estado "buscar hoja", que permanece activo hasta que la hormiga encuentra la hoja. Cuando esto suceda, el estado cambiará a "ir a casa". El mismo estado permanecerá activo hasta que nuestra hormiga llegue al hormiguero. Después de eso, el estado vuelve a cambiar a "buscar hoja".

Si el estado "buscar hoja" está activo, pero el cursor del mouse está al lado de la hormiga, entonces el estado cambia a "huir". Tan pronto como la hormiga esté a una distancia lo suficientemente segura del cursor del mouse, el estado volverá a cambiar a "buscar hoja".

Tenga en cuenta que cuando regrese a casa o salga de ella, la hormiga no le temerá al cursor del mouse. ¿Por qué? Y porque no existe una transición correspondiente.

Implementando una máquina de estados simple

Se puede implementar una máquina de estados usando una sola clase. Llamémoslo FSM. La idea es implementar cada estado como un método o función. También usaremos la propiedad activeState para determinar el estado activo.

Clase pública FSM ( var privada activeState:Función; // puntero al estado activo del autómata función pública FSM() ( ) función pública setState(estado:Función) :void ( activeState = estado; ) función pública update() :void (si (estadoactivo!=nulo) (estadoactivo();))))

Cada estado es una función. Además, se llamará cada vez que se actualice el marco del juego. Como ya se mencionó, activeState almacenará un puntero a la función de estado activo.

El método update() de la clase FSM debe llamarse en cada cuadro del juego. Y él, a su vez, llamará a la función del estado que está actualmente activo.

El método setState() establecerá el nuevo estado activo. Además, cada función que define algún estado del autómata no tiene por qué pertenecer a la clase FSM; esto hace que nuestra clase sea más universal.

Usando una máquina de estados

Implementemos IA de hormigas. Arriba, ya hemos mostrado un conjunto de sus estados y las transiciones entre ellos. Ilustrémoslos nuevamente, pero esta vez nos centraremos en el código.

Nuestra hormiga está representada por la clase Ant, que tiene un campo cerebral. Esta es sólo una instancia de la clase FSM.

Clase pública Ant ( posición var pública:Vector3D; velocidad var pública:Vector3D; cerebro var pública:FSM; función pública Ant(posX:Número, posY:Número) ( posición = nuevo Vector3D(posX, posY); velocidad = nuevo Vector3D( -1, -1); Brain = new FSM(); // Comienza buscando una hoja. Brain. setState(findLeaf); ) /** * Estado "findLeaf". * Hace que la hormiga busque hojas. */ función pública findLeaf( ) :void ( ) /** * El estado "goHome" * Hace que la hormiga entre en el hormiguero */ función pública goHome() :void ( ) /** * El estado "runAway" * Provoca la hormiga para huir del cursor del mouse * / public function runAway() :void ( ) public function update():void ( // Actualiza la máquina de estado. Esta función llamará // a la función de estado activo: findLeaf(), goHome () o runAway(). Brain.update( ); // Aplica velocidad al movimiento de la hormiga. moveBasedOnVelocity(); ) (...) )

La clase Ant también contiene propiedades de velocidad y posición. Estas variables se utilizarán para calcular el movimiento utilizando el método de Euler. La función update() se llama cada vez que se actualiza el marco del juego.

A continuación se muestra la implementación de cada uno de los métodos, comenzando con findLeaf(), el estado responsable de encontrar las hojas.

Función pública findLeaf() :void ( // Mueve la hormiga a la hoja. velocidad = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distancia (Juego .instance.leaf, esto)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

El estado goHome() se utiliza para hacer que la hormiga regrese a casa.

Función pública goHome() :void ( // Mueve la hormiga a la casa velocidad = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance( Juego.instancia.casa, esto)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

Y finalmente, el estado runAway(), que se utiliza al esquivar el cursor del mouse.

Función pública runAway() :void ( // Aleja la hormiga del cursor speed = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // ¿El cursor todavía está alrededor? ? if (distancia(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // No, ya está muy lejos. Es hora de volver a buscar hojas. Brain.setState(findLeaf); ) )

Mejora de FSM: autómata basado en pila

Imagínese que la hormiga que regresa a casa también necesita huir del cursor del mouse. Así se verán los estados FSM:

Parece un cambio trivial. No, tal cambio nos crea un problema. Imagine que el estado actual es "huir". Si el cursor del ratón se aleja de la hormiga, ¿qué debería hacer: ir a casa o buscar una hoja?

La solución a este problema es una máquina de estados basada en pilas. A diferencia del FSM simple que implementamos anteriormente, este tipo de FSM utiliza una pila para administrar los estados. En la parte superior de la pila está el estado activo y las transiciones ocurren cuando se agregan o eliminan estados de la pila.

Y aquí hay una demostración visual del funcionamiento de una máquina de estados basada en la pila:

Implementación de un FSM basado en pila

Una máquina de estados finitos de este tipo se puede implementar de la misma manera que una simple. La diferencia será el uso de una serie de punteros a los estados requeridos. Ya no necesitaremos la propiedad activeState, porque la parte superior de la pila ya apuntará al estado activo.

Clase pública StackFSM ( pila var privada:Array; función pública StackFSM() ( this.stack = new Array(); ) actualización de función pública() :void ( var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) ( currentStateFunction(); ) ) función pública popState() :Función ( return stack.pop(); ) función pública pushState(estado:Función) :void ( if (getCurrentState() != estado) ( stack.push(estado) ; ) ) función pública getCurrentState(): Función (retorno pila.longitud> 0? pila: nulo;))

Tenga en cuenta que el método setState() ha sido reemplazado por pushState() (agregando un nuevo estado a la parte superior de la pila) y popState() (eliminando el estado de la parte superior de la pila).

Usando el FSM basado en pila

Es importante tener en cuenta que cuando se utiliza una máquina de estados basada en pila, cada estado es responsable de eliminarse de la pila cuando no es necesario. Por ejemplo, el estado attack() debería eliminarse de la pila si el enemigo ya ha sido destruido.

Public class Ant ( (...) public var Brain:StackFSM; public function Ant(posX:Number, posY:Number) ( (...) Brain = new StackFSM(); // Comience buscando un cerebro hoja. pushState( findLeaf); (...) ) /** * Estado "findLeaf". * Hace que la hormiga busque hojas. */ public function findLeaf() :void ( // Mueve la hormiga a la hoja. velocidad = new Vector3D(Juego.instancia.hoja.x - posición.x, Juego.instancia.hoja.y - posición.y); if (distancia(Juego.instancia.hoja, esto)<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // No, ya está muy lejos. Es hora de volver a la búsqueda de hojas. Brain.popState(); ) ) (...) )

Conclusión

Las máquinas de estados son ciertamente útiles para implementar la lógica de la inteligencia artificial en los juegos. Se pueden representar fácilmente como un gráfico, lo que permite al desarrollador ver todas las opciones posibles.

Implementar una máquina de estados con funciones de estado es una técnica simple pero poderosa. Se pueden implementar entrelazamientos de estados aún más complejos utilizando FSM.