A pattern for finite (game) state machine in Rust

问题:

I'm trying to write a turn-based game in Rust and I'm running up against a wall in the language (unless I'm not understanding something quite right – I'm new to the language). Basically, I'd like to change states in my game where each state has different behavior. For example I have something like:

struct Game {
    state: [ Some GameState implementer ],
}

impl Game {
    fn handle(&mut self, event: Event) {
         let new_state = self.handle(event);
         self.state = new_state;
    }
}

struct ChooseAttackerPhase {
    // ...
}

struct ResolveAttacks  {
    // ...
}

impl ResolveAttacks {
    fn resolve(&self) {
        // does some stuff
    }
}

trait GameState {
    fn handle(&self, event: Event) -> [ A New GateState implementer ]
}

impl GameState for ChooseAttackerPhase {
    fn handle(&self, event: Event) -> [ A New GameState implementer ] {
        // ...
    }
}

impl GameState for ResolveAttacks {
    fn handle(&self, event: Event) -> [ A New GameState implementer ] {
        // ...
    }
}

This was my original plan. I want handle to be a pure function that returns a new GameState instance. But as I understand it, this is not currently possible in Rust. So I tried using enums with tuples, each with their respective handler, that ended up being a dead end since I would have to match for every state.

Anyways, the code is not from my original project. Its just an example. My question is: is there a pattern for doing this in Rust that I'm missing? I'd like to be able to separate the logic for things I need to do in each state that are unique to each state and avoid writing lengthy pattern matching statements.

Let me know if I need to clarify my question a bit more.

回答1:

A finite state machine (FSM) can be directly modeled using two enums, one representing all the states and another representing all the transitions:

#[derive(Debug)]
enum Event {
    Coin,
    Push,
}

#[derive(Debug)]
enum Turnstyle {
    Locked,
    Unlocked,
}

impl Turnstyle {
    fn next(self, event: Event) -> Turnstyle {
        use Event::*;
        use Turnstyle::*;

        match self {
            Locked => {
                match event {
                    Coin => Unlocked,
                    _ => self,
                }
            },
            Unlocked => {
                match event {
                    Push => Locked,
                    _ => self,
                }
            }
        }
    }
}

fn main() {
    let t = Turnstyle::Locked;
    let t = t.next(Event::Push);
    println!("{:?}", t);
    let t = t.next(Event::Coin);
    println!("{:?}", t);
    let t = t.next(Event::Coin);
    println!("{:?}", t);
    let t = t.next(Event::Push);
    println!("{:?}", t);
}

The biggest downside is that one method ends up becoming very cluttered with all the state / transition pairs. You can sometimes neaten up the match a bit by matching on the pairs:

match (self, event) {
    (Locked, Coin) => Unlocked,
    (Unlocked, Push) => Locked,
    (prev, _) => prev,
}

avoid writing lengthy pattern matching statements.

Each match arm can be a function that you call for every unique action you'd like to do. Above, Unlocked could be replaced with a function called unlocked that does whatever it needs to.

using enums [...] ended up being a dead end since I would have to match for every state.

Note that you can use the _ to match any pattern.

A downside to the enum is that it is not open for other people to add to it. Maybe you'd like to have an extensible system for your game where mods can add new concepts. In that case, you can use traits:

#[derive(Debug)]
enum Event {
    Damage,
    Healing,
    Poison,
    Esuna,
}

#[derive(Debug)]
struct Player {
    state: Box<PlayerState>,
}

impl Player {
    fn handle(&mut self, event: Event) {
         let new_state = self.state.handle(event);
         self.state = new_state;
    }
}

trait PlayerState: std::fmt::Debug {
    fn handle(&self, event: Event) -> Box<PlayerState>;
}

#[derive(Debug)]
struct Healthy;
#[derive(Debug)]
struct Poisoned;

impl PlayerState for Healthy {
    fn handle(&self, event: Event) -> Box<PlayerState> {
        match event {
            Event::Poison => Box::new(Poisoned),
            _ => Box::new(Healthy),
        }
    }
}

impl PlayerState for Poisoned {
    fn handle(&self, event: Event) -> Box<PlayerState> {
        match event {
            Event::Esuna => Box::new(Healthy),
            _ => Box::new(Poisoned),
        }
    }
}

fn main() {
    let mut player = Player { state: Box::new(Healthy) };
    println!("{:?}", player);
    player.handle(Event::Damage);
    println!("{:?}", player);
    player.handle(Event::Healing);
    println!("{:?}", player);
    player.handle(Event::Poison);
    println!("{:?}", player);
    player.handle(Event::Esuna);
    println!("{:?}", player);
}

Now, you can implement whatever states you'd like.

I want handle to be a pure function that returns a new GameState instance.

You cannot return a GameState instance because the compiler needs to know how much space each value requires. If you could return a struct that took up 4 bytes in one call or 8 bytes from another, the compiler wouldn't have any idea how much space the call you actually make needs.

The trade-off you have to make is to always return a newly allocated trait object. This allocation is required to give a homogenous size to every possible variant of PlayerState that might arise.

In the future, there might be support for saying that a function returns a trait (fn things() -> impl Iterator for example). This is basically hiding the fact that there is a value with a known size that the programmer doesn't / cannot write. If I understand correctly, it would not help in this case because the ambiguity of size would not be determinable at compile time.

In the extremely rare case that your states don't have any actual state, you could create a shared, immutable, global instance of each state:

trait PlayerState: std::fmt::Debug {
    fn handle(&self, event: Event) -> &'static PlayerState;
}

static HEALTHY: Healthy = Healthy;
static POISONED: Poisoned = Poisoned;

impl PlayerState for Healthy {
    fn handle(&self, event: Event) -> &'static PlayerState {
        match event {
            Event::Poison => &POISONED,
            _ => &HEALTHY,
        }
    }
}

impl PlayerState for Poisoned {
    fn handle(&self, event: Event) -> &'static PlayerState {
        match event {
            Event::Esuna => &HEALTHY,
            _ => &POISONED,
        }
    }
}

This will avoid the overhead (whatever it may be) of the allocation. I wouldn't try this until you know there's no state and there's lots of time spent in the allocation.

回答2:

I'm experimenting with encoding the FSM into the type model. This requires each state and each event to have it's type but I guess it's just bytes underneath and the explicit types allow me to break the transitions apart. Here's a playground with a tourniquet example.

We start with the simplest assumptions. Machine is represented by it's states and transitions. An event transits the machine in one step to a new state, consuming old state. This allows for the machine to be encoded in immutable state and event structs. States implement this generic Machine trait to add transitions:

pub trait Machine<TEvent> {
    type State;
    fn step(self, event: TEvent) -> Self::State;
}

That's all the framework for this pattern really. The rest is application and implementation. You cannot make a transition that is not defined and there's no unpredictable state. It looks very readable. For instance:

enum State {
    Go(Open),
    Wait(Locked),
}

struct Locked {
    price: u8,
    credit: u8,
}

struct Open {
    price: u8,
    credit: u8,
}

struct Coin {
    value: u8,
}

impl Machine<Coin> for Locked {
    type State = State;
    fn step(self, coin: Coin) -> Self::State {
        let credit = self.credit + coin.value;
        if credit >= self.price {
            println!("Thanks, you've got enough: {}", credit);
            State::Go(Open {
                credit: credit,
                price: self.price,
            })
        } else {
            println!("Thanks, {} is still missing", self.price - credit);
            State::Wait(Locked {
                credit: credit,
                price: self.price,
            })
        }
    }
}

And the client code is pretty semantic, too:

let locked = Locked {
    price: 25,
    credit: 0,
};
match locked.step(Coin { value: 5 }) {
    State::Go(open) => {println!("Weeeeeeeeeeeeee!");},
    State::Wait(locked) => {panic!("Oooops");},
}

I was much inspired by Andrew Hobben's Pretty State Machine Pattern.