TLDR
AI and ML has proven to be skilled in its mastery of playing video games. From beating grand master chess players to eventually mastering the strategy game, Go, the limitations of what machines can do are seemingly endless. Yet, AI/ML integrations into video games have remained unchanged since the first few games hit the market. While the complexities of AI have grown, their core functions remain the same. However, with emerging technologies, the integration of AI in video games shows a promising future.
Outline
Pathfinding
Finite State Machines
Behavior Trees
Limitations of Neural Networks
Procedural Generation
Conclusion
Pathfinding
In many video games, AI/ML comes in the form of NPCs (non-player characters) moving around the game map. Pathfinding allows NPCs the understanding of how best to navigate this game map based on a set of given constraints. These systems first determine the start and end of their path; then will determine a series of points that will get them to their
Directed pathfinding AIs don’t blindly wander throughout the map, instead, they are given some method of processing their space. Similar to a
, the game map is built on a series of nodes which the directed pathfinder processes and then chooses the best node possible for its intended function. The most commonly used pathfinding algorithm used in gaming is A*. A* (a-star) assesses the best direction for it’s path and finds the shortest path between two points.
Despite their benefits and widespread usage, there are limitations to pathfinding and A*. World building can be difficult when using pathfinding as the NPC’s path is created early on in the processing stage. As a result, it can be difficult to add new elements to a game, such as a rock or tree, without the NPC not recognizing these objects and walking right through them. Moreover, using A* also doesn’t scale well as the processing speed quickly declines as more NPCs are created.
A possible solution to the shortcomings of pathfinding is the integration of machine learning and
. With further integrations of machine learning, pathfinding could allow for generalizations of situations which didn’t occur during the early processing phases (or training phase). By training an ML model using a human player, the AI can initiate what is observed. Then through thousands of rounds of training, the ML model will eventually learn and perform the desired behavior. So if more elements were added in the game later, such as a rock or tree, the NPC will understand it needs to go around these objects.
Finite State Machines
Finite state machines (FSM) are models used to simulate simple sequential logic. When a player performs an input based on a series of actions, the software drives the NPC to perform a certain action or output. The NPC will remain in this state until it’s signaled by another input to change.
There are two main types of finite state machines: deterministic and non-deterministic. Deterministic FSMs read an input and can only transition to one other state. Non-deterministic FSMs occur when it reads an input and can transition to multiple different states. The latter approach can lead to much more realistic behavior in games.
PAC-MAN uses non-deterministic FSMs to operate how the ghosts move throughout the game. Each ghost operates in a slightly different way — all with the same goal of following the player. When the player obtains an energizer (changes the ghosts to blue, allowing them to be eaten), the ghosts change states to avoid the player.
While FSMs can bring a lot of NPC interaction within a game, they don’t scale well as the number of interaction transitions increase. The more complex your game becomes, the more unique states your game needs to capture and maintain.
Neural networks follow a similar structure as FSMs but are able to learn from past data to improve themselves. The elements of consistency and predictability are holding back the implementation of neural networks in gaming. We’ll touch on this more in the sections below.
Behavior Trees
In lieu of more complex ML, video games are heavily reliant on behavior trees to navigate how NPCs navigate and move throughout the game and provide an answer to the shortcomings of FSMs. Behavior trees share a similar data structure to decision trees — series of nodes which dictates what can occur and in what order. The node at the top of the tree is the “parent” and any node that is linked below is its “child”. As the player interacts with an NPC, the behavior tree is triggered to execute a certain node which then triggers a series of other nodes based on previous actions.
The majority of AI behaviors that take place on behavior trees are at the “leaf” of the tree — these behaviors can be shooting an enemy, running from danger, etc. Composite nodes control the sequence of how the tree is run, decide what action to execute based on a given input action, and can have more than one child node. Decorator nodes can only have one child and will only execute one action.
Trees give developers greater freedom to develop complex behaviors in a more organized way than with FSMs. As the system scales, behavior trees remain easier to follow than with FSMs which not only make designing them easier, but finding bugs as well.
While behavior trees are an extremely popular and functional tool in gaming, they aren’t on par with the complex AI/ML processing tools in other types of technology.
Limitations of Neural Networks
have experienced a rise in popularity and usability in nearly every tech sector. Video games however have been reluctant to adopt this technology. One reason for this is predictability and control within the game. Video game developers like to know what their players will experience. When implementing AI, they need the AI to be predictable by using systems like pathfinding, finite state machines, and behavior trees. Games would experience a great amount of unpredictability if developers were to implement a neural network that learned from the players behavior. This could make the game too difficult to get through or cause the NPCs to undergo behaviors that don’t fit within the storyline of the game.
Procedural Generation
One way neural networks are being used in video games is through procedural generation. Procedural generation is the process of a computer randomly creating content. They use neural networks to learn from and replicate data. Video games, such as Minecraft, use procedural generation to create a seemingly infinite number of new worlds; allowing players to interact with new aspects of the game for years.
Advancements in AI have made procedurally generated worlds in gaming much more realistic. Further advancements in this technology will allow game developers to create new games much quicker without sacrificing the quality of the game.
Conclusion
AI powered video games have come a long way from the days of them beating grandmasters of chess. The AI research and development company OpenAI created the machine learning project OpenAI Five — a team of video game bots whose purpose was to play against professional human players in
(a video game which favors working as a team). The project was successful and showed how machine learning could successfully use collaboration to achieve a common goal.
Video games have used AI since the beginning of video game development. The industry has built its gaming systems on improving upon the same software and algorithms. The implementation of emerging AI technology has the potential to change the gaming industry as it could mean more dynamic and exciting experiences for gamers.