Bergerak / menghindari rintangan

12

Saya ingin menulis "permainan", di mana Anda dapat menempatkan penghalang (merah), dan kemudian titik hitam mencoba menghindarinya, dan mencapai target hijau.
Saya menggunakan cara yang sangat mudah untuk menghindarinya, jika titik hitam dekat dengan merah, ia mengubah arahnya, dan bergerak sebentar, lalu bergerak maju ke titik hijau.
Jalan "tidak realistis"

Bagaimana saya bisa membuat jalur "halus" untuk "pemain" yang dikendalikan komputer?
Sunting: Bukan kelancaran adalah poin utama, tetapi untuk menghindari "dinding" pemblokiran merah dan tidak menabraknya lalu menghindarinya.

Bagaimana saya bisa menerapkan beberapa algoritma pencarian jalur jika pada dasarnya saya hanya memiliki 3 poin?
(Dan apa yang akan membuat hal-hal menjadi jauh lebih rumit, jika Anda dapat menempatkan banyak rintangan?)
Jalur yang mulus

ai path-finding pengguna
sumber

Jawaban:

9

Pendekatan yang sangat umum dan umum adalah membagi ruang dunia Anda ke dalam kisi-kisi dan menggunakan algoritma seperti A *.

Tautan ini membantu saya memulai dengan memahami dan menerapkan algoritma A *.

Edit :

Pikiran yang lebih sederhana yang muncul di benak saya adalah ... begitu Anda memiliki dunia ke dalam sel-sel. Selalu, minta titik hitam mengikuti jarak manhattan ke titik hijau. Kemudian, Anda dapat menetapkan bobot untuk setiap sel. Rintangan dapat memiliki berat yang tinggi pada sel-grid dan free-to-move dapat memiliki (katakanlah) 0 bobot. Saat Anda bergerak di sepanjang jarak manhattan, untuk setiap gerakan, periksa untuk melihat apakah berat sel berikutnya tidak lebih tinggi dari berat sel saat ini. Jika lebih tinggi, periksa berat sel yang berdekatan lalu lanjutkan.

Semoga ini membantu

brainydexter
sumber
Artikel algoritma A * ini sepertinya adalah yang saya cari, tetapi sayangnya yang masih belum saya ketahui adalah bagaimana membagi "dunia" saya ke dalam kisi-kisi: S
user
Itu sangat tergantung. Pikir: bagi dunia Anda menjadi kisi-kisi 32 x 32 yang kemudian akan mewakili posisi dalam array 2D. Misalnya, dalam kasus Anda: titik merah berada pada 120, 120 piksel (atau 120/32 x 120/32: 3,75 x 3,75) 3,75 x 3,75 mewakili posisi di jaringan-dunia Anda (atau larik 2D). Karena array diindeks oleh integer, Anda hanya ingin bagian integer darinya. Dengan demikian, titik merah akan berada di 3 x 3. Semoga ini bisa membantu
brainydexter
18

Setir perilaku dirancang untuk set masalah yang tepat ini.

http://www.red3d.com/cwr/steer/

Pada dasarnya Anda akan menggabungkan perilaku penghindaran rintangan dengan mungkin perilaku mencari atau mengejar. Halaman itu memiliki banyak animasi java dari berbagai perilaku dan apa yang mereka lakukan. Ada beberapa implementasi open source dari perilaku kemudi. Ini dia.

Tetrad
sumber
Perilaku kemudi sangat cocok untuk ini.
tenpn
2

Hal yang mudah untuk dicoba adalah memiliki titik tak terlihat yang berjalan di depan titik hitam dan mengeksekusi jalur di gambar pertama Anda. Titik hitam kemudian mengikuti titik yang tak terlihat pada jarak kecil di belakang.
Saya telah melihat pekerjaan ini dengan hasil yang baik tetapi tentu saja mungkin tidak sesuai dengan kebutuhan Anda.

Paulo Pinto
sumber