Menemukan Jalan Di Antara Hambatan Bulat

Navigasi hutan

Al * Path Finder Algorithm adalah alat yang ampuh untuk menghasilkan jalur optimal dengan cepat. Biasanya A * ditampilkan saat menavigasi peta dari grid, tetapi dapat digunakan tidak hanya untuk grid! Ini dapat bekerja dengan grafik apa pun. Anda dapat menggunakan A * untuk menemukan jalan Anda di dunia rintangan bundar.


Dalam artikel asli, semua gambar bersifat interaktif.

Bagaimana satu algoritma menyelesaikan kedua masalah ini? Mari kita mulai dengan deskripsi singkat tentang cara kerja A *.

Algoritma A *

Algoritma A * menemukan jalur optimal dari awal ke titik akhir, menghindari rintangan di sepanjang jalan. Dia menyadari hal ini, secara bertahap memperluas banyak jalur parsial . Setiap jalur parsial adalah serangkaian langkah dari titik awal ke beberapa titik menengah di jalan menuju tujuan. Dalam proses bekerja A *, jalur parsial semakin dekat ke titik akhir. Algoritma berhenti bekerja ketika menemukan path lengkap, yang lebih baik daripada opsi yang tersisa, dan ini bisa dibuktikan.

Pada setiap langkah algoritma, A * mengevaluasi set path parsial dan menghasilkan path baru, memperluas jalur yang paling menjanjikan dari set. Untuk melakukan ini, A * menyimpan jalur parsial dalam antrian prioritas, diurutkan berdasarkan perkiraan panjang - panjang jalur yang diukur sebenarnya ditambah perkiraan jarak yang tersisa ke target. Perkiraan ini harus diremehkan ; yaitu, perkiraannya mungkin kurang dari jarak sebenarnya, tetapi tidak lebih besar dari itu. Dalam sebagian besar tugas pencarian jalur, estimasi yang baik adalah jarak geometris dalam garis lurus dari ujung jalur parsial ke titik akhir. Jalur terbaik sebenarnya ke sasaran dari ujung jalur parsial bisa lebih panjang dari jarak garis lurus ini, tetapi tidak bisa lebih pendek.

Ketika A * mulai, antrian prioritas hanya berisi satu jalur parsial: titik awal. Algoritme berulang kali menghilangkan jalur paling menjanjikan dari antrian prioritas, yaitu jalur dengan panjang perkiraan terkecil. Jika jalur ini berakhir di titik akhir, maka algoritme telah menyelesaikan tugas - antrian prioritas memastikan bahwa tidak ada jalur lain yang lebih baik. Kalau tidak, mulai dari ujung jalur parsial yang dihapusnya dari antrian, A * menghasilkan beberapa jalur baru, mengambil langkah unit di semua arah yang mungkin. Dia menempatkan jalur baru ini kembali ke antrian prioritas dan memulai proses lagi.

Hitung

A * bekerja dengan grafik : satu set node yang terhubung oleh tepi . Dalam dunia berbasis grid, setiap node menunjukkan sel jala yang terpisah, dan setiap tepi adalah koneksi ke sel tetangga ke utara, selatan, timur, atau barat.

Sebelum kita dapat menjalankan A * untuk hutan dari rintangan bundar, kita perlu mengubahnya menjadi grafik. Semua jalur melalui hutan terdiri dari segmen garis dan busur bolak-balik. Mereka adalah tepi grafik jalur. Titik akhir dari tepi ini menjadi simpul.

Jalur melalui grafik adalah serangkaian node yang terhubung oleh tepian:


Kedua segmen dan busur adalah tepi grafik. Kami akan menyebut segmen sebagai tepi transisi , karena jalur menggunakannya untuk bergerak di antara rintangan. Kami menyebutnya busur tepi amplop , karena tugas mereka di sepanjang jalan adalah untuk pergi di sekitar sisi hambatan.

Selanjutnya, kita akan mengeksplorasi cara sederhana untuk mengubah hutan dengan rintangan menjadi grafik: kita akan menghasilkan semua kemungkinan tepi transisi dan amplop tepi.

Generasi Tepi Transisi

Tepi transisi antara sepasang lingkaran adalah segmen garis yang hampir tidak menyentuh kedua lingkaran; segmen tersebut disebut garis singgung ke dua titik , dan untuk setiap pasangan lingkaran ada empat garis singgung seperti itu. Garis singgung ke dua titik yang berpotongan antara lingkaran disebut garis singgung internal dengan dua titik , dan yang melewati luar disebut eksternal .

Garis singgung batin menjadi dua titik

Di masa lalu, pencarian garis singgung internal penting untuk menghitung panjang sabuk yang menghubungkan dua katrol dengan ukuran berbeda, sehingga tugas membuat garis singgung internal ke dua titik disebut masalah sabuk . Untuk menemukan garis singgung internal ke dua titik, Anda perlu menghitung sudutnya $$$\ theta$ dalam gambar di bawah ini.


Ternyata, untuk lingkaran dengan pusat $$$A$ dan $$$B$ dan jari-jari $$$r_A$ dan $$$r_B$ yang pusatnya di kejauhan $$$d$ :

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

Mendefinisikan $$$\ theta$ kita dapat dengan mudah menemukan poinnya $$$C$ , $$$D$ , $$$E$ dan $$$F$ .

Garis singgung eksternal menjadi dua titik

Ketika membangun garis singgung eksternal (ini adalah tugas puli ), teknik serupa digunakan.


Untuk garis singgung eksternal dapat kita temukan $$$\ theta$ sebagai berikut:

$$

$$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d}$$

Tidak masalah lingkaran mana yang lebih besar, A atau B, tetapi seperti yang Anda lihat dari gambar, $$$\ theta$ diletakkan di sisi A paling dekat dengan B, tetapi di sisi B terjauh dari A.

Garis pandang

Diambil bersama-sama, garis singgung internal dan eksternal untuk dua titik antara dua lingkaran membentuk tepi transisi antara lingkaran. Tetapi bagaimana jika satu atau lebih tepi transisi menutup lingkaran ketiga?


Jika tepi transisi tumpang tindih oleh lingkaran lain, maka kita harus membuang tepi ini. Untuk mengenali kasus seperti itu, kami menggunakan perhitungan sederhana jarak antara titik dan garis . Jika jarak dari tepi transisi ke pusat penghalang kurang dari jari-jari penghalang, maka penghalang tumpang tindih dengan tepi transisi, jadi kita harus membuangnya.

Untuk menghitung jarak dari suatu titik $$$C$ ke segmen garis lurus $$$\ overline {AB}$ kami akan menggunakan metode berikut :

Pertama, kami menghitung $$$u$ - Bagian dari jarak di sepanjang segmen $$$\ overline {AB}$ di mana tegak lurus memotong titik $$$C$ :

$$

$$u = {(C - A) \ cdot (B-A) \ lebih dari (B-A) \ cdot (B-A)}$$

Lalu kami menghitung posisi $$$E$ pada $$$\ overline {AB}$ :

$$

$$E = A + \ mathrm {clamp} (u, 0, 1) * (B - A)$$

Jarak $$$d$ dari $$$C$ untuk memotong $$$\ overline {AB}$ Apakah jarak dari $$$C$ sebelumnya $$$E$ :

$$

$$d = \ | E - C \ |$$

Sejak $$$d <r$ , lingkaran tumpang tindih dengan garis pandang $$$A$ masuk $$$B$ , dan ujungnya harus dibuang. Jika $$$d \ ge r$ kemudian garis pandang $$$A$ masuk $$$B$ ada dan tulang rusuk harus dibiarkan.

Edge Envelope Generation

Node pada grafik menghubungkan tepi transisi dengan tepi amplop. Di bagian sebelumnya, kami menghasilkan tepi transisi. Untuk menghasilkan amplop tepi, kita mulai dari titik ujung tepi transisi, berkeliling lingkaran dan berakhir di titik ujung tepi transisi lain.


Untuk menemukan set amplop dari tepi lingkaran, pertama-tama kita menemukan semua tepi transisi yang bersinggungan dengan lingkaran. Kemudian buat amplop tepi antara semua titik ujung tepi transisi pada lingkaran.

Menyatukan semuanya

Setelah menghasilkan tepi transisi, amplop tepi dan node, dan kemudian membuang semua tepi transisi yang tumpang tindih, kita dapat membuat grafik dan mulai mencari jalur menggunakan algoritma A *.

Perangkat tambahan

Prosedur pembuatan grafik yang kami kaji bekerja cukup baik untuk menjelaskan algoritme, tetapi dapat ditingkatkan dalam banyak aspek. Perbaikan semacam itu akan memungkinkan algoritma menghabiskan lebih sedikit sumber daya CPU dan memori, serta menangani lebih banyak situasi. Mari kita lihat beberapa situasi.

Rintangan yang memprihatinkan satu sama lain

Anda mungkin telah memperhatikan bahwa dalam contoh yang ditunjukkan di atas, rintangan bundar tidak tumpang tindih dan bahkan tidak menyentuh. Dengan asumsi bahwa lingkaran dapat saling bersentuhan, ini mempersulit tugas menemukan jalan

Dua titik singgung

Ingat bahwa garis singgung ke dua titik dapat ditemukan menggunakan rumus ini untuk garis singgung internal:

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

dan rumus untuk garis singgung eksternal:

$$

$$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d}$$

Ketika dua lingkaran saling menyentuh atau berpotongan, maka tidak ada garis singgung internal di antara mereka. Dalam hal itu $$${r_A + r_B} \ lebih dari d$ lebih dari satu. Karena nilai arccosine berada di luar domain definisi $$$[- 1, 1]$ tidak ditentukan, penting untuk memeriksa persimpangan lingkaran sebelum menemukan arccosine.

Demikian pula, jika satu lingkaran sepenuhnya terletak di lingkaran lain, maka tidak akan ada garis singgung eksternal di antara mereka. Dalam hal itu $$${r_A - r_B} \ lebih dari d$ di luar jangkauan $$$[- 1, 1]$ , yaitu tidak memiliki arccosine.

Garis visibilitas tepi transisi

Jika kita membiarkan kemungkinan menyentuh atau melewati rintangan, maka kasus baru muncul dalam perhitungan garis pandang tepi transisi.

Ingat perhitungannya $$$u$ - bagian dari jarak sepanjang tepi transisi di mana tegak lurus ke titik menyentuh tepi. Jika menyentuh lingkaran tidak diizinkan, maka nilainya $$$u$ di luar jangkauan $$$[0,1]$ , yaitu, lingkaran tidak dapat menyentuh tepi, karena untuk ini ia harus menyentuh salah satu titik ujung tepi. Ini tidak mungkin karena titik akhir tepi sudah bersinggungan dengan lingkaran lain.

Namun, jika kita mengizinkan kemungkinan tumpang tindih lingkaran, maka nilainya $$$u$ di luar jangkauan $$$[0,1]$ dapat tumpang tindih garis pandang di sepanjang tepi. Ini sesuai dengan kasus di mana lingkaran terletak di luar ujung tepi transisi, tetapi tumpang tindih atau menyentuh titik akhir. Untuk melacak kasus tersebut secara matematis, kami akan membatasi $$$u$ interval $$$[0,1]$ :

$$

$$E = A + clamp (u, 0, 1) * (B - A)$$

Garis pandang amplop

Ketika rintangan dapat saling menyentuh atau berpotongan, amplop tepi dapat terhalang oleh rintangan dengan cara yang sama seperti tepi transisi. Pertimbangkan tepi amplop dari gambar di bawah ini. Jika amplop tulang rusuk menyentuh hambatan lain, maka tulang rusuk tersumbat dan harus dibuang.


Untuk menentukan apakah amplop tepi terhalang oleh hambatan lain, kami menggunakan metode berikut untuk menentukan titik di mana dua lingkaran berpotongan. Jika lingkaran memiliki pusat di titik $$$A$ dan $$$B$ dan jari-jari $$$r_A$ dan $$$r_B$ dimana $$$d$ - jarak antara $$$A$ dan $$$B$ , sebagai permulaan, kita perlu memeriksa beberapa kasus. Jika lingkaran tidak saling bersentuhan (mis. $$$d> r_A + r_B$ ),
adalah satu di dalam yang lain ( $$$d <| r_A - r_B |$ ) atau cocok ( $$$d = 0$ dan $$$r_A = r_B$ ), maka lingkaran tidak dapat memengaruhi amplop satu sama lain.

Jika tidak satu pun dari kondisi ini dipenuhi, maka lingkaran berpotongan di dua titik; jika lingkaran saling bersentuhan, maka kedua titik ini bertepatan. Pertimbangkan sumbu radikal yang menghubungkan titik persimpangan; itu tegak lurus ke jalur penghubung $$$A$ dan $$$B$ di beberapa titik $$$C$ . Kita bisa menghitung jarak $$$a$ dari $$$A$ sebelumnya $$$C$ sebagai berikut:

$$

$$a = {r_A ^ 2 - r_B ^ 2 + d ^ 2 \ lebih dari 2d}$$

Menemukan $$$a$ kita dapat menemukan sudutnya $$$\ theta$ :

$$

$$\ theta = \ arccos {a \ over r_A}$$

Jika $$$\ theta$ adalah nol, lalu lingkaran menyentuh $$$C$ . Jika tidak, ada dua titik persimpangan yang sesuai dengan positif dan negatif $$$\ theta$ .


Selanjutnya, kami menentukan apakah ada titik persimpangan antara titik awal dan akhir amplop tepi. Jika demikian, maka penghalang menghalangi tepi amplop, dan kita harus membuang tepi ini. Perhatikan bahwa kita tidak perlu mempertimbangkan kasing ketika tepi amplop seluruhnya berada di dalam penghalang, karena garis putus pandang untuk tepi transisi telah terlempar dari tepi ini.

Setelah melakukan perubahan pada perhitungan garis singgung menjadi dua titik dan garis pandang untuk tepi transisi dan amplop tepi, semuanya bekerja dengan benar.

Radius aktor variabel dan ekstensi Minkowski

Saat menghitung navigasi objek bundar di dunia rintangan melingkar, orang dapat mempertimbangkan pengamatan yang menyederhanakan solusi masalah. Pertama, seseorang dapat menyederhanakan pekerjaan dengan mencatat bahwa gerakan lingkaran jari-jari r melalui hutan mirip dengan pergerakan titik melalui hutan yang sama dengan perubahan tunggal: jari-jari setiap rintangan meningkat sebesar r . Ini adalah kasus yang sangat sederhana dalam menerapkan jumlah Minkowski . Jika jari-jari aktor lebih besar dari nol, maka sebelum memulai, kita cukup menambah ukuran rintangan.

Generasi Tepi Tangguhan

Secara umum, grafik untuk hutan dari $$$n$ rintangan mengandung $$$O (n ^ 2)$ tepi transisi, tetapi karena masing-masing harus diperiksa untuk saling berhadapan $$$n$ hambatan, maka total waktu pembuatan grafik adalah $$$O (n ^ 3)$ . Selain itu, pasangan tepi transisi dapat mengarah pada pembuatan tepi amplop, dan masing-masing harus diperiksa dengan setiap penghalang untuk garis pandang. Namun, karena efisiensi tinggi dari algoritma A *, biasanya hanya melihat sebagian dari grafik besar ini untuk membuat jalur optimal.

Kita dapat menghemat waktu dengan membuat bagian-bagian kecil grafik dengan cepat selama eksekusi algoritma A *, daripada melakukan semua pekerjaan sebelumnya. Jika A * menemukan jalur dengan cepat, maka kita hanya akan menghasilkan sebagian kecil dari grafik. Kami melakukan ini dengan memindahkan generasi tepi ke fungsi neighbors() .

Ada beberapa kasus. Pada awal algoritma, kita membutuhkan tetangga dari titik awal. Ini adalah tepi transisi dari titik awal ke tepi kiri dan kanan setiap rintangan.

Kasus berikutnya adalah ketika A * baru saja sampai ke titik $$$p$ di tepi rintangan $$$C$ di sepanjang tepi transisi: neighbors() harus mengembalikan amplop dari tepi tempat asal $$$p$ . Untuk melakukan ini, kami menentukan tepi transisi mana yang keluar dari rintangan dengan menghitung garis singgung menjadi dua titik di antaranya $$$C$ dan semua hambatan lainnya, membuang semua yang tidak sejalan. Kemudian kami menemukan semua amplop dari tepi yang terhubung $$$p$ dengan tepi transisi ini, menjatuhkan yang terhalang oleh hambatan lain. Kami mengembalikan semua amplop tepi ini, menyimpan tepi transisi untuk pengembalian panggilan berikutnya ke neighbors() .

Kasus terakhir adalah ketika A * mengelilingi tepi amplop di sepanjang rintangan $$$C$ dan dia harus pergi $$$C$ di sepanjang tepi transisi. Karena langkah sebelumnya menghitung dan menyimpan semua tepi transisi, Anda dapat dengan mudah menemukan dan mengembalikan kumpulan tepi yang benar.

Kami memotong amplop rusuk yang runcing

Iga amplop menghubungkan tepi transisi menyentuh satu lingkaran, tetapi ternyata banyak iga amplop ini tidak cocok untuk digunakan secara optimal. Kami dapat mempercepat algoritme dengan menghilangkannya.

Jalur optimal melalui hutan rintangan selalu terdiri dari tepi transisi bergantian dan amplop tepi. Misalkan kita memasuki sebuah simpul $$$A$ dan putuskan bagaimana keluar dari situ:


Masuk melalui $$$A$ berarti kita bergerak searah jarum jam ( $$$\ circlearrowright$ ) Kita harus keluar melalui simpul, yang memungkinkan kita untuk terus bergerak searah jarum jam ( $$$\ circlearrowright$ ), yaitu, kita hanya bisa keluar melalui node $$$B$ atau $$$D$ . Jika Anda keluar $$$C$ kemudian infleksi ( $$$\ curlywedge$ ) cara yang tidak akan pernah optimal. Kita perlu menyaring ujung runcing tersebut.

Pertama, perhatikan bahwa A * memproses setiap sisi yang tidak berorientasi. $$$P \ longleftrightarrow Q$ seperti dua tepi berorientasi $$$P \ longrightarrow Q$ dan $$$Q \ longrightarrow P$ . Kita dapat mengambil keuntungan dari ini dengan menandai tepi dan simpul dengan orientasi.

1. Simpul $$$P$ menjadi node dengan orientasi - searah jarum jam ( $$$P \ circlearrowright$ ) atau berlawanan arah jarum jam ( $$$P \ circlearrowleft$ ) panah.
2. Tepi transisi tidak berorientasi $$$P \ longleftrightarrow Q$ menjadi tepi berorientasi $$$P, p \ longrightarrow Q, \ hat {q}$ dan $$$Q, q \ longrightarrow P, \ hat {p}$ dimana $$$p$ dan $$$q$ Apakah orientasi, dan $$$\ hat {x}$ berarti arah yang berlawanan $$$x$ .
3. Rib Amplop Berorientasi $$$P \ longleftrightarrow Q$ menjadi tepi berorientasi $$$P \ circlearrowright \ longrightarrow Q \ circlearrowright$ dan $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowleft$ . Di sinilah pemfilteran terjadi: kami tidak mengaktifkan $$$P \ circlearrowright \ longrightarrow Q \ circlearrowleft$ dan $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowright$ , karena perubahan arah menciptakan ketegaran ( $$$\ curlywedge$ )

Di sirkuit kami, simpul $$$A$ akan berubah menjadi dua node, $$$A \ circlearrowright$ dan $$$A \ circlearrowleft$ ia memiliki tepi transisi yang masuk $$$\ longrightarrow A \ circlearrowright$ dan tepi transisi keluar $$$A \ circlearrowleft \ longrightarrow$ . Jika kita melewati jalan $$$A \ circlearrowright$ maka harus keluar melalui node $$$\ circlearrowright$ yang akan menjadi tepi transisi $$$B \ circlearrowright \ longrightarrow$ (melalui tepi amplop $$$A \ circlearrowright \ longrightarrow B \ circlearrowright$ ), atau tepi transisi $$$D \ circlearrowright \ longrightarrow$ (melalui tepi amplop $$$A \ circlearrowright \ longrightarrow D \ circlearrowright$ ) Kami tidak bisa keluar $$$C \ circlearrowleft \ longrightarrow$ , karena arah rotasi akan berubah dengan cara ini, dan kami menyaring amplop tepi $$$A \ circlearrowright \ longrightarrow C \ circlearrowleft$ .

Dengan menyaring amplop tepi yang runcing dari grafik, kami meningkatkan efisiensi algoritme.

Memotong ujung yang berpotongan

Jalur parsial dapat terputus, tepi terakhir dari transisi yang memotong tepi kedua dari belakang transisi.

Hambatan poligonal

Lihat Game Programming Gems 2 , Bab 3.10, Mengoptimalkan Pathfinding Point-of-Visibility, yang ditulis oleh Thomas Young. Bab ini membahas kliping node, tetapi tidak untuk lingkaran, tetapi untuk poligon.

Referensi

• Tugas sabuk
• Tugas katrol
• Jarak antara titik dan garis
• Persimpangan dua lingkaran