31
area
pencarian menjadi
array
dua
dimensi
yang
sederhana.
Tiap
nilai
dalam
array
merepresentasikan satu
node pada area pencarian, dan statusnya disimpan sebagai “yang
bisa
dilalui”
atau
“yang
tidak
bisa
dilalui”.
Jalur
ditemukan
dengan
menentukan
node
mana
saja
yang
dilalui
untuk
mencapai
node
B
dari
node
A.
Ketika
jalur
ditemukan
maka akan berpindah dari satu node ke node yang lain sampai ke tujuan.
Ketika
area
pencarian
sudah
disederhanakan
ke
dalam
beberapa
node.
Seperti
yang
telah
dilakukan
diatas,
langkah
berikutnya
adalah
melakukan pencarian
untuk
mencari
jalur terpendek.
Dalam
pencarian
jalur
A*,
dimulai dari
node
A,
memeriksa node yang
berdekatan, dan secara umum mencari kesebelah sampai tujuan ditemukan.
Pencarian dilakukan dengan tahap sebagai berikut :
1.
Dimulai
dari
start
node
A
dan
start
node
tersebut
ditambahkan
ke
sebuah
open
list
dari
node-node
yang
akan
diperiksa.
List
tersebut
berisi
node-node
yang
mungkin dilalui
pada
jalur
yang
ingin
dicari,
atau
mungkin juga
tidak,
jadi
list
tersebut berisi node-node yang perlu diperiksa.
2.
Lihatlah
semua
node-node
yang dapat
dilalui
yang
terhubung dengan start
node,
hindari
node-node
yang
merupakan
penghalang-penghalang.
Tambahkan ke
dalam
open
list,
untuk
tiap-tiap
node,
node
A
merupakan
node
parent,
node
ini
berguna ketika ingin mengikuti jalur.
3.
Buang
node
A
dari
open
list,
kemudian tambahkan
node
A
ke
dalam
closed
list,
dimana pada list ini tidak perlu lagi memeriksa node-node yang ada di dalamnya.
Pada saat
ini,
harus dilakukan seperti
yang
terlihat pada
gambar, pada
gambar dibawah
node
yang
berwarna
hijau
di
tengah-tengah adalah
start
node.
Node yang
sisinya
berwarna
biru
adalah
node
yang
telah
dimasukkan
ke
dalam
closed
list,
semua
node
 |