Thread by @andrew_gresyk

A thread on #cpp #state_machine #software_design.

Random ideas around writing an FSM library, with examples from, and motivations behind hfsm.dev, a header-only library created using #cpp template #metaprogramming with #gamedev, #embedded and #robotics in mind.

*Reuse vs reimplement*

State machines can be deceptively complex, and, unless a trivial one is needed, a reusable framework is highly recommended.

Rolling out one's own for special needs is ok.

Otherwise - pick from a variety of existing solutions from #boost, on #github, etc.

*Static vs dynamic structure*

The first important decision is whether the structure of FSM could be built/changed at runtime.

The implementation of a dynamic FSM relies on heap-allocated memory, resizable containers and pointers, all of which come at a steep perf price.

If the structure is static, TMP can be used to build the structure of a particular FSM at compile time, allowing the compiler to generate smaller and faster code at the cost of increased compile times.

(Which is the way of hfsm.dev).

*Basic state methods*

Typically, state would have some equivalent of:

void enter();
void exit();

E.g. #boost::msm:
void on_entry();
void on_exit();

#boost::statechart:
ctor();
~dtor();

More on why that might be a bad idea, and on states' lifetimes - later.

*Basic transitions*

At a bare minimum, transitions should:

struct FSM {
State* states[];
State* active;
void changeTo(StateId targetId) {
active->exit();
active = states[target];
active->enter():
}
};

*Periodic updates*

If your platform's operation is based on periodical updates (e.g. UI, #gamedev), FSM needs to support that:

struct State {
void update();
};

struct FSM {
State* active;
void update() {
active->update();
}
};

FSM fsm;
while (true)
fsm.update();

*Event polling vs listening*

In C++ land, anything is an event:
- message (with or w/o payload)
- function call
- variable value change

Which makes polling viable (even if limited) event handling strategy for periodically updating FSMs.

*State IDs*

First take:

enum StateID {
STATE_1,
STATE_2,
..
STATE_COUNT
};

struct FSM {
State* getState(StateID id) { return states[id]; }
..
State* states[STATE_COUNT];
};

Simple but clumsy.
Too much boilerplate burden on user.

*Better state IDs*

Use std::type_info:

struct FSM {
template <class TState>
State* getState() { return states[typeid(TState)]; }
..
hash_table<std::type_index, State*> states;
};

Deprecated github.com/andrew-gresyk/… used this.

*Even better state IDs*

⚠️ TMP warning ⚠️

hfsm.dev uses type list to map state types to sequential array indices.

See hfsm2::_TL<>::index<>() in
github.com/andrew-gresyk/…

*State types as IDs*

Ultimately, using state types to refer to states:
- is more natural
- eliminates spelling mistakes
- makes maintenance easier
- allows for compile-time validation
- benefits from refactoring tools and search/replace
- is a major quality of life improvement

*State data interface*

Event polling FSMs need R[+W] access outside:

struct Ctx;

struct State {
void update(Ctx&);
};

struct FSM {
FSM(Ctx& c) : ctx{c} {}
void update() { active->update(ctx); }
State* active;
Ctx& ctx;
};

Ctx ctx;
FSM<Ctx> fsm{ctx};
fsm.update();

For an FSM controlling a game object - the reference to said object can be used as 'context', thus allowing FSM states to control it.

*Internal transition interface*

Take 1: Return transition from State::update():

struct State {
std::optional<StateID> update(Ctx&);
};

void FSM::update() {
if (auto tr = active->update(ctx)) {
active->exit(ctx);
active = states[*tr];
active->enter(ctx);
}
}

Better:

struct Ctrl {
template <class S> changeTo() {
dest = typeid(S);
}
Ctx& ctx();
std::optional<StateID> dest;
};

void State::update(Ctrl& c) {
c.changeTo<State2>();
}

void FSM::update() {
Ctrl c{ctx};
active->update(c);
if (auto dest = *c.dest)
...
}

As a bonus, now both internal and external transition interfaces match:

struct State1;
struct State2;

void State1::update(Ctrl& c) {
c.changeTo<State2>(); // internal
}

Ctx ctx;
FSM fsm{ctx};
fsm.changeTo<State1>(); // external

*Delayed transition processing*

Important: FSM processes transitions outside of the state methods to avoid nested out-of-order enter() / exit() calls:

void FSM::update() {
prev->update();
if (transition) {
prev->exit();
next->enter();
}
}

*Reacting to events*

Event listener-style FSM:

struct Evt;

void State::react(Evt&, Ctrl&);

void FSM::react(Evt& e) {
Ctrl c{ctx};
active->react(e, c);
if (c.dest) {
active->exit(c);
active = states[*c.dest];
active->enter(c);
}
}

@threadreaderapp unroll

*Basic introspection*

struct FSM {
template <typename S> bool isActive() const {
return active == states[typeid(S)];
}
};

*Example*

You can find the example, illustrating the concepts in this thread, implementing a minimally functional FSM in under 100 mloc: github.com/andrew-gresyk/…