Using Graph-Based Analysis to Enhance Automatic Level Generation for Platform Videogames

The combination of graph representations with level geometry provide additional information that can enhance automatic level generation processes. In particular, perceiving the main paths that are represented in a certain geometry allows content adaptation to apply certain game design patterns, such as the existence of path detours or the inclusion of optional content. This article explores that approach for the specific genre of platform videogames, focusing the adaptation algorithm that the authors have developed. Starting with a primal level structure and a corresponding graph that sketches the user path, our algorithm detects mandatory and optional path sections and adapts them in order to create more elaborate challenges to the user, forcing detours to gather specific objects or trigger certain events. In addition, the authors present the graph related analysis that support the referred algorithm. Their experiments showed interesting results on some popular games, where it is possible to observe the previous principles put into practise. The approach is generic and can be expanded to other videogames where similar graph structures can be used.