Implementing a Pathfinder algorithm- Soccer Game v0.0.6

In this version of the game, I implemented a Pathfinder algorithm. As the video below shows, the AI system computes a path towards the goal. Notice how the white jersey player drives the ball towards the goal.

Implementing a Pathfinder algorithm requires knowledge about Graph Theory and the Dijkstra's algorithm. I've heard about these topics, but I wasn't well versed on them. So I decided to spend my weekend reading about them. I did learn a lot. However, as I was about to implement the algorithm, I realized that the Dijkstra's algorithm might not be suitable for soccer.

Let me explain.

In Graph Theory, a graph is composed of nodes and edges, as shown in the figure below:

A node can represent a location. An edge represents a connection. For example, you can go from your Home to the School by taking the path towards the Park. Or by taking the path towards your friend's house and CoffeeHouse.

By scanning the image, you can see that the shortest path from your home to school is towards the park (only takes two connections). However, this route may not be the fastest.

If each edge is given a weight; in this case representing traffic, then the fastest path is the one towards your friend's house. The Dijkstra's algorithm is used for these instances. It analyzes a graph and determines the fastest path between two endpoints.

I figured that I could use the Dijkstra's algorithm in the game. My idea was to compute the path a dribbling player can pursue to reach the goal.

However, the Dijkstra's algorithm works well for static nodes. It does not operate well in a dynamic environment such as in soccer. For example, a path computed at time t=0s will be invalid at time t=1s.

So, instead of using Dijkstra's algorithm, I decided to implement a "Look and Go" algorithm. The algorithm works as follows:

Once a player obtains possession of the ball, the algorithm divides the player's surrounding area into 36 positions. The algorithm then scans each location. If an opposing player is close to the location, the algorithm discards the position.

The algorithm then analyzes the location that would bring the player closer to the goal. The AI system uses this information to move the player towards that direction.

Does this algorithm work? It works quite well as shown in the image below.

As you can see, unlike the Dijkstra's Algorithm, which computes a complete set of paths, the "Look and Go" algorithm analyzes one path at a time and is more suitable for dynamic environments.

Cleaning up the AI Architecture- Soccer Game v0.0.5

The video below shows the latest implementations to the soccer game. In a nutshell, I cleaned up the AI architecture and implemented a Player Indicator.

Implemented modularity to the AI system

This month I focused on cleaning up the AI game architecture. As it turned out I was violating an OOP principle which states that:

A class should have only one responsibility.

In my case, one of the classes was not only responsible for assigning roles to each player, such as the attacker, defender and supporter role. It was also responsible for executing AI algorithms.

To remedy this, I created several classes responsible for AI operations. Specifically, I created an AI class responsible for Defending. And another class responsible for Attacking AI operations.

However, I went further and created an interface for these classes. Doing so provides modularity and flexibility whenever I need to change an AI strategy.

I also implemented methods in the AI to steal the ball from the attacking player. However, it does not know what to do once it gets possession of the ball, yet. I plan to fix this soon.

Added a Player Indicator

In the previous version of the game, it was somewhat hard to follow which player had possession of the ball. To remedy this, I added an indicator which shows who is the dribbling player and what is its heading. The indicator also points out the current defending player.

Improving the Soccer Kits

Finally, I decided to hire a game artist. I was not happy with the soccer kit texture; which was painted by me. He is currently working on the soccer kits, and I like what he has done as of now. Hopefully, by the next version update, I can show you a small video of the game with more realistic soccer kits.

Thanks for reading.

Implementing team formation-Soccer Game v0.0.4

This week was a very productive week for the development of the soccer game. As you can see in the video, I implemented most of the 11 players per team. Currently, I'm missing the goalies.

I improved the performance of the game by disabling shadows and collision detection on all but three players; dribbling player, receiving player and defender. Thus, at any time, the engine only renders a shadow to the player currently dribbling, the player who will get a pass and the defender. The same logic was applied to the collision system. Only three players have collision detection enabled at any time. Doing so improved the performance by 20%.

You may say that doing so will reduce the aesthetics of the game, and you are right. However, when you play a soccer game, your eyes are mainly focused on the controlling player and the defender. Your vision ignores all other players' aesthetics.

I also improved the AI of the game. Supporter players no longer go out of bound whenever they search for a good passing angle. The same logic applies for defenders. They are smart enough not to go out of bound.

Additionally, I added a feature that controls the strength of the kick depending on how long you press the game buttons. The longer you press the buttons, the stronger the pass; thus the farthest the ball will travel.

Implementing the 4-4-2 team formation

Up to now, I have been developing the soccer game with relatively few game characters. The reason was obvious. I was focused on implementing the properties of individual players and not the team properties.

However, this week I focused on implementing intelligence into the team as a whole. My first task was to apply "Formation" logic into the game.

There are several formations used in soccer. I decided to use the 4-4-2 formation. That is four defenders, four midfielders and two forwards.

The idea of a formation is the following:

When the team is in attacking mode, the formation should spread out; thus creating space.

In contrast, when the team is in defending mode, the formation should shrink; reducing space. Notice that no matter the mode, the team should always keep the 4-4-2 structure.

Since at any time, the game characters could be running towards a passing angle or defending positions, it made sense to implement separate game objects that serve as reference points for the players.

These game objects (formation objects) would spread out or come together depending on the state (attacking/defending) of the team. Each player is assigned a formation object and would use the position of the formation object only as a reference. The formation objects are shown as squares in the image below.

Doing so keeps the structure of team compact and resembling a 4-4-2 formation throughout the game.

Thanks for reading.

Computing Defending Positions-Soccer Game v0.0.3

This month I worked on implementing a bit of intelligence into the soccer game. The AI system can now determine the best position for a player to receive a pass. Alternatively, the system can also determine the best defending positions to intercept a pass.

The video below shows these implementations:

Computing Passing Angles

Passing angles are important concepts in soccer. Players are always scanning their surroundings looking for passing angles to reach. Passing angles is also an important concept for the dribbling player. If the dribbling player can spot a good passing angle, the chances of scoring a goal increases.

In the mobile game, I implement a method that scans 36 segments, each 10 degrees apart. Thus, forming a circle with the dribbling player at the center.

The system does interception tests of each segment against nearby players of the opposite team. If a segment intercepts one of these players, the segment is discarded as a passing angle. If it does not intercept a player, it is kept as a possible passing angle.

In the end, the system tries to select two segments whose angle with respect to the dribbling player is 45 degrees and 135 degrees, respectively.

The system then sorts the players closest to these segments and orders them to move to these passing angles.

Computing Defending Positions

Passing angles are not only important for a team who is in possession of the ball, but also for the defending team. As a defender, learning to read passing angles is crucial. And even more important is positioning yourself in a spot where you can intercept the pass.

The system determines defending positions by scanning the movement of the supporting players. And orders the defending players to move towards the passing angle. However, the defending players do not position themselves between the dribbling players and the supporting players. Instead, the defending players stand between the supporting players and the goal.

Determining a Time Interval

In a soccer game, players are constantly scanning for passing angles and defending positions. In a mobile game, the AI system scans for passing angles and defending positions at a set interval. There is no point in scanning for these items continuously.

The key is to find a balanced time interval to compute these elements. If you make the time interval too long, you will miss good passing angles and defending positions. If you make the time interval too short, you will make unnecessary computations; since players don't move around instantly.

Unfortunately, there is no formula to find the best time interval. The time interval to compute the passing angle and defending positions is determined through experimentation.

Thanks for reading

Enabling communication among players -Soccer Game v0.0.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 me time 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 State Design Pattern and a messaging system for the AI. As the video below shows, the players can now communicate among themselves and be alerted whenever the ball is being passed to them.

State Design Pattern

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.

Thus, instead of using a switch statement to implement a state machine, you use classes to represent a state object. Below is an illustration of the State Object:

Every state object contains an enter, execute and exit methods.

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."

Let's see how this works:

Assume that the player is in an idle state; it is just standing on the field waiting to change from an idle to dribbling state.

When the player changes to a "dribbling" state, the "enter" method is called. The "enter" method plays the dribbling animation.

The "execute" method is then called in a continuous loop. In our instance, the player keeps dribbling the ball, until a message is sent to change state.

When the player receives a message to change state, the "execute" method is stopped, and the "exit" method is called. The "exit" method ends the dribbling animation.

Here is an illustration of the process mentioned above:

State Manager

A soccer player requires several State Objects. For example, every player needs a running, passing, dribbling and marking state. A State Manager class is required to manage all these state objects.

The state manager is responsible for changing the state of the player, and for keeping track of the previous state. The State Manager is also responsible for calling the "enter," "execute" and "exit" methods in the appropriate order.

For example, when a player changes states, the State Manager calls the "exit" method of the current State object. It then calls the "enter" and "execute" methods of the new State object.

Messaging System

An AI system requires a messaging system to allow objects to communicate. For example, the player dribbling the ball can alert a nearby player of an incoming pass.

However, players don't receive these messages directly. Instead, the messages are received by the players' state objects.

Thus, aside from implementing an "enter," "execute" and "exit" methods, each state object also implements a "receiveMessage" method. The "receiveMessage" method acts upon the message received. For example, it can ask the player to change to a new state, or if the message is not appropriate for the current state, it ignores the message.

In the video above, when the button is pressed, a message is sent to the dribbling player with a request to pass the ball. The player changes states from dribbling to Passing state. Then another message is sent to the nearby player most likely to receive the ball.