OPTIMIZING RPG PATHFINDING A HYBRID APPROACH FOR STATIC AND DYNAMIC OBSTACLE AVOIDANCE

Renaldy Ari Gunawan; Wirawan Istiono

doi:10.56327/ijiscs.v7i3.1576

OPTIMIZING RPG PATHFINDING A HYBRID APPROACH FOR STATIC AND DYNAMIC OBSTACLE AVOIDANCE

Renaldy Ari Gunawan⁽¹⁾, Wirawan Istiono⁽²⁾,

(1) Depaetement of Informatics, Universitas Multimedia Nusantara, Tangerang, Banten
(2) Depaetement of Informatics, Universitas Multimedia Nusantara, Tangerang, Banten

Corresponding Author

Abstract

Playing a role The popular game genre known as "RPG" employs a pathfinding algorithm in its operation. The process of discovering a path from one place to another is called pathfinding. Pathfinding algorithms come in a variety of forms and are varyingly efficient. One of these methods is the A-star algorithm, which is frequently used in different games to determine routes and has actually been evaluated for efficiency. An additional algorithm to consider is the dynamic pathfinding algorithm, which is quite tiny for reference and not well-known. Combining these two techniques can result in an algorithm that avoids both static and dynamic barriers in addition to finding the fastest path. The two algorithms will be combined in this research, and two static and dynamic obstacle scenarios will be used for testing. According to the study's findings, the combination of these two algorithms enables the algorithm to avoid both static and dynamic obstacles. However, it should be noted that in the event of a dynamic obstacle, the Non-Player Character (NPC) will need to travel 3.04 seconds longer to reach their destination because they will need to find an alternate route.

Keywords

A-star; Dynamic Pathfinding; Non-Player Character; Pathfinding; Role-Playing Game

References

C. Potard et al., “Psychology of Popular Media Culture Video Game Players ’ Personality Traits : An Exploratory Cluster Approach to Identifying Gaming Preferences Video Game Players ’ Personality Traits : An Exploratory Cluster Approach to Identifying Gaming Preferences,” Psychology of Popular Media Culture, vol. 9, no. 4, 2019.

D. Y. Wohn, R. Ratan, and L. Cherchiglia, “Gender and genre differences in multiplayer gaming motivations,” Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12211 LNCS, pp. 233–248, 2020, doi: 10.1007/978-3-030-50164-8_16.

G. M. Troiano et al., “Exploring How Game Genre in Student-Designed Games Influences Computational Thinking Development,” Conference on Human Factors in Computing Systems - Proceedings, pp. 1–17, 2020, doi: 10.1145/3313831.3376755.

B. Chrismanto, L. Toruan, and W. Istiono, “Enhancing Gaming Performance : A Recommender System for Selecting Optimal Gaming Headsets Based on SAW Method,” Journal of Advances in Mathematics and Computer Science, vol. 38, no. 9, pp. 230–247, 2023, doi: 10.9734/JAMCS/2023/v38i91818.

D. Kim, J. E. K. Nam, and C. Keum, “Adolescent Internet gaming addiction and personality characteristics by game genre,” PLoS ONE, vol. 17, no. 2 February, pp. 1–14, 2022, doi: 10.1371/journal.pone.0263645.

D. Kao, “The effects of juiciness in an action RPG,” Entertainment Computing, vol. 34, no. February, p. 100359, 2020, doi: 10.1016/j.entcom.2020.100359.

T. N. Luluquisin et al., “Beast chasers: A 3D PC-based third person action RPG game used to spread societal issue awareness,” 2021 11th International Workshop on Computer Science and Engineering, WCSE 2021, no. Wcse, pp. 201–206, 2021, doi: 10.18178/wcse.2021.06.030.

I. S. Baker, I. J. Turner, and Y. Kotera, “Role-play Games (RPGs) for Mental Health (Why Not?): Roll for Initiative,” International Journal of Mental Health and Addiction, no. 0123456789, 2022, doi: 10.1007/s11469-022-00832-y.

R. H. P. Prager, “Exploring the Use of Role-playing Games in Education,” Master of Teaching Research Journal, vol. 2, no. 2, 2019.

P. C. Joni, “Analisis Kualitas Software Pada Pembangunan Mobile Game RPG Berdasarkan Kebutuhan Kualitas Untuk Mobile Game,” It Journal Research and Development, vol. 3, no. 1, pp. 62–71, 2018, doi: 10.25299/itjrd.2018.vol3(1).1901.

F. Rozi and F. Firdausiah, “Implementation of Role-Playing Games in Overcoming Introverted Children,” AL-ISHLAH: Jurnal Pendidikan, vol. 13, no. 2, pp. 1394–1402, 2021, doi: 10.35445/alishlah.v13i2.629.

M. Grande-de-Prado, R. Baelo, S. García-Martín, and V. Abella-García, “Mapping role-playing games in Ibero-America: An educational review,” Sustainability (Switzerland), vol. 12, no. 16, 2020, doi: 10.3390/SU12166298.

J. Sirota, V. Bulitko, M. R. G. Brown, and S. Poo Hernandez, “Towards procedurally generated languages for non-playable characters in video games,” IEEE Conference on Computatonal Intelligence and Games, CIG, vol. 2019-August, pp. 1–4, 2019, doi: 10.1109/CIG.2019.8848093.

K. Fathoni, R. Y. Hakkun, and H. A. T. Nurhadi, “Finite State Machines for Building Believable Non-Playable Character in the Game of Khalid ibn Al-Walid,” Journal of Physics: Conference Series, vol. 1577, no. 1, 2020, doi: 10.1088/1742-6596/1577/1/012018.

G. A. da Silva and M. W. de Souza Ribeiro, “Development of Non-Player Character with Believable Behavior: a systematic literature review,” pp. 319–323, 2022, doi: 10.5753/sbgames_estendido.2021.19660.

O. R. Chandra and W. Istiono, “A-star Optimization with Heap-sort Algorithm on NPC Character,” Indian Journal Of Science And Technology, vol. 15, no. 35, pp. 1722–1731, 2022, doi: 10.17485/ijst/v15i35.857.

G. T. Kumala and W. Istiono, “Comparison of Flow Field and A-Star Algorithm for Pathfinding in Tower Defense Game,” International Journal of Multidisciplinary Research and Analysis, vol. 5, no. 9, pp. 2445–2453, 2022, doi: 10.47191/ijmra/v5-i9-20.

J. H. Kim, J. Lee, and S. J. Kim, “Navigating non-playable characters based on user trajectories with accumulation map and path similarity,” Symmetry, vol. 12, no. 10, 2020, doi: 10.3390/SYM12101592.

A. Novita et al., “Longda Xiokan : Journal of Mandarin Learning and Teaching Development Of Learning Media Based on Car Racing Games In Mandarin Subjects For Class X Pangudi Luhur Don Bosko High School Semarang,” Journal of Mandarin Learning and Teaching, vol. 1, no. 2, pp. 43–53, 2022.

S. R. Lawande, G. Jasmine, J. Anbarasi, and L. I. Izhar, “A Systematic Review and Analysis of Intelligence-Based Pathfinding Algorithms in the Field of Video Games,” Applied Sciences (Switzerland), vol. 12, no. 11, 2022, doi: 10.3390/app12115499.

Z. Zhang, J. Jiang, J. Wu, and X. Zhu, “Efficient and optimal penetration path planning for stealth unmanned aerial vehicle using minimal radar cross-section tactics and modified A-Star algorithm,” ISA Transactions, vol. 134, pp. 42–57, 2023, doi: 10.1016/j.isatra.2022.07.032.

Z. Zhang, J. Wu, J. Dai, and C. He, “A Novel Real-Time Penetration Path Planning Algorithm for Stealth UAV in 3D Complex Dynamic Environment,” IEEE Access, vol. 8, pp. 122757–122771, 2020, doi: 10.1109/ACCESS.2020.3007496.

B. Wang, Z. Liu, Q. Li, and A. Prorok, “Mobile robot path planning in dynamic environments through globally guided reinforcement learning,” IEEE Robotics and Automation Letters, vol. 5, no. 4, pp. 6932–6939, 2020, doi: 10.1109/LRA.2020.3026638.

A. Andreychuk, K. Yakovlev, D. Atzmon, and R. Sternr, “Multi-agent pathfinding with continuous time,” IJCAI International Joint Conference on Artificial Intelligence, vol. 2019-August, no. 1, pp. 39–45, 2019, doi: 10.24963/ijcai.2019/6.

Full Text: PDF