Finite State Machines in Game Development

[Dienes]

So I have lately been thinking about re-doing a game I started some time back ([URL="http://facepunch.com/showthread.php?t=1109571"]Mors Cerebri[/URL]), because the code became rather messy to work with.

I've been reading/watching stuff on the web about Finite State Machines and how they are extensively used in game development, but I just can't wrap my head around it at all. I understand the basics that any given system can be in certain states and transition between them, but when I think about implementing it in the game, I just don't know how to do it.

The game originally had a state stack for handling the different screens, like main menu, game itself, pause screen, etc. I had all states derive from a base state and be singletons, having references to them on the stack which is processed/rendered top to bottom. It worked, but I had for example no idea how to implement transitions between those screens. Fading out the gameplay state when the pause screen overlayed was pretty difficult and resulted in hackish code. I somehow needed substates, so the game state could be in some sort of fade-out substate or something (which I assume is a transition in a FSM?).

Now, when I want to implement all sorts of things with state machines, like the AI, menues, inventory system, etc. it seems to me that I will end up with a huge amount of nested state machines with hundrets of state classes that somehow do stuff. It just overwhelms me.

Has anyone of you some experience in the correct usage of FSMs in game development? Or are there good resources for exactly this problem and how to design your code base accordingly?

Thanks for any input on this topic.

[Tamschi]

You should use infinite substates for the transitions :v:

The finite state stuff isn't really rigid, it's just a tool to handle coroutine style behaviour (which is needed a lot because of independent entities). Look at C#'s iterators or async methods for examples.

The screen stack shouldn't really be a rigid FSM imo, you could program it more like a display manager instead, so that you can dynamically insert screens and have them call methods to be shown, letting the screen manager route input accordingly. When two screens are shown at once, you can render them to framebuffers to composite them afterwards, making transitions much easier.

Your game state and most of the screens are about as much FSMs as a computer is: only technically due to not being infinitely precise. Writing a game completely as FSM would be terribly inefficient, because it's a really bad fit for most large systems (but an extremely good one for certain small ones).

If you're trying to use a finite state machine for something more complex than the current goal of a single AI you're doing it fundamentally wrong.

[editline]27th July 2013[/editline]

Also, making states classes probably isn't the best way to do this, usually it's just an integer or enum value and a switch statement in the step method.

[Dienes]

Interesting. On the web you find a lot of writings and youtube stuff where the (hobby) developers are like "everything here is a state machine, yeah, the gun, each enemy, the tree over there" and it [I]kind of[/I] made sense to me.

The precision thing really is something I didn't understand. Many tutorials give examples like "the enemy is in roaming state, then the event of spotting the player transitions it to attacking". But this sounds to me like a very very high-level description of how an enemy acts and is not a base for an implementation. What if the enemy is following and attacking me at the same time? Can it be in two states? What does "attacking state" actually mean, how do I know if the enemy is about to fire his gun, has fired his gun, started reloading, is reloading, finished reloading, etc.? You'd literally have to subdivide the states infinitely.

So what is the alternative? How do I keep track of alle the states some entity can be in, and what it triggers when changing its state? Having lots of bools and switch statements with enums is something I wanted to avoid.

[Tamschi]

[QUOTE=Dienes;41612715]Interesting. On the web you find a lot of writings and youtube stuff where the (hobby) developers are like "everything here is a state machine, yeah, the gun, each enemy, the tree over there" and it [I]kind of[/I] made sense to me.

The precision thing really is something I didn't understand. Many tutorials give examples like "the enemy is in roaming state, then the event of spotting the player transitions it to attacking". But this sounds to me like a very very high-level description of how an enemy acts and is not a base for an implementation. What if the enemy is following and attacking me at the same time? Can it be in two states? What does "attacking state" actually mean, how do I know if the enemy is about to fire his gun, has fired his gun, started reloading, is reloading, finished reloading, etc.? You'd literally have to subdivide the states infinitely.

So what is the alternative? How do I keep track of alle the states some entity can be in, and what it triggers when changing its state? Having lots of bools and switch statements with enums is something I wanted to avoid.[/QUOTE]

These very-high-level descriptions are the right application for FSMs, from that subroutines are called that actually implement the actions or change the state.
For example an enemy's AI could have two states: unaware and aware. While it's unaware, it runs code to, for example wander around and checks if there's a target. If a target is found, it's stored somewhere and the system transitions into the aware/chasing state. In that state, the behaviour function moves towards the stored target, if it's out of range it's removed and the state is set to unaware again.

A real AI would probably have more states, but not everything has to be on the same level: If you don't need other parts of the program to be aware that the entity is currently "attacking", it could be enough to call an asynchronous (not parallel!) method and suspend the current state machine until that's finished.

You can write state machines implicitly in C# with async methods, they are rewritten into a state machine during compilation. Each suspension site becomes a state, and the method continues depending on where it was suspended previously. The feature uses duck-typing, so it's easy to perfectly integrate into a game loop. (The awaiters can be empty structs that just register a continuation with the right game event, for example.)

I don't know if C++ has the feature built-in, but I would be very surprised if this didn't already exist as library somewhere. You could also create the state machines dynamically, the important part is saving the local state (C# rewrites locals as fields of the state machine to achieve this). Search for "coroutine", that's the name of the untransformed state machine method.

[editline]27th July 2013[/editline]

If you want to have enemies take two actions at the same time, you can either attach two controllers (one for movement, one for interaction, for example, the visuals just have to handle the independent states then), or you could call two coroutines at the same time and await them, if the simultaneous actions are part of a larger script. You could also call a "follow this entity indefinitely" routine with a cancellation token (can be just a bool*), then call and await the attack, then cancel and await the following method.

Edit: I'll write a bit of pseudocode to explain this better.

[editline]27th July 2013[/editline]

async void AILoop()
{
  while (true)
  {
    target = await WaitForEnemy()
    if (cancel) break
    await MoveTo(target)
    bool cancelFollow = false
    followAwaitable = Follow(target, ref cancelFollow)
    await Attack(target)
    cancelFollow = true
    await followAwaitable
  }
}

async void Follow(Ent target, ref bool cancel)
{
  while (cancel == false)
  {
    await MoveStepTowards(target)
  }
}

"async" is the marker for a state machine method, "await" marks a suspension site that is reactivated by a call from the awaitable value (ideally without increasing stack depth, that could be bad with all these loops)

The calls to the engine throw an exception with this model if the entity is not valid (but not if the target was unavailable or it's caught, because a missed attack shouldn't freeze the AI), then the GC/RAII and shared_ptr should clean up the state machines.

[editline]27th July 2013[/editline]

Attack could be something like that:

async void Attack(Ent target)
{
  await Animate(this, attackAnimation)
  target.Damage(12) //instantaneous, queues effects
}

Basically, you can break down the coroutines just like normal methods to reuse code, then make certain things calls to non-async methods, with instantaneous things as normal method calls and yields (wait for the next frame, wait a second, wait for a trigger) as awaitable methods that add the continuation as subscribers for an event or something like that.

It's also important to call the continuations if the trigger has already taken place, possibly just by immediately calling the queued up delegate.

[Dienes]

Thanks for all the effort you put into your answer.
This this async/await feature in .NET looks interesting, I'll check if there are C++ libs available that mimic it. I guess this would be an elegant way to solve the problem of "have the logic wait for the visuals".

So the bottom line would be to use states where appropriate, don't make them too granular and it's okay to have switch statements instead of classes all over the place.