How to develop game AI and NPC algorithms

6 of votes

2438

Game AI: how to make game smart and interesting

Video Game AI algorithms are the chunks of code that control the game logic. In most cases,  they are in charge of enemies, traps and other stuff that reacts to the player’s actions and makes the game interesting to play. For example, it is the AI in chess and strategy games, enemies in action games, AI controlled cars in racing games and so on.

game ai

Developing the AI is much more difficult than coding the game mechanics or planning levels. For example, in First-Person Shooter game development the programmers has to teach the AI to change position, take cover, shoot the player and fall back if needed. Sounds simple, unless the developer understands that the bots doesn’t have to do this in written order, but to think and make decisions what to do in the exact moment. Otherwise, the game will be boring to play. Like in Cyberpunk 2077, where poor AI and combat system became meme.

Why a game should have good algorithms

Good game algorithms promise the player that he will be satisfied with the single player experience. It is crucial for games where the multiplayer isn’t so popular or doesn’t exist: strategy games, story-dependent action games and RPGs, simulators, logic and table games, etc.

New and indie developers are better to start with story-dependent games, because they don’t need tons of content, flawless net code and expensive servers. So, in this article we will tell you why good AI makes the game interesting and how to develop one in the most efficient way.game artificial intelligence

Why Game AI is difficult to develop

Most video games are made on conflict between the player and the game itself. The player is trying to reach the goal while the game is preventing him from doing so. For example, in Mario Bros 1 there are dozens of enemies who won’t let Mario walk peacefully. In SimCity or Cities: Skylines there are many unpredictable events that the player has to deal with. And in FPS games there are enemies which try to kill the player.

The best example of using the AI is racing games development. There are two types to do it:

  • to record a “ghost car” for different prize places and let the player to compete with them;
  • to develop an actual AI that competes the player on the track.

Only a few racing games use “ghost cars”, because they aren’t so exciting as rivals. Also, the players can’t use dirty tricks like pushing the rival out of the track. So most developers stick with AI.

ai gif

How the AI challenges the players

The main challenge of racing game AI development is to make the bots challenging while possible to beat. Developers have to solve two problems:

  • the player is a good driver, goes too far ahead and doesn’t see any competition;
  • the player is a bad driver, the bots left him too far behind, so the player has no chance to compete with them.

Also, every bot has a different car with different racing cars. There are relatively slow but maneuverable cars that can turn on high speed and there are very fast cars with bad steering. These cars have to be handled differently, so the bots need to have different algorithms for driving.

Second also, there are different racing modes: regular racing, demolition, speed radar, etc. Bots have to accommodate to them and behave differently.

And that’s the bare minimum the AI developer has to make for a simple racing game. Every new variable in gameplay doubles the amount of work.

Simple video game AI development — Final State Machine

There are two instruments of video game AI development:

  • Final State Machine (FSM);
  • Monte Carlo Search Tree (MCST).

Final State Machine are instructions that AI follows in preprogrammed cases — Final States. Instruction examples:

  • if the bot with gun is out of ammo, it will first take cover, then reload;
  • if the previously hidden player came to the bot’s line of sight, the bot will raise the alarm and try to shoot the player.
  • if the player disappeared from the line of sight behind the cover, the bot will try to flank him.

final state machine ai

In general, the FSM is just “if, else” algorithms. This approach has a big drawback: predictability. The player will quickly adapt to the AI’s behavior patterns and will use them to gain advantage. For example, the developer told the bot to change cover after every 10 seconds. The player understood it and now is waiting for the bot to change cover instead of trying to flank it or to throw grenades.

Complex video game AI development — Monte Carlo

Monte Carlo Search Tree is different from Final State Machine. It grows a decision branches:

  • calculate a few possible reactions to the player’s actions;
  • calculate a few ways the player can response the reaction with;
  • calculate a few possible reactions to these responses;
  • execute the best branch.

MCST is a real CPU eater, because every decision requires 10x more calculations than FSM uses. But the results are worth it, if the developer’s goal is to create the ultimate opponent. For example, MCST method was used to create Deep Blue — the strongest chess computer in the world. It literally calculated millions of moves on every turn and played the game in the most efficient manner, but it is way bigger than a modern gaming PC with two GPUs and water cooling.

deep blue ai example

Where to use Monte Carlo algorithm

The expensive Monte Carlo Trees are best to use in strategy and logic games, like in Civilization, Europa Universalis, Total War, etc. There are a few reasons to do like this:

  • the player can wait a few seconds to let the AI calculate branches;
  • there are many variables to take into account;
  • the player wants to play with a smart opponent to feel the real challenge.

And we have described the drawback of Monte Carlo: it is slow as turtle. A typical strategy game have thousands of variables: resources, units, rules and game mechanics. That’s why while playing Civilization or other turn based strategy the bots need to think for a longer time after every move. One gamer set a game between a few bots, and it took 10 years for one bot to win.

Optimal game AI — Monte Carlo + Final State + random

If you are a chess player, you may have noticed that the bot rarely responds to the same move similarly. That’s because it’s Monte Carlo algorithm skips most of the possible outcomes and analyzes only a few random ones. The AI’s response depends on which

Here’s an example: there are 10 moves the AI can do. Two are good, two are bad, six are meh. If the AI has only 1 random branch to analyze, it has 20% chance to pick a good move and 80% to pick a move which will gave the advantage to the player. But if the algorithm can calculate 3 random branches, it has 45% chance to make a good move.

monte carlo optimized algorithm

So, with picking between a few random branches the AI can still make a good move without spending hours on thinking. And that’s how modern video game artificial intelligence works.

Optimal game AI example — F.E.A.R.

Old FPS F.E.A.R. has very smart bots, that behave like real persons. They push the player out of cover with grenades, press him to the ground by firing in turns and often flank him. And the most exciting thing is that the bots are unpredictable. The average player can kill them only because he has more HP, more suitable weapons and slo-mo mode.

Bots from F.E.A.R. use the next approach. The level is divided into arenas where the player will encounter the bots. Arenas are divided into zones: covers, paths, corners and open areas. While in fight, bots are communicating with each other every 5-10 seconds. Bot #1 runs the Monte Carlo Algorithm, decides that among three random options the best one is to take cover. He says to other bots what he is planning to do. Bot #2 knows, that he can’t take that cover, so his Monte Carlo run won’t include the branches which start with “take that cover”. That’s why F.E.A.R. bots doesn’t do things simultaneously and act unpredictable.

Meanwhile, in modern FPS bots are dumb. They can only move in predefined area, hide in cover and sometimes shoot back. The reason of their bland behavior is that the developers don’t want or don’t have resources to develop serious AI based on Monte Carlo Trees. They use simple Final State Machine. Sometimes it’s enough. For example, in Call of Duty and Battlefield the single player and bots are there only to show game mechanics and weapons.

How to develop a video game AI

The best way to make a video game artificial intelligence is to describe the decision picking algorithms on paper and then turn them into code. To do this the developer has to set a goal.

For example, in a Starcraft-like strategy the goal is to destroy the enemy base. To do so, the player has to mine gold, build barracks, hire army and send it to the enemy base. So, the AI has to the same thing. At first, the AI will decide how many workers to send to the mine. Then it will decide what is better: to build first barracks or to hire more workers to mine more gold. Then — to build more barracks or to hire a soldier. And after every hired soldier it will decide between these options:

  • mine gold;
  • build barracks;
  • hire soldier;
  • send army to the enemy base.

In a real strategy game with dozens of buildings, units and resources the choice will be tougher. The AI will have to build the defense, to set the economy, to recon the player base and so on. But how the AI will know what is the best decision on any given moment? Because the developer sets the final goal.

For example, in the strategy game it is enough to hire 10 soldiers to win the war. Then the AI will calculate the fastest way to achieve it: to send all workers into goldmine and immediately hire new workers, then at some point to build the barracks and hire a soldier when possible. The AI has a great to-do list, but can’t access it freely. Instead, it takes a few random options and then executes the best one.

More complex games require more complex AI. For example, Dark Souls and other third person action games use simple Final State Machine: if the player is close — melee attack, if the player is far — run to the player. But in strategy games AI has to operate with dozens of variables and calculate hundreds of Monte Carlo Branches. Just look at the Europa Universalis interface! Only AI can properly manage this amount of information.

europa universalis AI

Hire us to outsource the game AI development

We are Kreonit game art and development outsourcing studio. Our programmers are skilled with algorithms and AI suitable for all genres, from simple Tic-Tac-Toe games to complex strategies, from slow souls-like games to racing games.

If you don’t know how to develop AI for a game or are struggling with it — fill the brief below. We will help you with advice or write the code and work on your project with you.

PLEASE, RATE MY ARTICLE :)

6 of votes

Post views:
2438

Our game development studio is based in London. With over 13 years of expertise in design, marketing, 3D animation, and programming, we are a cornerstone of the koloro.group of companies. We craft games tailored for clients and also passionately drive our in-house projects. Our commitment is clear – delivering premium content and deriving revenues from games, all while adhering to the highest moral standards and valuing people’s interests. If you’re looking to craft magnificence and reap monetary rewards, we’re your destination.

GET A TOUCH

Send us a message via messenger or email