A* Pathfinding ( Algoritma Pencarian Rute A* ) Part 2

Ok... Klo Part 1 lebih membahas tentang pengertian dan pseudocode dari Algoritma A* ( A Star ), Partn 2 ini lebih ke implementasinya..... :->

Pertama, kita misalkan ada persoalan menentukan rute seperti dibawah ini

Segilima berwarna kuning adalah tempat tujuan dan kotak kuning adalah tempat asal, sedangkan titik biru adalah persimpangan setiap jalan.Setiap titik memiliki nilai X dan Y yang digunakan untuk perhitungan.

Langkah - langkah penentuan rute adalah :

1. Karena A adalah persimpangan terdekat dari tempat asal maka A masuk ke closelist (ket lbh lanjut tentang closelist etc baca Part 1 ).

2. Sedangkan H adalah persimpang terdekat dengan tempat tujuan, maka H masuk ke closelist. Kemudian dilakukan pengecekan percabangan dari A yaitu B dan C.B dan C masuk ke openlist

3. Dilakukan perhintungan dengan algoritma A* diantar B dan C mana yang lebih dekat dengan H. Rumusnya : 

4. Hasil pehitungan adalah

 

5. Maka persimpangan yang dipilih adalah B, maka B masuk ke closelist dan mengkosongkan openlist

6. Lalu dilakukan pengecekan apakah H sudah masuk ke closelist, jika belum maka dilakukan proses seperti no 2 - 6 hingga H masuk ke close list.

7. Sehingga jalur yang ditemukan adalah A - B - D - G - F.

catatan kecil :

Untuk melakukan perhitungan dengan algoritma A* ada beberapa hal yg diperlukan yaitu  :-?

1. posisi x dan y suatu titik.
2. tabel closelist untuk menyimpan rute yg sudah pasti.
3. tabel openlist untuk menyimpan rute yg belum fix.
4. tabel routing untuk menyimpan data persimpangan, percabangan dari setiap persimpangan dan posisi x, y dari persimpangan.

OK...sekian semoga bermanfaat /nobigdeal