Bagaimana RTS Penghindaran Lokal Dilakukan?

15

Saat ini, saya mensimulasikan kekuatan dampak fisika untuk penghindaran lokal unit tetapi metode ini kadang-kadang mendorong unit keluar dari formasi dan memiliki efek yang sangat tidak diinginkan ketika unit menggumpal.

Untuk game RTS seperti Starcraft 2, bagaimana penghindaran lokal dilakukan? Apakah fisika disimulasikan atau pengontrol omnicient memutuskan di mana semuanya seharusnya? Saya tahu pertanyaan ini mungkin sedikit luas, jadi saya bertanya secara spesifik bagaimana cara mencapai perilaku penghindaran lokal Starcraft 2; meskipun apa pun yang bekerja akan sangat dihargai.

Saya tidak mencari kode apa pun - hanya sumber daya yang berguna atau penjelasan tentang bagaimana Starcraft 2 (atau game serupa) menangani penghindaran lokal.

Saat ini, saya memiliki deteksi tabrakan (dengan vektor penetrasi), gaya tabrakan, dan gerakan dengan kecepatan diimplementasikan. Setiap unit diperiksa terhadap yang lain untuk tabrakan - jika mereka bertabrakan, objek segera diimbangi oleh vektor penetrasi maka gaya tabrakan diterapkan. Kemudian loop lain menggerakkan objek dengan kecepatannya dan menerapkan gaya tarik ke kecepatan. Offset ini mengurangi masalah gaya tabrakan yang berlebihan yang diterapkan pada unit bergerombol, tetapi unit kadang-kadang masih menembak.

Solusi yang saya cari perlu memenuhi persyaratan berikut (seperti dalam Starcraft 2):

  • Objek tidak tumpang tindih; atau setidaknya tumpang tindih akhirnya harus diselesaikan.
  • Objek tidak mendorong satu sama lain lebih dari yang diperlukan sehingga 2 unit dapat berdiri dan bergerak bersebelahan dalam suatu formasi.
  • Seharusnya tidak ada perilaku aneh ketika benda-benda menggumpal ke arah tujuan yang sama.
  • Dapat mendukung unit dengan ukuran yang berbeda, dan bahkan bentuk cembung yang berbeda.

Apa yang saya pikirkan sejauh ini adalah bukannya mendeteksi tabrakan, mendeteksi tabrakan di masa depan sehingga tumpang tindih tidak pernah terjadi. Kemudian terapkan kendala, pastikan kecepatan 2 unit tidak menyebabkan mereka tumpang tindih. Saya masih mengutak-atik algoritma untuk membatasi gerakan di luar tumpang tindih.

JPtheK9
sumber
"berkelompok perilaku" (istilah google) adalah masalah yang sangat luas,
ratchet freak
Ini dalam antrian penutupan suara sebagai "terlalu luas" —saya cenderung setuju. Mencoba mempersempit: Apa yang sudah Anda coba? "Efek yang tidak diinginkan" apa yang ingin Anda hindari? Apakah saya benar mengatakan Anda ingin unit tetap dalam formasi?
Anko
Game RTS sering bekerja oleh setiap klien yang menjalankan simulasi deterministik yang sama pada setiap mesin. Jadi pada dasarnya, jika Anda dapat menyelesaikannya untuk satu mesin, Anda dapat menerapkan solusi yang sama untuk situasi multipemain, teknik penghindaran lokal apa pun yang Anda gunakan.
Alan Wolfe
Terima kasih atas umpan balik atas pertanyaannya. Saya mempersempit pertanyaan dan menjelaskan secara spesifik apa yang ingin saya capai.
JPtheK9
Ini adalah sumber yang bagus: red3d.com/cwr/steer
tbkn23

Jawaban:

11

Sepertinya yang Anda cari adalah algoritma Optimal Reciprocal Collision Avoidance . The kertas sebelumnya juga layak membaca. Meskipun makalah ini mungkin sedikit melibatkan teori di balik algoritma ini cukup mudah:

Asumsikan bahwa Anda sudah memiliki simulasi (permainan) dengan agen (unit) yang memiliki semacam volume pembatas di sekitar mereka. Volume pembatas ini kemungkinan besar sudah Anda gunakan untuk melakukan deteksi dan respons tabrakan. Untuk setiap agen, tentukan kecepatan v_pyang disukai yang mungkin atau mungkin tidak didasarkan pada tujuan agen.

Sekarang, untuk melakukan simulasi:

  1. Untuk setiap agen, dengan anggapan bahwa itu diam, hitung semua kecepatan yang akan menyebabkannya bertabrakan pada titik mana pun di masa depan dengan agen penggerak lainnya. Ini dapat direpresentasikan dalam "ruang kecepatan" sebagai seperangkat bidang setengah berpotongan (juga dikenal sebagai hambatan kecepatan ).
  2. Tentukan titik di ruang ini terdekat v_p, ini adalah kecepatan baru unit.

Jika semua agen menjalankan algoritma yang sama, maka mereka akan memilih kecepatan yang saling melengkapi satu sama lain dan akan menghindari agen lain. Dalam beberapa situasi, Anda dapat menyebabkan osilasi seperti hal canggung yang terjadi ketika Anda berjalan langsung ke seseorang di aula dan Anda berdua mencoba untuk bergerak keluar dari arah yang sama, tetapi makalah tersebut membahas cara menghindarinya.

Untuk menghitung dua tahap algoritma di atas, Anda dapat menggunakan Minkowski Sums untuk menentukan apa hambatan kecepatan, dan kemudian menggunakan model pemrograman linier (seperti Algoritma Simplex ) untuk menentukan titik terdekat dengan v_pyang menghindari hambatan kecepatan. Juga, kode untuk melakukan penghindaran tabrakan tersedia untuk teliti Anda dan telah porting ke C # untuk digunakan dalam mesin game seperti Unity. Teknik ini telah digunakan setidaknya di Warhammer 40.000: Space Marine , dan mungkin game lainnya .

Mokosha
sumber
Itu adalah artikel yang luar biasa dan saya merasa saya akan membaca setengahnya dari penjelasan Anda. Terima kasih atas informasi ini.
JPtheK9
0

Saya tidak tahu bagaimana unit Anda bekerja tetapi saya berasumsi bahwa mereka seperti mesin negara:

Kemungkinan status

  • Berlari ke (x, y, z)
  • Attaking (enemy_id)
  • Mengumpulkan ressource (ressource_id)

Jika Anda memperhatikan bagaimana starcraft mendekati masalah ini, Anda akan menemukan bahwa:

  1. Jika ada ruang untuk bergerak ke suatu arah, charachter bergerak ke arah itu.
  2. Jika tidak ada ruang, unit di jalan akan bergerak untuk membuat ruang
  3. Jika unit yang perlu bergerak untuk membuat ruang sudah memiliki perintah, itu akan menjaga perintah, tetapi memodifikasinya sedikit untuk akhirnya membuat tempat.

Di sini skenario 1:

masukkan deskripsi gambar di sini

Apakah saya memiliki ruang untuk pergi ke sana? Iya ? Lalu pergi

Skenario 2:

masukkan deskripsi gambar di sini

Apakah saya memiliki ruang untuk pergi ke sana? Tidak ? Hei, bisakah kamu menyediakan ruang untukku, kamu menghalangi aku. Saya sudah memiliki perintah untuk pindah foward tetapi saya akan mengakomodasi Anda.

Jadi apa yang perlu Anda terapkan:

  • Unit harus menyadari lingkungannya
  • Unit harus memiliki cara untuk berkomunikasi satu sama lain
  • Anda harus menerapkan cara untuk tetap menjalankan perintah sambil mengakomodasikan unit lain
Antoine
sumber
Terima kasih atas info dan visualisasi. Saat ini saya sedang menggunakan deteksi tabrakan untuk mengetahui apakah suatu unit dapat pindah ke tempat lain atau jika unit lain sedang menempatinya. Hal utama yang saya coba cari tahu adalah algoritma dari beberapa jenis untuk memberi tahu unit lain berapa jarak untuk bergerak atau berapa kecepatan untuk menyesuaikan. Dengan kata lain, bagaimana unit pemblokiran akan mengakomodasi unit yang mencoba untuk lulus.
JPtheK9
Karena perilaku ini dihitung setiap pembaruan fisika, Anda tidak benar-benar harus tahu jaraknya, itu akan bergerak sampai keluar dari jalan. Untuk arah, Anda memindai cukup gandakan kecepatan dari dua unit, ini akan memberi Anda titik di tengah sehingga terus bergerak sambil mengakomodasi. Setelah itu Anda bisa bermain-main dengan itu untuk membuatnya sehingga lebih menempel pada urutan atau keluar dari jalan lebih cepat.
Antoine
Apa yang Anda maksud dengan "bergerak sampai keluar dari jalan"? Bagaimana unit bergerak di tempat pertama?
JPtheK9
Maaf saya lupa menyebutkan: Unit bukan mesin negara. Mereka memiliki banyak kemampuan di loker mereka yang disimulasikan setiap frame - kecuali kemampuan ini hanya memiliki efek ketika diaktifkan, baik dengan tujuan jarak X atau dengan adanya target. Gerakan suatu unit adalah hasil dari kecepatannya yang dapat diubah oleh suatu kemampuan.
JPtheK9
0

Salah satu cara untuk melakukannya adalah dengan memiliki formasi form otomatis unit, dan meminta mereka untuk tetap pada posisi yang relatif terhadap pusat formasi . Kemudian, alih-alih memindahkan setiap unit, pindahkan pusat formasi secara terpisah.

Berikut adalah cara dasar untuk melakukannya menggunakan formasi kotak dan pegas sederhana untuk menjaga unit di posisi yang sesuai:

// Defines a phalanx (box) formation
class Formation
    // Center of the box in the world
    Position center;
    // Width in # of units
    int width;
    // Height in # of units
    int height;
    // Space between units
    float scale;
    // How much force units will apply to stay near
    // their assigned spot.
    float springforce;

    // Return a position of a unit at the given row and column
    // Todo: add a rotation to this formation so it can rotate when moving.
    Position GetUnitPhalanxPosition(int row, int column)
        return new Position(center.X + column * scale - width * scale /2, 
                            center.Y + row * scale    - height* scale / 2);

// Represents a simple point object with a velocity and position;
// it belongs to a formation.
class Unit
    Position pos;
    Velocity vel;
    Formation formation;
    // What's our assigned spot in the formation?
    int row;
    int column;

    void Update(float dt)
        // Get the desired target position in the formation
        Position target = formation.GetUnitPhalanxPosition(row, column);
        // Apply a spring force toward the position (todo: you might want to damp this)
        vel += (target - position) * dt * formation.springforce;
        // Move along the velocity vector.
        pos += vel * dt;
mklingen
sumber
Terima kasih! Ini adalah solusi yang sangat menarik dan kreatif. Saya telah menerapkan sesuatu yang mirip dengan ini untuk perilaku kerumunan / formasi tetapi saya masih memiliki masalah unit yang tumpang tindih. Apa yang harus terjadi jika 2 formasi bertemu satu sama lain?
JPtheK9
Saya pikir itu tergantung desainnya. Hal yang paling mudah adalah dengan menggunakan kekuatan kemudi lain dari unit terdekat dalam formasi lain seperti pada gambar ini . Hal lain yang dapat Anda lakukan adalah menggabungkan formasi bersama ketika formasi tersebut dipilih oleh pemain, atau bahkan membentuk "meta-formasi"
mklingen
Meta-formasi terdengar sangat rumit dan bermasalah: C. Gambar yang Anda tautkan mungkin persis seperti yang saya butuhkan. Saya akan melakukan penelitian lebih lanjut tentang kekuatan kemudi. Apakah Anda memiliki tautan ke artikel gambar?
JPtheK9
Saya memiliki masalah yang sama dengan Anda, akan menarik untuk mengetahui bagaimana Anda menyelesaikannya. Satu ide muncul di pikiran setelah membaca artikel ini: mungkin menggabungkan Pathfinding (A *) untuk perencanaan jalur makro sambil menggunakan kekuatan reppel untuk menghindari tabrakan mikro:
ColdSteel
0

Saya tahu beberapa orang tidak menyukai link dumping, namun saya menemukan Pendekatan Berbasis Potensi Multi-Agen untuk Bot Game Strategi Real-Time (ISBN 978-91-7295-160-0) sebagai kertas yang sangat mencerahkan, dan itu jelas menyampaikan jauh lebih dari yang saya bisa uraikan. Makalah ini mengeksplorasi menggunakan bidang potensial buatan (konsep yang berasal dari robot), untuk memfasilitasi penghindaran tabrakan lokal dalam konteks pengembangan game.

DanoThom
sumber
Terima kasih! Penelitian sama bermanfaatnya dengan penjelasan bagi saya. Saya akan terjun ke makalah ini.
JPtheK9
Saya memiliki peta pengaruh yang sudah diatur tetapi ini tampaknya terlalu rumit untuk seleraku. Hal utama adalah menghasilkan bidang potensial untuk unit yang berbeda untuk memindahkannya, dan juga mengubah data dari bidang potensial menjadi kecepatan untuk bergerak. Pada dasarnya, saya tidak berpikir ini akan bekerja untuk unit dengan ukuran yang berbeda. Ini adalah bacaan yang bagus dengan banyak ide menarik.
JPtheK9