29. June 2016

Welcome to a new tutorial series here on GameFromScratch.com where we will be looking at core concepts of game programming.  This includes data structures, design patterns and algorithms commonly used in game development.  We start the series off with Finite State Machines.

There is an HD video version of this tutorial available here and embedded below.

## What is a Finite State Machine?

A Finite State Machine (or FSM for short) is one of those concepts that sounds much scarier than it actually is.  In the simplest form it’s a datatype that can have only one value (state) from a finite selection of values(states).  The easiest way is to understand the finite state machine is to look at a real world example.

Yep, a traffic light is a perfect example of a FSM, or at least, the logic controlling it is.  Consider the three possible states this particular traffic light can be in.  At any given point (assuming I suppose the power is working...) the light will be one of three states, red, yellow or green.  It can never been more than one of those states at a time, it’s always red or yellow or green.  These are the two keep concepts of a finite state machine.  There are a finite number of states ( 3 in this case ) and only one is true or active at a time.

It’s a very simple concept, but extremely useful in game development.

## What are FSMs Used For?

In game development, one of the most common uses for finite state machines is artificial intelligence.  Consider the example of PacMan’s ghosts.  A state machine can be used to control how they behave.  A ghost may have one of several different operating modes for example waiting to be released, hunting, hunted and dead.  The state machine is what is used to drive the ghost’s actions and to switch between states.  You will find AI examples absolutely loaded with state machines, often with some fuzzy logic controlling the transition between states to give a layer of unpredictability to your characters.

AI isn’t the only place of course, think of all the different things in a game that are related, there are multiple different states they can be in, but only one can be active at a time.  Game states are a very common example, where you break your game up into a series of states, for example Loading, Main Menu, Playing, High Score, Exiting.  Many game engines ( one such example is Phaser ) split your game up into a series of states.  The ultimate controller of these states is a finite state machine.  A sequential UI ( think of a sequence of dialogs controlled by next/back buttons ) can also be implemented using FSMs.  They are also commonly used to control elements in a games world.  Consider a game with a weather system, be it day or night cycles or season cycles like Spring, Summer, etc...  these would most likely be controlled via FSMs.

## Implementing a Finite State Machine

The example we are going to use here is to implement a traffic light via FSM.  At it’s core the data is going to be stored in an enum, a natural fit for state machines, but stack based or array based options are also viable.  This example is not only going to switch the traffic lights periodically, it’s also going to implement callbacks so the world at large can interact with the light.  This example is implemented using C#, but should be easily adapted to most modern programming languages.

```using System;

namespace GameFromScratchDemo
{

public class TrafficLight{
// This enum represents the three possible values our state machine can
be
public enum States { Green, Yellow, Red };
// This is the amount of time for the timer to wait before changing
between states
private const int LIGHT_DURATION = 5000;

// An actual instance of our enum.
private States _state;

// The timer object that is going to be used to switch between states

// This function is called by the timer when it's time for a light to
change
public void lightChanged(){
System.Console.WriteLine("Light Changed");

//  For each state, move to the next appropriate state.  I.e, red
becomes green, etc.
switch(_state){
case States.Green:
_state = States.Yellow;
break;

case States.Yellow:
_state = States.Red;
break;

case States.Red:
_state = States.Green;
break;
}

// Reset our timer, so this will all happen again and again

// Call our event.  This is used to communicate with the outside
world that our state change occured
onStateChange(_state);
}

// In our constructor we simply set out default state (green) and
create/start our timer
public TrafficLight() {
_state = States.Green;
System.Console.WriteLine("Light Created with initial Green state");

_timer = new System.Threading.Timer( _ => lightChanged(), null,
LIGHT_DURATION,
}

// these two work together to provide the callback functionality
// Implementing callback is going to differ greatly from langauge to
language
public delegate void StateChangedResult(States newState);
public event StateChangedResult onStateChange;
}

// Our actual program.  Simply create a traffic light instance
// Register a callback that will simply print the current state returned
when the light state changes
// And finally wait for the user to hit enter before ending the program
public class Program
{
public static void Main(string[] args)
{
TrafficLight light = new TrafficLight();
light.onStateChange += (TrafficLight.States state) => { Console.
WriteLine(state); };
}

}
}
```

The example is pretty well documented in the code above.  Essentially we are creating a class TrafficLight that can internally have one of three states Green, Yellow or Red.  It also implements a timer that switches between those states.  To make the code actually useful, it also implements a callback system so code external to the TrafficLight can interact with it as a black box.  The callback will be passed the current state value every time the light changes.

This is obviously a simple example of a state machine but the same basic premise remains regardless to complexity.  It is a very useful data structure for organizing code, especially the flow of logic.  Coupled with callbacks, it is also a great way of keeping systems decoupled as much as possible.

## The Video

20. November 2011

Handling game time is problem that almost all games have to deal with.  A very good question recently came up in my C++ game from scratch tutorial about why I didn’t normalize the players movements which reminded me of a post on the subject.

Years ago Shawn Hargreaves of XNA ( and Allegro ) fame blogged about how XNA handles the Update and Render loops.  I simply post it here again because it is one of the most succinct posts I have encountered on the subject.  So, if you are looking into creating a game and need to figure out how to implement the game loop, I recommend you give it a read.

By default XNA runs in fixed timestep mode, with a TargetElapsedTime of 60 frames per second. This provides a simple guarantee:

• We will call your Update method exactly 60 times per second
• We will call your Draw method whenever we feel like it

Digging into exactly what that means, you will realize there are several possible scenarios depending on how long your Update and Draw methods take to execute.

The simplest situation is that the total time you spend in Update + Draw is exactly 1/60 of a second. In this case we will call Update, then call Draw, then look at the clock and notice it is time for another Update, then Draw, and so on. Simple!

What if your Update + Draw takes less than 1/60 of a second? Also simple. Here we call Update, then call Draw, then look at the clock, notice we have some time left over, so wait around twiddling our thumbs until it is time to call Update again.

What if Update + Draw takes longer than 1/60 of a second? This is where things get complicated. There are many reasons why this could happen:

1. The computer might be slightly too slow to run the game at the desired speed.
2. Or the computer might be way too slow to run the game at the desired speed!
3. The computer might be basically fast enough, but this particular frame might have taken an unusually long time for some reason. Perhaps there were too many explosions on screen, or the game had to load a new texture, or there was a garbage collection.
4. You could have paused the program in the debugger.

We do the same thing in response to all four causes of slowness:

• Set GameTime.IsRunningSlowly to true.
• Call Update extra times (without calling Draw) until we catch up.
• If things are getting ridiculous and we are too far behind, we just give up.

If you think about how this algorithm deals with the four possible causes of slowdown I listed above, you'll see it handles them all rather well:

1. Even if the computer is too slow to run Update + Draw inside a single frame, chances are that Update + Update + Draw will fit into two frames. The game may look a little jerky, but it will still play correctly. If the programmer is particularly smart they might even notice that we set IsRunningSlowly, and automatically reduce detail or turn off special effects to speed things up.
2. If the computer is way too slow (ie. if the Update method alone is too slow to fit into a single frame) there isn't really much we can do, other than set IsRunningSlowly, cross our fingers, and hope the game might do something clever in response to that. Most of the time, though, if you find yourself in this situation you just need a faster computer!
3. If a particular frame happens to take unusually long, we automatically call Update some extra times to catch up, after which everything carries on as normal. The player may notice a slight glitch, but we automatically correct for this to minimize the impact.
4. Pausing in the debugger will leave the game a long way behind where the clock says it should be, so our algorithm will give up, accept that it has lost some time, and continue running smoothly from the time execution was resumed.

Shawn’s blog in general is a very good read, but this this post in particular is one that I seem to keep coming back to.

For the record, Pang from the C++ tutorial does not gracefully handle hitting a breakpoint ( it adds a layer of unwanted complexity for learning purposes ), so will do downright stupid things when it hits a breakpoint causing it to pause for a while.  I believe on the next frame it will cause your movement to be really really really far.  It would be as simple as adding if(elapsedTime > someReallyBigValue) startTimeOver() if you really wanted to fix this.

Sorry for digging up the past, now back to your regular broadcast!

1. May 2011

Hmmmm, really need to settle on a name for the bipedal robotic characters that isn't Mech/Mecha soon just to ease these conversations! Not my most creative day so I’ll just go with GPR now.

Anyways, the GPR is very much fundamental to the game.  One of my favorite things about Autoduel and Mechwarrior Mercs was the sense of acquisition.  Start with a lowly machine and work your way up the ranks.  One of my favorite factors of Chromehounds was the customization aspect.  I intend to incorporate both into our game.

The very first Mech, er GPR the character starts with is very primitive, like the Powerloader from Aliens that Ripley used.  Very simple bipedal machine with a single weapon forward firing weapon mount.  As the player wins matches, they will have the option of swapping that weapon out for better weapons and eventually with be able to buy better GPR frames.  In the end though, it will entirely be about trade offs.

Each frame will have a certain number of slots available, of different sizes to accommodate different sized weapons.  Additionally frames will be able to have different power plants, that will be a factor in speed, battery life, weapon power and charges.  So you could mount a big heavy laser, that really sucks the juice or mount smaller engine which would be lighter and faster but couldn’t power the weapons as well.

It is all about trade offs, so you could create a fast lightly armed frame, or a heavily armed slow machine or simply an average all around machine.  You could also use munitions based weapons like rocket launchers or machine guns that don’t use energy from the engine, but once they run out of ammunition are as good as useless.

All frames start with a certain amount of energy, tied to the type of power plant installed.  Things like the weight of the frame ( from weapons and armor ), firing of energy weapons, running at high speeds, taking damage from certain types of weapons, etc.  If energy goes to zero, you stop dead and can’t fire.  Engines will recharge slowly on their own, so you need to balance speed and weapon use to keep your power levels healthy.  Or, go with a power plant that has a rapid recharge rating.  In my head now, statistically a power plant is rated by:  size ( amount of space needed by frame to install ), weight, power available, recharge rate and frame class(es) ( what size of frames the engine can be install into ) and finally cost.

Frames work on a very similar manner, with various weight classes, like featherweight, light, medium, etc…  In addition they have variant number of weapon mounts of different types ( forward facing, 360, back facing, 360 degrees auto tracking, pod based, etc ), maximum weight for all add-ons ( engines, weapons, armour, etc ), maximum internal space for engines.

So, in the beginning, machines would be only a few meters tall, with a single weapon and underpowered engines and minimal armor.  By the end though, the player could be piloting a literal titan, several meters tall and bristling with weapons and armor.  Of course then, so will their enemies.

From a developers perspective, this means I need to figure out how to make weapons modular.  In the end I imagine this comes down to dynamic parenting of bones, but it is something I need to look into from a technical point of view before continuing too far ahead.  I had been tempted to make frames even more customizable, so different legs, torsos, cockpits, arms and weapons, but truth is I think the level of work is too high to handle right now, especially when it comes to creating the animations.  If the modular weapons end up being not too difficult, I may revisit this concept.

You know, the name Frames is starting to grow on me.  BattleFrames?  Battle Frame Formats?  Yeah, that’s the perfect name, BFF!  Oh, wait….  *groan*  Back to the drawing board.

For those looking at the various inspirational images in this post, they are from the top Ripley in a Power Loader in Aliens, the Walker from Avatar and finally the Imperial Guard Walker, which is probably the closest in my minds eye to the kind of vehicle the player will start in.  Think of it like the go-cart of Frames.

1. May 2011

Hmmmm, really need to settle on a name for the bipedal robotic characters that isn't Mech/Mecha soon just to ease these conversations! Not my most creative day so I’ll just go with GPR now.

Anyways, the GPR is very much fundamental to the game.  One of my favorite things about Autoduel and Mechwarrior Mercs was the sense of acquisition.  Start with a lowly machine and work your way up the ranks.  One of my favorite factors of Chromehounds was the customization aspect.  I intend to incorporate both into our game.

The very first Mech, er GPR the character starts with is very primitive, like the Powerloader from Aliens that Ripley used.  Very simple bipedal machine with a single weapon forward firing weapon mount.  As the player wins matches, they will have the option of swapping that weapon out for better weapons and eventually with be able to buy better GPR frames.  In the end though, it will entirely be about trade offs.

Each frame will have a certain number of slots available, of different sizes to accommodate different sized weapons.  Additionally frames will be able to have different power plants, that will be a factor in speed, battery life, weapon power and charges.  So you could mount a big heavy laser, that really sucks the juice or mount smaller engine which would be lighter and faster but couldn’t power the weapons as well.

It is all about trade offs, so you could create a fast lightly armed frame, or a heavily armed slow machine or simply an average all around machine.  You could also use munitions based weapons like rocket launchers or machine guns that don’t use energy from the engine, but once they run out of ammunition are as good as useless.

All frames start with a certain amount of energy, tied to the type of power plant installed.  Things like the weight of the frame ( from weapons and armor ), firing of energy weapons, running at high speeds, taking damage from certain types of weapons, etc.  If energy goes to zero, you stop dead and can’t fire.  Engines will recharge slowly on their own, so you need to balance speed and weapon use to keep your power levels healthy.  Or, go with a power plant that has a rapid recharge rating.  In my head now, statistically a power plant is rated by:  size ( amount of space needed by frame to install ), weight, power available, recharge rate and frame class(es) ( what size of frames the engine can be install into ) and finally cost.

Frames work on a very similar manner, with various weight classes, like featherweight, light, medium, etc…  In addition they have variant number of weapon mounts of different types ( forward facing, 360, back facing, 360 degrees auto tracking, pod based, etc ), maximum weight for all add-ons ( engines, weapons, armour, etc ), maximum internal space for engines.

So, in the beginning, machines would be only a few meters tall, with a single weapon and underpowered engines and minimal armor.  By the end though, the player could be piloting a literal titan, several meters tall and bristling with weapons and armor.  Of course then, so will their enemies.

From a developers perspective, this means I need to figure out how to make weapons modular.  In the end I imagine this comes down to dynamic parenting of bones, but it is something I need to look into from a technical point of view before continuing too far ahead.  I had been tempted to make frames even more customizable, so different legs, torsos, cockpits, arms and weapons, but truth is I think the level of work is too high to handle right now, especially when it comes to creating the animations.  If the modular weapons end up being not too difficult, I may revisit this concept.

You know, the name Frames is starting to grow on me.  BattleFrames?  Battle Frame Formats?  Yeah, that’s the perfect name, BFF!  Oh, wait….  *groan*  Back to the drawing board.

For those looking at the various inspirational images in this post, they are from the top Ripley in a Power Loader in Aliens, the Walker from Avatar and finally the Imperial Guard Walker, which is probably the closest in my minds eye to the kind of vehicle the player will start in.  Think of it like the go-cart of Frames.