Bagian 1. Algoritma pencarian umum
Pendahuluan
Menemukan jalan adalah salah satu topik yang biasanya paling sulit bagi pengembang game. Terutama orang-orang miskin memahami algoritma
A * , dan banyak yang berpikir bahwa ini adalah semacam sihir yang tidak dapat dipahami.
Tujuan artikel ini adalah untuk menjelaskan pencarian jalur secara umum dan
A * khususnya dengan cara yang sangat mudah dipahami dan dapat diakses, sehingga mengakhiri kesalahpahaman yang tersebar luas bahwa topik ini kompleks. Dengan penjelasan yang tepat, semuanya cukup sederhana.
Harap perhatikan bahwa dalam artikel ini kami akan mempertimbangkan pencarian cara
untuk game ; tidak seperti artikel akademis lainnya, kami akan menghilangkan algoritma pencarian seperti Kedalaman-Pertama atau Luas-Pertama. Sebagai gantinya, kami akan mencoba untuk beralih dari nol ke
A * secepat mungkin.
Pada bagian pertama kami akan menjelaskan konsep paling sederhana untuk menemukan jalan. Dengan memahami konsep-konsep dasar ini, Anda akan menyadari bahwa
A * ternyata sangat jelas.
Sirkuit sederhana
Meskipun Anda dapat menerapkan konsep-konsep ini ke lingkungan 3D kompleks yang arbitrer, mari kita mulai dengan skema yang sangat sederhana: kotak persegi 5 x 5. Untuk kenyamanan, saya menandai setiap sel dengan huruf besar.
Jaring sederhana.Hal pertama yang akan kita lakukan adalah membayangkan lingkungan ini sebagai grafik. Saya tidak akan menjelaskan secara rinci apa itu grafik; sederhananya, ini adalah satu set lingkaran yang terhubung dengan panah. Lingkaran disebut
"knot," dan panah
disebut "ujung .
"Setiap node mewakili
"keadaan" di mana karakter mungkin. Dalam kasus kami, status karakter adalah posisinya, jadi kami membuat satu simpul untuk setiap sel kisi:
Node mewakili sel kisi.Sekarang tambahkan tulang rusuk. Mereka menunjukkan negara-negara yang dapat
"dijangkau" dari masing-masing negara; dalam kasus kami, kami dapat beralih dari sel mana saja ke sel berikutnya, kecuali yang diblokir:
Busur menunjukkan gerakan yang diizinkan antara sel-sel kotak.Jika kita dapat berpindah dari
A ke
B , maka kita mengatakan bahwa
B adalah
"tetangga" ke simpul
A.Perlu dicatat bahwa tulang rusuk memiliki
arah ; kita membutuhkan tepian dari
A ke
B , dan dari
B ke
A. Ini mungkin tampak berlebihan, tetapi tidak ketika “kondisi” yang lebih kompleks mungkin muncul. Misalnya, karakter dapat jatuh dari atap ke lantai, tetapi tidak dapat melompat dari lantai ke atap. Anda bisa beralih dari keadaan "hidup" ke keadaan "mati", tetapi tidak sebaliknya. Dan sebagainya.
Contoh
Misalkan kita ingin pindah dari
A ke
T. Kita mulai dengan
A. Anda dapat melakukan dua tindakan tepat: pergi ke
B atau pergi ke
F.Katakanlah kita pindah ke
B. Sekarang kita dapat melakukan dua hal: kembali ke
A atau pergi ke
C. Kami ingat bahwa kami sudah berada di
A dan mempertimbangkan opsi di sana, jadi tidak masuk akal untuk melakukannya lagi (kalau tidak kita bisa menghabiskan sepanjang hari bergerak
A →
B →
A →
B ...). Karena itu kita akan pergi ke
C.Berada di
C , kita tidak punya tempat untuk bergerak. Kembali ke
B tidak ada gunanya, yaitu jalan buntu. Memilih transisi ke
B ketika kami berada di
A adalah ide yang buruk; mungkin Anda harus mencoba
F sebagai gantinya?
Kami terus mengulangi proses ini sampai kami berakhir di
T. Saat ini, kami cukup membuat ulang jalur dari
A , kembali ke langkah kami. Kami berada di
T ; bagaimana kita sampai di sana? Dari
o ? Artinya, ujung jalan memiliki bentuk
O →
T. Bagaimana kami bisa sampai ke
O ? Dan sebagainya.
Ingatlah bahwa kita tidak benar
- benar
bergerak ; semua ini hanyalah proses berpikir. Kami terus berdiri di
A , dan kami tidak akan keluar dari sana sampai kami menemukan seluruh jalan. Ketika saya mengatakan "pindah ke
B ", maksud saya "bayangkan bahwa kita pindah ke
B ".
Algoritma umum
Bagian ini adalah bagian terpenting dari keseluruhan artikel . Anda benar
- benar
harus memahaminya untuk dapat mewujudkan pencarian jalan; sisanya (termasuk
A * ) hanyalah detail. Di bagian ini, Anda akan mengerti sampai Anda
mengerti artinya .
Selain itu, bagian ini sangat sederhana.
Mari kita coba memformalkan contoh kita, mengubahnya menjadi kode semu.
Kita perlu melacak titik-titik yang kita tahu bagaimana mencapainya dari simpul awal. Pada awalnya, ini hanya simpul awal, tetapi dalam proses "menjelajahi" grid kita akan belajar bagaimana untuk sampai ke node lain. Sebut saja daftar node yang
reachable :
reachable = [start_node]
Kita juga perlu melacak node yang sudah ditinjau agar tidak mempertimbangkannya lagi.
explored mereka yang
explored :
explored = []
Selanjutnya, saya akan menguraikan inti dari algoritma : pada setiap langkah pencarian, kami memilih salah satu node yang kami tahu cara menjangkau dan melihat node baru yang bisa kami dapatkan dari itu. Jika kita menentukan bagaimana mencapai simpul (target) akhir, maka masalahnya terpecahkan! Kalau tidak, kami akan melanjutkan pencarian.
Sangat sederhana, apa yang bahkan mengecewakan? Dan ini benar. Tapi ini keseluruhan algoritma. Mari kita menuliskannya langkah demi langkah dengan pseudo-code.
Kami terus mencari hingga kami sampai ke simpul akhir (dalam hal ini, kami menemukan jalur dari awal ke simpul terakhir), atau sampai kami kehabisan simpul tempat Anda dapat mencari (dalam hal ini, tidak ada jalan antara simpul awal dan akhir) .
while reachable is not empty:
Kami memilih salah satu simpul yang kami tahu cara mendapatkannya, dan yang belum diselidiki:
node = choose_node(reachable)
Jika kita baru belajar cara mencapai simpul akhir, maka tugasnya selesai! Kita hanya perlu membangun jalur dengan mengikuti tautan
previous kembali ke simpul awal:
if node == goal_node: path = [] while node != None: path.add(node) node = node.previous return path
Tidak masuk akal untuk memeriksa node lebih dari sekali, jadi kami akan melacak ini:
reachable.remove(node) explored.add(node)
Kami mengidentifikasi node yang tidak dapat kami jangkau dari sini. Kita mulai dengan daftar node yang berdekatan dengan yang sekarang dan menghapus yang sudah kita periksa:
new_reachable = get_adjacent_nodes(node) - explored
Kami mengambil masing-masing:
for adjacent in new_reachable:
Jika kita sudah tahu cara mencapai node, abaikan saja. Jika tidak, tambahkan ke daftar yang
reachable , lacak bagaimana ia masuk ke dalamnya:
if adjacent not in reachable: adjacent.previous = node
Menemukan simpul akhir adalah salah satu cara untuk keluar dari loop. Yang kedua adalah ketika
reachable menjadi kosong: kami telah kehabisan node yang dapat dieksplorasi, dan kami belum mencapai simpul akhir, yaitu, tidak ada jalan dari awal ke simpul akhir:
return None
Dan ... itu dia. Ini adalah keseluruhan algoritme, dan kode konstruksi jalur dialokasikan dalam metode terpisah:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
Berikut adalah fungsi yang membangun jalur, mengikuti tautan
previous kembali ke simpul awal:
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
Itu saja.
Ini adalah pseudocode dari
setiap algoritma pencarian jalur, termasuk
A * .
Baca kembali bagian ini hingga Anda memahami cara kerja semuanya, dan, yang lebih penting,
mengapa semuanya bekerja. Akan ideal untuk mengambil contoh dengan tangan di atas kertas, tetapi Anda juga dapat menonton demo interaktif:
Demo interaktif
Berikut ini adalah demo dan contoh implementasi algoritma yang ditunjukkan di atas (Anda dapat menjalankannya di
halaman artikel asli ).
choose_node hanya memilih simpul acak. Anda dapat memulai algoritme langkah demi langkah dan melihat daftar
explored reachable dan
explored , serta ke mana tautan
previous mengarah.
Perhatikan bahwa pencarian berakhir segera setelah jalur terdeteksi; mungkin saja beberapa node bahkan tidak dipertimbangkan.
Kesimpulan
Algoritma yang disajikan di sini adalah algoritma umum untuk
semua algoritma pencarian jalur.
Tapi apa yang membedakan masing-masing algoritma dari yang lain, mengapa
A * adalah
A * ?
Berikut ini tip: jika Anda menjalankan pencarian di demo beberapa kali, Anda akan melihat bahwa algoritma tersebut tidak selalu selalu menemukan jalur yang sama. Dia menemukan jalan, dan jalan ini belum tentu yang
terpendek . Mengapa
Bagian 2. Strategi Pencarian
Jika Anda tidak sepenuhnya memahami algoritma yang dijelaskan di bagian sebelumnya, maka kembalilah ke sana dan baca lagi, karena itu perlu untuk memahami informasi lebih lanjut. Ketika Anda mengetahuinya,
A * akan tampak sepenuhnya alami dan logis bagi Anda.
Bahan rahasia
Di akhir bagian sebelumnya, saya membiarkan dua pertanyaan terbuka: jika setiap algoritma pencarian menggunakan kode yang sama, mengapa
A * berperilaku seperti
A * ? Dan mengapa demo terkadang menemukan jalur yang berbeda?
Jawaban untuk kedua pertanyaan terkait satu sama lain. Meskipun algoritme didefinisikan dengan baik, saya meninggalkan satu aspek yang belum terpecahkan, dan ternyata, itu adalah kunci untuk menjelaskan perilaku algoritma pencarian:
node = choose_node(reachable)
Ini adalah string yang terlihat polos yang membedakan semua algoritma pencarian dari satu sama lain.
choose_node tergantung pada metode implementasi
choose_node .
Jadi mengapa demo menemukan jalur yang berbeda? Karena metode
choose_node memilih sebuah node secara acak.
Masalah panjang
Sebelum menyelam ke perbedaan dalam perilaku fungsi fungsi
choose_node , kita perlu memperbaiki kesalahan kecil dalam algoritma yang dijelaskan di atas.
Ketika kami mempertimbangkan node yang berdekatan dengan arus, kami mengabaikan mereka yang sudah tahu cara mencapai:
if adjacent not in reachable: adjacent.previous = node
Ini adalah kesalahan: bagaimana jika kita baru saja menemukan cara
terbaik untuk mencapainya? Dalam hal ini, perlu untuk mengubah tautan simpul
previous untuk mencerminkan jalur yang lebih pendek ini.
Untuk melakukan ini, kita perlu mengetahui panjang jalur dari titik awal ke titik mana pun yang dapat dijangkau. Kami akan menyebut ini biaya jalan. Untuk saat ini, kami mengasumsikan bahwa berpindah dari satu node ke salah satu node yang berdekatan memiliki biaya konstan
1 .
Sebelum memulai pencarian, kami menetapkan nilai
cost setiap node hingga
infinity ; berkat ini, jalan
apa pun akan lebih pendek dari ini. Kami juga akan menetapkan
cost simpul
start_node menjadi
0 .
Maka beginilah tampilan kode:
if adjacent not in reachable: reachable.add(adjacent)
Biaya pencarian yang sama
Sekarang mari kita lihat metode
choose_node . Jika kami berusaha menemukan jalur terpendek yang mungkin, maka memilih simpul secara acak bukanlah ide yang baik.
Lebih baik memilih simpul yang bisa kita capai dari simpul awal di sepanjang jalur terpendek; Berkat ini, kami umumnya memilih jalur yang lebih pendek daripada jalur yang lebih panjang. Ini tidak berarti bahwa jalur yang lebih panjang tidak akan dipertimbangkan sama sekali, itu berarti bahwa jalur yang lebih pendek akan dipertimbangkan terlebih dahulu. Karena algoritma berakhir segera setelah menemukan jalur yang sesuai, ini akan memungkinkan kita untuk menemukan jalur pendek.
Berikut adalah contoh yang mungkin dari fungsi
choose_node :
function choose_node (reachable): best_node = None for node in reachable: if best_node == None or best_node.cost > node.cost: best_node = node return best_node
Secara intuitif, pencarian untuk algoritma ini diperluas "secara radial" dari simpul awal hingga mencapai simpul akhir. Berikut ini adalah
demo interaktif perilaku ini:
Kesimpulan
Perubahan sederhana dalam metode memilih simpul yang dipertimbangkan oleh yang berikut memungkinkan kami untuk mendapatkan algoritma yang cukup baik: ia menemukan jalur terpendek dari awal hingga akhir.
Tetapi algoritma ini, sampai batas tertentu, tetap "bodoh." Dia terus mencari ke mana-mana hingga menemukan terminal node. Misalnya, apa gunanya contoh yang ditunjukkan di atas untuk mencari di arah
A , jika jelas bahwa kita
bergerak menjauh dari simpul akhir?
Apakah mungkin membuat
choose_node lebih pintar? Bisakah kita
mengarahkan pencarian ke node akhir , tanpa mengetahui jalur yang benar sebelumnya?
Ternyata kita bisa - di bagian selanjutnya, kita akhirnya
choose_node , yang memungkinkan kita untuk mengubah algoritma pencarian jalur umum menjadi
A * .
Bagian 3. Lepaskan tabir kerahasiaan dari A *
Algoritma yang diperoleh pada bagian sebelumnya cukup baik: ia menemukan jalur terpendek dari titik awal ke titik akhir. Namun, ia membuang-buang energinya: ia menganggap cara-cara yang seseorang jelas sebut salah - mereka biasanya
menjauh dari tujuan. Bagaimana ini bisa dihindari?
Algoritma ajaib
Bayangkan kita menjalankan algoritma pencarian di komputer khusus dengan chip yang bisa melakukan
sihir . Berkat chip yang luar biasa ini, kami dapat mengekspresikan
choose_node cara yang sangat sederhana yang dijamin untuk membuat jalur terpendek tanpa membuang waktu menjelajahi jalur sebagian yang mengarah ke mana-mana:
function choose_node (reachable): return magic(reachable, " , ")
Kedengarannya menggoda, tetapi chip ajaib masih membutuhkan semacam kode tingkat rendah. Berikut ini perkiraan yang baik:
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = magic(node, " ") total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Ini adalah cara terbaik untuk memilih simpul berikutnya: Anda memilih simpul yang memberi kita jalur terpendek dari awal hingga akhir, yang merupakan apa yang kita butuhkan.
Kami juga meminimalkan jumlah sihir yang digunakan: kami tahu persis berapa biaya bergerak dari node awal ke setiap node (ini
node.cost ), dan kami hanya menggunakan magic untuk memprediksi biaya perpindahan dari node ke node terakhir.
Tidak ajaib, tapi cukup luar biasa A *
Sayangnya, chip ajaib baru, dan kami membutuhkan dukungan dari peralatan yang sudah ketinggalan zaman. Sebagian besar kode cocok untuk kita, dengan pengecualian pada baris ini:
Artinya, kita tidak bisa menggunakan sihir untuk mengetahui biaya jalan yang belum dijelajahi. Kalau begitu, mari kita membuat prediksi. Kami akan optimis dan menganggap bahwa tidak ada apa pun antara node saat ini dan yang terakhir, dan kami dapat langsung pindah:
cost_node_to_goal = distance(node, goal_node)
Perhatikan bahwa
jalur terpendek dan
jarak minimum berbeda: jarak minimum menyiratkan bahwa sama sekali tidak ada hambatan antara node saat ini dan akhir.
Perkiraan ini cukup mudah diperoleh. Dalam contoh kisi kami, ini adalah
jarak blok kota antara dua node (mis.
abs(Ax - Bx) + abs(Ay - By) ). Jika kita bisa bergerak secara diagonal, maka nilainya akan sama dengan
sqrt( (Ax - Bx)^2 + (Ay - By)^2 ) , dan seterusnya. Yang terpenting, kami tidak pernah mendapatkan estimasi nilai
terlalu tinggi.
Jadi di sini adalah versi non-
choose_node dari
choose_node :
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Sebuah fungsi yang memperkirakan jarak dari arus ke simpul akhir disebut
heuristik , dan algoritma pencarian ini, nyonya-nyonya, disebut ...
A * .
Demo interaktif
Saat Anda pulih dari keterkejutan yang disebabkan oleh kesadaran bahwa
A * misterius sebenarnya
sangat sederhana , Anda dapat melihat demo (atau menjalankannya di
artikel asli ). Anda akan melihat bahwa, tidak seperti contoh sebelumnya, pencarian menghabiskan sedikit waktu untuk bergerak ke arah yang salah.
Kesimpulan
Akhirnya, kami sampai pada algoritma
A * , yang tidak lebih dari algoritma pencarian umum yang dijelaskan di bagian pertama artikel dengan beberapa perbaikan yang dijelaskan di bagian kedua dan menggunakan fungsi
choose_node , yang memilih node yang, menurut perkiraan kami, membawa kami lebih dekat ke simpul akhir. Itu saja.
Berikut adalah pseudo-code lengkap dari metode utama untuk referensi Anda:
function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty:
Metode
build_path :
function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path
Dan di sini adalah metode
choose_node , yang mengubahnya menjadi
A * :
function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node
Itu saja.
Tetapi mengapa kita membutuhkan
bagian 4 ?
Sekarang setelah Anda memahami cara kerja
A * , saya ingin berbicara tentang beberapa area penerapannya yang menakjubkan, yang jauh dari terbatas pada menemukan jalur dalam kisi-kisi sel.
Bagian 4. A * dalam praktek
Tiga bagian pertama artikel dimulai dengan dasar-dasar algoritma pencarian jalur dan diakhiri dengan deskripsi yang jelas tentang algoritma
A * . Semua ini bagus dalam teori, tetapi memahami bagaimana ini berlaku dalam praktik adalah topik yang sama sekali berbeda.
Misalnya, apa yang terjadi jika dunia kita bukan kisi?
Bagaimana jika suatu karakter tidak dapat langsung memutar 90 derajat?
Bagaimana membangun grafik jika dunia tidak ada habisnya?
Bagaimana jika kita tidak peduli tentang panjangnya jalan, tetapi kita bergantung pada energi matahari dan kita harus berada di bawah sinar matahari sebanyak mungkin?
Bagaimana menemukan jalur terpendek ke salah satu dari dua node ujung?
Fungsi biaya
Pada contoh pertama, kami mencari jalur terpendek antara titik awal dan akhir. Namun, alih-alih menyimpan panjang jalur parsial dalam
length variabel, kami menyebutnya
cost . Mengapa
Kita dapat membuat
A * mencari tidak hanya jalan
terpendek , tetapi juga jalan
terbaik , dan definisi "terbaik" dapat dipilih berdasarkan tujuan kita. Ketika kita membutuhkan jalur terpendek, biaya adalah panjang jalur, tetapi jika kita ingin meminimalkan, misalnya konsumsi bahan bakar, maka kita perlu menggunakannya sebagai biaya. Jika kita ingin memaksimalkan "waktu yang dihabiskan di bawah matahari", maka biaya adalah waktu yang dihabiskan tanpa matahari. Dan sebagainya.
Dalam kasus umum, ini berarti bahwa biaya terkait dikaitkan dengan setiap sisi grafik. Dalam contoh yang ditunjukkan di atas, nilai ditetapkan secara implisit dan selalu dianggap sama dengan
1 , karena kami menghitung langkah-langkah di sepanjang jalan. Tetapi kita dapat mengubah biaya iga sesuai dengan apa yang ingin kita meminimalkan.
Fungsi kriteria
Katakanlah objek kita adalah mobil, dan dia harus pergi ke pompa bensin. Pengisian bahan bakar apa pun akan cocok untuk kita. Dibutuhkan rute terpendek ke pompa bensin terdekat.
Pendekatan naif adalah menghitung jalur terpendek untuk setiap pengisian bahan bakar secara bergantian dan memilih jalur terpendek. Ini akan berhasil, tetapi itu akan menjadi proses yang cukup mahal.
Bagaimana jika kita bisa mengganti satu
goal_node dengan metode yang, pada node tertentu, dapat mengetahui apakah itu terbatas atau tidak. Berkat ini, kami dapat mencari beberapa tujuan secara bersamaan. Kita juga perlu memodifikasi heuristik sehingga mengembalikan perkiraan biaya minimum dari semua node akhir yang mungkin.
Bergantung pada spesifikasi situasinya, kita mungkin tidak dapat mencapai tujuan dengan
sempurna , atau biayanya terlalu mahal (jika kita mengirim karakter melalui setengah peta besar, apakah perbedaan satu inci itu penting?), Jadi metode
is_goal_node dapat kembali
true ketika kita Kami "cukup dekat."
Kepastian penuh tidak diperlukan.
Mewakili dunia sebagai grid diskrit mungkin tidak cukup untuk banyak game. Ambil, misalnya, penembak orang pertama atau game balap. Dunia itu diskrit, tetapi tidak bisa direpresentasikan sebagai kisi.
Tetapi ada masalah yang lebih serius: bagaimana jika dunia ini tidak ada habisnya? Dalam hal ini, bahkan jika kita dapat menyajikannya dalam bentuk kisi, maka kita tidak akan dapat membuat grafik yang sesuai dengan kisi, karena itu harus tak terbatas.
Namun, tidak semuanya hilang. Tentu saja, untuk algoritma pencarian grafik, kita pasti membutuhkan grafik. Tetapi tidak ada yang mengatakan bahwa grafik harus
komprehensif !
Jika Anda mengamati algoritma dengan cermat, Anda akan melihat bahwa kami tidak melakukan apa pun dengan grafik secara keseluruhan; kami memeriksa grafik secara lokal, mendapatkan node yang dapat kami capai dari node yang dimaksud. Seperti yang dapat dilihat dari demo
A * , beberapa node grafik tidak diselidiki sama sekali.
Jadi mengapa kita tidak membuat grafik saja dalam proses penelitian?
Kami menjadikan posisi karakter saat ini sebagai simpul awal. Saat memanggil
get_adjacent_nodes ia dapat menentukan cara yang memungkinkan di mana karakter dapat bergerak dari node yang diberikan, dan membuat node tetangga dengan cepat.
Melampaui Tiga Dimensi
Bahkan jika dunia Anda
benar -
benar mesh 2D, ada aspek lain yang perlu dipertimbangkan. Sebagai contoh, bagaimana jika sebuah karakter tidak dapat langsung memutar 90 atau 180 derajat, seperti biasanya?
Keadaan yang diwakili oleh setiap node pencarian tidak harus hanya
posisi ; sebaliknya, itu mungkin mencakup serangkaian nilai yang rumit dan semena-mena. Misalnya, jika belokan 90 derajat membutuhkan waktu sebanyak transisi dari satu sel ke sel lainnya, maka status karakter dapat diatur sebagai
[position, heading] . Setiap node dapat mewakili tidak hanya posisi karakter, tetapi juga arah pandangannya; dan tepi-tepi baru grafik (eksplisit atau tidak langsung) mencerminkan hal ini.
Jika Anda kembali ke kisi 5x5 asli, maka posisi pencarian awal sekarang dapat
[A, East] . Node yang bertetangga sekarang adalah
[B, East] dan
[A, South] - jika kita ingin mencapai
F , kita pertama-tama perlu menyesuaikan arah sehingga jalannya berbentuk
[A, East] ,
[A, South] ,
[F, South] .
Penembak orang pertama? Setidaknya empat dimensi:
[X, Y, Z, Heading] . Mungkin bahkan
[X, Y, Z, Heading, Health, Ammo] .
Perhatikan bahwa semakin kompleks keadaannya, semakin kompleks fungsi heuristiknya.
A * itu sendiri sederhana; seni sering muncul dari heuristik yang baik.
Kesimpulan
Tujuan artikel ini adalah untuk menghilangkan mitos sekali dan untuk semua itu
A * adalah algoritma mistik yang tidak dapat diuraikan. Sebaliknya, saya menunjukkan bahwa tidak ada yang misterius di dalamnya, dan sebenarnya dapat disimpulkan dengan sederhana dengan mulai dari awal.
Bacaan lebih lanjut
Amit Patel memiliki
"Pengantar algoritma A *" yang sangat baik [
terjemahan di Habré] (dan artikel-artikelnya yang lain tentang berbagai topik juga sangat bagus!).