Progressive Content Generation Based on Cyclic Graph for Generate Dungeon

Muhammad Anshar(1*), Raden Sumiharto(2), Moh Edi Wibowo(3)

(1) Magister Ilmu Komputer Departemen Ilmu Komputer Dan Elektronika, (FMIPA) Universitas Gadjah Mada, Yogyakarta
(2) Departemen Ilmu Komputer dan Elektronika (FMIPA) Universitas Gadjah Mada, Yogyakarta
(3) Departemen Ilmu Komputer dan Elektronika (FMIPA) Universitas Gadjah Mada, Yogyakarta
(*) Corresponding Author


Dungeon is level in game consisting collection of rooms and doors with obstacles inside. To make good level, takes a lot of time. With Procedural Content Generation (PCG), dungeons can be created automatically. One of the approaches in PCG to create levels is progressive. Progressive approach produces timeline as representation of the interactions in the game. Timeline representation that is in the form of one straight line is good for endless runner, but for dungeon, the levels are linear. In this research, the timeline is changed to cyclic graph. Cyclic graph is formed using graph grammar algorithm. This research aims to build dungeon that has not linear and minimal dead ends. To eliminate linearity in dungeons, branching in dungeons needs to be formed. The steps carried out in this research are designing graph grammar rules, generating population of graphs, evaluating graphs with fitness values, and building dungeons. Four functions are used to determine the fitness value: shortest vertices, average duration, replayability, and variation. Dungeons produced with progressive approach manage to minimize linearity in dungeons. Dungeon formation is very dependent on the rule grammar that forms it. With the evaluation process, linear dungeons resulting from grammar rules can be minimized.


Generative Grammars, Graph, Procedural Content

Full Text:



[1] M. Niemann and M. Preuß, “Constructive Generation Methods for Dungeons,” presented at
the Seminar-Thesis in Procedural Content Generation for Games. Westfalische Wilhelms
Universitat Munster, 2015.
[2] B. Lavender and T. Thompson, “The Zelda Dungeon Generator: Adopting Generative
Grammars to Create Levels for Action-Adventure Games,” 2015.
[3] I. Antoniuk and P. Rokita, “Procedural generation of multilevel dungeons for application in
computer games using schematic maps and L-system,” in Intelligent Methods and Big Data
in Industrial Applications, Springer, 2019, pp. 261–275.
[4] J. Togelius, E. Kastbjerg, D. Schedl, and G. N. Yannakakis, “What is Procedural Content
Generation?: Mario on the Borderline,” in Proceedings of the 2Nd International Workshop
on Procedural Content Generation in Games, New York, NY, USA, 2011, p. 3:1-3:6. doi:
[5] N. Shaker, A. Liapis, J. Togelius, R. Lopes, and R. Bidarra, “Constructive generation
methods for dungeons and levels,” in Procedural Content Generation in Games, Springer,
2016, pp. 31–55.
[6] J. Togelius, G. N. Yannakakis, K. O. Stanley, and C. Browne, “Search-based procedural
content generation,” presented at the European Conference on the Applications of
Evolutionary Computation, 2010, pp. 141–150.
[7] M. Shaker, N. Shaker, J. Togelius, and M. Abou-Zleikha, “A progressive approach to
content generation,” presented at the European Conference on the Applications of
Evolutionary Computation, 2015, pp. 381–393.
[8] J. Dormans, “Cyclic Generation,” in Procedural Generation in Game Design, AK
Peters/CRC Press, 2017, pp. 83–96.
[9] D. Karavolos, A. Liapis, and G. N. Yannakakis, “Evolving missions to create game spaces,”
presented at the 2016 IEEE Conference on Computational Intelligence and Games (CIG),
2016, pp. 1–8.
[10] J. Dormans, Engineering emergence: applied theory for game design. Universiteit van
Amsterdam [Host], 2012.


Article Metrics

Abstract views : 775 | views : 769


  • There are currently no refbacks.

Copyright (c) 2023 IJCCS (Indonesian Journal of Computing and Cybernetics Systems)

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Copyright of :
IJCCS (Indonesian Journal of Computing and Cybernetics Systems)
ISSN 1978-1520 (print); ISSN 2460-7258 (online)
is a scientific journal the results of Computing
and Cybernetics Systems
A publication of IndoCEISS.
Gedung S1 Ruang 416 FMIPA UGM, Sekip Utara, Yogyakarta 55281
Fax: +62274 555133 |

View My Stats1
View My Stats2