Automatic generation and evaluation of platform games

Abstract

A two-dimensional platformer game can be characterized by levels consisting of uneven terrain that requires jumping and climbing to traverse. This study explores the use of graph grammars as a rule system for procedurally generating and evaluating these kinds of games. It follows the technique of separating the objectives or mission of a level from the layout or space of a level into two different domains, where a mission is created following the syntax of a graph grammar and the space is generated based on a mission. During this generation process, both the missions and spaces generated are evaluated directly with the use of search-based evaluation functions and indirectly with an elementary player AI simulation. To evaluate the generator’s capabilities, a simple prototype game using this generation technique was created along with three separate mission grammars. The output levels generated with these grammars were analyzed based on four data properties: linearity, leniency, density, and candidate feasibility. The grammar that showed the most favourable results in terms of feasibility was then tested with a small group of human players to validate the playability of the levels created by the generator. The obtained data showed that the generator is capable of generating playable and engaging levels, but that generating only the missions with a single grammar limits the possibilities of the content generated and makes the position of structures more difficult to validate, indicating that using various targeted grammars in tiny amounts might produce better outcomes.