Algoritma pencarian jalur?

24

Saya memposting pertanyaan ini pada stack overflow pertama, tapi saya kira tidak ada yang sangat tertarik dengan video game di sana ...

Apa saja algoritma pencarian jalur yang digunakan dalam semua jenis permainan? (Dari semua jenis di mana karakter bergerak, sih) Apakah Dijkstra banyak digunakan? Saya pikir tidak, karena itu tidak benar-benar melacak langkah yang harus diambil untuk sampai ke suatu tempat, kan? Jika saya memahaminya dengan benar, itu hanya menentukan objek mana yang paling dekat. Saya tidak benar-benar ingin kode apa pun; hanya melakukan beberapa penelitian, meskipun jika Anda menempelkan pseudocode atau sesuatu, itu akan baik-baik saja (saya bisa mengerti Java dan C ++). Saya pada dasarnya mencari gambaran singkat tentang pencarian jalur secara umum.

Saya tahu A * seperti algoritma yang digunakan dalam game 2D. Itu hebat dan semuanya, tapi bagaimana dengan game 2D yang tidak berbasis grid? Hal-hal seperti Zaman Kerajaan, atau Kebangkitan Tautan. Tidak ada ruang persegi yang berbeda untuk dinavigasi, jadi apa yang mereka lakukan?

Apa yang dilakukan game 3D? Saya telah membaca artikel ini http://www.ai-blog.net/archives/000152.html , yang saya dengar adalah otoritas yang hebat dalam masalah ini, tetapi itu tidak benar-benar menjelaskan BAGAIMANA, setelah jerat-jerat diatur, pencarian jalan dilakukan. JIKA A * adalah apa yang mereka gunakan, lalu bagaimana hal seperti itu dilakukan dalam lingkungan 3D? Dan bagaimana tepatnya splines bekerja untuk pembulatan sudut?

Pojo
sumber
2
Saya pikir pertanyaan ini terlalu terbuka untuk format Tanya Jawab SE. FAQ
John McDonald
1
Gim yang Anda sebutkan harus memecah peta menjadi simpul untuk A * dengan satu atau lain cara. Proses penghancuran itu tidak harus melibatkan kisi kuadrat dan ada banyak cara untuk melakukannya. Periksa vid ini youtube.com/watch?v=nGC_kBCoHYc , gim yang bagus membuatnya sehingga pemain tidak dapat mengetahui apa yang sedang mereka lakukan. benar-benar melakukan di belakang layar.
XiaoChuan Yu
1
Ada banyak pertanyaan di sini, jadi saya tidak bisa benar-benar menulis jawaban, tetapi saya akan perhatikan bahwa Dijkstra's mengembalikan sebuah path, dan sebagian besar algoritma pathfinding multiguna. Anda mengubah dunia Anda, 2D atau 3D, menjadi grafik yang terhubung, dan menjalankan algoritme pathfinding di atasnya.
Gregory Avery-Weir
Hanya untuk referensi: Saya menjawab pertanyaan di Stack Overflow .
Julian
1
Izinkan saya mengucapkan kata-kata kasar. Pertanyaan ini mendapat 4 suara positif di SO, dibandingkan dengan 4 suara dekat di sini di GDSE. Saya merasa bahwa moderator di situs ini terlalu agresif. Tentu, saya bisa melihat bagaimana pertanyaannya bertentangan dengan pedoman yang ditentukan dalam FAQ, tetapi mengutip, pedoman itu ada untuk mencegah diminishing the usefulness of our site. Pertanyaan ini telah difavoritkan 3 kali yang merupakan bukti bahwa itu bermanfaat bagi beberapa pengguna. Jadi saya merasa bahwa memilih untuk menutupnya dan mempertaruhkan pemecatan akhirnya, jauh lebih kontraproduktif.
David Gouveia

Jawaban:

62

Terlalu banyak pertanyaan sekaligus, sehingga sulit untuk memberikan jawaban yang konkret tetapi untuk membahas beberapa topik ini. Saya akan membagi jawaban menjadi dua dan mencoba mengatasinya sebaik mungkin. Saya tidak mengklaim salah satu dari daftar ini lengkap , tetapi mereka adalah beberapa metode berbeda yang dapat saya ingat.


Bagian 1 - Algoritma Pathfinding

Sebagai permulaan, ada banyak cara untuk mengimplementasikan pathfinding, tetapi tidak semuanya mengembalikan jalur terpendek, atau efisien atau bahkan dapat diandalkan. Contohnya:

  • Metode primitif yang tidak "melihat ke depan" dan mengambil satu langkah pada satu waktu:

    • Pengunduran diri acak - Ambil satu langkah pada satu waktu ke arah tujuan. Jika ada hambatan yang ditemukan cobalah untuk mengatasinya dengan mundur sedikit ke arah acak dan kemudian mencoba lagi. Tidak dapat diandalkan sama sekali dan akan terjebak dalam banyak situasi.

    • Rintangan penelusuran - Pendekatan lain, mirip dengan langkah mundur acak tetapi alih-alih bergerak mundur secara acak, mulailah melacak di sekitar objek setelah tabrakan ditemukan, seolah-olah Anda memiliki tangan kanan yang menempel di dinding dan harus menyentuhnya. Setelah tidak ada tabrakan, lanjutkan bergerak ke arah tujuan. Sekali lagi bisa mandek di banyak situasi.

  • Metode yang melihat ke depan untuk menemukan seluruh jalur sekaligus:

    • Breadth First Search - Traversal grafik sederhana dengan mengunjungi setiap lapisan anak-anak sekaligus, berhenti ketika jalan ditemukan. Jika grafik tidak berbobot (yaitu jarak antara setiap node yang berdekatan selalu sama) ia menemukan jalur terpendek meskipun tidak terlalu efisien. Untuk grafik berbobot, ia mungkin tidak mengembalikan jalur terpendek, tetapi akan selalu menemukannya jika ada.

    • Depth First Search - Cara lain untuk melintasi grafik, tetapi alih-alih mengambilnya lapis demi lapis, algoritme mencoba mencari jauh ke dalam grafik terlebih dahulu. Metode ini dapat memiliki masalah jika kedalaman pencarian tidak terbatas, terutama ketika menggunakan implementasi rekursif, yang dapat menyebabkan stack overflow, sehingga biasanya lebih aman untuk mengimplementasikannya secara iteratif menggunakan stack.

    • Pencarian Pertama Terbaik - Mirip dengan Breadth First Search tetapi menggunakan heuristik yang memilih tetangga yang paling menjanjikan terlebih dahulu. Jalur yang dikembalikan mungkin bukan yang terpendek, tetapi lebih cepat untuk dijalankan daripada pencarian pertama yang luas. A * adalah jenis Pencarian Pertama Terbaik.

    • Metode Dijkstra - Melacak total biaya dari awal hingga setiap node yang dikunjungi, dan menggunakannya untuk menentukan urutan terbaik untuk melintasi grafik. Bekerja dengan grafik tertimbang dan mengembalikan jalur terpendek, tetapi mungkin melibatkan banyak pencarian.

    • A * - Mirip dengan Dijkstra tetapi juga menggunakan heuristik untuk memperkirakan seberapa mungkin setiap node dekat dengan tujuan, untuk membuat keputusan terbaik. Karena heuristik ini, A * menemukan jalur terpendek dalam grafik berbobot dengan cara yang jauh lebih tepat waktu.

  • Kemudian ada variasi A * (atau optimisasi pencarian jalan secara umum) yang membuatnya lebih cepat atau lebih disesuaikan dengan keadaan tertentu, seperti (lihat jawaban terkait dan daftar lengkap tentang cstheory.SE ):

    • LPA * - Mirip dengan A * tetapi dapat lebih cepat menghitung ulang jalur terbaik ketika perubahan kecil pada grafik dilakukan
    • D * Lite - Berdasarkan LPA *, ia melakukan hal yang sama, tetapi mengasumsikan "titik awal" adalah unit yang bergerak menuju finish sementara perubahan grafik sedang dilakukan
    • HPA * (Hierarchical) - Menggunakan beberapa layer pada level abstraksi yang berbeda untuk mempercepat pencarian. Misalnya, lapisan tingkat yang lebih tinggi dapat dengan mudah menghubungkan kamar, sementara lapisan tingkat yang lebih rendah akan menghindari rintangan.
    • IDA * (Iterative Deepening) - Mengurangi penggunaan memori dibandingkan dengan A * biasa dengan menggunakan iterative deepening.
    • SMA * (Memori Sederhana) - Hanya menggunakan memori yang tersedia untuk melakukan pencarian.
    • Jump Point Search - Kredit untuk Eric di komentar untuk menyebutkannya! Mempercepat pathfinding pada peta kisi yang seragam ( tautan ).

Bagian 2 - Representasi Pencarian Ruang

Dan akhirnya untuk menjawab pertanyaan ini:

Saya tahu A * seperti algoritma yang digunakan dalam game 2D. Itu hebat dan semuanya, tapi bagaimana dengan game 2D yang tidak berbasis grid?

Dua kesalahpahaman besar di sini! Faktanya:

  1. A * tidak peduli apakah gim ini 2D atau 3D, dan sama-sama sesuai untuk kedua kasus.
  2. A * bekerja di bawah representasi grafik apa pun , sehingga tidak peduli apakah dunia adalah kisi atau tidak.

Jadi, jika dunia tidak perlu menjadi grid, dengan cara apa lagi Anda bisa mewakilinya? Berikut ini ikhtisar singkat cara untuk mempartisi ruang dunia untuk pencarian jalan, dan sebagian besar berfungsi baik untuk 2D maupun 3D:

  • Rectangular grid - Partisi dunia menjadi grid kotak biasa dengan setiap sel dalam grid menjadi satu simpul dalam grafik, dan koneksi antara dua node yang tidak terhalang adalah sebuah edge.

    masukkan deskripsi gambar di sini

  • Quadtree - Cara lain untuk mempartisi ruang, tetapi alih-alih mempartisi ke dalam kisi sel berukuran biasa, partisi dalam empat, kemudian secara rekursif membagi masing-masing dalam empat lagi. Menambahkan dimensi ketiga menjadikannya sebuah octree .

    masukkan deskripsi gambar di sini

  • Convex polygons - Mempartisi area walkable ke dalam mesh poligon cembung yang saling berhubungan. Setiap poligon menjadi simpul, dan tepi yang dibagikan adalah tepi grafik. Ini bisa menjadi segitiga misalnya, dan kadang-kadang bahkan menjadi jala yang dibuat oleh seorang seniman saat membuat aset tingkat. Sering disebut sebagai jala navigasi . Lihat tautan ini . Berikut ini adalah toolset konstruksi konstruksi navigasi yang sangat populer: Menyusun kembali .

    masukkan deskripsi gambar di sini

  • Poin visibilitas - Cara yang paling umum adalah menempatkan sebuah simpul tepat di luar masing-masing simpul cembung penghalang, dan kemudian menghubungkan setiap pasangan node yang dapat saling melihat . Periksa tautan ini . Node tidak harus menjadi simpul, dan dapat ditempatkan secara manual oleh desainer di peta. Dalam hal ini, sistem sering disebut sebagai grafik waypoint .

    masukkan deskripsi gambar di sini

David Gouveia
sumber
1
Dua tautan: 1) Mikko Mononen telah melakukan pekerjaan pencarian jalur Killzone 3 , dan ia memiliki blog yang sangat bagus di mana ia mendokumentasikan proses pengembangan Recast (navmesh generator) dan Detour (path finding toolkit), keduanya di bawah lisensi MIT dan digunakan sebagai contoh di Kingdoms of Amalur: Reckoning . 2) Pencarian titik lompat , saya pikir, adalah salah satu perkembangan terbaru terbesar dalam pencarian jalur berbasis grid.
Eric