Generasi Bawah Tanah tanpa koridor dan dependensi ruang

Saya membuat game dengan dunia yang dihasilkan secara prosedural yang dibuat pada awal permainan, terdiri dari beberapa area yang diwakili oleh kisi-kisi (katakanlah, 8x8, 9x6, ukuran idealnya akan berubah-ubah). Area-area ini seharusnya terhubung satu sama lain melalui daftar ketergantungan.

Koneksi ada ketika setidaknya 3 spasi dari kisi itu terekspos di antara kedua area tersebut. Di sel tengah area koneksi 3 ruang adalah pintu antara area:

Saya sudah mencoba mencari cara untuk menghubungkan mereka, tetapi menjadi semakin kompleks semakin banyak area yang perlu Anda pertimbangkan pada saat yang sama.

Saya sudah mencoba beberapa prototipe kertas dan walaupun ini adalah proses yang sangat sederhana ketika melakukannya secara visual, saya belum menemukan serangkaian ekspresi matematika yang baik yang memungkinkan saya untuk menempatkan kamar dengan efisiensi yang sama dengan kode.

Berikut ini contoh "sederhana" yang sedang saya perjuangkan:

• Area 'a' perlu dihubungkan ke 'b' dan 'c'
• Area 'b' perlu dihubungkan ke 'a' dan 'd'
• Area 'c' perlu dihubungkan ke 'a' dan 'd'
• Area 'd' harus terhubung ke 'b' dan 'c'

Pertimbangkan, untuk kesederhanaan, kami menempatkan kamar berdasarkan urutan penampilan mereka di daftar (Saya sudah mencoba yang lain). Jadi saya mendekati ini sebagai algoritma Generasi Bawah Tanah prosedural prosedural Anda.

Kami menempatkan 'a' di mana saja di papan tulis, karena ini adalah area pertama. Selanjutnya, kita memilih dinding secara acak dan, karena tidak ada yang terhubung ke dinding itu, kita dapat menempatkan 'b' di sana:

Sekarang kita perlu menempatkan 'c', tetapi 'a' sudah ada di papan, dan memiliki dinding yang ditempati, jadi kami memutuskan untuk meletakkannya di dinding lain. Tetapi tidak setiap penempatan akan berhasil, karena 'd' akan muncul dan perlu dihubungkan ke 'b' dan 'c' juga:

Saya mencoba batasan yang mungkin bahwa 2 kamar yang memiliki set dependensi yang sama tidak boleh berada di dinding yang berlawanan, tetapi bahkan itu tidak menjamin kesuksesan:

Dan dalam kasus lain, di mana area memiliki ukuran yang berbeda, berada di dinding yang berlawanan dapat bekerja:

Juga, tidak mempertimbangkan dinding bekas adalah asumsi yang salah karena mengesampingkan solusi yang valid:

Saya sudah mencoba mencari penelitian tentang algoritma Generasi Prosedural lainnya atau yang serupa, seperti Optimal Rectangle Packing dan algoritma Layout Grafik, tetapi biasanya algoritma tersebut tidak memperhitungkan setiap kendala dari masalah ini dan sulit untuk dicampur bersama.

Saya memikirkan banyak pendekatan, termasuk menempatkan area dan mundur sampai penempatan yang cocok ditemukan, tetapi mereka tampaknya sangat tergantung pada coba-coba dan mahal dalam hal perhitungan. Tetapi, mengingat penelitian yang luas tentang dua masalah terakhir yang saya sebutkan, mungkin itu satu-satunya / solusi terbaik?

Saya hanya ingin melihat apakah seseorang memiliki masalah yang sama di masa lalu atau bersedia membantu saya mencari tahu dan memberi saya beberapa petunjuk tentang di mana saya harus memulai dengan algoritma. Atau, jika gagal, saya harus melihat ke dalam melonggarkan kendala yang telah saya tetapkan.

Ini masalah yang keren. Saya percaya ini bisa diselesaikan dengan perencanaan aksi di ruang penempatan kamar.

Tetapkan Negara dunia sebagai berikut:

//State:
//    A list of room states.
//    Room state:
//      - Does room exist?
//      - Where is room's location?
//      - What is the room's size?

Definisikan Kendala sebagai:

 // Constraint(<1>, <2>):
 //  - If room <1> and <2> exist, Room <1> is adjacent to Room <2>

Di mana "berdekatan" seperti yang Anda gambarkan (berbagi setidaknya 3 tetangga)

Sebuah Kendala dikatakan valid setiap kali dua kamar tidak berdekatan, dan kedua kamar ada.

Tetapkan suatu Negara untuk valid ketika:

// foreach Constraint:
//        The Constraint is "not invalidated".
// foreach Room:
//       The room does not intersect another room.

Definisikan Tindakan sebagai penempatan ruangan, dengan status saat ini. The Aksi ini berlaku setiap kali negara yang dihasilkan dari tindakan tersebut valid. Oleh karena itu, kami dapat membuat daftar tindakan untuk setiap negara:

// Returns a list of valid actions from the current state
function List<Action> GetValidActions(State current, List<Constraint> constraints):
    List<Action> actions = new List<Action>();
    // For each non-existent room..
    foreach Room room in current.Rooms:
        if(!room.Exists)
            // Try to put it at every possible location
            foreach Position position in Dungeon:
                 State next = current.PlaceRoom(room, position)
                 // If the next state is valid, we add that action to the list.
                 if(next.IsValid(constraints))
                     actions.Add(new Action(room, position));

Sekarang, yang tersisa adalah grafik , di mana States adalah node, dan Actions adalah tautan. Tujuannya adalah untuk menemukan Negara yang keduanya valid, dan semua kamar telah ditempatkan. Kami dapat menemukan penempatan yang valid dengan mencari melalui grafik dengan cara sewenang-wenang, mungkin menggunakan pencarian kedalaman-pertama. Pencarian akan terlihat seperti ini:

// Given a start state (with all rooms set to *not exist*), and a set of
// constraints, finds a valid end state where all the constraints are met,
// using a depth-first search.
// Notice that this gives you the power to pre-define the starting conditions
// of the search, to for instance define some key areas of your dungeon by hand.
function State GetFinalState(State start, List<Constraint> constraints)
    Stack<State> stateStack = new Stack<State>();
    State current = start;
    stateStack.push(start);
    while not stateStack.IsEmpty():
        current = stateStack.pop();
        // Consider a new state to expand from.
        if not current.checked:
            current.checked = true;
            // If the state meets all the constraints, we found a solution!
            if(current.IsValid(constraints) and current.AllRoomsExist()):
                return current;

            // Otherwise, get all the valid actions
            List<Action> actions = GetValidActions(current, constraints);

            // Add the resulting state to the stack.
            foreach Action action in actions:
                State next = current.PlaceRoom(action.room, action.position);
                stateStack.push(next);

    // If the stack is completely empty, there is no solution!
    return NO_SOLUTION;

Sekarang kualitas ruang bawah tanah yang dihasilkan akan tergantung pada urutan di mana kamar dan tindakan dipertimbangkan. Anda bisa mendapatkan hasil yang menarik dan berbeda mungkin dengan hanya secara acak mengubah tindakan yang Anda lakukan pada setiap tahap, sehingga melakukan perjalanan acak melalui grafik tindakan negara. Efisiensi pencarian akan sangat tergantung pada seberapa cepat Anda dapat menolak status yang tidak valid. Mungkin membantu untuk menghasilkan status yang valid dari kendala setiap kali Anda ingin menemukan tindakan yang valid.

Prioritas generasi Anda dalam konflik. Saat menghasilkan level, sasaran pertama Anda harus berupa web planar (non-tumpang tindih), titik-titik yang terhubung , terlepas dari skala. Kemudian lanjutkan untuk membuat kamar dari titik-titik dalam web itu. Membuat bentuk ruangan terlebih dahulu adalah kesalahan, secara umum. Buat konektivitas terlebih dahulu, dan kemudian lihat bentuk ruangan apa yang dapat ditampung di dalamnya.

Algoritma Umum

1. Buat grid lantai quantised dengan ukuran yang cukup untuk mendukung level Anda, menggunakan array 2D atau gambar.

2. Scatter menunjuk secara acak melintasi ruang lantai kosong ini. Anda dapat menggunakan pemeriksaan acak sederhana pada setiap ubin untuk melihat apakah mendapat poin, atau menggunakan distribusi standar / Gaussian untuk menyebarkan poin. Tetapkan nilai warna / angka unik untuk setiap titik. Ini adalah ID. (PS Jika setelah langkah ini Anda merasa perlu meningkatkan ruang Anda, tentu saja, lakukan.)

3. Untuk setiap titik yang dihasilkan tersebut, secara berurutan, secara bertahap menumbuhkan lingkaran atau persegi batas dengan langkah tunggal (biasanya laju 0,5-1,0 sel / piksel per langkah) dalam xdany . Anda dapat menumbuhkan semua batas secara paralel, semua dimulai dari ukuran nol pada langkah yang sama, atau Anda dapat mulai menumbuhkannya pada waktu yang berbeda dan dengan laju yang berbeda, memberikan bias pada ukuran yang mulai lebih awal (bayangkan pembibitan tumbuh, di mana beberapa mulai terlambat). Maksud saya "menumbuhkan" maksud saya adalah mengisi batas yang baru bertambah dengan warna / ID unik ke titik awal untuk batas tersebut. Sebuah metafora untuk ini adalah memegang spidol di bagian belakang selembar kertas, dan menonton noda tinta dengan warna berbeda tumbuh, sampai mereka bertemu.

4. Pada titik tertentu batas-batas suatu titik dan titik lain akan bertabrakan, selama langkah tumbuh. Ini adalah titik di mana Anda harus berhenti menumbuhkan batas untuk kedua titik - setidaknya dalam arti seragam yang dijelaskan dalam langkah 3.

5. Setelah Anda mengembangkan batas semua poin sejauh mungkin dan menghentikan semua proses pertumbuhan, Anda akan memiliki peta yang sebagian besar harus diisi, tetapi tidak sepenuhnya terisi. Sekarang Anda mungkin ingin mengemas ruang kosong itu, yang saya anggap putih, seolah-olah mewarnai selembar kertas.

Post-process Space-filling

Berbagai teknik dapat digunakan untuk mengisi ruang kosong / putih yang tersisa, per langkah 5:

• Memiliki satu tetangga, area yang sudah berwarna mengklaim ruang, dengan banjir mengisinya warna sehingga semuanya bergabung.
• Banjir dengan warna / angka / ID baru yang belum digunakan, sehingga membentuk area yang sama sekali baru.
• Pendekatan round robin sedemikian rupa sehingga setiap area tetangga yang sudah terisi "tumbuh" sedikit ke ruang kosong. Pikirkan hewan yang minum di sekitar lubang berair: mereka semua mendapatkan air.
• Jangan mengisi ruang kosong sepenuhnya, cukup menyeberanginya untuk menghubungkan area yang ada menggunakan jalan lurus.

Gangguan

Sebagai langkah terakhir untuk membuat hal-hal terlihat lebih organik, Anda bisa melakukan edge-perturbation dalam berbagai derajat, pada sel tepi area. Pastikan untuk tidak memblokir rute pergerakan penting.

Teori, demi kepentingan

Ini mirip dengan pendekatan yang diambil dalam Voronoi Diagram / Delaunay Triangulation , kecuali bahwa di atas Anda tidak secara eksplisit menciptakan tepi - sebagai gantinya, ketika berbatasan area bertabrakan, pertumbuhan berhenti. Anda akan melihat bahwa Diagram Voronoi mengisi ruang; ini karena mereka tidak menghentikan pertumbuhan hanya karena sentuhan, tetapi lebih pada tumpang tindih tingkat nominal. Anda bisa mencoba yang serupa.