AI in games

Enemy AI, those pesky buggers that make games so much harder but so much fun? How exactly do they manage to react to your movements in the game despite only being made up of a computer?

from the game F.E.A.R

They find you using pathfinding. A simple AI technique found in most games which finds the optimal way of moving an entity (such as enemies) from point A to point B while avoiding obstacles and reducing cost.

Now there are different types of pathfinding, the three most common examples are:

1. Breadth first search, where the ‘search’ emanates from a node to its neighbors constantly expanding until it finds the destination. It’s not very fast and gets slowed down by obstacles

to see more simulations like this, go to PathFinding.js

1. Dijkstra’s algorithm emanates from a node as well, but operates on a weighted graph and assigns cost values to neighboring nodes of the starting point. It then selects the node with the lowest cost and repeats the process with this new node as the central node. It always goes to the lowest cost node (which might make it go in the wrong direction)
2. A* algorithm, the most efficient algorithm uses a combination of techniques. It favors nodes that have lower cost, but simultaneously favors the nodes that are closer to the goal. This having an idea of the goals location is called a heuristic. This allows for the search to always move towards the goal with a path that has the lowest cost, and avoids Dijkstra’s problem of going in the wrong direction.

The grey blocks represent obstacles that A* must navigate to reach the goal.

Now what exactly do I mean when I say pathfinding occurs on a graph? The graph is essentially the world in which pathfinding occurs, and is often called a navigation mesh (navmesh for short). Pathfinding implemented in its simplest form is done on a 2 dimensional plane, and entities move on either the faces (most common), edges, or vertices.

Varying cost values can be implemented on the graph to show changes in terrain. For example, mountainous areas on the graph could be assigned higher cost values than roads on the map. Cost functions could also vary depending on the entity being moved to make game mechanics more realistic, an example of this would be a larger entity having higher costs assigned to it changing altitude

Neural networks, a more traditional form of AI can be implemented in pathfinding. Neural networks can be useful for cost function approximation when it varies from game to game. After playing multiple times it could come up with better and better paths by putting the measurements of cost each time into the neural network and taking into account its past attempts.

Now, knowing how entities in games move is cool and everything, but how does enemy AI respond to your in game actions? They do it using Finite State Machines and behavior trees.

Finite state machines are a system of defined states that can be transitioned between. These transitions are triggered by conditions that must be met, and these conditions are met with input events.

There are two different types of FSMs, deterministic and non-deterministic. The name is pretty self explanatory, deterministic FSMs have a predictable outcome, while non-deterministic FSMs do not. For enemy AI, non-deterministic FSMs are more ideal because having completely predictable enemies with obvious state sequencing isn’t very fun to play against in most scenarios.

Deterministic FSM example

The industry has started moving away from FSM because they don’t scale well. The more states in the system, the more transitions will need to be coded and that causes a very labor intensive process.

So instead, many developers opt for behavior trees

Behavior trees are similar to Finite State Machines in that they’re a way of structuring the transition between different tasks/actions. Behavior trees allow for the design of modular systems, where certain actions can be integrated into larger actions. Essentially, they break down a complex task into smaller and smaller tasks.

When we refer to connected nodes, the terminology ‘parent’ and ‘child’ are used. Root nodes have no parent, selector nodes have both a parent and child nodes, and execution nodes don’t have child nodes.

There are traditionally four different types of selector nodes…

The selector nodes constantly checks on the status of execution nodes to see if they’ve succeeded, failed, or still running (this update is called a tick). This allows for a behavior tree to be reactive and respond to changes.

There are also two different execution types, one is called an action and the other is a condition the program has to meet.

Now it might be a bit unclear as to why behavior trees are preferred for more complex tasks, but instead of explaining let me just show you…

Heres a fairly simple behavior tree

Now let’s see what it would look like as a hierarchical FSM (regular FSMs won’t really work to express the modular aspect of the above diagram).

take it from the person who drew this, its much more complicated than the behavior tree

And there really isn’t a whole lot of complicated AI concepts behind most video games. Enemy AI in games is quite limited, it can’t be too advanced, or else it’d worsen the gaming experience for the player.

Enemy AI with too much free reign could cause unpredictable scenarios that could worsen user experience for a player. Successful game design makes so that the player feels as if they’re playing against an intelligent enemy, when really they’re not.

So now you know what goes on behind enemy AI: Pathfinding, FSM, and a healthy amount of deception.

Despite games being really good so far, theres always room to grow, and AI can help the future of gaming become a reality

Let’s look at some of the benefits emerging AI could have on the future of games

• Generating games without a game engine using GANs. NVIDIA has already made this possible, using their GameGAN (trained on 50,000 episodes of the game Pac-Man) to recreate Pac-Man without using a game engine.
• Allowing for NPCs to provide a larger variety of dialogue responses to character actions can be done using GPT-3 to generate believable text, and Deepmind’s wavenet algorithm can generate audio from that text. This will make the NPCs seem more realistic and making the world more interactive.
• Animating the above generated dialogue using a CNN (Convolutional neural network) trained on videos of characters speaking. Emotion can also be applied to the animation, allowing it to better correspond with the dialogue

With time, its inevitable that this technology will develop enough to become widely useful in a number of fields, including gaming.

TL;DR:

• Enemy AI entities in games commonly use pathfinding to reach its target location and navigate around obstacles
• There are many different pathfinding algorithms, A* is most efficient (and its widely used)
• Enemy AI use Finite State Machines or Behavior Trees to make decisions that correspond to the player’s actions.
• Behavior trees are simpler than FSM, and follow the common tree data structure
• Emerging AI could make games much higher quality, and could make for a more immersive experience for the player.

Here are the sources I learned all of this from, highly suggest checking them out if you want to delve deeper into these topics:

freeCodeCamp.org. 2020. Understanding State Machines. https://www.freecodecamp.org/news/state-machines-basics-of-computer-science-d42855debc66/

Stout, B., 1999. Gamasutra — Smart Move: Intelligent Path-Finding. https://www.gamasutra.com/view/feature/3317/smart_move_intelligent?print=1 [Accessed 28 December 2020].

Web.archive.org. 2001. The Clash Of Civilizations — Map Generator. http://web.archive.org/web/20091104094002/http://clash.apolyton.net/models/Model-MapAI.shtml

Li, J., Monroe, W., Shi, T., Jean, S., Ritter, A. and Jurafsky, D., 2017. Adversarial Learning For Neural Dialogue Generation. https://arxiv.org/pdf/1701.06547.pdf

Patel, A., 2020. Amit’S A* Pages. [online] Theory.stanford.edu. http://theory.stanford.edu/~amitp/GameProgramming/#S1

Colledanchise, M. and Ogren, P., 2020. https://arxiv.org/pdf/1709.00084.pdf

Thibaud, 2020. Using Openai’s GPT-3 To Enrich NPC Interactions. [online] Blog.writtenrealms.com.https://blog.writtenrealms.com/gpt3/

Statt, N., 2019. How Artificial Intelligence Will Revolutionize The Way Video Games Are Developed And Played. The Verge. https://www.theverge.com/2019/3/6/18222203/video-game-ai-future-procedural-generation-deep-learning

PS: I skipped over a major application of AI in games… physics systems

But don’t worry! I’m planning on doing a separate article on it, look forward to seeing you there!