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:
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:
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:
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;
}
}
}