Finite State Machines and ... Miniatures Gaming?

A word of warning: this blog is basically my way of thinking through ideas, even unfinished ones. I find that I do better writing things down rather than just sitting there pondering, and hoping I remember the good bits later. I hope you will bear with me as I sort through my thoughts and hopefully you will find something of interest and use.

The first AI technique discussed in Programming Game AI By Example (see last blog entry for the reference to this book) is a classic: finite state machines (FSM). In the words of the author, the definition of an FSM is:

A finite state machine is a device, or a model of a device, which has a finite number of states it can be in at any given time and can operate on input to either make transitions from one state to another or to cause an output or action to take place. A finite state machine can only be in one state at any moment in time.

The idea being using an FSM is to decompose an object's behavior (in our case, a unit's behavior) into manageable  states. A simple example provided in the book is probably one most of us can understand, that of the "ghost" in the video game Pac Man. The normal state of the ghost is to "chase Pac Man". However, when Pac Man eats the power pill, the ghost switches from "chase" to "evade". The ghost reverts back to chase mode once the timer runs down and the power pill wears off. The rules for the ghost might look something like this:

rule: if in 'Chase Mode' and 'Power Pill Active'
    then switch to 'Evade Mode'
    else continue 'Chase Mode'

rule: if in 'Evade Mode' and not 'Power Pill Active'
    then switch to 'Chase Mode'
    else continue 'Evade Mode'

The same sort of behavior can be encapsulated for units in a game. This is essentially what I was referring to when I discussed creating and using programmed opponents on this blog. What makes a FSM "better" than the rule-based approach I discussed previously is a matter of organization. The rule base mechanic simply lists a set of rules to follow, in a strict order, and to stop evaluating the rules once you find a rule that applies. What makes developing this rule base complex is setting the evaluation order of the rules. It is not usually impossible to determine the correct order, but sometimes it gets so complex that the gamer decides to forego the whole process and just "play each side to the best of my ability", which after awhile can get pretty stale and predictable.

Put another way, a single rule base evaluates a set of conditions in a strict order. An FSM allows you to evaluate conditions in order based upon the state you are currently in. You can essentially have a set of rules associated with every state.

Sample Game

Okay, enough of the theoretical; you can get that from any book. Let's make this concrete. The image to the right shows the start of a skirmish game. The red player (you) have four units: two Warriors (the groups of eight red circles, on the flanks), one Bodyguard unit (the four red circles in the center), and the Warlord (the large red circle in the center). The blue player (represented by a non-player general) also has four units, but they are Warriors (group of eight blue circles on the left), Levy (group of 12 light blue circles in the center, on the hill), the Bodyguard (four dark blue circles on the right), and the Warlord (large blue-in-white circle on the right).

The player's side is oriented towards melee. In fact, all four units have no missile weapons. The non-player side is oriented towards shooting; all four units have missile and melee weapons, but are weaker in melee than their red counter-parts. The basic blue battle plan is to:

• Use the Levy and Bodyguard to fire upon and weaken the opposite red unit.
• When the red unit has been weakened sufficiently, the Bodyguard will charge in with the Warlord and finish it off.
• The Warrior unit will skirmish with the red units, attempting to engage them sufficiently so they do not go support their unit being attacked by the Levy and Bodyguard, but not so heavily engaged that they become overwhelmed.

For now, I am going to ignore the orders of the Levy and Bodyguard and simply focus on the Warriors. Basically, their mission is to tie up one, and hopefully, to three units. There are three basic states (although this may depend upon the rules you use):

• Neither in missile or melee range.
• In missile range.
• In melee range.

There are all sorts of variations or "sub-states", if you prefer to call them that, but I like to think more in terms of conditions. Rather than having a state for "in missile range of the Warriors" and another for "in missile range of the Bodyguard" and maybe yet another for "in missile range of the Warriors and Bodyguard", etc. I simply treat it as the state "in missile range", with conditions indicating which units that applies to. I can then have rules that list the preferable target in order of precedence.

Range Bands

One thing to note about these example states is that you can visualize them as range bands. Consider a unit that moves 6" and has a missile range of 6". The opponent has a movement of 6" also. Technically, if you are in the Melee band, you are also within the Missile and Move bands. This helps us understand that we need to set an precedence order for checking which band, and thus which state we are (or should be) in: Melee, then Missile, then Move.

So, let's think about this, We start the game in the Move band, i.e. outside of both melee (6" move) and missile (6" move plus 6" shoot) range. The first condition to check is whether the enemy moved and we are now at a different range. To keep it simple (for now), let's assume we have the first move, and the situation is as indicated in the map above.

My basic program is to move towards the closest enemy and get into a position where the unit can fire its missiles, and if possible, move back. If the enemy approaches, the unit is to back off, firing missiles as it retreats. (Note: the basic reason for firing then retreating is because the unit's missile range is 6", the same as the movement distance of the enemy. That means if the unit moves forward to fire, it put itself into Melee range automatically. Thus it wants to back out of Melee range before the enemy unit can react. Your rules may not allow such a maneuver, thus this model will not work for you. The rules I will be testing this with, Saga, do allow this sort of behavior.) One other point might be that where the unit can either move and fire at either the Warriors or Bodyguards unit, it will choose the more valuable unit, the Bodyguards.

As the rules I will be testing this with is Saga, for those unfamiliar with the rules here are the basics you need to know:

• Each turn the player gets a certain number of dice to roll.
• Each die rolled indicates what abilities the player can activate during the turn, which includes ordering a unit to take a single action.
• A unit can be ordered to take more than one action per turn by committing more dice to that unit.
• The more actions a unit takes in a single turn, the more fatigued the unit becomes.
• When a unit takes enough fatigue, it is exhausted, and it may not move or shoot until it has rested sufficiently.

This last point brings out another state required in our model: Exhausted. If a unit is exhausted, it can do nothing else before resting. This state will take priority over Melee, Missile, or Move.

Back to our Warrior unit. An ideal turn would be to move forward into missile range (6"), shoot at the enemy, and then retreat back out of the enemy's Melee range (6"), for a total of three actions. As this sequence causes fatigue, a fourth action for resting would make this a truly ideal turn. I can tell you now that committing four actions to a single unit is excessive in most Saga games, so we need to look at the next best option, which is move in, shoot, and move back in one turn, and rest on the alternate turn.

If we put all this into an ordered rule base it might look like:

State: Exhausted

rule: ...

State: In Melee Band (within any enemy unit's movement distance)

rule: ...

State: In Missile Band (movement distance + missile range to an enemy unit)

rule: if not overly fatigued
    then move forward into missile range, shoot the enemy, and retreat out of the enemy's melee range

rule: if overly fatigued
    then rest

State: In Move Band (farther than Melee and Missile bands)

rule: ...

This now covers the basic program of the unit for harassing the enemy with missile fire. We still do not have specifics about how the unit approaches or retreats, or if it fires at the enemy in any specific way (for example, to attempt to kill off a special character like a leader), but we have the basics on how it should act.

As I indicated in the articles on Battle Card Systems and Hand Management, rule bases should be built up over time, rather than trying to do it all up front, at once. I will close this out for now and try and write up the skeleton for the programmed units for this scenario (i.e. all four units) and post them. Maybe then someone else can take them up and play a game with them and provide a critique.