Evolved cellular automata for 2D video game level generation

Abstract: Manual design of levels can be an expensive and time consuming process. Procedural content generation (PCG) entails methods to algorithmically generate game content such as levels. One such way is by using cellular automata (CA), and in particular evolved cellular automata. Existing research primarily considers specifically determined starting states, as opposed to randomly initialized ones. In this paper we investigate the current state of the art regarding using CA’s that have been evolved with a genetic algorithm (GA) for level generation purposes. Additionally, we create a level generator that uses a GA in order to evolve CA rules for the creation of maze-like 2d levels which can be used in video games. Specifically, we investigate if it is possible to evolve CA rules that, when applied to a set of random starting states, could transform these into game levels with long solution paths and a large number of dead ends. We generate 60 levels over 6 experiments, rendering 58 playable levels. Our analysis of the levels show some flaws in certain levels, such as large numbers of unreachable cells. Additionally, the results indicate that the designed GA can be further improved upon. Finally, we conclude that it is possible to evolve CA rules that can transform a set of random starting states into game levels.