[Algoritma] Berguru Algoritma A* Untuk Pencarian Jalur / Rute Terdekat
Pencarian jalur atau istilah kerennya ialah pathfinding dalam deskripsi saya ialah proses pencarian rute/jalur (biasanya rute terdekat) dari suatu arena yang pada umumnya mempunyai penghalang-penghalang dari arena tersebut. Adapun penghalang sanggup berupa tembok, sungai, dsb. Goal dari pathfinding ini pada umumnya ialah untuk mencari jalur paling efisien dengan sebisa mungkin menghindari penghalang yang ada.
Pathfinding sanggup diterapkan contohnya dalam menciptakan AI dari suatu game, contohnya semoga AI tersebut sanggup mengejar musuh secara efisien dan tanpa menabrak tembok atau menghindari penghalang lain. Terdapat beberapa metode yang sanggup diterapkan dalam pathfinding ini, salah satu metode yang sering dipakai ialah A*. Ok, tanpa berbelit-belit pribadi saja kita berkenalan dengan metode yang satu ini.
Langkah 1 : Arena
Berikut ialah referensi simple arena yang akan kita gunakan. Warna hijau ialah starting point, warna merah ialah goal/end point, dan biru ialah penghalang. Goal dari aplikasi ini ialah mencari rute dari titik hijau ke merah tanpa melewati penghalang biru
Berikut ialah referensi simple arena yang akan kita gunakan. Warna hijau ialah starting point, warna merah ialah goal/end point, dan biru ialah penghalang. Goal dari aplikasi ini ialah mencari rute dari titik hijau ke merah tanpa melewati penghalang biru
Langkah 2 : Movement Cost / Biaya Pergerakan
Kita asumsikan setiap langkah dari hijau ialah legal baik vertikal, horizontal, maupun diagonal dengan catatan tidak membentur tembok. Setiap langkah yang diizinkan kita berikan nilai G dimana G ialah cost atau biaya dalam setiap langkah. Dalam kasus ini kita akan berikan nilai 10 untuk setiap langkah vertikal maupun horizontal, dan 14 untuk diagonal. Nilai 14 kita dapatkan dari perhitungan pitagoras dimana 14,1421 = sqrt(sqr(10)+sqr(10)). Hasil data nilai G ini selanjutnya kita gambarkan sbb :
Kita asumsikan setiap langkah dari hijau ialah legal baik vertikal, horizontal, maupun diagonal dengan catatan tidak membentur tembok. Setiap langkah yang diizinkan kita berikan nilai G dimana G ialah cost atau biaya dalam setiap langkah. Dalam kasus ini kita akan berikan nilai 10 untuk setiap langkah vertikal maupun horizontal, dan 14 untuk diagonal. Nilai 14 kita dapatkan dari perhitungan pitagoras dimana 14,1421 = sqrt(sqr(10)+sqr(10)). Hasil data nilai G ini selanjutnya kita gambarkan sbb :
Selain dari perhitungan tersebut, kita sanggup mengalikan dengan konstanta tertentu untuk memanipulasi biaya, misal : dikala melewati sungai maka G = G * 2.
Langkah 3 : Estimated Movement / Estimasi gerakan
Langkah selanjutnya kita hitung biaya estimasi pergerakan dan kita simbolkan dengan H. Nilai H ini secara singkat ialah nilai jarak / estimasi biaya dari pergerakan dari suatu titik terhadap titik finish dengan mengabaikan penghalang yang ada. Untuk lebih jelasnya silahkan lihat gambar di bawah :
Langkah selanjutnya kita hitung biaya estimasi pergerakan dan kita simbolkan dengan H. Nilai H ini secara singkat ialah nilai jarak / estimasi biaya dari pergerakan dari suatu titik terhadap titik finish dengan mengabaikan penghalang yang ada. Untuk lebih jelasnya silahkan lihat gambar di bawah :
Langkah 4 : Scoring / Penilaian
Setelah nilai G dan H kita dapatkan, maka kita berikan skor dari masing-masing titik yang akan dilalui. Skor kita lambangkan contohnya dengan F dimana nilai F = G + H. Nilai F selanjutnya kita masukkan dalam setiap titik dari setiap langkah yang akan dilalui. Untuk lebih jelasnya lihat gambar di bawah :
Setelah nilai G dan H kita dapatkan, maka kita berikan skor dari masing-masing titik yang akan dilalui. Skor kita lambangkan contohnya dengan F dimana nilai F = G + H. Nilai F selanjutnya kita masukkan dalam setiap titik dari setiap langkah yang akan dilalui. Untuk lebih jelasnya lihat gambar di bawah :
Dari setiap nilai tersebut kita ambil keputusan dengan mengambil langkah dengan nilai F terkecil.
Langkah 5 : Looping / Perulangan
Setelah pergerakan pertama jawaban selanjutnya lakukan perulangan dari dari langkah 1 hingga 4. Untuk lebih jelasnya setiap pergerakan akan digambarkan di bawah :
Setelah pergerakan pertama jawaban selanjutnya lakukan perulangan dari dari langkah 1 hingga 4. Untuk lebih jelasnya setiap pergerakan akan digambarkan di bawah :
Selamat… Akhirnya Anda telah berhasil mempelajari algritma A* untuk proses pencarian rute terdekat. Untuk pertanyaan silahkan ditanyakan di bab komentar. Adapun kalau terdapat kesalahan dalam klarifikasi saya mohon maaf yang sebesar-besarnya dan silahkan diberi komentar di bawah. Akhir kata, terima kasih telah membaca dan terus berkarya…
Sumber : http://www.policyalmanac.org/games/aStarTutorial.htm
Baca juga :
Tutorial Pencarian Rute ( Pathfinding ) dengan Algoritma A* di Unity Menggunakan Library Arongranberg
Baca juga :
Tutorial Pencarian Rute ( Pathfinding ) dengan Algoritma A* di Unity Menggunakan Library Arongranberg
Sumber http://duniadigit.blogspot.com/
