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
Abstract views: 25 , PDF downloads: 21
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