# HFSM2 ## Overview [HFSM2](https://github.com/andrew-gresyk/HFSM2) is a feature-rich header-only hierarchical FSM framework written in C++ using template meta-programming, distributed under permissive [MIT license](https://github.com/andrew-gresyk/HFSM2/blob/master/LICENSE). Originally conceived as a traditional hierarchical state machine framework, over the years it evolved into a powerful decision making system, incorporating a variety of features usually found in dedicated AI formalisms. [HFSM2 ](https://github.com/andrew-gresyk/HFSM2)is an evolution of [HFSM](https://github.com/andrew-gresyk/HFSM), and being actively developed with the new features to empower the developers in embedded, robotics, game development, and other high-performance domains. ## Under Construction [doc.hfsm.dev](https://doc.hfsm.dev/) is the new home for [HFSM2](https://github.com/andrew-gresyk/HFSM2). Older [GitHub Project Wiki](https://github.com/andrew-gresyk/HFSM2/wiki) might have more information on a particular topic. ## Project Resources * [GitHub](https://hfsm.dev) * [Gitter](https://gitter.im/andrew-gresyk/HFSM2) * [Blog](https://gresyk.dev/) * [Twitter](https://twitter.com/andrew_gresyk) # Quick Tutorial 1\. Include the C/C++ headers ```cpp #include ``` 2\. Configure optional [HFSM2](https://hfsm.dev/) functionality using `#define`s\ (in this case we're using Plans to make transition cycle more straightforward): ```cpp #define HFSM2_ENABLE_PLANS ``` 3\. Include [HFSM2](https://hfsm.dev/) header: ```cpp #include ``` 4\. Define interface class between the state machine and its host\ (also ok to use the host object itself): ```cpp struct Context { bool powerOn; }; ``` 5\. (Optional) Define type config: ```cpp using Config = hfsm2::Config::ContextT; ``` 6\. (Optional, recommended) Define`hfsm2::Machine` for convenience: ```cpp using M = hfsm2::MachineT; ``` 7\. Declare state machine structure.\ States need to be forward declared, e.g. with a magic macro: ```cpp #define S(s) struct s using FSM = M::PeerRoot< S(Off), // initial top-level state M::Composite, S(Done) >; #undef S ``` 8\. (Optional) While [HFSM2](https://hfsm.dev/) transitions aren't event-based, events can be used to have FSM react to external stimuli: ```cpp struct Event {}; ``` 9\. Define states and override required state methods: ```cpp struct Off : FSM::State { void entryGuard(FullControl& control) { // called before state activation, use to re-route transitions if (control.context().powerOn) // access shared data control.changeTo(); // initiate a transition into 'On' region } }; ``` ```cpp struct On : FSM::State { void enter(PlanControl& control) { // called on state activation auto plan = control.plan(); // access the plan for the region plan.change(); // sequence plan steps, executed when the previous state succeeds plan.change(); plan.change(); plan.change(); } void exit(PlanControl& /*control*/) {} // called on state deactivation void planSucceeded(FullControl& control) { // called on the successful completion of all plan steps control.changeTo(); } void planFailed(FullControl& /*control*/) {} // called if any of the plan steps fails }; ``` ```cpp struct Red : FSM::State { void update(FullControl& control) { // called on periodic state machine updates control.succeed(); // notify successful completion of the plan step } // plan will advance to the 'Yellow' state }; ``` ```cpp struct Yellow : FSM::State { void update(FullControl& control) { control.succeed(); // plan will advance to the 'Green' state on the first entry // and 'Red' state on the second one } }; ``` ```cpp struct Green : FSM::State { void react(const Event&, FullControl& control) { // called on external events control.succeed(); // advance to the next plan step } }; ``` ```cpp struct Done : FSM::State {}; ``` 10\. Write the client code to use your new state machine: ```cpp int main() { ``` 11\. Create context and state machine instances: ```cpp Context context; context.powerOn = true; FSM::Instance fsm{context}; assert(fsm.isActive()); // activated by Off::entryGuard() assert(fsm.isActive()); // On's initial sub-state ``` 12\. Call `FSM::update()` for the FSM to process transitions: ```cpp fsm.update(); assert(fsm.isActive()); // 1st setp of On's plan fsm.update(); assert(fsm.isActive()); // 2nd setp of On's plan ``` 13\. (Optional) Event reactions also cause transitions to be processed: ```cpp fsm.react(Event{}); assert(fsm.isActive()); // 3rd setp of On's plan ``` 14\. Keep updating the FSM for as long as necessary: ```cpp fsm.update(); assert(fsm.isActive()); // 4th setp of On's plan fsm.update(); assert(fsm.isActive()); // activated by On::planSucceeded() return 0; } ``` ## See Also [snippets/wiki\_tutorial.cpp](https://github.com/andrew-gresyk/HFSM2/blob/master/examples/snippets/wiki_tutorial.cpp) # General Information # History The predecessor of [HFSM2](https://hfsm.dev/) has been created in 2013 in C# for a 3D platformer game in Unity. UML statechart has been considered, and ultimately rejected. Instead, the decision has been made to create yet another state machine framework based on the actual needs of the project. The C# framework supported: * 2 types of regions: `Composite` and `Orthogonal` * 3 kinds of transitions: `Restart()`, `Resume()` and `Schedule()` It has been used for most of the game objects, including: * Animated player character (\~50 states total) * Doors * Game menus * etc. After the release of VS 2013 (which debuted with C++ variadic templates), the first version of HFSM has been developed with the idea to exploit variadic teplates to generate the entire FSM structure at compile time. [HFSM](https://github.com/andrew-gresyk/HFSM) 1 has been [presented](https://gresyk.dev/presentations/2017/04/11/hfsm-for-videogames.html) for the first time at the [C++ London](https://www.meetup.com/CppLondon/)’s [April 2017 Meetup](https://www.meetup.com/CppLondon/events/237580202/). At the end of September 2018, [HFSM](https://github.com/andrew-gresyk/HFSM) evolved into [HFSM2](https://github.com/andrew-gresyk/HFSM2). [HFSM](https://github.com/andrew-gresyk/HFSM) used a variation of the Robin Hood hash table to map `stateId` (implemented using [std::type\_info](https://en.cppreference.com/w/cpp/types/type_info)) and state info. Starting with [HFSM2](https://github.com/andrew-gresyk/HFSM2), the `stateId` became a cumulative index of the state, which is known for every state at compile time. # Goals [HFSM2](https://hfsm.dev/) has been created to provide a feature complete FSM framework for the needs of game and embedded development projects. It uses template meta-programming to generate the layout of the FSM instance at compile time, sacrificing build times for reduced memory footprint and improved performance. Beyond the basic FSM features, [HFSM2](https://hfsm.dev/) offers a set of advanced functionality, including: * serialization * improved debugging tools * dynamic planning * etc. # Development Principles ## High Performance [HFSM2](https://github.com/andrew-gresyk/HFSM2) uses template meta-programming to generate **optimal code** for a given FSM topology. It does not use performance-prohibitive dynamic allocation, virtual methods, complex algorithms. The structural information is **statically encoded** into the FSM instance **type**, which removes the need for complex lookups, and internal bookkeeping logic can always **access** the required information **directly**. ## Small Footprint With memory access being the performance bottleneck on modern architectures, small data structures **fit better** in memory **caches**, not only resulting in **better performance** for the FSM instance itself, and also leaving more **resources available** to be used by the other parts of the host application. Additionally, low memory requirements make [HFSM2](https://github.com/andrew-gresyk/HFSM2) a **good fit** for the memory-constrained environments including **embedded** systems and **robotics**. ## Powerful Feature Set [HFSM2](https://github.com/andrew-gresyk/HFSM2) evolution is driven by the **development experience** rather than dry mathematical theory. The tools provided by the library are not restricted to conform to an external standard, and the ideas for the **new features** come from from both the **solutions** to the **typical** problems encountered in development, and **competing** decision making **methodologies**, including behavior trees, utility theory and AI planners. ## No Artificial Limitations [HFSM2](https://github.com/andrew-gresyk/HFSM2) will not hold you back following questionable conventions.\ It's goal is to **empower the developer** instead. It does not support any artificial standards (including UML), but rather **provides tools** that make sense in a given setting. There are no superfluous **transition tables**, beyond the one **defined implicitly** in your client code. # Future Plans * Behavior tree -style resolve transitions # User Guide # Getting Started # Configuration [HFSM2](https://hfsm.dev/) can be configured to satisfy particular requirements using: * [Feature macros](https://doc.hfsm.dev/user-guide/configuration/feature-macros) * [Type configuration](https://doc.hfsm.dev/user-guide/configuration/type-configuration) Heavyweight advanced features are enabled using relevant [feature macros](https://doc.hfsm.dev/user-guide/configuration/feature-macros) (e.g. `HFSM2_ENABLE_SERIALIZATION`) [Type configuration](https://doc.hfsm.dev/user-guide/configuration/type-configuration) can be used to adjust the types used in an FSM instance and sometimes require a particular feature to be enabled (e.g. `hfsm2::Config::RandomT` defining the type of the PRNG used in utility theory transitions, `HFSM2_ENABLE_UTILITY_THEORY` requires to be defined) # Feature Macros Several advanced [HFSM2](https://hfsm.dev/) features are disabled by default to improve build times for the average case, and are explicitly enabled using feature macros: | Macro | Feature | API | | --------------------------------------------------------------------------------------------------------------- | --------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | `HFSM2_ENABLE_ALL` |

All
Advanced

Features

| See below | | `HFSM2_ENABLE_UTILITY_THEORY` |

Utility
Theory
Transitions

|

Config::RankT<>
Config::UtilityT<>
Config::RandomT<>

void \*Root::utilize()

void \*Root::randomize()

void FullControl::utilize()

void FullControl::randomize()

void Plan::utilize()

void Plan::randomize()

void LoggerInterface::recordUtilityResolution() void LoggerInterface::recordRandomResolution()

| | `HFSM2_ENABLE_PLANS` | Plans |

struct Plan
struct ConstPlan
void State::planSucceeded()
void State::planFailed()
ConstPlan Control::plan()
Plan PlanControl::plan()
void FullControl::succeed()
void FullControl::fail()
void LoggerInterface::recordTaskStatus()
void LoggerInterface::recordPlanStatus()

| | `HFSM2_ENABLE_SERIALIZATION` | Serialization |

struct SerialBuffer

void \*Root::load()

void \*Root::load()

| | `HFSM2_ENABLE_TRANSITION_HISTORY` |

Transition

History

|

struct Transition

struct TransitionHistory

TransitionHistory \*Root::transitionHistory()

void \*Root::replayTransition()

void \*Root::replayTransitions()

| | `HFSM2_ENABLE_STRUCTURE_REPORT` |

Structure

Report

|

struct StructureEntry

struct Structure

Structure \*Root::structure()

struct ActivityHistory

ActivityHistory \*Root::activityHistory()

| |

HFSM2\_ENABLE\_VERBOSE\_DEBUG\_LOGand / or

HFSM2\_ENABLE\_LOG\_INTERFACE

| Logging |

void \*Root::attachLogger()
struct LoggerInterface
void LoggerInterface::recordMethod()
void LoggerInterface::recordTransition()
void LoggerInterface::recordTaskStatus()
void LoggerInterface::recordPlanStatus()
void LoggerInterface::recordCancelledPending()

void LoggerInterface::recordUtilityResolution() void LoggerInterface::recordRandomResolution()

| # Type Configuration The types used by [HFSM2](https://hfsm.dev/) can be configured using parameterized `hfsm2::MachineT` structure in place of default-configured `hfsm2::Machine`, e.g.: `using M = hfsm2::MachineT<`\ `hfsm2::Config`\ `::ContextT`\ `::RandomT`\ `>;` (from [test\_debug.cpp](https://github.com/andrew-gresyk/HFSM2/blob/master/test/test_debug.cpp)). Once `hfsm2::Config` is fully declared, it needs to be passed as a template argument into `hfsm2::MachineT<>` to define configured [HFSM2](https://hfsm.dev/) parent struct containing all derivative types used in client code. ### `hfsm2::Config` customization points: | Feature Define | Type | Used In | Default | | ----------------------------- | ----------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | ------------------------------------------------ | | | `ContextT` |

Context& Control::context()

(see Context)

| `EmptyContext` | | `HFSM2_ENABLE_UTILITY_THEORY` | `RankT` | `Rank State::rank()` | `int8_t` | | `HFSM2_ENABLE_UTILITY_THEORY` | `UtilityT` | `Utility State::utility()` | `float` | | `HFSM2_ENABLE_UTILITY_THEORY` | `RandomT` | Used internally by `randomize()` transition and `Random` region | `RandomT` | | | `SubstitutionLimitN` | Maximum number of times `State::entryGuard()`methods are allowed to substitute the transition into their class for a transition into another one during the single `*Root::update()` | `4` | | `HFSM2_ENABLE_PLANS` | `TaskCapacityN` | Total number of tasks across all plans in an FSM | 2x Number of Sub-States of All Composite Regions | # Context # Basic Features # Hierarchy # Root # Region # State # State Methods # Control # Transitions # Events # Update Cycle # Advanced Features # Transitions into Regions # Guards # Entry Guards # Exit Guards # State Injections # State Data Access # Dynamic States # Plans # Debugging and Tools # Activity Report # Structure Report # Transition History # Serialization \* ## Quick Facts * Version: [1.3](https://github.com/andrew-gresyk/HFSM2/releases/tag/1_3) * Enabled with `HFSM_ENABLE_SERIALIZATION` * Test: [test\_serialization.cpp](https://github.com/andrew-gresyk/HFSM2/blob/master/test/test_serialization.cpp) ## Interface | | | | ---------------------------------------- | ------------------------------------------------- | | `hfsm2::Root::SerialBuffer` | Buffer for serialization | | `hfsm2::Root::save(SerialBuffer&) const` | Serialize the structural configuration | | `hfsm2::Root::load(const SerialBuffer&)` | De-serialize the configuration and initialize FSM | ## Example ``` // Enable serialization #define HFSM_ENABLE_SERIALIZATION #include #include using M = hfsm2::Machine; using FSM = M::PeerRoot< struct State1, struct State2 >; struct State1 : FSM::State { /* .. */ }; struct State2 : FSM::State { /* .. */ }; int main() { // Buffer for serialization // Members: // bitSize - Number of payload bits used // payload - Serialized data FSM::Instance::SerialBuffer buffer; { FSM::Instance fsm; // Create a new FSM instance fsm.changeTo(); // Request a transition to 'State2' fsm.update(); // Process transitions assert(fsm.isActive()); // Check if transition completed fsm.save(buffer); // Serialize FSM configuration into 'buffer' } { FSM::Instance fsm; // Create a fresh FSM instance assert(fsm.isActive()); // Initial 'State1' is activated by default fsm.load(buffer); // De-serialize FSM from 'buffer' assert(fsm.isActive()); // Check its configuration is restored } } ``` ## Serialization Between Different FSMs As demonstrated in [test\_serialization.cpp](https://github.com/andrew-gresyk/HFSM2/blob/master/test/test_serialization.cpp), it is allowed to exchange the `SerialBuffer` between **different FSMs**, so long as their hierarchical **structure** is exactly **the same**. This can be useful for **network replication** between structurally equivalent server and client FSM instances implementing some specific logic. ## SerialBuffer Size and Compression [HFSM2](https://hfsm.dev/) does not compress `SerialBuffer`. However, the configuration data saved to `SerialBuffer::payload` is **tightly packed** to use the **minimal** number of **bits**. The number of **bits used** in the payload is recorded in `SerialBuffer::bitSize`, which could be used for example in custom network replication logic to minimize network bandwidth usage. Compressing `SerialBuffer` can also be used to further reduce the size serialized state. # Logging Support # Practical Topics # How-To # Designing Hierarchy # Reducing State Coupling # Reusing State Code # Common Patterns # Delayed Teardown # Users HFSM2 is used in the following projects: * [Weird West](https://store.steampowered.com/app/1097350/) [by](https://twitter.com/jeff_lake/status/1257802186119143424) [Wolfeye Studios](https://wolfeye-studios.com/)