Selamat datang di Tim Algoritma Graceful!
Sebagai percobaan, kami memutuskan untuk menyimpan "buku harian" pengembang tempat kami akan berbagi pengalaman dan menyoroti beberapa hasil menarik dari eksperimen kami. Ini adalah artikel debut kami di proyek "Pathfinder 3D" - aset untuk mesin game Unity, yang memungkinkan Anda untuk mencari jalur dalam ruang tiga dimensi. Di dalamnya, kita akan berbicara tentang jalan dari asal usul ide ke produk lengkap dan tentang beberapa masalah yang kita temui. Materi ini akan berguna bagi orang yang ingin memulai proyek mereka dan mendukungnya di masa depan, serta bagi mereka yang ingin menerapkan pencarian untuk jalur di luar angkasa.
Sebuah tim yang terdiri dari dua orang mulai mengerjakan aset tersebut. Yang pertama memiliki beberapa perkembangan yang memungkinkan untuk mempercepat proses menemukan jalur terpendek pada grafik kompleks yang cukup untuk bekerja secara real time, dan keinginan untuk menemukan aplikasi praktis untuk mereka, yang kedua memiliki pengalaman bekerja dengan Unity dan sedang mencari ide untuk memulai. Karena mereka sering berkomunikasi satu sama lain, tidak mengherankan bahwa pada titik tertentu muncul ide tentang kemungkinan menciptakan aset untuk mencari jalan di ruang tiga dimensi.
Ketika mempelajari katalog aset Unity, banyak solusi ditemukan untuk menemukan jalan dalam ruang dua dimensi, tetapi tidak satu dalam tiga dimensi. Menjadi jelas bahwa ini adalah peluang besar untuk memasuki pasar perangkat lunak Unity, terutama mengingat visibilitas dan hiburan dari hasil yang diharapkan.
Tujuannya adalah untuk mengimplementasikan secara langsung pencarian jalur di ruang tiga dimensi dan kemampuan khas solusi yang ada untuk menemukan jalur di ruang dua dimensi. Kami mulai bekerja: yang dikembangkan secara langsung mekanisme pencarian jalur, kelas kedua dan metode untuk mengelola proses pencarian jalur, antarmuka konfigurasi, adegan pengujian, dokumentasi, lokasi proyek, dan juga terlibat dalam mendaftar dan menyiapkan akun layanan yang diperlukan untuk menjual aset.
Segera setelah dimulainya pekerjaan, menjadi jelas bahwa beberapa jenis sumber daya bersama diperlukan bagi tim untuk membuat catatan: daftar tugas dan masalah yang perlu diselesaikan, informasi tentang keputusan yang diambil, ide-ide menarik dan hasil penelitian di masa depan. Setelah menganalisis solusi yang ada, kami berhenti di
Trello , karena fungsionalitasnya, kesederhanaannya, kenyamanan dan penampilannya yang menyenangkan. Seperti yang telah ditunjukkan oleh latihan, layanan ini sangat nyaman untuk tim kecil. Jika tim memiliki lebih dari 5 orang, kami akan merekomendasikan menggunakan sistem manajemen proyek yang lengkap.
Selanjutnya, kami menggambarkan keputusan yang dibuat selama pengembangan versi pertama dari aset, dan logika yang kami ikuti saat membuat mereka. Orang-orang yang memiliki pengalaman dengan Unity dan terbiasa dengan algoritma pencarian jalur akan segera memahami di mana masalah akan muncul di masa depan. Di tempat-tempat ini, kami menggunakan solusi sederhana untuk mengurangi waktu pengembangan hingga versi pertama dari aset diterima, agar tidak macet, karena antusiasme terbatas dan tidak konstan. Dengan demikian, kami berurusan dengan salah satu alasan paling umum untuk menutup startup seperti itu, karena itu banyak proyek mati tanpa dilahirkan. Semua bidang masalah diperbaiki setelah publikasi aset.
Untuk menemukan lintasan, algoritma
A * (A star) dipilih karena kecepatan operasinya yang tinggi di ruang terbuka yang luas. Sebagian besar algoritma pencarian jalur bekerja pada grafik yang diwakili oleh matriks diskrit. Dimungkinkan untuk membuat matriks ini sebelumnya, tetapi proses konstruksi satu kali dalam ruang tiga dimensi dengan hambatan memandang waktu itu sebagai tugas yang agak sulit. Selain itu, tidak jelas bagaimana melakukan ini tanpa mengorbankan kinerja, karena pada saat awal bekerja pada aset tidak ada pengalaman dengan proses latar belakang dan multithreading di Unity, serta dengan multithreading secara umum. Grafik dibentuk secara real time dengan memeriksa ruang dengan sinar fisik (Physics.BoxCast) ke arah pencarian. Lintasan yang ditemukan dikurangi menjadi rusak dengan titik tengah lebih sedikit, dan kemudian dihaluskan oleh splines.
Kesulitan utama adalah ketidakmungkinan menggunakan metode fisik mesin secara serempak, karena mereka dapat bekerja secara eksklusif di utas utama. Pada adegan yang tidak terlalu rumit, menggunakan fungsi pencarian pada saat yang sama oleh tidak lebih dari dua puluh agen tidak secara signifikan mempengaruhi laju bingkai. Untuk menghilangkan drawdowns FPS yang langka dan kuat, beban komputasi ditempatkan dalam waktu menggunakan coroutine. Ini memperlambat pencarian, tetapi tidak signifikan.
Sebelum mengirimkan aset untuk moderasi, Anda perlu memasukkan kode dan menyusun dokumentasi terperinci, sesuai dengan
persyaratan , mendaftar, dan mengonfigurasi surat dukungan. Juga disarankan untuk membuat situs web proyek di mana berita dan demo pengembangan akan ditampilkan dengan nyaman. Ini akan menjadi nilai tambah yang besar baik selama moderasi, dan saat mempelajari aset Anda oleh pengguna sebelum membeli. Layanan hosting dan surat dipesan oleh kami dari
BeGet , karena pada saat itu menawarkan penawaran yang paling menguntungkan, dan biaya kami 1000r / tahun.
Moderasi aset berlangsung selama 22 hari dan berlalu untuk pertama kalinya, karena kami dengan sangat hati-hati mendekati dokumentasi dan desain halaman aset di Unity store. Setelah publikasi, aset langsung jatuh ke tempat pertama dalam kategori Scripting / AI. Sejak saat itu, surat-surat mulai datang ke surat dukungan yang meminta bantuan dalam memecahkan masalah-masalah tertentu. Kadang beberapa per hari, kadang tidak sebulan. Jika Anda rata-rata, maka selama sebulan 2 orang mengajukan pertanyaan, korespondensi dengan yang memakan waktu total 2-3 jam. Tidak terlalu banyak, tetapi harus diingat bahwa terlepas dari beban kerja Anda saat ini, Anda harus merespons dengan sangat cepat sehingga pengguna yang marah tidak menulis ulasan buruk tentang produk, tetapi, sebaliknya, antusias tentang dukungan kualitas, meninggalkan yang positif. Juga, cukup banyak pertanyaan datang ke surat seperti "apakah aset Anda akan berfungsi jika ...". Surat-surat semacam itu juga tidak boleh diabaikan, karena ini adalah pembeli potensial yang dapat pergi.
Ketika keluhan dari pembeli pertama diterima, menjadi jelas bahwa banyak pengguna menggunakan aset pada adegan kompleks yang memiliki konfigurasi labirin atau rongga terhubung lainnya. Dalam proyek semacam itu, skema pencarian jalur kami, berdasarkan pemeriksaan tabrakan, dan bahkan di arus utama, tidak cukup efektif. Oleh karena itu, kami mulai menerapkan konstruksi awal grafik sehingga akan mungkin untuk mencari jalur di aliran samping tanpa menggunakan fisika dan mengakses objek pemandangan.
Diskretisasi ruang tiga dimensi memecahnya menjadi kubus. Menyimpan informasi tentang semua kubus partisi adalah mubazir dan sangat intensif memori. Oleh karena itu, logis untuk menyimpan hanya koordinat sel yang tidak dapat dilewati, yang telah dilakukan.
Hambatan permainan adalah angka poligonal dan terdiri dari segitiga. Untuk memperhitungkan hambatan dalam grafik pencarian, Anda harus menemukan semua kubus partisi yang memotong segitiga apa pun dari hambatan apa pun. Sudah pada tahap ini, kemungkinan untuk secara dinamis menghapus dan menambahkan hambatan ke panggung telah diletakkan, dan tidak hanya koordinat kubus yang diduduki diselamatkan, tetapi juga pengidentifikasi kendala yang ada di dalamnya. Sekarang dimungkinkan untuk membuat grafik navigasi sebelum dimulainya proses permainan dan, karena dihilangkannya sejumlah besar perhitungan kompleks selama pencarian jalur, lebih dari dua ratus agen bisa membuatnya secara bersamaan tanpa mengorbankan kinerja.
Masalah lain yang kami ketahui juga terasa: algoritma A * dan modifikasinya bekerja sangat buruk di ruang terbatas pada grafik daya tinggi. Karena algoritma mereka lebih memilih arah rute menuju mendekati titik target, setiap jalan buntu yang mengarah ke target sangat memperlambat pencarian jalan, karena sebelum memilih arah yang berbeda dari "perkecambahan", algoritma pertama "mengisi" seluruh ruang di dalam jalan buntu.
Dalam situasi seperti itu,
algoritma pencarian gelombang (Lee Algoritma) terbukti sangat efektif karena
jumlah operasi yang lebih kecil diperlukan untuk "mengisi" ruang. Oleh karena itu, ditambahkan ke aset sebagai alternatif. Saat menguji pada tahap yang merupakan labirin, waktu pencarian untuk jalur berkurang lebih dari 30 kali.
Untuk mempercepat pemrosesan awal adegan dan menemukan jalur ke aset, kemungkinan eksekusi paralel proses ditambahkan, tetapi efisiensi paralelisme sangat rendah, karena kenyataan bahwa ketika bekerja dengan wadah yang menyimpan koordinat sel yang ditempati, perlu untuk menyinkronkan aliran, yang dilakukan dengan menyinkronkan aliran, yang dilakukan dengan menggunakan mutex, karena koleksi kompetitif dan banyak alat lain untuk memastikan sinkronisasi yang efisien
diimplementasikan hanya dalam standar .NET Framework 4.5, dan di Unity, versi .NE digunakan hingga rilis 2018. T Framework 3.5. Kami mencoba untuk memecahkan masalah ini menggunakan alat yang tersedia, tetapi mereka memiliki kinerja yang sangat biasa-biasa saja, dan kami hanya mendapatkan hasil yang diinginkan setelah beralih ke rilis Unity 2018. Penggunaan koleksi kompetitif juga membuka kemungkinan untuk menyadari perubahan dinamis dari rintangan di tempat kejadian.
Pada tahap tertentu, ketidaksepakatan mulai timbul dalam tim mengenai distribusi keuntungan, dan orang ketiga bergabung dengan tim, yang memperkenalkan sistem untuk menilai waktu investasi dari masing-masing anggota tim, dan juga mulai terlibat dalam inspeksi dan pengujian kode, yang secara signifikan meningkatkan kualitas produk.
Sistem untuk memperkirakan biaya waktu saat ini dibuat dalam bentuk tabel Excel dan merupakan sistem otomatis di mana sebulan sekali perlu memasukkan informasi tentang penjualan dan tugas yang diselesaikan selama sebulan terakhir. Anggota tim perlu mengevaluasi berapa banyak waktu yang mereka perlukan untuk menyelesaikan masalah tertentu. Dengan demikian, ketika menilai kompleksitas waktu tugas, kecepatan setiap peserta diperhitungkan. Penaksiran berlebihan atau pernyataan yang tidak wajar oleh salah satu peserta segera menjadi jelas dari akumulasi statistik penilaian sebelumnya. Dan, dengan tidak adanya penjelasan yang memuaskan, masalah ini diputuskan oleh seluruh tim. Pendekatan ini terbukti baik untuk digunakan selama enam bulan dan diizinkan untuk mengumpulkan statistik yang menarik. Kami tidak menemukan solusi gratis siap pakai yang akan menyediakan fitur yang dijelaskan. Oleh karena itu, saat ini, untuk tim kecil, implementasi dalam bentuk tabel Excel tampaknya optimal bagi kami. Untuk tim yang relatif besar, kemungkinan besar Anda harus merancang basis data, mengembangkan bagian server dan klien, atau menerapkan ekstensi untuk salah satu sistem manajemen proyek yang ada.
Untuk meringkas. Setahun telah berlalu sejak awal pengembangan ke versi pertama dengan fungsionalitas minimum yang diperlukan dan kinerja yang cukup untuk digunakan dalam proyek nyata. Enam bulan lagi dihabiskan untuk meningkatkan kinerja dan mengimplementasikan pekerjaan multi-utas aset. Saat ini, kami memperkirakan biaya waktu untuk proyek ini pada 1065 jam kerja (ini adalah perkiraan yang agak optimis), dan laba rata-rata untuk bulan tersebut adalah 9,5t. Sangat mudah untuk menghitung bahwa biaya rata-rata satu jam kerja saat ini adalah sekitar 160 rubel, yang tidak terlalu banyak. Namun, hal utama dalam acara ini adalah pengalaman yang didapat oleh masing-masing peserta. Termasuk pengalaman kerja tim dan pengalaman dukungan produk perangkat lunak. Proyek ini dapat dianggap berhasil.
Sekarang tim kami telah mulai menerapkan fungsi tambahan yang berguna: verifikasi jangkauan algoritmik; kemampuan untuk menetapkan objek game ke portal; dukungan hambatan dinamis; Navigasi lokal antara agen untuk mencegah tabrakan dan merencanakan rute lokal.
Kami berharap materi ini membantu seseorang membawa proyek mereka ke garis finish.