| A NOTE FROM THE EDITOR |
| ARTICLE -- FINITE STATE MACHINES FOR FIGHTING GAME DESIGN -- PART 1 |
| Finite
State Machines are the basis for many games, especially fighting games.
This is a snippet from the M.U.G.E.N. documentation:
"A finite state machine (henceforth abbreviated FSM) is an automaton with a finite set of subroutines, each of which performs some function and then employs some criterion to choose the next subroutine to jump to. Each subroutine is called a "state", and the FSM is said to be in a given state when it is currently processing the directives in that state. A FSM can only be in one state at any given time." "The following is a trivial example of a FSM, given in pseudocode." State 0: 1. Read in a number. 2. If the number is 0, go to state 0. Else, go to state 1. State 1: 1. Print "Woohoo!" 2. Go to state 3. State 2: 1. Go to state 0. State 3: 1. Quit"Suppose this FSM starts in state 0 and reads in the value 0. Then it will return to the beginning of state 0, and read another number. This will continue until the FSM reads a nonzero number, at which point it will switch to state 1. In state 1, the FSM prints "Woohoo!" and then switches to state 3. State 3 causes the FSM to quit. State 2 is never reached in this example." "Here's a state out of an FSM which might be used for a fighting game character." State 555: 1. Try to punch the other guy. 2. If successful, and the user is holding punch, go to state 555 (chain move). 3. If successful and the user is not holding punch, play recovery animation. 4. If not successful, play miss animation. 5. When the recovery or miss animation ends, go to state 0 (idle).So basically, an FSM is like an engine that interprets and controls these "states" based on various factors and conditions. Each "state" has a number of attributes which determine what it does and how it can change to a different state. For a practical example, we will look at how states might be defined for a fighting game. Generally speaking, a state is always running. Therefore, there is likely some sort of "default" state. We'll call this default state "State 0". For our example, let's say State 0 is your game character just standing around, doing nothing, waiting for something to happen. That something could be you controlling him, him getting beat on by the opponent, the timer running out, or virtually anything else. So this default state continually repeats itself until it is interrupted by most anything. Now let's say you decide to move your character forward. He will now switch to what we'll call "State 10", or moving forward. As long as you keep pressing in the same direction and nothing else affects the state, this state will repeat itself. Releasing the direction will revert him back to State 0. If the opponent comes too close, you'd want to try to fight him off. So, you press one of the attack buttons. Let's say the one you pressed starts State 50. State 50 now puts your character into a state with different attributes than States 0 and 10; now he's in a sequence where fewer things can change the state, and this state will revert back to 0 if nothing changes this state before its sequence is completed. Now in this State 50, there is going to be a time when it can put the opponent into another state. Let's say we have two main states for this, being a "block" state and a "hit" state. We'll call them State 1000 and State 2000 for Block and Hit respectively. Depending on the opponent's state during your State 50, one of these two states could be called. Being a certain distance away, or the collision of bounding boxes (another fighting game concept but outside the scope of this article) will put the opponent in one of these two states. As with all states thus far, once the state is over, if they're not put into another state, they'll revert back to State 0. The concept of this logic is called a "trigger". Triggers determine what states are called. One way to affect a trigger is through the use of a "Command", probably better known as a keypress or button press. For example, let's say you have a Command that binds the key "A". When "A" is pressed, its Trigger goes off that changes to State 50. This is one of the ways a State can be changed. For example: Trigger1 = Command("A")
SetState = 50
Now, what happens if "A" is entered while the character is in
State 2000, for example? Will you want him to throw his punch during a
fall animation? Probably not. So, there are a couple of ways of
handling this problem. The first way is to add a Trigger to the "A"
Command, telling it not to execute if the character is in State 2000.
However, this method would require it to also check for State 1000, and
possibly hundreds of other States. So, what do you do? You implement
what we call a Flag, and in this case, we call it "Ctrl", short for
"Control". Ctrl can be either on or off, and is tied to whether or not
Commands can be entered or not. So, we include a new trigger into our
"A" Command, telling it not to execute if Ctrl = 0 (player has no
control). In our State 2000, we will set this Ctrl Flag to 0, which now
disables Commands. When State 2000 or whatever State it transitions
into has completed, we add a Ctrl = 1, making Commands usable again.
As a build-on to our previous example: Trigger1 = Command("A")
Trigger2 = Ctrl = 1
SetState = 50
Note how it now looks for Ctrl = 1. Both of these conditions must be true for the State to activate.
You will find that you will need to implement more and more triggers as time goes on. For example, now we can check that our guy can't punch someone if he's already in another state which has Ctrl disabled. But what if he's in the air? Or crouching? Certainly we don't want him to use the same exact attack State, so we can create a new kind of trigger. For this example, we'll call this trigger MoveType. To build on our previous example: Trigger1 = Command("A")
Trigger2 = Ctrl = 1
Trigger3 = MoveType = STANDING
SetState = 50
You could theoretically assign any value system you want to
MoveType, provided your state machine can read and understand its
syntax. The key issue is that now, this State is only entered IF (1)
Command = "A" (2) Player has control and (3) Player character is
Standing.
Now for the States themselves. What specifically happens in a State? Well, a State contains the data the FSM needs to carry out functions. It does this through a series of what we call State Controllers. A State Controller is basically like a function call to a very specific action. Here's an example of what State 50 could possibly look like: [Statedef 50] [State 50.1] Set Ctrl = 0 Anim = 50 [State 50.2] Trigger1 = AnimFrameLeft = 0 Set Ctrl = 1Now, what the heck did we just do? Okay, from the top: First, we set a "Statedef", short for State Definition. This Statedef says "hey look, I'm State 50!". The FSM looks at this State 50 and carries out the first instruction it finds, which will be State 50.1. Now, it turns off Ctrl and plays Animation 50 (it is wise practice to keep your animations the same number as your States, to avoid confusion). Now, having done this, it goes on to the next State. Hrm...it sees that there's a Trigger here, so it needs to check to see if it can execute the code in this particular snippet. Until AnimFrameLeft = 0 (this would be a variable that returns the number of animation frames left in the Anim sequence), it cannot execute the function. Once this is true, Ctrl is reset to 1, and because the Statedef is now completed, the FSM returns to State 0. Set and Anim are what we call State Controllers. So is Trigger. Anything that controls the State can be considered a State Controller. Now, this is all working theory. The task you are faced with is developing an engine that can interpret a language that you develop for your FSM. There is no standard methodology for developing this language. However, there are several working models of FSM's in action. For fighting games, one of the most popular is the M.U.G.E.N. fighting game engine, available on the WWW (the official webpage disappeared). It contains a VERY rich FSM language, and is a good basis for your own language. A final note on Commands: The M.U.G.E.N. engine uses Commands as a special State, called State -2, which is checked every frame. This is not a terribly difficult process to accomplish, but if the Statedef -2 gets too many State -2's, it can easily bog down any FSM no matter how optimized it may be. In addition, this Statedef -2 exits itself as soon as it has carried out the very first State -2 it finds that meets all of its criteria (all the Triggers check out ok), so it can never execute more than one State change per frame. This is an extremely effective system, and it is recommended that you use this type of system in developing an FSM language. By this note, a proper example of some Commands might look like this: [Statedef -2]
[State -2]
Trigger1 = Command("A")
Trigger2 = Ctrl = 1
Trigger3 = MoveType = STANDING
SetState = 50
[State -2]
Trigger1 = Command("B")
Trigger2 = Ctrl = 1
Trigger3 = MoveType = STANDING
SetState = 60
[State -2]
Trigger1 = Command("C")
Trigger2 = Ctrl = 1
Trigger3 = MoveType = STANDING
SetState = 70
[State -2]
Trigger1 = Command("A")
Trigger2 = Ctrl = 1
Trigger3 = MoveType = CROUCHING
SetState = 150
[State -2]
Trigger1 = Command("B")
Trigger2 = Ctrl = 1
Trigger3 = MoveType = CROUCHING
SetState = 160
[State -2]
Trigger1 = Command("C")
Trigger2 = Ctrl = 1
Trigger3 = MoveType = CROUCHING
SetState = 170
Does it look like a lot of work? It is. This is not an easy
system to implement. Finite State Machines are not trivial, but the
time you spend implementing one will give you the flexibility and power
to create some very spectacular games.
In the next issue of QBOA, I will build on State Controllers and attempt (!) to cover Bounding Boxes and Animation Definitions (they usually go together). Article by Nekrophidius |