So, I've read a lot about using FSMs to do game state management, things like what an FSM is, and using a stack or set of states for building one. I've gone through all that. But I'm stuck at writing an actual, well-designed implementation of an FSM for that purpose. Specifically, how does one cleanly resolve the problem of transitioning between states, (how) should a state be able to use data from other states, and so on. Does anyone have any tips on designing and writing a implementation in C++, or better yet, code examples?
I wrote a FSM based off of a chapter in "Massively Multiplayer Game Development" Edited by Thor Alexander. Inside is a chapter labelled "Parallel-State Machines for Believable Characters". This is written in python, but the concepts are easily translatable into C++. I highly recommend checking this out, even though this is about character states, not game states.
What I created is here: https://github.com/swganh/mmoserver/tree/master/src/ZoneServer/GameSystemManagers/State%20Manager look under StateManager for implementation details, but basically you have different 'base states' that you can use. Then from there you have the specific states that you transition to as a character, so every state is a class. You then check if can transition from one state to another and then on 'enter' you make your switch, you can also easily do things like put in events after moving to a state. I found this worked out really well for the game so far.
What I have implemented is what the book calls a parallel state machine, which is essential multiple fsm's working together, in this case you can transition into one state, that blocks all other states (ie: CreatureState_Dead). I'm not going to go too much more into detail as I don't think it would really help you, but if you'd like I can elaborate.
Programming Game AI By Example (http://www.ai-junkie.com/books/toc_pgaibe.html) has an example implementation that's pretty straightforward and just handles the basics. Transitions are handled in a single method call (first Enter(), then Execute() every update, Exit() when transitioning)> I don't know what you'd need besides that. I would implement more complicated transitions as states of their own that are just designed to execute once and move to the next state in sequence.
I'll take a stab and assume you're looking at FSMs for AI, if so I recommend you take a look at behavior trees. AIGameDev has some great articles on it.
If C++ template magic and potential long compilation times is not a problem for you and you already have Boost installed to work with:
Boost now have an efficient (in speed and size) meta-state-machine library that have the advantage of letting you set the transition table separately from the states structures : you have a table that describe when to go from wich state to witch other state. You just have to read it to understand what's going on in the state machine.
The other advantage is that it have been tested by several enterprises even in embedded softwares with high-performance software (see the boost mailing list for details). As the implementation is already there, it might be a good choice if you need a generic state machine implementation that Just Works(tm).
It also support orthogonal states (parallel states) and other useful UML-based features.
It also provide several ways to express the transition table, one being experimental but interesting on the expressivity side (although limited by current compiler performance -- too bad!)