state machines tutorials
Solution 1
State machines are very simple in C if you use function pointers.
Basically you need 2 arrays - one for state function pointers and one for state transition rules. Every state function returns the code, you lookup state transition table by state and return code to find the next state and then just execute it.
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;
}
I don't put lookup_transitions()
function as it is trivial.
That's the way I do state machines for years.
Solution 2
I prefer using function pointers over gigantic switch
statements, but in contrast to qrdl's answer I normally don't use explicit return codes or transition tables.
Also, in most cases you'll want a mechanism to pass along additional data. Here's an example state machine:
#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);
}
Solution 3
Unfortunately, most of the articles on state machines are written for C++ or other languages that have direct support for polymorphism as it's nice to model the states in an FSM implementation as classes that derive from an abstract state class.
However, it's pretty easy to implement state machines in C using either switch statements to dispatch events to states (for simple FSMs, they pretty much code right up) or using tables to map events to state transitions.
There are a couple of simple, but decent articles on a basic framework for state machines in C here:
- http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation/
- http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/
Edit: Site "under maintenance", web archive links:
- http://web.archive.org/web/20160517005245/http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation
- http://web.archive.org/web/20160808120758/http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/
switch
statement-based state machines often use a set of macros to 'hide' the mechanics of the switch
statement (or use a set of if
/then
/else
statements instead of a switch
) and make what amounts to a "FSM language" for describing the state machine in C source. I personally prefer the table-based approach, but these certainly have merit, are widely used, and can be effective especially for simpler FSMs.
One such framework is outlined by Steve Rabin in "Game Programming Gems" Chapter 3.0 (Designing a General Robust AI Engine).
A similar set of macros is discussed here:
If you're also interested in C++ state machine implementations there's a lot more that can be found. I'll post pointers if you're interested.
Solution 4
State machines are not something that inherently needs a tutorial to be explained or even used. What I suggest is that you take a look at the data and how it needs to be parsed.
For example, I had to parse the data protocol for a Near Space balloon flight computer, it stored data on the SD card in a specific format (binary) which needed to be parsed out into a comma seperated file. Using a state machine for this makes the most sense because depending on what the next bit of information is we need to change what we are parsing.
The code is written using C++, and is available as ParseFCU. As you can see, it first detects what version we are parsing, and from there it enters two different state machines.
It enters the state machine in a known-good state, at that point we start parsing and depending on what characters we encounter we either move on to the next state, or go back to a previous state. This basically allows the code to self-adapt to the way the data is stored and whether or not certain data exists at all even.
In my example, the GPS string is not a requirement for the flight computer to log, so processing of the GPS string may be skipped over if the ending bytes for that single log write is found.
State machines are simple to write, and in general I follow the rule that it should flow. Input going through the system should flow with certain ease from state to state.
Solution 5
This is all you need to know.
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;
}
}
Related videos on Youtube
ant2009
Updated on July 05, 2022Comments
-
ant2009 almost 2 years
I am just wondering if anyone know of some good tutorials on the Internet for developing state machines. Or ebooks?
I am starting working on state machines and just need something general to get me started.
-
paxdiablo over 14 yearsSee also here: stackoverflow.com/questions/1647631/c-state-machine-design/…
-
-
visual_learner almost 15 yearsI woud consider it better practice to explicitly set the state, but that's just me.
-
ChaosPandion almost 15 yearsIt would be event better practice to name the state. Let me fix that.
-
ChrisW almost 15 yearsYou've left out a lot, for example: substates; events, and event/state combinations; state transition diagrams; guards ("don't change state if"); state entry and state exit methods ("on exiting this state do the following method").
-
X-Istence almost 15 yearsThis is oversimplifying state machines, and not that great of an example.
-
marcc almost 15 years1 new from $60.20 and 24 used from $0.81. That's pretty humorous.
-
ChaosPandion almost 15 yearsDon't over complicate something that is very simple.
-
visual_learner almost 15 yearsJust curious - how does a balloon get "near space"? Don't balloons need an atmosphere? Wouldn't you get to the point where it's hard/impossible to come back?
-
X-Istence almost 15 years@Chris: Near Space is defined as anything above 60,000 ft, our balloon got to 92,999 ft. At some point the latex balloon starts to become so large because of the decompression (the gas keeps expanding the balloon) that the balloon pops, at which point the near space craft free-falls back to earth (we attach a parachute off course), see the linked Wiki for more information about our Near Space efforts and Google around, it is an absolutely awesome hobby!
-
mrduclaw almost 15 yearsSure, as a skeleton for what a basic state machine might look like this might suffice. But I think it's not quite "all you need to know". Also, you might want to make your state unsigned.
-
ant2009 almost 15 yearsThanks, they were good articles. I found one here also. en.wikipedia.org/wiki/Event_driven_finite_state_machine
-
visual_learner almost 15 yearsThat sounds like a wildly inefficient, ridiculously expensive, perhaps a bit wasteful, and completely awesome hobby.
-
dmckee --- ex-moderator kitten almost 15 yearsMany powerful and important experiments have been run from balloon platforms, you have to compare costs with the those of launching an equivalent orbiting platform. By the time you get to circa 100,000 ft, your heat management problem is essential that of a spacecraft: conductive and convective heating/cooling are vanishing by comparison to radiation.
-
X-Istence almost 15 years@Chris: We had a budget of $2000 to work with, and we have so far successfully launched two balloons. The most expensive part was the helium to fill the latex balloons which were the second most expensive part.
-
TOMKA over 14 yearsYour
main
doesn't return a value . . . should it? -
Christoph over 14 years@dreamlax: C99 5.1.2.2.3: reaching the end of
main()
implicitly returns0
-
Alex over 10 yearsNice, thanks for this. The only thing possible flaw here is that the lookup_transitions will likely be linear (O(n)) with this transition table datastructure. Its possible to make it better with multidimentional array - guaranteed O(1). Eg. the table can be represented as a multidimentional array where key is state and the value is an array where the key is the return code and value is the next state:
int state_transitions[][3] = { [entry] = { foo, end, foo }, ... } /* ok, fail, repeat */
-
Carl over 10 yearsInteresting that the referrer on that link is StackOverflow.
-
ChrisW over 10 years
-
AntonioCS over 9 yearsReally liked this answer. Simple and direct. Good job.
-
Django about 8 yearsWhy don't your state functions return enum instead of ints for the lookup function? You're returning a ret code are you not?
-
Multisync almost 8 yearsSorry, I really don't get it. What happens in the
while
condition in the last line? Are you callingfoo()
? Which default arguments are assumed if none are given? -
Multisync almost 8 yearsWouldn't it be much easier to just have
src_state
anddst_state
as function pointers? I don't understand the benefit of having them of enum type, when all you use them for is to look up some function pointers in an array. -
qrdl almost 8 years@Multisync Generally speaking, state != function, it is common to have several different states that in fact use the same function. For example, you can have couple of functions that prepare message, and one function to send it and one function to receive response, but these two I/O functions will be used in different states.
-
Dan Bechard over 7 years@Multisync The struct initializer in the previous line sets
state.next
(a function pointer) to the address offoo
. Sostate.next(&state)
is the same asfoo(&state)
(the first iteration of the loop, it points elsewhere later). For comparison, if this were C++,foo()
would be a member of theState
class (State::foo()
) and would not take any parameters. It's body would usethis->next = bar
instead ofstate->next = bar
. In C you have to pass the equivalent of thethis
pointer explicitly as there are no stateful class scopes. -
Dan Bechard over 7 years@ChrisLutz I'd argue the exact opposite. Compared to the alternative: rockets; It's by far more efficient, less expensive and significantly less wasteful, but slightly less awesome.
-
scooby over 7 yearsFunny that the discussion moved from function pointers to balloons. !! :)
-
MrBit over 6 yearsDoesn't this way consume more ram than just using a big if, else if, else pattern? Would this be harmless in embedded systems?
-
Ashley Duncan over 6 yearsBesides perhpaps labelling the states, this covers most of the simple state machine implementations I have come across. Some people like to complicate it to demonstate their langauge prowess. Keep it simple if it is simple...
-
Stephen305 about 5 yearsLinks are broken. See the following Github repository for the project: github.com/bertjwregeer/bertjwregeer.com/blob/master/input/…
-
Fuevo over 4 yearsAny state can be considered as one "sub_main_function", due the the actions in these "sub_main_functions", it can change to different state again, let's use a switch, each "case state:" has multi functions in side, anyone with me?
-
the_endian over 4 yearsDoesn't answer the question. Instead, goes on an editorial about why state machines are bad.
-
Theo d'Or over 3 yearsUpvoted, for being close to the only correct answer, though the exact wording and the provided link are unfortunate. Automata theory that encompasses state machines is a mathematical model of computation with no direct practical application. We use programming languages said to be Turing-complete on computers that are themselves state machines, and we would not use them to simulate a Turing machine, would we? Why then would we simulate a constrained sub-concept? The algorithms described by the other answers on this page are a retardation and a sign of the crowd mentality in programming.