Implementation of A* Algorithm in the Development of an Evacuation Pathfinding Simulation

Muhammad Ananda Radianto, Moh. Edi Wibowo, S.Kom., M.Kom, Ph.D.

2024 | Skripsi | ILMU KOMPUTER

Memastikan keselamatan individu selama evakuasi adalah hal yang terpenting di berbagai lingkungan, terutama di lembaga pendidikan dimana siswanya secara konsisten terlibat dalam kegiatan belajar. Kesadaran akan jalur evakuasi dan kesiapsiagaan terhadap potensi bahaya merupakan aspek yang penting. Walaupun sudah diterapkan jalur evakuasi di lingkungan gedung seperti perkantoran, mall, dan lain-lain, hal tersebut masih belum mencukupi untuk kesiapsiagaan evakuasi. Oleh karena itu, dengan menggabungkan sistem pathfinding dan juga peta jalur evakuasi, simulasi evakuasi dapat dinormalisasi dan juga didistribusikan ke bangunan-bangunan penting yang padat penduduk.

Penelitian ini bertujuan untuk mengatasi kebutuhan ini dengan mengembangkan sistem simulasi evakuasi. Simulasi evakuasi berbentuk simulasi top-down, memungkinkan pemain untuk menavigasi melalui lingkungan simulasi untuk mencari rute teraman menuju pintu keluar. Inti dari desainnya adalah implementasi algoritma A*, Breadth First Search, Dijkstra, dan Greedy Best First. Algoritma pathfinding ini kemudian kami implementasikan dalam simulasi evakuasi yang terdiri dari lima lantai berdasarkan gedung universitas sebenarnya yaitu gedung FMIPA UGM. Oleh karena itu, penerapan simulasi evakuasi ini dapat bermanfaat dalam kejadian nyata demi kemajuan lingkungan pendidikan.

Simulasi ini menggunakan algoritma untuk menghitung panjang jalur dan runtime. Algoritma A* kemudian kita bandingkan dengan Breadth First Search, Dijkstra, dan Greedy Best First untuk mendapatkan hasil terbaik. Memanfaatkan Unity Game Engine, penelitian ini menghasilkan hasil yang beragam seperti algoritma A* dan Dijkstra mengalahkan algoritma pathfinding lain yang diuji pada kategori panjang jalur traversal. Algoritma Greedy Best First mengungguli algoritma pathfinding lain yang diuji pada kategori waktu berjalan untuk menyelesaikan jalur. A* memiliki waktu berjalan yang cukup cepat bahkan dibandingkan dengan Greedy Best First. Namun, jika dibandingkan secara keseluruhan, Algoritma A* merupakan algoritma yang paling kompatibel untuk simulasi evakuasi, menghasilkan node jalur 36,16 dan metrik rata-rata 19,916 detik dari lima jenis simulasi peta.

Ensuring the safety of individuals during evacuations is paramount across various environments, especially in educational institutions where students are consistently engaged in learning activities. Awareness of evacuation routes and preparedness for potential dangers are crucial aspects. Although evacuation routes has been implemented in the building environments such as the office, malls, etc., it is still not suffice for an evacuation preparedness. Hence, by combining pathfinding system and also evacuation route maps, evacuation simulation could be normalized and also be distributed to essential buildings that packed full with people.

This research aims to address these needs by developing an evacuation simulation that informs people about safety measures and incorporates timely reminders applicable in diverse settings. The evacuation simulation takes the form of a top-down simulation, allowing players to navigate through a simulated environment in search of the safest routes to exits. Central to its design is the implementation of the A* algorithm, Breadth First Search algorithm, Dijkstra algorithm and also Greedy Best First algorithm. We then implement these pathfinding algorithms in the said evacuation simulation that consist of five floors in total based on a real university building that is Faculty of Mathematics and Natural Sciences Universitas Gadjah Mada (UGM) building. Therefore, the implementation of this evacuation simulation can be useful for real life events for the betterment of an educational environment.  

The simulation utilizes this algorithm to calculate path length and runtime. We then compare the A* Algorithm with BFS, Dijkstra, and Greedy Best First to achieve the best result. Leveraging the Unity Game Engine, this research outcomes with various results such as A* and Dijkstra algorithm overcomes other pathfinding algorithms tested in the category of path length of traversal. The Greedy Best First algorithm overcomes other pathfinding algorithms tested in the category of running time to complete the path. The A* has a rather quick running time even compared to the Greedy Best First. But when compared overall the A* Algorithm is the most compatible algorithm for evacuation simulation, resulting in 36.16 path nodes and 19.916 seconds as the average metric from five types of map simulation.

Kata Kunci : a* algorithm, pathfinding, evacuation, simulation, grid-based map, 2d game, unity game engine.