Peta ruang bawah tanah rekursif yang diwakili oleh array 2d yang elastis

8

Saya datang dengan metode untuk menghasilkan peta ruang bawah tanah sederhana secara rekursif dengan mulai dengan satu ruangan dan secara rekursif menghubungkan kamar-kamar baru yang berdekatan secara acak ke sana.

Peta direpresentasikan sebagai array dua dimensi di mana setiap sel berisi nilai 0-15. 0 mewakili tidak ada ruang sementara setiap arah diwakili oleh utara = 1, timur = 2, selatan = 4, barat = 8.

Saya ingin memulai dengan satu ruangan non ([[0]]) dan kemudian memperluas array 2d sesuai kebutuhan agar sesuai dengan peta yang dihasilkan. Kesulitan yang saya hadapi dengan pohon seperti rekursi ini adalah bahwa jika array harus tidak tergeser untuk menambahkan baris dan kolom ke kiri dan atas peta, saya harus menyesuaikan posisi fungsi saat ini, baris dan kolom apa yang ada di . Ini membuatnya sehingga cabang-cabang yang terpisah tidak menyadari penyesuaian indeks array dari cabang-cabang lain, hanya fungsi anak-anak mereka yang akan tahu karena mereka memiliki posisi yang disesuaikan diteruskan kepada mereka sebagai argumen baris dan kolom mereka.

Apakah ada cara untuk melakukan ini? Saya mencoba menyimpan nilai offset baris dan kolom di luar rekursi, tetapi tidak berhasil karena suatu alasan.

software-engineering game-mechanics level-design
sumber

Jawaban:

5

Apakah ada alasan Anda harus menggunakan array 2D, atau apakah tabel hash atau jenis peta lainnya bisa digunakan? Kemudian indeks x, y hanya berlanjut ke ruang negatif, tetapi itu tidak masalah.

Jika Anda mengkhawatirkan kecepatan memori atau CPU, 1) Jangan, tabel hash sangat efisien untuk hal-hal seperti pasangan bilangan bulat padat, 2) Anda dapat membangun level dalam tabel hash dan kemudian mempostingnya menjadi array begitu Anda tahu ukuran akhir.


sumber
jadi fungsi hash akan menerima argumen x dan ay dan ini pada dasarnya akan dipetakan ke array asosiatif dengan kunci seperti 1x1, -1x3, dll?
Ya. Dalam C ++ saya hanya menggunakan std :: pair <int, int>; dalam Python, dikt dengan (x, y) tupel untuk kunci. Saya tidak yakin bahasa apa yang Anda gunakan.
2

Saya melakukan hal serupa, dengan Python. (Atau setidaknya bagian elastis).

Saya memiliki kamus (x, y) pemetaan tupel ke sel. Dalam kode semu: 

map = dictionary( (0,0) : cell at (0,0), (1,0) : cell at (1,0) ... (2, 2) : cell at (2,2)
getCell(x,y):
    return map[(x,y)]
    catch error if out of bounds:
         map[(x,y)] = new cell and return

Tabel hash akan sangat baik untuk hal semacam ini.

Bebek Komunis
sumber
1

Solusi upaya minimum adalah memilih ukuran maksimum (X dan Y) yang Anda ingin mencapai penjara bawah tanah, meletakkan titik awal Anda di tengah itu, dan jangan biarkan pertumbuhan di luar itu. Tidak perlu melakukan perubahan apa pun. Tergantung pada batas tertentu yang dapat diterima, tentu saja.

kekacauan
sumber
-1

Anda ingin menggunakan grafik daripada array 2D.

Setiap kamar akan menjadi simpul dalam grafik dan tahu kamar mana yang berdekatan dengannya:

Room {
    long x;
    long y;
    List adjacentRooms;
}

Dengan begitu Anda tidak perlu menentukan seberapa besar peta Anda bisa menjadi.

Koordinat x, y dapat digunakan sebagai kunci unik dalam hashmap untuk akses cepat ke setiap kamar. Menambahkan ruang baru hanya akan menambahkan entri ke daftar Kamar yang berdekatan di dekatnya.

Grafik juga bagus untuk algoritma pencarian jalur, jika Anda membutuhkannya.

Stephen
sumber
Ini akan berkinerja buruk dan membutuhkan lebih banyak pembukuan daripada tabel atau array hash. Tidak ada manfaat di kamar yang memiliki kunci hash X, Y, dan membentuk grafik terarah.
Bagaimana Anda mengakses kamar dengan cepat hanya dengan grafik yang diarahkan? Bagaimana Anda melakukan pencarian jalan dengan hanya kunci hash X, Y? Ini akan membutuhkan logika tambahan untuk menentukan kamar yang berdekatan. Kunci hash sebenarnya hanyalah pandangan lain dari dunia game. Saya setuju bahwa menangani grafik lebih banyak masalah, tetapi akan menguntungkan algoritma menggunakan grafik. Kinerja tergantung pada ukuran dunia game. Jadi ini harus ditiru. Terima kasih untuk down-vote. Bersulang!
Stephen
Tidak ada dalam pathfinding yang menghalangi penggunaan hash dari X, pasangan Y. Status penggantinya adalah status penggantinya, tidak masalah jika Anda mempertahankan grafik gila atau mencarinya di tabel hash, kecuali bahwa tabel hash lebih cepat dan menggunakan lebih sedikit memori.
Solusi kunci hash kurang abstrak. Seperti yang saya tulis sebelum pathfinder harus tahu kamar mana yang berdekatan satu sama lain, bagaimana menghitung jarak ke ruang target dll. Anda akan memasukkan pengetahuan tentang dunia game ke dalam algoritma pathfinding Anda. Jika pengaturan dunia game berubah, mis. Perpindahan dari kamar yang diagonal satu sama lain diizinkan atau dimensi ketiga ditambahkan, Anda perlu mengubah setiap algoritma yang mengakses dunia game. Grafik abstrak sejauh ini. Tidak ada yang gila tentang itu. Selalu ada kekurangan untuk setiap solusi.
Stephen
1
"Grafik abstrak sejauh ini." Begitu juga metode iterator, generator, coroutine, atau daftar-bangunan, dan mereka tidak memerlukan O (n) struktur mengasapi atau lebih banyak pembukuan build-time.