Finite State Machines : A Tutorial Part One

[Haywood Slap]

Ok, I've been on the road, away from my gaming rig for over a week now and it's driving me crazy. So to kill time I've put together a short tutorial for Finite State Machines (FSM) in Lua.

Notes

1. The code here is based on the code in the Finite State Machine tutorial on the LUa Wiki.
2. All the code presented here is meant to be run in Lua for Windows (L4W) and not in OFP.
3. This tutorial is intended for beginning programmers, but an understanding of Lua tables wouldn't hurt.

Finite State Machines

Finite State Machines (FSM) are used extensively in game AI programming, and it is likely impossible (or at least very difficult) to write a good AI that doesn't use a state machine of some sort. For example, in a sector control style mission every sector could have a FSM to keep track of who is present in the sector, who controls the sector, etc. Or each AI echelon could have a FSM that controls its behaviour in combat; when half the members have been killed the echelon enters the "Weak" state, if the AI is attacked while in the "Weak" state it falls back and calls for back up. Etc. A full discussion of state machines is beyond the scope of this tutorial, but lots of good articles can be found with Google, on Wikipedia, or in any computer science text book.

However, in brief, a FSM is a finite set of states (hence the name), a set of transitions/events between the states, and a "current state". Each FSM also has a "state transition table" that is used to look up the next state given the current state and an event.

Before we can implement a FSM we need to figure out what the "states" and "events" are; a FSM isn't very useful if no action is performed when the FSM switches states. Therefore we will use functions as the states in our FSM. When the FSM transitions to a new state we will simply "execute" the new state (call the function). For the events we will use strings. Using strings for the events makes it easy to print a human readable description of the event.

So, lets write a simple FSM for controlling the state of a sector in a sector control style mission. We'll start with two states, Unoccupied and Occupied and two events ENTERED and LEFT. When a unit enters a sector that is in the Unoccupied state the sector will move to the Occupied state. When a unit leaves the sector it will revert to the Unoccupied state (for now we are assuming there is only one unit and one sector... which won't be a very fun mission, but it lets us focus on the essentials of the FSM).

Here are the definitions for the states and transitions.

-- This will be called when a sector enters the Unoccupied state
function Unoccupied()
    print("Sector is unoccupied")
end

-- This will be called when a sector enters the Occupied state
function Occupied()
    print("Sector is occupied")
end

-- The transitions used to move between states
ENTERED = "entered the sector"
LEFT = "left the sector"

Now that we have our states and our events defined we need to contruct a state transition table. This table is used by the FSM to look up the next state based on the current state and the event that occurred. First we will define a table that contains a series of "triples" (tables with exactly three values). Each triple takes the form { current_state, event, new_state}. The triples for our simple sector control FSM are:

sc_triples = {
    {Unoccupied, ENTERED, Occupied},
    {Occupied, LEFT, Unoccupied}
}

This says that when a FSM is in the Unoccupied state and recieves an "ENTERED" event it will transition to the Occupied state. And if a FSM is in the Occupied state and recieves a "LEFT" event it will transition to the Unoccupied state. Defining our transitions this way makes it "easy" (a relative term here) to examine the FSM behaviour.

Now we will write a function that takes the sc_triples table and constructs the state transition table we need for the FSM.

function createFSM(triples)
    local fsm = {}
    for _,row in ipairs(triples) do
        local old, event, new = row[1], row[2], row[3]
        if fsm[old] == nil then
            fsm[old] = {}
        end
        fsm[old][event] = new
    end
    return fsm
end

This function iterates over all the rows in the 'triples' table and extracts the three values into local variables. Then we check the fsm table to see if it already contains an entry for fsm[old], if not we initialize fsm[old] to a new empty table. Then we add the new state to fsm[old][event].

Now, if we know the current state and the event, we can find the new state by looking it up in the state transition table. All we need to do is keep track of the current state and let the FSM bounce around (for lack of a better term) based on the events it receives.

-- Start in the unoccupied state.
state = Unoccupied
event_list = {ENTERED, ENTERED, LEFT, ENTERED, LEFT, LEFT, ENTERED}
fsm = createFSM(sc_triples)
for _,e in ipairs(event_list) do
    local newState = fsm[state][e]
    if newState ~= nil then
        newState()  -- execute the function
        state = newState
    end
end

The above code constructs a FSM from our transition definitions in 'sc_triples' and executes a sequence of events in succession. In a real mission these events would be "fired" in OFP's onEnter and/or OnLeave event handlers.

If there is enough interest, I will expand on this tutorial to add more states and transitions, show how to pass information into the state functions, and simulate the OFP:* functions to make debugging OFP scripts in L4W easier.

Enjoy!

Below is the complete code for the above FSM:

--[[
    Haywood's Finite State Machine Tutorial
    Part One.

    You will need Lua for Windows (http://luaforwindows.luaforge.net/)
    to run run this code.
]]

-- The unoccupied state
function Unoccupied()
    print("Sector is unoccupied")
end

-- The occupied state
function Occupied()
    print("Sector is occupied")
end

-- Transitions used in the FSM
ENTERED = "entered the sector"
LEFT = "left the sector"

-- The triples that describe our state machine.
sc_triples = {
    {Unoccupied, ENTERED, Occupied},
    {Occupied, LEFT, Unoccupied}
}

-- Creates the state transition table from the above triples.
function createFSM(triples)
    local fsm = {}
    for _,row in ipairs(triples) do
        local old, event, new = row[1], row[2], row[3]
        if fsm[old] == nil then
            fsm[old] = {}
        end
        fsm[old][event] = new
    end
    return fsm
end

-- Test the FSM!
-- Start in the unoccupied state.
fsm = createFSM(sc_triples)
state = Unoccupied

-- These would be generated by in game events (onEnter, onLeave, 
-- onDeath, etc.) so we will simulate a few events ourselves.
event_list = {ENTERED, ENTERED, LEFT, ENTERED, LEFT, LEFT, ENTERED}
for _,e in ipairs(event_list) do
    local newState = fsm[state][e]
    if newState ~= nil then
        newState()  -- execute the function
        state = newState
    end
end
print("FSM Completed")