Hierarchical state machines are a very convenient design pattern for character control in video games. In two recent games I worked on (an adventure game and a platformer), my team used a data-driven, policy-based hierarchical state machine engine to drive the character animations.
Data-Driven
A data-driven model provides two main advantages. First, it allows for the use of a declarative scripting language to construct the state machines for the characters in the game. That way, designers and other content creators can create new character behaviors and modify existing ones.
Second, a data-driven approach makes possible the creation of a GUI tool for editing a character’s behavior. A GUI combined with a scripting language can make iterating over a character’s behavior a very quick and satisfying process for designers.
Policy-Based
Abstracting a state’s child activation policy outside of the state’s hierarchy lends itself to some interesting results.
The traditional state machine policy is transition-based. An event entering the system, combined with the systems current state, results in a change of state. Every state in the state machine lists its transitions explicitly.
I refer to this policy as the Explicit Transition Activation Policy.
Other activation policies we implemented are:
- Sequential Activation Policy - each child state is activated in sequence starting with the first child. The sequence is advanced when the active child’s Post Condition evaluates to TRUE.
- Priority Activation Policy - the highest priority child state whose Pre Condition is TRUE is activated. Typically, the lowest priority child has no Pre Conditions, resulting in an always TRUE Pre Condition. We refer to this as the ground state.
- Concurrent Activation Policy - all child states are activated whenever the containing state is activated.
Pre Conditions, Post Conditions, and Triggers
Every state has a (possibly empty) set of Pre Conditions and Post Conditions. Each activation policy type interprets these differently.
Pre Conditions and Post Conditions evaluate to either TRUE or FALSE. Their value is derived from the value of a Trigger state (which are also either TRUE or FALSE).
Triggers are the mechanism with which a system event is translated into a TRUE or FALSE value that can be used as a Post Condition or Pre Condition.
For example, a common Trigger in our games is the Animation Finish Trigger. This trigger responds to Animation Finish Events. An Animation Finish Trigger and an Animation Finish Event both have a string property containing the name of the animation. When this Event is received by the state machine, and the animation name happens to match the animation name of the Trigger, the Trigger’s activation status becomes TRUE.
Another common Trigger is the Timer Expired Trigger.
Enter Actions and Exit Actions
Every state has a (possibly empty) set of Enter Actions and Exit Actions. These are fired whenever its state is entered (activated) or exited (deactivated), respectively. An Action is nothing more than a wrapper around an Event generated from within the state machine itself.
Common Action types are the Play Animation Action and the Start Timer Action.
Examples
The platformer we used this engine for was a run-jump-attack, 3D platformer. There are several related and reusable state machine patterns that we catalogued during the game’s development.
Basic Attack
The basic attack is executed whenever the player presses the basic attack button, while the character is in the idle state. The attack animation would play out entirely, then the character would return to the idle state.
Following is the state machine for such a simple character:
Machine
{
State<Priority>("Character")
{
State("BasicAttack")
{
Precondition<InputTrigger>("BasicAttackButton");
Enter<PlayAnimation>("BasicAttack", /*loop=*/false);
Enter<PlaySound>("BasicAttack", /*loop=*/false);
Enter<EnableDamageCollision>("BasicAttack", /*damage=*/1.0f);
Exit<DisableDamageCollision>("BasicAttack");
Postcondition<AnimationFinishTrigger>("BasicAttack");
}
State("Idle")
{
Enter<PlayAnimation>("Idle", /*loop=*/true);
}
}
}
Combination Attack
The combination attack is a complex sequence of attacks that are played out if the player keeps pressing the advanced attack button within designer-tunable windows of opportunity. Each attack in the combination does increasingly more damage to enemies.
Following is the state machine for this character:
Machine
{
State<Priority>("Character")
{
State<Sequential>("ComboAttack")
{
Precondition<InputTrigger>("ComboAttackButton");
State<ExplicitTransition>("ComboAttack1")
{
Enter<EnableDamageCollision>("ComboAttack1",
/*damage=*/2.0f);
State("Pre")
{
Enter<PlayAnimation>("ComboAttack1", /*loop=*/false);
Enter<PlaySound>("ComboAttack1", /*loop=*/false);
Enter<StartTimer>("Pre", /*delay=*/0.75f);
Transition<TimerExpiredTrigger>("Pre")("Window");
}
State("Window")
{
Enter<StartTimer>("Window", /*delay=*/0.5f);
Transition<TimerExpiredTrigger>("Window")("Post");
Transition<InputTrigger>("ComboAttackButton")("Next");
}
State("Post");
State("Next")
{
Enter("Next");
}
Exit<DisableCollision>("ComboAttack1");
Exit<ClearHistory>();
Postcondition("Next");
}
State<ExplicitTransition>("ComboAttack2")
{
Enter<EnableDamageCollision>("ComboAttack2",
/*damage=*/4.0f);
State("Pre")
{
Enter<PlayAnimation>("ComboAttack2", /*loop=*/false);
Enter<PlaySound>("ComboAttack2", /*loop=*/false);
Enter<StartTimer>("Pre", /*delay=*/1.0f);
Transition<TimerExpiredTrigger>("Pre")("Window");
}
State("Window")
{
Enter<StartTimer>("Window", /*delay=*/0.35f);
Transition<TimerExpiredTrigger>("Window")("Post");
Transition<InputTrigger>("ComboAttackButton")("Next");
}
State("Post");
State("Next")
{
Enter("Next");
}
Exit<DisableCollision>("ComboAttack2");
Exit<ClearHistory>();
Postcondition("Next");
}
State("ComboAttack3")
{
Enter<EnableDamageCollision>("ComboAttack3",
/*damage=*/8.0f);
Enter<PlayAnimation>("ComboAttack3", /*loop=*/false);
Enter<PlaySound>("ComboAttack3", /*loop=*/false);
Exit<DisableCollision>("ComboAttack3");
}
Exit<ClearHistory>();
Postcondition<AnimationFinishTrigger>("ComboAttack1");
Postcondition<AnimationFinishTrigger>("ComboAttack2");
Postcondition<AnimationFinishTrigger>("ComboAttack3");
}
State("Idle")
{
Enter<PlayAnimation>("Idle", /*loop=*/true);
}
}
}
Take some time studying this state machine. There are some subtle details:
- The initial (or start) state of an ExplicitTransition or a Sequential state is always the first state listed.
- The ClearHistory exit action in both the ExplicitTransition and Sequential states causes the those states to restart at their starting child state next time the parent state is entered. The default behavior in our engine was to keep the history and reenter the child state that was last active.
- Events always enter the state machine starting at the root. Therefore, depth acts as an implicit form of priority. This was used in our game to provide top-level states Alive and Dead. Therefore, dying always overrode whatever action was occurring.
- Transition actions inside an ExplicitTransition child state must name the state they are transitioning to. For example, see the TimerExpired Transition actions.
- The StartTimer and EnableDamageCollision actions in our engine were not actually performed by the state machine itself (even though it is possible). Those Events were actually sent from the Animation Engine on a particular animation frame. This gave the animators and content integrators fine control over exactly when the windows of opportunity and the damage windows should start and stop for every attack.
In Part 2, we will look at state concurrency and how we created reusable state patterns.
No user commented in " Hierarchical State Machines (Part 1) "
Follow-up comment rss or Leave a TrackbackLeave A Reply