OPTIMISASI ALGORITMA A* PADA LINGKUNGAN BERBASIS HEXAGON MENGGUNAKAN PARALLEL BIDIRECTIONAL SEARCH
Total View This Week0
Total View This Week0
Institusion
Universitas Atma Jaya Yogyakarta
Author
SAIAN, PRATYAKSA OCSA NUGRAHA
Subject
Mobile Computing
Datestamp
2017-02-08 07:45:20
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.
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.
Download
book
BibTex
Latex, Jabref
cloud_download
Original Resource
url resource Institution
