Membuat AI mengambil jalur yang berbeda satu sama lain

16

Saya memiliki permainan 2d dari atas ke bawah di mana AI muncul di tepi peta dan berlari ke tengah.

Saya menggunakan A * dan simpul mesh untuk melakukan pathfinding.

Saat ini, AI menelurkan pada titik di tepi peta dan semua mengambil jalur yang sama yang merupakan rute terpendek ke pusat.

Sekarang saya ingin mereka lebih mengejutkan dan menarik dan mengambil jalan yang berbeda satu sama lain.

Saya dapat langsung memikirkan dua ide untuk melakukan ini tetapi ingin tahu apakah ada cara lain atau cara yang lebih baik yang sering digunakan orang?

  1. Ketika satu musuh menumbuhkan dan menghasilkan jalur ke pusat, sementara meningkatkan biaya semua node di jalur itu, kemudian perlahan-lahan turunkan kembali dari waktu ke waktu. Maka musuh AI yang akan muncul nanti akan dipaksa untuk mengambil jalan yang lebih luas.

  2. Pendekatan di atas akan menyebabkan AI hanya mengambil jalur yang lebih luas dan lebih luas dan masih sangat dapat diprediksi. Jadi saya pikir saya juga akan memperkenalkan sejumlah node tujuan menengah di sekitar peta. Ketika AI menelurkan mereka secara acak memilih salah satu tujuan menengah dan menuju ke sana terlebih dahulu sebelum menuju ke tengah peta. Menggabungkan ini dengan pendekatan di atas untuk meningkatkan biaya mungkin terlihat cukup bagus?

Pendekatan apa yang orang temukan bekerja paling baik untuk mendapatkan AI untuk memvariasikan jalan yang mereka ambil, terlihat meyakinkan dan mengejutkan?

TerryB
sumber

Jawaban:

7

Opsi kedua Anda mengisyaratkan pendekatan yang lebih mendasar: memastikan musuh mendekati pemain Anda dari arah yang berbeda. Pertanyaannya adalah, seberapa jauh mereka harus melakukan perjalanan untuk mendapatkan "sekitar" pemain Anda? Yang ideal untuk ini adalah campuran

  • menghasilkan poin yang secara dinamis mengelilingi (yaitu mengikuti) posisi pemain;
  • apa yang Nevermind telah menyarankan dalam hal jalur acak ke titik-titik sekitarnya, ke tingkat yang lebih besar atau lebih kecil.

Dengan cara ini, Anda dapat memastikan bahwa AI tidak akan mengambil jalan memutar yang tidak perlu hanya untuk mendapatkan variasi jalur yang realistis saat melakukan konvergensi pada pemain.

Difusi kolaboratif melakukan apa yang Anda inginkan secara implisit sebagai bagian dari algoritma. Tapi itu tidak mudah untuk diterapkan.

Insinyur
sumber
Difusi kolaboratif hanyalah isian banjir dengan bobot. Ini sepele untuk diterapkan, mungkin lebih mudah daripada A *. Ini hanya membutuhkan pandangan yang berbeda dari dunia Anda - perubahan konseptual yang tidak sepele, mungkin, tetapi tidak ada masalah implementasi.
Ini masih non-sepele untuk diterapkan karena itu menjadi sudut pandang non-standar dalam hal mengelola entitas AI :)
Engineer
Terima kasih Nick. Saya pikir pengaturan beberapa titik arah yang mengelilingi pemain di tengah peta akan menjadi cara utama untuk pergi. Tidak yakin pada tahap ini apakah mereka akan dihasilkan secara dinamis atau melibatkan kerajinan tangan untuk setiap level untuk situasi khusus saya. Terima kasih lagi!
TerryB
12

Sebagai ide pertama, coba tambahkan nilai acak kecil ke bobot masing-masing simpul saat merintis jalan. Dengan cara ini, setiap agen akan mencari jalan di lingkungan yang sedikit berbeda. Saya tidak yakin apakah ini akan berhasil dalam kasus Anda, tetapi harusnya benar-benar mudah untuk dicoba.

Lupakan
sumber
Musuh-musuh pada akhirnya akan berjalan seperti ayam, dan di lingkungan berbutir halus jalannya tidak akan begitu berbeda. Ini merupakan tambahan yang bagus untuk solusi lain, tetapi bukan solusi itu sendiri
Coyote
@Coyote Ini sangat tergantung pada struktur nav-mesh, dan hubungan antara bobot node, kecepatan dan komponen acak. Itu sebabnya saya membingkai jawaban sebagai saran untuk dicoba, bukan sebagai jawaban yang pasti.
Nevermind
Memang :) Saya biasanya penggemar entropi. Tetapi hasil akhirnya jarang bagus.
Coyote
Saya benar-benar percaya jawaban Nick Wiggill jauh lebih baik daripada jawaban saya. Tetapi entah bagaimana itu tidak mendapatkan upvotes yang layak.
Nevermind
Itu adalah ... Tetapi milik Anda adalah yang pertama dan lebih sederhana ... kita dapat mencoba untuk memilih: P
Coyote
3

Saya suka jawaban Nevermind , namun, mengingat batasan yang dijelaskan dalam komentar inilah yang akan saya coba:

  1. Algoritma untuk satu unit ke pusat, mencatat jarak total yang ditempuh.
  2. Untuk setiap unit berikutnya mengalokasikannya jarak yang acak dan jumlah kecil lebih lama dari ini.
  3. Saat melakukan A * untuk setiap unit, tambahkan bobot ekstra berdasarkan seberapa dekat Anda dan seberapa jauh Anda 'ingin' bepergian. Ini mungkin akan seperti sesuatu(distanceToGoal) + Max(0, desiredDistance - distanceTravelled)) .

Ini akan membuat unit berusaha untuk melangkah lebih jauh, yang mungkin merupakan jalur yang berbeda, yang akan menghasilkan mereka mungkin mengambil jalur yang berbeda.

Anda juga bisa menambahkannya ke huerestic awal Anda untuk setiap unit, tetapi rentang acak mungkin harus sedikit lebih besar.

Jonathan Dickinson
sumber
2

Seperti yang ditunjukkan oleh Nick Wiggill, pendekatan paling sederhana adalah dengan mendapatkan lingkaran di sekitar tujuan.

  • secara acak berikan titik dekat dengan lingkaran ini sebagai titik lewat.
  • menghilangkan semua jalur dalam lingkaran dari jalur awal (atau meningkatkan nilai titik-titik ini secara dramatis)
  • kemudian dari titik arah itu dapatkan jalan menuju tujuan.

Bagian penting adalah untuk menghilangkan semua jalur dalam lingkaran untuk titik jalan asli karena Anda mungkin akan berakhir dengan musuh melintasi lingkaran untuk sampai ke titik jalan awal mereka.

Dari sana Anda bisa mendapatkan varian apa pun dengan bermain dengan beberapa nilai menambahkan titik arah sekunder di lingkaran dekat dengan yang awal dll.

Anjing hutan
sumber
jika peta Anda mendukungnya, cari lokasi 'menarik' di sekitar lingkaran ini (pintu, tutup, pohon, batu, bangunan; sembarang simpul dengan keunggulan taktis) dan minta musuh Anda menuju lokasi tersebut terlebih dahulu jika tersedia dan hanya muncul di terbuka jika mereka harus. Ini akan terlihat jauh lebih pintar daripada hanya mengenai titik acak di tepi lingkaran.
DampeS8N
Terima kasih Coyote, ya saya mungkin akan pergi dengan solusi Nicks dan seperti yang disarankan oleh DampeS8N beberapa lokasi utama yang menarik sebagai titik arah. Untuk menghindari masalah AI "crossing the circle" Saya hanya akan sangat meningkatkan biaya node dalam lingkaran sehingga A * harus merutekaninya semoga :)
TerryB
2

Masalah Anda di sini pada dasarnya adalah bahwa A * adalah algoritma untuk menemukan rute tercepat ke target. Jika itu adalah kriteria utama Anda untuk jalur 'baik', maka tidak mengejutkan bahwa semua aktor Anda membuat keputusan yang sama.

Yang perlu Anda lakukan adalah memodifikasi kriteria kualitas Anda untuk jalur, sehingga 'terpendek adalah yang terbaik' bukan satu-satunya faktor. Unsur keacakan adalah kunci dalam hal ini, tetapi tidak terlalu banyak sehingga mengurangi kecerdasan pencarian-jalur (yaitu para aktor mengambil jalan memutar yang bundar ke target).

Pathfinding bawaan naif, karena biasanya mengasumsikan bahwa aktor memiliki pengetahuan yang sempurna tentang seluruh rute sebelum dimulai. Itu akan selalu terlihat tidak realistis. Solusinya menyarankan agar memilih tujuan antara adalah selangkah lagi - AI berusaha mendekati target, tetapi hanya mencoba bernavigasi dalam bagian kecil sekaligus (ini analog dengan kehidupan nyata di mana Anda hanya dapat menavigasi sejauh ini seperti yang Anda lihat, dan saat Anda melintasi lebih banyak jalan, Anda bisa melihat lebih jauh ke depan).

Saya mungkin akan merekomendasikan cara yang lebih sederhana untuk melihatnya. Ketika Anda mencari jalan, jangan hanya mempertahankan satu jalur terbaik yang saya temukan sejauh ini. Sebagai gantinya, kumpulkan satu set jalur 5 atau 10 terbaik. Gunakan ambang batas untuk membuang outlier yang jelas. Misalnya jika jalur terbaik melintasi 20u untuk mencapai target, jalur terbaik berikutnya 21u, dan yang berikutnya setelah itu melintasi 50u. Tetapkan ambang batas 20% lebih besar dari jalur terbaik, jadi buang jalur 50u karena lebih panjang. Sekarang Anda memiliki beberapa jalur untuk dipilih, dan dengan memilih secara acak dari serangkaian jalur itu, aktor Anda akan membuat keputusan yang berbeda.

Namun Anda tidak akan mendapatkan informasi seperti ini dengan pencarian A * standar, jadi saya pikir Anda harus memodifikasi algoritme atau menggunakan sesuatu yang lain untuk mengumpulkan serangkaian jalur yang mungkin.

MrCranky
sumber
1

Jika Anda memiliki satu set kecil musuh berulang (atau tipe musuh), Anda dapat mencoba memberi mereka kepribadian yang mempengaruhi gerakan mereka. Mereka tidak harus menjadi hal besar, hanya hal-hal yang muncul setiap saat. Contoh yang baik dari ini adalah hantu dari Pac-Man. Biarkan A * Anda dibagi menjadi beberapa sasaran perantara. Mungkin satu musuh benar-benar bodoh dan tersesat dengan mudah, menuju ke arah acak setiap simpul ketiga (selain langsung mundur). Jadilah kreatif.

Beberapa pria
sumber