Modeling a Simple AI behavior using a Finite State Machine

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:

  1. If State is Off:
    1. If button clicked:
      1. Turn On Led
      2. Reset Timer
      3. State = On
  2. Else If State is On:
    1. If Timer Expired:
      1. Turn Off Led
      2. State = Off
    2. Else If button clicked:
      1. Flash Led (Frequency = 5Hz)
      2. Reset Timer
      3. State = Flash
  3. Else If State is Flash:
    1. If (Timer Expired) or (Button Clicked):
      1. Turn Off Led
      2. State = Off

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