|
Title: Best approaches to state machines Post by: Melly on January 11, 2011, 08:13:29 PM As you start making a game a bit more complex than your usual shmup, you find yourself having to worry with how your game entities behave in relation to eachother and their environment a lot more than usual. This is something I've been dealing with for a while now, and I'm not really sure of how to approach it.
Right now, my projects have used a simple system of having a large pool of boolean variables, each representing a different state. Many states can coexist, like "attacking" and "crouching". This approach is somewhat loose and can get out of hand when your entity is very complex, like the main player character, and I keep having to remember to set or reset several state flags with every action. I'm wondering if you guys can help me find a better approach from a programming standpoint to handling entity states, that is still simple enough that just telling the game the entity is now "vulnerable" doesn't take more than a line of code. Title: Re: Best approaches to state machines Post by: mcc on January 11, 2011, 08:51:10 PM Maybe I don't understand the question, however, have you tried bitfields / bit arithmetic?
enum { STATE_RESET = 0 STATE_JUMP = 1 STATE_CROUCH = 2 STATE_RUN = 4 STATE_VULNERABLE = 8 STATE_DEAD = 16 } state = STATE_JUMP | STATE_CROUCH; // Set flags to exactly jumping+crouching if (state & STATE_JUMP) do_something_jump_related(); // Query jump bit state |= STATE_JUMP; // Set jump bit state &= ~(STATE_CROUCH); // Unset crouch bit state &= ~(STATE_CROUCH | STATE_JUMP); // Unset crouch bit and jump bit at once Replace "enum" with whatever is appropriate for constants in your language. This at least lets you compress several operations at once into a single line. Title: Re: Best approaches to state machines Post by: Melly on January 11, 2011, 09:47:50 PM That looks like an interesting way to do it, though with my luck I'd probably lose track of it even more.
Title: Re: Best approaches to state machines Post by: Chris Z on January 11, 2011, 09:59:27 PM Doesn't sound like you need a state machine for what you mention, since state machines/graphs are more useful for behavior. mcc's bitfield solution is probably as clean as it can get, in terms of lines of code. I can type up my general state machine solution if you really do need something for behavior.
Title: Re: Best approaches to state machines Post by: Melly on January 11, 2011, 11:08:41 PM Then what would I use for what I mention?
Title: Re: Best approaches to state machines Post by: Chris Z on January 11, 2011, 11:36:15 PM how your game entities behave in relation to eachother and their environment simple enough that just telling the game the entity is now "vulnerable" doesn't take more than a line of code. These are two different problems, the second being handled by something like the bitfield solution. In other words, there are two types of state here: behavioral (#1) and object state (#2) In any case, for behavior through FSMs I use something similar to what is described in Programming Game AI by Example (http://www.amazon.com/Programming-Game-AI-Example-ebook/dp/B0029LCJXE/ref=sr_1_45?ie=UTF8&m=AG56TWVU5XWC2&s=digital-text&qid=1273106659&sr=1-45). Here's part of my implementation (C#): Code: public abstract class State<OwnerType> { public abstract void Update(OwnerType owner); public virtual void Enter(OwnerType owner) { } public virtual void Exit(OwnerType owner) { } public virtual bool OnMessage(OwnerType owner, Message msg) { return false; } } public class StateMachine<OwnerType> { protected OwnerType m_owner; protected State<OwnerType> m_currentState = null; protected State<OwnerType> m_previousState = null; protected State<OwnerType> m_globalState = null; public OwnerType Owner { get { return m_owner; } set { m_owner = value; } } public State<OwnerType> CurrentState { get { return m_currentState; } } public State<OwnerType> PreviousState { get { return m_previousState; } } public State<OwnerType> GlobalState { get { return m_globalState; } set { m_globalState = value; } } public StateMachine( OwnerType owner, State<OwnerType> currentState, State<OwnerType> previousState, State<OwnerType> globalState ) { m_owner = owner; m_currentState = currentState; m_previousState = previousState; m_globalState = globalState; if (m_globalState != null) { m_globalState.Enter(owner); } if (m_currentState != null) { m_currentState.Enter(owner); } } public void Update() { if (m_globalState != null) { m_globalState.Update(Owner); } if (m_currentState != null) { m_currentState.Update(Owner); } } public void ChangeState(State<OwnerType> state) { if (m_currentState != null) { m_currentState.Exit(Owner); } m_previousState = m_currentState; m_currentState = state; if (m_currentState != null) { m_currentState.Enter(Owner); } } ... } Basically, each State object represents a node in your machine. An Update() implementation is required while Enter() and Exit() functions are optional for any kind of setup or cleanup you dont want to repeat every update. The idea is that your custom states derive from this class (notice its abstract) and you can of course store other state specific variables in the derived state class like timers for some behavior, etc. EDIT: Forgot to mention the reason for the templating. The idea is that the OwnerType object (which will be Player/Ship/whatever) will expose public functions or properties that the state object can modify on Update. The StateMachine class handles updating the current state and an optional global state (if you want to do stuff like differing input depending on the state). Your object for the player, enemy, etc. would only maintain the StateMachine pointer but also has the option of caching State objects instead of allocating them everytime it wants to change state. You can also choose to add an integer ID to the states if you want to make comparison of the current state easier or just use reflection if it's not a performance problem in your language. Hope this helps... Title: Re: Best approaches to state machines Post by: Klaim on January 12, 2011, 01:36:27 AM I've used and implemented a lot of different kind of state machine system and I can say that none is suited to all cases. I've also used similar approaches to the one of Game AI by Practice as cited before.
I often, in the end, implement a simple game-specific solution, either dynamic or fixed at compilation time. Now, I want to try boost::msm (Meta State Machine) (http://www.boost.org/doc/libs/1_45_0/libs/msm/doc/HTML/index.html) as (if you understand a bit of template magic and can afford the compilation time) it seem to be an excellent solution to the problem. If you can't stand heavy templates magic and compilation, just implement simple solutions. Maybe I'll report about using it in a big game in few months, see if it was useful in the end. The main things to implment are : 1. Have one class per state. 2. All states should be able to have sub states (use the Composite pattern). 3. Call one state object function when entering the state and one function when exiting the state. 4. Define a unique way to get from one state to another. Those points are easy to implement in a simple (almost naive) way if you don't want to make a state machine library and just want your game to work. The only exception is if you want several states to be running at the same time in the same state machine. Then you'll need to implement a tricky system, and it will be a mess because it's not esay to manage. It's better to have several parallel state machines than one state machine allowing several states running at the same time. Title: Re: Best approaches to state machines Post by: bateleur on January 12, 2011, 02:00:36 AM I prefer using integers to bits (whether packed into bitfields or not) because it makes it easier to express which regions of a multidimensional state space are legal.
For example, a character might be able to jump and shoot at the same time but not jump and swim, which could be captured like this: Code: static const motion_undefined:int = 0; static const motion_stand:int = 1; static const motion_walk:int = 2; static const motion_run:int = 3; static const motion_jump:int = 4; static const motion_swim:int = 5; static const action_none:int = 0; static const action_use:int = 1; static const action_shoot:int = 2; static const action_throw:int = 3; static const action_boogie:int = 4; function initCharacter() { myCharacter.motion = motion_stand; myCharacter.action = action_none; } More complex examples left as an exercise for the reader. 8) Title: Re: Best approaches to state machines Post by: st33d on January 12, 2011, 03:03:18 AM I use bitwise flags also:
https://github.com/st33d/red-rogue/blob/master/src/com/robotacid/phys/Block.as Though I use the left shift operator instead of multiples of 2 in the code because those operations will get converted to raw numbers at compile time. Bitwise looks a little confusing, but testing one variable as opposed to dozens is a lot easier to read. You'll be saving yourself a lot of bother if you get to grips with it. For discreet states I just use separate integers (1, 2, 3, etc.), so that it's clear that there will never be any cross over. Title: Re: Best approaches to state machines Post by: Alex May on January 12, 2011, 03:37:13 AM Also consider non-finite state machines e.g. fuzzy logic (http://www.pcai.com/web/ai_info/fuzzy_logic.html)
(also you can read up on finite state machines here (http://ai-depot.com/FiniteStateMachines/FSM-Background.html) if you need more info on that Title: Re: Best approaches to state machines Post by: gnat on January 12, 2011, 06:26:29 AM Function pointers can make extremely simple state machines without any extra constants or conditional statements and are built into most languages from C to Python.
Consider the following: Code: void (*StateMovement)(); // Change state. StateMovement = StateMovementRun; StateMovement = StateMovementWalk; // Run current state. StateMovement(); Title: Re: Best approaches to state machines Post by: Melly on January 13, 2011, 09:19:22 PM Thanks for the answers guys. I'll study this and give some thought to what I'm going to use.
|