Saya seorang pemula mutlak dengan pengembangan game dan semua yang saya tahu tentang penghindaran / resolusi tabrakan, saya mempelajarinya di atau melalui situs ini dalam seminggu terakhir ... jadi jangan ragu untuk memperbaiki saya jika apa yang saya tanyakan di sini adalah berdasarkan asumsi yang salah / kesalahpahaman. Saya mencoba yang terbaik untuk menjadi jelas, tetapi yang mengatakan, subjek masih novel bagi saya.
Kendaraan
Dalam permainan saya, saya memiliki kendaraan yang bergerak secara mandiri. Mereka ditempatkan di ruang 3D, dan gerakan mereka diatur oleh sejumlah variabel yang berbeda untuk setiap kendaraan. Yang menarik di sini adalah:
- Hanya gerak maju .
- Sebuah kecepatan yang dapat bervariasi antara min & max, tapi yang min adalah tidak (bahkan mendekati) nol.
- Sebuah radius kemudi yang tergantung dari kecepatan (kecepatan yang lebih tinggi, jari-jari yang lebih besar)
- Dua akselerasi maksimum (untuk penurunan dan peningkatan kecepatan)
Tujuan
Tujuan saya adalah menerapkan semacam AI yang akan menghindari tabrakan 100% akurat (yaitu saya akan memastikan bahwa kendaraan tidak akan pernah bertabrakan).
Desain
- Meskipun saya lebih suka ide memiliki AI "onboard" (yaitu masing-masing kendaraan yang memiliki "AI penghindaran tabrakan" sendiri, akhirnya meminta dan / atau mengirim pesan ke kendaraan lain) juga memungkinkan bagi saya untuk mengimplementasikan CA AI di tingkat pusat (mengirim perintah ke kendaraan).
- Dalam sebagian besar kasus, kendaraan hanya harus menghindari satu sama lain ke segala arah, tetapi dalam keadaan tertentu, mereka harus menghindari tabrakan dan pergi ke sasaran yang sama
Apa yang saya temukan sejauh ini dan di mana saya terjebak
Di dalam banyak banyak tautan yang saya temukan di pertanyaan lain di situs ini, saya menemukan penggunaannya sebagai berikut:
Walaupun ketiga tautan ini "membuka mata saya" dalam banyak hal, tidak segera jelas bagi saya bagaimana menggunakan informasi itu dalam kasus saya. Dalam artikel # 2 khusus hanya "mencoba" untuk mencegah tabrakan (tetapi tabrakan memang terjadi dari waktu ke waktu). Sementara artikel # 3 perlu menghentikan kendaraan kadang-kadang untuk mencegah tabrakan.
Apa yang juga saya perhatikan, adalah bahwa algoritma penghindaran benturan yang dihubungkan di atas menggunakan "proyeksi instan" kecepatan linear untuk memeriksa apakah ada sesuatu yang menghalangi kendaraan. Saya bertanya-tanya apakah ini cukup dalam kasus saya atau jika saya harus memproyeksikan posisi saya dengan cara yang lebih realistis (misalnya: Jika saya 60 ° ke kemudi 90 ° ke kanan, saya harus menghitung posisi saya untuk sisa 30 ° dari kurva, dan kemudian mengasumsikan gerakan linier).
Akhirnya, saya sangat takut akan kebuntuan . Dengan kata lain: meskipun kepadatan kendaraan di dunia akan cukup rendah, saya khawatir bahwa mengingat sejumlah kendaraan tertentu berkumpul menuju titik yang sama, begitu mereka akan menyadari bahwa mereka berada di jalur tabrakan, setiap manuver mengelak tidak akan mungkin karena akan membawa kendaraan pada jalur tabrakan dengan beberapa yang lain.
Pertanyaan
Bagaimana saya bisa mencapai "tujuan" saya? Penjelasan mendalam tentu saja sangat dihargai, tetapi tautan ke sumber daya eksternal juga akan sangat membantu (saya yakin saya bukan yang pertama dengan masalah ini, tapi mungkin saya menggunakan kata kunci yang salah untuk mencari di web? )
Terima kasih sebelumnya atas bantuan Anda!
Jawaban:
Sudahkah Anda melihat algoritma berkelompok ? Ketika saya melihat deskripsi Anda, itulah yang terlintas dalam pikiran saya. Ada banyak artikel untuk ini, ini yang saya suka . Kemungkinan Anda tidak akan menggunakan semua aspek berkelompok, seperti kohesi. Sebagian besar aspek akan berguna untuk apa yang Anda coba lakukan, seperti penyelarasan dan pemisahan, yang keduanya akan membantu menghindari tabrakan. Anda akan berakhir dengan sesuatu yang sedikit berbeda dari berkelompok, tetapi itu akan membantu Anda memulai.
Semoga berhasil!
sumber
Berikut ini pendekatannya: Setiap kendaraan memiliki lintasan pendek yang diproyeksikan di mana kendaraan pada akhirnya melambat dan memasuki lingkaran, lintasan ini mungkin tidak tumpang tindih. Setiap kali kendaraan datang ke titik di mana ia diatur untuk memperlambat Anda mencoba untuk menghasilkan jalur baru yang tidak tumpang tindih dengan yang ada. Jika ternyata tidak memungkinkan, kendaraan melanjutkannya di jalur yang diberikan dan mencoba membuat jalur baru secara berkala.
Metode ini dapat ditingkatkan untuk memungkinkan lalu lintas yang lebih ketat dengan membiarkan jalur yang mengarah ke loop saling tumpang tindih dan loop di mana dapat ditentukan bahwa ini tidak akan menyebabkan tabrakan.
sumber
Memiliki metode di setiap kendaraan di mana ia melakukan pencarian radial di sekelilingnya, jika ada kendaraan lain di dalam radius ini, menjauhlah dengan cara yang sesuai dengan keinginan Anda: 1) Bergerak dalam vektor yang berlawanan, 2) melambat, 3) mempercepat, dll.
Anda bahkan dapat melakukan kombinasi: Jika vektor kendaraan lain tidak lurus ke depan atau tepat di belakang: menjauh; lain jika lurus di depan: melambat; lain: mempercepat.
sumber
Jika ini memungkinkan, itu akan dimasukkan ke dalam semua pesawat dunia sekarang.
Saya menyarankan untuk menenangkan aspek 'otonom' dan memiliki fungsi yang menyelesaikan tabrakan yang diperkirakan antara 2 (atau lebih) kendaraan. Ini bisa sama naifnya dengan memilih arah baru secara acak untuk bepergian dan melihat apakah itu menyelesaikan masalah, tetapi yang penting adalah bahwa fungsinya hanya kembali ketika sudah mencapai kesepakatan yang sesuai dengan kedua kendaraan.
Saya juga menyarankan bahwa kendaraan apa pun yang diperkirakan akan bertabrakan dalam waktu dekat mengurangi kecepatannya dengan tetap menjaga jarak pandang yang sama - ini akan memberi kendaraan Anda lebih banyak peluang untuk menghindari tabrakan, seperti halnya dalam kehidupan nyata.
sumber
Kedengarannya bagi saya bahwa simulasi kerumunan mungkin menjadi topik yang paling relevan dengan apa yang Anda coba capai. Kelompok GAMMA di UNC memiliki sejumlah besar pekerjaan pada subjek yang mungkin perlu ditelaah. Deskripsi mereka:
http://gamma.cs.unc.edu/research/crowds/
sumber
Saya tidak berpikir ada metode penghindaran 100%, tetapi jika kendaraan Anda memiliki informasi dunia penuh, Anda bisa membungkus setiap kendaraan ke dalam kotak yang panjangnya tergantung pada kecepatannya, dan melakukan pemeriksaan tabrakan pada kotak-kotak itu. Jika memang ada tabrakan, menjauhlah, dengan kekuatan tergantung pada dampak yang akan terjadi (atau area tabrakan antara dua kotak), dan memperlambat dow (tapi simpan kotak Anda sama panjang selama operasi penghindaran).
Jelas ini tidak akan berfungsi jika kendaraan tidak memiliki informasi lengkap, tetapi dalam hal ini tidak ada yang akan menjamin penghindaran 100% (kecuali, seperti yang telah dikatakan, gerakan paralel)
beberapa metode yang dijelaskan di sini mungkin akan bermanfaat, terutama yang ini: Perilaku kemudi yang tidak selaras Menghindari tabrakan
salam
sumber