Implementing a State Design Pattern for an A.I. System

As you may know, I decided to develop a mobile soccer game using my game engine. The reason is quite simple. I want to test the features of the game engine and hopefully find as many bugs as possible.

Developing a mobile soccer game has introduced me to the world of Artificial Intelligence. Although I am not an expert in A.I., I have learned a valuable lesson; An A.I. system uses a state machine, and this state machine should be implemented as modular as possible.

State machines are taught using if-then or switch statements. Although such implementation is OK for small projects, it also leads to spaghetti code in complex projects.

A better way to implement a State Machine is with a Design Pattern known as State Pattern. The pros of using such pattern are that your State machine becomes modular and flexible. That is, you can remove or add as many States into your code without making it a chaotic mess.

Let me show you how to implement a State Pattern.

Note: You can download the project on my Github page so you can follow along.

Create an Abstract State Class

First, implement an abstract State class as shown below:

Abstract State Class
class StateInterface {

public:

    virtual ~StateInterface(){};

    virtual void enter(Player *uPlayer)=0;

    virtual void execute(Player *uPlayer, double dt)=0;

    virtual void exit(Player *uPlayer)=0;

};

The "execute" method will perform your "State" operations. The "enter" and "exit" methods are useful methods in an A.I. system. For example, you may have a 3D model that as it enters the "state", it waves his hand. Or it performs a goodbye gestures as it exits the "state."

Implement the concrete State Classes

Then, implement the concrete state classes. In this instance, let's implement a "Walking" and "Running" state class.

Walking State class
void WalkingState::enter(Player *uPlayer){

    std::cout<<"Player entering Walking State"<<std::endl;

}

void WalkingState::execute(Player *uPlayer, double dt){

    std::cout<<"Executing Walking State"<<std::endl;

}

void WalkingState::exit(Player *uPlayer){

    std::cout<<"Player exiting Walking State"<<std::endl;

}
Running State class
void RunningState::enter(Player *uPlayer){

    std::cout<<"Player entering Running State"<<std::endl;

}

void RunningState::execute(Player *uPlayer, double dt){

    std::cout<<"Executing Running State"<<std::endl;

}

void RunningState::exit(Player *uPlayer){

    std::cout<<"Player exiting Running State"<<std::endl;

}

As explained earlier, the "execute" method is the heart of your State operation. It is in this function where most of your logic resides. Moreover, this method will be called continuously until a change of state occurs.

You may notice that the States are implemented as Singletons. You don't have to implement the State classes as singletons, but I usually do.

Implement a State Manager

The State Manager class is responsible for changing the states and keeping track of previous states. This is shown in the snippet below:

State Manager Class
void StateManager::update(double dt){

    currentState->execute(player, dt);

}

void StateManager::changeState(StateInterface *uState){

    //keep a record of previous state
    previousState=currentState;

    //call the exit method of the existing state
    if (currentState!=NULL) {
        currentState->exit(player); 
    }

    //change state to new state
    currentState=uState;

    //call the entry method of the new state
    currentState->enter(player);

}

Before changing to a new state, the manager keeps a copy of the current state. It then calls the "exit" method of the current state. Changes to the new state and calls the "enter" method of the new state.

After the "changeState" method has completed, the manager enters the "update" method, where it continuously calls the "execute" method of the current state.

Putting it all together

Let's implement a simple class called "Player." This object will hold a pointer to the State Manager object. It will also contain a "changeState" and "update" method. Note that these methods delegate its operations to the State Manager member. See snippet below:

Player class
Player::Player(StateManager *uStateManager){

    stateManager=uStateManager;

}

Player::~Player(){
}

void Player::update(double dt){

    stateManager->update(dt);
}

void Player::changeState(StateInterface *uState){

    stateManager->changeState(uState);

}

Finally, let's put the State Pattern in action.

In the "main" function, let's create a state manager object, a player object and let's change the player object state as shown below:

main() Method
//Create a State manager object
    StateManager *stateManager=new StateManager();

    //Create a player object
    Player *player=new Player(stateManager);

    //Change the state of the object to a RUNNING state
    player->changeState(RunningState::sharedInstance());

    //call the update method
    player->update(1.0);

    //Change the state of the object to a WALKING state
    player->changeState(WalkingState::sharedInstance());

    //call the update method
    player->update(1.0);

When you run the project, the output window will show the player entering, executing and exiting the state as shown below:

  • Player entering Running State
  • Executing Running State
  • Player exiting Running State
  • Player entering Walking State
  • Executing Walking State

If you want to add a new state, you simply create a new state class, without having the need to modify the if-then/switch statements commonly used in state machines.

State Patterns make the implementation of a state machine very flexible, modular and clean. If 100 years from now, you need to add more states to your project, you won't have to modify the inner workings of your application. Instead, you just create new state classes.

Hope this helps

Should you start a technical blog?

I started this blog on Dec 2014. I've been writing for about two years (and some months) and have published about 190 articles. I think I have enough experience to comment if you should or shouldn't start a technical blog.

First, let me start off with the harsh aspects of blogging.

Writing Consistently

The hardest part of blogging is making writing a habit. I love writing, but I must confess that writing regularly has been quite a challenge. There are times when an influx of writing energy flows through me that I end up writing a post a day. Other times, I go weeks or months without writing a single post. I used to fight this writing drought by forcing myself to write, but I realized that writing is like music. When it comes, it comes; there is no point in pushing it.

No rewards for a long time

This past January I got about 7000 visits. That is the highest number of visits I've ever gotten in a month. However, during the first year, my average number of visitors was less than 20 a day.

Be prepared to write and have no one read your articles. This fact brings me to an important point; your purpose should be to HELP readers, not be concerned about your blog stats.

If helping your readers, even if it is only one, brings you satisfaction, then blogging is for you. Else, do yourself a favor and find another hobby.

Now, let me share the positive of having a blog.

Your writing will improve

Writing is a skill. You need to practice it to improve it. Blogging is the perfect stage to practice this skill. I have noticed a huge improvement in my writing. If you go back to my articles written around 2015 and compare them to recent articles, you will see improvements; not only in clarity but also grammatically.

You get to help people

Helping others is the one reason that makes blogging worthwhile. I feel an enormous sense of satisfaction every time I get a message from a reader thanking me for a post or asking for advice. This type of satisfaction is hundred times more rewarding than seeing your blog stats improve. A "Thank-You" message from readers like you, makes all the trouble of writing an article worth it.

You will become an expert

It is interesting how cracks in your understanding of a topic emerge once you start teaching others. As a matter of fact, It was writing that developed my understanding of game engine development and allowed me to complete my project.

I modified the engine's architecture several times after writing an article. Writing and teaching solidified my understanding and gave me ideas how to improve the engine. Teaching, not coding, enhanced my computer graphics knowledge.

So, should you start a technical blog?

If your goal is to express yourself through writing and you have an honest desire to help others, then blogging will be rewarding. However, if your goal is to make money like some bloggers have been able to, then be aware that the money will not come that easily and it may take a while.

Developing a Soccer Mobile Game-Part 2

Developing a soccer video game has been more fun that I thought it would be. It has also been harder than I expected. Aside from coding, the part of development that has taken the longest is creating the animations. I have done my best to create several animations that mimic a player movement on the field. As of today, I have created 21 animations and counting.

This month I focused on developing a messaging system for the AI. As the video below shows, the players can now communicate among themselves and be alerted whenever a player is passing the ball.

 
 

Implementing a messaging mechanism is crucial for an AI system. One thing to note is that the messages are not carried out by the object itself, but by the current state of the object. Doing so makes improves the robustness of your game. For example, let's say that Player A is dribbling, and player B finds a good open position to receive a pass. Player B can send a message to Player A requesting a pass. The dribbling state determines if it should pass the ball or not. Now imagine that Player A is in an idle state and does not have control of the ball, and by mistake, Player B sends a message to Player A requesting a pass. The Idle state of Player A will completely ignore the request since it has no way how to handle such message. Thus, implementing a messaging system that works directly with the "states" of the object prevents access to null pointers and unforeseen bugs.

Moreover, implementing a State Pattern instead of a simple state machine have been critical. The modularity characteristics of a State Pattern Design makes adding new "states" simple and a clean process. I strongly suggest that if you need to implement a state machine, to implement it using State Design Patterns instead of using the common "switch" statements.

How I managed to develop a game engine?

Recently I was analyzing how I was able to develop a game engine. It was a complex project which took approximately 15,330 hours. All in all, the basic framework of the engine took about three years to complete. So, how was I able to complete such enormous task?

I turned coding into a habit

Developing a game, app or a game engine can turn into a chaotic process if you don't break it down into simple tasks. And it can become overwhelming if you try to code things all at once. For example, the hardest part of a game engine is developing the physics engine. There are so many moving parts in a physics engine that can overwhelm anyone.

I manage this complex project by doing the following: For a particular feature of the engine, I would write down which Class I should implement. Then, I would write down all the methods/functions necessary for the Class. Then, instead of saying: "Today, I will implement Class X," I would instead focus on implementing ONLY one method/function a day. The key here is that I trained my brain to code every day. Even if I coded for only 15 mins, I still showed up to code every day.

By the second year of development, coding had become a lifestyle for me; just like working out and eating healthy is to me. The day I didn't code, it felt awkward. And I would find myself coding even if I wasn't planning to do so.

I used pen and paper before coding

I learned that using pen and paper before coding can save you hours of development. The first iteration of the engine was a total mess. I ended up throwing it into the trash can. The second time around, I started sketching the game engine operations, methods, classes on paper way before I started to code.

Nowadays, if I'm about to implement a method/function, I usually draw a sketch of its operation and how it may affect other parts of the engine. Having a sketch of what you are about to implement not only saves you hours of work, but it can help you avoid bugs which you may be introducing into your app unconsciously.

I used the power of visualization

You may think this is crazy, but trust me, it works. Visualizing the finish line is the most useful thing if you want to achieve your goals.

It took me about a year to implement the Collision Detection System of the engine. As I implemented the collision detection features, I would visualize the features working way before they were completed. For example, instead of me saying, "I'm implementing the GJK algorithm" I would say to myself "I'm DONE implementing the GJK algorithm" and I would visualize 3D objects colliding on the screen.

Call me crazy, but for some reason visualizing the finish line way before you cross it is a powerful tool. It worked for me, who knows it may also work for you.

Hope these tips can be of use to you.

Developing a soccer mobile game-Part 1

At the start of this year (2017), I decided to develop a full blown game using my game engine.

For a couple of weeks, I struggled to come up with the type of game to develop. Since I am not a gamer, this task was difficult. Although I am capable of developing a game (technically-wise), I lack gameplay knowledge.

So, I started playing several video games. Unfortunately, most of them bored me within a couple of minutes. I guess that is why I never got into games; some of the games I played in the past bored me quick. Of course, Super Mario and Pac-Man never had that effect on me.

As I searched for the type of game to develop, I ended up playing a soccer video game. Instantly, I knew this was the kind of game I wanted to develop. I didn't even think about it twice; I just knew this was it.

Not only do I enjoy playing soccer (Currently I play in two leagues), I also know the game quite well. I understand the role of each player and the strategies used. And since developing a soccer video game requires a lot of AI (Artificial Intelligence), this knowledge will be quite useful.

The video below shows the initial development stage of the game.

 
 

As the video shows, I was able to create the effect of dribbling and kicking motion through the use of the game engine's animation system and physics engine.

How did I do it?

Animations

The first thing that I focused on was in developing several animations. I am not an animator by any means, so I had to read several books and do several test animations. Luckily, I found this book The Animator's Survival Kit. It was a great help. With it, I was able to do a walking, running and kicking animation as shown below:

Now, one of the things that you need to consider is the transition between animations. To make it look smoothly, you need to blend each animation. I ended up doing this by interpolating the last keyframe of the previous animation with the first keyframe of the new animation. Here is a transition from running to kicking animation:

Creating the effect of a kick

The logic to kick a ball is very simple. Once there is a collision between the soccer ball and the player's feet, an impulse force is exerted on the ball, thus producing the kicking effect.

For a collision to occur, the collision detection system computes a convex-hull bounding volume for each model; ball and player. However, the problem is that the player's convex-hull is not updated during each animation. Let me explain the problem with more detail.

As you may know, a 3D animation is possible through the use of an armature. Unlike animation in 2D games, which consists of sprites played sequentially over a period, animation in 3D games consists of an armature influencing the vertices of a 3D model. An armature consists of several bones. The motion of these bones, affect the vertices of the mesh, thus creating the illusion of an animation. The video below shows the bones of a 3D model during a running animation (in Blender):

The video below shows the player with its convex-bounding volume using the game engine.

As you can see, the bounding volume does not follow the animation. Thus, when a player extends its foot, and the soccer ball is on the foot's path, the engine will not detect the collision.

You may ask, "Why don't you update the convex-hull on every animation?" The reason is that computing a convex hull is an expensive operation.

It took me while to figure out how to detect a collision with the foot and the ball. I ended up playing FIFA and other soccer games for hours trying to figure out how they do it. I tried different methods, but they all failed.

Finally, around 2 am, I got an idea how to implement the most logical solution to my problem. It took me about 4 hours to code it.

This is what I did:

Since I need to know the feet bone's position during each keyframe, I linked two cubes to the player as children objects. These cubes represent the position of the player's feet. I then retrieved the position of each feet bone during each keyframe and used this information as the cube's new position. Here is a video of the cubes following the feet path:

I then enabled collision detection between the soccer ball and the cubes. Thus, as the animation runs, the cubes follows the path of the feet. And if the ball happens to be on the cube's path, a collision is detected; thus exerting a force onto the ball. Here is a video showing the effect:

Is this how other studios do it? I have no idea, but it works for me.

State Machines

One of the reasons why I decided to develop a soccer game was because I wanted to know how to develop an AI (Artifical Intelligence) system. It so happens, that a soccer game requires a complex AI system. I felt that learning AI through a soccer game would be time well spent.

I bought this book Programming Game AI by Example. This book has a whole chapter on how to develop a soccer game's AI. To be honest, it has been a fantastic book and has helped me a lot through the initial stage of the game.

An AI system requires a Finite State Machine. In simple terms, a state machine transitions from one state to another state depending on a current condition.

As of today, the soccer player in my game has these states:

  • Idle
  • Halt Ball
  • Dribble
  • Kick Ball

Depending on a condition, the state machine transitions the player from its current state to a new state. For example, it can transition from a "dribble" state to a "kick ball" state.

You would agree that a simple way to implement the state machine would be to implement an "if-then" or a "switch" statement. However, this is a naive way to implement a state machine. And you should avoid these type of implementations in complex projects.

Instead, you should use State Patterns to implement a state machine. A state pattern is a design pattern which encapsulates each state in an object class. Each class contains the behavior for a particular state. Thus, instead of using "switch" statements, you will use objects that will implement the states' logic in a clean, modular way.

Thanks for reading