Perbandingan Kinerja Antara Heuristics Euclidean Dan Manhattan Pada Dua Tipe Grid Menggunakan Algoritma A*

Ajitama, Gustti Rahman Priska and Eriq Muhammad Adams Jonemaro,, S.T., M.Kom and Agi Putra Kharisma, S.T., M.T. (2024) Perbandingan Kinerja Antara Heuristics Euclidean Dan Manhattan Pada Dua Tipe Grid Menggunakan Algoritma A*. Sarjana thesis, Universitas Brawijaya.

Abstract

Maraknya gim dengan variasi genre yang berkembang menuntut performance gim yang lebih menarik dan terasa hidup, eksistensi algoritma A* dalam pemanfaatannya di dunia gim sangat dibutuhkan. Penelitian ini bertujuan untuk mengetahui Teknik heuristic mana yang lebih efisien terhadap grid yang memiliki weight layer antara teknik heuristic Manhattan dan heuristic Euclidean dengan faktor jarak, waktu, dan skor. Dalam penelitian ini, penulis mengembangkan pemanfaatan algoritma A* untuk mengetahui manakah diantara teknik heuristic Manhattan dan heuristic Euclidean yang memiliki Kinerja yg lebih baik terhadap grid yang memiliki weight layer dengan faktor jarak, waktu, dan skor. Metodologi yang digunakan dalam penelitian ini meliputi perancangan algoritma pathfinding dengan desain penelitian deskriptif komparatif. Alat bantu yang digunakan dalam analisis data adalah Microsoft excel, selanjutnya data di analisis dengan Teknik statistic deskriptif. Hasil dari penelitian ini menunjukan bahwa heuristic Manhattan lebih efisien dalam penentuan jalur dengan skor weight rendah sedangkan Heuristic Euclidean lebih unggul dalam hal kecepatan penemuan rute. Evaluasi dilakukan dengan simulasi melalui beberapa tahapan, dan hasilnya menunjukan bahwan Heuristik Manhattan dan Euclidean memiliki keunggulan masing – masing dalam perhitungan skor dan waktu. Kontribusi utama dari penelitian ini adalah memberikan wawasan yang berguna bagi pengembang dan peneliti dalam memilih algoritma yang sesuai untuk berbagai kebutuhan dan kondisi. Analisis lebih lanjut dan pengujian tambahan mungkin diperlukan untuk mengeksplorasi lebih dalam performa kedua algoritma dalam konteks yang berbeda.

English Abstract

The rise of games with various evolving genres demands more engaging and lifelike game performance, making the existence of the A* algorithm crucial in its application in the gaming world. This study aims to determine which heuristic technique is more efficient on grids with weight layers between the Manhattan heuristic technique and the Euclidean heuristic technique, considering factors of distance, time, and score. In this study, the author develops the use of the A* algorithm to find out which of the Manhattan heuristic and Euclidean heuristic techniques has better performance on grids with weight layers, taking into account distance, time, and score factors. The methodology used in this research includes designing a pathfinding algorithm with a descriptive comparative research design. The tool used in data analysis is Microsoft Excel, and then the data is analyzed using descriptive statistical techniques. The results of this study indicate that the Manhattan heuristic is more efficient in pathfinding with low weight scores, while the Euclidean heuristic excels in route discovery speed. Evaluation was conducted through simulations in several stages, and the results show that both the Manhattan and Euclidean heuristics have their respective advantages in score and time calculations. The main contribution of this research is to provide useful insights for developers and researchers in selecting the appropriate algorithm for various needs and conditions. Further analysis and additional testing may be required to explore the performance of both algorithms in different contexts.

Item Type:	Thesis (Sarjana)
Identification Number:	052415
Uncontrolled Keywords:	kinerja pathfinding, weighted grid, algoritma A*-pathfindings performance, weighted grid, algoritma A*
Divisions:	Fakultas Ilmu Komputer > Sistem Informasi
Depositing User:	Sugeng Moelyono
Date Deposited:	04 Nov 2024 06:33
Last Modified:	04 Nov 2024 06:33
URI:	http://repository.ub.ac.id/id/eprint/228044

Text (DALAM MASA EMBARGO) Gustti Rahman Priska Ajitama.pdf Restricted to Registered users only Download (3MB)

Actions (login required)

View Item