26 May 2019

Penerapan Algoritma Pencarian A* Game Random Pathfinder

  1. 1.      Random Pathfinder

Random pathfinder, merupakan sebuah game PC di mana pemain akan disuguhkan world (dunia) dengan segala rintangan dengan acak, lalu player (pemain) akan memilih titik awal dan titik akhir agar sebuah titik/karakter utama akan berjalan dari titik awal ke titik akhir dengan jarak terdekat, melewati segala rintangan, dengan sendirinya.

Game (gim) ini bukan sebuah game betulan, melainkan merupakan demo yang bertujuan untuk menunjukkan bagaimana fitur pathfinder (pencari jalan) dalam sebuah game bekerja menggunakan algoritma A*. Banyak game-game yang mengandung fitur pathfinder dan menggunakan algoritma A* sebagai penggeraknya, terutama pada game-game real time strategy seperti Warcraft, Age of Empire, Rise of Nations, dan lain lain. Fitur pathfinder dalam game-game tersebut biasanya terdapat pada karakter utama player, di mana player akan memilih titik pada sebuah map agar karakter tersebut bergerak menuju titik, melewati rintangan, melalui jarak terdekat dengan sendirinya.

  1. 2.      Algoritma A* 

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.

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)).

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.

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 :

Dari setiap nilai tersebut kita ambil keputusan dengan mengambil langkah dengan nilai F terkecil.

  • katergori
  • tes

  • Kirim Komentar

    Nama :
    E-mail :
    Web : tanpa http://
    Komentar :
    Verification Code :   
       

    REYNALDI YUSUF KURNIAWAN

    Komentar Terbaru