Saya telah membaca ini: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
Tetapi ada beberapa hal yang saya tidak mengerti, misalnya artikel mengatakan untuk menggunakan sesuatu seperti ini untuk merintis jalan dengan gerakan diagonal:
function heuristic(node) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * max(dx, dy)
Saya tidak tahu bagaimana mengatur D untuk mendapatkan jalur tampak alami seperti dalam artikel, saya menetapkan D ke biaya terendah antara kotak yang berdekatan seperti yang dikatakan, dan saya tidak tahu apa yang dimaksud dengan hal-hal tentang heuristik yang seharusnya menjadi 4 * D, itu tampaknya tidak mengubah apa pun.
Ini adalah fungsi heuristik dan fungsi bergerak saya:
def heuristic(self, node, goal):
D = 5
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return D * max(dx, dy)
def move_cost(self, current, node):
cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
return 7 if cross else 5
Hasil:
Jalur berlayar yang mulus yang kita inginkan terjadi:
Sisa kode saya: http://pastebin.com/TL2cEkeX
Memperbarui
Ini adalah solusi terbaik yang saya temukan sejauh ini:
def heuristic(node, start, goal):
dx1 = node.x - goal.x
dy1 = node.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
dx3 = abs(dx1)
dy3 = abs(dy1)
return 5 + (cross*0.01) * (dx3+dy3) + (sqrt(2)-2) * min(dx3, dy3)
def move_cost(current, node):
cross = abs(current.x - node.x) == 1 and abs(current.y - node.y) == 1
return 7 if cross else 5Ini menghasilkan jalur yang diinginkan dari gambar kedua, tetapi tidak menangani rintangan dengan baik (cenderung merangkak di dinding) dan gagal menghasilkan jalur yang optimal kadang-kadang pada jarak yang lebih jauh.
Apa saja tweak dan optimasi yang dapat saya terapkan untuk memperbaikinya?
sumber
Jawaban:
A * memberi Anda jalur terpendek dalam grafik. Saat menggunakan kisi sebagai grafik Anda, seringkali ada beberapa jalur terpendek. Dalam diagram pertama Anda, itu adalah salah satu jalur terpendek. Ini menempatkan semua gerakan aksial pertama dan semua gerakan diagonal sesudahnya. Tapi itu jalan panjang yang sama seperti jika Anda meletakkan semua diagonal terlebih dahulu, atau jika Anda mencampur gerakan aksial dan diagonal. Ini semua sama pendeknya, dan yang satu A * picks tergantung pada bagaimana kode ditulis dan bagaimana grafik diwakili.
Saya pikir yang Anda inginkan adalah:
sumber
Algoritma A * memungkinkan Anda menetapkan biaya yang berbeda untuk tepi jalur. Anda juga dapat menetapkan biaya tergantung pada keadaan. Ini adalah alat utama Anda untuk membentuk jalur A * agar tampak seperti yang Anda inginkan.
Ketika Anda ingin mencegah diagonal panjang, Anda bisa menghukum mereka. Tambahkan sedikit biaya untuk setiap kali jalan menuju ke arah yang sama. Ketika Anda melakukan ini, algoritme akan secara otomatis mencoba mendistribusikan langkah-langkah diagonal serata mungkin di seluruh jalur. Pastikan saja biaya tambahan ini tidak lebih dari biaya mengambil keunggulan tambahan, atau algoritma akan mulai membuat jalan memutar yang sama sekali tidak perlu hanya untuk menghindari garis lurus.
Formula yang baik bisa:
cost = normal_cost * (1.1 - 0.1 / num_of_steps_in_the_same_direction)Perhatikan bahwa ini mensyaratkan bahwa biaya jalur dilacak sebagai nilai titik-mengambang, bukan sebagai bilangan bulat.
sumber
Mengadaptasi A *
Seperti kata Philipp, Anda harus menambahkan biaya ketika arah tidak berubah untuk waktu yang lama. Namun, fungsi oleh Philipp dapat dengan cepat mengarah pada penjumlahan biaya tambahan, yang lebih tinggi dari biaya untuk melintasi ubin tambahan. Tapi ide kuncinya benar!
Tampaknya mudah untuk mengadaptasi A * untuk menghitung "semua" jalur optimal (dengan panjang terpendek) dan kemudian memilih salah satunya dengan heuristik lain. Tapi ada masalah. Jika Anda memiliki jalan panjang, mungkin ada banyak solusi dengan panjang optimal. Ini menyebabkan algoritma A * membutuhkan waktu lebih lama untuk menghitung semua solusi lain ini juga. Ini karena grid. Anda tidak dapat berjalan 80 derajat alih-alih 90 derajat, yang mengarah ke beberapa solusi suboptimal alih-alih satu solusi optimal. Untuk imajinasi, bayangkan peta tanpa hambatan. Jarak x adalah 2 jarak y adalah 3. Ini berarti, semua jalur terpendek memiliki 2 gerakan diagonal dan 1 gerakan lurus. Ada 3 kombinasi yang valid: SDD, DSD, DDS (di mana D = diagonal, S = lurus) untuk jalur sederhana ini. "Kegembiraan" yang sebenarnya sudah dimulai ketika Anda memiliki jalur dengan mis 3 gerakan lurus dan 2 diagonal: SSSDD, SSDSD, SSDDS, SDSSD, SDSDS, SDDSS, DSSSD, DSSDS, DSDSS, DDSSS (10 variasi jalur terpendek, jika saya tidak ketinggalan). Saya pikir Anda harus mendapat ide ...
Jadi kita harus memperbaikinya dengan mengadaptasi fungsi biaya sedemikian rupa sehingga lebih sedikit solusi (atau bahkan hanya satu solusi) yang "optimal".
Menyesuaikan Fungsi Biaya
Melakukan adaptasi seperti yang disarankan Philipp dalam formula contohnya akan memberi Anda hasil yang jauh lebih baik, tetapi masih memiliki beberapa masalah. Itu tidak akan secara merata mendistribusikan "bagian" yang lebih pendek / lebih lama di sepanjang jalan, yang berarti: perubahan arah akan lebih sering di awal jalan atau sebaliknya.
Selain itu, jalan dengan tanpa henti memiliki aktor untuk "berubah" tampaknya suboptimal ketika diamati oleh manusia. Karena membutuhkan waktu (untuk menunjukkan animasi belokan) dan karena itu harus lebih lambat.
Namun, alih-alih menggunakan pelampung untuk biaya, Anda dapat menerapkan "biaya sekunder" atau kriteria pengurutan sekunder. Jika biaya primer sama, biaya sekunder digunakan untuk memperkirakan solusi mana yang lebih disukai. Ini tidak akan secara tidak sengaja menyebabkan biaya primer (panjang rute dalam ukuran grid) meningkat.
sumber