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.

Astralia – A.R.S.S.E Update 1

Couple more screenshots to show a bit of HUD work – see that ugly minimap…

Also, a lot of invisible work happened, I think the gameplay is now pretty much feature complete, I got all that I had on my “design document” in, there’s some balancing needed with regards to weapons and units armor but it all works, now who’s going to do level design?

EDIT: There aren’t not enough visible changes to warrant a new video, just watch the last one.

Messaging systems for games (and an XNA implementation)

I have been coding and using various incarnations of the messaging system that I will describe below for some time now and I’m still not sure what to call it, it is not exactly an event-driven system or a message bus, message manager seems to be to closest description I can think of.

Now, the advantages of a message driven system should be fairly obvious (systems decoupling mostly) and not the subject of this post, what I have are few empirical rules for when to use messages versus direct systems collaboration:

  • If it is a fire-and-forget situation when you do not need a reply send a message.
  • If it appears that you are implementing an interface just to bring polymorphism to what appears to be unrelated classes then messaging is probably a better alternative. For example some of your game characters (but not all of them) can follow a leader, so you can do something like an IHasLeader interface with leader property and have your character classes implement this interface or you could send a “SetLeader” message and whoever is interested will receive that message and update their leader reference.
  • If you find that some central class holds and maintains various list of objects just for the purpose of changing their state see if you can refactor the code to use messages (usually the Player and the Gameplay implementation have a tendency to do this).
  • If there’s any kind of state that needs to be maintained do not use message, it will get complex real quick, in other words if it seems that you need to exchange multiple messages between components do not do it. Also, there will surely be an unforeseen sequence of messages that will result into subtle and apparently “Heisenbergian” bugs.

Back to my message manager, this is the XNA version of it and I have greatly reduced its features and code base to a very simple and unsophisticated mechanism (this is probably a consequence of starting with the actual game code instead of building a framework first). A few more things about it:

  • Untyped message content, I’m using strings and objects (this can be seen both as a feature and lack of one…).
  • No registering with the message manager, objects query the manager directly for messages directed to them.
  • Double buffered, an event is visible in the next frame.
  • Very little code, about 80 lines.


EDIT: Reddit user geishastudios had some very legitimate questions and wanted me to explain why am I doing things this way, this is my reply:
I needed a mechanism to pull messages vs a push/callback/delegate system so a component can decide when and if is going to process a message. I also needed to be able to skip processing certain messages if other messages where sent. My initial code was using the classic observer pattern with delegates and I ended up with a lot of checks to see what messages were received and was called and what not.

Another reason (and this is probably the main one) is that messages need to be “double-buffered”, basically all messages need to show up at once in the next frame, not partially in the current one, that would cause an event handler to work with an incomplete state since there was still stuff that was going to happen (there will be more messages) after it finished running, or it could itself send messages for components that already should have gotten their messages and they will get called again and I had to account for that. Anyway, it was all getting quite complicated and apparently the way I handling events was the cause. Now, this may say something about my code and the way entities are handling their state but this is my approach and it works pretty well for me.

The switch block is probably not faster but I did not see a performance hit for using it, there may even be a small improvement in performance and memory usage for broadcast events when a large numbers of components need to be notified of something (not really sure I can back this affirmation, it may have also been caused by other changes in the code). Also the switch blocks did not get terribly big in my case, each component gets 4, maybe 5 message types.

Slightly better type checking could be achieved by replacing strings with enums but I was just having too many and also enums do not have inheritance – anyway I ended up using strings.

Hope all this makes some sense.

Here is some code to give a better picture of what I’m talking about:

//the message manager should be globally available
public MessageManager MessageManager { get; private set; }
...
MessageManager = new MessageManager();
...

protected override void Update(GameTime gameTime) {
MessageManager.Update();
...
}

...
//send a message
MessageManager.Send(new Message {
Type = "DoSomething",
Sender = this,
Destination = someGameObject,
Payload = someItem
});

...
//somewhere in someGameObject's code
List messages = new List();
//find messages for someGameObject
MessageManager.FindMessagesByDestination(this, messages);
foreach (var m in messages) {
switch (m.Type) {
case "DoSomething":
DoSomething(m.Payload);
break;
...

Here is the full code of the MessageManager class, very simple stuff as you can see. There are multiple FindMessagesBy* methods (I got a bit into framework writing mode) but I think I’m using only FindMessagesByDestination and FindMessagesBySender in my code. There’s also a FindFutureMessage that I had to add because of an unforeseen need to maintain state, some component needed to know the content of a message that was sent in the current frame instead of waiting its turn next frame, if this happens to you it is probably a good indication you should not be using messages in this situation.

public class MessageManager {
private List lastFrameMessages = new List();
private List currentFrameMessages = new List();

public void Send(Message message) {
currentFrameMessages.Add(message);
}

public void FindMessagesByDestination(object destination, List result) {
for (var i = 0; i < lastFrameMessages.Count; i++) {
var m = lastFrameMessages[i];
if (m.Destination != null && m.Destination.Equals(destination)) {
result.Add(m);
}
}
}

public void FindMessagesBySender(Object sender, List result) {
for (var i = 0; i < lastFrameMessages.Count; i++) {
var m = lastFrameMessages[i];
if (m.Sender.Equals(sender)) {
result.Add(m);
}
}
}

public void FindMessage(Predicate criteria, List result) {
for (int i = 0; i < lastFrameMessages.Count; i++) {
Message m = lastFrameMessages[i];
if (criteria.Invoke(m)) {
result.Add(m);
}
}
}

public void FindMessagesByType(string type, List result) {
for (var i = 0; i < lastFrameMessages.Count; i++) {
var m = lastFrameMessages[i];
if (m.Type.Equals(type)) {
result.Add(m);
}
}
}

public void FindMessagesByTypeAndDestination(string type, object destination, List result) {
FindMessage(type, destination, lastFrameMessages, result);
}

public void FindFutureMessagesByTypeAndDestination(string type, object destination, List result) {
FindMessage(type, destination, currentFrameMessages, result);
}

public void FindMessagesByTypeAndSender(string type, Item sender, List result) {
for (int i = 0; i < lastFrameMessages.Count; i++) {
var m = lastFrameMessages[i];
if (m.Type.Equals(type) && m.Sender.Equals(sender)) {
result.Add(m);
}
}
}

private static void FindMessage(string type, object destination, List frameMessages, List result) {
for (var i = 0; i < frameMessages.Count; i++) {
var m = frameMessages[i];
if (m.Destination != null && m.Type.Equals(type) && m.Destination.Equals(destination)) {
result.Add(m);
}
}
}

public void Update() {
var t = lastFrameMessages;
lastFrameMessages = currentFrameMessages;
currentFrameMessages = t;
currentFrameMessages.Clear();
}
}

public struct Message {
public string Type;
public object Sender;
public object Destination;
public object Payload;

public Message(string type, object sender, object destination, object payload) {
Type = type;
Sender = sender;
Destination = destination;
Payload = payload;
}
}

One of these days I will move to blogger

Maybe … Moved

Some background, I’ve had my Astroboids blog located on a free web host, so far it’s been very convenient, full control, no ads, maybe a little slow but not terrible. The only problem is that this free hosting service seems to be in some kind of Google black hole, the indexing frequency is terrible. I decided to move, here we go again…

Update: I started moving things, the posts before this one are moved from my old host and backdated.

Update2: I finished moving over this year’s stuff, the rest will stay on the old host.

Update3: Already indexed and showing up in searches, hmmm…

A.R.S.S.E – A Real-time Strategy Shooter Experiment

My game used to be called Astroboids, the initial idea involved boids heavily, hence the name. While actually implementing the thing the design has changed. A lot. I kept steering behaviors as part of the game A.I. but the rest had to go – apparently playing a game with herds of boids is not much fun. The name did not make much sense anymore, so this is the new (and maybe temporary) name of my game: A.R.S.S.E A Real-time Strategy Shooter Experiment. I know I know, so many horrible puns, so little time…

To celebrate the name change I also have some game-play footage. The fine music is “slingshot suplex” from tettix.

Also, I noticed that I am pretty bad at playing my own game.