Best Approaches for AI in Game Development

Best Approaches for AI in Game Development

When the term artificial intelligence (AI) is mentioned, it is widely believed that the computers really have the ability to think. However, the truth is a little bit different – computers just execute complex mathematical models and algorithms that are created to simulate thinking and decision making. In this article, we will see the most popular artificial intelligence algorithms used in game development.

Minimax Algorithm

The Minimax algorithm is one of the most widely used algorithms applied in two player games (e.g. Tic-tack-toe or chess). Its purpose is to determine which move is best for the AI (computer player) to make. The algorithm is based on Minimax theorem, a decision rule used in game theory, which says that Player 1’s strategy is to maximize its minimum gain, and that the Player 2’s strategy is to minimize its maximum loss (note that negative values are also allowed for gain and loss). In game development, the theorem is usually used in combination with the game tree. The game tree is generated from the current game position to the final game position, from Player 1’s point of view. So, each node in the tree represents how effective the move is. Node values are filled from bottom to top.

After generating the game tree, the Minimax algorithm is applied.

MinMax (GamePosition game) {  return MaxMove (game);} MaxMove (GamePosition game) {  if (GameEnded(game)) {    return EvalGameState(game);  }  else {    best_move < - {};    moves <- GenerateMoves(game);    ForEach moves {       move <- MinMove(ApplyMove(game));       if (Value(move) > Value(best_move)) {          best_move < - move;       }    }    return best_move;  }} MinMove (GamePosition game) {  best_move <- {};  moves <- GenerateMoves(game);  ForEach moves {     move <- MaxMove(ApplyMove(game));     if (Value(move) > Value(best_move)) {        best_move < - move;     }  }   return best_move;}

A* Algorithm

A* algorithm offers a solution to a common problem in more complex games - path finding or making characters know where they can - and where they should - move. It is widely used because of its performance and accuracy.

There are two things you will need in order to make A* work:

  1. A graph of your terrain
  2. A method to estimate cost to reach between points

A* then traverses the graph, using best-first search to find the path that has lowest expected total cost. The cost function is usually a sum of two functions:

  1. Past path-cost function, which is the known distance from the starting node to the current node (G score)
  2. Future path-cost function, which is a cost estimate from the current node to the goal (H score)

Sample A* code:

function A*(start,goal)    closedset := the empty set    // The set of nodes already evaluated.    openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node    came_from := the empty map    // The map of navigated nodes.    g_score[start] := 0    // Cost from start along best known path.    // Estimated total cost from start to goal through y.    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)         while openset is not empty        current := the node in openset having the lowest f_score[] value        if current = goal            return reconstruct_path(came_from, goal)                 remove current from openset        add current to closedset        for each neighbor in neighbor_nodes(current)            tentative_g_score := g_score[current] + dist_between(current,neighbor)            tentative_f_score := tentative_g_score + heuristic_cost_estimate(neighbor, goal)            if neighbor in closedset and tentative_f_score >= f_score[neighbor]                    continue            if neighbor not in openset or tentative_f_score < f_score[neighbor]                 came_from[neighbor] := current                g_score[neighbor] := tentative_g_score                f_score[neighbor] := tentative_f_score                if neighbor not in openset                    add neighbor to openset    return failure

State Machine

The finite-state machine is a mathematical model that perceives an object as an abstract machine that can be in a finite number of states. The machine can be only in one state at a time. It can also change states. This is called a transition and can be triggered by an event or condition.

State machine is used to determine the behavior of AI, i.e. which actions to take at a certain time.

Here is a simple example:

switch( npc[i].state ){ case state_idle:   {      // First, see if I should attack.      target = TryToFindAttackTarget(npc[i]);      if( target )      {        npc[i].SetTarget( target );        npc[i].state = state_attack;        break;      }      // Next, see if I should heal myself      ...       // Check if I should heal neighbors      ...      /* other idle tasks */      ...   } case state_flee:   {  ...   } case state_attack:   {     // Determine if the target is still valid.  Maybe it died.     if( !npc[i].GetTarget() )      {        // Try to find a new target        ...     }     // If I still don't have a target, go back to idle     if( !npc[i].GetTarget() )     {       npc[i].state = state_idle;     }   }  case state_dead:   {  ...    }...      }

Artificial Neural Networks

An artificial neural network (or ANN) is an algorithm used in artificial intelligence to simulate human thinking. It is called a neural network because it works similarly to human brain - it receives input, the neurons communicate with each other and produce a "smart" output.

Artificial neural network has three layers of neurons:

  1. Input layer
  2. Hidden layer
  3. Output layer

Every neuron is connected to all neurons in the next layer. The neurons solve the problem by adjusting output (i.e. weight coefficients between them). The process of adjusting weight coefficients is called training. So, you will need to prepare sample data in order to make the neural network "learn" your problem. The better the training data is, the better the output will be.

Neural networks are widely used in game development because once trained they have good performance, and because they enable the game AI to learn over time. They can also be applied in resolving recognition problems, such as deciding whether the seen person is a friend or a foe.


This article explains the basic algorithms used in game development and simplifies them for easier understanding. In reality, game development is much more complex. You will be working with a lot of data, which makes these algorithms expensive in terms of CPU and RAM usage. That means that you will have to consider optimization techniques, which were not discussed in this article.

Share the Post:
Heading photo, Metadata.

What is Metadata?

What is metadata? Well, It’s an odd concept to wrap your head around. Metadata is essentially the secondary layer of data that tracks details about the “regular” data. The regular

XDR solutions

The Benefits of Using XDR Solutions

Cybercriminals constantly adapt their strategies, developing newer, more powerful, and intelligent ways to attack your network. Since security professionals must innovate as well, more conventional endpoint detection solutions have evolved

AI is revolutionizing fraud detection

How AI is Revolutionizing Fraud Detection

Artificial intelligence – commonly known as AI – means a form of technology with multiple uses. As a result, it has become extremely valuable to a number of businesses across

AI innovation

Companies Leading AI Innovation in 2023

Artificial intelligence (AI) has been transforming industries and revolutionizing business operations. AI’s potential to enhance efficiency and productivity has become crucial to many businesses. As we move into 2023, several

data fivetran pricing

Fivetran Pricing Explained

One of the biggest trends of the 21st century is the massive surge in analytics. Analytics is the process of utilizing data to drive future decision-making. With so much of

kubernetes logging

Kubernetes Logging: What You Need to Know

Kubernetes from Google is one of the most popular open-source and free container management solutions made to make managing and deploying applications easier. It has a solid architecture that makes