# Animation State Machine Transitions Implementation

## Recommended Posts

Say we have a simple animation state machine. The state machine is described by some simple nodes with transitions between them. Transitions have conditions that need to be satsified in order to take a transition. Say we have a simple IDLE and WALK state with a transition between them. The transition has a simple condition SPEED > 0. Now the game sets SPEED = 1. What happens here is that the state machine instantaneously changes to WALK. For the underlying animation system the change is not so instantaneous. First we need to blend from idle to walk and then continue the walk animation.

How is this effectively implemented? In practice the WALK state is not necessarily a simple animation, but can be a complex blend tree or an ASM itself.

##### Share on other sites

Some time ago (woops, more than a year, how time flies), I wrote

http://www.gamedev.net/page/resources/_/technical/game-programming/from-user-input-to-animations-using-state-machines-r4155

this handles user input, and how you switch animations from that input at the right moment.

The basic idea is that you see the animation as another state machine, and synchronize on taken edges, when a) the input machine wants to switch, and b) the animation state machine allows to switch.

Hope this helps,

##### Share on other sites

Yup. I saw this post. I am interested in the details of the TakeEdge() function. E.g. in the article you say:

There is also a function TakeEdge(<state-machine>, <current-state>, <edge-name>) that takes the edge with the given name in the state machine, performs the assignments, and returns the new current state.

How can you return the new state? At least from the perspective of the animation this takes time. I see that I could add two assignments though:

1) Blend to target state

2) Run target state

Still I am interested in implementation details on this problem. Conceptually I see something like this:

void State::Update()
{
// Find edges that can transition and choose one (e.g. based on priority)
if ( !mTransition )
{
mTransition = CheckEdges();
}

// Are we transitioning to a new state
if ( mTransition )
{
// Run the transition to the new state. This is not instantaneous for the animation
if ( mTransition->Update() == FINISHED )
{
mASM->SetState( mTransition->GetTarget() );
}

return;
}

// Nothing is happening so simply update current animation...
}

Edited by Dirk Gregorius

##### Share on other sites

One way would be to create transition states to represent the edges, but if I'm understanding you correctly then you could just have a cur_state and goal_state, then to transition you do something like:

cur_state = goal_state

goal_state = new_goal

state_trans_start_time = now

state_trans_end_time = state_trans_start_time + whatever

update  'remaining' as you go and then get the ratio:

trans_ratio = (state_trans_end_time - now) / (state_trans_end_time - state_trans_start_time)

and interpolate based on that value to blend the animations. (Make sure to check the finished condition.)

Unless I'm misunderstanding the question?

##### Share on other sites

Which module would do this? In the state machine itself or one layer above? And then also, when does the SM current state change. Immediately or after the transition is finished?

##### Share on other sites

This is (the shallow end of) fuzzy state. There doesn't necessarily need to be a definite single state that you are "in", just a membership value for states that are relevant. The fine details depend on what you're animating, what transitions are allowed and when, and what information you need from the SM.

In other words, you have to decide that yourself, based on your needs. You can limit the transition rate with game mechanics or you can blend more than two states, or have unique rules for each transition, etc.

Edited by Khatharr

##### Share on other sites

I would say that your transition is also a mini state machine, with an "in a state" condition, a transition for starting a transition, a state indicating it is in the middle of a transition, and a transition to be done with the condition.

Games use state machines for lots of thing, and this type of thing is not uncommon for items that need to be in transition over time.

##### Share on other sites

Yup. I saw this post. I am interested in the details of the TakeEdge() function.

There is also a function TakeEdge(, , ) that takes the edge with the given name in the state machine, performs the assignments, and returns the new current state.

How can you return the new state? At least from the perspective of the animation this takes time.

Edges are instantaneous and atomic. You spend time in a state, not in an edge.

If you find you want to spend time in an edge, you can always add a new intermediate "do thing" state, and have a "start thing" edge to the intermediate state, and "end thing" edge from the intermediate state to the original destination of the edge.

I think you don't actually need such an intermediate state though.

I am not exactly sure what semantics you have attached to SPEED values. "SPEED=1" suggests to me you start changing x and y coordinates. However, in my view, you don't control that data, the animation knows how and when to change coordinates.

So instead, your "SPEED" should be seen as "desired_speed", ie expressing the wish to move. Setting "desired_speed" to 1 doesn't mean you start moving immediately. It's only a message to the animation state machine that it should work towards performing movement.

The latter could look something like

[attachment=34351:walk_states.png]

Each state represents "displaying frames of an animation". The edges are listed below.

Init: (initialization of the variables)
int frame = 0; // Current displayed frame
SetIdleAnimation();
SetAnimationFrame(frame);

RepIdle: (repeat idle animation)
condition:
(frame == LastIdleFrame && desired_speed == 0)

update:
frame = 0;
SetAnimationFrame(frame);

condition:
true

update:
frame = frame + 1
SetAnimationFrame(frame);
// Update (x,y) position if required

Ssw: (start start-walking)
condition:
(frame == LastIdleFrame && desired_speed > 0)

update:
frame = 0;
SetStartWalkAnimation();
SetAnimationFrame(frame);

Sw: (start walking)
condition:
(frame == LastStartWalkFrame && desired_speed > 0)

update:
frame = 0;
SetStartWalkAnimation();
SetAnimationFrame(frame);

Aw: (abort walk)
condition:
(frame == LastStartWalkFrame && desired_speed == 0)

update:
frame = 0;
SetStopWalkAnimation();
SetAnimationFrame(frame);

RepWalk: (repeat walking, ie do next step of the character)
condition:
(frame == LastWalkFrame && desired_speed > 0)

update:
frame = 0;
SetAnimationFrame(frame);

Stw: (start stop walking)
condition:
(frame == LastWalkFrame && desired_speed == 0)

update:
frame = 0;
SetStopWalkAnimation();
SetAnimationFrame(frame);

Si: (start idle)
condition:
(frame == LastStopWalkFrame && desired_speed == 0)

update:
frame = 0;
SetIdleAnimation();
SetAnimationFrame(frame);

Rw: (restart walking)
condition:
(frame == LastStopWalkFrame && desired_speed > 0)

update:
frame = 0;
SetStartWalkAnimation();
SetAnimationFrame(frame);


You stay in a state, displaying an animation, frame after frame (Tick advances to the next frame). At the end, of the animation, you jump to the next animation to display, depending on the value of the desired_speed.

Here I used the "desired_speed" variable to express what the animation system should work towards. If you want to have a separate state machine for expressing this, that's also possible. You have to synchronize with event-names then. In the above edges, take out all the "desired_speed" conditions, and add the event-name "TowardWalk" on all edges with the condition "desired_speed > 0". Add the event-name "TowardIdle" on all edges with the condition "desired_speed == 0".

Then add the following state machine (synchronizing on "TowardWalk" and "TowardIdle"):

[attachment=34352:toward.png]

The animation state machine switches to the next animation at the end of each animation. It does so by using an edge labeled "TowardIdle" or "TowardWalk". The above state machine limits the choice towards a single direction, since it can do only one of the events, and it synchronizes with the animation state machine.

This is what KhatHarr proposed too, I think, but more formalized. This kind of separation starts to pay off when you have more goal states you may want to work towrds, and the conditions of switching goal states are more complicated.

Edit: Sorry for the small images, I saw that too late.

Edited by Alberth

##### Share on other sites

Thanks everybody! Alberth, what you write makes a lot of sense! I think the only problem I have is to use two state machines. How about we have the state machine only know about state. E.g. idle and walk. And changes are instantaneous. Now I move the joystick forward and speed goes to one. The state machine signals switching state from idle to walk. I now describe the entire animation in a blend tree. I capture the event and add a blend node which blends from idle to walk and when it is done it continues with walk (or whatever has a 1.0 weighting).

It is probably a matter of choice and both work fine.

Edited by Dirk Gregorius

##### Share on other sites

In my approaches transitions are generally modeled as states, and changing states happens instantaneously.

The example in the OP may then be modeled with

a) a stable idle state;

b) a transitional state that replays a canned animation to bring the skeleton into a defined motion phase with a defined speed;

c) a transitional state that interpolates over time from the current speed to the goal speed, setting appropriate animation clips for blending;

d) a stable state that continues the walk cycle with the reached speed.

Alternatively to c) and d) there could be:

e) a stable state that regulates the speed in dependence on the difference between current speed and goal speed, hence running a continuous blending.

However, such a state machine is not only controlling animation since it also controls locomotion. Its granularity w.r.t. states is derived from animation needs, and hence does not reflect the difference between e.g. "still" and "moving" very well. When understood as component of a locomotion system, then states like b) can be seen as synchronization points where control is granted for a short time to the animation system. When control is returned, the state machine immediately enters state e).

##### Share on other sites

I think the only problem I have is to use two state machines.

"have to" is a bit strong :)

There is a computation known as "synchronous product of automata" that can merge several synchronous automata into one. The caveat is that the resulting automaton is hard to understand, not easily human-editable anymore, and may contain lots of states (if you merge a automaton with N states with one with M states, the product may contain up to N*M states, ie you may get a state explosion). You want tool-support to generate such a product. All this makes the product less useful for an article, which is why I didn't mention it.

For the example, where the Idle/Walk automaton has just 2 states, and the synchronizing events cause state changes in only one automaton, it's quite doable by hand, as shown below:

[attachment=34368:walk_product.png]

You make a copy of the entire animation state machine for each state in the idle/walk state machine. In the picture, the upper dotted box represents the combination "WantIdle&<animation-state>", the lower dotted box represents the combination "WantWalk&<animation-state>".

Next you copy the edges from the Idle/Walk state machine to every corresponding pairs of states between the round boxes, the thick cyan and magenta arrows are the "desired_speed == 0" and the "desired_speed > 0" edges.

Finally, the "WantIdle" state forbids the WantWalk edges, so remove them from the upper box. Similarly, remove the WantIdle edges from the lower box. I also removed the Init edge from the bottom box, assuming you want to start in idle state.

All the 8 states are reachable, so you can't remove any of them. In this way you can have a single state machine with combined behavior, if you don't mind having many states.

I now describe the entire animation in a blend tree.

I didn't know these, so I had a quick look. After reading the general description, it looks to me more like a way to re-use parts of an animation, but I may be under-estimating its power.

It is probably a matter of choice and both work fine.

I think so too. How you represent state in run-time is not very relevant, a variable with a value is as much state as a pointer to a "current state" object.

Edited by Alberth

##### Share on other sites

What I do in EMotion FX is have each state output a pose.

A state can be a simple motion, or state machine or blend tree (or anything else that generates a pose).

Between the states are transitions with the conditions on them, so exactly as you describe.

The state machine holds a current state and target state and current transition.

When a transition is active, the transition pointer points to the transition being active.

The transition object outputs a pose as well and can mark itself finished.

I then output the pose of the transition. But the state machine is still in the current source state as current state.

Once the transition is fully completed the state machine's current state becomes the transition's target state.

There is a separate Update and Output call in the graph. The Update call would update the node and transition timers. So performing a tick and performs the actual current state changes once transitions finish etc.

The Output will calculate the output pose of the root state machine, so processing everything hierarchically.

You only update and output the current and possible target state inside the state machines.

Hope that helps.

##### Share on other sites
Posted (edited)

Hi John! Awesome, thanks for sharing this information. This is a bit more in the line I am thinking about this system. Please let me ask you two more quick questions:

1) Can you elaborate a bit more on the Update() function. Does a state update itself? E.g. do you simply iterate over all transitions of the state update checking the associated conditions? Then out of all possible transitions you choose the one with the highest priority? Or does the transition happen from the outside and is triggered by some controlling game code.

2) Does the active transition calculate and cache the current pose for the Output() call when updating? Or does all evaluation happen exclusively in Output()? Also why does the current state holds the target state and the transition. Is this only rhetorical? I would imagine this to be redundant since the transition would store the target as well. Or maybe is there a case where this is necessary and the two targets can be different?

Thanks,

-Dirk

Edited by Dirk Gregorius

##### Share on other sites
Posted (edited)

Hi Dirk :)

1) Can you elaborate a bit more on the Update() function. Does a state update itself? E.g. do you simply iterate over all transitions of the state update checking the associated conditions? Then out of all possible transitions you choose the one with the highest priority? Or does the transition happen from the outside and is triggered by some controlling game code.

The update of states (which are essentially emfx graph nodes) update things internally depending on the node. For example a motion node could update its current play timer. It is a bit more complex than this though, with hierarchical synchronization etc. But that is essentially what it does. It outputs non-pose values as well inside the updates. For example math nodes require their values to be calculated already during update stage, as we optimize the graph output by not processing nodes that aren't needed. For example if the weight of some IK node is 0 (calculated by some math nodes), then we do not calculate the full IK on the pose.

The Output would really do the heavy per bone calculations, outputting a real pose that gets blend etc.

Regarding conditions being checked, these are only the ones on the transitions originating from the current state. And also wild card transitions. If multiple transitions can be taken, we pick the one with the highest priority value. We also allow transitions to be interrupted and some other features.

We can also trigger them manually. But that's mostly just used in the editor. Or to force the game in some given state. But normally all is automated.

2) Does the active transition calculate and cache the current pose for the Output() call when updating? Or does all evaluation happen exclusively in Output()? Also why does the current state holds the target state and the transition. Is this only rhetorical? I would imagine this to be redundant since the transition would store the target as well. Or maybe is there a case where this is necessary and the two targets can be different?

The evaluation happens inside the Output. Update only updates things like timers etc, and what transition is active. There is no caching of that pose. I pool all poses though, so transitions and nodes do not store poses as that eats more and more memory the more nodes you have. Also I can share the animation graphs among different instances, each having their own parameter values and internal states of the nodes. For example each instance can be in another current state or transition in a given state machine.

The active transition pointer can be null. In that case you still want to know the current state. It is probably why it is stored twice in EMFX. It has been like 10 years ago since it got written, so I cannot remember the exact details right now. But surely it is not perfect, so perhaps not all would be needed :)

Cheers,

- John

Edited by Buckshag

##### Share on other sites

Supi, that is exactly what I was looking for. Thanks a lot, sir! :)