Sundays at AiGameDev.com is dedicated to explaining problems visually using sketches. This article extrapolates from last week’s discussion (thanks Sergio) and explains different ways of looking at hierarchies.
Most developers say they use a “HFSM” in their games. But you’ll be surprised how different their technology can be — despite them using the same name to describe it.
There are two reasons why you want a hierarchy for your finite state machine:
To provide ways to re-use logic by sharing external transitions.
To help split up the problem internally into sub-parts.
Granted, there’s a certain overlap between these two concepts, but yet they are orthogonal issues (you can do one without doing the other). Here are two opposing examples, one FSM for animation and the other for AI behaviors.
Using Groups of States to Share Transitions
Say you want to build a finite state machine for an animation system. In this case, you need:
Complete control over every low-level state in the system, so you can make sure the correct animation is played in every case.
A set of tools to help you reuse logic so that you don’t have too much redundancy in the transitions.
To build this kind of FSM, you do the following:
You build the system as a flat state machine by default, only grouping states together to reuse transition logic.
You follow the process of reusing logic by “tagging,” e.g. you can dive/sprint/crouch from this state.
You think from the bottom-up deciding which transitions each state should inherit.
You always edit the FSM as a whole to keep the big picture, as much of the system doesn’t make sense when broken down into small parts.
When you do this, the hierarchy becomes loose collection of states used informally to reduce redundant logic by sharing transitions.
Making Modular FSM and Assembling them Hierarchically
Now on the other hand, assuming you want to build a FSM for high-level AI, you’d need:
A well-structured strict hierarchy that will scale to handle many states.
A logical way to break down states based on recursively decomposing tasks.
Fully modular states so that they can be changed locally without risking breaking the rest of the logic.
To build this kind of system, you follow these steps:
You create many small modular FSMs that handle sub-parts of the problem witohut refering to any other FSM.
You think from the top-down by breaking up problems into smaller modular parts.
You build a tree structure that reflects the AI solving problems recursively.
You design your editor as a tree editor rather than tag-based like in the animation system.
When you do this, the hierarchy becomes a strict tree of nested states, each completely encapsulated to define sub-behaviors modularly.
Finding a Compromise
Now ideally, you want to be able to use both. But sadly, you can’t get complete control at the lowest-level if you have states that are encapsulated modularly, and vice versa. So, it’s always a trade-off!
How would you approach this problem?