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;
            }
        }
    }
  • I don't see why some people here are claiming that this is not what iterators are for. Iterators provide an interface to iterate over a sequence, without regard to the implementation of the sequence. In this case, the sequence is a list of actions for our game agent. Sounds pretty natural to me. The only possibly unintuitive aspect of it is that we aren't using the iterator in a foreach loop, but that hardly makes it unnatural.

  • re. memory allocations: there will typically be one object allocation when you create a new enumerator, but once created, iterating through the sequence does not allocate anything (unless your own code itself allocates, of course)

  • If you think this is not what iterators/enumerators are for, have a look at Rx and you'll probably be horrified. Not every game/program is a sequence of foreach loops...

  • May it is easier to handle this in a event messeging system? This also would do a very simple network communication by just transmitting those messages.

  • I just love this technique and have been using it for years now.

    A challenge for the proposed example: How would you implement this technique if the Think method on the agent had to work with the current game time?

    Intuitively one would maybe come up with the following signature: IEnumerable<Action> Think(GameTime gameTime)

    However, since GameTime has a new value each frame, it actually makes things much more complicated. I'm yet to find a clean implementation for this scenario, which is a pity since it would obviously be of interest. It's possible to do it, but it's not pretty...

  • Chance: as long as the object you pass into the Think method is a reference type, you can change its members while the iterator is running. So you could pass in a ThinkContext object, which contains a GameTime, WorldState, PlayerInputs, CollisionSkin, etc, whatever the AI needs access to, then modify these fields on that single ThinkContext instance before each call to the enumerator MoveNext.

  • There are a few subtle differences between the state machine and the iterator method.  The iterator method calls RunAway 30 times from when the enemy is FIRST seen, the state machine will call RunAway 30 times counting from just before the enemy disappears from sight.  After the state machine stops running away, it continues moving as it was before the enemy was spotted, while the iterator picks a new random direction immediately.

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