Melola Discovery

← Melola Discovery

Open access Jurnal SINTA 2

Progressive Content Generation Based on Cyclic Graph for Generate Dungeon

IJCCS (Indonesian Journal of Computing and Cybernetics Systems) · Vol. 17 No. 1 (2023) · pp. 91–102

DOI
10.22146/ijccs.81178
ISSN
2460-7258, 1978-1520
Published
2023-02-23
Publisher
IndoCEISS in colaboration with Universitas Gadjah Mada, Indonesia.
Language
eng
License
creativecommons.org/licenses/by-sa/4.0

Abstract

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.

Keywords

Collaboration network of the authors

10 authors · 14 co-authorship links

Hover or tap a name to highlight its co-authors. Double-click to open the author's page.

  • Universitas Gadjah Mada
  • Different organisations
  • Same organisation
  • Affiliation unknown
  • Thicker line = more joint articles · bigger circle = more articles
Show as table
Co-authorOrganisationJoint articles
Muhammad Zha'farudin Pudya WardanaUniversitas Gadjah Mada1
Hizbullah HamdaUniversitas Gadjah Mada1
Sri MulyanaUniversitas Gadjah Mada1
Arie KurniawanUniversitas Gadjah Mada1
Retantyo WardoyoUniversitas Gadjah Mada1
Doni SetyawanUniversitas Gadjah Mada1
E. Elsa Herdiana MurhandarwatiUniversitas Gadjah Mada1

Affiliations come from OpenAlex; journal OAI-PMH metadata carries none. Authors without an OpenAlex ID are matched by name, which can merge or split people.

Metadata source: OAI-PMH (metadata jurnal) https://journal.ugm.ac.id/ijccs/oai, first harvested 26 Okt 2026, last seen 26 Okt 2026.
Original metadata (oai_dc) 
<oai_dc:dc xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/  http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
	<dc:title xml:lang="en-US">Progressive Content Generation Based on Cyclic Graph for Generate Dungeon</dc:title>
	<dc:creator>Anshar, Muhammad</dc:creator>
	<dc:creator>Sumiharto, Raden</dc:creator>
	<dc:creator>Wibowo, Moh Edi</dc:creator>
	<dc:subject xml:lang="en-US">Computer Science</dc:subject>
	<dc:subject xml:lang="en-US">Generative Grammars, Graph, Procedural Content</dc:subject>
	<dc:description xml:lang="en-US">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.</dc:description>
	<dc:publisher xml:lang="en-US">IndoCEISS in colaboration with Universitas Gadjah Mada, Indonesia.</dc:publisher>
	<dc:contributor xml:lang="en-US">Universitas Gadjah Mada</dc:contributor>
	<dc:date>2023-02-23</dc:date>
	<dc:type>info:eu-repo/semantics/article</dc:type>
	<dc:type>info:eu-repo/semantics/publishedVersion</dc:type>
	<dc:type xml:lang="en-US"></dc:type>
	<dc:format>application/pdf</dc:format>
	<dc:identifier>https://journal.ugm.ac.id/ijccs/article/view/81178</dc:identifier>
	<dc:identifier>10.22146/ijccs.81178</dc:identifier>
	<dc:source xml:lang="en-US">IJCCS (Indonesian Journal of Computing and Cybernetics Systems); Vol 17, No 1 (2023): January; 91-102</dc:source>
	<dc:source>2460-7258</dc:source>
	<dc:source>1978-1520</dc:source>
	<dc:language>eng</dc:language>
	<dc:relation>https://journal.ugm.ac.id/ijccs/article/view/81178/35784</dc:relation>
	<dc:rights xml:lang="en-US">Copyright (c) 2023 IJCCS (Indonesian Journal of Computing and Cybernetics Systems)</dc:rights>
	<dc:rights xml:lang="en-US">http://creativecommons.org/licenses/by-sa/4.0</dc:rights>
</oai_dc:dc>