XNA AI Finite State Machine

Coding game AI naively with switch statements nested 3-4 levels deep is bad, really bad, really really bad (I just can’t find a better word), it starts simple enough – if this do that – and then it gets ugly real quick. I did not get to nest 3 levels of ifs but I was not very far from it either. There are a few approaches to coding game AI (GOAP seems interesting) but I have little time so it seems that the easiest way to solve my problem is an old friend, the Finite State Machine. A quick search of the internets revealed a number of C# FSM implementations but it seems that they were created to scratch specific itches that are almost but not quite exactly as mine, so I had to write my own. There is nothing special about it (I think it’s actually quite trivial) other than the fact that I could not find something like it and that’s the reason I’m sharing it. Also, the code is not really XNA or game or AI specific but I’m using it to implement AI in an XNA game so…

To see how it all started, this is the flow of one of the formation-flying enemies in Astralia:

Modeling the above flow with ifs and switch statements is possible but requires a level of obsessive compulsiveness that I do not have and after a little work I ended up with something more manageable that looks like this:

var idle = new State>("idle", null, null, null);
var follow = new State>("follow", null, null, null);
var lead = new State>("lead", null, EnterLead, null);
var rally = new State>("rally", Rally, EnterRally, null);
var patrol = new State>("patrol", Patrol, null, null);
var attack = new State>("attack", null, null, null);

idle.AddTransition(lead, () => Leader == null);
idle.AddTransition(follow, () => Leader != null);
follow.AddTransition(lead, () => Leader == null);
lead.AddTransition(rally, () => Members.Count rally.AddTransition(patrol, () => Members.Count == FormationSize);
patrol.AddTransition(attack, () => Target != null);
attack.AddTransition(patrol, () => Target == null);
...
aiMachine = new StateMachine


What happens should be reasonably obvious, first declare the states and then add transitions between them.

A state has a name (for debugging purposes mostly), a tag which is whatever you want to associate with that state and two more actions that get called when entering/leaving the state.

State(string name, T tag, Action onEnter, Action onExit)

Adding a transition to a state requires the next state and a condition function that “guards” the transition, the condition needs to be true for the transition to happen. If there are multiple transitions leaving a state they are simply checked in the order they were added and the first one that has the condition satisfied is used.

public void AddTransition(State<lT> nextState, Func condition)

All that is left now is to update the state machine in your game loop and do whatever you need to do with the state tag (in my case I have a delegate that I call).

aiMachine.Update();
aiMachine.CurrentState.Tag(elapsedTime);

And now for the code:

public class State {
internal readonly Action OnEnter;
internal readonly Action OnExit;
internal readonly List> Transitions = new List>();

public State(string name, T tag, Action onEnter, Action onExit) {
OnEnter = onEnter;
OnExit = onExit;
Name = name;
Tag = tag;
}

public string Name { get; private set; }
public T Tag { get; set; }

public void AddTransition(State nextState, Func condition) {
Transitions.Add(new Transition(nextState, condition));
}
}

internal class Transition {
internal readonly Func Condition;
internal readonly State NextState;


internal Transition(State nextState, Func condition) {
NextState = nextState;
Condition = condition;
}
}

public class StateMachine {
public StateMachine(State currentState) {
CurrentState = currentState;
}

public State CurrentState { get; private set; }

public void Update() {
while (MoveToNext()) {}
}

private bool MoveToNext() {
for (int i = 0; i < CurrentState.Transitions.Count; i++) {
Transition t = CurrentState.Transitions[i];
if (t.Condition()) {
if (CurrentState.OnExit != null) CurrentState.OnExit();
CurrentState = t.NextState;
if (CurrentState.OnEnter != null) CurrentState.OnEnter();
return true;
}
}
return false;
}
}

This is it.

2 thoughts on “XNA AI Finite State Machine

  1. DrPool

    Hi Gabriel,

    thanks for the post. I tried to implement something similar with you statemachine (the classic lightswitch), which works, but I don’t really know what purpose of the Tag is. Also when first implementing your example using some dummy classes for target, leader etc. it crashed when setting the time here:
    aiMachine.CurrentState.Tag(elapsedTime);
    since for some states (e.g. idle) you put a null pointer, so how is this going to work.

    Anyway, here my simple example, comments are welcome:

    bool light = false;

    Action enterLightOn = delegate { Console.WriteLine(“enter light on”); };
    Action exitLightOn = delegate {Console.WriteLine(“exit light on”);};
    Action enterLightOff = delegate { Console.WriteLine(“enter light off”); };
    Action exitLightOff = delegate {Console.WriteLine(“exit light off”);};

    Action lightCheck = delegate(bool myLight) { Console.WriteLine(“Mylight is ” + myLight);};

    var lightOff = new State>(“lightOff”, lightCheck, enterLightOff, exitLightOff);
    var lightOn = new State>(“lighton”, lightCheck, enterLightOn, exitLightOn);

    lightOff.AddTransition(lightOn,() => light == true);
    lightOn.AddTransition(lightOff,() => light == false);

    var aiMachine = new StateMachine>(lightOff);
    aiMachine.CurrentState.Tag(light);
    aiMachine.Update();
    aiMachine.CurrentState.Tag(light);
    light = false;
    aiMachine.Update();
    aiMachine.CurrentState.Tag(light);
    light = true;
    aiMachine.Update();
    aiMachine.CurrentState.Tag(light);
    light = false;
    aiMachine.Update();
    aiMachine.CurrentState.Tag(light);
    aiMachine.Update();

    string name = Console.ReadLine();

    Reply
  2. Gabriel

    The Tag is basically user data associated with the state, in my example I assign it a delegate with the action the AI should repeatedly take in that state – that’s why I have the Tag() calls in the code.

    You could put whatever your logic requires in the Tag, a string message, object reference, etc.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *