Evolving Cellular Automata Rules for Maze Generation

Maze running games represent a popular genre of video games and the automated designof playable mazes thus provides an interesting research challenge for computationalintelligence research in games. The ability to automatically create levels would be ofparticular benefit to maze running games as they require a large number of mazes pergame. The automatic generation of mazes removes a large time bottleneck in mazerunning game development, the manual creation of mazes by expensive designers. Wetherefore attack the problem of automatically designing mazes using a genetic algorithm.However a genetic algorithm requires measuring the quality of the generated mazes inorder to function. This poses a problem as human players have differing opinions on whatmakes mazes enjoyable. We therefore first have a human user acting as a fitness functionguide an interactive genetic algorithm that generates mazes in order to collect data onwhat types of mazes human players find interesting. Analysis of the generated mazesby our human experts led to two properties that appear in mazes that players foundinteresting; path length and number of dead ends. We then created fitness functionsbased upon these properties to guide a non-interactive genetic algorithm.To show the viability of our approach we compared genetic algorithm generated mazesagainst the global optimum found by exhaustive search on a small, though non-trivialmaze generation problem. The genetic algorithm generates mazes on average within 90%of optimal, producing a maze of such quality or better 65% of the time while having afloor level of performance at about 80% of optimum. We then expanded our experimentby creating a new probabilistic representation, increasing the overall search space for ourgenetic algorithm. The probabilistic representation produced mazes that achieved higherfitness scores than even the optimum for our previous experiment. These results provideevidence that genetic algorithms are a viable approach to automatic maze generation inmaze game