Fahreza, Akmal Zidan (2026) Application of Graph Grammar Method to Procedural Level Generation with Conditional Access Mechanism in 2D Platformer Games. Undergraduate thesis, UPN Veteran Jawa Timur.
![[img]](https://repository.upnjatim.ac.id/style/images/fileicons/text.png) |
Text (Cover)
22081010163-cover.pdf Download (2MB) |
|
Text (Bab 1)
22081010163-bab1.pdf Download (2MB) |
|
Text (Bab 2)
22081010163-bab2.pdf Restricted to Repository staff only until 7 September 2028. Download (6MB) |
|
Text (Bab 3)
22081010163-bab3.pdf Restricted to Repository staff only until 7 September 2028. Download (10MB) |
|
Text (Bab 4)
22081010163-bab4.pdf Restricted to Repository staff only until 7 September 2028. Download (24MB) |
|
Text (Bab 5)
22081010163-bab5.pdf Download (988kB) |
|
Text (Daftar Pustaka)
22081010163-daftarpustaka.pdf Download (2MB) |
|
Text (Lampiran)
22081010163-lampiran.pdf Restricted to Repository staff only until 7 September 2028. Download (616kB) |
Abstract
Procedural Content Generation (PCG) is an approach that can be used to generate game content automatically, including game levels. One challenge in procedural level generation is producing a consistent gameplay flow that can be translated into a playable physical layout. This research aims to implement the Graph Grammar method to produce a logical structure for a 2D platformer game, translate the graph structure into chunk-based physical levels, and measure playability using Breadth First Search (BFS) validation. The Graph Grammar method is applied through three generation rules: Linear Expansion, Branching, and Key-Lock Mechanism. The resulting graph structure is converted into a physical level by mapping each node into a chunk and each relationship into a connection between spaces. Level validation is based on two criteria: the successful stablishment of the Key-Lock mechanism and BFS successfully finding a path from the Start node to the Goal node. Testing was conducted using four scenarios of 10, 20, 30, and 50 iterations. The results showed validity levels of 95% for 10 iterations, 99% for 20 iterations, and 100% for 30 and 50 iterations. Failures were mainly caused by the Key-Lock mechanism being unable to form due to limited free space in dense level structures. Overall, the results demonstrate that the Graph Grammar method can generate consistent 2D platformer levels, translate graph structures into chunk-based levels, and achieve high playability based on the applied validation criteria.
| Item Type: | Thesis (Undergraduate) | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Contributors: |
|
||||||||||||
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science Q Science > QA Mathematics > QA76.6 Computer Programming |
||||||||||||
| Divisions: | Faculty of Computer Science > Departemen of Informatics | ||||||||||||
| Depositing User: | Akmal Zidan Fahreza | ||||||||||||
| Date Deposited: | 07 Sep 2026 01:44 | ||||||||||||
| Last Modified: | 07 Sep 2026 01:56 | ||||||||||||
| URI: | https://repository.upnjatim.ac.id/id/eprint/59959 |
Actions (login required)
 |
View Item |