Finite State Machine: How It Has Affected Your Gaming For Over 40 Years
AI is not a new technology, but simply a technology that has finally found a way to overcome its limits and reach its full potential...especially with video games.
Artificial intelligence (AI) is one of the latest tech trends, and it definitely is one of the technologies with the highest revolutionizing power. However, as we’ve probably mentioned so many other times already, AI is not a new technology, but simply a technology that has finally found a way to overcome its limits and reach its full potential.
In fact, one of the fields of computing science where the first more or less rudimentary AI has been used at least since the early ’80s and ’90s is… [ominous suspense music playing in the background] well, just video games.
To tell the truth, we may even claim that the first practical applications of finite state machine (FSM) AI are nearly as old as video games themselves, since even the widely popular “Pac Man” used one of those classic computational models (more on this later).
Nearly all of the games we used to play, and a lot of the modern games we’re still playing use FSM-based AI. It is used not just to generate somewhat credible interactions between the player and the other characters, but to implement other critical elements of game development such as the graphical user interface (GUI), input handling, player controls and progression through the history. (Read How is artificial intelligence used in video games?)
So stay with me and together we’ll drill below the crust to find out how FSM has influenced our gaming experience so far.
But beware! Get ready for high levels of pop-culture nostalgia!
What Is a Finite State Machine?
An FSM is an abstract model of computation that can exist in one state at a time (current state), chosen from a finite selection of values. In other words, each state is unique and mutually exclusive and, therefore, finite. Inputs signal when the machine can switch from the initial state to the next one in a process-defined transition.
Probably the most well-known example is the traffic light. It may be green, yellow or red, but never more than one at a time. When a passerby presses the button (input), it will transition from green to yellow, and then from yellow to red. After some time, it will revert back to green, completing a cycle. (Read How is a finite state machine used in artificial intelligence?)
The result is an incredibly simple but elegant model that provides all the answers needed by most game developers, especially since it is simple enough that it can even be used without programming. Game features can be implemented by diagramming FSMs into direct graphs — a simple and understandable format that could be easily converted again into state tables.
FSMs have been used for decades to model decent AI on resource-limited platforms, such as the early gaming consoles of the ’70s, ’80s and ’90s, as well as the simpler handheld games from that same age such as the Tiger games.
How Are FSMs Used in Video Games?
Probably the most obvious and widely used implementation of FSMs in the video gaming industry is the creation of rudimentary effective AI. A finite state can be used to define certain non-playable character (NPC) behavior, such as attacking, roaming or running. (Read The Most Important Trends in Gaming.)
As we mentioned earlier, FSM was used to control the behavior of Pac Man’s ghosts. They could only have one operating mode at a time, namely hunting, chased, dead, or waiting to be resurrected. In later, more modern games some fuzzy logic was sprinkled on a solid foundation of FSM to add some unpredictability and make characters feel less robotic and stiff.
For example, in stealth-based action games such as the immortal “Commandos,” “Assassin’s Creed” or the popular “Metal Gear” franchise, whenever an enemy detects the player, he will transition from the idle state to the alerted one. After a few seconds, if the player doesn’t hide in a safe spot again, the NPC will start actively searching for him by switching into an aggressive state.
The randomness here can be found only in the enemy paths when they roam around, or their decision to use one weapon rather than the other. That’s FSM AI at its finest, and you can probably find it at the core of even more complex and intelligent behaviors, such as those shown by — but definitely not the sole iteration of — this mathematical model.
FSMs for Interface, UIs and Controls
FSMs are incredibly simple and can be used as the framework supporting all player controls and handling. Think of a platformer game such as “Super Mario Bros. 2.” Your character can either be standing or crouching, but never both of them at the same time.
After the character has been crouching for some time, he or she will transition into the charging state and will start to flash — a particular condition that will increase your jumping height. Similarly, all the various power ups used by Mario in “Super Mario Bros. 3,” such as the Fire Flower, Super Leaf and Starman are nothing but states that activate the main character’s transformations (Fire Mario, Raccoon Mario or Invincible Mario).
This same logic is applied to other form of game states, such as Main Menu, Paused, Loading, Playing and Exiting. Even games that include different game modes such as “Minecraft” that features Survival, Creative, Adventure, Spectator and Hardcore modes use FSM to switch from one mode to the other.
Literally every feature that consists of a fixed state is built through an FSM system. For example, if a game has a weather system (rain, snow, sun, etc.) , day/night cycles, season cycles, above vs. underground states — well, with due probability an FSM is controlling each one of them. Think about all the differences in movement speed, or attack and defense bonuses when you navigate different terrains in the “Heroes of Might & Magic” franchise, or when you move above and below ground in “Age of Wonders 3”.
FSM in Adventure Games and RPGs
FSMs have been a fundamental component of all RPG/adventure games since their earliest inception. For example, they control all sequential dialogues in old-school adventure games such as “The Curse of Monkey Island,” “Rex Nebular and the Cosmic Gender Bender,” or the “Leisure Suit Larry” series. FSMs can also be used to create complex and highly branching storylines.
As the player progresses through the story, he may make different choices that open up a path while closing another one.
Other in-game elements may also be affected by these choices, such as player’s stats, dialog outcomes, and types of enemies encountered, and are usually associated with multiple endings. Early pioneers of this type of nonlinear narrative include big names such as “Chrono Trigger” and “Fallout.”
However, this type of gameplay has survived throughout the years and can be found even in modern story-rich games such as “Mass Effect” and the popular indie game “Undertale.”
What We've Learned
If you’re a tech buff or information technology expert, there’s a really high chance you grew up playing video games a lot. Now that you’ve read this article, you’ve experienced FSM models firsthand. In fact, in addition to enjoying this nostalgia trip, you just switched from the not-knowing state to the enlightened mode!
You will probably need to focus just a few seconds to spot an FSM-controlled feature in nearly all games you played so far, and probably in most games you will play in the future.