Bagaimana saya bisa menerapkan sesuatu seperti kotak kerajinan Minecraft?

55

Sistem kerajinan tangan di Minecraft menggunakan kisi 2x2 atau 3x3. Anda menempatkan bahan-bahan pada kisi-kisi, dan jika Anda meletakkan bahan-bahan yang tepat dalam pola yang tepat, itu akan mengaktifkan resep.

Beberapa poin menarik tentang desain:

  • Beberapa resep dapat menukar bahan-bahan tertentu dengan yang lain. Misalnya, pick menggunakan tongkat untuk haft, dan dapat menggunakan papan kayu, batu bulat, batang besi, batang emas, atau permata berlian untuk kepala.
  • Posisi relatif dalam pola adalah yang penting, bukan posisi absolut pada grid. Artinya, Anda dapat membuat obor dengan menempatkan tongkat dan batu bara (atau arang) dalam pola yang benar di salah satu dari enam posisi pada kisi 3x3.
  • Pola dapat dibalik secara horizontal.

Saya mungkin terlalu banyak berpikir, tapi sepertinya ini masalah pencarian / set-reduksi yang menarik. Jadi, bagaimana cara (atau bisa) ini bekerja, secara algoritmik berbicara?

David Eyk
sumber
6
Pertanyaan yang luar biasa! Saya sangat tertarik! Saya sudah memiliki beberapa ide tetapi dan saya akan membagikannya segera setelah saya pulang.
jcora
Saya sebenarnya mencoba untuk menulis salinan Minecraft "sedekat mungkin". Saya sudah menulis semua inventaris dan resep manajer dan saya harus mengatakan itu bekerja dengan sangat rapi. Saya puas dengan kode bersih. Namun, tidak mudah untuk menulisnya. Saya menulis sekitar 10 kelas untuk membuat semuanya bekerja dengan baik resep, grid, inventaris, dll. Ketika saya menemukan waktu, saya akan menulis jawaban.
Martijn Courteaux
Anda harus melihat bagaimana minecraft mengkode resep kerajinan mereka.
Bradman175

Jawaban:

14

Solusi lain adalah dengan menggunakan pohon yang agak rumit. Simpul cabang di pohon Anda akan dibuat dengan mengulangi resep (sekali lagi menggunakan for (y) { for (x) }); ini adalah struktur pohon by-the-book standar stok Anda. Node akhir Anda akan berisi struktur tambahan ( Dictionary/ HashMap) yang memetakan dimensi ke resep.

Pada dasarnya apa yang Anda tuju adalah ini:

Pohon Resep

Node hitam adalah cabang Anda yang menunjukkan jenis item - yang merah adalah dedaunan Anda (terminator) yang memungkinkan Anda untuk membedakan ukuran / orientasi.

Untuk mencari di pohon ini, Anda pertama-tama akan menemukan kotak pembatas (seperti dijabarkan dalam jawaban pertama saya ) dan kemudian beralih ke node dalam urutan yang sama melintasi pohon saat Anda pergi. Akhirnya Anda cukup melihat dimensi di Dictionaryatau HashMapAnda dan Anda akan mendapatkan hasil resep.

Hanya untuk iseng saya pergi dan menerapkan ini - yang mungkin akan mengklarifikasi jawaban saya. Juga : Saya menyadari ini adalah jawaban yang berbeda - dan memang seharusnya begitu: ini adalah solusi yang berbeda.

Jonathan Dickinson
sumber
Sangat mudah. Saya suka itu.
David Eyk
Saya akan menerima yang ini, karena saya suka pohon, hash, dan diagram yang memotong inti permasalahan. Sekali lihat diagram, dan saya segera mengerti algoritma Anda.
David Eyk
23

Anda harus ingat bahwa Minecraft hanya menggunakan satu set resep yang sangat kecil, jadi tidak perlu apa pun yang sepintar itu.

Yang mengatakan apa yang akan saya lakukan adalah menemukan grid terkecil yang cocok (yaitu mengabaikan baris dan kolom kosong untuk mengetahui apakah itu 2x2 atau 3x3, atau 2x3 (pintu)). Kemudian lewati daftar resep dengan ukuran itu, cukup periksa apakah jenis itemnya sama (yaitu, paling buruk 9 perbandingan bilangan bulat di minecraft karena menggunakan id jenis bilangan bulat untuk item dan blok) dan berhenti ketika Anda menemukan kecocokan.

Cara ini juga membuat posisi relatif item tidak relevan (Anda dapat meletakkan obor di mana saja di kotak kerajinan dan itu akan berfungsi karena ia melihatnya sebagai kotak 1x2, bukan kotak 3x3 yang sebagian besar kosong).

Jika Anda memiliki sejumlah besar resep sehingga melakukan pencarian linier melalui pertandingan yang mungkin membutuhkan waktu lama akan mungkin untuk mengurutkan daftar dan melakukan pencarian biner (O (log (N)) vs O (N)). Ini akan menyebabkan beberapa pekerjaan tambahan dalam membangun daftar, tetapi ini bisa dilakukan saat startup sekali dan disimpan di memori sesudahnya.

Juga satu hal terakhir, untuk memungkinkan membalik resep secara horizontal paling sederhana adalah dengan menambahkan versi cermin ke daftar.

Jika Anda ingin melakukannya tanpa menambahkan resep kedua, Anda dapat memeriksa apakah resep input memiliki item dalam [0,0] dengan id lebih tinggi daripada [[0,2] (atau [0,1] untuk 2x2, tidak perlu cek) untuk 1x2 dan jika demikian cerminkan itu, jika tidak melanjutkan memeriksa baris berikutnya sampai Anda mencapai akhir. Dengan menggunakan ini Anda juga harus memastikan resep ditambahkan dalam rotasi yang benar.

Elva
sumber
1
Saya bertanya-tanya apakah sejumlah kecil resep di Minecraft mungkin tidak cocok untuk pencarian linier.
David Eyk
1
Ya, dan pada dasarnya adalah apa yang saya tulis di atas (dengan kemungkinan optimasi pencarian biner). Namun itu menyisakan beberapa opsi untuk membuat obor yang bisa Anda pasangkan di mana saja. Dengan terlebih dahulu mendapatkan ukuran resep, Anda tidak perlu menambahkan 6 resep untuk obor dan Anda membatasi pencarian hanya pada ukuran yang benar dalam satu langkah. - Jadi pada dasarnya opsi untuk poin 2 Anda adalah kelompok berdasarkan ukuran, pindahkan resep ke sudut atau tambahkan lebih banyak resep duplikat.
Elva
15

Melihat apakah konfigurasi kisi tertentu cocok dengan resep tertentu mudah jika Anda menyandikan kisi 3x3 sebagai string dan menggunakan kecocokan ekspresi reguler . Mempercepat tampilan adalah masalah yang berbeda, yang pada akhirnya akan saya bicarakan. Baca terus untuk informasi lebih lanjut.

Langkah 1) Encode kisi sebagai String

Cukup berikan id karakter untuk setiap jenis sel dan gabungkan semuanya berdampingan dalam urutan ini:

123
456 => 123456789
789

Dan sebagai contoh yang lebih konkret, pertimbangkan resep tongkat, di mana W berarti kayu dan E adalah sel kosong (Anda bisa menggunakan arang kosong ''):

EEE
WEE => EEEWEEWEE
WEE

Langkah 2) Cocokkan Resep menggunakan Ekspresi Reguler (atau String. Berisi dengan sedikit pemrosesan pada data)

Melanjutkan dari contoh di atas, bahkan jika kita memindahkan formasi, masih ada pola dalam string (WEEW padded oleh E di kedua sisi):

EEW
EEW => EEWEEWEEE
EEE

Jadi, di mana pun Anda memindahkan tongkat, tetap akan cocok dengan ekspresi reguler berikut: /^E*WEEWE*$/

Ekspresi reguler juga memungkinkan Anda melakukan perilaku kondisional yang Anda sebutkan. Misalnya (resep dibuat-buat), jika Anda ingin beliung yang terbuat dari besi atau batu memberikan hasil yang sama, yaitu:

III    SSS
EWE or EWE
EWE    EWE

Anda dapat menggabungkan keduanya ke dalam ekspresi reguler: /^(III)|(SSS)EWEEWE$/

Membalik horisontal juga dapat ditambahkan dengan mudah (menggunakan operator | juga).

Sunting: Bagaimanapun, bagian regex tidak sepenuhnya diperlukan. Ini hanya salah satu cara untuk merangkum masalah dalam satu ekspresi Tapi untuk masalah lokasi variabel Anda bisa memangkas string grid dari setiap ruang padding (atau E dalam contoh ini) dan melakukan String.Contains (). Dan untuk masalah bahan berganda atau resep cermin, Anda bisa menangani semuanya sebagai resep ganda (yaitu terpisah) dengan hasil yang sama.

Langkah 3) Mempercepat Pencarian

Sedangkan untuk mengurangi pencarian, Anda perlu membuat beberapa struktur data untuk mengelompokkan resep bersama dan membantu pencarian. Memperlakukan kisi sebagai string juga memiliki beberapa keuntungan di sini :

  1. Anda bisa mendefinisikan "panjang" resep sebagai jarak antara karakter non-kosong pertama dan karakter non-kosong terakhir. Sederhana Trim().Length()akan memberi Anda informasi ini. Resep bisa dikelompokkan berdasarkan panjang dan disimpan dalam kamus.

    atau

    Definisi alternatif "panjang" dapat berupa jumlah karakter yang tidak kosong. Tidak ada yang berubah. Anda dapat mengelompokkan resep berdasarkan kriteria ini juga.

  2. Jika poin nomor 1 tidak cukup, resep juga dapat dikelompokkan berdasarkan jenis bahan pertama yang muncul dalam resep. Ini akan sesederhana melakukan Trim().CharAt(0)(dan menjaga Trim menghasilkan string kosong).

Jadi misalnya Anda akan menyimpan resep di:

Dictionary<int, Dictionary<char, List<string>>> _recipes;

Dan lakukan pencarian seperti:

// A string encode of your current grid configuration 
string grid;

// Get length and first char in our grid
string trim = grid.Trim();
int length = trim.Length();
char firstChar = length==0 ? ' ' : trim[0];

foreach(string recipe in _recipes[length][firstChar])
{
    // Check for a match with the recipe
    if(Regex.Match(grid, recipe))
    {
        // We found a matching recipe, do something with it
    }
}
David Gouveia
sumber
3
Ini ... sangat cerdas.
Raveline
18
Anda memiliki masalah dan Anda ingin menyelesaikannya menggunakan ekspresi reguler? Sekarang Anda memiliki 2 masalah :)
Kromster mengatakan mendukung Monica
2
@Krom, saya pikir Anda mungkin hanya bercanda, tetapi ada alasan di balik komentar itu? Menggunakan ekspresi reguler hanyalah cara ringkas (kotak pencocokan terhadap resep dengan satu baris kode) dan fleksibel (cocok dengan semua persyaratan masalah ini) cara untuk melakukan pencocokan pada set data (isi kisi). Saya tidak melihat ada kerugian yang signifikan dari pengguliran algoritma pencocokan Anda sendiri, dan menyederhanakan seluruh proses.
David Gouveia
2
@ David Gouveia, itu hanya ungkapan untuk orang-orang yang tidak terlalu nyaman dengan Regex. Jika mereka memutuskan untuk menyelesaikan masalah dengan regex, mereka sekarang memiliki dua masalah: (1) masalah aktual yang ingin mereka selesaikan (2) menulis pola regex untuk memecahkan masalah itu
iamserious
2
Kembali ke 'sekarang Anda memiliki dua masalah' - Regex akan memiliki masalah segera setelah Anda memiliki lebih banyak item daripada rentang ASCII yang dapat dicetak, kecuali prosesor regex Anda mendukung unicode dan Anda dapat menjamin bahwa kombinasi tertentu tidak akan melompati kompiler regex NFA naik. Anda bisa menggabungkan DFA Anda sendiri (sebenarnya cukup mudah) untuk mencocokkan pola; tetapi regex akan menjadi cara terbaik untuk pergi sambil membuat prototipe.
Jonathan Dickinson
3

Saya tidak dapat memberi tahu Anda cara kerja Minecraft - meskipun saya yakin jika Anda melihat MCP (jika Anda memiliki salinan resmi Minecraft) Anda bisa mengetahuinya.

Saya akan menerapkan ini sebagai berikut:

  1. Memiliki beberapa kamus / hashmap berbasis disk ( B + Tree / SQL-Light ) - nilainya akan menjadi ID item dari hasil resep.
  2. Ketika seorang pengguna membuat sesuatu cukup temukan baris / kolom pertama dengan item SECEPATNYA ; menggabungkannya menjadi offset.
  3. Temukan baris / kolom terakhir dengan item, sekali lagi, secara mandiri.
  4. Hitung lebar dan tinggi dari item dan tambahkan ke tombol.
  5. Ulangi rentang kotak pembatas yang baru saja Anda hitung dan tambahkan ID setiap item (menggunakan yang biasa Anda lakukan for (y) { for (x) }).
  6. Cari kunci di basis data.

Jadi misalnya katakanlah kita memiliki dua bahan; X dan Y dan kosong menjadi *. Ambil resep berikut:

**X
**Y
**Y

Pertama kita mengerjakan kotak pembatas, menghasilkan (2,0)-(2,2). Karenanya kunci kita akan terlihat seperti ini [1][3](1 lebar, 3 tinggi). Selanjutnya kita mengulang setiap item dalam kotak pembatas dan menambahkan ID, dengan demikian kuncinya menjadi [1][3][X][Y][Y]- Anda kemudian mencari ini di kamus / DB Anda dan Anda akan mendapatkan hasil dari resep itu.

Untuk menjelaskan independensi pada langkah 2 dengan lebih jelas, pertimbangkan resep berikut:

*XX
XXX
XX*

Atas / kiri jelas pada 0,0 - namun item pertama yang biasanya Anda temui adalah 0,1 atau 1,0 (tergantung pada loop Anda). Namun jika menemukan kolom non-kosong pertama serta baris non-kosong pertama dan menggabungkan koordinat tersebut Anda akan mendapatkan 0,0 - prinsip yang sama berlaku untuk bagian bawah / kanan kotak pembatas.

Jonathan Dickinson
sumber
Repositori Bukkit tidak memiliki kode Minecraft, Anda memerlukan MCP (dan salinan Minecraft)
BlueRaja - Danny Pflughoeft
Bukankah ini kebalikan dari jawaban Anda yang lain?
David Eyk
@ Davidvidy (Ini adalah jawaban pertama saya) tidak terlalu, itu lebih tergantung pada struktur hashmap (apakah itu bigtable-like atau in-memory). Alasan saya menjawab lagi adalah karena saya khawatir tentang tabrakan hash yang mengarah pada kinerja yang buruk - setidaknya dalam hashmap dalam memori. Jawaban saya yang lain akan bekerja lebih baik untuk lebih banyak item dan struktur dalam memori - di mana ini akan bekerja lebih baik jika itu dalam SQL / etc.
Jonathan Dickinson