Resolving the game state machine cyclic dependency

#refactoring #cpp #rust #patterns

If you've been making (or trying to make) games for any amount of time, it's likely you've seen and used the state machine. Here's a minimal implementation in C++:

class State {
    StateMachine* stateMachine;
public:
    virtual void onEnter() {}
    virtual void onExit() {}
}

class StateMachine {
    std::stack<std::unique_ptr<State>> states;
public:
    void push_state(std::unique_ptr<State> state) {
        states.top()->onExit();
        states.push(std::move(state));
        states.top()->onEnter();
    }
    void pop_state() {
        states.top()->onExit();
        states.pop();
        states.top()->onEnter();
    }
    void change_state(std::unique_ptr<State> state) {
        states.top()->onExit();
        states.pop();
        states.push(std::move(state));
        states.top()->onEnter();
    }
    State& peek() {
        return *states.top();
    }
}

The pointer inside the State class allows itself to access methods from the StateMachine class. This is particularly useful in game development.

Say if you were designing a platformer game. You could have a MainMenu state, a InLevel state, and a Settings state. In order for the MainMenu state to be able to transition to the InLevel state it needs to access the change_state method.

The problem is we have a cyclic dependency here! StateMachine needs to know about State for it to call its onExit and onEnter methods (and more). State needs to know about StateMachine so it can change the current states.

The works well enough in C++ but it poses a huge problem in Rust (which is what I'm creating my game in). See the following code:

pub trait State {
    fn event(&mut self);
    fn update(&mut self, state_manager: &mut StateManager);
    fn draw(&self);
}

pub struct MainMenuState {}

impl State for MainMenuState {
    fn event(&mut self) {}
    fn update(&mut self, state_manager: &mut StateManager) {}
    fn draw(&self) {}
}

pub struct StateManager {
    states: Vec<Box<State>>
}

impl StateManager {
    pub fn new(initial_state: Box<State>) -> StateManager {
        StateManager {
            states: vec![initial_state],
        }
    }

    pub fn peek(&mut self) -> &mut Box<State> {
        return self.states.last_mut().expect("StateManager is empty");
    }
}

fn main() {
    let mut state_machine = StateManager::new(Box::new(MainMenuState{}));
    state_machine.peek().update(&mut state_machine);
}

That's my attempt at replicating the state machine in Rust. If we compile this code we get the following error:

error[E0499]: cannot borrow `state_machine` as mutable more than once at a time
  --> src/main.rs:33:38
   |
33 |     state_machine.peek().update(&mut state_machine);
   |     -------------                    ^^^^^^^^^^^^^- first borrow ends here
   |     |                                |
   |     |                                second mutable borrow occurs here
   |     first mutable borrow occurs here

I'd just like to point out how awesome Rust's error messages are. None of that cryptic stuff that I find with C++ compilers.

If you aren't too familiar with Rust, here's the gist (no, not a Github gist) of what's happening. Rust only allows you to have one piece of code modifying the same variable at the same time (a mutable borrow). This's so it can find and prevent data races at compile time. We modify the state_machine variable when we use the peek method from StateManager and when we use the update method (which modifies the StateManager it's given).

At this point I decided to change the structure of the code instead of "fighting the borrow checker".

Somehow I needed a way to notify the StatesManager to change its states without doing so directly. That means the code responsible for notifying the StatesManager couldn't be the State struct.

I do this by making the State struct return a Rust enum that signifies whether it wants to change the current states. The StateManager would then change the states depending on the value of the enum.

Rust makes this especially easy because you can "attach" any value to any enumeration. See the following:

pub enum StatesRequest {
    PushState(Box<State>),
    ChangeState(Box<State>),
    PopState,
    None,
}

pub trait State {
    fn event(&mut self);
    fn update(&mut self) -> StatesRequest;
    fn draw(&self);
}

fn main() {
        let mut state_manager = StateManager::new(Box::new(MainMenu{}));
        let request_status = state_manager.peek().update();
}

Now State doesn't need to know anything about the StateManager. The only dependency it has is the StatesRequest enum. Whenever it wants to change the state it just needs to create a new instance of StatesRequest with the State added in the enum.

// Inside the MainMenuState impl
fn update(&mut self) -> StatesRequest {
        if userPressedStartGame {
            return StatesRequest::ChangeState(Box::new(InLevel{}));
        }
}

Here's the rest of the modified code:

impl StateManager {
    pub fn new(initial_state: Box<State>) -> StateManager {
        StateManager {
            states: vec![initial_state],
        }
    }

    pub fn update_states(&mut self, states_status: StatesRequest) {
        match states_status {
            StatesRequest::PushState(state) => {
                self.states.push(state)
            },
            StatesRequest::ChangeState(state) => {
                self.states.pop().expect("StateManager is empty");
                self.states.push(state);
            },
            StatesRequest::PopState => {
                self.states.pop().expect("StateManager is empty");
            },
            StatesRequest::None => ()
        }
    }

    pub fn peek(&mut self) -> &mut Box<State> {
        self.states.last_mut().expect("StateManager is empty")
    }
}

fn main() {
    let mut state_manager = StateManager::new(Box::new(MainMenu{}));

    // The following code would be in some sort of loop
    let request_status = state_manager.peek().update();
    state_manager.update_states(request_status);
}

Hurrah! No more compile errors and we remove the cyclic dependency.

This was easy enough to do in Rust (owing to it's fantastic enums) but can we do it in C++?

Absolutely. It does look slightly different though:

struct StatesRequest {
    std::unique_ptr<State> new_state;
    enum Type {
        PUSH,
        POP,
        CHANGE,
        NONE
    } type;
}

(I've grown a slight liking to snake case instead of camel due to Rust)

Feel free to ask any questions you may have. I'll try my best to answer them but I'm not a Rust or C++ expert (or a program design expert) by any means. Otherwise, thanks for reading!