Overview

Procedural Content Generation (PCG): Angry Bots is a single player, top-down shooter game that pits a lone soldier against swarms of security robots defending each map. However, what distinguishes this game is that every map is procedurally generated and, most importantly, is designed to match the preferences and skill of an individual player. The game gives the player an infinite number of maps to play, allowing the player to control the layout of the each map through interactive evolution while the arrangement of content (i.e. enemies and pickups) is optimized to maximize the player’s enjoyment.

Features

Demo Site


Algorithm Details

PCG: Angry Bots is an experiment in Experience-Driven Procedural Content Generation in
which the content we focus on is maps (or “levels”) for a top-down shooter. For generating the
maps, we break the process into two separate processes: generating the Geometry of the map,
followed by generating the Content to populate the map.

Geometry: The term “Geometry” refers to the physical layout of the walls, floors, and doors of
the map, encompassing the area that the player navigates through while playing the game. In
this implementation, the Geometry is represented as a Fixed n-Tree (more specifically a Fixed
3-Tree) where each node in the tree is a room and each edge is a corridor that connects the
rooms. The rooms and corridors are pre-designed building blocks that need only be connected
to each other. The root node is a starting room (where the player first enters the map) and
exactly 1 leaf node is an exit room (which the player must try to reach to complete the map).
Each node has only 1 parent and therefore there are no circular paths through the tree and
there is 1, and only 1, path from the start room to the exit room.

The reason a 3-Tree is used is that currently there are no rooms with more than 4 doors; 1 door
connects to the room before it (the parent node) and the other 1 to 3 doors connect to the rooms
after it. The term “Fixed” means that once a node is put in the tree, it’s coordinates relative to
nodes at the same depth never change, even if other nodes are removed. An example of a map
is shown in Figure 1, where node S is the starting room, node E is the exit room, and all other
nodes are labelled with a [depth, sibling number] coordinate. With this representation, if node
[2,0] is removed, for example, nodes [2,1], [2,2], and [2,3] do not shift left, their coordinates stay
the same. This representation becomes important later when Content placement is explained.

The Geometry of maps is procedurally generated using an Interactive Evolution with a
population of 8 maps. When a new player account is created, the first generation of maps
is generated randomly. The player is then shown a preview of all 8 maps and they choose
which map they would like to play next. This chosen map is then the single parent for the next
generation, which is mutated by adding and removing nodes in the tree (with each node given
a randomly generated probability of mutation) to create 7 more offspring in the next generation.
Interactive Evolution is sufficient here to capture the player’s preferences as the previews of the
maps clearly show the size of the map, the types of rooms that will be experienced, and how
many branching paths the map has.

Content: The “Content” of a map is all of the objects a player will interact with in the map. In
this game, there are 6 types of content that can be separated into 2 categories; enemies and
pickups. Enemies: Spider Bots, Buzz Bots, Mechs. Pick-ups: Health, Ammo, New Weapons. A
setting value of None, Low, Medium, and High is then given to each content type in each room
to specify the quantity of that content. These values are used to better discretize the amount of
quantity in each room.

The process of procedurally generating the Content for a map is, therefore, a process of
stepping through the map the player chose through Interactive Evolution, and deciding the
setting value for each content type in each room. As this is detailed information that we cannot
expect our player’s to comprehend easily, Interactive Evolution is not ideal here. Instead, we
frame the Content placement as Recommender System problem in which a model of each
player’s preferences is built by requiring them to rate each map that they play on a 1-6 star
scale. After a player has played a handful of maps, the system should be able to discern the
player’s preferences and “recommend” the Content layout for the next map.

To achieve the aforementioned, we use a combination of a Naive Bayes (NB) classifier and
a Compositional Pattern Producing Network (CPPN) evolved through Neuroevolution of
Augmenting Topologies (NEAT). Once a Geometry has been chosen through Interactive
Evolution, a population of 50 CPPN candidates are evolved over 200 generations. The 2 inputs
to a CPPN candidate are the coordinates of each node in the tree and the 6 outputs specify the
Content settings for that node. Once all the Content settings of a map have been calculated
for a single candidate, 16 high-level features about the map (such as the normalized quantity
of each Content and the types of transitions between rooms) are extracted and passed to the
NB classifier. The NB classifier returns a prediction on the probability that the player will enjoy
the map. This value is used as the fitness value for that candidate and the process is repeated
for all CPPN candidates. After 200 generations, the top ranking CPPN is once more combined
with the chosen Geometry and the map is rendered for play. As the player plays more maps and
rates them, the NB classifier becomes more accurate and makes better recommendations on
content layouts.

The NB classifier was chosen because of its reported ability to learn quickly from only a
few examples. We cannot expect a player to experience dozens of maps before providing
acceptable Content layouts and so a classifier that learns quickly was needed. This was backed
up by initial testing with range of classifiers in the WEKA framework, which showed the NB
classifier to perform the best. A CPPN representation was used because it would be ideal for a
pattern to present throughout the flow of the map. For example, a room of high enemies being
followed by a room full of health and ammo, which is followed by another room of enemies.
The Fixed Tree representation insures that minor mutations to the geometry do not change
the coordinates that are fed to the CPPN, which prevents two successive maps with similar
Geometry from having completely different Content layouts (and therefore player experience)
even if the same CPPN is used. Initial experiments on the entire game system have provided
promising results.