Article
files/design-states

Why State Machines Struggle With Concurrency

Alex J. Champandard on July 12, 2007

Finite state machines (FSM) work well for linear control, as only one state is active at the same time. That’s what they’re intended for, so pretty quickly, your design starts to take advantage of this. Since only one state runs at any moment, the FSM becomes a resource allocation strategy — deciding which behavior to allow next.

State Machine In Trouble

A state machine controlling a single resource.

This works reasonably well until your designers start requesting concurrent behaviors: it’s “next-gen.” Since the original FSM worked so well for resource allocation, you then create another FSM for a different resource and split up the first one into two. (For example, two state machines controlling different body parts in the animation system.)

Trying to Scale Up…

After a while, late in production, you find yourself with a spaghetti mess of interdependencies. It’s not just the familiar internal transitions, but external synchronization with other resource allocators make things so much more complicated.

On a daily basis, you find yourself sweating to:

  • Keep multiple state machines synchronized and working well together.

  • Work out how goals are achieved emergently since they are never written explicitly.

  • Add new behaviors by spreading them into multiple different resource controllers.

So with a control system per resource, like most typical FSM are used, you end up with no modularity at all. Every change in behavior impacts everything else. That’s bad because you can’t scale up the number of behaviors easily… It’s not even a complexity of O(N^2) anymore because you can’t even isolate the N behaviors in the first place! Instead, it’s closer to O(spaghetti) — which you all know is the worst known time complexity in computer science.

Solutions?

If you’ve come here desperate for tricks to fix your current FSM, there are no silver bullets that will help a FSM resource controller scale well. But here are some little tips to ease your pains:

  1. Don’t use specific conditions (e.g. state checks) when referring to external state machines; try to keep things generic using tags so you have a level of decoupling at least.

  2. Try to keep most of the logic centralized in one master state machine, which moves and deletes the token in other state machines.

  3. Alternatively, if you’re keen on keeping your state engine, rebuild your FSM with a different approach…

The best you can do is try to use FSM to model behaviors instead of resources. Then use simpler resource allocation strategies, like an ordered queue; it’s more modular.

How do you deal with concurrency using state machines?

Discussion 0 Comments

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!