Login | Register   
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Best Approaches for AI in Game Development

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


advertisement

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;
}

http://ai-depot.com/articles/minimax-explained/

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.

Conclusion

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.



   
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap