Mi chiedo solo se qualcuno sa di alcuni buoni tutorial su Internet per lo sviluppo di macchine a stati. O ebooks?tutorial macchine stato
Sto iniziando a lavorare su macchine di stato e ho solo bisogno di qualcosa di generale per iniziare.
Le macchine di stato sono molto semplici in C se si utilizzano i puntatori di funzione.
Fondamentalmente sono necessari 2 array: uno per i puntatori funzione stato e uno per le regole di transizione stato. Ogni funzione di stato restituisce il codice, si ricerca la tabella di transizione di stato in base allo stato e il codice di ritorno per trovare lo stato successivo e quindi solo eseguirlo.
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;
}
Non inserisco la funzione lookup_transition() in quanto è banale.
Questo è il modo in cui faccio macchine di stato per anni.
Bello, grazie per questo. L'unica pecca possibile qui è che le route di ricerca saranno probabilmente lineari (O (n)) con questa infrastruttura della tabella di transizione. È possibile renderlo migliore con array multidimentale - garantito O (1). Es. la tabella può essere rappresentata come un array multidimentale dove key è stato e il valore è un array dove la chiave è il codice di ritorno e il valore è lo stato successivo: 'int state_transitions [] [3] = {[voce] = { foo, end, foo}, ...}/* ok, fail, repeat */' – Alex
Perché le funzioni di stato non restituiscono enum al posto di inte per la funzione di ricerca? Non stai restituendo un codice di ritorno? – Django
Non sarebbe molto più semplice avere 'src_state' e' dst_state' come puntatori di funzione? Non capisco il vantaggio di averli di tipo enum, quando tutti li usi per cercare alcuni puntatori di funzione in un array. – Multisync
Questo è tutto ciò che devi sapere.
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;
}
}
Considero una procedura migliore per impostare esplicitamente lo stato, ma questo è solo per me. –
Sarebbe una buona pratica per gli eventi nominare lo stato. Lascia che ti aggiusti. – ChaosPandion
Hai omesso molto, ad esempio: sottostati; eventi e combinazioni evento/stato; diagrammi di transizione di stato; guardie ("non cambiare stato se"); metodi di entrata e uscita dallo stato ("all'uscita da questo stato segui il seguente metodo"). – ChrisW
Real-Time Object-Oriented Modeling era fantastico (pubblicato nel 1994 e ora in vendita per meno di 81 centesimi, più $ 3,99 SPEDENDO).
Le macchine di stato non sono qualcosa che richiede intrinsecamente un tutorial per essere spiegato o utilizzato. Quello che suggerisco è che date un'occhiata ai dati e come deve essere analizzato.
Ad esempio, ho dovuto analizzare il protocollo dei dati per un Near Space balloon flight computer, ha memorizzato i dati sulla scheda SD in un formato specifico (binario) che doveva essere analizzato in un file separato da virgole. Usare una macchina a stati per questo ha più senso perché, a seconda di quale sarà il prossimo bit di informazione, è necessario modificare ciò che stiamo analizzando.
Il codice è scritto utilizzando C++ ed è disponibile come ParseFCU. Come puoi vedere, in primo luogo rileva quale versione stiamo analizzando e da lì entra in due diverse macchine a stati.
Entra nella macchina a stati in uno stato noto, a quel punto iniziamo l'analisi e, a seconda dei personaggi che incontriamo, passiamo allo stato successivo o torniamo a uno stato precedente. Questo in pratica consente al codice di adattarsi automaticamente al modo in cui i dati vengono archiviati e se alcuni dati esistono o no.
Nel mio esempio, la stringa GPS non è un requisito per il log di volo da registrare, quindi l'elaborazione della stringa GPS può essere ignorata se si trovano i byte finali per quella singola scrittura di registro.
Le macchine di stato sono semplici da scrivere e in generale seguo la regola che dovrebbe scorrere. L'input che attraversa il sistema dovrebbe scorrere con una certa facilità da stato a stato.
Solo curioso: come fa un palloncino a "avvicinarsi allo spazio"? I palloncini non hanno bisogno di un'atmosfera? Non arriveresti al punto in cui è difficile/impossibile tornare? –
@Chris: lo spazio vicino è definito come qualcosa sopra i 60.000 piedi, il nostro palloncino arriva a 92.999 piedi. A un certo punto il pallone in lattice inizia a diventare così grande a causa della decompressione (il gas continua ad espandere il palloncino) che il palloncino si apre, a quale punto il mestiere di spazio vicino cade di nuovo alla terra (noi attacciamo un paracadute fuori rotta), vedi il Wiki collegato per ulteriori informazioni sui nostri sforzi di Near Space e Google intorno, è un hobby assolutamente terrificante! –
Questo suona come un passatempo estremamente inefficiente, incredibilmente costoso, forse un po 'dispendioso e assolutamente fantastico. –
Sfortunatamente, la maggior parte degli articoli su macchine a stati sono scritti per C++ o altri linguaggi che hanno il supporto diretto per il polimorfismo, poiché è bello modellare gli stati in un'implementazione di FSM come classi che derivano da una classe di stato astratta.
Tuttavia, è abbastanza semplice implementare macchine di stato in C utilizzando le istruzioni di commutazione per inviare eventi agli stati (per gli FSM semplici, praticamente tutto il codice) o utilizzare le tabelle per associare gli eventi alle transizioni di stato.
ci sono un paio di semplici, ma gli articoli decenti su un quadro di base per macchine a stati in C qui:
Edit: Sito "in manutenzione ", collegamenti all'archivio web:
switch macchine a stati economico-based utilizzano spesso un insieme di macro per 'nascondere' i meccanismi della dichiarazione switch (o utilizzare un insieme di if/then/else dichiarazioni invece di un switch) e creare ciò che equivale a un "linguaggio FSM" per descrivere la macchina a stati nella sorgente C. Personalmente preferisco l'approccio basato su tabelle, ma sicuramente hanno un merito, sono ampiamente utilizzate e possono essere efficaci soprattutto per le FSM più semplici.
Uno schema simile è delineato da Steve Rabin nel "Game Programming Gems" Chapter 3.0 (Designing a General Robust AI Engine).
Un simile insieme di macro è discusso qui:
Se siete interessati a C++ implementazioni della macchina statale c'è molto di più che si possono trovare anche. Posterò i puntatori se sei interessato
Grazie, erano buoni articoli. Ne ho trovato uno anche qui. http://en.wikipedia.org/wiki/Event_driven_finite_state_machine – ant2009
Ci sono un sacco di lezione da imparare artigianale macchine a stati in C, ma mi permetta di suggerire anche Ragel macchina a stati compilatore:
http://www.complang.org/ragel/
Ha modo molto semplice di definire macchine a stati e poi si può generare grafici, generare codice in diversi stili (basato su tabella, goto-driven), analizzare il codice se lo si desidera, ecc. Ed è potente, può essere utilizzato nel codice di produzione per vari protocolli.
Preferisco utilizzare i puntatori di funzione su gigantesche istruzioni switch, ma in contrasto con qrdl's answer Normalmente non utilizzo codici di ritorno espliciti o tabelle di transizione.
Inoltre, nella maggior parte dei casi è necessario un meccanismo per trasmettere dati aggiuntivi. Ecco un esempio di macchina di stato:
#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);
}
Le macchine di stato possono essere molto complesse per un problema complesso. Sono anche soggetti a errori imprevisti. Possono trasformarsi in un incubo se qualcuno si imbatte in un bug o ha bisogno di cambiare la logica in futuro. Sono anche difficili da seguire e eseguire il debug senza il diagramma di stato. La programmazione strutturata è molto migliore (ad esempio, probabilmente non si utilizzerà una macchina a stati a livello di linea principale). È possibile utilizzare la programmazione strutturata anche in contesto di interrupt (che è dove vengono generalmente utilizzate le macchine di stato). Vedi questo articolo "Macros to simulate multi-tasking/blocking code at interrupt level" trovato su codeproject.com.
Vedere anche qui: http://stackoverflow.com/questions/1647631/c-state-machine-design/1647679#1647679 – paxdiablo