How to make Artificial Intelligence for a 2D Platform Game – Part 2

Game’s Menu

(If you haven’t seen the first post of this series I recommend you to read it) 

Already one week has passed since the Game Jam ended and it feels good to look back and say: I gave my best in the game.  It is true the AI didn’t end working as I expected, but I’m glad to know that when Game Jam started I had no idea on how to implement the AI, I understand how difficult it can be to build an AI.. Once the Game Jam ended I decided with my friend Ignacio to plan what would be our next game, and after much thinking we concluded that we will be making a game for smartphones related to the cyberpunk theme, for now that’s all I can say. As soon as we have news about the game, we will share them through our social media.

---

The problem

Following the first post of this series, in which I discussed the problem of programming an AI that can recognize an environment built with static platforms, now this problem add to the most complex part, where the artificial intelligence must be able not only to represent the environment, but in addition to devise a way for that the AI is against the player and attack him. So now the problem is: How to do an artificial intelligence that moves correctly through platforms and attack the player?

---

The solution

The easiest way to represent the different actions that the artificial intelligence must do is through a finite-state machine … A what?

Formal explanation

I recommend you to skip this formal explanation and read directly the informal explanation, especially if you want to avoid the headache.

Finite-state machine: A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition; this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition.

For mathematics lovers.

In accordance with the general classification, the following formal definitions are found: 

• A deterministic finite state machine or acceptor deterministic finite state machine is a quintuple , where:
  •  is the input alphabet (a finite, non-empty set of symbols).
  •  is a finite, non-empty set of states.
  •  is an initial state, an element of .
  •  is the state-transition function:  (in a nondeterministic finite automaton it would be , i.e.,  would return a set of states).
  •  is the set of final states, a (possibly empty) subset of .

Informal explanation 

I’m going to show you the simplest example and I think it can serve you to understand it in an entertaining way:

Pacman pursuing a scared ghost in the original video game cutscene. From Wikipedia.

The Pac-Man game is characterized by its charismatic ghosts that try to make life impossible just to harm us and make us lose the game. Precisely these ghosts use a finite-state machine for their behavior (AI). These ghosts change their behavior depending on what Pac-Man does. For example when Pac-Man eats the super pill, the ghosts cease to pursue it and now evade it trying to not be eaten. This is a good example of a finite-state machine applied to the artificial intelligence of a  game. The image below will certainly clarify to you even more the meaning of finite-state machine.

A simple finite state machine for a enemy AI agent

The states of the machine in the image are patrol, follow, and attack, as you can see each of these states have an entrance and exit condition or event. For example if our AI is patrolling a place and it sees the player then it will pass immediately to the follow state, and it will remaing following the player as long the player doesn’t disappear from his sight or comes inside the attack range. In the case that the player disappears from artificial intelligence sight the AI will change back to the follow state.. In the case that the player is in the artificial intelligence attack’s range then it will go into the attack state. The same logic can be applied in the attack state, which has its own entrance and exit conditions.

Solving the problem

As our AI would have a maximum of three states: search, attack and evade. I decided to simplify things and represent the states like an enum type variable. An enum type contains a set of constants that are represented through numbers. Example code:

public class AI {
        private enum states = {search, attack, evade};
}

Once we define the states we can proceed to ask ourselves: How do we make an artificial intelligence that can see the player? 

The simplest answer and most appropriate according to my perspective is: Raycast. Honestly I’m not sure of the name of this technique in other graphic engine that are not Unity3D, but with this technique we can make imaginary rays that start in the artificial intelligence position in horizontal and vertical direction, by doing this we could realize that the player is our left, right, up or down, also combined with the fact that we always have a  reference to the player’s position, you can turn this into an algorithm able to move from one state to another, and also make it so that in each of these states the algorithm must perform certain actions. This is the most complex part of the algorithm, since soon you’ll realize that the approach that I used, and which I will explain, contains many different cases for the search state. Therefore, I will try to explain its structure and then provide the corresponding pseudocode. 

For the particular case of this game (considering the size of characters, the size of the level, the distance between platforms, among others) I made two horizontal rays, one to the left of the artificial intelligence’s position and other to its right. Apart from these horizontal rays also I made nine vertical rays that depend on the position of the player, in the case of the player being above the position of the AI then the rays are go up, and in the case of the player’s position being below the position of the AI then the rays go down. I imagine you will be wondering: Why did I use so many vertical rays? I did it to give the AI a wider range of visibility that would allow him to know if it should or shouldn’t start running up or down across the platforms to reach the player. I hope that you can understand better with the image below, where the AI is the red character, the rays are white, notices how the vertical rays have a horizontal margin/limit but at the height in which the AI is located.

Raycasting – In game

Whenever one of these rays collides with an object, we can determine what object it struck, in this way we can distinguish easily between the player of the other objects in the environment.

Something fundamental in the artificial intelligence’s algorithm are the platforms, because this is the only way in which the AI may approach and eventually attack the player. Therefore the approach that I decided to implement involves the following: since not only we must search horizontally but also vertically then instead of having a single state of search I divided it in horizontal search and vertical search. Therefore the AI can be in three main states (because of the time constraints I couldn’t implement the evade state, that should have triggered for example when the AI had 30% of his life or less and in which instead of following the player, it should look for something that would allow it to recover his life):

1. Horizontal search
2. Vertical search
3. Attack

Horizontal Search

For this case we should have these two bases cases covered:

• The player is located to the left of the position of the AI.
• The player is located to the right of the position of the AI.

For each of these cases we should verify the following:

• The artificial intelligence is on a platform.
• The artificial intelligence isn’t on a platform.

And for each of these cases we should check the following:

• The player is above the position of the AI.
• The player is below the position of the AI.

The artificial intelligence recognizes the platforms that it can’t reach along with the platforms that are nearby, and also, most importantly, it recognizes the platform where it stands. From here it’s easy to determine where to move obviously depending on the player’s position, for example if the player is above and to the left of the position of the AI, the most obvious action would be to move towards the left vertex of the platform on which the AI stands, once this vertex is reached we should check if there is a platform to the left and above relative to the position of the AI in the list of nearby platforms, in absence of this platform we should check the other platforms to the left, in the other hand in case this platform exists then we should send a signal indicating the AI to move there, and so the AI will jump and move to the left until it reaches the new target platform. Finally for each case, we should have plan of action using the platforms, the position of the player (environment) and the current position of the AI (agent) and the respective distances to the platforms and the player with the rays (sensors). It is important to note that the entrance condition to the horizontal search state is that none of the rays are crashing with the player (the player isn’t visible by the AI). The exit condition is that some vertical ray hit the player where we proceed to pass to the vertical search state (the player is above or below the position of the AI).

Vertical Search

This search follows the same pattern of the horizontal search, with the difference that the AI looks for the player vertically.

• The player is above the position of the AI.
• The player is below the position of the AI.

For each of these we check if:

• The AI is on a platform.
• The AI isn’t on a platform.

Here’s the difference, now we just look at the nearby vertices to the AI, for example if we know that the player is above the AI position then the simplest thing to do would be to first check if there is some nearby vertex above the AI position, if so, we found the closest vertex and this is the place where the AI must go to reach the platform containing that vertex. If we don’t find any close vertex , then we look down and we try to climb to the low platform closer to the AI. There should be an instant in which the player is no longer up or down, or the player is facing us. Therefore the condition of entry for this state is that the player is above or under the position of AI, and the exit condition is that it isn’t nor up or down the position of AI.

Attack

This state is the simplest since it only needed to check if the player is just in front or behind the AI, this obviously means that the they are at the same height. So the only thing we should check in the code is that when a horizontal ray hits the player then we turn to the attack state of the AI, once it’s verified that the state of attack is activated, the AI proceeds to attack once again. The exit condition of this state is that when the horizontal rays stop hitting the player. And the entrance condition to the state is that the horizontal ray begins to hit the player.

---

 Pseudocode

To facilitate the writing and reading I will put the pseudocode for rays separated from the states’ code. The sole purpose of doing this, is that it is as clear as possible how you could implement an AI with the same or similar characteristics, taking this post as a basis of the situations to consider.

---

// CheckRays – Method called for each physical change of the AI (Example : For each movement)

---

// UpdateCurrentState – Method called by each frame (or very short intervals)

---

 Conclusion

I think it would be inappropriate to conclude many things after the extension of this post. I could even make another post with only conclusions. I hope that the major conclusions about all the problems I had to face when choosing the approach shown here to make an artificial intelligence can be inferred by reading the post carefully. Needless to say, perhaps in a third post I will explain which should have been the right approach to properly implement the AI of this game. I leave you a video of the game and the artificial intelligence in action with all its virtues and flaws.