Grid Tabanlı Yol Planlamasında En Kısa Yol Algoritmalarının Analizi İçin Simülasyon Programı Tasarımı

Öz

Bu çalışma, 91 ila 7651 arasında değişen altıgen hücrelerden oluşan bir haritada farklı arazi tipleri ve yükseklik seviyelerine sahip hücreler arasındaki en kısa yolu bulmak için kullanılan algoritmaların analizini inceler. Analiz için bir simülasyon programı tasarlanır. Simülasyon programı, Unity 3D oyun motoru ve C# programlama dili kullanılarak uygulanır. Unity oyun motoru, altıgen ızgara tabanlı hücrelerden oluşan bir harita tasarlamak ve en kısa yol bulma algoritmalarının simülasyon sonuçlarını görselleştirmek için kullanılır. Her hücre, hücreler arasındaki hareket maliyetini belirleyen komşuluk bağlantılarına sahiptir. Çalışma kapsamında simülasyona bir akıllı ajan dahil edilir. Akıllı ajan, çevresini algılar, arazi türü ve yükseklik faktörlerini değerlendirir ve seçilen algoritmaya göre iki nokta arasında en düşük geçiş maliyetine sahip en kısa yolu bulmaya çalışır. Algoritmaların performansı, hesaplama süresi, ziyaret edilen hücre sayısı ve geçiş maliyeti açısından karşılaştırılır. Sonuçlar, sezgisel algoritmaların hesaplama süresi ve ziyaret edilen hücre sayısı açısından yüksek performans gösterdiğini ortaya koymaktadır. Ancak, geçiş maliyetleri açısından aynı başarıyı elde edemedikleri görülmektedir.

Anahtar Kelimeler

• Optimum yol planlama
• simülasyon programı
• en kısa yol algoritmaları
• unity 3D

Design of Simulation Program for Analysis of Shortest Path Algorithms in Grid-Based Path Planning

Abstract

This study examines the analysis of algorithms used to find the shortest path between cells with different terrain types and elevation levels on a map comprising hexagonal cells ranging from 91 to 7651. A simulation program is designed for the analysis. The simulation program is implemented using the Unity 3D game engine and the C# programming language. The Unity game engine is used to design a map comprising hexagonal grid-based cells and visualize the simulation results of the shortest path finding algorithms. Each cell has neighborhood connections that determine the movement cost between cells. A smart agent is included in the simulation within the scope of the study. The smart agent perceives its environment, evaluates terrain type and elevation factors, and attempts to find the shortest path between two points with the lowest transition cost according to the selected algorithm. The performance of the algorithms is compared in terms of computation time, number of cells visited, and transition cost. The results demonstrate that the heuristic algorithms achieve high performance in terms of computation time and number of cells visited. However, it is seen that they cannot achieve the same success in terms of transition costs.

Keywords

• Optimal path planning
• simulation program
• shortest path algorithms
• unity 3D

Kaynakça

1. [1] Ruszczynski, A. (2011). Nonlinear optimization. Princeton university press.
2. [2] Xing, H., Chai, M., Song, Y. (2024). Artificial intelligence pathfinding based on Unreal Engine 5 hexagonal grid map. In 2024 IEEE 4th International Conference on Neural Networks, Information and Communication (NNICE), 1708-1711.
3. [3] Adaixo, M. C. G. (2014). Influence Map-Based Pathfinding Algorithms in Video Games, M.S. Thesis, Universidade da Beira Interior.
4. [4] Lawande, S. R., Jasmine, G., Anbarasi, J., Izhar, L. I. (2022). A systematic review and analysis of intelligence-based pathfinding algorithms in the field of video games. Applied Sciences, 12(11), 5499.
5. [5] Johner, R., Lanaia, A., Dornberger, R., Hanne, T. (2022). Comparing the Pathfinding Algorithms A*, Dijkstra’s, Bellman-Ford, Floyd-Warshall, and Best First Search for the Paparazzi Problem. In Congress on Intelligent Systems: Proceedings of CIS, 561-576.
6. [6] Real-Time 3D Development Platform, Unity, https://unity.com/products/unity-engine
7. [7] Jeong-Shick, Y. (2023). Unity: A Powerful Tool for 3D Computer Animation Production. Journal of the Korea Computer Graphics Society, 29(3), 45-57.
8. [8] Boyraz G, Kırcı, P. (2019). 3D Game Design with UNITY 3D Game Simulator. International Journal of Multidisciplinary Studies and Innovative Technologies, 3(2), 225-229.

9. [9] Gunes, M., Dilipak, H. (2020). Shortest Path Approach in Pedestrian Transfers Application in Unity. Gazi Mühendislik Bilimleri Dergisi, 6(2), 111-119.
10. [10] Zhang, X., Zhang, X. (2022). Based on Navmesh to implement AI intelligent pathfinding in three-dimensional maps in UE4. In Proceedings of the 2022 5th International Conference on Algorithms, Computing and Artificial Intelligence, 1-5.
11. [11] Barbour Jr, R. D. (2008). Reduction of complexity in path finding using grid-based methods. Faculty of Graduate Studies and Research, University of Regina.
12. [12] Bailey, J. P., Nash, A., Tovey, C. A., Koenig, S. (2021). Path-length analysis for grid-based path planning. Artificial Intelligence, 301, 103560.
13. [13] Yang, Y., Zhang, S., Zhang, C., James, J. Q. (2021). Origin-destination matrix prediction via hexagon-based generated graph. In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC), 1399-1404.
14. [14] Wüthrich, C. A., Stucki, P. (1991). An algorithmic comparison between square-and hexagonal-based grids. CVGIP: Graphical Models and Image Processing, 53(4), 324-339.
15. [15] Duszak, P. (2022). SLAM on the Hexagonal Grid. Sensors, 22(16), 6221.
16. [16] Edler, D., Keil, J., Bestgen, A. K., Kuchinke, L., Dickmann, F. (2019). Hexagonal map grids–an experimental study on the performance in memory of object locations. Cartography and Geographic Information Science, 46(5), 401-411.
17. [17] Her, I. (1995). Geometric transformations on the hexagonal grid. IEEE Transactions on Image Processing, 4(9), 1213-1222.
18. [18] Hex Map 1, Hexagonal Grid, https://catlikecoding.com/unity/tutorials/hex-map/part-1/
19. [19] Rafiq, A., Kadir, T. A. A., Ihsan, S. N. (2020). Pathfinding algorithms in game development. In IOP Conference Series: Materials Science and Engineering, 769(1), 012021.
20. [20] Yan, Y. (2023). Research on the A Star Algorithm for Finding Shortest Path. Highlights in Science, Engineering and Technology, 46, 154-161.
21. [21] Wayahdi, M. R., Ginting, S. H. N., Syahputra, D. (2021). Greedy, A-Star, and Dijkstra’s algorithms in finding shortest path. International Journal of Advances in Data and Information Systems, 2(1), 45-52.
22. [22] Deng, Z., Wang, D. (2023). Research on Parking Path Planing Based on A-Star Algorithm. Journal of New Media, 5(1).
23. [23] Candra, A., Budiman, M. A., Pohan, R. I. (2021). Application of a-star algorithm on pathfinding game. In Journal of Physics: Conference Series (IOP Publishing), 1898(1), 012047.
24. [24] Saian, P. O. N. (2016). Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search. In 2016 IEEE 8th International Conference on Information Technology and Electrical Engineering (ICITEE), 1-5.
25. [25] Zhang, H., Tao, Y., Zhu, W. (2023). Global path planning of unmanned surface vehicle based on improved A-Star algorithm. Sensors, 23(14), 6647.
26. [26] Frăsinaru, C., Răschip, M. (2019). Greedy best-first search for the optimal-size sorting network problem. Procedia Computer Science, 159, 447-454.
27. [27] Heusner, M. (2019). Search behavior of greedy best-first search (Doctoral dissertation, University_of_Basel).
28. [28] Heusner, M., Keller, T., Helmert, M. (2017). Understanding the search behaviour of greedy best-first search. In Proceedings of the International Symposium on Combinatorial Search, 8(1), 47-55.
29. [29] Heusner, M., Keller, T., Helmert, M. (2018). Best-case and worst-case behavior of greedy best-first search. International Joint Conferences on Artificial Intelligence, 1463-1470.
30. [30] Lina, T. N., Rumetna, M. S. (2021). Comparison analysis of breadth first search and depth limited search algorithms in sudoku game. Bulletin of Computer Science and Electrical Engineering, 2(2), 74-83.
31. [31] Fayed, H. A., Atiya, A. F. (2013). A mixed breadth-depth first strategy for the branch and bound tree of Euclidean k-center problems. Computational Optimization and Applications, 54, 675-703.
32. [32] Sihotang, J. (2020). Analysis Of Shortest Path Determination By Utilizing Breadth First Search Algorithm. Jurnal Info Sains: Informatika dan Sains, 10(2), 1-5.
33. [33] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2022). Introduction to algorithms. MIT press.
34. [34] Pandika, I. K. L. D., Irawan, B., Setianingsih, C. (2018). Apllication of optimization heavy traffic path with floyd-warshall algorithm. In 2018 IEEE International Conference on Control, Electronics, Renewable Energy and Communications (ICCEREC), 57-62.
35. [35] Mirino, A. E. (2017). Best routes selection using Dijkstra and Floyd-Warshall algorithm. In 2017 IEEE 11th International Conference on Information & Communication Technology and System (ICTS), 155-158.
36. [36] Hougardy, S. (2010). The Floyd–Warshall algorithm on graphs with negative cycles. Information Processing Letters, 110(8-9), 279-281.
37. [37] Azis, H., Lantara, D., Salim, Y. (2018). Comparison of Floyd-Warshall algorithm and greedy algorithm in determining the shortest route. In 2018 IEEE 2nd East Indonesia conference on computer and information technology (EIConCIT), 294-298).
38. [38] Noto, M., Sato, H. (2000). A method for the shortest path search by extended Dijkstra algorithm. In Smc 2000 conference proceedings. 2000 IEEE international conference on systems, man and cybernetics, 3, 2316-2320.
39. [39] Salem, I. E., Mijwil, M. M., Abdulqader, A. W., Ismaeel, M. M. (2022). Flight-schedule using Dijkstra's algorithm with comparison of routes findings. International Journal of Electrical and Computer Engineering, 12(2), 1675.
40. [40] Cui, X., Shi, H. (2011). A*-based pathfinding in modern computer games. International Journal of Computer Science and Network Security, 11(1), 125-130.
41. [41] Du, D. Z., Kleitman, D. J. (1990). Diameter and radius in the Manhattan metric. Discrete & computational geometry, 5, 351-356.