Your games don't need State Machine

Introduction

Today I will finally tell you why game AI based on the State Machine (or simply SM) is a lazy imitation of AI and should not see the light of day in any non-pet project.

My name is still Misha, I have been programming for more than 7 years, for the last year I have been closely involved in gaming artificial intelligence, implementing it in all possible variations. I also managed to see a lot of shitty code with state machines, where it could have been avoided quite simply. Also, of course, I lead telegram channelwhere I talk even more about development, a career in game development and warm up to mentoring.

Why not?

Of course, you can always say “yes, my behavior is very basic, there’s no need to go crazy with AI frameworks” or “my genre is Idle, where mobs just perform a sequence of actions.” But let's remember the life cycle of almost any game. Yes, we do core features first, only the main set of actions for mobs. But how long does this last? How long until our idle mobs begin to change their behavior on the fly. For example, when they can’t do something or when they just want to be happy about the advertisement they watched?

At such moments we realize how lazy we were in choosing a state machine. After all, it has a quadratic complexity of increasing the number of behaviors. And let’s all remember together that the graph for states in our state machines is oriented and multiply the number by 2. That is, 2 states – 2 arrows between them, 5 states – 20 arrows, 12 → 132 and so on.

Staying in the comfort zone

Of course, we all follow the great mantra “if it works, don’t touch it!” Therefore, no matter how hard this state machine shoots us in the legs, we stay with it until the victorious (sometimes) end.

The second stage is usually “acceptance” or as we call it “writing crutches”. That is, to deal with the quadratic complexity of adding new behavior, programmers use one of three crutches or all of them together.

Let's consider them using the example of an NPC or a conditional RPG game. Our mob can do some actions like: communicate with the main character, go to work, eat, sleep, fight.

Any State. This blue square in the animator is familiar to any unit developer. By drawing an arrow from it, we show that you can move to this state from any other. In order not to draw 20 arrows to the 10th state, we will draw 10, and draw the eleventh from Any state. And everything is fine until we decide that from some state we still don’t want to move into this new one…
Speaking of our NPC. We want to add a separate state for death (maybe we finally forked out for an animation not from Mixamo and want to show off it). We decide “well, he can die at any time, so we can make a transition from any state. Everything is great, except that the NPC gave the hero a quest during the dialogue, and now during the chat he can die and end the story arc 10 hours earlier. Therefore, you still have to draw 10 more arrows.
Hierarchical state machine (HSM). Some people are also familiar with it from the animator as a “nested state machine”. If some of the states are equally connected with the rest of the state machine, then it is quite reasonable to separate it into its own internal SM. Thus, out of 90 arrows, we can remove roughly half. But everything again goes to one place, when some of these states still have to work differently with the external state machine…
Let's return to the NPCs. We decide that all his peaceful activities (eating, sleeping, chatting) are worthy of being kept apart from his fighting skills. We remove them separately and look at the improved state graph… Oh yes, he still gives the story quest, but instead of dialogue he ran off to fight… Then unpack it back and draw 40 arrows back…
Layers.
– You see, state cars are like onions
– Do they stink? Bringing you to tears?
– No, layers. Onions have layers and state machines have layers.
Like if you recognize the reference))
If some action can be performed independently of some of the others, then it can be placed in a separate layer. At its core, this is the same state machine, working in parallel, but in the same external context. It looks at the same data and changes states based on the same triggers as the main SM. But in the same way, everything is nothing as long as its parallelism is absolute. Which is usually not the case…
The game designer played Skyrim and decided that our NPC could also talk during some actions. For example, he can do this while sitting at a table. We create a separate layer for the state machine, which contains only communication states. But the character cannot leave the table while he is talking. Especially when he gives you a story quest. And he can’t always talk. What do we have to do then? Still indirectly connecting our state machines. The communication state must know exactly what is going on in the rest of the character's logic. And she, in turn, must wait until the head finishes. In the end, it's even worse than other crutches. Not only are we wasting our time trying to optimize behavior, but we are also hiding state dependencies inside the player context itself.

PS, initially the examples could have been more varied, but I liked how one pathetic story quest spoils absolutely the entire state machine. It turns out to be a very destructive plot)

We are afraid and put our tail between our legs

In fact, most of the time this problem stems from lack of education or laziness. Someone is either afraid or lazy to look at the world around them and the alternatives it offers, or they are afraid to lose when implementing more serious approaches.

And you don’t have to look far to understand the main alternative to our state machine – the Behavior Tree. What is by default in Unreal and what was used as an alternative to the state machine that burns itself. That's what made the Halo series' opponents an example to other game makers.

Let's look at the “features” that it offers out of the box. Please note, FROM UNDER THE BOX, for this you do not need to wrap the owl on the globe as we did with the NPC:

Nesting (it's called a tree for a reason)
Global transitions between states, as a consequence of this
Parallel execution of states

Of course, we can’t forget about Utility AI. It is more suitable in the case when there are many states and we do not want to build connections between them (remember The Sims). Although a whole separate article is devoted to the choice between approaches to writing AI.

Bottom line

Don't be afraid to step out of your comfort zone and look for new solutions to standard problems! AND NEVER USE THE STATE MACHINE FOR GAME AI!!! And of course subscribe to my channel and contact for mentoringif you still haven’t found a job in game development) Thank you!