Jump to content

  • Log In with Google      Sign In   
  • Create Account

True, False, Maybe

State Machines in Games – Part 6

Posted by , in Programming 17 March 2013 - - - - - - · 1,436 views

Okay, this is the wrap-up.

I was planning on part 6 adding to the pet game having them loop back to the individual pet in determining the interest, and part 7 adding inventory items, a plot, and otherwise finishing off the dungeon explorer.

Then I realized --- it doesn't add anything new to the series. They are just new machines that replicate the behaviors already taught.

What Have We Learned

We learned that state machines are the "least powerful" of the automata in Computer Science. We also learned that they can do incredible things for games.

We can use state machines to run different code based on state.

We can use state machines to represent arbitrary meshes. These meshes can include things like maps and connectivity grids.

We don't need to hard code state machines. In fact, when you load them from data you can get substantially more power from them. Designers and artists and modelers and animators and producers can all modify the game without touching the code.

We can build complex systems, such as AI behavioral trees, out of a nested tree of very simple state machines.

How Can I Apply This

Most games apply these concepts all over the place.

One of the most common jobs in the industry is "Gameplay Engineer", or GPE. All they do is create the exact types of items we have made in this series of tutorials.

For example, in Littlest PetShop I spent months adding new behaviors and actions. They ranged from 'in the world' behaviors like I implemented in part 5, to minigames such as hide and seek where pets would run behind bushes to hide, then run up to the camera and celebrate with the player when they were found.

In The Sims every one of the tens of thousands of objects in the game required scripting. You need a pile of clothes, then you need some of these scripts: Behaviors and interactions to create the piles of clothes; interactions to drop the piles of clothes and pick them up again; interactions for a washing machine; interactions for a dryer; interactions for the maid to come clean up; and on and on and on.

Or if you are into faced paced games, you need behaviors and actions for your main characters to know to attack or run away, or decide if they should attack towers or players or minions. You need to create objects to pick up, weapons, inventories, and more. All of these behave the same way that we implemented in parts 3-5.

These little activities and behaviors grow into complex ecosystems powering most games.

The End?

I still want to add those abilities to the code, and my kids want to help me expand on the pet simulation. So I'm sure I'll be adding to this article with an addendum or two. But for now, it has been a good week. I got to spend about 6 hours writing two proof-of-concepts games, and I got to write a bunch of journal entries, and finally I was invited to turn these into an article.

So expect more on this to come. But for now, if you want more you'll need to use your own creativity and post what you did with the knowledge you have gained.

Thanks for reading.


State Machines in Games – Part 3

Posted by , in Programming 11 March 2013 - - - - - - · 1,490 views

In Part 1 we learned what state machines are and we also hard-coded a simple state machine using a switch statement.

In Part 2 we made a simple state machine interface and a generic state machine runner. We also created one boring state machine instance.

Now in Part 3 we are going to actually make a game. It isn't much of a game, but it has all the elements of gameplay. It has risk. It has danger. It has a way to win.

Okay, it is just navigating a maze of rooms in a text adventure. There are no monsters, no inventory, and no plot (we'll add all those later). For now we can just navigate a castle full of rooms.

We won't modify the state machine interface or the state machine runner that we made in part 2. They work just fine for our purposes right now.

The States of the Game

Just like the boring state machine, each state implements the IState interface and also contains some useful information specific to that state machine implementation.

The 'useful information' is a name of the room, a description of the room, and links to the neighboring rooms. The name and description are set by the constructor and the neighbors are added by the state machine when it builds the graph.

The run function actually does something this time: It writes out the description of the room as written by the constructor.

On to the code!
class FunMachineState : IState
    {
        string mName;
        string mDescription;
        List<FunMachineState> mNeighbors = new List<FunMachineState>();
        public List<FunMachineState> Neighbors { get { return mNeighbors; } }


        /// <summary>
        /// Initializes a new instance of the FunnerState class.
        /// </summary>
        /// <param name="mName">Name to display for this state</param>
        /// <param name="mDescription">Text to display for this state</param>
        public FunMachineState(string mName, string mDescription)
        {
            this.mName = mName;
            this.mDescription = mDescription;
        }

        #region IState Overrides
        public override string GetName()
        {
            return mName;
        }

        public override void Run()
        {
            // We don't do any fancy stuff, just print out where we are
            Console.WriteLine();
            Console.WriteLine(mDescription);
        }
        #endregion
    }

That wasn't too bad, was it?

Most of the State Machine

Now comes the time to describe the state machine implementation.

This one gets to be a little more interesting.

I'm going to include everything in the short listing EXCEPT the state machine constructor. I'll go over that in detail in the next section.

It implements the generic IStateMachine interface and that is pretty simple.

It also adds three machine-specific values: A list of states, a link to the current state, and a link to the exit state (which we'll get rid of in the next lesson).

You might have realized this already, but each state represents a room in the map. Hopefully that was already clear, but if not I figured I should point that out.

Of special note is how it gets the list of possible transitions and how it advances. We look at the names of the current node's neighbors -- in this case is the name of a room on the map. We advance by making sure we can only travel to neighboring rooms. That avoids the exploit of typing in "move Exit" and winning the game in the first step.
    class FunMachine : IStateMachine
    {
        List<FunMachineState> mStates;
        FunMachineState mCurrent;
        FunMachineState mExit;

        /// CONSTRUCTOR NOT SHOWN

        #region IStateMachine Overrides
        public override IState CurrentState
        {
            get { return mCurrent; }
        }
        public override string[] PossibleTransitions()
        {
            List<string> result = new List<string>();
            foreach (FunMachineState state in mCurrent.Neighbors)
            {
                result.Add(state.GetName());
            }
            return result.ToArray();
        }
        public override bool Advance(string nextState)
        {
            foreach (FunMachineState state in mCurrent.Neighbors)
            {
                if (nextState == state.GetName())
                {
                    mCurrent = state;
                    return true;
                }
            }
            System.Console.WriteLine("Invalid state.");
            return false;
        }
        public override bool IsComplete()
        {
            return mCurrent == mExit;
        }
        #endregion
    }

Again, this is mostly straightforward. We've got our game state machine in just a few lines of code.

On to the Game's State Machine Constructor...

Here is where the fun is.

This state machine is also hard coded. In order to generate the game's maze we'll need to manually construct each room (aka FSM state, or vertex, or node). And we'll need to construct each transition (aka edge) of the state machine.
        public FunMachine()
        {
            // Create all the fun states in our mini-world
            FunMachineState entryHall = new FunMachineState("Grand Entrance", "You are standing in a grand entrance of a castle.\nThere are tables and chairs, but nothing you can interact with.");
            FunMachineState staircase = new FunMachineState("Grand Staircase", "The staircase is made from beautiful granite.");
            FunMachineState eastWing = new FunMachineState("East Wing", "This wing is devoted to bedrooms.");
            FunMachineState westWing = new FunMachineState("West Wing", "This wing is devoted to business.");
            FunMachineState bedroomA = new FunMachineState("Master Suite", "This is the master suite.  What a fancy room.");
            FunMachineState bedroomB = new FunMachineState("Prince Bob's Room", "The prince has an extensive library on his wall.\nHe also has more clothes than most males know what to do with.");
            FunMachineState bedroomC = new FunMachineState("Princess Alice's Room", "The princess has filled her room with a small compur lab.\nShe spends her days playing games and writing code.");
            FunMachineState workroomA = new FunMachineState("Study", "This is the study.  It has many books.");
            FunMachineState workroomB = new FunMachineState("Bathroom", "Every home needs one");
            FunMachineState workroomC = new FunMachineState("Do Not Enter", "I warned you not to enter.\nYou are in a maze of twisty little passages, all alike.");
            FunMachineState passage = new FunMachineState("Twisty Passage", "You are in a maze of twisty little passages, all alike");

            mExit = new FunMachineState("Outside", "You have successfully exited the castle.");

            // Hook up doors.
            entryHall.Neighbors.Add(staircase);
            entryHall.Neighbors.Add(mExit);

            staircase.Neighbors.Add(eastWing);
            staircase.Neighbors.Add(westWing);
            staircase.Neighbors.Add(entryHall);

            eastWing.Neighbors.Add(bedroomA);
            eastWing.Neighbors.Add(bedroomB);
            eastWing.Neighbors.Add(bedroomC);
            eastWing.Neighbors.Add(staircase);

            bedroomA.Neighbors.Add(eastWing);
            bedroomB.Neighbors.Add(eastWing);
            bedroomC.Neighbors.Add(eastWing);

            westWing.Neighbors.Add(workroomA);
            westWing.Neighbors.Add(workroomB);
            westWing.Neighbors.Add(workroomC);

            workroomA.Neighbors.Add(westWing);
            workroomB.Neighbors.Add(westWing);

            // Trap of doom.
            workroomC.Neighbors.Add(passage);
            passage.Neighbors.Add(passage);

            // Add them to the collection
            mStates = new List<FunMachineState>();
            mStates.Add(entryHall);
            mStates.Add(staircase);
            mStates.Add(eastWing);
            mStates.Add(westWing);
            mStates.Add(bedroomA);
            mStates.Add(bedroomB);
            mStates.Add(bedroomC);
            mStates.Add(workroomA);
            mStates.Add(workroomB);
            mStates.Add(workroomC);
            mStates.Add(passage);
            mStates.Add(mExit);

            // Finally set my starting point
            mCurrent = entryHall;
        }

This creates a fun little graph.

In case you're having trouble visualizing it, the picture version looks like this:

Attached Image

It has a few rooms with their descriptions. It has a death trap room, and it has a route to victory.

It looks like a game!

It isn't much of a maze but that's all I wanted to hard code right now.

Run the Sample Code

Now is the time to actually see the game start to come together. If you haven't downloaded the source code already from the first two samples, you can download it at the bottom of this article.

Just run the project.

When you run it you can hit "1" for the boring state machine we had in Part 2. It is boring but it works.

Much more interesting is to hit "2" for this funner state machine. Navigate the map. Get lost in the death trap (and manually close the window or Ctrl+C out of the app because there is no way out).

And you can hit "3" to see a preview of what is coming.

Always Leave Them Wanting More

So now we're done with Part 3. We have made a minimal game with state machines.

Sure the game has no items to manipulate, or plot, but that will all come later. Also to come later are other uses for state machines, such as for AI systems.

Now I'm getting ahead of myself.

If you hit "3" in the sample code (I know you did) you have had your preview to Part 4 - making your state machine data driven.

Why make it data driven? You weren't seriously thinking of hard coding a large complex dungeon into your game, were you?

Attached File  StateMachineTutorials.zip   13.42KB   103 downloads


State Machines in Games – Part 2

Posted by , in Programming 10 March 2013 - - - - - - · 1,410 views

We completed Part 1 with a simple boring hard-coded state machine, implemented by a switch statement.

It didn’t do much. In textbooks that would be called “an exercise for the reader.”

In this entry (Part 2) we're going to prepare the rest of the way for our game. Since I know in advance where I am leading you, I'll tell you that we need a bunch of state machines.

As this is going to become a collection of state machines, we’ll extend it out into a common interface.

Programming to an interface, also called the Dependency Inversion Principle, allows us to extend a simple state machine into many different types of machines.

The Interface

Here are the two interface classes used in all the examples.
public abstract class IStateMachine
{
    // Accessor to look at the current state.
    public abstract IState CurrentState { get; }

    // List of all possible transitions we can make from this current state.
    public abstract string[] PossibleTransitions();

    // Advance to a named state, returning true on success.
    public abstract bool Advance(string nextState);

    // Is this state a "completion" state. Are we there yet?
    public abstract bool IsComplete();
}
public abstract class IState
{
    // Utility function to help us display useful things
    public abstract string GetName();
    // Do something
    public abstract void Run();

    // This isn't really needed, but it helps in debugging and other tasks.
    // It allows hover-tips and debug info to show me the name of the state
    // rather than the default of the type of the object
    public override string ToString()
    {
        return GetName();
    }
}


That’s it for our interface.

The State Machine Runner

Now that we have the interface we can start using it.

One of the beauties of using interfaces ("Dependency Inversion Pattern") is that we can start writing our state machine without any other details.

So here is the app I wrote. Again I didn’t actually implement any of the state machines for this state machine runner. I just used the interfaces:
static void Main(string[] args)
{
    // First we need to create the state machine.
    // Note that I'm using the abstract IStateMachine instead of a concrete class.
    IStateMachine machine = GetMachine();

    // We have a machine, now run it.
    while(!machine.IsComplete())
    {
        // Print out our current state
        Console.WriteLine("Currently in " + machine.CurrentState);
        machine.CurrentState.Run();

        // Print out our possible transitions
        Console.WriteLine("\nAvailable choices are:");
        string[] transitions = machine.PossibleTransitions();
        foreach (string item in transitions)
        {
            Console.WriteLine(" " + item);
        }

        // Request a transition from the user
        Console.WriteLine("\nWhat do you want to do?");
        string nextState = Console.ReadLine();
        machine.Advance(nextState);
    }

    // And we're done!
    // Run our final node as a special case since the above loop won't do it.
    Console.WriteLine("Currently in " + machine.CurrentState);
    machine.CurrentState.Run();

    // Finish off.
    Console.WriteLine("\n\nPress any key to continue.");
    Console.ReadKey(true);
}
That’s it! 36 lines of code and our game runner is finished.

What?! The game runner is finished?

That little beauty will run any state machine that implements the interface. And our little game can fit into that interface. So let’s get on to filling in those pesky details.

Let’s try it out with a traditional textbook state machine. I’m talking about how textbooks use labels like 0, 1, 2, and variables like x, y, and z, that carry no real useful information.

Boring State Machine Implementation

There are two major options when it comes to state machines. You can make the machine know about traversing the machine, or you can make the state know about it. It's just like in graphics how you can either have objects move around the world or you can have the world move around objects. Either way, the result is the same.

In this boring example I made a single state and made the state modify itself as the machine moved around it.

Boring Machine Source
class BoringMachine : IStateMachine
{
    BoringMachineState mState = new BoringMachineState();

    public override IState CurrentState
    {
        get { return mState; }
    }
    public override string[] PossibleTransitions()
    {
        // For this simple example, forward it on to the state
        return mState.ListTransitions();
    }
    public override bool Advance(string nextState)
    {
        Console.WriteLine("I'm a boring state machine. I don't care what you entered. Advancing state.");
        return mState.Advance();
    }
    public override bool IsComplete()
    {
        // For the simple example, forward it on to the state
        return mState.IsComplete();
    }
}
Because it is a boring example I’ve simply ignored the name of the state transition. We don’t need it, we simply tell the state that it is time to move on.

Boring Machine State code

Here it is, in all it’s boring detail:
class BoringMachineState : IState
{
    #region Members
    internal enum SameOldStates
    {
        Enter,
        DoStuff,
        Exiting,
        Done
    }
    SameOldStates mState = SameOldStates.Enter;
    #endregion
    #region IState overrides
    public override string GetName()
    {
        return mState.ToString();
    }
    public override void Run()
    {
         // Do nothing. This is the game logic.
    }
    #endregion
    #region Helper functions
    public bool IsComplete()
    {
        return mState == SameOldStates.Done;
    }
    public string[] ListTransitions()
    {
        List<string> result = new List<string>();
        switch (mState)
        {
        case SameOldStates.Enter:
            result.Add("DoStuff");
            break;
        case SameOldStates.DoStuff:
            result.Add("Exiting");
            break;
        case SameOldStates.Exiting:
            result.Add("Done");
            break;
        case SameOldStates.Done:
            result.Add("Done");
            break;
        }
        return result.ToArray();
    }
    public bool Advance()
    {
        switch (mState)
        {
        case SameOldStates.Enter:
            mState = SameOldStates.DoStuff;
            break;
        case SameOldStates.DoStuff:
            mState = SameOldStates.Exiting;
            break;
        case SameOldStates.Exiting:
            mState = SameOldStates.Done;
            break;
        case SameOldStates.Done:
            // Do nothing.
            break;
        }
        return true;
    }
    #endregion
}
It is a little boring. Everything is hard coded. It doesn’t look like a game. It ignores user input.

But when I run it, IT WORKS!

And that’s what matters.

Always Leave Them Wanting More

Okay, my game really is close to being finished.

The game runner is complete. It works perfectly for the game we’re trying to make.

In part three, I’ll create a second implementation of IStateMachine and IState that make an actual interactive game.

(Okay, part 3 isn't an actual FUN game, but it is enough to technically be a text adventure. That is for a very loose definition of 'adventure'.)

You can download the code in the link below. Just like before it has a preview of what is to come.

Attached File  StateMachineTutorials.zip   13.42KB   103 downloads


State Machines in Games – Part 1

Posted by , in Programming 10 March 2013 - - - - - - · 2,312 views

I recently had a conversation with a beginner on GameDev.net about the importance of state machines.

Most of the beginners on the site are teenagers enrolled in secondary school. Often they pick up concepts here and there over the Internet when they think it will help, but don’t take the time to learn topics that don’t seem interesting.

State machines. Bah! Who needs them, right?

Games need them.

Let’s get the boring part over with…

The Computer Science Part

Finite State Machines, FSMs, or Finite State Automata, are an abstract machine. The machine is made up of multiple states, also called a node or vertex. The machine transitions to a new state by a trigger or event or condition. The transitions are also called edges. One node is designated as the start node. Notes may be marked as exit nodes. The machine enters at the start node, transitions to new states, and eventually ends on an exit node.

So what does that mean?

We can explain the same state machine in many different ways. It is usually easier to understand a state machine when it is put into a pretty picture. It is usually easier to modify, codify, and program state machines when they are in tables. So we’ll do both.

Let’s start with this very simple state machine:

Attached Image

Note that there are 2 entries for state 2. That is because it has two transitions.

Graphically it looks like this:

Attached Image

But we don’t have to use boring names like 0, 1, 2, and 3 for state names, just like we don’t have to stick with x and y for variable names.

Let’s redraw the graphs with better names:

Attached Image

Suddenly it looks much less like a boring theory topic and more like something to do with games.

In fact, it looks like an NPC’s game logic.

Implementing a simple state machine

Now we can start out simple implementation.

For the common quick-and-dirty simple state machine that will never change, we can simply hard code the machine into the code. In that case the programmer calls on his favorite little friend, the switch statement:
public class StateMachine
{
public enum State
{
Routing,
Sentrying,
Attacking,
Ending
}
State mState = State.Routing;
Random rng = new Random();

public string GetStateName()
{
return mState.ToString();
}
public string UpdateState()
{
return "Running state " + GetStateName() +". Your game logic goes here.";
}

public void NextState()
{
switch (mState)
{
case State.Routing:
mState = State.Sentrying;
break;
case State.Sentrying:
mState = State.Attacking;
break;
case State.Attacking:
// TODO: Make this based on game logic instead of random name generator
if (rng.NextDouble() < 0.75)
{
Console.WriteLine("Random generator says NPC has survived.");
mState = State.Routing;
}
else
{
Console.WriteLine("Random generator says NPC did not survive.");
mState = State.Ending;
}
break;
case State.Ending:
// Nothing to do.
break;
}
}
public bool IsDone()
{
return mState == State.Ending;
}
}


"But wait", you might exclaim, "That doesn’t look like a big ugly table or a fancy graph!" That’s right. I said above that you can have many different ways to represent a state machine, and this is one of them.

Always Leave Them Wanting More

This sums up the first lesson. You know what a state machine is in an abstract way. You saw that they might potentially have some uses in games. And you hopefully want to know more.

Stop by next time for the second lesson about extending the basic state machine.

Source code is attached. You can download it to get a sneak peak at what is coming up.

Attached File  StateMachineTutorials.zip (13.42KB)
downloads: 103





December 2016 »

S M T W T F S
    123
456789 10
11121314151617
18192021222324
25262728293031

Recent Comments