Tutoriais de máquinas de estado [fechado

https://stackoverflow.com/questions/1371460

21-09-2019
|

Pergunta

Só estou me perguntando se alguém conhece alguns bons tutoriais na Internet para o desenvolvimento de máquinas de estado. Ou ebooks?

Estou começando a trabalhar em máquinas de estado e só preciso de algo geral para me iniciar.

Solução

As máquinas de estado são muito simples em C se você usar ponteiros de função.

Basicamente, você precisa de 2 matrizes - uma para ponteiros de função do estado e outro para regras de transição do estado. Toda função de estado retorna o código, você procure a tabela de transição do estado por estado e o código de retorno para encontrar o próximo estado e, em seguida, executá -lo.

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;
}

Eu não coloco lookup_transitions() função como é trivial.

É assim que faço máquinas de estado por anos.

Outras dicas

Eu prefiro usar ponteiros de função sobre gigantescos switch declarações, mas em contraste com Resposta do QRDL Normalmente, não uso códigos de retorno explícitos ou tabelas de transição.

Além disso, na maioria dos casos, você desejará um mecanismo para transmitir dados adicionais. Aqui está um exemplo de máquina de estado:

#include <stdio.h>

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);
}

As máquinas de estado não são algo que inerentemente precisa de um tutorial a ser explicado ou mesmo usado. O que eu sugiro é que você dê uma olhada nos dados e como eles precisam ser analisados.

Por exemplo, eu tive que analisar o protocolo de dados para um Perto do computador de vôo de balão espacial, ele armazenou dados no cartão SD em um formato específico (binário) que precisava ser analisado em um arquivo separado por vírgula. Usar uma máquina de estado para isso faz mais sentido, porque dependendo do que a próxima informação é que precisamos alterar o que estamos analisando.

O código é escrito usando C ++ e está disponível como Parsefcu. Como você pode ver, primeiro detecta qual versão estamos analisando e, a partir daí, entra em duas máquinas de estado diferentes.

Ele entra na máquina estadual em um estado conhecido, nesse momento começamos a analisar e dependendo de quais personagens encontramos, seguimos para o próximo estado ou voltamos para um estado anterior. Isso basicamente permite que o código se auto-adapte à maneira como os dados são armazenados e se existem ou não determinados dados.

No meu exemplo, a sequência GPS não é um requisito para o registro do computador de vôo, portanto, o processamento da string GPS pode ser ignorado se os bytes finais para essa gravação de log único for encontrada.

As máquinas de estado são simples de escrever e, em geral, sigo a regra que deve fluir. A entrada que passa pelo sistema deve fluir com certa facilidade de estado para estado.

Infelizmente, a maioria dos artigos sobre máquinas de estado é escrita para C ++ ou outros idiomas que têm suporte direto ao polimorfismo, pois é bom modelar os estados em uma implementação do FSM como classes que derivam de uma classe de estado abstrata.

No entanto, é muito fácil implementar máquinas de estado em C usando as instruções de troca para despachar eventos para os estados (para FSMs simples, eles praticamente codificam bem) ou usando tabelas para mapear eventos para transições de estado.

Existem alguns artigos simples, mas decentes, sobre uma estrutura básica para máquinas de estado em C aqui:

Editar: Site "em Manutenção", links de arquivo da web:

switch Máquinas de estado baseadas em declarações costumam usar um conjunto de macros para "ocultar" a mecânica do switch declaração (ou use um conjunto de if/then/else declarações em vez de um switch) e faça o que equivale a uma "linguagem FSM" para descrever a máquina de estado na fonte C. Pessoalmente, prefiro a abordagem baseada em mesa, mas eles certamente têm mérito, são amplamente utilizados e podem ser eficazes especialmente para o FSMS mais simples.

Uma dessas estruturas é descrita por Steve Rabin em "Game Programming Gems" Capítulo 3.0 (projetando um motor de IA robusto geral).

Um conjunto semelhante de macros é discutido aqui:

https://contário

Se você também estiver interessado nas implementações de máquinas de estado C ++, há muito mais que pode ser encontrado. Vou postar dicas se você estiver interessado.

Modelagem orientada a objetos em tempo real foi fantástico (publicado em 1994 e agora vendido por apenas 81 centavos, mais US $ 3,99 frete).

Isso é tudo que você precisa 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;
    }
}

Há muita lição para aprender máquinas de estado de criação de manobras em C, mas também sugira o compilador de máquinas Ragel State:

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

Ele tem uma maneira bastante simples de definir máquinas de estado e, em seguida, você pode gerar gráficos, gerar código em diferentes estilos (orientados por mesa, acionados por goto), analisar esse código se quiser, etc. e é poderoso, pode ser usado na produção código para vários protocolos.

As máquinas de estado podem ser muito complexas para um problema complexo. Eles também estão sujeitos a bugs inesperados. Eles podem se transformar em um pesadelo se alguém encontrar um bug ou precisar mudar a lógica no futuro. Eles também são difíceis de seguir e depurar sem o diagrama do estado. A programação estruturada é muito melhor (por exemplo, você provavelmente não usaria uma máquina de estado no nível principal). Você pode usar a programação estruturada, mesmo no contexto de interrupção (que é onde as máquinas de estado geralmente são usadas). Veja este artigo "Macros para simular o código multitarefa/bloqueio no nível de interrupção" Encontrado em codeProject.com.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow