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

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

Fausto Mourato (Escola Superior de Tecnologia, Instituto Politécnico de Setúbal, Setubal, Portugal & CITI, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, Lisbon, Portugal), Fernando Birra (CITI, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, Lisbon, Portugal) and Manuel Próspero dos Santos (CITI, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, Lisbon, Portugal)
DOI: 10.4018/ijcicg.2013010104
OnDemand PDF Download:


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.
Article Preview


Procedural Content Generation (PCG) is an interesting topic in videogames research, which includes different computer science areas such as artificial intelligence, human-computer interaction, among others. It is a pertinent topic as it allows independent developers and small companies to overcome the issue of lack of resources to design game environments from scratch.

The increase of mobile and casual gamming expanded even more the videogame market, which brought additional opportunities to that kind of development. Furthermore, automatic generation processes promotes content adaptation to the user profile, allowing the creation of a level to fit certain preferences, the user skill or other features. Also, PCG brings several interesting challenges to researchers regarding the generation algorithms and all the features that have to be taken into account, such as physical validity, visual aesthetics, game flow and contexts, among many others. In this work, we focus PCG in platform videogames. In this genre, the user controls the movement of a character (or various users control their respective characters, for multiplayer games) in a scenario, performing jumps to avoid terrain gaps and traps and overcoming opponents in a simple manner, such as jumping over the enemy or shooting him with a certain weapon.

Regarding PCG, this type of videogames are interesting to study because its mechanics raises several non-trivial questions in the process of automatic level creation. At first, it is important to ensure that the gaming elements are positioned to provide a valid level where the user can fulfill a goal. In addition, the element positioning must make sense as a whole, resulting in a visually plausible scenario. Also, the level has to represent an appropriate rhythmic set of actions that the user should complete in order to keep him/her engaged. Finally, it is important to take into account that those actions represent a challenge with a certain difficulty that has to be perceived and estimated.

Concerning user interaction, this kind of games is also interesting as it is a genre that is suitable for all types of gameplay and gamers. For instance, classic titles such as Sonic: The Hedgehog (“Sonic – the hedgehog,” 1991) or Super Mario Bros. (Miyamoto & Tezuka, 1985), which were designed initially to be difficult and suitable especially to expert players, have recent adaptations based on cooperative play, transforming this genre in some kind of contemporary family games.

In the scope of this work, the following platform videogames will be referred in order to support our tests and examples:

  • The original version of the videogame Prince of Persia (Mechner, 1989), which has unofficial level editors and technical details available online (Calot, 2008), as well as the recently released source code for the original Apple version of the game (Mechner, 2012). This videogame has already been considered in research on the topic of computational complexity (Viglietta, 2012).

  • Infinite Mario Bros., an open-source platformer inspired by the classic videogame Super Mario Bros., which has been used frequently in academia, namely in the development of intelligent agents to control the main character (Togelius, Karakovski, & Baumgarten, 2010; Karakovskiy, & Togelius, 2012) and automatic level generation (Shaker et al., 2010). Recently, it was adapted to use different game art based in the platform game Super Tux (“Supertux,” 2010), assuming the new name Infinite Tux.

  • XRick (“XRick”, 2001), an open-source remake of the original videogame Rick Dangerous (“Rick Dangerous,” 1989), which combines the free movement of Infinite Mario Bros. with closed environments similar to those in Prince of Persia.

  • Tux Likes You, our adaptation of Infinite Tux to record gameplay data and use the generators that we present in this article, among other implementations based on some of our preceding studies.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 7: 2 Issues (2016)
Volume 6: 2 Issues (2015)
Volume 5: 2 Issues (2014)
Volume 4: 2 Issues (2013)
Volume 3: 2 Issues (2012)
Volume 2: 2 Issues (2011)
Volume 1: 2 Issues (2010)
View Complete Journal Contents Listing