Salah satu proyek yang telah lama saya impikan untuk diimplementasikan adalah bot tugas modular dengan memori. Tujuan akhir dari proyek ini adalah untuk menciptakan dunia dengan makhluk yang mampu bertindak secara mandiri dan kolektif.
Saya biasa memprogram generator dunia, jadi saya ingin mengisi dunia dengan bot sederhana yang menggunakan AI untuk menentukan perilaku dan interaksi mereka. Jadi, berkat pengaruh aktor di dunia, adalah mungkin untuk meningkatkan detailnya.
Saya sudah menerapkan sistem pipeline tugas Javascript dasar (karena menyederhanakan hidup saya), tetapi saya menginginkan sesuatu yang lebih dapat diandalkan dan terukur, jadi saya menulis proyek ini dalam C ++. Persaingan untuk implementasi kebun prosedural dalam generasi subreddit / r / prosedural membawa saya ke ini (maka topik yang sesuai).
Dalam sistem saya, simulasi terdiri dari tiga komponen: dunia, populasi, dan serangkaian tindakan yang menghubungkan mereka. Karena itu, saya perlu membuat tiga model, yang akan saya bahas dalam artikel ini.
Untuk meningkatkan kompleksitas, saya ingin para aktor menyimpan informasi tentang pengalaman sebelumnya dengan dunia dan menggunakan pengetahuan tentang interaksi ini dalam tindakan di masa depan.
Saat membuat model dunia, saya memilih jalur sederhana dan menggunakan suara Perlin untuk meletakkannya di permukaan air. Semua benda lain di dunia terletak secara acak.
Untuk model populasi (dan "ingatannya"), saya cukup membuat kelas dengan beberapa karakteristik dan koordinat. Ini seharusnya merupakan simulasi resolusi rendah. Memori adalah antrian, bot melihat sekeliling, menyimpan informasi tentang lingkungan mereka, menulis ke antrian dan mengelola antrian ini sebagai interpretasi dari memori mereka.
Untuk menghubungkan kedua sistem tindakan ini, saya ingin membuat kerangka kerja tugas-tugas primitif di dalam sistem hirarki tugas antrian sehingga entitas individu dapat menerapkan perilaku kompleks di dunia.
Peta contoh. Air mengambil bentuk sungai sepenuhnya tanpa sengaja. Semua elemen lain terletak secara acak, termasuk sarang semut, yang pada benih ini bergeser terlalu jauh ke tepi (tetapi sungai terlihat indah).Saya memutuskan bahwa sekelompok semut dalam pengumpulan daun rumput akan menjadi model pengujian yang baik yang menjamin keandalan pelaksanaan fungsi dasar (dan sistem antrian tugas secara keseluruhan) dan mencegah kebocoran memori (ada banyak).
Saya ingin menjelaskan secara lebih rinci struktur sistem tugas dan memori, dan juga menunjukkan bagaimana kompleksitas diciptakan dari (sebagian besar) fungsi dasar primitif. Saya juga ingin menunjukkan beberapa “memori semut” yang lucu yang mungkin Anda temui ketika semut mulai berputar-putar mencari rumput atau berdiri diam dan membuat program melambat.
Struktur umum
Saya menulis simulasi ini di C ++, dan menggunakan SDL2 untuk rendering (saya sudah menulis kelas presentasi kecil untuk SLD2 sebelumnya). Saya juga menggunakan implementasi A * (sedikit dimodifikasi) yang saya temukan di github karena
implementasi saya sangat lambat dan saya tidak bisa mengerti mengapa.
Peta hanyalah kotak 100 × 100 dengan dua lapisan - lapisan tanah (digunakan untuk mencari jalur) dan lapisan isi (untuk menyelesaikan interaksi dan jalur pencarian). Kelas dunia juga menangani berbagai fungsi kosmetik, seperti pertumbuhan rumput dan tumbuh-tumbuhan. Saya berbicara tentang ini sekarang karena ini adalah satu-satunya bagian yang tidak akan dijelaskan dalam artikel ini.
Populasi
Bot berada di kelas dengan properti yang menggambarkan makhluk tunggal. Beberapa di antaranya bersifat kosmetik, yang lain memengaruhi eksekusi tindakan (misalnya, kemampuan terbang, jangkauan penglihatan, apa yang dimakannya, dan apa yang bisa dikenakan makhluk itu).
Yang paling penting di sini adalah nilai tambahan yang menentukan perilaku. Yaitu: vektor yang berisi jalur mereka saat ini A *, sehingga tidak perlu dihitung dalam setiap siklus jam (ini menghemat waktu komputasi dan memungkinkan Anda untuk mensimulasikan lebih banyak bot), dan antrian memori yang menentukan interpretasi makhluk itu terhadap lingkungan mereka.
Antrian memori
Antrian memori adalah antrian sederhana yang berisi sekumpulan objek memori yang ukurannya dibatasi oleh properti bot. Setiap kali ingatan baru ditambahkan, mereka didorong ke depan, dan segala sesuatu yang melampaui batas di belakang terputus. Berkat ini, beberapa kenangan bisa lebih "segar" daripada yang lain.
Jika bot ingin mengingat informasi dari memori, maka ia membuat objek memori (permintaan) dan membandingkannya dengan apa yang ada di memori. Kemudian fungsi recall mengembalikan vektor kenangan yang cocok dengan salah satu atau semua kriteria yang ditentukan dalam kueri.
class Memory{ public:
Kenangan terdiri dari objek sederhana yang berisi beberapa properti. Properti memori ini dianggap "terkait" satu sama lain. Setiap memori juga diberi nilai "recallScore", yang diulang setiap kali memori diingat oleh fungsi recall. Setiap kali bot mengingat memori, bot melakukan penyortiran sekali jalan, mulai dari belakang, mengubah urutan memori jika memori recall dari memori yang lebih lama lebih tinggi daripada memori yang baru. Berkat ini, beberapa memori mungkin lebih "penting" (dengan ukuran memori besar) dan disimpan lebih lama dalam antrian. Seiring waktu, mereka akan digantikan oleh yang baru.
Antrian memori
Saya juga menambahkan beberapa operator kelebihan beban ke kelas ini sehingga perbandingan langsung antara antrian memori dan kueri dapat dilakukan, membandingkan properti "apa saja" atau "semua", sehingga hanya properti yang ditentukan yang ditimpa ketika memori ditimpa. Berkat ini, kita dapat memiliki memori objek yang dikaitkan dengan suatu tempat, tetapi jika kita melihat tempat ini lagi dan objek tidak ada di sana, kita dapat memperbarui memori dengan menimpanya dengan memori yang berisi kotak isian baru, menggunakan kueri yang sesuai dengan tempat ini .
void Bot::updateMemory(Memory &query, bool all, Memory &memory){
Dalam proses membuat kode untuk sistem ini, saya belajar banyak.
Sistem tugas
Sifat dari loop game atau rendering adalah bahwa fungsi yang sama diulang dalam setiap ukuran, namun, saya ingin menerapkan perilaku non-siklik di bot saya.
Di bagian ini, saya akan menjelaskan dua pandangan tentang struktur sistem tugas yang dirancang untuk melawan efek ini.
Struktur bottom-up
Saya memutuskan untuk pindah dari bawah ke atas dan membuat satu set "tindakan primitif" yang harus dilakukan bot. Masing-masing tindakan ini hanya berlangsung satu ketukan. Dengan pustaka fungsi primitif yang baik, kita dapat menggabungkannya ke dalam tindakan kompleks yang terdiri dari beberapa fungsi primitif.
Contoh tindakan primitif tersebut:
Perhatikan bahwa tindakan ini berisi referensi ke dunia dan populasi, memungkinkan Anda untuk mengubahnya.
- Tunggu menyebabkan makhluk itu tidak melakukan apa pun dalam lingkaran ini.
- Lihatlah mem-parsing lingkungan dan mengantri memori baru.
- Swap mengambil objek di tangan makhluk itu dan menggantinya dengan yang terbaring di tanah.
- Konsumsi menghancurkan item di tangan makhluk itu.
- Langkah mengambil jalur terhitung saat ini ke tujuan dan melakukan satu langkah (dengan banyak pemeriksaan kesalahan).
- ... dan seterusnya.
Semua fungsi tugas adalah anggota kelas tugas saya; setelah pengujian yang ketat, mereka telah membuktikan keandalan dan kemampuan mereka untuk bergabung ke dalam tugas yang lebih kompleks.
Dalam fungsi-fungsi sekunder ini, kami membangun fungsi hanya dengan merantai tugas-tugas lain:
- Tugas berjalan hanya beberapa langkah (dengan penanganan kesalahan)
- Tugas take adalah tugas look and swap (diperlukan karena pemrosesan memori semut, yang akan saya jelaskan nanti)
- Tugas idle adalah memilih tempat acak dan pindah ke sana (menggunakan jalan kaki), menunggu beberapa siklus (menggunakan menunggu), dan ulangi siklus ini selama beberapa kali
- ... dan seterusnya
Tugas-tugas lain lebih rumit. Tugas pencarian mengeksekusi kueri memori untuk mencari setiap memori tempat yang mengandung objek "makanan" (dapat dimakan untuk bot jenis ini). Dia mengunduh kenangan ini dan berkeliling di sekitar mereka semua, “mencari” makanan (dalam hal semut, ini adalah rumput). Jika tidak ada ingatan makanan, tugas itu membuat makhluk itu secara acak berkeliaran di dunia dan melihat-lihat. Dengan menonton dan mempelajari (dengan melakukan "tampilan" dengan viewRadius = 1; yaitu, hanya melihat ubin di bawahnya), makhluk itu dapat memperbarui ingatannya dengan informasi tentang lingkungannya, secara cerdas dan sengaja mencari makanan.
Tugas mencari makan yang lebih umum terdiri dari mencari makanan, mengambil makanan, memeriksa (untuk memperbarui memori dan menemukan makanan di lingkungan), kembali ke rumah dan menyimpan makanan.
Anda mungkin memperhatikan bahwa semut keluar dari sarang semut dan mencari makanan dengan sengaja. Karena inisialisasi, jalur awal semut diarahkan ke titik acak, karena ingatan mereka pada t = 0 kosong. Kemudian mereka diberi perintah untuk mengambil makanan dalam tugas mencari makan, dan mereka juga melihat sekeliling, memastikan bahwa tidak ada lagi makanan. Dari waktu ke waktu mereka mulai mengembara, karena mereka kehabisan tempat di mana mereka melihat makanan (rabun dekat).Dan akhirnya, bot memiliki "tampilan" yang menentukan jenis AI yang ditugaskan padanya. Setiap tampilan dikaitkan dengan satu tugas kontrol yang mendefinisikan semua perilakunya: terdiri dari serangkaian tugas yang semakin kecil, mudah ditentukan oleh satu set antrian memori dan tugas primitif. Ini adalah tugas-tugas seperti Ant dan Bee.
Struktur top-down
Jika Anda melihat dari atas ke bawah, sistem terdiri dari kelas master tugas yang mengoordinasikan tugas kontrol dan pelaksanaannya untuk setiap bot individu di peta.
Taskmaster memiliki vektor tugas kontrol, yang masing-masing dikaitkan dengan bot. Setiap tugas kontrol, pada gilirannya, memiliki antrian subtugas yang dimuat selama inisialisasi pertama objek tugas dengan fungsi tugas terkait.
class Task{ public:
Setiap objek tugas dalam antrian menyimpan array argumen, yang diteruskan ke penangan fungsi terkait. Argumen-argumen ini menentukan perilaku tugas-tugas primitif yang dibuat seluas mungkin. Argumen dilewatkan dengan referensi, sehingga objek tugas dalam antrian dapat menyimpan argumennya dan memungkinkan subfungsi untuk diubah, sehingga Anda dapat mengimplementasikan hal-hal seperti iterasi untuk menunggu sejumlah kutu atau permintaan untuk mengumpulkan sejumlah item tertentu, dll. Subfungsi mengubah nilai iterator (argumen [n]) dari fungsi induk dengan referensi dan menjadikan kondisi keberhasilannya bergantung pada nilainya.
Dalam setiap ukuran, pemberi tugas memeriksa daftar tugas kontrol dan menjalankannya dengan memanggil metode performanya. Metode perform, pada gilirannya, melihat elemen teratas dari antrian di dalam tugas dan mengeksekusinya dengan argumen dari tugas. Dengan demikian, Anda dapat menurunkan antrian tugas, selalu melakukan tugas tertinggi. Kemudian nilai balik tugas menentukan penyelesaian tugas.
Ketika tugas primitif mengembalikan true, ia telah mencapai titik stabilnya, atau setidaknya tidak boleh diulangi (misalnya, langkah mengembalikan true ketika makhluk telah mencapai titik akhir). Artinya, kondisi pengembaliannya terpenuhi dan dihapus dari antrian sehingga tugas berikutnya dapat diselesaikan pada langkah berikutnya.
Tugas yang berisi antrian tugas mengembalikan true setelah antrian kosong. Karena ini, dimungkinkan untuk membuat tugas-tugas kompleks dengan struktur antrian dan sub-antrian di mana fungsi yang sama terus-menerus dipanggil, tetapi masing-masing panggilan iterates status permainan dan status tugas dengan satu langkah.
Akhirnya, tugas kontrol menggunakan struktur sederhana - mereka dipanggil di setiap siklus, memuat tugas hanya jika mereka kosong, dan melakukan tugas yang dimuat dalam antrian mereka.
Dengan bantuan loop antrian saya (lihat kode), saya dapat berulang kali menjalankan satu fungsi dan setiap kali menjalankan elemen teratas dalam antriannya, mendorong elemen keluar dari itu jika memanggil metode performanya mengembalikan true.
Hasil
Semua ini dibungkus dengan libconfig, sehingga parameter simulasi sangat mudah diubah. Anda dapat mengkodekan banyak tugas kontrol tanpa masalah (saya membuat semut dan lebah), dan mendefinisikan dan memuat spesies baru menggunakan libconfig sangat sederhana.
Mereka dimuat dengan elegan ke dalam simulasi. Berkat pencarian baru yang ditingkatkan untuk jalur, saya dapat mensimulasikan sejumlah besar bot aktif individu mengumpulkan makanan di pesawat dua dimensi.
Simulasi 40 semut mengumpulkan rumput secara bersamaan. Jalan yang mereka buat di pasir disebabkan oleh peningkatan berat yang diberikan pada tanah yang "masih alami". Ini mengarah pada penciptaan karakteristik "jalan raya semut." Mereka juga dapat diartikan sebagai feromon, tetapi akan lebih seperti kebenaran jika semut benar-benar bertukar ingatan.Modularitas sistem ini memastikan penciptaan spesies baru secara cepat yang perilakunya ditentukan oleh tugas kontrol yang sederhana. Dalam kode di atas, Anda dapat melihat bahwa saya membuat cacing dan lebah AI hanya dengan mengubah warnanya, membatasi pencarian jalur (mereka tidak bisa terbang), jarak pandang dan ukuran memori. Pada saat yang sama, saya mengubah perilaku umum mereka, karena semua parameter ini digunakan oleh fungsi tugas primitif.
Debugging Ant Memories
Struktur tugas dan memori yang kompleks telah menyebabkan kesulitan yang tak terduga dan kebutuhan untuk menangani pengecualian.
Berikut adalah tiga bug memori yang sangat rumit yang membuat saya mengulang subsistem:
Semut berlari dalam lingkaran
Salah satu serangga pertama yang harus saya hadapi: semut berlari dengan gila di sepanjang pola yang tertutup di lapangan untuk mencari rumput di tanah kosong. Masalah ini muncul karena pada saat itu saya belum menerapkan pembaruan memori. Semut memiliki ingatan tentang lokasi makanan, dan segera setelah mereka mengambil rumput dan melihat sekeliling lagi, ingatan baru terbentuk.
Masalahnya adalah ingatan baru itu pada titik yang sama, tetapi ingatan lama tetap dipertahankan. Ini berarti bahwa dalam proses mencari makanan, semut mengingat dan menyimpan lokasi makanan yang tidak lagi berlaku, tetapi ingatan lama ini dipertahankan dan menggantikan yang baru (mereka ingat ramuan lezat ini).
Saya memperbaikinya sebagai berikut: data objek hanya ditimpa dalam ingatan lama, jika kita melihat tempat yang sama dan objek telah berubah (misalnya, makhluk itu melihat bahwa tidak ada lagi rumput di sana, tetapi tidak ingat bahwa dulu ada rumput). Mungkin di masa depan saya hanya akan menambahkan properti "tidak valid" ke dalam memori saya sehingga bot dapat mengingat informasi lama yang mungkin penting, tetapi informasi yang tidak lagi valid "muncul" ("Saya melihat beruang di sini, tetapi sekarang tidak ada di sana").
Semut mengambil benda di bawah semut lain
Dari waktu ke waktu (terutama dengan sejumlah besar semut dan kepadatan rumput yang tinggi), dua semut dapat naik ke satu ubin rumput dalam satu ukuran dan mencoba mengambilnya. Ini berarti bahwa semut pertama memasuki ubin, melihat sekeliling dan mengambil item dalam 3 langkah. Pada gilirannya, semut kedua melakukan hal yang sama, tepat sebelum mengangkat objek, semut lain mengambilnya dari bawah hidungnya. Dengan tenang dia melanjutkan tugasnya, memeriksa lingkungan yang sama dengan semut lainnya pada ukuran sebelumnya, dan memproses garis ingatannya dengan cara yang sama (karena pada tahap ini ingatan mereka identik). Hal ini menyebabkan semut kedua menyalin yang pertama, tidak pernah mengambil benda dan mengikuti yang pertama, yang benar-benar melakukan semua pekerjaan. Saya perhatikan ini karena dalam simulasi lima semut, hanya tiga yang terlihat. Butuh waktu lama untuk menemukan penyebabnya.
Saya memecahkan masalah ini dengan membuat tugas swap menjadi primitif dan membuat tugas take, yang pertama kali melihat ke tanah untuk melihat apakah ada objek di sana. Jika ya, ia "bertukar", dan jika tidak, ia "menunggu" untuk dua gerakan sehingga semut lainnya pasti akan pergi. Dalam satu kasus, tindakan ini untuk dua ukuran, di yang lain - untuk satu ukuran.
Lokasi yang tidak terjangkau
Bug lain yang tidak menyenangkan yang memaksa saya untuk mengulang pemrosesan memori adalah bahwa beberapa tempat yang bisa dilihat semut itu tidak terjangkau baginya. Mereka muncul karena penempatan "salib rumput" saya yang malas di tanah, yang terkadang tergantung di atas air. Ini membuat saya menggeneralisasi tugas langkah.
Ketika mengirimkan permintaan untuk pencarian makanan, semut sering memiliki ingatan tentang tempat-tempat yang benar-benar tidak dapat dijangkau (mereka melihat rumput di atas air dan dengan
gila -
gilaan ingin mengumpulkannya). Jika tidak ditandai dalam ingatan mereka (misalnya, variabel boolean "dapat dijangkau"), maka mereka terus mengingat ini dan menulis ke antrian hingga tindakan ini adalah satu-satunya. Hal ini menyebabkan penghambatan yang parah, karena mereka
terus melakukan operasi pencarian jalur di setiap langkah, berusaha untuk sampai ke sana, dan gagal .
Solusinya adalah memperbarui memori dalam tugas langkah jika tidak dapat menemukan jalur ke tempat itu, menandainya dalam memori sebagai tidak dapat dicapai. Selain itu, tugas pencarian hanya menanyakan tempat dengan makanan untuk kenangan yang bisa dijangkau.
Sistem secara umum
Secara umum, saya ingin mengatakan - ya, saya menyesal telah menghabiskan satu minggu hidup saya di maraton pemrograman karena saya terinspirasi untuk membuat bot yang melakukan apa yang saya katakan kepada mereka (dan juga apa yang ingin mereka lakukan!). Saya harus melakukan beberapa trik dan belajar banyak.
Sistem yang saya buat tidak 100% andal, dan saya masih melihat beberapa artefak. Misalnya, sebagai arah untuk mem-parsing tampilan, aksinya digunakan atas-bawah dan kiri-kanan, yaitu, memori terakhir ada di sudut kanan bawah. Saat mengingat informasi untuk mencari item, ini berarti makhluk cenderung bergerak ke tenggara. Ini terutama terlihat dalam simulasi besar, ketika, rumput tumbuh dengan cepat dan sedikit membungkuk ke arah tenggara, terlepas dari biji.
Perangkat tambahan
Saya pikir diperlukan perbaikan signifikan untuk mensimulasikan ingatan yang lebih kompleks dari makhluk yang lebih kompleks.
Ini termasuk meningkatkan keandalan fungsi pemrosesan memori, serta menambahkan primitif baru, seperti "berpikir", dan turunan dari tugas tingkat tinggi, seperti "memutuskan" atau "mimpi". "Berpikir" mungkin merupakan tindakan primitif dari permintaan memori. "Mimpi", pada gilirannya, dapat terdiri dari beberapa panggilan "pikir": memilih memori acak, mendapatkan properti acak, dan mengulanginya berulang kali untuk memperkuat tema umum atau asosiasi penting.
Untuk masa depan, saya merencanakan tiga tambahan khusus:
- Tambahkan penanganan terputus dan prioritas tugas
- Tambahkan komunikasi antar entitas
- Tambahkan struktur grup sehingga entitas dapat secara resmi mengidentifikasi satu sama lain
Memproses gangguan dan memprioritaskan tugas mungkin diperlukan untuk interaksi antar entitas, karena bot tidak dapat secara membabi buta melanjutkan aktivitasnya ketika mereka berkomunikasi dengannya (entah bagaimana harus "mendengarkan") atau diserang ("melarikan diri" atau "melawan" )
Komunikasi antara entitas mungkin terdiri dari satu atau dua tugas primitif untuk bertukar memori atau membuat permintaan ke memori bot lain (misalnya, "katakan" atau "tanya"). Dengan cara ini, informasi seperti lokasi makanan atau sumber daya lainnya dapat dikirimkan.
Saya berharap dapat melaksanakan tugas-tugas ini dan menyusun grafik tingkat akumulasi sumber daya oleh kelompok besar dengan dan tanpa komunikasi. Populasi sudah melacak jumlah makanan yang dikumpulkan dalam setiap ukuran. Akan menarik untuk menunjukkan bahwa berbagi kenangan dapat memengaruhi efisiensi.
Masa depan
Fungsi yang paling penting untuk mensimulasikan masyarakat adalah menambah struktur kelompok dan memberikan sifat-sifat tingkat makro pada kelompok-kelompok ini, misalnya, “tujuan dan tanggung jawab” bersama mereka. Ini memberi kita semacam "benih" dari mana kita bisa mendapatkan tugas tingkat tinggi yang didelegasikan ke dalam hierarki struktur kelompok untuk tugas tingkat tinggi "lebih rendah" yang secara langsung mempengaruhi dunia. Ini juga memungkinkan Anda untuk membuat bentuk struktur politik.
Sistem seperti itu cukup mandiri, dan visualisasi hanya ditumpangkan di atasnya. Akan sangat sederhana untuk mengganti serangga dengan humanoids, mengumpulkan sumber daya dan menyimpannya di suatu tempat, sehingga tumbuh dalam ukuran.
Sifat pertumbuhan rumah mereka dapat, misalnya, sangat tergantung atau sepenuhnya independen dari aksi bot. Spesies yang berbeda mungkin memiliki suku yang berbeda dengan karakteristik dan tren yang berbeda pula.Selain itu, saya dapat menggabungkan sistem ini dengan generator peta yang dibuat sebelumnya (memperluas kelas dunia) untuk membuat dunia lebih nyata.Kesimpulannya
Dalam waktu dekat, saya berencana untuk mengganti makhluk dengan orang-orang dan mengimplementasikan beberapa fungsi terakhir. Mungkin saya akan menerbitkan kode sumber lengkap ketika saya meningkatkan kualitas sistem (di beberapa tempat kode agak kacau).Tunggu artikel selanjutnya. Sementara itu, di sini ada video dengan lebah mencari serbuk sari dalam bunga; mereka dikodekan menggunakan kerangka kerja yang sama.Saya memilih benih ini karena titik awalnya terletak di sebuah pulau kecil. Namun, lebah tidak diprogram untuk kembali ke sarang, tetapi hanya terus mengumpulkan serbuk sari. Anda mungkin memperhatikan bahwa jangkauan penglihatan mereka lebih tinggi dan terkadang mereka dengan sengaja pindah ke bunga yang baru saja mereka lihat.... dan di sini adalah fungsi anggota Tugas Bee: bool Task::Bee(Garden &garden, Population &population, int (&arguments)[10]){