Bagaimana saya harus membangun struktur data untuk "labirin" yang dinamis dan tidak terbatas?

Saya sebenarnya tidak yakin bahwa "maze" adalah istilah yang benar. Pada dasarnya pengguna mulai dalam satu Roomyang memiliki 4 pintu (N, S, E, dan W). Mereka dapat pergi ke segala arah, dan setiap kamar berikutnya berisi ruangan lain dengan 1 hingga 4 pintu masuk yang menuju ke kamar lain.

"Labirin" seharusnya berukuran tidak terbatas, dan tumbuh saat Anda memindahkan kamar. Ada jumlah terbatas yang Roomstersedia, namun jumlah yang tersedia adalah dinamis dan dapat berubah.

Masalah saya adalah, saya tidak yakin dengan struktur data terbaik untuk jenis pola ini

Saya pertama kali berpikir tentang hanya menggunakan array [X] [X] Roomobjek, tapi saya lebih suka menghindari hal itu karena benda itu seharusnya tumbuh ke segala arah, dan hanya kamar yang "dikunjungi" yang harus dibangun.

Pikiran lain adalah membuat setiap Roomkelas berisi 4 Roomproperti yang ditautkan untuk N, S, E, dan W, dan hanya tautan ke sebelumnya Room, tetapi masalah dengan itu saya tidak tahu bagaimana mengidentifikasi apakah pengguna masuk ke ruangan yang memiliki kamar yang berdekatan sudah "dibangun"

Sebagai contoh,

--- --- ----------
| | | |
   Mulai 5 4
| | | |
--- --- --- ---
--- --- ---------- --- ---
| | | | | |
| 1 2 3
| | | | | |
--- --- --- --- ----------

Jika pengguna berpindah dari Mulai> 1> 2> 3> 4> 5, maka Room# 5 perlu tahu bahwa W berisi ruang awal, S adalah ruang # 2 dan dalam hal ini seharusnya tidak tersedia, dan N dapat berupa baru Roomatau tembok (tidak ada).

Mungkin saya perlu campuran array dan kamar terkait, atau mungkin saya hanya melihat ini dengan cara yang salah.

Apakah ada cara yang lebih baik untuk membangun struktur data untuk jenis "labirin" ini? Atau apakah saya berada di jalur yang benar dengan proses pemikiran saya saat ini, dan saya hanya kehilangan beberapa informasi?

(Jika Anda tertarik, proyek ini adalah game yang sangat mirip dengan Munchkin Quest )

Berikan setiap Koordinat Kamar (mulai akan (0,0)) dan simpan setiap Kamar yang dihasilkan dalam kamus / peta hash oleh koordinat.

Itu sepele untuk menentukan koordinat yang berdekatan untuk setiap Kamar, yang dapat Anda gunakan untuk memeriksa apakah Kamar sudah ada. Anda dapat memasukkan nilai nol untuk mewakili lokasi yang sudah ditentukan bahwa tidak ada Kamar. (atau jika itu tidak mungkin, saya tidak yakin atm, kamus terpisah / peta untuk koordinat yang tidak mengandung Kamar)

Dalam kebanyakan kasus, apa yang Anda gambarkan terdengar seperti grafik. Mengingat beberapa persyaratan Anda (aspek yang berkembang), saya mungkin akan memilih daftar adjacency sebagai implementasinya (opsi umum lainnya adalah matriks adjacency ).

Saya tidak yakin bahasa apa yang Anda gunakan, tetapi tutorial / penjelasan yang bagus dengan detail implementasi untuk grafik yang diimplementasikan dengan daftar adjacency di .NET ada di sini .

Beberapa pemikiran tentang implementasi (saya sudah memikirkan Carcassonne yang memiliki sejumlah aspek menantang lainnya untuk membangun matriks - itu bahkan pertanyaan wawancara yang pernah saya tanyakan).

Ada beberapa pertanyaan yang diajukan dari struktur ini:

1. apakah ada kamar di X, Y?
2. apakah ada kamar [N / S / E / W] dari lokasi kosong X, Y?

Masalah dengan daftar dan grafik sederhana

Kesulitan dengan daftar sederhana adalah bahwa seseorang harus berjalan struktur untuk menguji apakah sesuatu dapat ditempatkan di lokasi tertentu. Sistem membutuhkan cara untuk mengakses lokasi sewenang-wenang O (1).

Mempertimbangkan:

1 2 3 ? 4
5 . . * 6
7 8 9 A B

Untuk menemukan informasi lokasi yang mungkin '?', Ketika pada usia 3, seseorang harus berjalan jauh-jauh untuk sampai ke 4. Jawaban tautan dengan informasi tambahan tentang berapa banyak node yang dilompati (sehingga 3 akan dihubungkan ke 4 dengan info tambahan 'jump 1') masih memerlukan jalan kaki ketika menemukan kedekatan '*' dari 6 atau A.

Sederhana, besar, array

Ada sejumlah kamar yang tersedia

Jika ini bukan jumlah yang besar, buat saja array 2N x 2N dan tinggalkan di sana. Array 100 x 100 adalah 'hanya' 10.000 pointer dan 50 objek. Indeks langsung ke array.

Ini dapat dikurangi menjadi hanya NxN jika kegiatan di luar batas menggeser array sekitar untuk selalu berada dalam batasan. Misalnya, jika sebuah ruangan akan ditambahkan yang akan mengurangi array, minta grid untuk menggeser setiap elemen satu posisi sehingga tidak akan ada underflow lagi. Pada titik ini, ukuran dunia untuk 50 kamar akan menjadi 2.500 pointer dan 50 objek.

Array dan matriks yang jarang

Untuk membuat ini lebih optimal, lihat ke array jarang di mana sebagian besar elemen adalah 0 atau nol. Untuk dua dimensi, ini dikenal sebagai matriks jarang . Banyak bahasa pemrograman memiliki berbagai pustaka untuk bekerja dengan struktur ini. Jika perpustakaan membatasi ke bilangan bulat, orang bisa menggunakan bilangan bulat ini sebagai indeks ke dalam array kamar tetap.

Pendekatan pilihan saya adalah memiliki kamar sebagai struktur (pointer ke kamar yang berdekatan, dan koordinat) dan memiliki kamar juga pointer dari tabel hash yang di hash pada koordinat. Dalam situasi ini untuk menanyakan kamar apa [N / S / E / W] dari kamar nol, orang akan meminta tabel hash. Ini, kebetulan, adalah format 'DOK' untuk menyimpan matriks jarang.

Bagaimana dengan ini..

Berikan setiap sel tautan ke masing-masing tetangganya. Beri setiap sel semacam nama (yaitu "0/0", "-10/0" (Asumsikan Anda mulai dari 0,0)). Tambahkan HashSet dengan semua nama di dalamnya. Saat Anda mencoba untuk pindah ke sel lain, cukup periksa bahwa tetangga belum ada di HashSet.

Juga, jika Anda membuat celah ke kamar lain, apakah itu menyiratkan bahwa kamar itu ada? Jadi, Anda akan membuat tautan ke kamar kosong tanpa tautan ke kamar apa pun. Anda mungkin juga ingin memeriksa tetangga kamar baru. Jika ada, dan akan terbuka ke kamar baru Anda, tambahkan pintu ke kamar itu.

   Empty   
   (0,1)        

---    ---            ----------
|        |            |        |
    0,0       1,0        2,0       Empty
|        |            |        |   (3,0)
---    --- ---------- ---    ---
|        | |        | |        |
|   0,-1      1,-1       2,-1      Empty
|        | |        | |        |   (3,-1)
---    --- ---    --- ----------

   Empty     Empty   
  (0,-2)    (1,-2)

HashSet = {0 | 0, 1 | 0, 2 | 0, 3 | 0, 0 | 0, 1 | -1 ....} 1.0: W = 0,0 / Pintu; 1,0: N = 1,1 / Kosong; E = 2,0 / Pintu; S = 1, -1 / Dinding

Anda juga harus memastikan bahwa Anda memberikan setiap kamar baru setidaknya satu pintu (ke ruangan lain) yang tidak berdekatan sehingga labirin dapat tumbuh ke arah itu.

Apa yang Anda rancang terdengar sangat mirip grafik.

Ini sering direpresentasikan sebagai seperangkat keadaan Q , keadaan awal q ₀ ∈ Q , dan beberapa transisi Δ . Jadi, saya sarankan Anda menyimpannya seperti ini.

• Kumpulan Q : {s, 1, 2, 3, 5, 6}
• Keadaan awal q ₀ : s
• Peta hubungan transisi Δ : {s → 1, s → 5, 1 → 2, 2 → 3, 3 → 4, 4 → 5}

Sebagian besar bahasa yang masuk akal memiliki peta dan set.

Anda dapat mempertimbangkan daftar tertaut 4 arah ...

Saya pertama kali berpikir tentang hanya menggunakan array [X] [X] objek Kamar, tapi saya lebih baik menghindari itu karena benda itu seharusnya tumbuh ke segala arah, dan hanya kamar yang "dikunjungi" yang harus dibangun.

Anda masih dapat menggunakan [] [] untuk itu. Pertumbuhan dinamis mungkin lambat, terutama saat menambahkan di awal, tapi mungkin tidak terlalu buruk. Anda harus profil untuk memeriksa. Mencoba memanipulasi beberapa daftar atau peta yang terhubung mungkin sebenarnya lebih buruk, dan pada tingkat yang konstan daripada sesekali.

Anda hanya dapat membangun kamar yang dikunjungi dengan menerapkan evaluasi malas. Objek dapat berada di tempat yang berisi ruangan, dan tidak membangun ruangan itu sampai room()dipanggil. Maka itu hanya mengembalikan yang sama setiap kali setelah itu. Tidak sulit untuk dilakukan.

Saya belajar melakukan ini melalui buku "Membuat Game Petualangan Di Komputer Anda". Jika Anda ingin menggali melalui kode BASIC (buku itu setua itu) baca di sini:

http://www.atariarchives.org/adventure/chapter1.php

Untuk pintasan, yang mereka lakukan adalah memiliki array kamar, dengan elemen di setiap array menjadi pointer ke ruangan lain yang bisa Anda kunjungi, dengan 0 (saya akan menggunakan -1 hari ini) untuk menunjukkan bahwa Anda tidak bisa pergi ke sana. Misalnya, Anda akan membuat struktur ruang (atau kelas atau apa pun)

room {
 int north_dir;
 int south_dir;
 int west_dir;
 int east_dir;
 // All other variables and code you care about being attached to the rooms here
}

Maka Anda bisa memiliki susunan atau struktur daftar tertaut atau bagaimana pun Anda ingin mengelola kamar Anda. Untuk array-style (atau vektor C ++) saya akan menggunakan kode itu dan arah akan menahan indeks ruangan yang mereka tautkan; untuk daftar tertaut, Anda bisa menggunakan pointer ke kamar sebelah.

Seperti yang dikatakan orang lain, jika Anda perlu secara dinamis menghasilkan kamar baru ketika orang memasukinya, Anda juga bisa melakukannya.

Jangan mencoba dan menyelesaikan semua masalah dengan satu struktur.

Tentukan objek kamar Anda untuk menyimpan sesuatu tentang ruangan, bukan hubungannya dengan kamar lain. Kemudian array 1D, daftar dll dapat tumbuh sesuka Anda.

Struktur terpisah dapat menampung "reachability" - ruangan mana yang dapat diakses dari ruangan tempat saya berada. Kemudian putuskan apakah jangkauan transitif perlu perhitungan cepat atau tidak. Anda mungkin ingin perhitungan brute force dan cache.

Hindari pengoptimalan awal. Gunakan struktur yang sangat sederhana dan algoritma yang mudah dipahami bodoh kemudian optimalkan yang digunakan.