Producing content, such as levels, is a demanding and time consuming task. Using procedural content is a proven solution to generating a lot of content in a short amount of time. It has, however, a lot of pitfalls when it comes to living up to the expectations of the player. But what if we could make our generated content self-evolving? What if we could make our games become better over time?

Self-evolving generator

Creating levels procedurally may seem like a good way to reduce development time. However, creating an algorithm that produces a desirable result every time you run it can be just as time consuming as designing a set of levels. A lot of development time goes into evaluating the generated result and adding constraints and checks to make sure the created content is playable. By approaching this validation of the generated content as an optimization problem, we can use existing algorithms to find a solution that fits the anticipated result.

Simple optimization algorithms, such as hill climbing or variations thereof, would be sufficient to find a good solution for a single variable, but in the context of level generation there won’t be a single optimal solution and there are probably multiple variables driving the generation algorithm. Therefor a genetic algorithm might just be what we need to find a solution that is applicable and playable. A genetic algorithm mimics the process of natural selection to find a solution to a problem. A set of solutions is generated and then its fitness is evaluated on how well it solves this problem. The best solutions are then selected and its traits (variables) can be combined to produce new, potentially better, solutions.

Image 1: schematic overview to illustrate the basics of a genetic algorithm applied to levels.

Before we can evolve our levels to become better over time, we first need a procedural content generating algorithm. A generator as such can be a very complex algorithm, but even a simple implementation with only a few variables may be sufficient. The requirement here is that there need to be variables which will allow us to tweak the outcome of the algorithm. These variables will function as the “chromosomes” of the generated solutions and will change every new generation.

The generation

For Captain Collo, I am working on a generator which uses an implementation of cellular automata to generate landmass and rocks on a 2D grid. The landmass and rocks influence the overall gameplay of a level by forming obstacles a player has to maneuver through. The player (and enemies) can shoot over land but not sail through it, but the player cannot shoot through rock formations. After the generation of land and rock formations, suitable places are found to place points of interest such as enemies.

The first few levels are randomly generated. To evolve these levels, the levels must be evaluated and scored on how well they satisfy the player, in other words, how much fun a level is to play. We can then use this score to evaluate how good these levels are and attempt to combine successful features of these levels to produce new, and hopefully better, levels.

But how do we score these levels? How do we know which ones are good or bad? In most genetic algorithms, there is a fitness function that evaluates the generated solution. But it would be very hard to write a function that can interpret the generated levels and assign it a proper score.

Survival of the fitness function

There are examples of games [1], [2] that adapt to player behavior and measure a lot of game statistics and player input to model the player. This player model can then be used to make the game content adapt to this model, either online, on the fly, or offline. This method has a couple of downsides, especially when it comes to portability, meaning it is generally very game specific, but also in creating a model that works. Player modeling, or player profiling, can be too time consuming for indie developers and may not be useful beyond a single game, even though it could be used as an effective fitness function. Due to those limitations, I chose to base the evolution of the algorithm on player feedback.

I want to use explicit player feedback, asking them what they think of the content generated. The levels in my game generally have a short play time. Every time a player finishes a level, they are asked what they think of the level they just played. For the first implementation I will use a 5-star rating system. There are, however, many different ways to ask the player for this feedback. Different approaches would be, for example, to ask the player to rank the levels they play from bad to good, or an even simpler implementation would be to ask whether the player liked the level or not.

Image 2: illustration of the evolution loop.

More research needs to be done to find the best way to get this feedback, without breaking the flow of the game too much. However, the main function of this feedback is to drive the genetic algorithm forward. By the nature of this algorithm, the main reason to ask for this feedback is to eliminate the worst levels, making the player function as the actual fitness function of a generated solution. As long as it allows the best results to endure and reproduce into the next generation of levels, the way we gather that feedback from the player is less important.

Personal or global selection

There is one obvious issue with using player feedback in such a way to drive a genetic algorithm. The idea behind the genetic algorithm is that we can produce solutions by artificial evolution and evolution takes time. When we simulate the complete evolution on a computer, using a written fitness function, we can simulate hundreds or even thousands of new generations in a couple of seconds. With a player driven fitness function, we will have to wait until a generation of levels has been played and scored by the player.

This may form an issue when the genetic algorithm is run solely on one device for one player. It would probably take many a generation until you will see some profound results. Therefore this approach may be better suited to being applied to an entire community of players. By running the genetic algorithm on a server, distributing new levels to the players when they come online, we would be able to retrieve the fitness of a lot of levels in a small amount of time. The evolution would then not generate levels that adapt to a single player’s preference, but it would evolve the game as a whole.

The new generation

In this article I have given you an idea of the potential of using a genetic algorithm in combination with explicit player feedback as a solution to generate a wide variety of levels whiles also generating levels better suited for the player.

To validate this approach, I intend to release a version of the game with a working system like this in place. Initially the proof of concept will have all the basic ingredients in place; a level generation system, the rating system for the player and the genetic algorithm which will produce new solutions based on these ratings. The most important question would be whether or not such a system will produce better results than a generator which generates completely random results.

Ultimately I would like to build an online shared system with a much wider search-space, incorporating not only terrain generation, but also evolving game mechanics in this way. Once such a system is released, it would be very interesting to see in what way a game might evolve and how different that would be from the game that it was at the beginning.

References