Iterator state machines

Iterator state machines

  • Comments 22

In my talk at MIX earlier this year, I mentioned that C# iterators can be useful for building state machines. Some of you asked for more detail about this idea, so, late but not never, here ya go.

Let's say we are building a game with an AI that can choose between five possible actions:

    enum Action
    {
        WalkNorth,
        WalkEast,
        WalkSouth,
        WalkWest,
        RunAway,
    }

(yah I know, the game is likely to be boring if all they can do is walk around or run away, but hey, it's just an example :-)

We will use this base class for all AI controlled entities:

    abstract class Entity
    {
        public abstract Action Think();
    }

 

At periodic intervals the game engine will call the Think method for each entity. The Think implementation chooses what the entity wants to do next, taking into account both its internal state and also its surroundings in the game world. The engine then makes the entity perform the selected action:

    foreach (Entity entity in activeEntities)
    {
        switch (entity.Think())
        {
            case Action.RunAway:
                // TODO
                break;

            case Action.WalkNorth:
                // TODO
                break;

            // etc.
        }
    }

Using this infrastructure, we will examine a specific entity behavior:

  • Walk in a randomly chosen direction
  • Every 10 updates, change to a different randomly chosen direction
  • If you hit a wall, change to a different randomly chosen direction
  • If you see an enemy, run away for the next 30 ticks, then go back to random walking

This would traditionally be implemented using a state machine:

    class Dude : Entity
    {
        // If greater than zero, we should run away for this much more time.
        int runAwayTimer;

        // When this counts down to zero, it is time to change direction.
        int changeDirectionTimer;

        // Which way are we currently walking?
        Action currentDirection;


        override public Action Think()
        {
            // If we see an enemy, flag that we should run away for the next 30 ticks.
            if (IsEnemyInSight)
            {
                runAwayTimer = 30;
            }

            // Are we currently in the running away state?
            if (runAwayTimer > 0)
            {
                runAwayTimer--;
                return Action.RunAway;
            }

            // Change direction if we run into a wall, and also at periodic intervals.
            if (IsCollidingWithWall || --changeDirectionTimer <= 0)
            {
                currentDirection = ChooseRandomDirection();
                changeDirectionTimer = 10;
            }

            return currentDirection;
        }
    }

This works fine, but I do not find the code especially beautiful:

  • I have to read it carefully to understand what it does
  • The control flow is too much about figuring out which state we are currently in, and not enough about transitioning between states (which is really the important part)
  • The control flow looks nothing like the original description of the behavior
  • The class inevitably ends up with fields that are only valid in particular states, but it is not obvious which fields are valid when, how they get initialized, etc.
  • This only gets worse as the behavior becomes more complex...

It would be more readable if I could write a linear sequence of instructions, which would run up until it made a decision, yield control back to the game engine, then resume from its current location the next time the engine asked it to choose an action. That can be implemented using threads or coroutines, but:

  • .NET doesn't provide lightweight coroutines, which are commonly used for such purposes when scripting games in Lua
  • Threads are pretty heavyweight, so it would be excessive to create a separate thread per entity

Instead, we can use a C# iterator method. We write simple linear code, and the C# compiler applies magic to automatically transform it into a state machine object which implements the IEnumerator<T> interface.

First, we will change our Entity base class. We replace the Think method, which returned a single Action enum each time it was called, with a new ThinkIterator method, which returns an IEnumerable<Action> that can be used to choose future actions (fans of functional programming may recognize this pattern as a lazily evaluated infinite sequence):

    abstract class Entity
    {
        protected abstract IEnumerable<Action> ThinkIterator();
    }

We also add some helper code to the Entity base class. We look up and store the ThinkIterator when the entity is constructed, and provide a Think wrapper method that reads the next value of the sequence. This allows the game engine to call Think each time it wants the AI to choose a new action, exactly like it did with our original state machine implementation:

        IEnumerator<Action> thinkEnumerator;

        public Entity()
        {
            thinkEnumerator = ThinkIterator().GetEnumerator();
        }

        public Action Think()
        {
            thinkEnumerator.MoveNext();

            return thinkEnumerator.Current;
        }

Now the fun part. Here is our AI behavior rewritten as an iterator method:

    class Dude : Entity
    {
        override protected IEnumerable<Action> ThinkIterator()
        {
            // Infinite loop.
            while (true)
            {
                // If we see an enemy, run away for 30 ticks.
                if (IsEnemyInSight)
                {
                    for (int i = 0; i < 30; i++)
                    {
                        yield return Action.RunAway;
                    }
                }

                // Otherwise, choose a random direction and walk that way for a while.
                Action direction = ChooseRandomDirection();

                for (int i = 0; i < 10; i++)
                {
                    yield return direction;

                    if (IsCollidingWithWall || IsEnemyInSight)
                        break;
                }
            }
        }
    }

This is less code (29 lines as opposed to 37) and I also find it more logically structured and easier to understand. Sweet!

The "yield return" statement can only be used directly in the body of the iterator method. It cannot call other helper methods which then issue the "yield return" on its behalf. However, you can chain together multiple iterators to build up a library of reusable behaviors, an approach I find quite elegant and flexible. For instance, given this simple iterator which implements an "endlessly walk around the edge of a square" behavior:

    IEnumerable<Action> PatrolAroundSquare()
    {
        while (true)
        {
            for (int i = 0; i < 10; i++)
                yield return Action.WalkNorth;

            for (int i = 0; i < 10; i++)
                yield return Action.WalkEast;
                
            for (int i = 0; i < 10; i++)
                yield return Action.WalkSouth;
                
            for (int i = 0; i < 10; i++)
                yield return Action.WalkWest;
    }

We can build a more sophisticated behavior that combines square walking with enemy avoidance:

    IEnumerable<Action> PatrolUntilAttacked()
    {
        while (true)
        {
            // If we see an enemy, run away for 30 ticks.
            if (IsEnemyInSight)
            {
                for (int i = 0; i < 30; i++)
                {
                    yield return Action.RunAway;
                }
            }

            // Otherwise, chain to the PatrolAroundSquare behavior,
            // but stop doing that as soon as we see an enemy.
            foreach (Action action in PatrolAroundSquare())
            {
                yield return action;

                if (IsEnemyInSight)
                    break;
            }
        }
    }
  • As much as I love using IEnumerable/IEnumerator functions for doing asynchronous things, they're actually a very bad choice for some forms of game AI, because it's extremely difficult to control their behavior from outside, and you end up resorting to nasty hacks when you want to drive the AI from outside. I was using this approach for animation and AI in my game for quite a while until I realized that I had dozens of cases where I was forcefully restarting iterators or changing to other iterators. The alternative to that is not really any better; you end up with iterators that contain dozens of if/switch blocks where they decide whether it's time to switch behaviors, or nested iterators that iterate each other and pass actions up a chain. It ends up being very difficult to debug.

    However, I do find that using them to model *extremely trivial* behaviors is a huge win - things like walking along a path, having a conversation, etc. - because these behaviors have little to no branching, you can easily model them as an iterator and the compiler will do all the work for you.

  • > you end up resorting to nasty hacks when you want to drive the AI from outside

    That's where I like the pattern of layering complex iterators on top of other simpler ones. I don't think changing to other iterators on the fly is a hack at all: it often seems to produce quite nice code if your core worker algorithms are all very simple iterators, then you have what I guess you could call "controller iterators", that basically just delegate to the workers, but with logic to decide when to switch or restart an iterator.

  • This is not what an iterator is for. :-(

  • > This is not what an iterator is for. :-(

    Why not?

    Many of the more interesting C# languages features are really just LISP in disguise.

    Iterators, however, are actually a simplified form of Haskell :-)

  • Given that you are advocating this, I assume you've verified that this produces high-quality compiled code?

  • I didn't realise there were rules for how iterators could be used.

    I think it's this direction which C# is taking which allows developers to say what they're doing more clearly, rather than trying to model a concept as a series of imperative actions, and then having to cope with the cases where the abstraction is leaky.

    However, I would say that perhaps an IEnumerable provided by an iterator isn't the best solution here. I would say that an IObservable is! The entity can react to running into enemies or walls, and push out a new action. Then your app becomes reactive to events, which is what you're trying to model anyway, instead of having to constantly turn the crank to move everything forward one turn, then check everything to see if something's changed.

    I'm afraid that under the Observable hood is still naughty use of Enumerators, though. Bad Enumerator, no biscuit!

  • A while back, I was showing Jace some Lisp code that used functional combinators to create a parser library. The same idea applied to his bullet-hell game behaviors. With a "foreach yield" construct, you could similarly combine iterator-based state machines. Composeable state machines! Here's a little demo app I came up with in Python: code.google.com/.../bulletcombinators

  • I prefer not to use it for AI but instead for "fire & forget" (set of) actions, where all steps must be executed no matter what. Also, is there any penalty for using an IEnumerable return value on an intesive loop, like the Update one?

  • I hate this with a passion. As Tom said: this is not what iterators are for. It's one of those "cool tricks" where you use a feature for something completely counter to its intended function, based on its internal specification. Anyone who doesn't happen to know how iterators get compiled will be baffled by this code. Tricks like these ruin programming languages. C# needs to either get proper coroutine support or not bother at all.

    Apologies for the hate :)

  • Pretty neat trick. It does produce some very nice and readable code. How does it look once compiled? No GC problems from allocating iterators? I do wish it was less of a language hack though. Built in Coroutine support in C# would be awesome.

  • If you're worried about codegen quality, look at the resulting code in Reflector to see exactly what the compiler is doing.

    Iterators are generally pretty efficient, but they do require a couple of extra internal worker objects.

  • Yeesh. Why are people so up in arms for thinking outside the box? Isn't that what 90% of game programming is anyways?

  • Howdy,

    I thank you for taking the time to example this farther. In the time since your mix demo I have put some time in researching what this can be used for and found that for some types of AI this becomes very hard to manage and control. Although for others (RPG in particular) this approach worked great. It let me design be small behaviors that can be reused and composed to build complex behaviors.

    I have also played with IObservable in this process and it works equal as well for reactive behaviors. Now making these two play nice was a little tricky but I believe the resulting code is far simpler to understand then the large complex state machines I would have hand to build to create the same behavior.

    And I must say that non-programmers seem to get this more than state machines. To the point where my level designer (who had only written flash game before this) can comfortably write behaviors for Actors in the level.

  • Hmm, it always generates classes, huh? Are iterators normally used in such a way that garbage generation is fine? I'm rather partial to structs whenever it's feasible to use them instead, especially in enumerators.

  • > If you're worried about codegen quality, look at the resulting code in Reflector to see exactly what the compiler is doing.

    I know it does transform it into a state machine, but aren't you generating garbage by using IEnumerator<Action>?

Page 1 of 2 (22 items) 12
Leave a Comment
  • Please add 8 and 1 and type the answer here:
  • Post