FSMs -- Finite State Machines

- What is a FSM?
  - A collection of states, and how you transition between them.
  
- Where are Finite State Machines used in games?
  - The GAME's state -- paused, in-game, title screen, options, etc.
  - An AI's state -- attacking, defending, running for cover, etc.
  - A LEVEL's state -- doomsday switch pulled / not pulled
  - Remember the FSM from the first class?

  - This class is going to focus on AI state machines, as they are the most complicated.
    - Most other state machines are very simple to write.

- What do you need to have to define a FSM
  - A list of states, each of which define
    - Update logic for the state
    - A list of Exit conditions and next states
      - When you would transition to that state
    - Entry condition
      - When you can enter this state.  Technically not needed, but can be useful when writing the FSM
  - The initial state

- You can only record data (like getting a target) when entering a state.  That way you can reuse the state with different data

- C structures for an AI FSM
  - Very similar to animations, there is a "Def" structure and a Runtime structure.
  - Example:

    // Define a FSM
	struct FSMDef
	{
    	// List of states
	    vector<FSMStateDef*> states;

        // Initial state -- index into STATES array above
	    int initState;
	};

    // Define an FSM State
	struct FSMStateDef
	{
    	// Selects update logic
	    int behaviorStyle;

        // Entry condition
	    Condition entryCond;

        // Exit conditions
	    vector< pair<Condition,int> > nextStates;
	};

    // Runtime data
	struct FSM
	{
		FSMDef* def;
		int curState;
		GameData stateData;
	};
  - behaviorStyle is intentionally seperate from the state so it can be duplicated
    - "Find QuadDamage" and "Run to Cover" can use the same update logic, but with different targets to run toward.  They'd have the same behaviorStyle, but with slightly different Init's

  - Functions you'll need to define:
    - Init -- Set the FSM to the init state
    - Update -- Run update logic for the current state, then switch active states if necesarry
    - Destroy -- Clean up any memory allocated by the current state

  - psuedo code:
    void FSMInit(FSM* fsm, FSMDef* def)
	{
		fsm->def = def;
		fsm->curState = def->initState;

        // should set gameData, and do any other state specific
        // initialization
        FSMStateEnter( fsm->def->states[ fsm->curState ], ...);
    }
    
	void FSMDestroy(FSM* fsm)
	{
        // should free gameData and do any state specific cleanup
        FSMStateExit( fsm->def->states[ fsm->curState ], ...)
	    FSMStateExit( , &fsm->gameData );
    }
    
	void FSMUpdate(FSM* fsm)
	{
		FSMStateDef* curStateDef = fsm->def->states[ fsm->curState ];

        FSMStateUpdate( curStateDef->behaviorStyle, ... );

        foreach( pair in curStateDef->nextStates ) {
            FSMStateDef* stateDef = fsm->def->states[ pair.int ];
            if( ConditionValue( pair.Condition ) && ConditionValue( stateDef->entryCond )) {
                // change state
                FSMStateExit( curStateDef->behaviorStyle, ... );
                fsm->curState = pair.int;
                FSMStateEnter( StateDef->behaviorStyle, ... );

                return;
            }
        }
    }


- Conditions
  - VERY game specific
  - Can be nice to use a scripting language like Python here (will be covered next class)
  - If using a scripting language is too much work, can get most of it with just numeric comparisons
    - AND / OR
    - List of
      - Value name (PLAYER_HEALTH, TARGET_HEALTH, TIME_IN_STATE, etc)
      - Comparison op (LESS, GREATER, EQUAL, etc)
      - Number