Graph grammar-based controllable generation of puzzles for a learning game about parallel programming
Josep Valls-Vargas, Jichen Zhu, Santiago Ontañón · 2017
In the context of a learning game to teach parallel programming, we describe a procedural content generation (PCG) approach that can be controlled to generate programming puzzles involving a desired set of concepts, and of desired size and "difficulty". Our approach is based on grammars to control the generation of the puzzle structure, and orthographic graph embedding techniques to render it into a two-dimensional grid for our game. The proposed PCG system is designed to work with a player model in order to provide personalized learning experiences. We present an evaluation of the variability of the generated puzzles using several metrics including challenge and solvability as evaluated by a custom-build model checker. Our evaluation shows that this PCG system can generate a large number of varied puzzles but it is still not able to generate puzzles with certain aesthetic and functional qualities found in puzzles generated by human authors.