OPTIMISASI ALGORITMA A* PADA LINGKUNGAN BERBASIS HEXAGON MENGGUNAKAN PARALLEL BIDIRECTIONAL SEARCH

SAIAN, PRATYAKSA OCSA NUGRAHA (2016) OPTIMISASI ALGORITMA A* PADA LINGKUNGAN BERBASIS HEXAGON MENGGUNAKAN PARALLEL BIDIRECTIONAL SEARCH. S2 thesis, UAJY.

	Text (Halaman Judul) 0MTF02328.pdf Download (11MB)
	Text (Bab I) 1MTF02328.pdf Download (651kB)
	Text (Bab II) 2MTF02328.pdf Download (578kB)
	Text (Bab III) 3MTF02328.pdf Download (725kB)
	Text (Bab IV) 4MTF02328.pdf Restricted to Registered users only Download (674kB)
	Text (Bab V) 5MTF02328.pdf Restricted to Registered users only Download (1MB)
	Text (Bab VI) 6MTF02328.pdf Download (644kB)

Abstract

Pencarian jalur terpendek merupakan sebuah masalah klasik pada bidang teknologi informasi, khususnya dalam bidang game. Dalam sebuah game, algoritma pencarian jalur terpendek sering diimplementasikan pada Non-Playable Character (NPC). Salah satu algoritma pencarian jalur terpendek yang sering digunakan di bidang game adalah algoritma A*. Kemampuan A* dalam menemukan jalur, ditambah dengan kemampuan Central Processing Unit (CPU) saat ini, yang memungkinkan untuk mengolah data secara paralel dimanfaatkan untuk melakukan optimisasi pada algoritma A*. Penelitian ini akan menjelaskan bagaimana melakukan optimisasi pada algoritma A* menggunakan Parallel Bidirectional Search (PBS) pada hexagon-based environment. Penelitian dilakukan melalui tiga tahapan utama, yaitu studi pustaka dan studi tentang pembuatan aplikasi, pembuatan dan pengujian aplikasi, dan penulisan laporan. Pada tahapan pembuatan aplikasi dapat dibagi lagi menjadi tiga tahap, yaitu pembuatan labirin dengan hexagon-based environment, penerapan algoritma A* pada labirin yang telah dibuat, dan penerapan PBS pada algoritma A*. Hasil dari penelitian ini adalah diterapkannya PBS pada algoritma A* mampu mempercepat waktu eksekusi pencarian jalur terpendek. PBSA* akan memiliki waktu eksekusi yang lebih kecil dibandingkan dengan algoritma A* itu sendiri.

Actions (login required)

View Item