Bagaimana cara membuat jalur yang tampak alami dengan A * di grid?

13

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:

masukkan deskripsi gambar di sini

Jalur berlayar yang mulus yang kita inginkan terjadi:

masukkan deskripsi gambar di sini

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 5

Ini 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?

Entitas Anonim
sumber
2
Bagaimana jika Anda menggunakan jarak cartesian sebagai heuristik Anda?
Jimmy
2
di sini hanya sebuah ide, meningkatkan biaya bergerak dari satu ubin ke ubin lain untuk setiap langkah agen bergerak ke arah yang sama.
Ali1S232
@ Jimmy Saya mencoba sqrt (pow (goal.x - node.x, 2) + pow (goal.y - node.y, 2)) dan untuk path contoh kecil saya sebenarnya mengembalikan sama persis seperti gambar dalam pertanyaan saya .
Entitas Anonim

Jawaban:

10

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:

  1. Anda perlu bergerak di grid, tetapi Anda ingin mencampur langkah aksial dan diagonal sehingga terlihat lebih baik. Salah satu pendekatan adalah memilih salah satu dari jalur yang sama pendeknya; terus membaca halaman Heuristik untuk menemukan "tie breaking". Pendekatan lain adalah ketika Anda mengevaluasi tetangga, pilih secara acak mana yang harus dievaluasi terlebih dahulu sehingga tidak selalu memilih yang lain. Saya tidak merekomendasikan menggunakan jarak Euclidean / Cartesian jika Anda ingin pindah ke grid; itu ketidakcocokan yang membuat A * berjalan lebih lambat.
  2. Anda tidak perlu bergerak di grid, dan ingin bergerak dalam garis lurus. Salah satu pendekatan adalah meluruskan jalan menggunakan "string pulling". Anda sedang mencari tempat di mana jalannya berbelok, dan menggambar garis lurus di antara titik-titik itu. Pendekatan lain adalah menerapkan ini pada grafik yang mendasarinya sendiri. Alih-alih mencari jalan di grid, cari di titik-titik kunci di peta, dan kemudian bergerak di sepanjang garis lurus antara titik-titik kunci. Anda dapat melihat contohnya di sini . Namun pendekatan lain adalah algoritma Theta * .
amitp
sumber
Jawaban yang bagus. Saya memperbarui pertanyaan saya dengan beberapa info baru, saya harap Anda dapat menentukan jawaban Anda sedikit.
Entitas Anonim
Saya pikir sedikit tentang hambatan diharapkan; ada diagram pada halaman Heuristics yang berjudul "kurang cantik dengan rintangan". Pendekatan tie tie tidak banyak membantu di sekitar rintangan. Salah satu pendekatan lain (seperti Theta *) mungkin yang Anda inginkan.
amitp
2

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.

Philipp
sumber
1

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.

SDwarfs
sumber