Implementasi Algoritma Binary Space Partitioning Untuk Procedural Map Generation Dalam Gim

Harits Ar Rosyid; Ahmad Adi Prasetyo

doi:10.30591/jpit.v10i4.8629

Implementasi Algoritma Binary Space Partitioning Untuk Procedural Map Generation Dalam Gim

Harits Ar Rosyid, Ahmad Adi Prasetyo

Abstract

The popularity of games as an interactive entertainment medium continues to grow, with 2D maps playing a vital role in enhancing user experience. Manual map creation is time-intensive, particularly as game worlds become increasingly complex. Procedural Content Generation (PCG) offers a solution by automating map creation, improving replayability, and reducing designer workload. This research explores the use of the Binary Space Partitioning (BSP) algorithm for procedural dungeon map generation, incorporating random connections between rooms to create more exploratory and dynamic maps. The process includes three stages: developing a dungeon map generator, implementing BSP with random room connectors, and validating the generated maps to ensure navigability. Space Syntax analysis, including Visibility Graph Analysis (VGA) and Axial Line Analysis, is applied to evaluate the quality of the maps in terms of connectivity, visibility, and integration. Results show that BSP-generated maps with random connections offer dynamic layouts, while Space Syntax measures reveal that smaller minimum room sizes result in lower integration and connectivity but increase interaction hotspots. This study demonstrates the potential of BSP in generating varied game maps and the utility of Space Syntax for assessing their spatial properties.

Keywords

Procedural Content Generation; Game; Binary Space Partitioning; Game Maps; Space Syntax Analysis

Full Text:

References

P. O. Toups Dugas, N. Lalone, S. A. Alharthi, H. N. Sharma, dan A. M. Webb, “Making Maps Available for Play: Analyzing the Design of Game Cartography Interfaces,” ACM Trans. Comput.-Hum. Interact., vol. 26, no. 5, hlm. 1–43, Okt 2019, doi: 10.1145/3336144.

T. Nordvig Møller, J. Billeskov, dan G. Palamas, “Expanding Wave Function Collapse with Growing Grids for Procedural Map Generation,” dalam International Conference on the Foundations of Digital Games, Bugibba Malta: ACM, Sep 2020, hlm. 1–4. doi: 10.1145/3402942.3402987.

W. L. Raffe, “Personalized procedural map generation in games via evolutionary algorithms,” SIGEVOlution, vol. 7, no. 1, hlm. 27–28, Agu 2014, doi: 10.1145/2661735.2661739.

M. Prachyabrued, T. E. Roden, dan R. G. Benton, “Procedural generation of stylized 2D maps,” dalam Proceedings of the international conference on Advances in computer entertainment technology, Salzburg Austria: ACM, Jun 2007, hlm. 147–150. doi: 10.1145/1255047.1255077.

O. Davoodi, M. Ashtiani, dan M. Rajabi, “An Approach for the Evaluation and Correction of Manually Designed Video Game Levels Using Deep Neural Networks,” The Computer Journal, vol. 65, no. 3, hlm. 495–515, Mar 2022, doi: 10.1093/comjnl/bxaa071.

M. Hendrikx, S. Meijer, J. Van Der Velden, dan A. Iosup, “Procedural content generation for games: A survey,” ACM Trans. Multimedia Comput. Commun. Appl., vol. 9, no. 1, hlm. 1–22, Feb 2013, doi: 10.1145/2422956.2422957.

J. Roberts dan K. Chen, “Learning-Based Procedural Content Generation,” 9 Oktober 2013, arXiv: arXiv:1308.6415. Diakses: 17 September 2024. [Daring]. Tersedia pada: http://arxiv.org/abs/1308.6415

J. Togelius, M. Preuss, dan G. N. Yannakakis, “Towards multiobjective procedural map generation,” dalam Proceedings of the 2010 Workshop on Procedural Content Generation in Games, Monterey California: ACM, Jun 2010, hlm. 1–8. doi: 10.1145/1814256.1814259.

J. Togelius, G. N. Yannakakis, K. O. Stanley, dan C. Browne, “Search-Based Procedural Content Generation: A Taxonomy and Survey,” IEEE Trans. Comput. Intell. AI Games, vol. 3, no. 3, hlm. 172–186, Sep 2011, doi: 10.1109/tciaig.2011.2148116.

W. M. P. Reis, L. H. S. Lelis, dan Y. K. Gal, “Human computation for procedural content generation in platform games,” dalam 2015 IEEE Conference on Computational Intelligence and Games (CIG), Tainan, Taiwan: IEEE, Agu 2015, hlm. 99–106. doi: 10.1109/cig.2015.7317906.

A. B. Moghadam dan M. K. Rafsanjani, “A genetic approach in procedural content generation for platformer games level creation,” dalam 2017 2nd Conference on Swarm Intelligence and Evolutionary Computation (CSIEC), Kerman, Iran: IEEE, Mar 2017. doi: 10.1109/csiec.2017.7940160.

D. A. Ramadhan dan A. D. Indriyanti, “Procedural Content Generation pada Game World Exploration Sandbox Menggunakan Alogoritma Perlin Noise,” JINACS, vol. 4, no. 01, hlm. 86–91, Jul 2022, doi: 10.26740/jinacs.v4n01.p86-91.

D. Ashlock, “Evolvable fashion-based cellular automata for generating cavern systems,” dalam 2015 IEEE Conference on Computational Intelligence and Games (CIG), Tainan, Taiwan: IEEE, Agu 2015, hlm. 306–313. doi: 10.1109/CIG.2015.7317958.

E. W. Hidayat, E. N. F. Dewi, dan I. S. Ramadhan, “APPLICATION OF PROCEDURAL CONTENT GENERATION SYSTEM IN FORMING DUNGEON LEVEL IN DUNGEON DIVER GAME,” 2024.

R. Van Der Linden, R. Lopes, dan R. Bidarra, “Procedural Generation of Dungeons,” IEEE Trans. Comput. Intell. AI Games, vol. 6, no. 1, hlm. 78–89, Mar 2014, doi: 10.1109/tciaig.2013.2290371.

M. Ijai, A. Arbansyah, dan S. H. Suryawan, “Penerapan Algoritma Random Walk Untuk Procedural Map Pada Game ‘The Last Hope’ 2D,” CoSciTech, vol. 4, no. 3, hlm. 754–762, Jan 2024, doi: 10.37859/coscitech.v4i3.6420.

J. R. Baron, “Procedural Dungeon Generation Analysis and Adaptation,” dalam Proceedings of the SouthEast Conference, Kennesaw GA USA: ACM, Apr 2017, hlm. 168–171. doi: 10.1145/3077286.3077566.

S. Snodgrass, “Levels from Sketches with Example-Driven Binary Space Partition,” AIIDE, vol. 15, no. 1, hlm. 73–79, Okt 2019, doi: 10.1609/aiide.v15i1.5227.

E. A. Biyik dan E. Sürer, “DEVELOPING A SPACE SYNTAX-BASED EVALUATION METHOD FOR PROCEDURALLY GENERATED GAME LEVELS,” Mugla Journal of Science and Technology, vol. 6, no. 2, hlm. 79–88, Des 2020, doi: 10.22531/muglajsci.706895.

L. H. O. Rios dan L. Chaimowicz, “A Survey and Classification of A* Based Best-First Heuristic Search Algorithms,” dalam Advances in Artificial Intelligence – SBIA 2010, vol. 6404, A. C. Da Rocha Costa, R. M. Vicari, dan F. Tonidandel, Ed., dalam Lecture Notes in Computer Science, vol. 6404. , Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, hlm. 253–262. doi: 10.1007/978-3-642-16138-4_26.

W. Shang, J. Zhong, dan Q. Yan, “Analysis of DXF file with an application to 3D graphic display,” dalam 2012 IEEE International Conference on Information and Automation, Shenyang, China: IEEE, Jun 2012, hlm. 611–615. doi: 10.1109/ICInfA.2012.6246886.

A. Van Nes dan C. Yamu, “Orientation and Wayfinding: Measuring Visibility,” dalam Introduction to Space Syntax in Urban Studies, Cham: Springer International Publishing, 2021, hlm. 87–111. doi: 10.1007/978-3-030-59140-3_3.

DOI: https://doi.org/10.30591/jpit.v10i4.8629