Optimization of Breadth-First Search Algorithm for Path Solutions in Mazyin Games

  • Bonifacius Vicky Indriyono Dian Nuswantoro University, Semarang http://orcid.org/0000-0001-8805-9047
  • Widyatmoko Dian Nuswantoro University, Semarang
https://doi.org/10.25139/ijair.v3i2.4256
Abstract views: 1015 , PDF downloads: 1277
Keywords: Artificial Intelligence, Graph Search, Maze Game, Algorithm, Breadth-First Search

Abstract

A game containing elements of artificial intelligence, of course, requires an algorithm in its application. One example of a game that includes elements of artificial intelligence is the Labyrinth game. Maze is a simple educational game. This game is known as finding a way out of the maze to arrive at a predetermined goal. The labyrinth encounters numerous obstacles along the way, such as dead ends and parapets, to reach the target location. In this game, players are required to think logically about how to find the right maze path. The obstacle faced in this game is that sometimes players have difficulty finding a way out, especially if the game level has reached a high level in the process of finding a way out. To solve this problem, a graph tracing technique is needed. The Breadth-First Search (BFS) strategy can be used in conjunction with various graph search algorithms. An example of a broad search method is the Breadth-First Search Algorithm, which works by visiting nodes at level n first before moving on to nodes at level n+1. The advantage of the Breadth-First Search algorithm is that it can find a solution as the shortest path and find the minimum solution if there is more than one solution. This study will discuss how to find a path for the Labyrinth using the BFS algorithm. The result of applying this BFS algorithm is the shortest route solution raised so that the Labyrinth can arrive at the destination point through the route provided.

Downloads

Download data is not yet available.

References

D. Zai, H. Budiati and S.B. Berutu, "Simulation of the Shortest Route to Tourism Locations in Nias Using the Breadth-First Search and Tabu Search Methods", InFact Journal ,Vol. 1 No. 2, Nov. 2016.

B. Fu et al., "An improved A* algorithm for the industrial robot path planning with high success rate and short length," Rob. Auton. Syst., vol. 106, pp. 26–37, 2018.

S. K. Debnath et al., "A review on graph search algorithms for optimal energy efficient path planning for an unmanned air vehicle," Indones. J. Electr. Eng. Comput. Sci., vol. 15, no. 2, pp. 743–750, 2019.

G. L. Andrade and D. H. Thomas, "An Optimized Breadth-First Search Algorithm for Routing in Optical Access Networks," IEEE Lat. Am. Trans., vol. 17, no. 7, pp. 1088–1095, 2019.

Sugiyono, Educational Research Methods with Quantitative Approaches, Qualitative, and R & D. Bandung: Alfabeta. 2013.

D.J. Hodgetts and E.E. Stolte," Case‐based Research in Community and Social Psychology: Introduction to the Special Issue", Journal of Community & Applied Social Psychology, Vol. 22 No. 5, p. 379-389, Aug. 2012.

S. Arikunto, Research Procedure A practical approach. Jakarta: Rineka Cipta. 2010.

I.,G.,S. Astawa, April, 2012. "The Use of Advanced Tracing Intelligence Methods in Solving Labyrinth Game Problems". Journal of Computer Science. Vol 5 No 1. ISSN Print 1979-5661. ISSN Online 2622-321X

] R.B. Sirait, Desember, 2013. "Labyrinth Game Application Design Using Backtracking Algorithm". Pelita Informatics Budi Darma. Vol. V. No. 2. ISSN : 2301-9425.

Billy; I. Kuswardayan ; W.N., Khotimah, "Implementation of Artificial Intelligence in Game Defender of Metal City by Using Finite State Machine". Journal Of Engineering Pomits. Vol. 6, No. 2. ISSN- Online 2337-3520. ISSN Print 2301- 928X.

E. Wijaya,,2013. "Analysis of the Use of the Breadth First Search Algorithm in the Concept of Artificial Intelligence". TIME Journal, Vol. II No 2. P 18-26, 2013. ISSN 2337 – 3601.

R. Zhou and E. A. Hansen, "Breadth-first heuristic search," Artif. Intell., vol. 170, no. 4–5, pp. 385–408, 2006.

D. C. Kozen, "Lecture 4. Depth-First and Breadth-First Search," in The Design and Analysis of Algorithms, Springer, New York, NY, 2011.

F. Zhang et al., "An adaptive breadth-first search algorithm on integrated architectures," J. Supercomput., vol. 74, no. 11, pp. 6135–6155, 2018.

A. N. Putri, "Search the blind breadth first search algorithm in 3d game engine maze third person shooter android based on intelligent agent". Transformatika Journal, Vol. 14, No. 1, Jul. 2016.

Published
2021-11-30
How to Cite
Bonifacius Vicky Indriyono, & Widyatmoko. (2021). Optimization of Breadth-First Search Algorithm for Path Solutions in Mazyin Games. International Journal of Artificial Intelligence & Robotics (IJAIR), 3(2), 58-66. https://doi.org/10.25139/ijair.v3i2.4256
Issue
Vol. 3 No. 2 (2021): November 2021
Section
Articles

Copyright (c) 2021 Bonifacius Vicky Indriyono, Widyatmoko

Creative Commons License

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

Authors who publish with International Journal of Artificial Intelligence & Robotics (IJAIR) agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. 

  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.

  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.