Rustic State Machines for Fun and Profit
Video games got me into programming, and while I don't actively try to make games anymore, every now and then I take an interest in what the experts are doing, and occasionally write modules and bindings.
One of the key design patterns I've learned since then is the State pattern. Like all young, idealistic game programmers, my first programs were filled with complicated if-else branches that were nearly impossible to update or maintain, yet somehow they worked. The State pattern is something I sorely wish I'd known back then, as it solves the same problem that those if-else branches were intended to solve, but does it in a much cleaner and more modular way. The book-in-progress I linked to above does a great job of describing what the pattern is and sketches out a rudimentary C++ implementation. But C++ is a complicated, often twisted old beast of a programming language, so why not try to implement a state machine in the next-generation game programming language: Rust?
Truthfully, I doubt that Rust will ever knock C++ off of its dominant perch in the game programming industry, at least not for a long while. But it does stand the best chance, as it combines a number of good design ideas with a trait that most new programming languages tend to brush off: speed. While I'm a huge fan of other new languages like Go, mandatory garbage collection is a potential dealbreaker for games that want to milk as much performance out of the system as possible.
The State pattern is based on the concept of dynamic dispatch: the ability of a system to determine at runtime which code to run, rather than at compile-time. C++ uses virtual methods, Go uses interfaces, Haskell uses typeclasses, and Rust uses traits.
If you're familiar with how any of the other languages implements dynamic dispatch, then Rust traits should feel very familiar. A trait is defined by a set of method signatures, each made up of a name, parameter list, and return value. Other types can implement a trait by implementing the methods defined by it. Once implemented, that type can be used anywhere that trait is expected.
So by implementing the game hero's state as a trait, we can pass game input along to whatever record the hero's state is currently pointing to, then use its return value to determine if that state should be updated.
In code, here's what we'd like to be able to do:
This simply defines a State trait (empty for now) and a Hero struct with an inner field pointing to some value implementing State. Then when we want to process some input, we give it to the Hero and let it decide what to do based on its current state. Since we want each possible state to be able to handle its own input,
State should consist of a similar, but more specialized, method for input handling. But since the Hero points to the State and not the other way around, how do we tell the Hero whether or not a new state is needed? Consider that there are three possible cases:
- Invalid input.
- Valid input, and the state should change.
- Valid input, but the state should stay the same.
For this solution I've decided to represent these three cases using a combination of Rust's built-in
Option types. A
Result can represent one of two values, an error or a success, and an
Optionsimply represents a value that may or may not be present. When the input fails for any reason, we want to return that as an error. But if it succeeds, we want to be able to optionally return a new state to be used. Here's how that looks in Rust code:
Note that this is a very simplified example, and in reality, it would also be necessary for
handle_input() to take a pointer to
Hero or some subset of it. However, this post is written towards a functional programming style, and as such we want to prevent states from modifying the hero's
st field directly, hence this approach.
Res type is equivalent to what I just described, since it has only three possible values:
Err(...)for an error.
Ok(Some(...))for when we want to change state.
Ok(None)for when we want to keep the current state.
Now we can finish defining the Hero's
handle_input() method, which will serve as the entry-point for any
State-defined ones by passing along the input and updating itself based on the result:
For simplicity's sake, any errors received will simply be printed to standard output.
Writing Some States
Let's use this to implement two states for the Hero and define some commands for switching between them!
Assume that our hero starts out sitting, so we have a
Hero instance whose internal
st field points to an instance of
Sitting, which is an empty struct as it requires no additional information. But what if our hero wants to eat a burger? We simply tell him to
~[~"eat", ~"burger"], which gets passed along to the sitting implementation of
handle_input(). This ends up returning a value of
Ok(Some(~Eating as ~State)), which means that we should upate our hero's state to the provided
Eating contains one field, which is the value of the food we instructed him to eat; in this case,
~"burger". This demonstrates how each implementation of
State can itself keep track of its own internal state. Telling him to
~[~"eat", ~"pizza"] would cause our hero to stop eating the burger and pick up a slice of pizza. On the other hand, telling him to
~[~"chew"] while eating or to
~[~"stare"] while sitting will return a value of
Ok(None), since he will still be eating or sitting, respectively, after the action has finished.
The full working example can be found here. As an exercise, try downloading the source and implementing a few new behaviors for our intrepid
Hero. How would you get him to walk, or sleep? How would he react to a command to
~[~"walk"] while in the middle of a sandwich, or if he was told to
~[~"sleep"] while walking?