Pohon Perilaku Preempting

Saya mencoba untuk mendapatkan kepalaku sekitar pohon perilaku, jadi saya mengeluarkan beberapa kode tes. Satu hal yang saya perjuangkan adalah bagaimana mendahului simpul yang sedang berjalan saat sesuatu dengan prioritas yang lebih tinggi muncul.

Pertimbangkan pohon perilaku fiktif sederhana berikut untuk seorang prajurit:

Misalkan sejumlah kutu telah lewat dan tidak ada musuh di dekatnya, prajurit itu berdiri di atas rumput, sehingga simpul Duduk dipilih untuk eksekusi:

Sekarang aksi Duduk butuh waktu untuk mengeksekusi karena ada animasi untuk dimainkan, sehingga kembali Runningsebagai statusnya. Satu atau dua tanda centang lewat, animasi masih berjalan, tetapi Musuh dekat? pemicu node kondisi. Sekarang kita perlu mendahului node Sit ASAP sehingga kita dapat menjalankan node Attack . Idealnya prajurit itu bahkan tidak akan selesai duduk - dia malah bisa membalikkan arah animasinya jika dia baru saja mulai duduk. Sebagai tambahan realisme, jika dia melewati titik kritis dalam animasi, kita mungkin memilih untuk membiarkannya selesai duduk dan kemudian berdiri lagi, atau mungkin membuatnya tersandung dalam tergesa-gesa untuk bereaksi terhadap ancaman.

Berusaha sekuat tenaga, saya belum dapat menemukan panduan tentang bagaimana menangani situasi semacam ini. Semua literatur dan video yang saya konsumsi selama beberapa hari terakhir (dan itu sudah banyak) tampaknya mengesampingkan masalah ini. Hal terdekat yang dapat saya temukan adalah konsep mengatur ulang node yang sedang berjalan, tetapi itu tidak memberikan node seperti Duduklah kesempatan untuk mengatakan "hei, saya belum selesai!"

Saya berpikir mungkin mendefinisikan Preempt()atau Interrupt()metode pada Nodekelas dasar saya . Node yang berbeda dapat mengatasinya sesuai keinginan mereka, tetapi dalam kasus ini kami akan berusaha mendapatkan prajurit itu kembali secepatnya dan kemudian kembali Success. Saya pikir pendekatan ini juga akan mengharuskan basis saya Nodememiliki konsep kondisi secara terpisah untuk tindakan lain. Dengan begitu, mesin hanya dapat memeriksa kondisi dan, jika mereka lulus, mendahului setiap node yang sedang mengeksekusi sebelum memulai eksekusi tindakan. Jika diferensiasi ini tidak ditetapkan, mesin akan perlu mengeksekusi node secara membabi buta dan karena itu dapat memicu tindakan baru sebelum mencegah yang sedang berjalan.

Untuk referensi, di bawah ini adalah kelas dasar saya saat ini. Sekali lagi, ini adalah lonjakan, jadi saya telah berusaha untuk menjaga hal-hal sesederhana mungkin dan hanya menambah kompleksitas ketika saya membutuhkannya, dan ketika saya memahaminya, itulah yang sedang saya perjuangkan sekarang.

public enum ExecuteResult
{
    // node needs more time to run on next tick
    Running,

    // node completed successfully
    Succeeded,

    // node failed to complete
    Failed
}

public abstract class Node<TAgent>
{
    public abstract ExecuteResult Execute(TimeSpan elapsed, TAgent agent, Blackboard blackboard);
}

public abstract class DecoratorNode<TAgent> : Node<TAgent>
{
    private readonly Node<TAgent> child;

    protected DecoratorNode(Node<TAgent> child)
    {
        this.child = child;
    }

    protected Node<TAgent> Child
    {
        get { return this.child; }
    }
}

public abstract class CompositeNode<TAgent> : Node<TAgent>
{
    private readonly Node<TAgent>[] children;

    protected CompositeNode(IEnumerable<Node<TAgent>> children)
    {
        this.children = children.ToArray();
    }

    protected Node<TAgent>[] Children
    {
        get { return this.children; }
    }
}

public abstract class ConditionNode<TAgent> : Node<TAgent>
{
    private readonly bool invert;

    protected ConditionNode()
        : this(false)
    {
    }

    protected ConditionNode(bool invert)
    {
        this.invert = invert;
    }

    public sealed override ExecuteResult Execute(TimeSpan elapsed, TAgent agent, Blackboard blackboard)
    {
        var result = this.CheckCondition(agent, blackboard);

        if (this.invert)
        {
            result = !result;
        }

        return result ? ExecuteResult.Succeeded : ExecuteResult.Failed;
    }

    protected abstract bool CheckCondition(TAgent agent, Blackboard blackboard);
}

public abstract class ActionNode<TAgent> : Node<TAgent>
{
}

Adakah yang punya wawasan yang bisa mengarahkan saya ke arah yang benar? Apakah pemikiran saya sesuai dengan garis yang benar, atau naif seperti yang saya takutkan?

Saya menemukan diri saya mengajukan pertanyaan yang sama seperti Anda dan saya memiliki percakapan singkat yang hebat di bagian komentar dari halaman blog ini di mana saya diberi solusi lain untuk masalah ini.

Hal pertama adalah menggunakan simpul konkuren. Simpul serentak adalah jenis khusus simpul komposit. Ini terdiri dari urutan pemeriksaan prasyarat diikuti oleh node aksi tunggal. Ini memperbarui semua node anak-anak bahkan jika node tindakan dalam keadaan 'berjalan'. (Tidak seperti simpul urutan yang harus memulai pembaruan dari simpul anak yang berjalan saat ini.)

Gagasan utamanya adalah membuat dua status pengembalian lagi untuk simpul tindakan: "membatalkan" dan "dibatalkan".

Kegagalan pemeriksaan prekondisi dalam simpul bersamaan adalah mekanisme yang memicu pembatalan simpul aksi yang berjalan itu. Jika node tindakan tidak memerlukan logika pembatalan yang berjalan lama maka akan kembali 'dibatalkan' segera. Jika tidak, ia beralih ke status 'pembatalan' di mana Anda dapat meletakkan semua logika yang diperlukan untuk gangguan tindakan yang benar.

Saya pikir prajurit Anda dapat terurai menjadi pikiran dan tubuh (dan apa pun yang lain). Selanjutnya, tubuh dapat terurai menjadi kaki dan tangan. Kemudian, setiap bagian memerlukan pohon perilaku sendiri, dan juga antarmuka publik - untuk permintaan dari bagian tingkat yang lebih tinggi atau lebih rendah.

Jadi, alih-alih mengelola mikro setiap tindakan, Anda hanya mengirim pesan instan seperti "tubuh, duduk sebentar" atau "tubuh, jalankan di sana", dan tubuh akan mengelola animasi, transisi keadaan, penundaan dan hal-hal lain untuk kamu.

Atau, tubuh dapat mengatur perilaku seperti ini sendiri. Jika tidak ada pesanan, mungkin dia bertanya, "bisakah kita duduk di sini?" Lebih menarik, karena enkapsulasi, Anda dapat dengan mudah memodelkan fitur-fitur seperti kelelahan atau setrum.

Anda bahkan dapat bertukar bagian - membuat gajah dengan kecerdasan zombie, menambahkan sayap ke manusia (dia bahkan tidak akan memperhatikan), atau apa pun yang lainnya.

Tanpa dekomposisi seperti ini, saya yakin Anda berisiko menghadapi ledakan kombinatorial, cepat atau lambat.

Juga: http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Berbaring di tempat tidur semalam, saya memiliki sesuatu yang luar biasa tentang bagaimana saya bisa melakukan ini tanpa memperkenalkan kompleksitas saya condong ke arah dalam pertanyaan saya. Ini melibatkan penggunaan "paralel" komposit (nama buruk, IMHO). Inilah yang saya pikirkan:

Semoga itu masih terbaca. Poin-poin penting adalah:

• urutan Duduk / Tunda / Berdiri adalah urutan dalam urutan paralel ( A ). Pada setiap centang, urutan paralel juga memeriksa kondisi Musuh dekat (terbalik). Jika musuh sudah dekat, kondisinya gagal dan demikian juga seluruh urutan paralel (segera, bahkan jika urutan anak sedang di tengah jalan Duduk , Tunda , atau Berdiri )
• saat gagal, pemilih B di atas urutan paralel akan melompat ke bawah ke pemilih C untuk menangani gangguan. Yang penting, pemilih C tidak akan berjalan jika urutan paralel A selesai dengan sukses
• pemilih C kemudian mencoba untuk berdiri secara normal, tetapi juga dapat memicu animasi tersandung jika prajurit saat ini dalam posisi yang terlalu canggung untuk hanya berdiri

Saya pikir ini akan berhasil (saya akan segera mencobanya), meskipun sedikit lebih berantakan daripada yang saya bayangkan. Hal yang baik adalah bahwa saya pada akhirnya akan dapat merangkum sub-pohon sebagai potongan-potongan logika yang dapat digunakan kembali dan merujuk mereka dari berbagai titik. Itu akan meringankan sebagian besar kekhawatiran saya di sana, jadi saya pikir ini adalah solusi yang layak.

Tentu saja, saya masih ingin mendengar jika ada yang memiliki pemikiran tentang ini.

PEMBARUAN : walaupun pendekatan ini secara teknis berfungsi, saya telah memutuskan sux. Itu karena sub-pohon yang tidak terkait perlu "tahu" tentang kondisi yang ditentukan di bagian lain dari pohon sehingga mereka dapat memicu kematian mereka sendiri. Sementara berbagi referensi sub-pohon akan sedikit meringankan rasa sakit ini, itu masih bertentangan dengan apa yang diharapkan seseorang ketika melihat pohon perilaku. Memang, saya melakukan kesalahan yang sama dua kali pada lonjakan yang sangat sederhana.

Oleh karena itu, saya akan turun rute lain: dukungan eksplisit untuk preempting dalam model objek, dan komposit khusus yang memungkinkan serangkaian tindakan yang berbeda untuk dieksekusi ketika preemption terjadi. Saya akan memposting jawaban terpisah ketika saya memiliki sesuatu yang berfungsi.

Inilah solusi yang telah saya tentukan untuk saat ini ...

• NodeKelas dasar saya memiliki Interruptmetode yang, secara default, tidak melakukan apa pun
• Syarat adalah konstruk "kelas satu", di mana mereka diharuskan untuk kembali bool(dengan demikian menyiratkan bahwa mereka cepat dijalankan dan tidak pernah membutuhkan lebih dari satu pembaruan)
• Node memperlihatkan kumpulan kondisi secara terpisah pada koleksi node anak
• Node.Executejalankan semua kondisi terlebih dahulu dan langsung gagal jika ada kondisi gagal. Jika kondisinya berhasil (atau tidak ada), ia memanggil ExecuteCoresehingga subclass dapat melakukan pekerjaan yang sebenarnya. Ada parameter yang memungkinkan melompati kondisi, untuk alasan yang akan Anda lihat di bawah
• Nodejuga memungkinkan kondisi untuk dieksekusi secara terpisah melalui suatu CheckConditionsmetode. Tentu saja, Node.Executesebenarnya hanya menelepon CheckConditionsketika perlu memvalidasi kondisi
• SelectorKomposit saya sekarang memanggil CheckConditionssetiap anak yang dipertimbangkan untuk dieksekusi. Jika kondisinya gagal, ia bergerak lurus ke arah anak berikutnya. Jika mereka lulus, itu memeriksa apakah sudah ada anak yang mengeksekusi. Jika demikian, ia memanggil Interruptdan kemudian gagal. Itu semua dapat dilakukan pada titik ini, dengan harapan bahwa simpul yang sedang berjalan akan menanggapi permintaan interupsi, yang dapat dilakukan dengan ...
• Saya telah menambahkan sebuah Interruptiblesimpul, yang merupakan semacam dekorator khusus karena memiliki aliran logika yang teratur sebagai anak hiasnya, dan kemudian simpul yang terpisah untuk gangguan. Itu mengeksekusi anak regulernya untuk penyelesaian atau kegagalan selama itu tidak terganggu. Jika terputus, ia segera beralih ke mengeksekusi simpulnya penanganan simpul anak, yang bisa menjadi kompleks sebuah sub-pohon seperti yang diperlukan

Hasil akhirnya adalah sesuatu seperti ini, diambil dari spike saya:

Di atas adalah pohon perilaku untuk seekor lebah, yang mengumpulkan nektar dan mengembalikannya ke sarangnya. Ketika tidak memiliki nektar dan tidak di dekat bunga yang memiliki beberapa nektar, ia mengembara:

Jika simpul ini tidak terputus maka tidak akan pernah gagal, sehingga lebah akan berkeliaran selamanya. Namun, karena simpul orangtua adalah pemilih dan memiliki anak-anak dengan prioritas lebih tinggi, kelayakan mereka untuk eksekusi terus-menerus diperiksa. Jika kondisinya lewat, pemilih menimbulkan gangguan dan sub-pohon di atas segera beralih ke jalur "Terganggu", yang hanya menjamin ASAP dengan gagal. Itu bisa, tentu saja, melakukan beberapa tindakan lain terlebih dahulu, tetapi lonjakan saya tidak benar-benar ada hubungannya selain jaminan.

Namun, untuk mengikat ini kembali ke pertanyaan saya, Anda dapat membayangkan bahwa jalur "Terganggu" dapat mencoba untuk membalikkan animasi duduk dan, jika gagal, serdadu itu tersandung. Semua ini akan menahan transisi ke status prioritas yang lebih tinggi, dan itulah tujuan sebenarnya.

Saya pikir saya senang dengan pendekatan ini - terutama bagian inti yang saya uraikan di atas - tetapi sejujurnya, ini menimbulkan pertanyaan lebih lanjut tentang penyebaran implementasi kondisi dan tindakan tertentu, dan mengikat pohon perilaku ke dalam sistem animasi. Saya bahkan tidak yakin saya dapat mengartikulasikan pertanyaan-pertanyaan ini, jadi saya akan terus berpikir / spiking.

Saya memperbaiki masalah yang sama dengan menciptakan dekorator "Kapan". Ini memiliki kondisi dan dua perilaku anak ("lalu" dan "sebaliknya"). Ketika "Ketika" dijalankan, ia memeriksa kondisi dan tergantung pada hasilnya, dijalankan kemudian / bukan anak-anak. Jika hasil kondisi berubah, running child diatur ulang dan child yang berhubungan dengan cabang lain dimulai. Jika anak menyelesaikan eksekusi, seluruh "Kapan" menyelesaikan eksekusi.

Poin kuncinya adalah bahwa tidak seperti BT awal dalam pertanyaan ini di mana kondisi diperiksa hanya pada urutan awal, "Kapan" saya terus memeriksa kondisi saat sedang berjalan. Jadi, bagian atas pohon perilaku diganti dengan:

When[EnemyNear]
  Then
    AttackSequence
  Otherwise
    When[StandingOnGrass]
      Then
        IdleSequence
      Otherwise
        Hum a tune

Untuk penggunaan "Ketika" yang lebih lanjut, orang juga ingin memperkenalkan tindakan "Tunggu" yang tidak melakukan apa-apa untuk waktu yang ditentukan atau tanpa batas waktu (sampai diatur ulang oleh perilaku orang tua). Juga, jika Anda hanya membutuhkan satu cabang "Kapan", cabang lain dapat berisi tindakan "Sukses" atau "Gagal", yang dengan hormat akan berhasil dan gagal segera.

Walaupun saya terlambat, tapi saya harap ini bisa membantu. Terutama karena saya ingin memastikan bahwa saya sendiri tidak melewatkan sesuatu karena saya sudah mencoba untuk mencari tahu hal ini juga. Sebagian besar saya meminjam ide ini dari Unreal, tetapi tanpa membuatnya menjadi Decorator, properti di pangkalan Nodeatau sangat terikat dengan Blackboard, itu lebih umum.

Ini akan memperkenalkan tipe simpul baru Guardyang disebut yang merupakan kombinasi dari a Decorator, dan Compositedan memiliki condition() -> Resulttanda tangan di samping sebuahupdate() -> Result

Ini memiliki tiga mode untuk menunjukkan bagaimana pembatalan harus terjadi ketika Guardkembali Successatau Failed, pembatalan yang sebenarnya tergantung pada pemanggil. Jadi untuk Selectorpanggilan Guard:

1. Batalkan .self -> Hanya batalkan Guard(dan anak yang berjalan) jika berjalan dan kondisinya sudahFailed
2. Batalkan .lower-> Hanya batalkan node prioritas bawah jika sedang berjalan dan kondisinya sedang SuccessatauRunning
3. Batalkan .both -> Keduanya .selfdan .lowertergantung pada kondisi dan node yang berjalan. Anda ingin membatalkan sendiri jika sedang berjalan dan akan mengkondisikan untuk falseatau membatalkan node yang berjalan jika mereka dianggap prioritas rendah berdasarkan Compositeaturan ( Selectordalam kasus kami) jika kondisinya Success. Dengan kata lain, pada dasarnya kedua konsep tersebut digabungkan.

Suka Decoratordan tidak seperti Compositeitu hanya membutuhkan satu anak.

Meskipun Guardhanya mengambil satu anak, Anda dapat membuat sarang sebanyak mungkin Sequences, Selectorsatau jenis lain yang NodesAnda inginkan, termasuk yang lain Guardsatau Decorators.

Selector1 Guard.both[Sequence[EnemyNear?]] Sequence1 MoveToEnemy Attack Selector2 Sequence2 StandingOnGrass? Idle HumATune

Dalam skenario di atas, setiap kali Selector1diperbarui, ia akan selalu menjalankan pemeriksaan kondisi pada penjaga yang terkait dengan anak-anaknya. Dalam kasus di atas, Sequence1Dijaga dan perlu diperiksa sebelum Selector1melanjutkan runningtugas.

Setiap kali Selector2atau Sequence1sedang berjalan segera setelah EnemyNear?kembali successselama Guards condition()pemeriksaan maka Selector1akan mengeluarkan interupsi / batal running nodedan kemudian melanjutkan seperti biasa.

Dengan kata lain, kita dapat bereaksi terhadap cabang "idle" atau "menyerang" berdasarkan beberapa kondisi yang membuat perilaku jauh lebih reaktif daripada jika kita menetap di Parallel

Ini juga memungkinkan Anda untuk menjaga single Nodeyang memiliki prioritas lebih tinggi agar tidak berjalan Nodesdi samaComposite

Selector1 Guard.both[Sequence[EnemyNear?]] Sequence1 MoveToEnemy Attack Selector2 Guard.both[StandingOnGrass?] Idle HumATune

Jika HumATuneberjalan lama Node, Selector2akan selalu memeriksa yang pertama jika bukan karena Guard. Jadi jika npc diteleportasi ke tambalan rumput, waktu berikutnya Selector2berjalan, itu akan memeriksa Guarddan membatalkan HumATuneuntuk menjalankanIdle

Jika ia diteleportasi keluar dari patch rumput, itu akan membatalkan node yang sedang berjalan ( Idle) dan pindah keHumATune

Seperti yang Anda lihat di sini, pengambilan keputusan bergantung pada penelepon Guarddan bukan penelepon Guarditu sendiri. Aturan siapa yang dianggap lower prioritytetap dengan penelepon. Dalam kedua contoh, itu Selectoryang mendefinisikan apa yang merupakan lower priority.

Jika Anda telah seorang Compositeyang disebut Random Selector, maka Anda akan mendapatkan untuk menentukan aturan dalam pelaksanaan tertentu yang Composite.