FUNDAMENTALS OF GAME DESIGN, SECOND EDITION

Hierarchical Finite State Machines

In the absence of orders, go find something and kill it.

—Erwin Rommel

Hierarchical finite state machines have proven to be the most successful mechanism for creating artificially intelligent opponents in war games because they can handle large numbers of units and produce seemingly intelligent, coordinated behavior.

WHAT IS A FINITE STATE MACHINE?

A finite state machine (FSM) is a conceptual machine rather than a real piece of mechanical engineering. Its rules establish a simple behavioral system for an indi­vidual automated character, such as a unit in a war game. The unit can inhabit a limited number of states (such as scouting, guarding, pursuing, and retreating), and it's only ever in one state at a time. As long as the unit is in a given state, it per­forms a particular activity. Certain events cause it to make a transition to a new state, after which it starts performing a new activity. Here's an example from real life.

In 1960, researchers at Johns Hopkins University built a little robot called the Hopkins Beast. The only thing the robot did was wander around the computing laboratory. When its batteries got low, it would start to search for an electrical out­let with its photocell eye. (Electrical outlets were the only object that it could recognize.) If it found an outlet, it would plug itself in until its batteries recharged. Then it would set off wandering again. So the Hopkins Beast possessed only three possible states: wandering, searching, and recharging. Its initial state was always wandering. The only thing that would cause a transition to searching was a low battery. When it detected that its battery was low, it would transition to the search­ing state, turn on its eye, and continue to move through the halls. Once it detected an outlet, it would transition to the recharging state and plug itself in. Once it detected that it was charged up, the Beast would transition back to the wandering state. It would unplug itself and start wandering again.

The Hopkins Beast was extremely simple, but you get the idea. You can use FSMs to define the behavior of units. One state should be a default for that unit type—nor - mally, holding its current position or patrolling (General Rommel's advice notwith­standing). For each state that you define, you must indicate how the unit behaves in that state and list all the things that will cause it to transition to a new state. FSMs have a weakness in that they can't walk and chew gum at the same time—that is, they can only be in one state at a time, so a single individual can't work on two things at once. However, the units in war games seldom need to do this anyway.

For more information about designing FSMs, read the chapter "Fundamental AI Technologies" in Core Techniques and Algorithms in Game Programming by Daniel Sanchez-Crespo Dalmau (Dalmau, 2004). Although it is a book on programming the text is very accessible to non-programmers.

HIERARCHICAL FINITE STATE MACHINES IN GAMES

A hierarchical finite state machine (hFSM) actually consists of several different FSMs, and the ones higher up in the hierarchy give orders to the ones lower down—that is, the controlling hFSMs send signals to those lower down in the hier­archy, ordering them to change states. An artificially intelligent opponent in such a system chooses a top-level goal, such as "take and hold this hill," and delegates the tasks required to achieve the overall goal to subordinate FSMs that further delegate down to the individual unit level.

This is the way commands move down through a real army. The captain decides that he needs to take a hill and so delegates different activities to different platoons under him: providing covering fire, creating a diversion, and so on. If done properly, the platoons each have a different goal and won't get in each others' way. The sergeant in each platoon then commands his individual men to achieve the platoon's goal in the same way that the captain commanded the sergeants. Each of the men then tries to achieve his own goal by executing the command he has been given. In a video game, each man has his own FSM that determines his behavior. The FSM reacts to changing conditions on the battlefield (for example, "The unit I was told to attack is dead, so I will look for another one to attack") and also to orders received from the superior FSM, that is, the sergeant's FSM that governs the platoon as a whole (for example, "Your mission is accomplished, so cease fire and guard your position").

The nice thing about hFSMs is that they produce emergent behavior—that is, they may cause units to behave in ways that are not explicitly programmed into the rules. hFSMs also allow you to design the AI from the top down, creating large - scale strategies that are made up of individual smaller-scale strategies. hFSMs are not restricted to combat, either: You can also use them to achieve economic goals, directing worker units to produce different resources as needed and telling them to stop when they've stockpiled enough.

You may be tempted to try to create large-scale AI systems that coordinate the movements of individual units right from the top—a sort of micromanagement. Don't do this; the result will be as unwieldy in your game as it would be in real life if a general tried to tell each individual soldier what to do. Create intelligent behaviors for each level of the hier­archy, and intelligent results will emerge.