Sistem inventaris yang terorganisir secara otomatis / cerdas?

11

selama seminggu terakhir saya telah mengerjakan sistem persediaan dengan Unity3D. Pada awalnya saya mendapat bantuan dari orang-orang di Design3 tetapi tidak terlalu lama sampai kami membagi jalan, karena saya benar-benar tidak suka cara mereka melakukan kode mereka, tidak ada bau OOP sama sekali.

Saya mengambil langkah lebih jauh ke depan - item mengambil lebih dari satu slot, sistem penempatan canggih (item mencoba yang terbaik untuk menemukan yang paling cocok), sistem mouse lokal (mouse terjebak di area tas aktif), dll.

Ini demo pekerjaan saya.

Apa yang ingin kami miliki dalam permainan kami, adalah fitur pengorganisasian otomatis - bukan pengurutan otomatis. Kami menginginkan fitur ini karena inventaris kami akan berada dalam 'waktu-nyata' - tidak seperti di Resident Evil 1,2,3 dll di mana Anda akan menjeda permainan dan melakukan hal-hal dalam inventaris Anda. Sekarang bayangkan diri Anda dalam situasi lengket dikelilingi oleh zombie, dan Anda tidak memiliki peluru, Anda melihat-lihat, Anda melihat ada peluru di dekatnya di tanah, jadi Anda pergi untuk mereka dan mencoba untuk mengambilnya, tetapi mereka tidak cocok! Anda melihat inventaris Anda dan mengetahui bahwa jika Anda mengatur kembali beberapa item, itu akan cocok! - sekarang pemain - dalam situasi itu tidak punya waktu untuk mengatur kembali karena dia dikelilingi dengan zombie dan akan mati jika dia berhenti dan mengatur inventaris untuk membuat ruang (ingat inventaris secara real-time, tanpa jeda) - tidak akan t baguskah hal itu terjadi secara otomatis? - Iya!

(Saya percaya ini telah diterapkan di beberapa game seperti pengepungan Penjara Bawah Tanah atau sesuatu, jadi yakin itu bisa dilakukan)

lihat gambar ini misalnya:

Apa yang dilakukan penyortiran otomatis

Ya, jadi jika Anda menyortir masalah secara otomatis, Anda akan mendapatkan ruang Anda, tetapi itu buruk karena: 1- Mahal: tidak perlu operasi penyortiran keseluruhan untuk membebaskan ruang-ruang tersebut, pada gambar pertama, cukup geser item merah di bagian bawah ke kiri, dan Anda mendapatkan ruang yang sama dengan yang Anda dapatkan dari auto-sort. 2 - Ini menjengkelkan bagi pemain: "Siapa yang F memberitahu Anda untuk memesan kembali barang-barang saya?"

Saya tidak meminta "Bagaimana cara menulis kode" untuk ini, saya hanya meminta beberapa panduan, ke mana harus mencari, algoritma apa yang terlibat? Apakah ini terkait dengan grafik dan hal-hal jalur terpendek? Saya harap tidak karena saya tidak berhasil melanjutkan studi ke perguruan tinggi: / Tetapi meskipun demikian, katakan saja kepada saya dan saya akan mempelajari hal-hal terkait.

Perhatikan mungkin ada lebih dari satu solusi. Jadi saya kira hal pertama yang harus saya lakukan adalah mencari tahu apakah situasinya 'dapat dipecahkan' - jika saya tahu bagaimana menentukan apakah suatu situasi dapat dipecahkan atau tidak, maka saya dapat 'menyelesaikannya'. Saya hanya perlu mengetahui kondisi yang membuatnya 'bisa dipecahkan'. Dan saya percaya harus ada beberapa algoritma / struktur data untuk ini.

Berikut ini foto untuk lebih dari satu solusi untuk mencoba memasukkan barang 1x3:

masukkan deskripsi gambar di sini

Panah menunjukkan hanya satu dari solusi, tetapi jika Anda melihat Anda akan menemukan lebih dari satu. Inilah yang akhirnya saya tidak menyortir otomatis tetapi menemukan solusi dan menerapkannya.

Perhatikan bahwa jika saya menghabiskan waktu untuk itu, saya akan menemukan cara untuk menyelesaikannya, tetapi itu tidak akan menjadi cara terbaik, itu seperti, memegang roda mobil dengan kaki Anda, bukan tangan Anda! XD Atau seperti mencoba memecahkan masalah yang membutuhkan array, tetapi Anda belum mengetahui keberadaannya! Jadi apa pendekatan yang tepat untuk ini?

Pembaruan dari Komentar

@Stephen Saya benar-benar bukan guru di Alogs, Anda menyebutkan 'knapsack' dan @BlueRaja - Danny Pflughoeft menyebutkan bin binok 2D. Apakah keduanya terkait / sama? - Saya masih bingung bagaimana saya harus mendekati ini.

Dan ya saya sudah menggunakan "heuristik" tetapi saya tidak benar-benar tahu bahwa saya adalah: D ia menemukan slot pertama yang tersedia, dan melihat apakah item cocok di sana.

Saya tidak tahu apakah memesan item berdasarkan "bulkiness" mereka (yang saya sebut nSlotsRequired = nRowsReq * nColsRec) akan berfungsi, karena Anda memiliki item 2x2 dan 1x4 misalnya, mereka memiliki bulkiness yang sama, tetapi bentuk yang berbeda dan akan memiliki efek yang berbeda pada bagaimana sisa barang selanjutnya akan pergi. JADI ...: /

Saya menonton video ini , saya benar-benar menyukai ide pengemasan penuh, tapi saya ingin tahu bagaimana melakukannya karena inventarisnya 2D. Saya bahkan tidak yakin bahwa pengemasan bin adalah kuncinya di sini karena, ya memang benar bahwa saya dapat memiliki lebih dari satu tas, tetapi dalam permainan kami itu hanya akan menjadi satu tas. Jadi, ini soal memasukkan barang ke dalam tas 'satu' dan tidak lebih dari itu. Jadi contoh di vid itu (pipa dan bus) tidak benar-benar cocok dengan masalah saya. Juga memperhatikan beberapa hal tentang ransel ini, saya tidak melihat bagaimana 'nilai' itu terkait dengan barang / inventaris saya, tapi saya kira 'berat' sama dengan bulkiness, tidak yakin.

kesal
sumber
7
Ini adalah bin-packing 2D, yang merupakan NP-Complete. Jadi, algoritma apa pun yang akan memberi tahu Anda jika Anda dapat memuat semua item akan tidak efisien (dalam kasus terburuk). Anda dapat menemukan beberapa algoritma perkiraan yang cukup bagus.
BlueRaja - Danny Pflughoeft
Inilah sebabnya saya memutuskan pada model persediaan tipe satu-slot-per-item (lebih umum hari ini). Saya berharap saya punya solusi untuk Anda, saya menyerah pada masalah ini ...
Ryno
@ BlueRaja-DannyPflughoeft Saya bertanya-tanya apakah algoritma sederhana / efisien tersedia jika item terbatas pada bentuk tertentu?
congusbongus
Membatasi bentuk tidak mengurangi kompleksitas tetapi hanya membuatnya lebih mudah untuk dipikirkan sehingga Anda berpikir kompleksitas telah ditangani, afaik.
Patrick Hughes
@VeXe Maaf saya ketinggalan pembaruan pada pertanyaan Anda. Tempat sampah dan ransel tidak sama. Namun keduanya merupakan masalah pengepakan. 'Nilai' dalam kasus Anda adalah bentuk dan ukuran objek inventaris Anda.
Stephen

Jawaban:

8

Ini adalah variasi dari masalah ransel. Seperti Danny Pflughoeft menyebutkan itu NP-Lengkap. Berarti itu tidak dapat diselesaikan dalam waktu linier, jika saya ingat dengan benar.

Tetapi Anda dapat mencoba menyelesaikannya dalam beberapa langkah. Ini pada dasarnya masalah pemilahan.

Saya akan mulai dengan menghitung 'bulkiness' dari setiap item: ini dapat dihitung beberapa cara:

  • bulkiness = max (panjang, lebar);

  • bulkiness = panjang * lebar

  • bulkiness = sqrt (panjang * lebar)

Kemudian mulailah menempatkan item dengan skor tertinggi terlebih dahulu ke dalam inventaris. Karena mereka kemungkinan besar tidak akan masuk ke dalam ruang yang tersisa nanti. Barang-barang kecil akan selalu pas.

Anda memerlukan heuristik (nama mewah untuk tebakan ;-)) untuk strategi penempatan Anda. Sesuatu seperti mencoba memasukkan item di slot bebas pertama dari kiri atas atau apalah.

Menurut saya, strategi penyortiran persediaan Diablo II agak mirip. Benda-benda seperti pedang dan tombak akan berakhir di kiri atas, lalu pakaian dan baju besi, kemudian gesper dan sebagainya.

Saya pikir Anda benar-benar perlu mencoba ini dan men-tweak algoritma (perhitungan bulkiness berbeda, heuristik berbeda), sampai itu bekerja cukup masuk akal.

Stephen
sumber
1
NP-complete adalah serangkaian masalah dengan kompleksitas lebih tinggi dari jumlahnya banyak. Untuk inventaris yang relatif kecil (kurang dari seribu item saya katakan :)) bahkan algoritma eksponensial akan bekerja cukup cepat, karena satu langkah dari algoritma tersebut membutuhkan waktu yang sangat sedikit. Namun demikian menggunakan ide Anda harus cukup baik dan lebih mudah daripada menerapkan algoritma pemrograman dinamis -> +1
MartinTeeVarga
Terima kasih untuk upvote. Ya inventaris tidak boleh berpotensi tak terbatas sehingga algoritma eksponensial harus berfungsi dengan baik ^^
Stephen
@ sm4: Seribu biasanya merupakan jumlah yang sangat besar untuk masalah NP-Complete. Ingat, masalah-masalah ini adalah O (2 ^ n) - bahkan hanya 2 ^ 64 tidak layak secara komputasi!
BlueRaja - Danny Pflughoeft
3

Haha, @Semua orang yang membantu, terima kasih. Saya akhirnya berhasil menyelesaikannya. Inilah yang pada dasarnya saya lakukan:

IEnumerator AddItem_Sorted (Item item)
  1. Kondisi sepele: periksa apakah kami mendapat barang minimum dan diperlukan item agar sesuai, jika kami memilikinya, lanjutkan ...
  2. kami akan mengosongkan semua tas - memasukkan barang ke dalam placeholder (daftar atau sesuatu)
  3. tambahkan item yang diinginkan ke slot / SANGAT terakhir tempat itu bisa masuk, pastikan itu yakin dalam bentuk horizontal
  4. menggunakan algo pengurangan fit pertama kami akan menambahkan sisa barang kami
  5. selama penambahan, kami akan menggunakan pemrograman dinamis (memoisasi) untuk mengingat indeks yang kami tambahkan (indeks slot yang tersedia berikutnya)
  6. jika semua penambahan berhasil, kami telah berhasil menyesuaikan barang yang diinginkan kami, dan entah bagaimana mengurutkan tas - dari barang besar ke kecil
  7. jika kami tidak dapat menambahkan semua item, ini berarti, ini bukan situasi yang bisa dipecahkan, jadi kami harus membawa tas ke keadaan sebelumnya
  8. salah satu cara untuk melakukan itu, (muncul dari permukaan pikiranku), adalah dengan menyalin keadaan kantong sebelum seluruh operasi ini, dan kemudian jika gagal kita akan beralih ke keadaan sebelumnya, atau bahkan lebih baik lagi, selama ' mengosongkan 'tas, kami mengingat di mana setiap item berada, sehingga jika op gagal, kami akan mendapatkannya kembali - menggunakan AddItem (item, indeks) - pada indeks sebelumnya :)
  9. seluruh proses ini mungkin memakan waktu, sehingga kami dapat membagi beban pada frame yang berbeda, menggunakan hasil yang bagus :)
  10. DIBUAT ! \ m / (@ ~ 9:00)

MEMPERBARUI:

  1. Saya membuat array yang menyimpan indeks dari semua item yang ditambahkan, dengan cara itu saya tidak perlu pergi dan mencari slot yang ditempati untuk saya bebas - peningkatan besar.

  2. tidak perlu menambahkan pada slot terakhir, bahkan kadang-kadang mungkin tidak berfungsi seperti itu, saya telah menambahkan item yang diinginkan ke sisa item lainnya dan mengurutkannya dengan mereka.

Seperti yang dapat Anda lihat dari video, itu perlu sedikit pengoptimalan, pengurutannya tidak sempurna, saya ingin menggunakan pengemasan bin penuh, tetapi sudah serakah kinerja. Saya terbuka untuk saran pengoptimalan, terima kasih lagi :)

kesal
sumber
Sama-sama! :) Saya ingin mengucapkan terima kasih kepada BlueRaja - Danny Pflughoeft untuk menyebutkan bin packing, @Stephen untuk ide besar dan Richard Buckland untuk kuliah pemrograman dinamisnya, dan semua kuliah.
vexe