🎇 🆚 👨🏽‍🎤 Membuat generator puzzle prosedural 🧗🏿 🧖🏼 👩‍⚖️

Posting ini menjelaskan generator level untuk permainan puzzle Linjat saya. Posting dapat dibaca tanpa persiapan, tetapi lebih mudah untuk berasimilasi jika Anda bermain di beberapa level. Saya memposting kode sumber di github ; semua yang dibahas dalam artikel ini ada di file src/main.cc

Paket contoh pos:

Linjat adalah gim logika di mana Anda harus menutup semua angka dan poin dalam kotak dengan garis.
Teka-teki ini dihasilkan secara prosedural menggunakan kombinasi solver, generator, dan optimizer.
Solver mencoba memecahkan teka-teki dengan cara yang akan dilakukan seseorang, dan memberikan peringkat menarik kepada setiap teka-teki.
Generator puzzle dirancang sedemikian rupa sehingga memungkinkan untuk dengan mudah mengubah satu bagian dari puzzle (angka), sementara semua bagian lainnya (poin) diubah sehingga puzzle tetap dapat dipecahkan.
Pengoptimal puzzle berulang kali memecahkan level dan menghasilkan variasi baru dari yang paling menarik yang ditemukan saat ini.

Aturannya

Untuk memahami bagaimana generator level bekerja, Anda perlu, sayangnya, untuk memahami aturan permainan. Untungnya, mereka sangat sederhana. Teka-teki ini terdiri dari kisi yang berisi kotak, angka, dan titik kosong. Contoh:

Tujuan pemain adalah menggambar garis vertikal atau horizontal melalui masing-masing angka, dengan tunduk pada tiga syarat:

Garis melalui angka harus sama panjang dengan angka.
Garis tidak dapat berpotongan.
Semua poin harus ditutup dengan garis.

Contoh solusi:

Hore! Desain game sudah siap, UI diimplementasikan, dan sekarang satu-satunya yang tersisa adalah menemukan beberapa ratus teka-teki yang bagus. Dan untuk gim semacam itu, biasanya tidak masuk akal untuk mencoba membuat puzzle semacam itu secara manual. Ini adalah pekerjaan komputer.

Persyaratan

Apa yang membuat puzzle untuk game ini bagus? Saya cenderung percaya bahwa permainan puzzle dapat dibagi menjadi dua kategori. Ada gim di mana Anda menjelajahi ruang keadaan rumit dari awal hingga akhir (misalnya, Sokoban atau Rush Hour ), dan di mana mungkin tidak jelas status mana yang ada dalam gim tersebut. Dan ada permainan di mana semua negara diketahui dari awal, dan kami secara bertahap membuat ruang negara menggunakan proses menghilangkan yang tidak perlu (misalnya, Sudoku atau Picross ). Game saya pasti termasuk dalam kategori kedua.

Pemain memiliki persyaratan yang sangat berbeda untuk berbagai jenis teka-teki ini. Dalam kasus kedua, mereka berharap bahwa puzzle hanya dapat diselesaikan dengan deduksi, dan bahwa mereka tidak akan pernah perlu kembali / tebak / coba-coba ^[0] ^[1] .

Tidak cukup hanya untuk mengetahui apakah sebuah teka-teki hanya dapat diselesaikan dengan logika. Selain itu, kita perlu entah bagaimana memahami seberapa baik teka-teki yang dibuat. Kalau tidak, sebagian besar level akan hanya terak sepele. Dalam situasi yang ideal, prinsip ini juga dapat digunakan untuk membuat kurva kemajuan yang halus, sehingga saat pemain maju melalui permainan, levelnya secara bertahap menjadi lebih sulit.

Solver

Langkah pertama untuk memenuhi persyaratan ini adalah membuat pemecah permainan yang dioptimalkan untuk tujuan ini. Solver backtracking memungkinkan Anda untuk dengan cepat dan akurat menentukan apakah puzzle dapat dipecahkan; selain itu, dapat dimodifikasi untuk menentukan apakah solusinya unik. Tapi dia tidak bisa memberikan gambaran betapa rumitnya teka-teki itu, karena orang menyelesaikannya secara berbeda. Solver harus meniru perilaku manusia.

Bagaimana seseorang memecahkan teka-teki ini? Berikut adalah beberapa langkah nyata yang diajarkan oleh tutorial dalam game:

Jika suatu titik dapat dicapai hanya dari satu angka, maka untuk menutup suatu titik Anda perlu menggambar garis dari angka itu. Dalam contoh ini, poin hanya dapat dicapai dari ketiganya, tetapi tidak dari empat:

Dan ini mengarah pada situasi ini:
Jika garis tidak pas di satu arah, maka harus ditempatkan di yang lain. Pada contoh di atas, keempat tidak dapat lagi diposisikan secara vertikal, jadi kita tahu bahwa itu akan horisontal:
Jika diketahui bahwa garis panjang X harus dalam posisi tertentu (vertikal / horizontal) dan tidak ada ruang kosong yang cukup untuk menempatkan garis sel kosong X di kedua sisi, maka Anda perlu menutup beberapa kotak di tengah. Jika keempatnya tiga dalam contoh yang ditunjukkan di atas, maka kita tidak akan tahu apakah itu membentang sampai ke kanan atau kiri. Tapi kita akan tahu bahwa garis harus mencakup dua kotak tengah:

Alasan yang sama adalah dasar dari game ini. Pemain mencari cara untuk merentangkan satu garis kecil, dan kemudian memeriksa bidang lagi, karena itu dapat memberinya informasi untuk membuat kesimpulan logis lain. Membuat solver yang mengikuti aturan-aturan ini akan cukup untuk menentukan apakah seseorang dapat memecahkan puzzle tanpa kembali.

Namun, ini tidak memberi tahu kami apa pun tentang kompleksitas atau ketertarikan level. Selain solvabilitas, kita perlu mengukur kompleksitas.

Gagasan pertama yang jelas untuk fungsi peringkat: semakin banyak gerakan yang Anda butuhkan untuk menyelesaikan teka-teki, semakin sulit. Ini mungkin metrik yang baik di gim lain, tetapi saya, kemungkinan besar, lebih penting daripada jumlah gerakan yang diizinkan yang dimiliki pemain. Jika seorang pemain dapat membuat 10 kesimpulan logis, maka ia kemungkinan besar akan menemukan salah satu dari mereka dengan sangat cepat. Jika hanya ada satu gerakan yang benar, itu akan membutuhkan lebih banyak waktu.

Artinya, sebagai perkiraan pertama, kita membutuhkan pohon keputusan untuk menjadi dalam dan sempit: ada ketergantungan yang panjang dari gerakan dari awal ke akhir, dan pada setiap saat waktu hanya ada sejumlah kecil cara untuk naik ke atas rantai ^[2] .

Bagaimana kita menentukan lebar dan kedalaman pohon? Solusi tunggal untuk teka-teki dan evaluasi pohon yang dibuat tidak akan memberikan jawaban yang pasti. Urutan yang tepat di mana gerakan dilakukan mempengaruhi bentuk pohon. Kita perlu mempertimbangkan semua solusi yang mungkin dan lakukan dengan mereka sesuatu seperti optimasi untuk kasus terbaik dan terburuk. Saya akrab dengan teknik pencarian kasar grafik pencarian di permainan puzzle , tetapi untuk proyek ini saya ingin membuat pemecah satu arah, dan bukan pencarian yang lengkap. Karena fase optimasi, saya mencoba memastikan bahwa runtime dari solver diukur tidak dalam hitungan detik, tetapi dalam milidetik.

Saya memutuskan untuk tidak melakukannya. Sebagai gantinya, pemecah saya sebenarnya tidak membuat satu langkah pada satu waktu, tetapi memecahkan teka-teki berlapis-lapis: mengambil keadaan, ia menemukan semua langkah valid yang dapat dibuat. Kemudian ia menerapkan semua gerakan ini pada saat yang sama dan memulai yang baru dalam keadaan baru. Jumlah lapisan dan jumlah gerakan maksimum yang ditemukan pada satu lapisan kemudian digunakan sebagai nilai perkiraan kedalaman dan lebar pohon pencarian secara keseluruhan.

Berikut cara memecahkan salah satu teka-teki sulit dengan model ini. Garis putus-putus adalah garis yang direntangkan pada lapisan pemecah ini, garis padat adalah garis yang tidak berubah. Garis hijau adalah panjang yang benar, yang merah belum lengkap.

Masalah selanjutnya adalah bahwa semua gerakan yang dilakukan oleh pemain dibuat sama. Apa yang kami sebutkan di awal bagian ini hanyalah akal sehat. Berikut adalah contoh aturan pengurangan yang lebih kompleks, pencarian yang akan membutuhkan sedikit pemikiran. Pertimbangkan bidang berikut:

Poin-poin dalam C dan D hanya dapat dicakup oleh lima dan empat tengah (dan tidak satu angka pun dapat mencakup kedua poin pada saat yang sama). Ini berarti bahwa keempat di tengah harus mencakup satu titik dua, dan karena itu tidak dapat digunakan untuk menutupi A. Oleh karena itu, titik A harus menutup empat di sudut kiri bawah.

Jelas, akan bodoh untuk menganggap rantai penalaran ini sama dengan kesimpulan sederhana "titik ini hanya dapat dicapai dari angka ini." Apakah mungkin untuk memberikan bobot lebih pada aturan yang lebih kompleks ini dalam fungsi evaluasi? Sayangnya, dalam pemecah berbasis lapisan, ini tidak mungkin, karena tidak dijamin untuk menemukan solusi dengan biaya terendah. Ini bukan hanya masalah teoritis - dalam praktiknya sering terjadi bahwa bagian dari lapangan dapat diselesaikan baik dengan argumen tunggal yang kompleks, atau dengan rantai gerakan yang jauh lebih sederhana. Bahkan, pemecah berbasis lapisan menemukan jalur terpendek, dan bukan yang paling murah, dan ini tidak dapat tercermin dalam fungsi evaluasi.

Akibatnya, saya sampai pada keputusan ini: Saya mengubah solver sehingga setiap lapisan hanya terdiri dari satu jenis penalaran. Algoritme memintas aturan penalaran dalam urutan kompleksitas yang mendekati. Jika aturan menemukan beberapa gerakan, maka mereka diterapkan, dan iterasi berakhir, dan iterasi berikutnya memulai daftar dari awal.

Kemudian keputusan diberikan penilaian: setiap lapisan diberi biaya berdasarkan pada satu aturan yang digunakan di dalamnya. Ini masih tidak menjamin bahwa solusi akan menjadi yang paling murah, tetapi jika bobot dipilih dengan benar, algoritma setidaknya tidak akan menemukan solusi yang mahal jika ada yang murah.

Selain itu, ini sangat mirip dengan cara orang memecahkan teka-teki. Mereka pertama-tama mencoba menemukan solusi mudah, dan mulai secara aktif menggerakkan otak mereka hanya jika tidak ada gerakan sederhana.

Generator

Bagian sebelumnya menentukan apakah level tertentu baik atau buruk. Tapi ini saja tidak cukup, kita masih perlu entah bagaimana menghasilkan level sehingga pemecah dapat mengevaluasinya. Sangat tidak mungkin bahwa dunia yang dihasilkan secara acak akan terpecahkan, belum lagi menarik.

Gagasan utama (ini sama sekali tidak baru) adalah penggunaan alternatif dari solver dan generator. Mari kita mulai dengan sebuah teka-teki, yang mungkin tidak dapat dipecahkan: cukup tempatkan dua hingga lima angka dalam kuadrat acak sel:

Solver berfungsi hingga dapat berkembang lebih lanjut:

Kemudian generator menambahkan lebih banyak informasi ke puzzle dalam bentuk titik, setelah itu eksekusi solver berlanjut.

Dalam hal ini, titik yang ditambahkan ke pemecah tidak cukup untuk pengembangan lebih lanjut. Kemudian generator akan terus menambahkan poin baru sampai memuaskan pemecah:

Dan kemudian si pemecah melanjutkan pekerjaannya yang biasa:

Proses ini berlanjut baik sampai puzzle diselesaikan, atau sampai ada lebih banyak informasi yang tersisa untuk ditambahkan (misalnya, ketika setiap sel yang dapat dihubungi dari angka sudah mengandung titik).

Metode ini hanya berfungsi jika informasi baru yang ditambahkan tidak dapat membuat kesimpulan yang dibuat sebelumnya salah. Ini akan sulit dilakukan ketika menambahkan angka ke kotak ^[3] . Tetapi menambahkan poin baru ke bidang memiliki properti ini; setidaknya untuk aturan penalaran yang saya gunakan dalam program ini.

Di mana seharusnya algoritma menambahkan poin? Pada akhirnya, saya memutuskan untuk menambahkannya ke ruang kosong, yang dapat ditutup dalam keadaan awal dengan sebanyak mungkin garis, sehingga setiap titik berusaha memberikan informasi sesedikit mungkin. Saya tidak mencoba untuk secara khusus menempatkan titik di tempat di mana akan berguna untuk kemajuan dalam memecahkan teka-teki pada saat pemecah macet. Ini menciptakan efek yang sangat nyaman: sebagian besar poin di awal puzzle tampak sama sekali tidak berguna, yang membuat puzzle lebih sulit daripada yang sebenarnya. Jika semua ini banyak gerakan jelas yang bisa dilakukan oleh seorang pemain, tetapi untuk beberapa alasan tidak satu pun dari mereka tidak bekerja dengan baik. Hasilnya, ternyata generator puzzle itu berperilaku agak seperti babi.

Proses ini tidak selalu menciptakan solusi, tetapi cukup cepat (sekitar 50-100 milidetik), jadi untuk menghasilkan level, Anda cukup mengulanginya beberapa kali. Sayangnya, ia biasanya membuat teka-teki biasa-biasa saja. Sejak awal ada terlalu banyak gerakan yang jelas, lapangan mengisi dengan sangat cepat dan pohon keputusan ternyata agak dangkal.

Pengoptimal

Proses yang dijelaskan di atas membuat teka-teki biasa-biasa saja. Pada tahap terakhir, saya menggunakan level ini sebagai dasar untuk proses optimasi. Ini berfungsi sebagai berikut.

Pengoptimal membuat kumpulan yang berisi hingga 10 pilihan puzzle. Kolam diinisialisasi dengan puzzle acak baru yang dihasilkan. Pada setiap iterasi, optimizer memilih satu puzzle dari pool dan melakukan mutasinya.

Mutasi menghapus semua poin, dan kemudian sedikit mengubah angka (mis. Mengurangi / meningkatkan nilai angka yang dipilih secara acak atau memindahkan angka ke sel lain di dalam kisi). Anda dapat menerapkan beberapa mutasi ke bidang secara bersamaan. Kemudian kami menjalankan solver dalam mode generasi tingkat khusus yang dijelaskan di bagian sebelumnya. Dia menambahkan cukup banyak poin pada teka-teki itu sehingga menjadi bisa dipecahkan lagi.

Setelah itu, kita mulai solver lagi, kali ini dalam mode normal. Selama menjalankan ini, pemecah monitor a) kedalaman pohon keputusan, b) frekuensi kebutuhan untuk berbagai jenis aturan, c) lebar pohon keputusan pada berbagai titik waktu. Teka-teki dievaluasi berdasarkan kriteria yang dijelaskan di atas. Fungsi evaluasi lebih menyukai solusi yang dalam dan sempit, dan tingkat kompleksitas yang meningkat juga menambah bobot teka-teki di mana aturan penalaran yang lebih kompleks diperlukan.

Kemudian sebuah teka-teki baru ditambahkan ke kolam. Jika kolam berisi lebih dari 10 teka-teki, maka yang terburuk dibuang.

Proses ini diulang beberapa kali (sekitar 10.000-50000 iterasi membawa saya). Setelah itu, versi puzzle dengan nilai tertinggi disimpan ke basis data level puzzle. Begini bagaimana kemajuan puzzle terbaik dalam satu kali pengoptimalan:

Saya mencoba menggunakan cara lain untuk menyusun optimasi. Dalam satu versi, simulated annealing digunakan, yang lain adalah algoritma genetika dengan berbagai operasi cross-over. Tidak ada solusi yang dilakukan serta algoritma naif dengan kumpulan opsi yang kembali ke atas.

Solusi tunggal yang unik

Ketika sebuah puzzle memiliki solusi unik yang unik, muncul kesulitan yang menarik. Apakah mungkin untuk memungkinkan pemain untuk berasumsi bahwa ada satu solusi dan menarik kesimpulan berdasarkan ini? Apakah adil jika pembuat puzzle menyarankan agar pemain melakukannya?

Dalam sebuah posting di HackerNews, saya mengatakan bahwa ada empat opsi untuk mendekati situasi ini:

Nyatakan keunikan solusi sejak awal dan paksakan generator untuk membuat level yang memerlukan alasan seperti ini. Ini adalah keputusan yang buruk karena mempersulit pemahaman aturan. Dan biasanya ini adalah detail yang orang lupa.
Jangan menjamin keunikan suatu keputusan: berpotensi memiliki banyak keputusan dan membuat semuanya. Sebenarnya, ini tidak menyelesaikan masalah, tetapi mendorongnya.
Anggap saja ini adalah peristiwa yang sangat jarang, yang dalam praktiknya tidak penting. (Ini adalah solusi yang digunakan dalam implementasi awal.)
Ubah generator puzzle agar tidak menghasilkan teka-teki di mana pengetahuan tentang keunikan solusi akan membantu. (Mungkin solusi yang tepat, tetapi membutuhkan pekerjaan tambahan.)

Awalnya, saya memilih opsi yang terakhir, dan itu adalah kesalahan yang mengerikan. Ternyata saya hanya memperhitungkan satu cara di mana keunikan solusi menyebabkan kebocoran informasi, dan itu sebenarnya sangat jarang. Tetapi ada yang lain; salah satu dari mereka sebenarnya hadir di setiap level yang saya hasilkan dan sering kali mengarah pada fakta bahwa solusinya menjadi sepele. Oleh karena itu, pada Mei 2019, saya mengubah mode Keras dan Pakar menggunakan opsi ketiga.

Kasing yang paling menyebalkan adalah deuce dengan garis putus-putus di bidang ini:

Mengapa pemain yang licik dapat membuat kesimpulan seperti itu? Deuce dapat menutupi salah satu dari empat kotak tetangga. Tak satu pun dari mereka yang memiliki titik, sehingga mereka tidak harus ditutupi oleh garis. Dan kuadrat di bawah ini tidak memiliki overlay dengan angka lainnya. Jika ada solusi tunggal, maka ini harus menjadi kasus ketika nomor lainnya menutupi tiga kotak yang tersisa, dan keduanya menutup kotak di bawahnya.

Solusinya adalah menambahkan beberapa poin lagi ketika mengenali kasus-kasus tersebut:

Kasus umum lainnya adalah tanda hubung dengan garis putus-putus di bidang ini:

Kotak di sebelah kiri dan atas keduanya tidak berbeda. Tak satu pun dari mereka ada benarnya, dan tidak ada yang bisa dihubungi dari nomor lain. Setiap solusi yang mana deuce menutupi kuadrat atas akan memiliki solusi yang sesuai di mana ia menutup kuadrat kiri, dan sebaliknya. Jika ada solusi tunggal yang unik, maka ini tidak mungkin, dan deuce seharusnya sudah menutupi bagian bawah.

Saya memutuskan jenis kasus ini dengan cara "jika itu menyakitkan, maka jangan menyentuhnya." Solver menerapkan aturan ini pada tahap awal dalam daftar prioritas dan memberikan bobot negatif pada gerakan tersebut. Teka-teki dengan fitur ini biasanya dibuang oleh pengoptimal, dan beberapa yang tersisa dibuang pada tahap pemilihan level akhir untuk game yang diterbitkan.

Ini bukan daftar lengkap. Selama pengujian bermain dengan pencarian kesalahan yang disengaja, saya menemukan banyak aturan lain untuk solusi unik. Tetapi kebanyakan dari mereka tampak langka dan mereka cukup untuk menemukannya, sehingga mereka tidak terlalu menyederhanakan permainan. Jika seseorang memecahkan puzzle menggunakan alasan seperti itu, maka saya tidak akan menyalahkannya.

Kesimpulan

Awalnya, game ini dikembangkan sebagai percobaan dalam pembuatan teka-teki prosedural. Desain dan generator game berjalan beriringan, sehingga tekniknya sendiri sulit diterapkan langsung ke game lain.

Pertanyaan yang saya tidak punya jawaban: apakah investasi dari upaya-upaya semacam itu dalam generasi prosedural membenarkan dirinya sendiri? . , - . , .

, , . : .

Catatan

[0] , , . , , . Oh baiklah

[1] Solving Minesweeper and making it better .

[2] , / — , , . , , Rush Hour , , . , Rush Hour — , - .

[3] . , , . .

Membuat generator puzzle prosedural