Finite State Machine (FSM) have been used for many years in video games to model the AI of Non Playing Characters (NPCs). It is one of the easiest ways to model and code a character’s behavior in a finite number of states. The model includes the states and the transition between these states, which changes according to input from the game.
In this post, we will lay out the FSM of a suicidal bot called the “Terror Drone” as it appears in our game, Unstoppable Jake, we’ll explain how it behaves and we’ll share parts of the code that drives the AI for it.
Quick Intro to FSM
FSMs can be simple or very complex, depending on the task they are solving. The truth is that they create an abstraction of the problem that is easy to understand and to code, and they also aid in making an algorithm behave in a deterministic way (do exactly what it’s meant to do), which is especially hard to achieve otherwise when we don’t have control over the input the algorithm is fed with.
So what are FSMs?
Let’s take the example of a simple led flashlight which has 3 states and a single input – a button the user can click on and model an FSM for it. The states of the flashlight are:
- Off – The led is turned off
- On – The led is turned on
- Flash – The led is turned on and off alternatively at a constant frequency.
So, when the flash light is turned off it is in the Off State, the first button click will perform a transition to the On State (turning on the led), an additional click will perform a transition to the Flash State … and yet another press will bring the flashlight back to the Off State. Simple.
Here is a diagram that illustrates the different state transitions:
Lets make it a bit more complex. Lets say the flashlight has a timer as well and one of the features it has, is that it turns off after 30 minutes if no interaction is being made, this is done obviously to save battery life. So in every transition, we can reset a timer to 30 minutes and check for its expiration in our states. This is how it should look like:
A simple representation of the above diagram (the algorithm) in pseudo code will be:
- If State is Off:
- If button clicked:
- Turn On Led
- Reset Timer
- State = On
- If button clicked:
- Else If State is On:
- If Timer Expired:
- Turn Off Led
- State = Off
- Else If button clicked:
- Flash Led (Frequency = 5Hz)
- Reset Timer
- State = Flash
- If Timer Expired:
- Else If State is Flash:
- If (Timer Expired) or (Button Clicked):
- Turn Off Led
- State = Off
- If (Timer Expired) or (Button Clicked):
This pseudo code runs in a loop, and it performs different update statements according to the current state the flashlight is in.
There are other concepts to FSM, such as final states and UML diagrams that helps in designing them and you are advised to read a more thorough explanation of FSMs here.
The Terror Drone Example
Unstoppable Jake is a platform game for the iPhone where the player fight his way through Hax0r Headquarters, a villain who poisoned a whole town with a laxative gas
Hax0r had built his robots to protect his empire against intrusions, one of the bots is named the Terror Drone, a suicidal robot, one with a death wish. When it senses movement near it, it will try to chase the intruder and destroy him, even if it means self-destruction.
So how does the Terror Drone behaves?
- When it is in idle, it moves left and right in the map, the extremities are defined by the level designer when he places the bot in the map.
- When the player comes near the bot, the bot turns on a 5 seconds timer for self destruction and starts chasing the player wherever he goes.
- If the bot is successfully colliding with the player’s character it explodes and kills him, if the 5 seconds timer expires, the bot explodes in its current position, which may harm the player if he will be found nearby.
The following video of the gameplay illustrate the bot in action:
So how does the Finite State Machine of the Terror Drone is modeled?
These are the various states of the Terror Drone:
TerrorDroneState = {MOVE = 1, TURN = 2, CHASE = 3, EXPLODE = 4}
Each instance of the Terror Drone in the level, holds his own state variables, when the TerrorDrone is constructed, the mState variable, which keeps track of its current state is initialized to TerrorDroneState.MOVE, and the update function is called in an endless loop, performing different things according to the current state.
Main Loop
function TerrorDrone:Update() -- Update current time self.mCurMS = gw.getCurrentMs() -- get self current position self.x, self.y = go.getPosition(self.ptr) self.px, self.py = gw.getPlayerPosition() ------------------- -- State Machine -- ------------------- if (self.mState == TerrorDroneState.MOVE) then self:UpdateMOVE() elseif (self.mState == TerrorDroneState.TURN) then self:UpdateTURN() elseif (self.mState == TerrorDroneState.CHASE) then self:UpdateCHASE() elseif (self.mState == TerrorDroneState.EXPLODE) then self:UpdateEXPLODE() end end function TerrorDrone:switchState(newState) app.logString("TerrorDrone Changed State: " .. self.mState .. " -> " .. newState) self.mPrevState = self.mState self.mState = newState end
Code for the Move State
function TerrorDrone:UpdateMOVE() ------------------- -- MOVE -> CHASE -- ------------------- if (self:isPlayerInRange()) then self:stop() self.mChaseEndsMS = self.mCurMS + TerrorDroneChaseTimeMS return end ------------------ -- MOVE -> TURN -- ------------------ -- Turn Left if ((self.x > self.rightX) and (self.mFace == "right")) then self:stop() self.mTurnEndsMS = self.mCurMS + TerrorDroneTurnDurationMS self.mFace = "left" self:switchState(TerrorDroneState.TURN) return -- Turn Right elseif ((self.x < self.leftX) and (self.mFace == "left")) then self:stop() self.mTurnEndsMS = self.mCurMS + TerrorDroneTurnDurationMS self.mFace = "right" self:switchState(TerrorDroneState.TURN) return end ---------------- -- State Work -- ---------------- if (self.mFace == "right") then self:moveRight() else self:moveLeft() end end
Code for the Turn State
function TerrorDrone:UpdateTURN() if (self.mCurMS > self.mTurnEndsMS) then self:switchState(TerrorDroneState.MOVE) if (self.mFace == "right") then self:moveRight() else self:moveLeft() end return end ---------------- -- State Work -- ---------------- self:stop() end
Code for the Chase State
function TerrorDrone:UpdateCHASE() if ((self:isPlayerInShockProximity()) or (self.mCurMS > self.mChaseEndsMS)) then self:switchState(TerrorDroneState.EXPLODE) return end -- Compute Chase Direction (relative to player's direction) if (self.px > self.x) then self.mChase = "right" else self.mChase = "left" end -- Chasing if ((self.mChase == "right") and (self.mFace == "right")) then self:moveRight() elseif ((self.mChase == "left") and (self.mFace == "left")) then self:moveLeft() end end
Code for the Explode State
function TerrorDrone:UpdateEXPLODE() gw.spawnGameObject(self.layerIdx, "TerrorExplosion", self.x, self.y) snd.playFX("blast", self:distToPlayer()) go.destroy(self.ptr) end