Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Programming

Memahami Pathfinding Bidang Vektor Berbasis Sasaran

by
Difficulty:IntermediateLength:MediumLanguages:

Indonesian (Bahasa Indonesia) translation by Rossie (you can also view the original English article)

Dalam tutorial ini saya akan menjelaskan pathfinding bidang vektor dan keuntungannya daripada algoritma pathfinding yang lebih tradisional, seperti Dijkstra's. Pemahaman dasar tentang algoritma Dijkstra dan bidang potensial akan membantu Anda untuk memahami artikel ini, tetapi tidak diperlukan.


Pengantar

Pathfinding adalah masalah dengan banyak solusi, dan masing-masing memiliki pro dan kontra. Banyak algoritma pathfinding bekerja dengan menghitung jalur ke tujuan untuk setiap pathfinder, yang berarti bahwa pathfinding akan membutuhkan waktu dua kali lebih lama untuk dihitung dengan dua kali lebih banyak pathfinder. Ini dapat diterima dalam banyak situasi, tetapi ketika bekerja dengan ribuan pathfinders, pendekatan yang lebih efisien mungkin dilakukan.

Dikenal sebagai pathfinding bidang vektor, pendekatan ini menghitung jalur dari tujuan ke setiap simpul dalam grafik. Untuk memperkuat penjelasan pathfinding bidang vektor ini, saya akan menjelaskan algoritma menggunakan implementasi khusus saya sebagai contoh.

Catatan: Pathfinding bidang vektor dapat diabstraksi ke node dan grafik secara umum; hanya karena saya menjelaskannya menggunakan pendekatan berbasis tile dan grid bukan berarti algoritma ini terbatas pada dunia berbasis tile!


Gambaran Video

Pathfinding bidang vektor terdiri dari tiga langkah.

  • Pertama, heatmap dihasilkan yang menentukan jarak jalur antara tujuan dan setiap tile/node pada peta.
  • Kedua, bidang vektor yang menentukan arah untuk mencapai tujuan dihasilkan.
  • Ketiga, setiap partikel yang mencari tujuan bersama menggunakan bidang vektor untuk menavigasi menuju tujuan.

Video ini menunjukkan kepada Anda hasil akhir, dan kemudian memberi Anda gambaran umum tentang konsep-konsep yang disajikan dalam tutorial lengkap di bawah ini:



Turunan Heatmap

Heatmap menyimpan jarak jalur dari sasaran ke setiap ubin di peta. Jarak lintasan berbeda dari jarak Euclidean karena merupakan perhitungan jarak antara dua titik yang hanya melewati medan yang dapat dilalui. GPS, misalnya, selalu menghitung jarak lintasan, dengan jalan menjadi satu-satunya medan yang dapat dilalui.

Di bawah, Anda dapat melihat perbedaan antara jarak lintasan dan jarak linier dari sasaran (ditandai dengan warna merah) ke ubin yang berubah-ubah (ditandai dengan warna merah muda). Tile yang tidak dapat dilintasi digambar dalam warna hijau. Seperti yang Anda lihat, jarak jalur (ditunjukkan dengan warna kuning) adalah 9, sedangkan jarak linier (ditunjukkan dengan warna biru muda) adalah sekitar 4.12.

Angka-angka di kiri atas setiap tile menunjukkan jarak jalur ke tujuan yang dihitung oleh algoritma pembuatan heatmap. Perhatikan bahwa ada lebih dari satu kemungkinan jarak jalur antara dua titik; dalam artikel ini, kita hanya tertarik pada yang terpendek.

Efficient_Pathing_Path_vs_Linear_Distance

Algoritma turunan heatmap adalah algoritma wavefront. Dimulai pada tujuan dengan nilai 0, dan kemudian mengalir ke luar untuk mengisi seluruh wilayah yang dapat dilalui. Ada dua langkah untuk algoritma wavefront:

  • Pertama, algoritma dimulai pada tujuan, dan menandainya dengan jarak jalur 0.
  • Kemudian, setiap sebelahnya yang bertanda tile tidak ditandai, dan menandainya dengan the previous tile's path distance + 1.
  • Ini berlanjut sampai seluruh peta yang dapat dijangkau telah ditandai.

Catatan: Algoritma wavefront hanya menjalankan pencarian pertama yang luas pada grid dan menyimpan berapa banyak langkah yang diperlukan untuk sampai ke setiap tile di sepanjang jalan. Algoritma ini kadang-kadang juga disebut algoritma brushfire.


Turunan Bidang Vektor

Sekarang jarak jalur dari setiap tile ke sasaran telah dihitung, kita dapat dengan mudah menentukan jalur yang perlu diambil untuk lebih dekat ke sasaran. Dimungkinkan untuk melakukan ini pada saat runtime untuk setiap pathfinder setiap frame, tetapi seringkali lebih baik untuk menghitung bidang vektor satu kali dan kemudian meminta semua pathfinders merujuk ke bidang vektor pada saat runtime.

Bidang vektor hanya menyimpan vektor yang menunjukkan gradien fungsi jarak (menuju tujuan) di setiap tile. Berikut ini visualisasi bidang vektor, dengan vektor-vektor menunjuk dari pusat tile di sepanjang jalur terpendek ke sasaran (sekali lagi ditunjukkan dengan warna merah).

Efficient_Pathing_Vector_Field_Visualization

Bidang vektor ini dihasilkan satu tile pada satu waktu dengan melihat peta panas. Komponen x dan y dari vektor dihitung secara terpisah, seperti yang ditunjukkan dalam pseudocode di bawah ini:

Catatan: Setiap variabel jarak ubin menyimpan jarak jalur ke sasaran seperti yang dihitung oleh algoritma wavefront di atas.

Jika salah satu ubin yang direferensikan (kiri/kanan/atas/bawah) tidak dapat dilintasi dan dengan demikian tidak memiliki jarak yang dapat digunakan disimpan, jarak yang terkait dengan tile saat ini digunakan sebagai pengganti nilai yang hilang. Setelah vektor jalur dihitung secara kasar, dinormalisasi untuk menghindari inkonsistensi nanti.


Gerakan Pathfinder

Sekarang bidang vektor telah dihitung, sangat mudah untuk menghitung pergerakan pathfinder. Dengan asumsi bahwa vector_field (x,y) mengembalikan vektor yang kita hitung sebelumnya di ubin (x,y), dan yang diinginkan_velocity adalah skalar, pseudocode untuk menghitung kecepatan partikel pada ubin (x,y) terlihat seperti ini:

Partikel hanya perlu mulai bergerak ke arah yang ditunjukkan oleh vektor. Ini adalah cara paling sederhana untuk melakukan ini, tetapi sistem pergerakan yang lebih rumit dapat dengan mudah diimplementasikan menggunakan bidang aliran.

Misalnya, teknik yang dijelaskan dalam Memahami Steering Behaviors dapat diterapkan pada gerakan pathfinder. Dalam situasi seperti itu, velocity_vector yang dihitung di atas akan digunakan sebagai kecepatan yang diinginkan, dan steering behaviors akan digunakan untuk menghitung gerakan aktual pada setiap langkah waktu.

Optima Lokal

Saat menghitung pergerakan, ada satu masalah yang kadang-kadang bisa terjadi, dikenal sebagai optima lokal. Ini terjadi ketika ada dua jalur optimal (terpendek) yang harus diambil untuk mencapai tujuan dari tile yang diberikan.

Masalah ini bisa dilihat pada gambar di bawah ini. Tile (ditunjukkan dengan warna merah muda) tepat di sebelah kiri tengah dinding memiliki vektor jalur yang komponennya (x dan y) sama dengan 0.

Efficient_Pathing_Local_Optima

Optima lokal menyebabkan pathfinder terjebak; mereka akan merujuk ke bidang vektor yang akan gagal menunjukkan arah untuk masuk. Ketika ini terjadi, pathfinder akan tetap di lokasi yang sama kecuali jika perbaikan diterapkan.

Cara paling elegan (saya telah menemukan) untuk memperbaiki masalah adalah dengan membagi baik heatmap dan bidang vektor satu kali. Setiap satu heatmap dan vektor tile bidang sekarang telah terpecah menjadi empat tile yang lebih kecil. Masalah tetap sama dengan grid administratif; itu telah hanya telah sedikit diminimalkan.

Trik nyata yang memecahkan masalah lokal optima adalah untuk menambahkan node tujuan empat, bukan hanya satu. Untuk melakukan hal ini kita hanya perlu mengubah langkah pertama dari heatmap turunan algoritma. Saat kita dulu hanya menambahkan satu tujuan dengan jarak jalur 0, sekarang tambahkan empat tile yang paling dekat dengan tujuan.

Ada beberapa cara untuk memilih empat tile, tetapi bagaimana mereka dipilih sebagian besar tidak relevan - selama empat tile berdekatan (dan dapat dilalui), teknik ini harus bekerja.

Berikut adalah pseudocode yang diubah untuk turunan heatmap:

  1. Pertama, algoritma dimulai pada empat tile sasaran, dan tandai keempat ubin sasaran dengan jarak jalur 0.
  2. Kemudian, setiap sebelahnya yang bertanda tile tidak ditandai, dan the previous tile's path distance + 1.
  3. Ini berlanjut sampai seluruh peta yang dapat dijangkau telah ditandai.

Dan sekarang, inilah hasil akhirnya, yang dengan jelas menunjukkan bahwa masalah optima lokal telah dihilangkan:

Efficient_Pathing_Local_Optima_Solved

Meskipun solusi ini elegan, itu jauh dari ideal. Menggunakannya berarti menghitung heatmap dan bidang vektor membutuhkan waktu empat kali lebih lama karena peningkatan jumlah tile.

Solusi lain membutuhkan pemeriksaan dan kemudian menentukan arah mana yang harus diambil berdasarkan kasus per kasus, yang secara signifikan memperlambat perhitungan pergerakan partikel. Dalam kasus saya, membagi peta adalah pilihan yang lebih baik.


Kesimpulan

Semoga tutorial ini telah mengajarkan Anda bagaimana menerapkan pathfinding berbasis tujuan di dunia berbasis tile. Ingatlah bahwa jenis pathfinding ini, pada intinya, sederhana: partikel mengikuti gradien fungsi jarak menuju tujuan.

Implementasinya lebih kompleks, tetapi dapat dipecah menjadi tiga langkah berikut yang dapat dikelola:

  1. Turunan Heatmap
  2. Turunan Vector Field
  3. Gerakan Partikel

Saya berharap untuk melihat orang-orang yang mengembangkan ide-ide yang disajikan di sini. Seperti biasa, jika Anda memiliki pertanyaan, jangan ragu untuk bertanya kepada mereka di komentar di bawah ini!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.