I’ve always enjoyed working with artificial intelligence. It’s one of the main reasons I got into video game programming, as opposed to art or music. The way computers “think” and react, the way they “learn” always fascinated me when I was little.

Then I found out how it was done.

It’s all trickery, man. David Blaine is driving the “brain” in that Scorpion that’s kicking your ass. The computer isn’t “thinking” or “learning,” it follows a set of patterns and waits for conditions to be met and then fires off a sequence of events. While, for some people, that’s the extent of what “thinking” might be, I had always thought it was more.

Blaine Scorpion

GET OVER HERE! *Plunges your card into your chest*

Never the less, though, this stuff is pretty cool.

The patterns they follow are like drawn out math equations that are intermixed with a bit of randomness to seem more “human.” And the way the algorithm works isn’t too much different than a very basic understanding of how the world is around you, and acting accordingly. Cause and Effect. Stimuli and Reaction.

And that’s where we get the State Machine.

State Your Business

Getting this out of the way now, this tutorial is wrought with puns. 

You’re playing a fighting game. The match starts, and you start mashing buttons, flying towards your AI-controlled enemy like spinning top in a tornado, when, suddenly, your opponent blocks all your moves, counters, and puts you back into your corner of the screen. Surely in your chaotic button mashing, there would be no way for your enemy to figure out how to stop you, so what happened!?

Well, first off, you’re bad at fighting games. Second, Your opponent is driven by a well thought-out State Machine. What is a state machine? A state machine, or, more accurately, a Finite State Machine, is a design pattern of a mathematical computational model that can perform a set of logic (called a “state”) and can switch its state based on some form of input (what we’re calling a “conditional”).

So, if we wanted to visualize states, we can take a look at this diagram from Leanpub: Developing Games With Ruby.

34-tank-fsm

Alright! Pretty simple: Every bubble here is a State – A set of commands and logic to perform for that action. Every line here is a Conditional – An input that will force the current state to change to the next corresponding state. If we look at the Roaming state in the top-left of the image, you can see it has 2 conditionals that change the roaming state, and 2 conditions that change the current state to the roaming state. Roaming is a set of logic that would, I assume, have the enemy moving around a random space. So every update loop, it would wander around. But, at the end of the loop iteration, it checks “wait, is there an enemy around me?” And you can see how that drills down in the image. If I encounter an enemy and my health is low, I change my state to Fleeing. If my health is optimal, then we shoot ’em! This kind of logic is pretty simple to how we operate and think! It’s reminiscent of an old programmer joke:

A programmer is leaving for the store. He says bye to his wife, and his wife says “Oh! Can you pick up milk? And if they have eggs, get six.” So the man leaves, and, an hour later, he returns with 6 gallons of milk. His wife asks “Why did you get so much milk!?”

He responds, “They had eggs.”

Buh-dum-tss.

But that’s it! He had a state, he checked a condition, and he changed his state. That’s the State Machine in action. If we go back to fighting David Blaine’s Scorpion, we can break down the thought process of what the AI can observe.

IdleState:
if the player is within a specific distance and is in an attack state
     ChangeState(BlockState)

BlockState:
if Block resulted in a Parry
     ChangeState(AttackState)
else if the player is within a specific distance and is in an attack state
     continue to Block
else
     ChangeState(IdleState)

We can see the progression through the states through the gameplay. Sometimes (especially in fighting games) these states change like lightning, but every frame they check to see what’s happening in the world around them.

Keith’s Notes: Honestly, having a construct that’s aware of the “Game State” every frame is important to every game. Unity does that with its Scenes and how everything in the scene can be accessed via GameObject. If you’re doing an RTS, or a multiplayer anything, having a way to access your game state during any frame is crucial.

Welcome To The Machine

So, time to get to the actual code. The code is going to be written for Unity, but, really, you can apply the logic to just about any language. I’ll try to keep things general.

So, in our design pattern, we have 2 major classes: State and the State Machine. State will act as in interface class from which all our states are derived, and the State Machine is a class that contains all our states for that object. In our game, every AI object will have its own State Machine, and its own list of states. (There are other ways to do this – make the state machine a singleton, or make each state a set of static functions, and each AI object just passes flyweights to it. But this is the Super Simple State Machine tutorial, not the Optimized Abstract Polymorphic Functional Monad Immutable State Machine tutorial)

So, lets look at some code. First thing we’re looking at is the State.

public abstract class State : MonoBehaviour
{
    public string Name;
    public abstract void OnEnter();
    public abstract void Run();
    public abstract string CheckConditions();
    public abstract void OnExit();

}

Pretty basic. Very Abstract. Much polymorphic. Like I said, State is an interface. But we do have a number of things here that we need to touch on.

First, for those who don’t use Unity, we are deriving from MonoBehaviour here so we can attach multiple States to our objects. C# only allows for 1 inherited class, so I had to add it to State so our future states can be both States and MonoBehaviour. It’s weird, just go with it.

Second, we have a string Name. For those who do use Unity, you know that GameObjects already have a name, so what gives? Think of this Name as a key for looking up the State in a small list of States, because that’s exactly what it’s going to do.

Third, we have 4 abstract functions. These are really the heart of all states, and what really enable the functionality of the state machine. Each state must manage itself:

  1. When the State is entered, we call OnEnter() to initialize any variables – set timers, init a random value, find the Player object or nearest target, etc.
  2. Run() is were we perform our logic. We update our position, We send data to other managers, spawn objects, etc.
  3. CheckConditions() is called at the end of each Run(). This is where we check the state of the game to see if our input has triggered a change. We might be too {far from | close to} the player, or a timer has run out, or our health has dropped too low. When that happens, we return the name of the state we are switching to. If not, we return an empty string.
  4. We clean up any allocated memory or changed state with OnExit(), in case that wasn’t obvious.

So, that’s pretty basic. We’ll create a few states in just a bit, but lets look at the second-most-important part of the State Machine… The State Machine!

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

namespace SuperSimpleStateMachine
{
    [System.Serializable]
    public class StateMachine : MonoBehaviour
    {
        [System.Serializable]
        public abstract class State : MonoBehaviour
        {
            public string Name;
            public abstract void OnEnter();
            public abstract void Run();
            public abstract string CheckConditions();
            public abstract void OnExit();

        }

        public State[] States;
        public State CurrentState;
        public bool isActive = true;

        void Start()
        {
            if (CurrentState != null)
            {
                CurrentState.OnEnter();
            }
        }

        // Update is called once per frame
        void Update()
        {
            if (isActive == true && CurrentState != null)
            {
                CurrentState.Run();
                string stateId = CurrentState.CheckConditions();
                if (stateId.Length > 0)
                {
                    foreach (State s in States)
                    {
                        if (s.Name == stateId)
                        {
                            CurrentState.OnExit();
                            CurrentState = s;
                            CurrentState.OnEnter();
                            break;
                        }
                    }

                }

            }
        }

        public void ChangeState(State state)
        {
            if (state == null)
                return;
            if (CurrentState != null)
            {
                CurrentState.OnExit();
            }
            CurrentState = state;
            CurrentState.OnEnter();
        }

        public void SetActive(bool isActive)
        {
            this.isActive = isActive;
        }
    }
}

Now, now, the first thing you might notice is State inside of the StateMachine class. That’s fine, it’s the same one I talked about before. I tucked it inside the StateMachine class to keep things neat.

The StateMachine class has 3 members in it, and I’ll just run through and explain each one real quick:

  • State[] States – This, obviously, is an array of all the available states for this AI Object. When we make the call to switch to a new state, we look up the new state by it’s name out of this Array. Now, why is it an Array? Well, for the non-Unity users out there, Arrays in Unity are directly modifiable via the Unity IDE, known as the Inspector. The Inspector makes it easy to manage arrays, but stutters a bit when using more useful constructs like Stacks, Queues, or Hashmaps. If you’re not using Unity, or use a package or Editor tool for your project, then, please, use one of the other structures, for very obvious reasons. I didn’t do anything like that for this tutorial for simplicity’s sake (Super Simple, guys. Why do I have to keep saying this?).
  • State CurrentState – This is a simple pointer to keep track of the state we are currently on. Also could’ve been an integer that keeps the index of the Array, or a name, or some functor monstrosity, but it’s my StateMachine, so my rules!
  • bool isActive – So, this is something a little fun and handy that I put in for later projects. If I was to have 2 AI systems, like a Finite State Machine and a Flocking Algorithm, that I wanted to keep separate, but also be able to switch between them, I could literally pause the StateMachine by flipping this to false, and turn on the other system. Also acts as a handy mechanic for implementing a “Pause” functionality on your AI.

Now, onto the functions!

The Start() function is simple. Like I said before, when we first enter a State, we call OnEnter() to initialize the variables. Start() gets called once the GameObject is initialized in the scene, so, if we have a CurrentState already set, we have to initialize it.

Update() is our meat-and-potatoes. Update() is called every frame, so it’s our main loop for this AI system. Every frame, we first check to see if isActive is true, and if the CurrentState is not null (which it probably won’t be, but I’m sure someone will figure out how to break it). If so, then we step inside and call the CurrentState‘s Run() function, and perform the logic for that State. After, we then call CheckConditions() and see if there was anything that triggers our State to change. The if check on the next line checks the return value to see if it’s empty, and, if not, we drop down to a loop to change out state. We look up the State.name that was returned, call OnExit() on our CurrentState, change CurrentState to the new state, and call OnEnter() on it. That is our quick State change right there! Nothing too complex, right?

Keith’s Notes: It’s also worth mentioning that any State could go and return its own name. doing so would reinitialize the state and it would start over from there. Worth noting, so you could perform some wild actions – change an enemy’s target, choose a new random direction, etc…

Next we have ChangeState(State state). But, why do we have this? Aren’t we already changing the State a different way in the Update() function? Why do it twice? Why are you so bad at coding, Keith!?

Keith’s Notes: Did anyone else read that in my father’s voice? No? Right, anyway…

The reason we’re doing it again and differently is because this function is actually a Callback function. This function can be used as an event to change the State outside of the normal State change logic without needing the CheckConditions() function. You could set up an event to fire whenever the Player is killed, or if a “commander” AI unit dies and you want all the AI units to immediately switch to their Flee State. But why is this function different? Well, there’s a bit of extra error-checking to make sure we’re not passed a null state parameter. Then, we also check to make sure our CurrentState isn’t null, and, if it isn’t, we call our OnExit() on it. The rest is same as before; switch the CurrentState, and call OnEnter(). Done.

SetActive(bool isActive) is a mutator. Do people still use the word “mutator?” Uhhh… setter? Whatever. This was also done as a callback back before Unity allowed callbacks to use lamda functions in their UnityEvents. That’s all. Moving on.

So, by now, you see how our State is constructed, and now our StateMachine works. But now what? How do you actually make a State? Here are a few examples to get you going.

Secretary Of State

Here is a quick example of a State that probably everybody wants: A Chase State. The Chase State is a 2D quick-and-dirty smooth follow algorithm, but it shows how to set up a very basic State.

using UnityEngine;
using System.Collections;
using SuperSimpleStateMachine;

[System.Serializable]
public class ChaseState : StateMachine.State
{
	public Transform target;
	public float dampTime = 1.25f;
	private Vector3 velocity = Vector3.zero;
	public float minDistanceToTarget = 1.0f;
	public string OnEnemyLostState = "WanderState";
	public string OnEnemyMinDistanceState = "FleeState";

	public override void   OnEnter()
	{
        // TODO get target
	}
	public override void   Run()
	{
		if(target != null)
		{
			Vector3 delta = target.position - 
                                        transform.position;
			Vector3 destination = transform.position + delta;
			transform.position = Vector3.SmoothDamp(transform.position, destination, ref velocity, dampTime);
		}
	}
	public override string CheckConditions()
	{
		if(target == null)
		{
			return OnEnemyLostState;
		}
		else if( Vector3.Distance(transform.position, target.position) < minDistanceToTarget)
		{
			return OnEnemyMinDistanceState;
		}
		else
			return "";
	}
	public override void   OnExit()
	{
		
	}
}

Not overly complex, again, right? All our abstract methods from the State interface are all overridden and filled out nicely, except for OnEnter() and OnExit(). Lets do another run-down, starting with the members.

  • Transform target – Like I said, this is a basic Smooth Follow, and target is who we’re following. For those who don’t use Unity, a Transform is basically the 3D matrix that defines the Object’s position, rotation, and scale in our world.
  • float dampTime – This Smooth Follow makes use of Unity’s Vector3.SmoothDamp function. What this does is gradually change the Vector from one position to another over the specified time (in our case, dampTime). The link explains it in the best detail, and I’ll talk about it a little more once we talk about the Run() function.
  • Vector3 velocity – This is also used by the Vector3.SmoothDamp. It’s returned from the function as a way to let you utilize the velocity the object would need to travel at to reach the desired position.
  • float minDistanceToTarget – This is a cut-off condition that we check for. Once our AI Object is within this distance to the target, we then return OnEnemyMinDistanceState.
  • string OnEnemyLostState – This is the name of the State we switch to if the target is lost or suddenly becomes null. Logic could be added to check for a maxDistanceToTarget if we wanted to.
  • string OnEnemyMinDistanceState – Were you not paying attention? What did I say 2 members ago? Jeez, man.

Now that the members are explained, lets take a look at how they are used. First thing you’ll notice (if you’re a Unity Developer) is that we’re not using Start(), Update(), or OnDestroy(). You can totally use these function if you want, but that’s not how we’re driving the State. We want the State to be controlled by the StateMachine, so that’s how we’re using it.

First thing is OnEnter(). OnEnter() just has a TODO inside of it. Am I lazy? Yes, but not this time. In the example provided, the target is set in this State through the Inspector, and there is no logic that ever kills the target or sets the target member to null.

Next we have Run(), and that’s doing the real logic, here. We check if the target is null, and if it isn’t, then we determine the direction we have to take to the target, and we call that delta. We add delta to our position, and that’ll be the destination (basically, we want to move one “unit” in the direction of the target). We then call Vector3.SmoothDamp, passing in our position, the destination, a reference to our velocity (since SmoothDamp will fill that out) and our dampTime. Now, I could’ve just passed in the target.position instead of calculating a destination, but SmoothDamp utilizes a spring-damper-like function to smooth out its result. By making the destination a “unit in the direction” of the target, we get a different behavior out of the function. I say to you, play with this function. Multiply the destination by a scalar value. Use target.position. Maybe look up some simple steering algorithm and chuck that in there! It’s your world!

Now we’re on to CheckConditions(). Now that we’ve performed a “frame” of logic for this AI Object, we want to see if it’s time to change. Most of this I’ve explained in the members, but we’ll run through again. If the target is null, then we pass back the name of the State attributed to OnEnemyLostState. If we’re too close to the target (less than minDistanceToTarget), then we pass back OnEnemyMinDistanceState. If none of those, then we pass back an empty string. All of these values get ingested by the StateMachine, and the StateMachine‘s Update() function will look up those names and switch to the appropriate State. These members, OnEnemyLostState and OnEnemyMinDistanceState, are set inside the Inspector in Unity, so we can have them change around to do a lot of things, if we wanted to. Maybe OnEnemyMinDistanceState could change to a DetonateState that blows up next to the target. Maybe OnEnemyLostState could change to a State to go and find a new target in a HuntState. Again, it’s your world, buck-o.

Then we have OnExit(), which does 2 things: “Jack” and “Shit.”

Closing Statement

So, there you have it, a real basic run-down of a simple state machine, what it does, and how to use it. And you, you’re smart, right? You can do a lot with this thing. State Machines are just ripe to be messed with. You can use this StateMachine to not just drive movement, but you could use this on, say, a weapon. Have it switch from a hunting state to a lock on and fire state. Or a single-fire state to full-auto state. You can even putz around with the functionality of the StateMachine. Maybe off-load the State changing to another thread. One thing I did for mine was use a Stack instead of an Array to store my CurrentStates. I would then loop through my Stack, perform all the Run()s in each State, and only call CheckConditions() on the top. Then my ChangeState() would push and/or pop the top. You could even drive a menu system with this as well. You can really be flexible with this technology.

Download the code and a Unity Demo here and play with this. Give it a shot. I’ve included all the code you see here, plus a few other States, like a WanderState and a FleeState.

Let me know if you guys want to see more examples of other states or need help with anything. Enjoy!

Advertisements