Puzzle generation for action-adventure games using graph grammars

Abstract

Action-Adventure video games such as The Legend of Zelda provide a variety of challenges to players. These include exploration, combat, and puzzles. The player’s goal within these games is normally to reach a location, but various obstructions prevent the player from reaching it until they are overcome. By intertwining multiple challenges for the player, a puzzle can be made. We document the elements common to puzzles in action-adventure games. A game could be kept interesting indefinitely if the player was presented with new puzzles each time they played. This would be Procedural Content Generation. We design a system based on node replacement graph grammars capable of designing new puzzles like those seen in action-adventure games. Using this system we produce new lock-and-key puzzles. We also show that we can design a grammar that guarantees a solvable puzzle is produced.