A Basic State Machine for Games

Upon coding, I've stumbled across a different method to represent state machines in games compared to what I usually code.

Before I go into the details; what is a state machine you ask?  Imagine an application, a game if you will.  A hypothetical game starts in a main menu, then it transitions to a play-game state, then it can either transition to a score-screen or game-over state.  The score-screen will go to the play-game state (on another level we suppose), and the game-over state back to the main menu.

We can also apply states to sprites.  They can be walking, running, standing still.  They can also be healthy, or weak.  Each of these has an appropriate visual representation.  AI in games (if we can call it AI) is usually represented as a series of states.

More generally, we tend to represent states as a directed (potentially cyclic) graph.  However, I believe this view to be overly simplistic and problematic (disclaimer, I am not the originator of this viewpoint.  I simply agree with it.).  Also; we have the compute resources on most platforms to accept such a view.

I've found it convenient to redefine a "state" as a value between 0 and 1.  Of course, this complicates the programming, but it does have many benefits.  0 is disabled, 1 is enabled.  below 0 is less than enabled, above 1 is saturated -- extremely enabled.  The latter two, albeit they may seem redundant, appeal to creative types.

I'll confess: there are more complex state systems described in the literature that will allow for more flexibility than what I describe here.  Here, I describe what I found to be suitable for a game -- your needs (even if for a game) may differ when compared to mine.

Now, a tree structure.  The root state is always enabled at 1.  The root state handles transitions among the child states (through some pre-determined means of communication).  Here's where things get interesting:  all the sub-states at the root can be enabled.  Things can be half-enabled.

First implication: the layering among sub-states becomes important.  Things can be drawn on top of each other.

Second implication: the score-screen can become its own state, and hover above the game itself.  It does not need to be a substate of the game.  (this depends upon the game and how things are set up).  As is the pause screen.  Yes, these are simplistic examples - they could be done trivially using regular states as described at first.

Third implication: transition among states can be programmed as enabling/disabling a state.  Moving the enabled value between 0 and 1.  This provides an elegant way to describe the transitioning in of the pause menu.  It also provides a means independent of the animation to represent the time needed to get into the menu.  (all transition animation speeds should be easily tuned)

States in a tree (where the data structures are always in memory with manual dumping to disk when memory is low) is practical.  One; we maximize the use of memory (of course this is not perfect in all situations - and in some cases it may be counter-productive).  Two; dumping all elements of the tree back to disk is... trivial!  If done correctly, of course!

Why dump to disk?  Games should attempt to restore what they were doing last.  Skip the main menu - go right to the game - into the exact menu that the player was viewing.  Transitions should resume; as though the game was never turned off.

Why even go into that amount of detail?  I'm not detailing something for super-computers.  I'm thinking about portable devices.  Devices such as iPods where running a game in the background is silly.  The game should free resources and let the foreground application run with a lot of CPU power.

Shouldn't the OS manage all these details?  Isn't it silly for an application to worry about such trivialities?   Yes - the OS could manage these details with the help of the application (some apps do really need to work in the background while others could be swapped to disk).  If an application is coded to worry about such trivialities, then it can do a more optimal job than the OS.  For example, if data was loaded from disk with a bit of post-processing (instead of mmap'ed), then the OS has no clue that these pages can be released without dumping to disk.

Any other advantage to such an odd state machine?  I'll argue that it better represents the transition between walking, running, and standing still - but that might be more of a headache.

Something more genuine as a use might be the HUD elements.

And then - to be completely honest - save to disk can be done using a standard state system.  Just reflection would be required to make it much easier.  The transitions can be separate states.

In the end - whatever best suits the application (or game) at hand should be used.  Whatever gets the correct results faster in most cases.