Get best of the week

Kiat untuk Menggunakan Algoritma Fungsi Runtuh Gelombang

gambar

Baru-baru ini, saya telah banyak bereksperimen dengan generasi berbasis kendala prosedural. Secara khusus, dengan algoritma Wave Function Collapse (WFC, wave function collapse). Saya bahkan menulis perpustakaan open source saya sendiri dan aset persatuan .

WFC adalah algoritma yang sangat fleksibel, terutama dengan perbaikan yang saya kembangkan. Tetapi pada saat yang sama, saya merasa kesulitan untuk membuat level praktis yang dapat diterapkan pada game komputer dengan bantuannya . Kesulitan utama adalah bahwa WFC tidak memiliki struktur global. Yang dia lakukan adalah membuat generasi output terlihat mirip dengan input lokal, misalnya, dengan melihat masing-masing persegi panjang kecil output.

Dalam artikel ini saya akan memberi tahu Anda apa yang saya pelajari dan apa yang dapat meningkatkan generator berdasarkan batasan ke tingkat yang baru.

Dasar


Sulit untuk menggunakan WFC jika Anda tidak tahu cara kerjanya. Ini adalah algoritma generasi prosedural berbasis kendala yang telah diberi banyak perhatian baru-baru ini. Faktanya, ini hampir tidak ada hubungannya dengan konsep fisika kuantum yang namanya dinamai.

WFC mudah dikonfigurasi - Anda hanya memberikan algoritma contoh kartu, setelah itu menghasilkan kartu baru yang terlihat seperti kartu asli karena penggunaan berulang fragmen kecilnya.

Ini memiliki dua jenis - dengan pengaturan tetangga atau dengan overlay elemen. Ini dapat dilakukan dalam 2D ​​atau 3D, dan bahkan pada kisi segi enam atau tidak ratakisi-kisi. Sebagian besar tips saya berlaku terlepas dari bagaimana Anda menggunakan algoritme.

Saya sarankan Anda bermain dengan demo ini untuk mendapatkan ide tentang algoritma, dan baca pengantar ini [ terjemahan di Habré] jika Anda tertarik pada detail teknis.

Desain Tileset


Algoritma WFC berbasis ubin. Dalam hal ini, kualitasnya tergantung pada ubin yang Anda transfer untuk bekerja. Saya bukan seorang seniman, jadi saya dapat sedikit membantu dalam menggambar tileset yang indah (meskipun Anda dapat melihat di sini ), tetapi tileset yang baik juga membutuhkan pengetahuan teknis.

Kubus berbaris


Marching cubes adalah algoritma yang memilih ubin mana yang akan diatur tergantung pada apakah setiap simpul ubin penuh atau kosong. Berikut adalah daftar ubin yang digunakan untuk 2D.


Jika Anda membuat ubin agar sudut hitam dan putih selalu cocok, maka garis merah akan selalu terhubung dengan benar.

Di sini kita tidak perlu memahami keseluruhan algoritme, tetapi harus dicatat bahwa gagasan mendesain ubin dengan mempertimbangkan hanya perilaku mereka di sudut adalah teknik yang sangat kuat. Ini digunakan di banyak tileset terbaik, karena memastikan ubin selalu terhubung dengan baik.

Teknik ini sangat kuat untuk WFC. Itu terjadi, karena jika Anda melewatkan beberapa ubin, WFC tidak masalah. Dia akan menghindari masalah ini dan tidak akan pernah membuat konfigurasi yang membutuhkan ubin yang hilang. Ini sangat nyaman untuk 3D, karena ada puluhan ubin potensial, dan beberapa dari mereka diperlukan hanya dalam situasi yang sangat sulit. Lihat bagian “Yayasan” di bawah, di mana saya menggunakan trik ini bahkan lebih luas.

Mengetahui pola ubin lain mungkin juga membantu , tetapi Marching Cubes adalah yang terbaik.

Ruangan-ruangan


Terkadang paling mudah untuk bekerja dengan tileset sederhana. Kombinasi 4 ubin (satu ubin kosong) dengan mudah menghasilkan kamar persegi.



Ukuran kamar dapat dengan mudah diubah dengan mengubah berat masing-masing ubin. Setelah menambahkan ubin pintu dan koridor, Anda dapat menciptakan keragaman yang menjadi ciri khas denah orang.

Dasar


Saat bekerja dengan WFC, menarik untuk bereksperimen dengan tileset. Jika Anda hanya meletakkan ubin, WFC berupaya untuk memanfaatkan ruang yang tersisa secara maksimal. Terkadang ini mengarah ke hasil yang sangat berbeda, seperti yang dapat dilihat pada gambar Maxim Gumin:


Kita dapat menggunakan perilaku ini untuk merangsang WFC untuk menghasilkan banyak struktur yang dapat dikenali.

Berikut adalah contoh kastil (terinspirasi oleh @greentecq ):


Di dalamnya, saya menggunakan tileset berikut:


Ubin ini memiliki properti penting - semua ubin di pangkalan memiliki lebar tidak kurang dari di atas. Ini berarti bahwa tidak mungkin untuk membangun ubin ini dengan cara yang tidak didukung. WFC segera menanggapi hal ini dan membuat bangunan dengan fondasi yang baik.

Pendekatan Pecahan Fraktal


Mempelajari topik merangsang perilaku tertentu dengan memilih tileset yang sesuai, saya menemukan bahwa jika tileset terdiri dari jalan lurus dan cabang, tetapi tanpa sudut, maka Anda bisa mendapatkan perkiraan yang baik dari pemisahan rekursif (tanpa bagian "rekursif"). Ini cukup bagus untuk level grid.

Ubin besar


Anda dapat menambahkan WFC untuk mendukung ubin yang beberapa kali lebih besar dari ubin biasa. Misalnya, ini didukung di addon Tessera saya .

Ubin besar dapat digunakan dengan berbagai cara. Karena mereka melampaui batas kisi, Anda dapat menggunakannya untuk menambahkan kurva yang lebih halus dan lebih lebar daripada yang biasanya mungkin terjadi saat memotret ke kisi. Mereka juga bagus untuk elemen dari sejumlah besar ubin, atau hanya untuk menutupi bahwa generasi didasarkan pada ubin.

Berikut ini contoh untuk belajar dari Oscar Stalberg dari game Bad North . Oscar menunjukkan bagaimana ia menggunakan ubin besar untuk menambahkan pantai yang melengkung dengan mulus, rumah-rumah besar, dan variabilitas tebing.


Keterbatasan


Pada intinya, WFC adalah algoritma berbasis kendala. Ini berarti bahwa ia berupaya menghasilkan level yang sesuai dengan serangkaian kriteria tertentu. Dalam WFC murni, hanya ada satu kriteria - bahwa levelnya terlihat secara lokal seperti input sampel. Di bawah, saya akan berbicara tentang peningkatan WFC untuk menambahkan jenis pembatasan baru.

Memperbaiki ubin


Sangat mudah untuk memperbaiki ubin individu sebelum menghasilkan level di WFC. Kemudian mereka berintegrasi mulus dengan level yang dihasilkan.


Sebelum generasi


After Generation

Teknik ini dapat digunakan dengan berbagai cara. Berikut ini beberapa ide:

  • - , WFC .
  • ,
  • / WFC



Batasan jalur (Path constraint) - ini adalah kontribusi saya sendiri untuk WFC. Ini adalah teknik yang sangat kuat, tetapi artikel lengkap kemungkinan besar akan membutuhkan artikel terpisah.

Pembatasan ini secara global memindai semua output yang dihasilkan, dan secara paksa menunjukkan bahwa jalan harus melewati antara ubin yang ditandai. Atau dengan kata lain, ini memberitahu subset ubin untuk membentuk satu komponen grafik . Karena sifat globalnya, ini melengkapi perilaku WFC biasa, yang hanya memperhitungkan ubin lokal.

Saya menemukan bahwa menambahkan batasan ini sangat memengaruhi penampilan level yang dihasilkan. Tanpa itu, WFC sering menghasilkan beberapa ruangan atau area yang terbagi yang terlihat tidak realistis dan tidak dibuat oleh manusia.





. .


Situasi lain di mana batasan jalur sesuai adalah ... menggambar jalur. Secara default, pembatasan jalur hanya memastikan bahwa ada rute antara ubin. Itu tidak menjamin bahwa jalan akan sesederhana mungkin. Karena itu, dalam kasus sungai dan jalan, ia sering menggambar sambungan berbentuk T di tempat-tempat opsional. Caranya adalah dengan hanya menghapus semua ubin dari T-sendi, atau memberi mereka bobot yang sangat rendah, sehingga mereka dipilih hanya jika benar-benar diperlukan.

Saya suka menggunakan ubin tetap untuk memperbaiki titik akhir jalan. Karena itu, pembatasan jalur diperlukan untuk memasukkan ubin yang membuat sisa jalur terhubung.


Jalur yang dihasilkan dengan memperbaiki keempat sudut sebagai titik akhir jalur

Jika Anda ingin bereksperimen dengan jalur, maka saya memiliki demo javascript kecil yang diletakkan di sini .

Perbedaan


Ubin Alternatif


Sangat mudah untuk menambahkan opsi ubin ke algoritma WFC. Cukup tambahkan ubin ke daftar ubin yang mungkin, membuatnya memiliki koneksi yang sama dengan ubin yang diganti. Atau dapat dilakukan pada tahap pasca-pemrosesan, seperti yang biasanya dilakukan pada gaya generasi prosedural lainnya.


Dua ubin dinding, salah satunya dengan jendela. Mereka benar-benar dipertukarkan dan hanya menambah variabilitas pada desain.

Variabilitas ubin berdasarkan level


Jika Anda berusaha keras untuk membuat desain ubin, Anda akan melihat bahwa keacakan WFC mulai membahayakannya. Ini menggunakan seluruh tileset, yaitu, Anda bisa mendapatkan tingkat dengan campuran lava, salju, dan gurun. Seringkali ini terlihat sangat tidak masuk akal.

Anda dapat memulihkan integritas dengan cara sederhana: tentukan terlebih dahulu bioma level mana yang akan dimiliki, lalu nonaktifkan semua ubin yang tidak cocok untuk bioma ini.

Bad North (lagi) adalah contoh yang bagus untuk ini. Di beberapa tingkat, batu sepenuhnya dilarang, di tempat lain ada banyak vegetasi, di reruntuhan ketiga dan kuburan ditambahkan. Ini memberi setiap level gaya unik tanpa perlu perubahan signifikan dalam gaya generasi.


Hanya sekitar 10% pulau yang memiliki elemen gua, terlihat di sudut kanan atas.

Variabilitas ubin di dalam peta


Mencampur ubin bisa lebih jauh.

Jika Anda menggunakan WFC untuk menghasilkan kartu besar, maka mulai terlihat sangat seragam. Ini adalah konsekuensi lain dari kenyataan bahwa algoritma ini adalah pemecah kendala lokal .

Solusi terbaik untuk masalah ini yang saya lihat di game Caves of Qud . Dalam cerita pengembang tentang generasi ( 1 , 2 ), mereka mengatakan bahwa mereka membagi peta menjadi area yang berbeda, dan kemudian memulai WFC dengan parameter terpisah untuk subset peta. Ini berarti bahwa pada peta mungkin ada area reruntuhan dan area kota di mana template dan ubin yang sama sekali berbeda digunakan.


Contoh dari Matematika untuk Pengembang Game: Pembuatan Peta Berbasis Ubin menggunakan Wave Function Collapse di 'Caves of Qud'

Kesimpulan


Algoritma WFC, seperti semua teknik generasi berbasis kendala, memiliki prinsip untuk berhati - hati dengan keinginan Anda . Mudah untuk menyesuaikan dan mendapatkan hasil yang terlihat cantik, tetapi bisa sangat sulit untuk menerapkan detail spesifik yang diperlukan untuk gim Anda.

Saya berharap teknik yang disajikan oleh saya akan membantu Anda menjinakkan monster ini, tetapi pada akhirnya, yang terbaik adalah membuat desain game berdasarkan kekuatan generasi prosedural, dan tidak mencoba memaksanya untuk menciptakan terlalu banyak untuk Anda.

Saya sarankan Anda bermain Bad North dan Caves of Qud . Kedua game adalah contoh yang bagus untuk menggunakan WFC dalam kondisi nyata, dan para pengembang telah memikirkan dengan baik penggunaan optimal dari algoritma dalam game mereka.

More articles:


All Articles