Search-Based Procedural Generation of Maze-Like Levels

• Published in: IEEE transactions on computational intelligence and AI in games. 2011-09, Vol.3 (3), p.260-273
• Main Authors: Ashlock, D., Lee, C., McGuinness, C.
• Format: Article
• Language: English
• Subjects: Algorithms; Biological cells; Color; Design; Dynamic programming; Evolutionary computation; Fitness; Games; Heuristic algorithms; intelligence and AI in Games; Mathematical analysis; Mathematical models; Representations; search-based procedural content generation; Studies
• ISSN: 1943-068X; 2475-1502; 1943-0698; 2475-1510
• DOI: 10.1109/TCIAIG.2011.2138707

A correctly designed dynamic programming algorithm can be used as a fitness function to permit the evolution of maze-like levels for use in games. This study compares multiple representations for evolvable mazes including direct, as well as positive and negative indirect representations. The first direct representation simply specifies, with a binary gene, which squares of a grid are obstructed. The second paints the maze grid and passage is allowed only between colors that are the same or adjacent in a rainbow. The positive and negative representations are developmental and evolve directions for adding barriers or digging "tunnels." These representations are tested with a design space of fitness functions that automatically generate levels with controllable properties. Fitness function design is the most difficult part of automatic level generation and this study gives a simple framework for designing fitness functions that permits substantial control over the character of the mazes that evolve. This technique relies on using checkpoints within the maze to characterize the connectivity and path lengths within the level. Called checkpoint-based fitness, these fitness functions are built on a menu of properties that can be rewarded. The choice of which qualities are rewarded, in turn, specifies within broad limits the characteristics of the mazes to be evolved. Three of the representations are found to benefit from a technique called sparse initialization in which a maze starts mostly empty and variation operators fill in details while increasing fitness. Different representations are found to produce mazes with very different appearances, even when the same fitness function is used. The example fitness functions designed around dynamic programming with checkpoints are found to permit substantial control over the properties of the evolved mazes.