Many games procedurally generate significant portions of their environments, gameplay, and even narrative. Generated game environments are not new; roguelikes and other games using procedural content generation (PCG) have existed since almost the inception of the medium. Recently, however, high-profile titles such as No Man’s Sky, Fortnite, and Shadow of War have relied heavily on PCG.

With this focus on generativity, there is a need for improvement and research in designing and building compelling, capable AI agents to populate their complex, generated worlds. We are experimenting with one approach to help designers build more comprehensive and robust AI that may be more capable of tackling decision-making in generated environments.

The AI for Fortnite was one of the subjects of a GDC talk (Isla and Abercrombie 2016) about the challenges and possible approaches for AI in a generated environment, focusing on movement and pathfinding. These are important problems, and tractable ones for which the Fortnite team found solid solutions. However, the agents in question were limited to movement and combat behaviors. For generative games to become more inclusive and expand into new genres, we need to develop affordances beyond those, building more compelling narratives and enabling creative gameplay and problem-solving for players.

To begin to approach these problems, we are building on research on evolving behavior trees (Perez et. al. 2011). Our approach applies genetic programming to modify hand-designed behavior trees, a commonly used architecture for controlling game AI agents. By starting from designer-specified behavior trees, and then generating evolutionarily advantageous improvements to them for unforeseen situations, we hope to retain designers’ goals for their agents while building more robust behavior for generated environments.

Genetic programming is a technique for evolving trees, usually applied to “parse trees” for computer programs (Poli et. al. 2008). It naturally maps to behavior trees, which operate much like simple programs. Therefore, we built a genetic programming system for Unreal Engine 4’s behavior trees. The details are outside the scope of this article. However, the process involves mapping the behavior trees into a “library” of possible node types, simple crossover and mutation operators, which swap nodes between trees and randomly replace nodes with other known node types, and a fitness function to evaluate the resulting trees. We use a sped-up version of real gameplay for evaluation.

To test this system, we generated behavior for “zombie” AI agents in the open-source “Epic Survival Game” by Tom Looman. We removed functionality for chasing and attacking from the zombies’ behavior trees, but provided a library of useful nodes to our evolutionary algorithm. We found that, within a few generations, zombies would learn to chase the player and patrol the area. At first, some zombies would attack the player briefly, then turn and run away. By adding the size of the tree as a fitness penalty, we found that the efficiency and simplicity of the trees would improve over time, until most zombies exhibited consistent chasing behavior. Although this was a very simple test environment, we believe that future iteration will allow us to generate behavior for more varied and complex agents. Our next step will be to separate our system into a generic library for behavior tree evolution in Unreal Engine 4 so that it can be tested with more games.

In the future, we will need to perform further research to make our system easier to use for designers. We will need to provide visualizations and user-friendly tools for designers to understand, select between, and debug the resulting behavior trees. If designers feel that their control is infringed too heavily by generative tools, they are unlikely to trust and use them. Moreover, defining effective fitness functions for complex agent behavior is a difficult and under-studied area of game AI research. We will need to develop new methods for defining and tweaking fitness functions and controls for gameplay evaluation in order to make this tool accessible. Finally, we need to be able to test generated agents in realistic gameplay environments, which means developing models of player behavior with which to train the agents. Only by combining effective player models, generative worlds, and designer-friendly tools can we enable responsive AI that works with humans to create a more inclusive, expansive future for games.

Acknowledgements

Thanks to Isha Srivastava and Alex Grundwerg, who contributed code and ideas to this project.

References

Isla, Damian, and John Abercrombie. 2016. “AI For Generated Worlds.” presented at the Game Developers Conference. https://gdcvault.com/play/1023418/AI-For-Generated.

Perez, Diego, Miguel Nicolau, Michael O’Neill, and Anthony Brabazon. 2011. “Evolving Behaviour Trees for the Mario AI Competition Using Grammatical Evolution.” In Applications of Evolutionary Computation. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-20525-5_13.

Poli, Riccardo, William B. Langdon, and Nicholas Freitag McPhee. 2008. A Field Guide to Genetic Programming. Lulu Enterprises, UK Ltd.