Advertisement
  1. Game Development
  2. Programming
Gamedevelopment

Finite-State Machines: Squad Pattern Using Steering Behaviors

by
Difficulty:IntermediateLength:LongLanguages:

Finite-state machines and steering behaviors are a perfect match: their dynamic nature allows the combination of simple states and forces to create complex behavior patterns. In this tutorial, you'll learn how to code a squad pattern using a stack-based finite-state machine combined with steering behaviors.

All FSM icons made by Lorc and available on http://game-icons.net. Assets in the demo: Top/Down Shoot 'Em Up Spritesheet by takomogames and Alien Breed (esque) Top-Down Tilesheet by SpicyPixel.

Note: Although this tutorial is written using AS3 and Flash, you should be able to use the same techniques and concepts in almost any game development environment.


Final Result

After completing this tutorial, you will be able to implement a squad pattern in which a group of soldiers will follow the leader, hunting down enemies and looting items:


Squad pattern implemented with stack-based FSM and steering behaviors. Move the mouse cursor to guide the leader and click to shoot.

Combining Stack-Based FSM and Steering Behaviors

The previous tutorial about finite-state machines described how useful they are for implementing artificial intelligence logic: instead of writing a very complex pile of AI code, the logic can be spread across a set of simple states, each one performing very specific tasks, like running away from an enemy.

The combination of states results in a sophisticated AI, yet easy to understand, tweak and maintain. That structure is also one of the pillars behind steering behaviors: the combination of simple forces to create complex patterns.

That's why FSMs and steering behaviors make a great combination. The states can be used to control which forces will act upon a character, improving the already powerful set of patterns that can be created using steering behaviors.


Controlling Behaviors Using a Stack-Based FSM

In order to organize all behaviors, they will be spread over the states. Each state will generate a specific behavior force, or a set of them, like seek, flee, and collision avoidance.

When a particular state is active, only its resulting force will be applied to the character, making it behave accordingly. For example, if the currently active state is runAway and its forces are a combination of flee and collision avoidance, the character will flee a place while avoiding any obstacle.

Steering forces are calculated every game update, and then added to the character's velocity vector. As a consequence, when the active state changes (and with it the movement pattern), the character will smoothly transition to the new pattern as the new forces are added after every update.

The dynamic nature of steering behaviors ensures this fluid transition; the states just coordinate which steering forces are active at any given time.


The Code Structure

The structure to implement a squad pattern will encapsulate FSMs and steering behaviors within properties of a class. Any class representing an entity that moves or is otherwise influenced by steering forces will have a property called boid, which is an instance of the Boid class:

The Boid class was used in the steering behavior series and it provides properties as velocity and position (both math vectors), along with methods to add steering forces, such as seek(), flee(), etc.

An entity that uses a stack-based FSM will have the same structure of the Ant class from the previous FSM tutorial: the stack-based FSM is managed by the brain property and every state is implemented as a method.

Below is the Soldier class, which has steering behavior and FSM capabilities:


Planning the "Brain"

The squad pattern will be implemented using a stack-based finite-state machine. The soldiers, which are the members of the squad, will follow the leader (controlled by the player), hunting down any nearby enemies.

When an enemy dies, it might drop an item that can be good or bad (a medkit or a badkit, respectively). A soldier will break the squad formation and collect nearby good items, or will evade the place to avoid any bad items.

Below is a graphical representation of the stack-based FSM controlling the soldier's "brain":


FSM representing the brain of a soldier.

The next sections present the implementation of every state. All code snippets in this tutorial describe the main idea of every step, omitting all the specifics regarding the game engine used (Flixel, in this case).


Following the Leader

The first state to be implemented is the one that will remain active almost all the time: follow the leader. The looting part will be implemented later, so for now the follow state will only make the soldier follow the leader, switching the current state to hunt if there is an enemy nearby:

Despite the presence of enemies, while the state is active it will always generate a force to follow the leader, using the leader following behavior.

If getNearestEnemy() returns something, it means there is an enemy around. In that case, the hunt state is pushed into the stack through the call brain.pushState(hunt), making the soldier stop following the leader and start hunting enemies.

For now, the implementation of the hunt() state can just pop itself from stack, that way the soldiers won't be stuck at the hunting state:

Note that no information is passed to the hunt state, such as who is the nearest enemy. That information must be collected by the hunt state itself, because it determines whether the hunt should remain active or pop itself from the stack (returning the control to the follow state).

The result so far is a squad of soldiers following the leader (note that the soldiers will not hunt because the hunt() method just pops itself):


Squad pattern with "follow" and non-functioning "hunt" states. Move the mouse cursor to guide the leader and click to shoot.

Tip: every state should be responsible for ending its existence by popping itself from the stack.


Breaking Formation and Hunting

The next state to be implemented is hunt, which will make soldiers hunt down any nearby enemy. The code for hunt() is:

The state begins by assigning aNearestEnemy with the nearest enemy. If aNearestEnemy is null it means there is no enemy around, so the state must end. The call brain.popState() pops the hunt state, switching the soldier to the next state in the stack.

If aNearestEnemy is not null, it means there is an enemy to be hunted down and the state should remain active. The hunting algorithm is based on the distance between the soldier and the enemy: if the distance is greater than 80, the soldier will seek the enemy's position; if the distance is less than 80, the soldier will face the enemy and shoot while standing still.

Since hunt() will be invoked every game update, if an enemy is around then the soldier will seek or shoot that enemy. The decision to move or shoot is dynamically controlled by the distance between the soldier and the enemy.

The result is a squad of soldiers able to follow the leader and hunt down nearby enemies:


Squad pattern with "follow" and "hunt". Move the mouse cursor to guide the leader and click to shoot.

Looting and Running Away

Every time an enemy is killed, it might drop an item. The soldier must collect the item if it's a good one, or flee the item if it's bad. That behavior is represented by two states in the previously described FSM:


FSM highlighting the collectItem and runAway states.

The collectItem state will make a soldier arrive at the dropped item, while the runAway state will make the soldier flee the bad item's location. Both states are almost identical, the only difference is the arrival or flee force:

Here an optimization about the transitions comes in handy. The code to transition from the follow state to the collectItem or the runAway states is the same: check whether there is an item nearby, then push the new state.

The state to be pushed depends on the item's type. As a consequence the transition to collectItem or runAway can be implemented as a single method, named checkItemsNearby():

This method checks the nearest item. If it's a good one, the collectItem state is pushed into the brain; if it's a bad one, the runAway state is pushed. If there is no item to collect, the method does nothing.

That optimization allows the use of checkItemsNearby() to control the transition from any state to collectItem or runAway. According to the soldier FSM, that transition exists in two states: follow and hunt.

Their implementation can be slightly changed to accommodate that new transition:

While following the leader, a soldier will check for nearby items. When hunting down an enemy, a soldier will also check for nearby items.

The result is the demo below. Note that a soldier will try to collect or evade an item any time there is one nearby, even though there are enemies to hunt and the leader to follow.


Squad pattern with "follow", "hunt", "collectItem" and "runAway". Move the mouse cursor to guide the leader and click to shoot.

Prioritizing States and Transitions

An important aspect regarding states and transitions is the priority among them. Depending on the line where a transition is placed within a state's implementation, the priority of that transition changes.

Using the follow state and the transition made by checkItemsNearby() as an example, take a look at the following implementation:

That version of follow() will make a soldier switch to collectItem or runAway before checking whether there is an enemy around. As a consequence, the soldier will collect (or flee from) an item even when there are enemies around that should be hunted down by the hunt state.

Here's another implementation:

That version of follow() will make a soldier switch to collectItem or runAway only after he finds out that there are no enemies to kill.

The current implementation of follow(), hunt() and collectItem() suffer from priority issues. The soldier will try to collect an item even when there are more important things to do. In order to fix that, a few tweaks are needed.

Regarding the follow state, the code can be updated to:

(follow() with priorities)

The hunt state must be changed to:

Finally, the collectItem state must be changed to abort any looting if there is an enemy around:

The result of all those changes is the demo from the beginning of the tutorial:


Squad pattern implemented with stack-based FSM and steering behaviors. Move the mouse cursor to guide the leader and click to shoot.

Conclusion

In this tutorial, you learned how to code a squad pattern where a group of soldiers will follow a leader, hunting down and looting nearby enemies. The AI is implemented using a stack-based FSM combined with several steering behaviors.

As demonstrated, finite-state machines and steering behaviors are a powerful combination and a great match. Spreading the logic over the FSM states, it's possible to dynamically select which steering forces will act upon a character, allowing the creation of complex AI patterns.

Combine the steering behaviors you already know with FSMs and create new and outstanding patterns!

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.