maquinas de estado tutoriales

Me pregunto si alguien sabe de algunos buenos tutoriales en Internet para desarrollar máquinas de estado. O libros electrónicos?

Estoy empezando a trabajar en máquinas de estado y solo necesito algo general para comenzar.

Las máquinas de estado son muy simples en C si usa punteros de función.

Básicamente necesita 2 matrices: una para los indicadores de función del estado y otra para las reglas de transición del estado. Cada función de estado devuelve el código, la tabla de transición de estado de búsqueda por estado y el código de retorno para encontrar el siguiente estado y luego simplemente ejecutarlo.

int entry_state(void); int foo_state(void); int bar_state(void); int exit_state(void); /* array and enum below must be in sync! */ int (* state[])(void) = { entry_state, foo_state, bar_state, exit_state}; enum state_codes { entry, foo, bar, end}; enum ret_codes { ok, fail, repeat}; struct transition { enum state_codes src_state; enum ret_codes ret_code; enum state_codes dst_state; }; /* transitions from end state aren't needed */ struct transition state_transitions[] = { {entry, ok, foo}, {entry, fail, end}, {foo, ok, bar}, {foo, fail, end}, {foo, repeat, foo}, {bar, ok, end}, {bar, fail, end}, {bar, repeat, foo}}; #define EXIT_STATE end #define ENTRY_STATE entry int main(int argc, char *argv[]) { enum state_codes cur_state = ENTRY_STATE; enum ret_codes rc; int (* state_fun)(void); for (;;) { state_fun = state[cur_state]; rc = state_fun(); if (EXIT_STATE == cur_state) break; cur_state = lookup_transitions(cur_state, rc); } return EXIT_SUCCESS; } 

No pongo la función lookup_transition() ya que es trivial.

Esa es la forma en que declaro las máquinas durante años.

Prefiero usar punteros de función sobre declaraciones de switch gigantescas, pero a diferencia de la respuesta de qrdl, normalmente no uso códigos de retorno explícitos o tablas de transición.

Además, en la mayoría de los casos, querrás un mecanismo para pasar datos adicionales. Aquí hay un ejemplo de máquina de estado:

 #include  struct state; typedef void state_fn(struct state *); struct state { state_fn * next; int i; // data }; state_fn foo, bar; void foo(struct state * state) { printf("%s %i\n", __func__, ++state->i); state->next = bar; } void bar(struct state * state) { printf("%s %i\n", __func__, ++state->i); state->next = state->i < 10 ? foo : 0; } int main(void) { struct state state = { foo, 0 }; while(state.next) state.next(&state); } 

Las máquinas de estado no son algo que inherentemente necesita un tutorial para ser explicado o incluso utilizado. Lo que sugiero es que eche un vistazo a los datos y cómo deben ser analizados.

Por ejemplo, tuve que analizar el protocolo de datos para una computadora de vuelo en globo Near Space , almacenó datos en la tarjeta SD en un formato específico (binario) que debía analizarse en un archivo separado por comas. Usar una máquina de estado para esto tiene más sentido, porque dependiendo de la siguiente información necesitamos cambiar lo que estamos analizando.

El código está escrito usando C ++, y está disponible como ParseFCU . Como puede ver, primero detecta qué versión estamos analizando, y desde allí ingresa a dos máquinas de estados diferentes.

Entra en la máquina de estado en un estado conocido, en ese punto comenzamos a analizar y, dependiendo de qué caracteres encontremos, pasamos al siguiente estado o volvemos a un estado anterior. Básicamente, esto permite que el código se autoadapte en la forma en que se almacenan los datos y si existen o no ciertos datos.

En mi ejemplo, la cadena de GPS no es un requisito para que la computadora de vuelo se registre, por lo que el procesamiento de la cadena de GPS se puede omitir si se encuentran los bytes finales para esa escritura de registro individual.

Las máquinas de estado son simples de escribir y, en general, sigo la regla de que debería fluir. Las entradas que pasan por el sistema deberían fluir con cierta facilidad de estado a estado.

Desafortunadamente, la mayoría de los artículos sobre máquinas de estado están escritos para C ++ u otros lenguajes que tienen soporte directo para el polymorphism, ya que es bueno modelar los estados en una implementación de FSM como clases que se derivan de una clase de estado abstracta.

Sin embargo, es bastante fácil implementar máquinas de estado en C, ya sea utilizando instrucciones de conmutación para enviar eventos a estados (para FSM simples, prácticamente codifican) o usando tablas para asignar eventos a transiciones de estado.

Hay un par de artículos simples pero decentes sobre un marco básico para máquinas de estado en C aquí:

Editar : Sitio “en mantenimiento”, enlaces de archivo web:

las máquinas de estado basadas en sentencias switch menudo usan un conjunto de macros para ‘ocultar’ la mecánica de la instrucción switch (o usan un conjunto de instrucciones if / then / else vez de un switch ) y crean lo que equivale a un “lenguaje FSM” para describiendo la máquina de estado en la fuente C. Yo personalmente prefiero el enfoque basado en tablas, pero estos ciertamente tienen mérito, son ampliamente utilizados y pueden ser efectivos especialmente para FSM más simples.

Steve Rabin esbozó uno de estos marcos en “Game Programming Gems” Capítulo 3.0 (Diseño de un motor robusto general de inteligencia artificial) .

Un conjunto similar de macros se trata aquí:

Si también está interesado en implementaciones de máquinas de estados C ++, puede encontrar muchas más. Voy a publicar punteros si estás interesado.

El modelado en tiempo real orientado a objetos fue fantástico (publicado en 1994 y ahora se vende por tan solo 81 centavos, más $ 3.99 de envío).

Hay mucha lección para aprender a fabricar máquinas de estado en C, pero permítanme sugerir el comstackdor de máquina de estado de Ragel:

http://www.complang.org/ragel/

Tiene una forma bastante simple de definir máquinas de estado y luego puedes generar gráficos, generar código en diferentes estilos (guiado por tablas, guiado por goto), analizar ese código si quieres, etc. Y es poderoso, se puede usar en producción código para varios protocolos.

Esto es todo lo que necesitas saber.

 int state = 0; while (state < 3) { switch (state) { case 0: // Do State 0 Stuff if (should_go_to_next_state) { state++; } break; case 1: // Do State 1 Stuff if (should_go_back) { state--; } else if (should_go_to_next_state) { state++; } break; case 2: // Do State 2 Stuff if (should_go_back_two) { state -= 2; } else if (should_go_to_next_state) { state++; } break; default: break; } } 

Las máquinas de estado pueden ser muy complejas para un problema complejo. También están sujetos a errores inesperados. Pueden convertirse en una pesadilla si alguien encuentra un error o necesita cambiar la lógica en el futuro. También son difíciles de seguir y depurar sin el diagtwig de estado. La progtwigción estructurada es mucho mejor (por ejemplo, probablemente no use una máquina de estado en el nivel principal). Puede utilizar la progtwigción estructurada incluso en el contexto de interrupción (que es donde normalmente se usan máquinas de estado). Consulte este artículo “Macros para simular código multitarea / locking en el nivel de interrupción” que se encuentra en codeproject.com.