Bekerja pada pemrograman, grafik, dan suara di beberapa gim baru sudah berakhir - hanya level yang tersisa. Pekerjaan mudah dan menyenangkan, tetapi karena suatu alasan datang dengan susah payah. Mungkin efek kelelahan umum.
Berpikir bagaimana menyederhanakan hidupnya, ide generasi prosedural muncul di pikiran. Tentu saja, itu juga harus ditulis, tetapi seperti yang dikatakan dalam salah satu karya terkenal, "lebih baik kehilangan satu hari, kemudian terbang dalam lima menit."
Perhatian! Di bawah potongan banyak teks dan gif "gemuk".
Pendahuluan
Level akan tetap dipoles secara manual, sehingga tidak ada persyaratan khusus untuk memori, kecepatan, atau bahkan kualitas level yang dihasilkan.
Awalnya, saya merencanakan bahwa generator hanya melempar kamar dan pintu, dan semua penyempurnaan lebih lanjut (plot, pemandangan dan musuh) akan dilakukan dalam mode manual. Tetapi untuk sekarang, saya pikir generator dapat melakukan lebih banyak. Namun demikian, penyetelan manual masih akan tetap - perlu bahwa para pemain merasa bahwa setidaknya sedikit cinta diinvestasikan di tingkat.
Saya melihat basis pengetahuan saya di game dev, dan menulis tautan ke artikel tentang generasi prosedural dalam dokumen terpisah. Kebanyakan, tentu saja, tentang menghasilkan labirin klasik atau tentang menghasilkan medan (omong-omong, hasilnya sangat mengesankan), yang tidak cocok untuk penembak 3D. Tetapi beberapa di antaranya dekat dengan apa yang saya butuhkan (dengan tanda bintang saya catat yang tampaknya paling cocok untuk saya):
Saya memutuskan untuk memulai dengan dua yang terakhir - mereka baru saja diterapkan, dan memberikan hasil yang baik.
Struktur generator
Sebenarnya, saya tidak langsung datang ke struktur ini, tetapi dalam proses banyak refactoring dan penulisan ulang, tetapi saya segera menulisnya sehingga jelas apa yang sedang terjadi:
- Generasi geometri awal (untuk memilih dari - "BSP", atau tata letak ruangan).
- Membersihkan bagian-bagian sampah (bagian-bagian yang tidak bisa ada dalam game).
- Membangun koneksi.
- Pembersihan subgraph sampah (kelompok-kelompok bagian yang saling berhubungan, tetapi tidak ada koneksi dengan bagian-bagian yang tersisa).
- Pembersihan koneksi yang tidak perlu (membangun pohon spanning , tautan diberikan ke pohon spanning minimum , karena ada gambar di sana, tetapi untuk generator tidak perlu untuk minimum).
- Pengacakan koneksi adalah pemulihan beberapa koneksi jarak jauh kembali (untuk jenis yang lebih "manusia" tingkat), serta transformasi beberapa orang lain menjadi bagian antara bagian (yang menggabungkan beberapa bagian menjadi satu, bentuk yang lebih kompleks).
- Generasi ruang rahasia.
- Pembuatan “skenario” (di mana bagian awal dan akhir akan berada, dan jalur mana yang harus dilalui untuk mendapatkan dari awal ke final).
- Optimasi koneksi.
- Membuat pintu dan jendela.
- Pilihan tindakan yang akan dilakukan di bagian ini (tekan tombol, naikkan kunci atau temukan dinding rahasia).
Masih ada sekitar 12 poin, tetapi mereka belum selesai (ketika saya selesai, saya akan menulis posting terpisah tentang mereka).
Generasi Geometri Awal: "BSP"
Terjemahan ini diambil sebagai dasarnya. Saya tidak yakin seberapa banyak yang terjadi dalam algoritma ini dekat dengan BSP asli, jadi saya menulis "BSP" dengan tanda kutip.
Algoritma ini cukup sederhana. Awalnya, buat persegi panjang ukuran seluruh lapangan bermain:
Kemudian kami membaginya menjadi dua bagian secara acak - baik secara horizontal maupun vertikal. Di mana garis pemisahan akan terjadi, kami juga memilih secara acak:
Kami secara rekursif melakukan hal yang sama untuk persegi panjang baru:
Dan lagi dan lagi, sampai batas tertentu:
Kemudian di setiap persegi panjang kita memilih "kamar" - persegi panjang dengan ukuran yang sama dengan aslinya atau lebih kecil (tapi tidak kurang dari 3x3 - lebih banyak di bawah).
Kemudian kamar dihubungkan oleh koridor. Tetapi tidak masing-masing, tetapi sedikit rumit, karena mereka disimpan dalam struktur mirip "BSP" (lihat algoritma asli untuk detail lebih lanjut).
Koridor yang menghubungkan bagian ungu dan putih.
Dalam algoritma asli, kedua kamar dan koridor memiliki warna yang sama (yaitu setara), sehingga di sana koridor hanya ditarik di atas kamar. Dalam kasus saya, kamar asli harus dilestarikan, sehingga koridor ditarik seolah-olah "di belakang" kamar.
Selain itu, jika ruangan (pirus dalam gambar) melintasi koridor, maka harus membaginya menjadi dua bagian yang berbeda (oleh karena itu, koridor yang sama dapat digambar dengan warna berbeda):
Dan inilah hasilnya:
Kemudian mulailah fase menandai sel sampah:
Seperti yang sudah saya tulis, tidak ada sektor yang bisa lebih kecil dari 3x3 sel. Ini karena fakta bahwa sektor ini harus dikelilingi oleh dinding (setidaknya 1 sel di setiap sisi), dan harus memiliki setidaknya satu sel ruang bebas:
Oleh karena itu, semua sel yang tidak cocok dengan aturan ini diberi label. Tapi ambil saja dan Anda tidak bisa menghapusnya - begitu banyak koneksi hilang, dan levelnya sangat sedikit.
Alih-alih, untuk setiap sel berlabel, sektor yang dapat digabungnya dicari (mengamati aturan 3x3):
Jika sel masih tidak dapat dikaitkan dengan sektor apa pun, itu akan dihapus (tetapi tidak dalam kasus ini - semuanya baik-baik saja di sini).
Pada tahap terakhir, gambar yang indah ini di-vektor-kan, dan sektor-sektor yang digambar berubah menjadi poly-box - poligon-poligon di mana setiap tepinya benar-benar vertikal atau horizontal (mungkin ada nama yang lebih ilmiah):
Generasi geometri awal: tata ruang
Artikel lain diambil sebagai dasar. Algoritma ini agak lebih rumit dari yang sebelumnya, tetapi juga bukan ilmu roket.
Pertama, lapangan bermain diisi dengan nilai berhenti tertentu, dan kemudian area persegi panjang dibersihkan secara acak di atasnya:
Tahap pembersihan persegi panjang acak dilakukan beberapa kali (juga acak) beberapa kali, dan sebagai hasilnya, kontur eksternal tingkat diperoleh:
Di ruang bebas, titik pertumbuhan kamar tersebar secara acak (ukuran kamar minimum adalah 3x3):
Tahap pertama pertumbuhan ruangan dimulai - untuk setiap kamar sisi terbesar dipilih, yang masih bisa tumbuh, dan tumbuh 1 sel (jika ada beberapa sisi dengan panjang yang sama - acak). Kamar-kamar dipindahkan secara bergiliran sehingga tidak ada persimpangan.
Kemudian kamar dikonversi menjadi polybox:
Dan tahap kedua pertumbuhan dimulai - pada tahap ini, sisi dapat dibagi menjadi beberapa bagian. Berbeda dengan tahap pertama, itu tidak tumbuh satu sel pada satu waktu, tetapi segera berhenti maksimal - ini menghindari "tangga" di sendi kamar. Jika setelah melewati semua kamar masih ada sel kosong, siklus berulang.
Hasilnya adalah ruang yang terisi penuh:
Kemudian polybox diambil dalam bentuk raster, dan (seperti pada generator "BSP"), tahap menandai sel "sampah" dimulai:
Dan bergabung dengan mereka ke sektor yang ada:
Di sini tidak mungkin untuk melampirkan semua sel - sel ekstra dihapus.
Hasilnya dikonversi kembali ke polybox:
Membersihkan bagian sampah
Kadang-kadang bagian muncul di mana aturan 3x3 tidak dihormati:
Anda dapat mencoba "mengembalikan" bagian-bagian tersebut, tetapi saya pergi dengan cara yang lebih sederhana, dan hapus saja:
Membangun koneksi
Untuk setiap bagian, tetangganya dicari, dan di tempat kontak bagian tersebut, koneksi dibuat. Koneksi dibuat di kedua sisi - jika bagian A bersentuhan dengan bagian B, maka akan ada koneksi dari A ke B dan dari B ke A. Hasilnya adalah grafik dua arah.
Membersihkan subgraph sampah
Kadang-kadang, sebagai hasil pembersihan dari bagian sampah, kami tidak mendapatkan satu grafik, tetapi beberapa grafik independen, seperti dalam contoh ini:
Dalam hal ini, subgraph dipilih sebagai yang utama, "area" dari bagian yang maksimal, dan sisanya dihapus ("area" dalam tanda kutip, karena meskipun dimungkinkan untuk menghitung area sebenarnya dari kotak poli, saya menyederhanakan tugas, dan saya mempertimbangkan area kotak pembatas - ini salah, tetapi cocok untuk generator).
Menghapus senyawa berlebih
Jika ada bagian dari masing-masing sektor ke masing-masing yang terhubung, maka akan ada terlalu banyak pintu di tingkat itu, dan akan lebih kuat dirasakan bahwa ia dihasilkan. Karenanya, pada tahap ini, koneksi berlebih dihapus:
Untuk pengacakan yang lebih banyak, saya tidak menghasilkan spanning tree dalam jumlah minimum lintasan, tetapi saya menghapus satu sisi acak sekaligus (memilihnya secara acak dari semua kemungkinan pada langkah saat ini).
Meskipun, ketika saya menulis ini, muncul ide bahwa akan cukup acak untuk memilih sektor awal, dan menghapus tepi yang sudah lebih efisien.
Pengacakan koneksi
Selanjutnya, ilustrasi akan datang dari generasi lain, karena dalam yang sebelumnya ada kesalahan dalam generator, karena gambar lebih lanjut salah.
Tetapi tingkat di mana tidak ada satu koneksi berlebihan juga tidak terlihat sangat manusiawi, sehingga beberapa kekacauan diperkenalkan:
- Beberapa tepi yang dihapus dikembalikan.
- Dan beberapa berubah menjadi lorong.
Selanjutnya, bagian-bagian di mana bagian-bagian itu dibentuk bergabung menjadi satu:
Jika Anda melihat bahwa dalam ilustrasi ini koneksi yang dihapus pada langkah sebelumnya muncul kembali - sepertinya bagi Anda :). Ketika saya membaca teks itu, menurut saya juga demikian, tetapi setelah melihat dengan seksama pada ilustrasi sebelumnya, menjadi jelas bahwa semuanya baik-baik saja.
Generasi Ruang Rahasia
Sektor yang hanya memiliki satu koneksi dipilih pada grafik:
Jika ada beberapa sektor seperti itu, maka mereka semua berkumpul dalam sebuah array, dan diurutkan berdasarkan "area". Kemudian array ini terpotong secara acak (tetapi agar setidaknya satu elemen tetap di dalamnya). Sektor-sektor ini akan menjadi ruang rahasia:
Pembuatan Skrip
Pertama, sektor-sektor dengan jumlah minimum koneksi gratis (yaitu, yang lebih dekat ke "tepi" grafik) dipilih:
Dalam ilustrasi ini, satu sektor dipilih, tetapi jika ada lebih banyak, toh sektor akan dipilih (secara acak).
NB. Selama pengoreksian artikel, saya dapat menemukan situasi di mana suatu sektor dengan jumlah minimum koneksi gratis tidak hanya tidak berada di ujung tombak, tetapi memberikan skrip pada artikel tersebut akan mengarah ke tingkat yang tidak dapat dilewati. Bahkan, Anda dapat memilih sektor apa saja, tetapi hanya satu, setelah itu grafik tidak akan jatuh ke dalam beberapa subgraph.
Selanjutnya, pilih sektor yang terhubung ke sektor saat ini, dan yang hanya memiliki satu koneksi gratis. Mereka, dengan beberapa kemungkinan, akan digunakan untuk melanjutkan skrip. Misalnya, jika grafiknya sama seperti pada ilustrasi di bawah ini, maka sektor yang ditunjukkan oleh pertanyaan dapat dimasukkan dalam daftar.
Ruang rahasia ditandai dengan warna abu-abu, salib adalah koneksi yang seharusnya dihapus dalam grafik asli, dan sektor sumber merupakan nilai tambah.
NB. Selama pengoreksian artikel, bagi saya tampaknya kondisi untuk kehadiran hanya satu koneksi terlalu ketat, sama seperti pada langkah sebelumnya sudah cukup - sehingga setelah menghapus sektor ini, grafik tidak akan putus.
Kemudian, nomor skrip ditugaskan untuk daftar sektor ini (hanya nomor, pada tahap ini tidak berarti apa-apa), dan koneksi di perbatasan daftar sektor ini ditandai sebagai ditutup oleh skrip ini.
Dalam ilustrasi ini, skenario yang berbeda akan memiliki warna isian sektor yang berbeda. Mereka tidak ada hubungannya dengan warna perbatasan sektor ini (pada langkah selanjutnya akan diperbaiki, tetapi pada langkah ini lebih nyaman bagi saya).
Selanjutnya, sektor berikutnya dipilih, daftar dikompilasi, dan daftar ini ditandai dengan skenario baru:
Perhatikan titik-titik biru kecil di dalam kotak merah - beginilah cara pembuka skenario - yaitu: suatu tempat di dalam bagian dengan skrip merah akan ada kunci atau saklar yang akan membuka bagian ke sektor dengan skrip biru.
Ini berlanjut sampai tidak ada sektor bebas yang tersisa:
Sektor terbaru tidak diberi skrip, tetapi hanya pembuka skenario. Sektor ini akan menjadi sektor di mana pemain memulai permainan.
Untuk level ini:
- Pemain mulai di sektor awal, di suatu tempat di sana ia menemukan "pembuka botol" ke sektor kuning, pergi ke sana.
- Di sektor kuning, buka sektor biru, pergi ke sana.
- Di sektor biru terbuka hijau, pergi ke sana.
- Di sektor hijau terbuka ungu, pergi ke sana.
- Dalam warna ungu terbuka merah.
- Merah - biru.
- Di mana ia menemukan saklar level akhir.
Secara skematis, ini dapat ditunjukkan sebagai berikut:
"Pembuka" dapat berupa kunci atau saklar, atau sesuatu yang lain, misalnya, tugas untuk menghancurkan semua musuh di sektor apa pun (tapi saya tidak berencana bahwa dalam waktu dekat generator atau mesin akan mendukung ini).
Optimasi koneksi
Pada langkah ini, untuk setiap koneksi satu sisi dipilih (seperti yang Anda ingat, awalnya koneksi dihasilkan di kedua arah). Ini diperlukan untuk membuat level terlihat lebih “manual”, dan untuk menyederhanakan langkah selanjutnya (tetapi untuk tipe level yang lebih menarik, dalam waktu dekat saya berencana untuk mengambil langkah “deoptimisasi” beberapa koneksi) .
Membuat pintu dan jendela
Untuk setiap sektor, semua koneksinya dilihat (yang setelah langkah sebelumnya hanya melihat satu arah), dan pintu dan jendela ditempatkan pada setiap koneksi yang dilihat.
- Pertama, suatu titik dipilih di persimpangan, lebih disukai lebih dekat ke pusat.
- Kemudian pada titik ini pintu atau jendela ditempatkan (dan jika itu adalah koneksi ke ruang rahasia, maka dinding rahasia).
- Jika pintu ditempatkan, ukurannya bisa dari 1 hingga 3 sel (satu adalah pintu biasa, dua atau tiga adalah pintu kedap udara yang tebal, yang terbuka setelah menekan sakelar).
- Selanjutnya, koneksi dibagi menjadi dua bagian - bagian sebelum titik yang dipilih, dan bagian sesudahnya. Dan, jika ada ruang yang tersisa sebelum atau sesudah, fungsinya disebut secara rekursif.
Untuk membuat level terlihat lebih menarik, pada langkah yang berbeda ada kemungkinan yang berbeda untuk menempatkan pintu atau jendela:
- Pada langkah pertama, pintu selalu diletakkan, karena apa gunanya menghubungkan jika hanya ada windows di sana.
- Pada langkah kedua, dengan probabilitas yang lebih tinggi (75%), sebuah jendela ditempatkan dari pada sebuah pintu.
- Jika ada langkah ketiga (misalnya, koneksi panjang), maka jendela harus diletakkan di sana.
- Dalam hal langkah ke-4, pintu atau jendela ditempatkan dengan kemungkinan yang sama.
- Jika koneksi terlalu panjang, generator kembali ke langkah kedua.
Pemilihan tindakan
Meskipun ini tidak terkait dengan generasi, visualisasi berubah pada langkah ini - sekarang batas sektor dicat dengan warna skrip:
Sektor awal berwarna abu-abu muda, sektor akhir berwarna biru. Perhatikan juga bahwa alih-alih pintu di ruang rahasia (abu-abu gelap di sebelah kiri) sebuah tembok digambar - semuanya benar, ini adalah tembok rahasia.
Selanjutnya, pilih sektor di mana Anda dapat menempatkan kunci:
Mereka dipilih cukup sederhana:
- Jika ini adalah ruang rahasia, maka tidak ada "pembuka" di dalamnya, dan kuncinya tidak dapat ditempatkan di sana.
- Anda tidak dapat menempatkan kunci di sektor final juga, karena itu final.
- Selain itu, kuncinya tidak dapat membuka pintu ganda dan tripel - karena fitur engine, mereka hanya dapat dibuka menggunakan sakelar (tidak ada sektor seperti itu dalam ilustrasi di atas) .
Setelah itu, jumlah kunci pada level (dari nol hingga tiga) dipilih secara acak, dan kemudian, secara acak, dari daftar sektor yang tersedia, yang di dalamnya akan ada kunci dipilih.
Di sektor yang tersisa akan ada switch.