Game Design: Decoding State Machines

If you’re a game programmer chances are you’ve worked with state machines. Most likely, you’ve worked with finite state machines informally. For instance, your code might be littered with conditionals such as:

if (lives > 3 && score < MAX_SCORE) {
    // keep running
}
if (lives == 0) {
    // display game over screen
}

The above code works and certainly gets it’s point across succinctly, but it can get messy quickly. Once the game states become more nuanced, start to involve multiple conditions, and multiply then it’s time to refactor your state machine.

The main advantage accrued is that it’s easier to understand each state and the transitions between states. This makes your code easier to understand for others and yourself down the road. It also makes it easier to find and fix bugs which commonly creep into state machines. The main disadvantage to this approach is that it requires more code to achieve the same thing. That’s why I only recommend it for complex state machines.

Light Approach

Probably the easiest way to formalize your states is to introduce an enum or something similar. I actually recommend that you adopt this approach even for trivial state machines as it makes things considerably clearer with little extra work. Start off by creating an enum for you class, let’s take our example above:

private enum InGameState { RUNNING, GAME_OVER };
private InGameState state;

if (state == InGameState.RUNNING) {
    // keep running

    if (lives == 0 || score > MAX_SCORE) {
        state = InGameState.GAME_OVER;
    }
}
if (state == InGameState.GAME_OVER) {
    // display game over screen

    if (newGameButton.pressed()) {
        lives = 3;
        score = 0;
        state = InGameState.RUNNING;
    }
}

As you can see the above example requires you to rewrite things slightly. Obviously as we are refactoring the result is functionally equivalent. However, the code is much clearer. Now, each conditional clearly encases a single state’s behavior. In addition, transitions are explicit. The result is that new developers will have a much easier time reading and understanding the code. It will also be much easier to find bugs with transitioning from one state to another now that you can clearly follow the state change logic.

Heavy Duty Approach

The last method is great if you’ve got a relatively simple state machine. For example, if you’re working with your game loop which only spans two methods, say render and update, and a few states. However, if you find your business logic spans multiple methods or you’ve got many states with complex transitions then you may want to adopt an even more formal approach. For instance, in my latest game I have several AI driven critters which move between four or five possible states. Initially I approached the problem using the last approach, but quickly it became very difficult to determine all the different ways to enter or exit a given state. As soon as you find yourself struggling to fully understand all of the possible transitions in your state machine you should consider adopting this approach.

To start off you need to identify all the methods where state logic occurs. In my case that was across three methods, render, update, and onCollision. Once you’ve identified your methods you should define an interface:

public interface State {
    /** Initialize the state whenever it is entered. */
    public void enter();
    /** Used by the StateManager. */
    public boolean equals(Object o);
    public void render(Graphics g);
    public void update(int delta);
    public void onCollision(Entity obstacle);
}

As you can see I’ve added the three methods relevant for my AI critters. You should replace mine with methods that are relevant to your task. The enter method will be called whenever the state is transitioned to. This lets you initialize things as necessary. The equals method is a simple way for the StateManager to assist in transitioning between states. You’ll see how this works when I put things together. First, let’s take a look at the state manager.

public class StateManager {
    private LinkedList<State> states;
    private State currentState;
    public StateManager() {
        states = new LinkedList<State>();
    }
    public void add(State s) {
        states.add(s);
        if (currentState == null) {
            currentState = s;
            currentState.enter();
        }
    }
    /** Transition to the designated state. */
    public void enter(Object o) {
        for (State s : states) {
            if (s.equals(o)) {
                currentState = s;
                currentState.enter();
            }
        }
    }
    /** Useful if you need to know what state you are currently in. */
    public Object currentState() {
        return currentState;
    }
    public void update(StateBasedGame game, int delta) {
        currentState.update(game, delta);
    }
    public void onCollision(Entity obstacle) {
        currentState.onCollision(obstacle);
    }
    public void render(Graphics g) {
        currentState.render(g);
    }
}

As you can see, the StateManager is a simple proxy for the State interface. While simple, it provides all the necessary logic to help formalize your state machine. The key to this approach is the Java inner class. For each state we will create an inner class implementing the State interface. After that we can simply add each state to a state manager and call the manager’s methods when appropriate. This approach makes a state completly explicit by separating its logic into an entirely separate class. Let’s put it all together.

public class Critter {
    private enum CritterState { SLEEPING, MOVING };
    private StateManager manager;

    private class SleepingState implements State {
        private int timer;
        public boolean equals(Object o) {
            return o == CritterState.SLEEPING;
        }
        public void enter() {
            timer = 0;
        }
        public void render(Graphics g) {
            // draw critter sleeping
        }
        public void update(int delta) {
            timer += delta;
            if (delta > SLEEP_TIME) {
                manager.enter(CritterState.MOVING);
            }
        }
        public void onCollision(Entity obstacle) {
            manager.enter(CritterState.MOVING);
        }
    }

    private class MovingState implements State {
        private int timer;
        public boolean equals(Object o) {
            return o == CritterState.MOVING;
        }
        public void enter() {
            timer = 0;
        }
        public void render(Graphics g) {
            // draw critter moving 
        }
        public void update(int delta) {
            timer += delta;
            // move a little bit
            if (delta > AWAKE_TIME) {
                manager.enter(CritterState.SLEEPING);
            }
        }
        public void onCollision(Entity obstacle) {
            // bounce off obstacle
        }
    }

    public void render(Graphics g) {
        manager.render(g);
    }
    public void update(int delta) {
        manager.update(delta);
    }
    public void onCollision(Entity obstacle) {
        manager.onCollision(obstacle);
    }
}

There you have it! That was a lot of code so let me try to touch on some of the interesting parts. First off, you’ll notice that I kept the enum. You don’t strictly need this but I think it helps keep things simple and clear. It’s especially useful when implementing the various states’ equals method. Of course, you could just drop the enum and have the states match unique integers. Next notice that each state has its own timer. Now that each state is implemented in its own private class we can separate out all of the various logic and data that they used. I’m sure you can think of at least one instance where you had a sleepTimer, awakeTimer, and timerX, well now you won’t run into that problem! As you can see, by adopting this pattern you alleviate the burden of bookkeeping that you must do. Each state is a self contained unit. This means that it’s much clearer what each state does and how it transitions to another state. It is also much harder to run into a case where one state affects another’s data. Now, this case only comes up when the states are using some of the parent class’s data. (Which sooner or later they will, so you still have to be careful.)

Hopefully, you can think of some instances where this pattern would be useful in your project. If you do let me know how it applied and what you found! Also if you have any suggestions on how to improve the approach leave a comment and I’ll update this post.

Related Posts

• Physical Queries for the Math Challenged: Real-time Shadows
• Making a Platformer: Physics
• Game AI Patterns
• Physical Queries for the Math Challenged: Collision Detection and Response
• Game Design and Iterative Development