Ruang Generasi dan Ruang Peluang

Dalam tutorial ini, saya akan berbicara tentang dua istilah yang saya gunakan untuk menggambarkan generator prosedural: ruang generatif dan ruang kemungkinan . Kami akan mendefinisikan dua istilah ini dan kemudian mempertimbangkan contoh-contoh interaktif untuk memahami perbedaan di antara mereka. Istilah-istilah ini sangat berguna untuk menggambarkan generator prosedural dan untuk memahami perbedaan antara dua generator. Ayo mulai!


Bayangkan sebuah buku besar yang menyediakan tangkapan layar dari setiap dunia Minecraft individu. Setiap tangkapan layar ditandai dengan seed acak , angka unik yang bisa Anda masukkan ke Minecraft dan hasilkan dunia ini. Halaman pertama menunjukkan dunia yang dihasilkan dari seed = 0, halaman berikutnya menunjukkan dunia dari seed = 1, dan seterusnya. Secara umum, generator dunia Minecraft berisi 2 ⁶⁴ nilai penghasil acak, dan ini adalah angka yang sangat besar: permainan dapat menghasilkan 18 446 744 073 709 551 616 dunia. Setiap kali Anda mengklik "Dunia Baru", dunia dibuat berdasarkan salah satu dari benih ini. Angka 2 ⁶⁴ adalah ukuran ruang generasi Minecraft, banyak hal yang bisa dihasilkan gim.


Sekarang bayangkan bahwa dunia Minecraft hanya terdiri dari rumput biasa, yang menyebar tanpa henti ke segala arah. Di bawahnya tidak ada gua, tidak ada batu, tidak ada pohon dan bukit, tidak ada binatang. Hanya satu lapis ubin rumput. Selain menjadi sangat membosankan, dunia seperti itu tidak akan pernah dihasilkan di Minecraft (kecuali modding digunakan). Kita dapat membayangkannya, menggambarkannya, bahkan membuka Minecraft dan membuatnya sendiri secara manual - tetapi Minecraft tidak dapat menghasilkannya. Bagaimana kita tahu itu? Anda dapat membuktikannya dengan berbagai cara, tetapi cara termudah untuk mengingat biomes Minecraft adalah di berbagai area seperti gurun atau hutan yang tersebar di seluruh dunia. Dalam contoh kita dengan dunia rumput, mereka bukan, oleh karena itu, kita tahu bahwa itu tidak dapat dibuat dengan generator standar.

Dunia rumput adalah dalam apa yang kita sebut Ruang Peluang Minecraft Worlds - himpunan semua dunia Minecraft yang dapat kita bayangkan, bayangkan, atau gambarkan. Tetapi dunia rumput tidak ada dalam ruang generasi Minecraft, karena itu tidak dapat dibuat oleh generator prosedural dari permainan. Kita dapat membayangkan dunia Minecraft dengan replika Persepolis yang tepat, atau dunia dalam bentuk patung batu Anda sambil duduk dan membaca artikel ini - semua ini adalah dunia Minecraft yang mungkin , tetapi mereka tidak akan dihasilkan oleh permainan.


Diagram yang ditunjukkan di atas memberi kita gambaran tentang bagaimana semua itu terlihat. Segala sesuatu yang ada di ruang generasi Minecraft juga harus ada dalam ruang kemungkinannya, karena jika Minecraft dapat menghasilkan sesuatu, maka harus dimungkinkan untuk membuatnya di Minecraft! Tetapi tidak semua ruang kemungkinan ada di ruang generasi, termasuk contoh kita dengan dunia yang terdiri dari rumput. Tetapi skalanya tidak dihormati dalam skema ini. Bahkan, ruang Minecraft kemungkinan jauh, jauh lebih besar daripada ruang generasi.

Untuk memahami seberapa besar itu, mari kita hitung ukuran satu dunia Minecraft. Volume adalah lebar dikalikan dengan tinggi, dikalikan dengan kedalaman. Secara default, dunia Minecraft adalah 256 ubin, dan mereka mulai terpecah menjadi sekitar 30.000.000 ubin di semua arah dari titik awal, yaitu, perkiraan volume dunia adalah:

256 x 60 000 000 x 60 000 000 = 921 600 000 000 000 000

Masing-masing blok ini dapat berupa elemen apa saja: batu, rumput, air, udara. Untuk penilaian kami, kami akan bermurah hati dan hanya menggunakan "blok dunia", yang, menurut wiki Minecraft, ada 64 jenis . Ini berarti bahwa setiap blok di dunia Minecraft memiliki 64 kemungkinan status. Rumus untuk menghitung jumlah dunia yang mungkin adalah sama dengan jumlah opsi negara untuk setiap blok dinaikkan ke kekuatan jumlah blok:

64 921 600 000 000 000 000 Minecraft

Jumlah ini sangat besar sehingga saya tidak dapat menemukan kalkulator di Internet yang dapat menghitungnya.


Untuk masuk lebih jauh ke dalam ruang generasi dan kemungkinan, kita membutuhkan contoh yang bisa kita masukkan ke dalam kepala kita dengan lebih baik. Oleh karena itu, di sisa tutorial, kita akan melihat level-level permainan platform 2D untuk game seperti Super Mario Bros. atau Spelunky . Kami akan melihat beberapa generator level untuk platformer 2D. Dalam artikel asli, semuanya interaktif, sehingga Anda dapat menghasilkan level Anda sendiri. Dalam proses mempelajari mereka, kami akan mengajukan pertanyaan tentang ruang generasi mereka. Semua contoh tersedia di GitHub kami sebagai sketsa sumber terbuka yang ditulis dalam Pemrosesan .

Dalam proses belajar, saya akan mengajukan pertanyaan dengan berani, misalnya: berapa ukuran ruang peluang untuk tingkat platforming ini? Anda dapat melewati mereka dengan aman jika Anda hanya ingin membaca artikel dan bermain dengan contoh. Saya juga terkadang menambahkan kiat untuk membantu menjawab pertanyaan, misalnya:

Petunjuk: level memiliki lebar 40 ubin dan tinggi 10 ubin, dan setiap ubin bisa menjadi salah satu dari tiga elemen: kekosongan, tanah, atau blok bonus.

Anda dapat menjeda saat diminta dan tidak menggulir ke bawah halaman jika Anda tidak ingin membaca jawaban yang sudah selesai. Jadi mari kita lihat generator pertama kami.

Algoritma 1: keacakan

Generator tingkat pertama kami sangat sederhana - benar-benar acak. Setiap kartu memiliki ubin mulai kiri dan ubin keluar kanan. Semua petak peta lainnya memiliki peluang 33% kosong, 33% sibuk, dan 33% menjadi blok bonus.


Anda mungkin memperhatikan bahwa ini bukan generator level yang sangat bagus. Bahkan, sebagian besar level ini bahkan tidak mungkin dimainkan, belum lagi minat mereka. Hasilkan beberapa level lagi dan pikirkan pertanyaannya: ukuran apa yang dimiliki ruang generasi generator semacam itu dibandingkan dengan ruang kemungkinan?

Petunjuk: dapatkah Anda menemukan tingkat yang ada dalam ruang kemungkinan, tetapi tidak dalam ruang generasi? Bisakah Anda menghasilkan level yang tidak bisa dibuat oleh generator ini?

Jawaban yang benar adalah bahwa ruang generasi generator ini sama dengan ruang kemungkinan. Ubin apa pun di peta dapat mengambil nilai apa pun, sehingga tingkat apa pun yang dapat kita bayangkan ada di ruang generasi. Level paling menarik, paling menarik ada di ruang generasi ini, bahkan peta tempat SUPER MARIO IS AWESOME ditulis dalam blok bonus. Sayangnya, ruang generasi sangat besar sehingga menemukan tingkat yang baik sangat tidak mungkin. Seperti yang Anda lihat dengan mengklik generator, sebagian besar level hanyalah sampah.

Algoritma 2: menggambar bentuk acak

Algoritme kami berikutnya sedikit lebih rumit, dan itu menciptakan level yang lebih seperti apa yang bisa Anda terapkan dalam game. Mulai dari level kosong, ia memilih titik acak di suatu tempat, dan kemudian menggambar garis atau persegi blok bonus atau tanah. Dia melakukan operasi ini 20 kali, menciptakan beberapa bentuk yang ditarik secara acak di tingkat. Seperti sebelumnya, Anda dapat mengklik contoh di artikel asli untuk memulai lagi algoritma dan menghasilkan level baru.


Ini sudah mulai menyerupai level untuk platformer, kan? Saat menghasilkan level, bayangkan secara mental bagaimana Anda memainkannya (bermurah hati jika perlu - tambahkan kemampuan untuk melompati ganda, jika perlu, atau kemampuan untuk melompat di luar langit-langit peta).

Berapa banyak level yang perlu dihasilkan sebelum Anda menemukan setidaknya satu level yang bisa Anda lalui?

Jangan berjuang untuk akurasi absolut dalam penelusuran mental Anda, hanya membuat perkiraan kasar.

Ketika saya melakukan latihan ini dengan penonton, biasanya dibutuhkan sekitar 10 upaya untuk menemukan level rata-rata. Berapa yang kamu butuhkan? Ingat nomor ini, dan sekarang lihat variasi generator yang sama seperti yang ditunjukkan di bawah ini. Gensetnya sama dengan yang baru saja kita lihat, tetapi sekarang ia menarik pada level bukan 20, tetapi 10 angka. Sekarang hitung lagi: berapa level yang perlu Anda hasilkan sebelum Anda menemukan level yang bisa Anda lalui?


Mungkin Anda membutuhkan waktu lebih sedikit untuk menemukan level yang dapat dimainkan. Mari kita berhenti sejenak dan pikirkan perbedaan antara dua generator, yang hampir identik, kecuali untuk sedikit perbedaan dalam parameter. Generator mana yang memiliki ruang generasi lebih besar - generator dengan 20 angka, atau dengan 10?

Petunjuk: pikirkan tentang level yang dibuat oleh generator dengan 10 angka - dapatkah generator dengan 20 angka dapat membuatnya? Dan kemudian pikirkan contoh sebaliknya.

Jawaban yang benar adalah bahwa generator dengan 20 angka memiliki ruang generasi yang lebih besar; sebenarnya, ini berisi seluruh ruang generasi generator dengan 10 angka. Untuk menunjukkan ini, bayangkan setiap level dari generator dengan 10 angka. Generator kami dengan 20 angka dapat membuatnya dengan secara tidak sengaja menampilkan sepuluh angka yang sama, dan kemudian dengan tidak sengaja menggambarnya untuk kedua kalinya di atas satu sama lain. Namun, tidak ada level dengan dua puluh angka terpisah yang dapat ditarik menggunakan generator dengan 10 angka.

Ini berarti bahwa generator dengan 20 angka memiliki lebih banyak level, termasuk level yang menarik. Tetapi perlu diingat bahwa jauh lebih mudah untuk menemukan level yang dapat dimainkan dengan generator dengan 10 angka. Jika Anda harus memilih generator untuk gim video Anda, yang mana yang akan Anda gunakan? Tidak ada jawaban yang benar, tetapi ini adalah keputusan yang sangat penting, yang seringkali harus dilakukan ketika bekerja dengan generator prosedural. Satu generator dapat menghasilkan lebih banyak variabilitas dan memiliki lebih banyak kejutan, yang lainnya lebih dapat diandalkan dan kurang stres bagi pemain.

Algoritma 3: Level Fragmen

Algoritma ini didasarkan pada generator level yang digunakan dalam Spelunky; Anda dapat membaca lebih lanjut di sini . Generator level secara acak memilih sebuah fragmen dari level yang dibuat oleh seseorang (saya) dan memasukkannya ke dalam level. Kemudian ia memilih fragmen acak lain dari level dan memasukkannya berdampingan, dan seterusnya, hingga level selesai. Ini generatornya, latar belakangnya gelap sehingga batas fragmen terlihat jelas:


Berapa banyak waktu yang dibutuhkan untuk menghasilkan level yang dapat dimainkan? Anda akan menemukan bahwa hampir setiap level dapat dimainkan. Kami tahu persis apa yang ada di setiap fragmen, yaitu, kami dapat menjamin bahwa akan ada objek menarik di tingkat yang dapat Anda lompati dan rintangan yang perlu Anda hindari. Pada saat yang sama, ini lebih dinamis daripada level statis - kita tidak tahu fragmen mana yang akan muncul di dalamnya dan dalam urutan apa. Algoritma Spelunky bahkan lebih kaya dari ini, ia memperhitungkan pergerakan vertikal, dan variasi acak ditambahkan ke setiap fragmen. Darius Casemi menciptakan generator tingkat interaktif Spelunky yang mengagumkan, yang dapat ditemukan di sini .

Generator seperti itu adalah kompromi yang baik antara kejutan yang menyenangkan dan kemampuan untuk mengendalikan. Ketika generator membuat pilihan dari katalog elemen dan menghubungkannya bersama-sama (kadang-kadang sesuai dengan aturan khusus, seperti di Spelunky), kami menyebutnya generator berbasis tata bahasa . Grammar memungkinkan kita untuk memutuskan blok bangunan mana yang harus digunakan generator prosedural, tetapi tidak terlalu ketat tentang bagaimana menghubungkannya. Tetapi kontrol dan keamanan ini ada harganya. Lihatlah generatornya lagi, lalu pikirkan contoh-contoh sebelumnya. Seberapa sering generator tingkat seperti itu mengejutkan kita?

Awalnya, generator penuh kejutan, karena kami bertemu setiap fragmen untuk pertama kalinya. Tetapi jika Anda bermain lebih banyak, maka Anda dengan cepat mulai memperhatikan di mana satu berakhir dan fragmen lain dimulai. Bahkan jika ada ratusan kombinasi fragmen dalam generator ini, hanya dalam beberapa level Anda mulai merasa seolah-olah Anda melihat semuanya. Kesederhanaan dan kemudahan memahami tata bahasa fragmen sangat bagus untuk pengembang, tetapi bisa menjadi kelemahan dalam hal kesenangan bagi pemain.

Algoritma 4: Desain Manusia

Sebagai contoh terakhir, kami tidak akan mempertimbangkan algoritme, tetapi jenis proses kreatif yang sangat berbeda: karya orang-orang dalam desain level. Klik generator di artikel asli dan Anda akan mendapatkan salah satu dari dua level Super Mario Bros pertama. (lebih tepatnya, awal mereka).


Dimulai dengan kebetulan mutlak, kami berakhir dengan ini, salah satu contoh paling terkenal dari desain platformer 2D dalam sejarah. Tentu saja, ini bukan generator, tetapi dalam arti tertentu, level-level ini dapat dianggap sebagai generator yang hanya menghasilkan satu level berkualitas tinggi. Kompromi maksimum antara kontrol dan kualitas. Melihat tingkat ini, pikirkan tentang semua generator yang kami periksa hari ini dan pikirkan pertanyaan: yang mana dari generator ini mengandung tingkat terkenal ini di ruang generasi mereka? .

• Generasi acak
• 20 bentuk generasi
• 10 bentuk generasi
• Level Fragmen

Hanya generator pertama yang mampu menciptakan level seperti itu. Generator bentuk dapat membuat mereka jika kita meningkatkan jumlah bentuk yang mungkin untuk digambar, tetapi itu juga akan secara signifikan meningkatkan jumlah level buruk atau aneh. Generator level fragmen dapat melakukan ini jika kami memberinya kumpulan fragmen yang berbeda, tetapi apakah semua kombinasi fragmen lain dapat dimainkan?

Ini menunjukkan kepada kita betapa sulitnya membuat generator prosedural. Kami ingin menganggap generator kami sebagai konten permainan yang biasa, untuk membayangkan bagaimana pemain melewati level tertentu dan menikmatinya. Tetapi sebagai perancang generasi, kita harus memikirkan seluruh ruang generasi, dan bukan hanya tentang satu contoh darinya. Seberapa besar ruangnya? Seberapa kayakah kejutan itu? Seberapa sering itu menciptakan sesuatu yang membosankan atau buruk? Bisakah kita mendeteksi dan menyaring kasus-kasus ini, atau kita perlu mencari solusinya? Ini hanya beberapa masalah yang perlu Anda pertimbangkan saat membuat sesuatu untuk generasi.

Untuk meringkas

Hari ini kami belajar tentang konsep-konsep berikut:

Ruang generasi

Ruang generasi generator konten prosedural (misalnya, generator dunia Minecraft) adalah himpunan semua hasil yang dapat dihasilkannya. Jika kita mengubah algoritme atau menetapkan nilai yang berbeda untuk variabel, ruang generasi akan berubah.

Ruang peluang

Ruang kemungkinan untuk jenis konten tertentu (misalnya, dunia Minecraft) adalah sekumpulan semua contoh konten yang dapat kami sajikan atau gambarkan. Biasanya, tetapi tidak selalu, ini jauh lebih besar dari ruang generasi generator prosedural.

Lebih banyak tidak selalu lebih baik

Generator dengan ruang generasi besar biasanya memiliki konten yang lebih baik, konten yang lebih tak terduga, dan konten yang lebih beragam. Tetapi biasanya ia memiliki lebih banyak konten sampah, lebih banyak konten yang membosankan dan lebih banyak konten yang tidak pantas.

Generator dengan ruang pembangkitan yang lebih sedikit lebih mudah dikendalikan, lebih mudah diuji, dan lebih mudah dipahami. Tapi ini bisa membuatnya lebih mudah ditebak dan tidak terlalu mengejutkan.

Menemukan cara untuk menyeimbangkan kekuatan dan kelemahan dari dua hal yang bertentangan ini adalah seni menciptakan perangkat lunak untuk generasi!

Bacaan tambahan dan terima kasih

Ini menyimpulkan tutorial saya! Terima kasih sudah membaca.

Di antara bahan-bahan menarik tentang topik yang telah kami periksa, saya merekomendasikan yang berikut:

• Spelunky oleh Derek Yu adalah kisah yang hebat tentang bagaimana Spelunky diciptakan, termasuk diskusi tentang generator prosedural permainan.
• Tracery Tutorials, oleh Kate Compton - Pelajari cara menulis tata bahasa berbasis teks, cara yang bagus untuk berlatih berpikir tentang ruang generasi!
• Bab buku luar biasa dari Dr. Gillian Smith tentang kisaran ekspresif (yang akan kita bahas dalam tutorial mendatang).
• Dr. Smith juga memiliki banyak sumber daya gratis, seperti ceramah GDC yang bagus tentang pertukaran timbal balik dalam generasi prosedural.
• Dan akhirnya, jangan lupa bahwa semua generator dari artikel dapat ditemukan di sketsa Pemrosesan sumber terbuka (di sini ).