Pencarian jalur atau istilah kerennya adalah pathfinding dalam
deskripsi saya adalah proses pencarian rute/jalur (biasanya rute
terdekat) dari suatu arena yang pada umumnya memiliki
penghalang-penghalang dari arena tersebut. Adapun penghalang dapat
berupa tembok, sungai, dsb. Goal dari pathfinding ini pada umumnya
adalah untuk mencari jalur paling efisien dengan sebisa mungkin
menghindari penghalang yang ada.
Pathfinding dapat diterapkan misalnya dalam membuat AI dari suatu
game, misalnya agar AI tersebut dapat mengejar musuh secara efisien dan
tanpa menabrak tembok atau menghindari penghalang lain. Terdapat
beberapa metode yang dapat diterapkan dalam pathfinding ini, salah satu
metode yang sering digunakan adalah A*. Ok, tanpa berbelit-belit
langsung saja kita berkenalan dengan metode yang satu ini.
Langkah 1 : Arena
Berikut adalah contoh simple arena yang akan kita gunakan. Warna hijau adalah starting point, warna merah adalah goal/end point, dan biru adalah penghalang. Goal dari aplikasi ini adalah mencari rute dari titik hijau ke merah tanpa melewati penghalang biru
Berikut adalah contoh simple arena yang akan kita gunakan. Warna hijau adalah starting point, warna merah adalah goal/end point, dan biru adalah penghalang. Goal dari aplikasi ini adalah mencari rute dari titik hijau ke merah tanpa melewati penghalang biru
Langkah 2 : Movement Cost / Biaya Pergerakan
Kita asumsikan setiap langkah dari hijau adalah legal baik vertikal, horizontal, maupun diagonal dengan catatan tidak membentur tembok. Setiap langkah yang diizinkan kita berikan nilai G dimana G adalah 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 adalah legal baik vertikal, horizontal, maupun diagonal dengan catatan tidak membentur tembok. Setiap langkah yang diizinkan kita berikan nilai G dimana G adalah 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 dapat mengalikan dengan
konstanta tertentu untuk memanipulasi biaya, misal : ketika 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 adalah 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 adalah 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 misalnya 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 misalnya 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 selesai selanjutnya lakukan perulangan dari dari langkah 1 sampai 4. Untuk lebih jelasnya setiap pergerakan akan digambarkan di bawah :
Setelah pergerakan pertama selesai selanjutnya lakukan perulangan dari dari langkah 1 sampai 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 bagian komentar. Adapun jika terdapat kesalahan dalam penjelasan 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
Pembahasannya bagus dan sangat membantu .. :)
ReplyDeletetapi mas.. kalau boleh tau ..
ada ngga contoh script nya yang bisa digunain untuk Unity3d atau Flash gt ?..
soalnya saya butuh pencerahan buat t.a saya,,
Terima Kasih.. :)
Ada kok.. Di blog ini juga udah saya buat artikelnya. Tapi bukan bikin dari nol. Klo bikin dari nol pasti lebih lama bikinnya. mengatur node nya juga bakal lama. Kalo pake lib arongranberg udah ada script buat bikin node otomatis pake grid graph, jadi lebih cepet. Jadi ini saya tulis artikel pathfinding A* pake assetnya arongranberg. Silahkan dibaca sendiri disini http://duniadigit.blogspot.com/2013/08/tutorial-pencarian-rute-pathfinding.html
Deletesemoga bermanfaat :)
Kalau Untuk contoh script yang bisa digunain untuk Java (eclipse) ada juga ngga mas ?..
Deletebutuh referensi buat belajar nih....,!!!
itu hitungan variabel H nya gak salah? kok ada yg beda, harusnya kan jalur paling singkatnya ada 2, bisa lewat atas atau lewat bawah seperti contoh..
ReplyDelete#maafklosoktau
Hahaha.... jeli amat... Iya Anda benar, saya kurang teliti. Hahahaha.... :D
Deletemas nilai G atau cost itu bisa 10 sama 14 di dapet dari mana.
ReplyDeletetolong kasih tau saya masih bingung
Bagaimana cara pengujian algoritma A* pada pencarian jalur terdekat/terpendek?
ReplyDeletemohon bantuannya
bang yang G itu gimana kok setelah di ulang nilai G nya jadi tambah ?
ReplyDeleteSetelah melangkah dilakukan perhitungan biaya G lagi dan ditambah G dari tempat berpijak sekarang. Masih bingung kayaknya.. hehehee...
Delete