Sturgeon-MKIII: Simultaneous Level and Example Playthrough Generation via Constraint Satisfaction with Tile Rewrite Rules
Seth Cooper · 2023
Completability is a key aspect of procedural level generation. In this work, we present a constraint-based approach to level generation for 2D tile-based games that simultaneously generates a level and an example playthrough of the level demonstrating its completability. The approach represents game mechanics as tile rewrite rules, which allows a variety of games and mechanics (beyond simple pathfinding) to be incorporated. The mechanics are represented as constraints in the same problem along with the constraints used to generate the level itself. Thus, the solution to the constraint problem contains both a level and a playthrough of the level. We demonstrate the flexibilty of the system and of tile rewrite rules in several applications, including lock-and-key dungeons, platformers, puzzles, and match-three style games.