Saya terjumpa beberapa bahan menarik tentang kecerdasan buatan dalam permainan. Dengan penjelasan tentang perkara asas tentang AI menggunakan contoh mudah, dan di dalamnya terdapat banyak alat dan kaedah yang berguna untuk pembangunan dan reka bentuknya yang mudah. Bagaimana, di mana dan bila untuk menggunakannya juga ada.
Kebanyakan contoh ditulis dalam pseudokod, jadi tiada pengetahuan pengaturcaraan lanjutan diperlukan. Di bawah potongan terdapat 35 helaian teks dengan gambar dan gif, jadi bersedialah.
UPD. Saya memohon maaf, tetapi saya telah membuat terjemahan saya sendiri untuk artikel ini tentang Habré . Anda boleh membaca versi beliau , tetapi atas sebab tertentu artikel itu melepasi saya (saya menggunakan carian, tetapi ada masalah). Dan kerana saya menulis di blog yang didedikasikan untuk pembangunan permainan, saya memutuskan untuk meninggalkan versi terjemahan saya untuk pelanggan (beberapa mata diformat secara berbeza, ada yang sengaja ditinggalkan atas nasihat pembangun).
Apakah AI?
AI Permainan memfokuskan pada tindakan yang harus dilakukan oleh objek berdasarkan keadaan di mana objek itu berada. Ini biasanya dirujuk sebagai pengurusan "ejen pintar", di mana ejen ialah watak pemain, kenderaan, bot, atau kadangkala sesuatu yang lebih abstrak: keseluruhan kumpulan entiti atau malah tamadun. Dalam setiap kes, ia adalah perkara yang mesti melihat persekitarannya, membuat keputusan berdasarkannya, dan bertindak mengikut mereka. Ini dipanggil kitaran Sense/Think/Act:
- Rasa: Ejen mencari atau menerima maklumat tentang perkara dalam persekitarannya yang boleh mempengaruhi tingkah lakunya (ancaman berdekatan, item untuk dikumpulkan, tempat menarik untuk diterokai).
- Fikirkan: Ejen memutuskan cara untuk bertindak balas (mempertimbangkan sama ada ia cukup selamat untuk mengumpul barang atau sama ada dia harus melawan/bersembunyi dahulu).
- Act: ejen melakukan tindakan untuk melaksanakan keputusan sebelumnya (mula bergerak ke arah musuh atau objek).
- ...kini keadaan telah berubah disebabkan oleh tindakan watak, jadi kitaran berulang dengan data baharu.
AI cenderung memfokus pada bahagian Sense gelung. Contohnya, kereta autonomi mengambil gambar jalan raya, menggabungkannya dengan data radar dan lidar, dan mentafsirnya. Ini biasanya dilakukan oleh pembelajaran mesin, yang memproses data masuk dan memberi makna, mengekstrak maklumat semantik seperti "ada kereta lain 20 ela di hadapan anda." Ini adalah apa yang dipanggil masalah klasifikasi.
Permainan tidak memerlukan sistem yang kompleks untuk mengekstrak maklumat, kerana kebanyakan data sudah menjadi sebahagian daripadanya. Tidak perlu menjalankan algoritma pengecaman imej untuk menentukan sama ada terdapat musuh di hadapan—permainan sudah mengetahui dan menyalurkan maklumat terus ke dalam proses membuat keputusan. Oleh itu, bahagian Sense kitaran selalunya lebih mudah daripada bahagian Think and Act.
Had Permainan AI
AI mempunyai beberapa batasan yang mesti dipatuhi:
- AI tidak perlu dilatih terlebih dahulu, seolah-olah ia adalah algoritma pembelajaran mesin. Tidak masuk akal untuk menulis rangkaian saraf semasa pembangunan untuk memantau puluhan ribu pemain dan mempelajari cara terbaik untuk bermain menentang mereka. kenapa? Kerana permainan belum dikeluarkan dan tiada pemain.
- Permainan ini harus menyeronokkan dan mencabar, jadi ejen tidak sepatutnya mencari pendekatan terbaik terhadap orang.
- Ejen perlu kelihatan realistik supaya pemain berasa seperti mereka bermain menentang orang sebenar. Program AlphaGo mengatasi prestasi manusia, tetapi langkah yang dipilih adalah sangat jauh daripada pemahaman tradisional permainan. Jika permainan meniru lawan manusia, perasaan ini tidak sepatutnya wujud. Algoritma perlu diubah supaya ia membuat keputusan yang munasabah dan bukannya yang ideal.
- AI mesti berfungsi dalam masa nyata. Ini bermakna bahawa algoritma tidak boleh memonopoli penggunaan CPU untuk jangka masa yang lama untuk membuat keputusan. Walaupun 10 milisaat adalah terlalu panjang, kerana kebanyakan permainan hanya memerlukan 16 hingga 33 milisaat untuk melakukan semua pemprosesan dan beralih ke bingkai grafik seterusnya.
- Sebaik-baiknya, sekurang-kurangnya sebahagian daripada sistem harus dipacu data, supaya bukan pengekod boleh membuat perubahan dan pelarasan boleh berlaku dengan lebih cepat.
Mari kita lihat pendekatan AI yang merangkumi keseluruhan kitaran Sense/Think/Act.
Membuat Keputusan Asas
Mari kita mulakan dengan permainan yang paling mudah - Pong. Matlamat: gerakkan dayung supaya bola melantun daripadanya daripada terbang melepasinya. Ia seperti tenis, di mana anda kalah jika anda tidak memukul bola. Di sini AI mempunyai tugas yang agak mudah - memutuskan ke arah mana untuk mengalihkan platform.
Kenyataan bersyarat
Untuk AI dalam Pong, penyelesaian yang paling jelas ialah sentiasa cuba meletakkan platform di bawah bola.
Algoritma mudah untuk ini, ditulis dalam pseudokod:
setiap bingkai/kemas kini semasa permainan berjalan:
jika bola berada di sebelah kiri dayung:
gerakkan dayung ke kiri
lain jika bola berada di sebelah kanan dayung:
gerakkan dayung ke kanan
Jika platform bergerak pada kelajuan bola, maka ini adalah algoritma yang ideal untuk AI dalam Pong. Tidak perlu merumitkan apa-apa jika tiada banyak data dan kemungkinan tindakan untuk ejen.
Pendekatan ini sangat mudah sehingga keseluruhan kitaran Sense/Think/Act hampir tidak dapat dilihat. Tetapi ia ada di sana:
- Bahagian Sense adalah dalam dua pernyataan jika. Permainan ini tahu di mana bola itu dan di mana platform itu, jadi AI mencarinya untuk mendapatkan maklumat itu.
- Bahagian Fikirkan juga termasuk dalam dua penyataan jika. Mereka merangkumi dua penyelesaian, yang dalam kes ini adalah saling eksklusif. Akibatnya, satu daripada tiga tindakan dipilih - gerakkan platform ke kiri, gerakkannya ke kanan atau jangan lakukan apa-apa jika ia telah diletakkan dengan betul.
- Bahagian Act terdapat dalam pernyataan Move Paddle Left dan Move Paddle Right. Bergantung pada reka bentuk permainan, mereka boleh menggerakkan platform serta-merta atau pada kelajuan tertentu.
Pendekatan sedemikian dipanggil reaktif - terdapat satu set peraturan mudah (dalam kes ini jika pernyataan dalam kod) yang bertindak balas kepada keadaan semasa dunia dan mengambil tindakan.
Pokok keputusan
Contoh Pong sebenarnya bersamaan dengan konsep AI formal yang dipanggil pokok keputusan. Algoritma melaluinya untuk mencapai "daun"—keputusan tentang tindakan yang perlu diambil.
Mari kita buat gambarajah blok pepohon keputusan untuk algoritma platform kami:
Setiap bahagian pokok dipanggil nod - AI menggunakan teori graf untuk menerangkan struktur tersebut. Terdapat dua jenis nod:
- Nod keputusan: memilih antara dua alternatif berdasarkan ujian beberapa keadaan, di mana setiap alternatif diwakili sebagai nod yang berasingan.
- Nod tamat: Tindakan untuk dilakukan yang mewakili keputusan muktamad.
Algoritma bermula dari nod pertama ("akar" pokok). Ia sama ada membuat keputusan tentang nod anak yang hendak dituju, atau ia melaksanakan tindakan yang disimpan dalam nod dan keluar.
Apakah faedah mempunyai pepohon keputusan melakukan kerja yang sama seperti pernyataan if dalam bahagian sebelumnya? Terdapat sistem umum di sini di mana setiap keputusan hanya mempunyai satu syarat dan dua kemungkinan hasil. Ini membolehkan pembangun mencipta AI daripada data yang mewakili keputusan dalam pokok tanpa perlu mengekodkannya dengan keras. Mari kita bentangkannya dalam bentuk jadual:
Di sebelah kod anda akan mendapat sistem untuk membaca rentetan. Buat nod untuk setiap daripada mereka, sambungkan logik keputusan berdasarkan lajur kedua dan nod anak berdasarkan lajur ketiga dan keempat. Anda masih perlu memprogramkan syarat dan tindakan, tetapi kini struktur permainan akan menjadi lebih kompleks. Di sini anda menambah keputusan dan tindakan tambahan, dan kemudian menyesuaikan keseluruhan AI dengan hanya mengedit fail teks definisi pokok. Seterusnya, anda memindahkan fail kepada pereka permainan, yang boleh mengubah tingkah laku tanpa menyusun semula permainan atau menukar kod.
Pepohon keputusan sangat berguna apabila ia dibina secara automatik daripada set contoh yang besar (contohnya, menggunakan algoritma ID3). Ini menjadikan mereka alat yang berkesan dan berprestasi tinggi untuk mengklasifikasikan situasi berdasarkan data yang diperoleh. Walau bagaimanapun, kami melampaui sistem mudah untuk ejen memilih tindakan.
Senario
Kami menganalisis sistem pepohon keputusan yang menggunakan syarat dan tindakan yang telah dibuat sebelumnya. Orang yang mereka bentuk AI boleh menyusun pokok itu mengikut kehendaknya, tetapi dia masih perlu bergantung pada pengekod yang memprogram semuanya. Bagaimana jika kita boleh memberi pereka alat untuk mencipta keadaan atau tindakan mereka sendiri?
Supaya pengaturcara tidak perlu menulis kod untuk syarat Is Ball Left Of Paddle dan Is Ball Right Of Paddle, dia boleh mencipta sistem di mana pereka bentuk akan menulis syarat untuk menyemak nilai ini. Kemudian data pokok keputusan akan kelihatan seperti ini:
Ini pada asasnya sama seperti dalam jadual pertama, tetapi penyelesaian dalam diri mereka sendiri mempunyai kod mereka sendiri, sedikit seperti bahagian bersyarat bagi pernyataan if. Di sebelah kod, ini akan dibaca dalam lajur kedua untuk nod keputusan, tetapi bukannya mencari syarat khusus untuk dilaksanakan (Adakah Bola Ditinggalkan Dari Paddle), ia menilai ungkapan bersyarat dan mengembalikan benar atau salah dengan sewajarnya. Ini dilakukan menggunakan bahasa skrip Lua atau Angelscript. Menggunakannya, pembangun boleh mengambil objek dalam permainannya (bola dan dayung) dan mencipta pembolehubah yang akan tersedia dalam skrip (ball.position). Juga, bahasa skrip adalah lebih mudah daripada C++. Ia tidak memerlukan peringkat kompilasi penuh, jadi ia sesuai untuk melaraskan logik permainan dengan cepat dan membolehkan "bukan pengekod" mencipta sendiri fungsi yang diperlukan.
Dalam contoh di atas, bahasa skrip digunakan hanya untuk menilai ungkapan bersyarat, tetapi ia juga boleh digunakan untuk tindakan. Contohnya, data Move Paddle Right boleh menjadi pernyataan skrip (ball.position.x += 10). Supaya tindakan itu juga ditakrifkan dalam skrip, tanpa perlu memprogram Move Paddle Right.
Anda boleh pergi lebih jauh dan menulis keseluruhan pepohon keputusan dalam bahasa skrip. Ini akan menjadi kod dalam bentuk kenyataan bersyarat berkod keras, tetapi ia akan ditempatkan dalam fail skrip luaran, iaitu, ia boleh diubah tanpa menyusun semula keseluruhan program. Anda selalunya boleh mengedit fail skrip semasa permainan untuk menguji respons AI yang berbeza dengan cepat.
Sambutan Acara
Contoh di atas sesuai untuk Pong. Mereka terus menjalankan kitaran Sense/Think/Act dan bertindak berdasarkan keadaan terkini dunia. Tetapi dalam permainan yang lebih kompleks anda perlu bertindak balas terhadap peristiwa individu, dan tidak menilai semuanya sekaligus. Pong dalam kes ini sudah menjadi contoh yang tidak baik. Jom pilih yang lain.
Bayangkan penembak di mana musuh tidak bergerak sehingga mereka mengesan pemain, selepas itu mereka bertindak bergantung pada "pengkhususan" mereka: seseorang akan berlari untuk "tergesa-gesa", seseorang akan menyerang dari jauh. Ia masih merupakan sistem reaktif asas - "jika pemain dikesan, lakukan sesuatu" - tetapi secara logiknya ia boleh dipecahkan kepada acara Dilihat Pemain dan Reaksi (pilih respons dan laksanakannya).
Ini membawa kita kembali kepada kitaran Sense/Think/Act. Kami boleh mengekod bahagian Sense yang akan memeriksa setiap bingkai sama ada AI melihat pemain. Jika tidak, tiada apa yang berlaku, tetapi jika ia melihat, maka acara Player Seen dicipta. Kod tersebut akan mempunyai bahagian berasingan yang mengatakan "apabila acara Player Seen berlaku, lakukan" di mana respons yang anda perlukan untuk menangani bahagian Think and Act. Oleh itu, anda akan menyediakan reaksi kepada acara Player Seen: untuk watak "tergesa-gesa" - ChargeAndAttack, dan untuk penembak tepat - HideAndSnipe. Perhubungan ini boleh dibuat dalam fail data untuk pengeditan pantas tanpa perlu menyusun semula. Bahasa skrip boleh digunakan di sini juga.
Membuat keputusan yang sukar
Walaupun sistem tindak balas mudah sangat berkuasa, terdapat banyak situasi di mana mereka tidak mencukupi. Kadangkala anda perlu membuat keputusan yang berbeza berdasarkan perkara yang sedang dilakukan oleh ejen, tetapi sukar untuk membayangkan ini sebagai syarat. Kadangkala terdapat terlalu banyak syarat untuk mewakilinya dengan berkesan dalam pepohon keputusan atau skrip. Kadangkala anda perlu menilai terlebih dahulu bagaimana keadaan akan berubah sebelum membuat keputusan mengenai langkah seterusnya. Pendekatan yang lebih canggih diperlukan untuk menyelesaikan masalah ini.
Mesin keadaan terhingga
Mesin keadaan terhingga atau FSM (mesin keadaan terhingga) ialah satu cara untuk menyatakan bahawa ejen kami kini berada dalam salah satu daripada beberapa keadaan yang mungkin, dan ia boleh beralih dari satu keadaan ke keadaan yang lain. Terdapat sebilangan negeri sedemikian—maka namanya. Contoh terbaik dari kehidupan ialah lampu isyarat. Terdapat urutan lampu yang berbeza di tempat yang berbeza, tetapi prinsipnya adalah sama - setiap keadaan mewakili sesuatu (berhenti, berjalan, dll.). Lampu isyarat berada dalam satu keadaan sahaja pada bila-bila masa, dan bergerak dari satu ke satu lagi berdasarkan peraturan mudah.
Ia adalah cerita yang sama dengan NPC dalam permainan. Sebagai contoh, mari kita ambil pengawal dengan keadaan berikut:
- meronda.
- Menyerang.
- melarikan diri.
Dan syarat-syarat ini untuk menukar keadaannya:
- Jika pengawal melihat musuh, dia menyerang.
- Jika pengawal menyerang tetapi tidak lagi melihat musuh, dia kembali untuk meronda.
- Jika pengawal menyerang tetapi cedera parah, dia melarikan diri.
Anda juga boleh menulis pernyataan jika dengan pembolehubah keadaan penjaga dan pelbagai semakan: adakah terdapat musuh berdekatan, apakah tahap kesihatan NPC, dsb. Mari tambah beberapa keadaan lagi:
- Kemalasan - antara rondaan.
- Mencari - apabila musuh yang kelihatan telah hilang.
- Mencari Bantuan - apabila musuh dikesan, tetapi terlalu kuat untuk melawan seorang diri.
Pilihan untuk setiap daripada mereka adalah terhad - sebagai contoh, pengawal tidak akan pergi mencari musuh tersembunyi jika dia mempunyai kesihatan yang rendah.
Lagipun, terdapat senarai besar "jika" , Itu " boleh menjadi terlalu rumit, jadi kita perlu memformalkan kaedah yang membolehkan kita mengingati keadaan dan peralihan antara negeri. Untuk melakukan ini, kami mengambil kira semua negeri, dan di bawah setiap negeri kami menulis dalam senarai semua peralihan ke negeri lain, bersama dengan syarat yang diperlukan untuk mereka.
Ini ialah jadual peralihan keadaan - cara komprehensif untuk mewakili FSM. Mari lukis gambar rajah dan dapatkan gambaran keseluruhan lengkap tentang cara tingkah laku NPC berubah.
Rajah menggambarkan intipati pembuatan keputusan untuk ejen ini berdasarkan situasi semasa. Selain itu, setiap anak panah menunjukkan peralihan antara keadaan jika keadaan di sebelahnya adalah benar.
Setiap kemas kini kami menyemak keadaan semasa ejen, melihat senarai peralihan, dan jika syarat peralihan dipenuhi, ia menerima keadaan baharu. Sebagai contoh, setiap bingkai menyemak sama ada pemasa 10 saat telah tamat tempoh, dan jika ya, maka pengawal itu pergi dari keadaan Melahu kepada Rondaan. Dengan cara yang sama, keadaan Attacking memeriksa kesihatan ejen - jika ia rendah, maka ia akan masuk ke dalam keadaan Melarikan diri.
Ini mengendalikan peralihan antara negeri, tetapi bagaimana pula dengan tingkah laku yang dikaitkan dengan negeri itu sendiri? Dari segi melaksanakan gelagat sebenar untuk keadaan tertentu, biasanya terdapat dua jenis "cangkuk" di mana kami menetapkan tindakan kepada FSM:
- Tindakan yang kami lakukan secara berkala untuk keadaan semasa.
- Tindakan yang kami ambil apabila beralih dari satu keadaan ke keadaan lain.
Contoh untuk jenis pertama. Negeri Rondaan akan menggerakkan ejen di sepanjang laluan rondaan setiap bingkai. Keadaan Menyerang akan cuba memulakan serangan setiap bingkai atau peralihan kepada keadaan di mana ini mungkin.
Untuk jenis kedua, pertimbangkan peralihan "jika musuh kelihatan dan musuh terlalu kuat, kemudian pergi ke keadaan Mencari Bantuan. Ejen mesti memilih tempat untuk mendapatkan bantuan dan menyimpan maklumat ini supaya keadaan Mencari Bantuan tahu ke mana hendak pergi. Setelah bantuan ditemui, ejen kembali ke keadaan Menyerang. Pada ketika ini, dia ingin memberitahu sekutu tentang ancaman itu, jadi tindakan NotifyFriendOfThreat mungkin berlaku.
Sekali lagi, kita boleh melihat sistem ini melalui lensa kitaran Sense/Think/Act. Sense terkandung dalam data yang digunakan oleh logik peralihan. Fikir - peralihan tersedia di setiap negeri. Dan Akta dijalankan dengan tindakan yang dilakukan secara berkala dalam keadaan atau pada peralihan antara negeri.
Kadangkala keadaan peralihan pengundian secara berterusan boleh memakan kos yang tinggi. Sebagai contoh, jika setiap ejen melakukan pengiraan kompleks setiap bingkai untuk menentukan sama ada ia boleh melihat musuh dan memahami sama ada ia boleh beralih daripada keadaan Rondaan kepada Menyerang, ini akan mengambil banyak masa CPU.
Perubahan penting dalam keadaan dunia boleh dianggap sebagai peristiwa yang akan diproses apabila ia berlaku. Daripada FSM menyemak keadaan peralihan "bolehkah ejen saya melihat pemain?" setiap bingkai, sistem yang berasingan boleh dikonfigurasikan untuk menyemak kurang kerap (cth. 5 kali sesaat). Dan hasilnya ialah mengeluarkan Player Seen apabila cek itu berlalu.
Ini diserahkan kepada FSM, yang kini sepatutnya pergi ke acara Player Seen yang diterima dan bertindak balas dengan sewajarnya. Tingkah laku yang terhasil adalah sama kecuali kelewatan yang hampir tidak dapat dilihat sebelum bertindak balas. Tetapi prestasi telah bertambah baik hasil daripada mengasingkan bahagian Sense ke bahagian berasingan program.
Mesin keadaan terhingga hierarki
Walau bagaimanapun, bekerja dengan FSM besar tidak selalunya mudah. Jika kita ingin mengembangkan keadaan serangan untuk memisahkan MeleeAttacking dan RangedAttacking, kita perlu menukar peralihan daripada semua negeri lain yang membawa kepada keadaan Attacking (semasa dan akan datang).
Anda mungkin perasan bahawa dalam contoh kami terdapat banyak peralihan pendua. Kebanyakan peralihan dalam keadaan Idling adalah sama dengan peralihan dalam negeri Patrol. Adalah lebih baik untuk tidak mengulangi diri kita sendiri, terutamanya jika kita menambah lebih banyak keadaan yang serupa. Adalah wajar untuk mengelompokkan Idling dan Patrolling di bawah label umum "bukan pertempuran", di mana terdapat hanya satu set peralihan biasa untuk memerangi negeri. Jika kita menganggap label ini sebagai negeri, maka Idling dan Patrolling menjadi substate. Contoh menggunakan jadual peralihan yang berasingan untuk substate bukan pertempuran baharu:
Negeri utama:
Status keluar dari pertempuran:
Dan dalam bentuk rajah:
Ia adalah sistem yang sama, tetapi dengan keadaan bukan pertempuran baharu yang termasuk Melahu dan Rondaan. Dengan setiap negeri yang mengandungi FSM dengan substate (dan substate ini, seterusnya, mengandungi FSM mereka sendiri - dan seterusnya selama yang anda perlukan), kami mendapat Hierarchical Finite State Machine atau HFSM (mesin keadaan terhingga hierarki). Dengan mengelompokkan keadaan bukan pertempuran, kami memotong sekumpulan peralihan yang berlebihan. Kita boleh melakukan perkara yang sama untuk mana-mana negeri baharu dengan peralihan biasa. Sebagai contoh, jika pada masa hadapan kita mengembangkan keadaan Attacking kepada keadaan MeleeAttacking dan MissileAttacking, mereka akan menjadi substate yang beralih antara satu sama lain berdasarkan jarak kepada musuh dan ketersediaan peluru. Akibatnya, gelagat dan gelagat kecil yang kompleks boleh diwakili dengan minimum peralihan pendua.
Pokok tingkah laku
Dengan HFSM, gabungan tingkah laku yang kompleks dicipta dengan cara yang mudah. Walau bagaimanapun, terdapat sedikit kesukaran bahawa membuat keputusan dalam bentuk peraturan peralihan berkait rapat dengan keadaan semasa. Dan dalam banyak permainan ini adalah apa yang diperlukan. Dan penggunaan hierarki keadaan yang teliti boleh mengurangkan bilangan ulangan peralihan. Tetapi kadangkala anda memerlukan peraturan yang berkesan tidak kira di mana anda berada, atau yang terpakai di hampir mana-mana negeri. Sebagai contoh, jika kesihatan ejen menurun kepada 25%, anda akan mahu dia melarikan diri tanpa mengira sama ada dia dalam pertempuran, terbiar atau bercakap - anda perlu menambahkan syarat ini pada setiap negeri. Dan jika pereka anda kemudiannya ingin menukar ambang kesihatan rendah daripada 25% kepada 10%, maka ini perlu dilakukan sekali lagi.
Sebaik-baiknya, situasi ini memerlukan sistem di mana keputusan tentang "keadaan apa yang akan diduduki" berada di luar negeri itu sendiri, untuk membuat perubahan hanya di satu tempat dan tidak menyentuh keadaan peralihan. Pokok tingkah laku muncul di sini.
Terdapat beberapa cara untuk melaksanakannya, tetapi intipatinya adalah lebih kurang sama untuk semua dan serupa dengan pepohon keputusan: algoritma bermula dengan nod "akar", dan pepohon itu mengandungi nod yang mewakili sama ada keputusan atau tindakan. Terdapat beberapa perbezaan utama walaupun:
- Nod kini mengembalikan satu daripada tiga nilai: Berjaya (jika kerja selesai), Gagal (jika ia tidak dapat dimulakan) atau Berjalan (jika ia masih berjalan dan tiada hasil akhir).
- Tiada lagi nod keputusan untuk dipilih antara dua alternatif. Sebaliknya, ia adalah nod Penghias, yang mempunyai satu nod anak. Jika mereka Berjaya, mereka melaksanakan satu-satunya nod anak mereka.
- Nod yang melakukan tindakan mengembalikan nilai Berjalan untuk mewakili tindakan yang dilakukan.
Set kecil nod ini boleh digabungkan untuk mencipta sejumlah besar gelagat kompleks. Mari bayangkan pengawal HFSM dari contoh sebelumnya sebagai pokok tingkah laku:
Dengan struktur ini tidak sepatutnya terdapat peralihan yang jelas daripada keadaan Melahu/Ronda kepada Menyerang atau mana-mana negeri lain. Jika musuh kelihatan dan kesihatan watak itu rendah, pelaksanaan akan berhenti di nod Melarikan diri, tanpa mengira nod mana yang telah ia laksanakan sebelum ini - Rondaan, Idling, Menyerang atau mana-mana yang lain.
Pokok gelagat adalah kompleks—terdapat banyak cara untuk mengarangnya dan mencari gabungan penghias dan nod kompaun yang betul boleh mencabar. Terdapat juga soalan tentang kekerapan memeriksa pokok - adakah kita mahu melalui setiap bahagiannya atau hanya apabila salah satu syarat telah berubah? Bagaimanakah kita menyimpan keadaan yang berkaitan dengan nod - bagaimanakah kita tahu apabila kita telah Melahu selama 10 saat, atau bagaimana kita tahu nod mana yang dilaksanakan kali terakhir supaya kita boleh memproses jujukan dengan betul?
Inilah sebabnya mengapa terdapat banyak pelaksanaan. Contohnya, sesetengah sistem telah menggantikan nod penghias dengan penghias sebaris. Mereka menilai semula pokok apabila keadaan penghias berubah, membantu menyertai nod dan menyediakan kemas kini berkala.
Sistem berasaskan utiliti
Sesetengah permainan mempunyai banyak mekanik yang berbeza. Adalah wajar bahawa mereka menerima semua faedah peraturan peralihan yang mudah dan umum, tetapi tidak semestinya dalam bentuk pokok tingkah laku yang lengkap. Daripada mempunyai satu set pilihan yang jelas atau pokok tindakan yang mungkin, lebih mudah untuk memeriksa semua tindakan dan memilih yang paling sesuai pada masa ini.
Sistem berasaskan Utiliti akan membantu dengan ini sahaja. Ini adalah sistem di mana ejen mempunyai pelbagai tindakan dan memilih tindakan yang mana untuk dilakukan berdasarkan utiliti relatif setiap satu. Di mana utiliti ialah ukuran sewenang-wenangnya tentang betapa pentingnya atau wajar bagi ejen untuk melaksanakan tindakan ini.
Utiliti tindakan yang dikira berdasarkan keadaan dan persekitaran semasa, ejen boleh menyemak dan memilih keadaan lain yang paling sesuai pada bila-bila masa. Ini serupa dengan FSM, kecuali apabila peralihan ditentukan oleh anggaran untuk setiap keadaan berpotensi, termasuk keadaan semasa. Sila ambil perhatian bahawa kami memilih tindakan yang paling berguna untuk meneruskan (atau kekal jika kami telah menyelesaikannya). Untuk lebih banyak variasi, ini boleh menjadi pilihan yang seimbang tetapi rawak daripada senarai kecil.
Sistem memberikan julat nilai utiliti sewenang-wenangnya—contohnya, daripada 0 (tidak diingini sepenuhnya) hingga 100 (diingini sepenuhnya). Setiap tindakan mempunyai beberapa parameter yang mempengaruhi pengiraan nilai ini. Kembali kepada contoh penjaga kami:
Peralihan antara tindakan adalah samar-samar—mana-mana negeri boleh mengikuti mana-mana yang lain. Keutamaan tindakan ditemui dalam nilai utiliti yang dikembalikan. Jika musuh kelihatan, dan musuh itu kuat, dan kesihatan watak itu rendah, kedua-dua Fleeing dan FindingHelp akan mengembalikan nilai bukan sifar yang tinggi. Dalam kes ini, FindingHelp akan sentiasa lebih tinggi. Begitu juga, aktiviti bukan pertempuran tidak pernah kembali lebih daripada 50, jadi ia akan sentiasa lebih rendah daripada aktiviti pertempuran. Anda perlu mengambil kira perkara ini apabila membuat tindakan dan mengira utilitinya.
Dalam contoh kami, tindakan mengembalikan sama ada nilai tetap tetap atau salah satu daripada dua nilai tetap. Sistem yang lebih realistik akan mengembalikan anggaran daripada julat nilai yang berterusan. Sebagai contoh, tindakan Melarikan diri mengembalikan nilai utiliti yang lebih tinggi jika kesihatan ejen rendah, dan tindakan Menyerang mengembalikan nilai utiliti yang lebih rendah jika musuh terlalu kuat. Oleh kerana itu, tindakan Melarikan diri lebih diutamakan daripada Menyerang dalam apa jua keadaan di mana ejen merasakan bahawa dia tidak mempunyai kesihatan yang mencukupi untuk mengalahkan musuh. Ini membolehkan tindakan diutamakan berdasarkan sebarang bilangan kriteria, menjadikan pendekatan ini lebih fleksibel dan berubah-ubah daripada pokok tingkah laku atau FSM.
Setiap tindakan mempunyai banyak syarat untuk pengiraan program. Mereka boleh ditulis dalam bahasa skrip atau sebagai satu siri formula matematik. The Sims, yang mensimulasikan rutin harian watak, menambah lapisan pengiraan tambahan - ejen menerima satu siri "motivasi" yang mempengaruhi penilaian utiliti. Jika watak lapar, mereka akan menjadi lebih lapar dari semasa ke semasa, dan nilai utiliti tindakan EatFood akan meningkat sehingga watak itu melaksanakannya, mengurangkan tahap kelaparan dan mengembalikan nilai EatFood kepada sifar.
Idea untuk memilih tindakan berdasarkan sistem penarafan adalah agak mudah, jadi sistem berasaskan Utiliti boleh digunakan sebagai sebahagian daripada proses membuat keputusan AI, dan bukannya sebagai pengganti lengkap untuknya. Pohon keputusan mungkin meminta penarafan utiliti dua nod anak dan pilih yang lebih tinggi. Begitu juga, pepohon tingkah laku boleh mempunyai nod Utiliti komposit untuk menilai utiliti tindakan untuk memutuskan kanak-kanak yang hendak dilaksanakan.
Pergerakan dan navigasi
Dalam contoh sebelumnya, kami mempunyai platform yang kami gerakkan ke kiri atau kanan, dan pengawal yang meronda atau menyerang. Tetapi bagaimana sebenarnya kita mengendalikan pergerakan ejen dalam satu tempoh masa? Bagaimanakah kita menetapkan kelajuan, bagaimana kita mengelakkan halangan, dan bagaimana kita merancang laluan apabila sampai ke destinasi adalah lebih sukar daripada hanya bergerak dalam garisan lurus? Mari kita lihat ini.
Управление
Pada peringkat awal, kami akan menganggap bahawa setiap ejen mempunyai nilai kelajuan, yang merangkumi berapa cepat ia bergerak dan ke arah mana. Ia boleh diukur dalam meter sesaat, kilometer sejam, piksel sesaat, dsb. Mengingat kembali gelung Sense/Think/Act, kita boleh bayangkan bahawa bahagian Think memilih kelajuan, dan bahagian Act menggunakan kelajuan itu kepada ejen. Biasanya permainan mempunyai sistem fizik yang melakukan tugas ini untuk anda, mempelajari nilai kelajuan setiap objek dan melaraskannya. Oleh itu, anda boleh meninggalkan AI dengan satu tugas - untuk menentukan kelajuan yang sepatutnya dimiliki oleh ejen. Jika anda tahu di mana ejen itu sepatutnya, maka anda perlu mengalihkannya ke arah yang betul pada kelajuan yang ditetapkan. Persamaan yang sangat remeh:
pengembaraan_ingin = kedudukan_destinasi – jawatan_ejen
Bayangkan dunia 2D. Ejen berada di titik (-2,-2), destinasi berada di suatu tempat di timur laut pada titik (30, 20), dan laluan yang diperlukan untuk ejen ke sana ialah (32, 22). Katakan kedudukan ini diukur dalam meter - jika kita mengambil kelajuan ejen menjadi 5 meter sesaat, maka kita akan menskalakan vektor anjakan kita dan mendapat kelajuan lebih kurang (4.12, 2.83). Dengan parameter ini, ejen akan tiba di destinasinya dalam hampir 8 saat.
Anda boleh mengira semula nilai pada bila-bila masa. Jika ejen berada separuh jalan ke sasaran, pergerakan akan menjadi separuh panjang, tetapi oleh kerana kelajuan maksimum ejen ialah 5 m/s (kami memutuskan ini di atas), kelajuannya adalah sama. Ini juga berfungsi untuk memindahkan sasaran, membolehkan ejen membuat perubahan kecil semasa mereka bergerak.
Tetapi kami mahukan lebih banyak variasi - contohnya, perlahan-lahan meningkatkan kelajuan untuk mensimulasikan watak bergerak daripada berdiri kepada berlari. Perkara yang sama boleh dilakukan pada penghujung sebelum berhenti. Ciri-ciri ini dikenali sebagai tingkah laku stereng, setiap satunya mempunyai nama khusus: Seek, Flee, Arrival, dsb. Ideanya ialah daya pecutan boleh digunakan pada kelajuan ejen, berdasarkan membandingkan kedudukan ejen dan kelajuan semasa dengan destinasi dalam untuk menggunakan kaedah yang berbeza untuk bergerak ke matlamat.
Setiap tingkah laku mempunyai tujuan yang sedikit berbeza. Seek and Arrival ialah cara untuk memindahkan ejen ke destinasi. Mengelak Halangan dan Pemisahan menyesuaikan pergerakan ejen untuk mengelakkan halangan dalam perjalanan ke gol. Penjajaran dan Kesepaduan memastikan ejen bergerak bersama. Sebarang bilangan gelagat stereng yang berbeza boleh dijumlahkan untuk menghasilkan vektor laluan tunggal dengan mengambil kira semua faktor. Ejen yang menggunakan gelagat Ketibaan, Pemisahan dan Mengelak Halangan untuk menjauhi dinding dan ejen lain. Pendekatan ini berfungsi dengan baik di lokasi terbuka tanpa butiran yang tidak perlu.
Dalam keadaan yang lebih sukar, penambahan tingkah laku yang berbeza berfungsi lebih teruk - contohnya, ejen boleh tersepit di dinding akibat konflik antara Ketibaan dan Pengelakan Halangan. Oleh itu, anda perlu mempertimbangkan pilihan yang lebih kompleks daripada hanya menambah semua nilai. Caranya ialah ini: daripada menambah hasil setiap tingkah laku, anda boleh mempertimbangkan pergerakan ke arah yang berbeza dan memilih pilihan terbaik.
Walau bagaimanapun, dalam persekitaran yang kompleks dengan jalan buntu dan pilihan tentang cara yang hendak dituju, kita akan memerlukan sesuatu yang lebih maju.
Mencari jalan
Tingkah laku pemanduan bagus untuk pergerakan mudah di kawasan lapang (padang bola sepak atau arena) di mana perjalanan dari A ke B adalah jalan lurus dengan hanya lencongan kecil di sekeliling halangan. Untuk laluan yang kompleks, kita memerlukan pencarian laluan, iaitu cara meneroka dunia dan menentukan laluan melaluinya.
Yang paling mudah ialah menggunakan grid pada setiap petak di sebelah ejen dan menilai yang mana antara mereka dibenarkan untuk bergerak. Jika salah satu daripadanya adalah destinasi, kemudian ikuti laluan dari setiap petak ke petak sebelumnya sehingga anda sampai ke permulaan. Ini adalah laluannya. Jika tidak, ulangi proses dengan petak lain yang berdekatan sehingga anda menemui destinasi anda atau anda kehabisan petak (bermaksud tiada laluan yang mungkin). Inilah yang secara rasmi dikenali sebagai Breadth-First Search atau BFS (algoritma carian pertama-luas). Pada setiap langkah dia melihat ke semua arah (oleh itu keluasan, "lebar"). Ruang carian adalah seperti muka gelombang yang bergerak sehingga ia mencapai lokasi yang dikehendaki - ruang carian mengembang pada setiap langkah sehingga titik akhir disertakan, selepas itu ia boleh dikesan kembali ke permulaan.
Akibatnya, anda akan menerima senarai petak di sepanjang laluan yang dikehendaki disusun. Ini ialah laluan (oleh itu, pencarian laluan) - senarai tempat yang akan dilawati ejen semasa mengikuti destinasi.
Memandangkan kita mengetahui kedudukan setiap petak di dunia, kita boleh menggunakan gelagat stereng untuk bergerak di sepanjang laluan - dari nod 1 ke nod 2, kemudian dari nod 2 ke nod 3, dan seterusnya. Pilihan paling mudah ialah menuju ke tengah petak seterusnya, tetapi pilihan yang lebih baik ialah berhenti di tengah-tengah tepi antara petak semasa dan petak seterusnya. Kerana ini, ejen akan dapat memotong selekoh pada selekoh tajam.
Algoritma BFS juga mempunyai kelemahan - ia meneroka seberapa banyak petak dalam arah "salah" seperti dalam arah "betul". Di sinilah algoritma yang lebih kompleks dipanggil A* (Bintang) dimainkan. Ia berfungsi dengan cara yang sama, tetapi bukannya memeriksa petak jiran secara membuta tuli (kemudian jiran jiran, kemudian jiran jiran jiran, dan seterusnya), ia mengumpul nod ke dalam senarai dan menyusunnya supaya nod seterusnya yang diperiksa adalah sentiasa satu yang menuju ke laluan terpendek. Nod diisih berdasarkan heuristik yang mengambil kira dua perkara—"kos" laluan hipotesis ke petak yang dikehendaki (termasuk sebarang kos perjalanan) dan anggaran sejauh mana petak itu dari destinasi (memihak carian dalam arah yang betul).
Contoh ini menunjukkan bahawa ejen meneroka satu petak pada satu masa, setiap kali memilih petak bersebelahan yang paling menjanjikan. Laluan yang terhasil adalah sama seperti BFS, tetapi lebih sedikit petak telah dipertimbangkan dalam proses - yang mempunyai kesan besar pada prestasi permainan.
Pergerakan tanpa grid
Tetapi kebanyakan permainan tidak diletakkan pada grid, dan selalunya mustahil untuk melakukannya tanpa mengorbankan realisme. Kompromi diperlukan. Apakah saiz petak yang sepatutnya? Terlalu besar dan mereka tidak akan dapat mewakili koridor kecil atau selekoh dengan betul, terlalu kecil dan akan terdapat terlalu banyak petak untuk dicari, yang akhirnya akan mengambil banyak masa.
Perkara pertama yang perlu difahami ialah mesh memberi kita graf nod bersambung. Algoritma A* dan BFS sebenarnya berfungsi pada graf dan tidak mengambil berat tentang jaringan kami sama sekali. Kami boleh meletakkan nod di mana-mana sahaja dalam dunia permainan: selagi terdapat sambungan antara mana-mana dua nod yang disambungkan, serta antara titik mula dan tamat dan sekurang-kurangnya satu daripada nod, algoritma akan berfungsi sama seperti sebelumnya. Ini sering dipanggil sistem titik laluan, kerana setiap nod mewakili kedudukan penting di dunia yang boleh menjadi sebahagian daripada sebarang bilangan laluan hipotesis.
Contoh 1: simpulan dalam setiap petak. Carian bermula dari nod di mana ejen berada dan berakhir pada nod petak yang dikehendaki.
Contoh 2: Satu set nod yang lebih kecil (titik jalan). Carian bermula di petak ejen, melalui bilangan nod yang diperlukan, dan kemudian terus ke destinasi.
Ini adalah sistem yang fleksibel dan berkuasa sepenuhnya. Tetapi sedikit berhati-hati diperlukan dalam menentukan tempat dan cara meletakkan titik laluan, jika tidak, ejen mungkin tidak melihat titik terdekat dan tidak akan dapat memulakan laluan. Lebih mudah jika kita boleh meletakkan titik laluan secara automatik berdasarkan geometri dunia.
Di sinilah jaringan navigasi atau navmesh (jaringan navigasi) muncul. Ini biasanya jaringan 2D segi tiga yang ditindih pada geometri dunia - di mana sahaja ejen dibenarkan berjalan. Setiap segi tiga dalam jaringan menjadi nod dalam graf dan mempunyai sehingga tiga segi tiga bersebelahan yang menjadi nod bersebelahan dalam graf.
Gambar ini adalah contoh daripada enjin Unity - ia menganalisis geometri di dunia dan mencipta navmesh (dalam tangkapan skrin dalam warna biru muda). Setiap poligon dalam navmesh ialah kawasan di mana ejen boleh berdiri atau bergerak dari satu poligon ke poligon yang lain. Dalam contoh ini, poligon lebih kecil daripada lantai di mana ia berada - ini dilakukan untuk mengambil kira saiz ejen, yang akan melampaui kedudukan nominalnya.
Kita boleh mencari laluan melalui mesh ini, sekali lagi menggunakan algoritma A*. Ini akan memberi kita laluan yang hampir sempurna di dunia, yang mengambil kira semua geometri dan tidak memerlukan nod dan penciptaan titik jalan yang tidak perlu.
Pathfinding adalah topik yang terlalu luas yang mana satu bahagian artikel tidak mencukupi. Jika anda ingin mengkajinya dengan lebih terperinci, maka ini akan membantu .
Планирование
Kami telah belajar dengan mencari laluan bahawa kadangkala tidak cukup dengan hanya memilih arah dan bergerak - kita perlu memilih laluan dan membuat beberapa pusingan untuk sampai ke destinasi yang kita inginkan. Kita boleh menyamaratakan idea ini: mencapai matlamat bukan sekadar langkah seterusnya, tetapi keseluruhan urutan di mana kadangkala anda perlu melihat ke hadapan beberapa langkah untuk mengetahui perkara pertama yang sepatutnya. Ini dinamakan perancangan. Pathfinding boleh dianggap sebagai salah satu daripada beberapa lanjutan kepada perancangan. Dari segi kitaran Sense/Think/Act kita, di sinilah bahagian Think merancang beberapa bahagian Act untuk masa hadapan.
Mari kita lihat contoh permainan papan Magic: The Gathering. Kami pergi dahulu dengan set kad berikut di tangan kami:
- Paya - Memberi 1 mana hitam (kad darat).
- Hutan - memberikan 1 mana hijau (kad tanah).
- Fugitive Wizard - Memerlukan 1 mana biru untuk dipanggil.
- Elvish Mystic - Memerlukan 1 mana hijau untuk dipanggil.
Kami mengabaikan baki tiga kad untuk memudahkannya. Mengikut peraturan, pemain dibenarkan bermain 1 kad darat setiap giliran, dia boleh "mengetuk" kad ini untuk mengeluarkan mana daripadanya, dan kemudian membuang mantra (termasuk memanggil makhluk) mengikut jumlah mana. Dalam situasi ini, pemain manusia tahu bermain Forest, ketik 1 mana hijau, dan kemudian memanggil Elvish Mystic. Tetapi bagaimana permainan AI boleh memikirkan perkara ini?
Perancangan yang mudah
Pendekatan remeh adalah mencuba setiap tindakan secara bergilir-gilir sehingga tiada yang sesuai lagi. Dengan melihat kad, AI melihat apa yang boleh dimainkan oleh Swamp. Dan dia memainkannya. Adakah terdapat sebarang tindakan lain yang tinggal pada giliran ini? Ia tidak boleh memanggil sama ada Elvish Mystic atau Fugitive Wizard, kerana mereka memerlukan mana hijau dan biru masing-masing untuk memanggil mereka, manakala Paya hanya menyediakan mana hitam. Dan dia tidak lagi boleh bermain Hutan, kerana dia sudah bermain Paya. Oleh itu, permainan AI mengikut peraturan, tetapi melakukannya dengan buruk. Boleh diperbaiki.
Perancangan boleh mencari senarai tindakan yang membawa permainan ke keadaan yang diingini. Sama seperti setiap petak di laluan mempunyai jiran (dalam mencari laluan), setiap tindakan dalam pelan juga mempunyai jiran atau pengganti. Kita boleh mencari tindakan ini dan tindakan seterusnya sehingga kita mencapai keadaan yang dikehendaki.
Dalam contoh kami, hasil yang diinginkan ialah "memanggil makhluk jika boleh." Pada permulaan giliran, kita melihat hanya dua kemungkinan tindakan yang dibenarkan oleh peraturan permainan:
1. Main Paya (hasil: Paya dalam permainan)
2. Main Hutan (hasil: Hutan dalam permainan)
Setiap tindakan yang diambil boleh membawa kepada tindakan selanjutnya dan menutup tindakan lain, sekali lagi bergantung pada peraturan permainan. Bayangkan kami bermain Paya - ini akan mengalih keluar Paya sebagai langkah seterusnya (kami sudah memainkannya), dan ini juga akan mengalih keluar Forest (kerana mengikut peraturan anda boleh bermain satu kad darat setiap giliran). Selepas ini, AI menambah mendapat 1 mana hitam sebagai langkah seterusnya kerana tiada pilihan lain. Jika dia meneruskan dan memilih Ketuk Paya, dia akan menerima 1 unit mana hitam dan tidak akan dapat berbuat apa-apa dengannya.
1. Main Paya (hasil: Paya dalam permainan)
1.1 Paya “Ketuk” (hasil: Paya “dituk”, +1 unit mana hitam)
Tiada tindakan tersedia - TAMAT
2. Main Hutan (hasil: Hutan dalam permainan)
Senarai tindakan adalah pendek, kami menemui jalan buntu. Kami mengulangi proses untuk langkah seterusnya. Kami bermain Hutan, buka aksi "dapatkan 1 mana hijau", yang seterusnya akan membuka aksi ketiga - panggil Elvish Mystic.
1. Main Paya (hasil: Paya dalam permainan)
1.1 Paya “Ketuk” (hasil: Paya “dituk”, +1 unit mana hitam)
Tiada tindakan tersedia - TAMAT
2. Main Hutan (hasil: Hutan dalam permainan)
2.1 Hutan "Tap" (hasil: Hutan "disetuk", +1 unit mana hijau)
2.1.1 Panggil Elvish Mystic (hasil: Elvish Mystic dalam permainan, -1 mana hijau)
Tiada tindakan tersedia - TAMAT
Akhirnya, kami meneroka semua tindakan yang mungkin dan menemui rancangan yang memanggil makhluk.
Ini adalah contoh yang sangat mudah. Adalah dinasihatkan untuk memilih pelan yang terbaik, bukannya sebarang pelan yang memenuhi beberapa kriteria. Secara umumnya adalah mungkin untuk menilai rancangan berpotensi berdasarkan hasil atau manfaat keseluruhan pelaksanaannya. Anda boleh menjaringkan 1 mata untuk bermain kad tanah dan 3 mata untuk memanggil makhluk. Bermain Paya akan menjadi pelan 1 mata. Dan bermain Forest → Tap the Forest → summon Elvish Mystic akan serta-merta memberikan 4 mata.
Beginilah cara perancangan berfungsi dalam Magic: The Gathering, tetapi logik yang sama digunakan dalam situasi lain. Sebagai contoh, menggerakkan bidak untuk memberi ruang kepada uskup untuk bergerak dalam catur. Atau berlindung di sebalik dinding untuk menembak dengan selamat dalam XCOM seperti ini. Secara umum, anda mendapat idea itu.
Perancangan yang lebih baik
Kadangkala terdapat terlalu banyak tindakan berpotensi untuk mempertimbangkan setiap pilihan yang mungkin. Kembali kepada contoh dengan Magic: The Gathering: katakan bahawa dalam permainan dan di tangan anda terdapat beberapa kad tanah dan makhluk - bilangan gabungan pergerakan yang mungkin boleh menjadi berpuluh-puluh. Terdapat beberapa penyelesaian kepada masalah tersebut.
Kaedah pertama ialah merantai ke belakang. Daripada mencuba semua kombinasi, lebih baik bermula dengan keputusan akhir dan cuba mencari laluan terus. Daripada pergi dari akar pokok ke daun tertentu, kita bergerak ke arah yang bertentangan - dari daun ke akar. Kaedah ini lebih mudah dan cepat.
Jika musuh mempunyai 1 kesihatan, anda boleh mencari pelan "deal 1 or more damage". Untuk mencapai matlamat ini, beberapa syarat mesti dipenuhi:
1. Kerosakan boleh disebabkan oleh jampi - ia mesti berada di tangan.
2. Untuk membuat mantra, anda memerlukan mana.
3. Untuk mendapatkan mana, anda perlu bermain kad tanah.
4. Untuk bermain kad tanah, anda perlu ada di tangan anda.
Cara lain ialah carian terbaik-pertama. Daripada mencuba semua laluan, kami memilih yang paling sesuai. Selalunya, kaedah ini memberikan pelan optimum tanpa kos carian yang tidak perlu. A* ialah satu bentuk carian pertama terbaik - dengan memeriksa laluan yang paling menjanjikan dari awal, ia sudah boleh mencari laluan terbaik tanpa perlu menyemak pilihan lain.
Pilihan carian pertama terbaik yang menarik dan semakin popular ialah Carian Pokok Monte Carlo. Daripada meneka rancangan yang lebih baik daripada yang lain apabila memilih setiap tindakan berikutnya, algoritma memilih pengganti rawak pada setiap langkah sehingga ia mencapai penghujung (apabila rancangan itu menghasilkan kemenangan atau kekalahan). Hasil akhir kemudiannya digunakan untuk menambah atau mengurangkan berat pilihan sebelumnya. Dengan mengulangi proses ini beberapa kali berturut-turut, algoritma memberikan anggaran yang baik tentang tindakan seterusnya yang terbaik, walaupun keadaan berubah (jika musuh mengambil tindakan untuk mengganggu pemain).
Tiada cerita tentang perancangan dalam permainan akan lengkap tanpa Perancangan Tindakan Berorientasikan Matlamat atau GOAP (perancangan tindakan berorientasikan matlamat). Ini adalah kaedah yang digunakan secara meluas dan dibincangkan, tetapi selain daripada beberapa butiran yang membezakan, ia pada asasnya adalah kaedah rantaian ke belakang yang kita bincangkan sebelum ini. Jika objektifnya adalah untuk "memusnahkan pemain" dan pemain berada di belakang perlindungan, rancangannya boleh: musnahkan dengan bom tangan → dapatkannya → baling.
Biasanya terdapat beberapa matlamat, masing-masing mempunyai keutamaan tersendiri. Jika objektif keutamaan tertinggi tidak dapat diselesaikan (tiada kombinasi tindakan mewujudkan rancangan "bunuh pemain" kerana pemain tidak kelihatan), AI akan kembali kepada objektif keutamaan yang lebih rendah.
Latihan dan penyesuaian
Kami telah mengatakan bahawa permainan AI biasanya tidak menggunakan pembelajaran mesin kerana ia tidak sesuai untuk mengurus ejen dalam masa nyata. Tetapi ini tidak bermakna anda tidak boleh meminjam sesuatu dari kawasan ini. Kami mahukan lawan dalam penembak yang boleh kami pelajari sesuatu. Sebagai contoh, ketahui tentang kedudukan terbaik pada peta. Atau lawan dalam permainan pertarungan yang akan menyekat gerakan kombo yang kerap digunakan pemain, mendorongnya untuk menggunakan orang lain. Jadi pembelajaran mesin boleh menjadi sangat berguna dalam situasi sedemikian.
Statistik dan Kebarangkalian
Sebelum kita masuk ke dalam contoh yang rumit, mari kita lihat sejauh mana kita boleh pergi dengan mengambil beberapa ukuran mudah dan menggunakannya untuk membuat keputusan. Contohnya, strategi masa nyata - bagaimana kita menentukan sama ada pemain boleh melancarkan serangan dalam beberapa minit pertama permainan dan pertahanan apa yang perlu disediakan untuk menentangnya? Kita boleh mengkaji pengalaman lepas pemain untuk memahami tindak balas masa hadapan. Sebagai permulaan, kami tidak mempunyai data mentah sedemikian, tetapi kami boleh mengumpulnya - setiap kali AI bermain melawan manusia, ia boleh merekodkan masa serangan pertama. Selepas beberapa sesi, kami akan mendapat purata masa yang diperlukan untuk pemain menyerang pada masa hadapan.
Terdapat juga masalah dengan nilai purata: jika pemain tergesa-gesa 20 kali dan bermain perlahan 20 kali, maka nilai yang diperlukan akan berada di suatu tempat di tengah, dan ini tidak akan memberi kita apa-apa yang berguna. Satu penyelesaian adalah untuk mengehadkan data input - 20 keping terakhir boleh diambil kira.
Pendekatan yang serupa digunakan apabila menganggarkan kemungkinan tindakan tertentu dengan mengandaikan bahawa pilihan masa lalu pemain adalah sama pada masa hadapan. Jika seorang pemain menyerang kita lima kali dengan bola api, dua kali dengan kilat, dan sekali dengan huru-hara, jelas sekali dia lebih suka bola api. Mari kita ekstrapolasi dan lihat kebarangkalian menggunakan senjata yang berbeza: bola api=62,5%, kilat=25% dan huru-hara=12,5%. AI permainan kami perlu bersedia untuk melindungi dirinya daripada kebakaran.
Kaedah lain yang menarik ialah menggunakan Pengelas Naive Bayes untuk mengkaji sejumlah besar data input dan mengklasifikasikan keadaan supaya AI bertindak balas dengan cara yang diingini. Pengelas Bayesian terkenal kerana penggunaannya dalam penapis spam e-mel. Di sana mereka meneliti perkataan, membandingkannya dengan tempat perkataan tersebut muncul sebelum ini (dalam spam atau tidak), dan membuat kesimpulan tentang e-mel masuk. Kita boleh melakukan perkara yang sama walaupun dengan input yang lebih sedikit. Berdasarkan semua maklumat berguna yang dilihat oleh AI (seperti unit musuh yang dicipta, atau mantra yang mereka gunakan, atau teknologi yang mereka selidiki), dan keputusan akhir (perang atau keamanan, tergesa-gesa atau bertahan, dsb.) - kami akan memilih tingkah laku AI yang diingini.
Semua kaedah latihan ini adalah mencukupi, tetapi dinasihatkan untuk menggunakannya berdasarkan data ujian. AI akan belajar menyesuaikan diri dengan strategi berbeza yang telah digunakan oleh penguji permainan anda. AI yang menyesuaikan diri dengan pemain selepas dikeluarkan mungkin menjadi terlalu boleh diramal atau terlalu sukar untuk dikalahkan.
Penyesuaian berasaskan nilai
Memandangkan kandungan dunia permainan kami dan peraturan, kami boleh menukar set nilai yang mempengaruhi pembuatan keputusan, dan bukannya hanya menggunakan data input. Kami melakukan ini:
- Biarkan AI mengumpul data tentang keadaan dunia dan peristiwa penting semasa permainan (seperti di atas).
- Mari kita ubah beberapa nilai penting berdasarkan data ini.
- Kami melaksanakan keputusan kami berdasarkan pemprosesan atau penilaian nilai ini.
Contohnya, ejen mempunyai beberapa bilik untuk dipilih pada peta penembak orang pertama. Setiap bilik mempunyai nilai tersendiri, yang menentukan betapa diingini untuk dikunjungi. AI secara rawak memilih bilik yang hendak dituju berdasarkan nilai. Ejen itu kemudian mengingati bilik mana dia dibunuh dan mengurangkan nilainya (kebarangkalian dia akan kembali ke sana). Begitu juga untuk keadaan sebaliknya - jika ejen memusnahkan banyak pihak lawan, maka nilai bilik meningkat.
model Markov
Bagaimana jika kami menggunakan data yang dikumpul untuk membuat ramalan? Jika kita mengingati setiap bilik yang kita lihat pemain masuk untuk tempoh masa tertentu, kita akan meramalkan bilik mana pemain itu mungkin pergi. Dengan menjejak dan merakam pergerakan pemain merentas bilik (nilai), kami boleh meramalkannya.
Mari kita ambil tiga bilik: merah, hijau dan biru. Dan juga pemerhatian yang kami rakamkan semasa menonton sesi permainan:
Bilangan pemerhatian dalam setiap bilik adalah hampir sama - kami masih tidak tahu di mana untuk membuat tempat yang baik untuk serangan hendap. Pengumpulan statistik juga rumit oleh pembiakan semula pemain, yang muncul secara sama rata di seluruh peta. Tetapi data tentang bilik seterusnya yang mereka masukkan selepas muncul pada peta sudah berguna.
Ia boleh dilihat bahawa bilik hijau sesuai dengan pemain - kebanyakan orang berpindah dari bilik merah ke bilik itu, 50% daripadanya kekal di sana lebih jauh. Bilik biru, sebaliknya, tidak popular; hampir tiada siapa yang pergi ke sana, dan jika mereka melakukannya, mereka tidak tinggal lama.
Tetapi data memberitahu kita sesuatu yang lebih penting - apabila pemain berada di dalam bilik biru, bilik seterusnya yang kita lihat dia akan menjadi merah, bukan hijau. Walaupun bilik hijau lebih popular daripada bilik merah, keadaan berubah jika pemain berada di bilik biru. Keadaan seterusnya (iaitu bilik yang akan dituju oleh pemain) bergantung pada keadaan sebelumnya (iaitu bilik yang sedang diduduki pemain). Kerana kami meneroka kebergantungan, kami akan membuat ramalan yang lebih tepat berbanding jika kami hanya mengira pemerhatian secara bebas.
Meramalkan keadaan masa depan berdasarkan data dari keadaan masa lalu dipanggil model Markov, dan contoh sedemikian (dengan bilik) dipanggil rantai Markov. Memandangkan corak mewakili kebarangkalian perubahan antara keadaan berturut-turut, ia dipaparkan secara visual sebagai FSM dengan kebarangkalian di sekitar setiap peralihan. Sebelum ini, kami menggunakan FSM untuk mewakili keadaan tingkah laku di mana ejen berada, tetapi konsep ini meluas ke mana-mana keadaan, sama ada ia dikaitkan dengan ejen atau tidak. Dalam kes ini, negeri mewakili bilik yang diduduki ejen:
Ini adalah cara mudah untuk mewakili kemungkinan relatif perubahan keadaan, memberikan AI sedikit keupayaan untuk meramalkan keadaan seterusnya. Anda boleh menjangka beberapa langkah ke hadapan.
Jika pemain berada di dalam bilik hijau, terdapat 50% peluang bahawa dia akan kekal di sana apabila dia diperhatikan. Tetapi apakah kemungkinan dia akan tetap berada di sana walaupun selepas itu? Bukan sahaja ada peluang pemain itu kekal di bilik hijau selepas dua pemerhatian, tetapi ada juga peluang dia pergi dan kembali. Berikut ialah jadual baharu dengan mengambil kira data baharu:
Ia menunjukkan bahawa peluang untuk melihat pemain di dalam bilik hijau selepas dua pemerhatian akan bersamaan dengan 51% - 21% bahawa dia akan berasal dari bilik merah, 5% daripada mereka bahawa pemain akan melawat bilik biru di antara mereka, dan 25% bahawa pemain tidak akan meninggalkan bilik hijau.
Jadual hanyalah alat visual - prosedur hanya memerlukan pendaraban kebarangkalian pada setiap langkah. Ini bermakna anda boleh melihat jauh ke masa hadapan dengan satu kaveat: kami menganggap bahawa peluang untuk memasuki bilik bergantung sepenuhnya pada bilik semasa. Ini dipanggil Harta Markov - keadaan masa depan hanya bergantung pada masa kini. Tetapi ini tidak seratus peratus tepat. Pemain boleh menukar keputusan bergantung pada faktor lain: tahap kesihatan atau jumlah peluru. Kerana kami tidak merekodkan nilai ini, ramalan kami akan menjadi kurang tepat.
N-Gram
Bagaimana pula dengan contoh permainan pertarungan dan meramalkan pergerakan kombo pemain? Sama! Tetapi bukannya satu keadaan atau peristiwa, kami akan memeriksa keseluruhan urutan yang membentuk mogok kombo.
Satu cara untuk melakukan ini ialah menyimpan setiap input (seperti Kick, Punch atau Block) dalam penimbal dan menulis keseluruhan penimbal sebagai acara. Jadi pemain berulang kali menekan Kick, Kick, Punch untuk menggunakan serangan SuperDeathFist, sistem AI menyimpan semua input dalam buffer dan mengingati tiga terakhir yang digunakan dalam setiap langkah.
(Barisan dalam huruf tebal adalah apabila pemain melancarkan serangan SuperDeathFist.)
AI akan melihat semua pilihan apabila pemain memilih Kick, diikuti dengan Kick lain, dan kemudian perhatikan bahawa input seterusnya sentiasa Punch. Ini akan membolehkan ejen meramalkan langkah kombo SuperDeathFist dan menyekatnya jika boleh.
Urutan peristiwa ini dipanggil N-gram, di mana N ialah bilangan unsur yang disimpan. Dalam contoh sebelumnya ia adalah 3-gram (trigram), yang bermaksud: dua entri pertama digunakan untuk meramalkan yang ketiga. Oleh itu, dalam 5-gram, empat entri pertama meramalkan yang kelima dan seterusnya.
Pereka bentuk perlu memilih saiz N-gram dengan berhati-hati. N yang lebih kecil memerlukan kurang ingatan tetapi juga menyimpan lebih sedikit sejarah. Sebagai contoh, 2 gram (bigram) akan merekodkan Kick, Kick atau Kick, Punch, tetapi tidak akan dapat menyimpan Kick, Kick, Punch, jadi AI tidak akan bertindak balas kepada kombo SuperDeathFist.
Sebaliknya, nombor yang lebih besar memerlukan lebih banyak memori dan AI akan menjadi lebih sukar untuk dilatih kerana terdapat lebih banyak pilihan yang mungkin. Jika anda mempunyai tiga kemungkinan input Kick, Punch atau Block, dan kami menggunakan 10 gram, itu kira-kira 60 ribu pilihan yang berbeza.
Model bigram ialah rantai Markov yang ringkas - setiap pasangan keadaan/keadaan semasa adalah bigram, dan anda boleh meramalkan keadaan kedua berdasarkan yang pertama. N-gram 3-gram dan lebih besar juga boleh dianggap sebagai rantai Markov, di mana semua elemen (kecuali yang terakhir dalam N-gram) bersama-sama membentuk keadaan pertama dan elemen terakhir yang kedua. Contoh permainan pertarungan menunjukkan peluang untuk beralih daripada keadaan Tendangan dan Tendangan kepada keadaan Tendangan dan Tebuk. Dengan menganggap berbilang entri sejarah input sebagai satu unit, kami pada asasnya mengubah urutan input menjadi sebahagian daripada keseluruhan negeri. Ini memberikan kami sifat Markov, yang membolehkan kami menggunakan rantai Markov untuk meramalkan input seterusnya dan meneka apa langkah kombo seterusnya.
Kesimpulan
Kami bercakap tentang alat dan pendekatan yang paling biasa dalam pembangunan kecerdasan buatan. Kami juga melihat situasi di mana ia perlu digunakan dan di mana ia amat berguna.
Ini sepatutnya cukup untuk memahami asas permainan AI. Tetapi, sudah tentu, ini bukan semua kaedah. Kurang popular, tetapi tidak kurang berkesan termasuk:
- algoritma pengoptimuman termasuk mendaki bukit, turun kecerunan dan algoritma genetik
- algoritma carian/penjadualan lawan (pemangkasan minimax dan alfa-beta)
- kaedah pengelasan (perceptron, rangkaian saraf dan mesin vektor sokongan)
- sistem untuk memproses persepsi dan ingatan ejen
- pendekatan seni bina kepada AI (sistem hibrid, seni bina subset dan cara lain untuk menindih sistem AI)
- alat animasi (perancangan dan penyelarasan gerakan)
- faktor prestasi (tahap perincian, bila-bila masa, dan algoritma pemasakan masa)
Sumber dalam talian mengenai topik:
1. GameDev.net mempunyai Dan .
2. mengandungi banyak pembentangan dan artikel mengenai pelbagai topik yang berkaitan dengan pembangunan AI permainan.
3. termasuk topik daripada Sidang Kemuncak AI GDC, kebanyakannya tersedia secara percuma.
4. Bahan berguna juga boleh didapati di laman web .
5. Tommy Thompson, penyelidik AI dan pembangun permainan, membuat video di YouTube dengan penjelasan dan kajian AI dalam permainan komersial.
Buku mengenai topik:
1. Siri buku Game AI Pro ialah koleksi artikel pendek yang menerangkan cara melaksanakan ciri khusus atau cara menyelesaikan masalah tertentu.
2. Siri Kebijaksanaan Pengaturcaraan Permainan AI ialah pendahulu siri Game AI Pro. Ia mengandungi kaedah yang lebih lama, tetapi hampir semuanya relevan walaupun hari ini.
3. adalah salah satu teks asas untuk semua orang yang ingin memahami bidang umum kecerdasan buatan. Ini bukan buku tentang pembangunan permainan - ia mengajar asas AI.
Sumber: www.habr.com