Bagaimana cara menghasilkan jaringan jalan kota?

Saya ingin membuat generator kota untuk sebuah game, tetapi saya menghadapi masalah di awal generasi: sistem jalan.

Karena ini adalah dunia abad pertengahan, saya tidak ingin rencana grid seperti banyak kota modern. Idealnya saya lebih suka generasi pseudo-acak jalan besar dan jalan-jalan yang lebih kecil, di mana mungkin untuk tersesat, tetapi dengan masih beberapa logika - bukan labirin lengkap.
Sesuatu yang akan terlihat seperti kota yang tumbuh secara alami.

Untuk membuatnya tetap sederhana, katakanlah kota saya akan berada di dataran yang datar dan stabil, tanpa masalah penyeberangan sungai atau bantuan. Saya bisa mencoba mengintegrasikannya ke solusi setelah.

Saya tidak memutuskan ukuran atau disposisi yang tepat untuk kota saya, jadi jika Anda memiliki solusi yang hanya akan bekerja dengan kota-kota dengan bentuk yang tepat (persegi, lingkaran, persegi panjang dll), saya akan mengambilnya.

Tempat yang baik untuk memulai dengan pembuatan kota prosedural adalah Pemodelan Kota menurut Paroki dan Muller . Makalah mereka menyajikan Sistem-L di mana aturan mengenai kepadatan populasi & pola jalan (kotak persegi panjang, radial & perubahan ketinggian minimum) digabungkan dan kemudian diperbaiki untuk mengakomodasi kendala lokal seperti front air & estetika jalan. Sementara hasil dari sistem ini mengesankan, telah dikritik sebagai hal yang tidak perlu rumit . Solusi alternatif Barrett disajikan kembali di blog dev Suku Cadang Rudzicz sebagai berikut:

• memelihara daftar jalan "yang diusulkan"
• mengevaluasinya dalam beberapa urutan
• jika dapat diterima (dengan atau tanpa sedikit modifikasi)
• menyimpan setiap jalan yang diterima sambil "mengusulkan" beberapa cabang lebih dari itu

Pendekatan ini menghilangkan sebagian besar simbol penulisan ulang housekeeping yang diwariskan di Parish dan Müller's L-System. Anda dapat melihat demo dari pendekatan ini di sini .

Manfaat dari pendekatan ini adalah bahwa itu adalah bentuk kota agnostik - Anda dapat menambahkan batasan garis besar sesuai kebutuhan, sehingga bentuk kota Anda dapat ditentukan oleh kebutuhan desain game Anda alih-alih algoritma. Tergantung pada ukuran kota Anda, ini mungkin cukup bagus. Berikut adalah hasil dari demo di atas dengan batas segmen 100: Tetapi jika Anda membutuhkan sesuatu yang besar, Anda mungkin mengalami masalah; inilah hasil dengan batas segmen 500:

Sebagian, Anda dapat menyesuaikan ini dengan mengubah aturan percabangan jalan, menghindari sudut 90 derajat, dll. Jika tata letak Anda masih terlalu teratur, inilah koreksi saya:

Ubah grid kota Anda menjadi grafik di mana setiap jalan adalah tepi & setiap persimpangan adalah sebuah simpul. Selanjutnya, gunakan algoritma apa pun yang Anda inginkan untuk mengubah grafik menjadi labirin . Inilah contoh terakhir yang diubah menjadi labirin:

Sekarang output memiliki masalah yang berlawanan, itu terlalu membingungkan. Tapi sekarang kita dapat menerapkan beberapa teknik dari Cara Rahasia Generator Penjara Bawah Tanah Jamis Buck . Pertama, tingkatkan sparseness dengan menghilangkan beberapa koridor jalan buntu. Selanjutnya, tingkatkan konektivitas dengan menambahkan jalan yang membuat loop (mis. Memperkenalkan siklus ke grafik). Inilah contoh hasil:

Catatan: dimungkinkan untuk mencapai hasil akhir yang sama langsung dari tahap tata letak berorientasi grid sebelumnya (sebelum menghasilkan labirin), dengan hanya menerapkan pemindahan tepi ke grid kota. Masalah dengan pendekatan itu adalah Anda harus memastikan menghapus tepi tidak mempartisi kota sehingga membuat bagian tidak terjangkau.

Jika Anda mencari rencana kota abad pertengahan / lama di Google, Anda akan menemukan banyak variasi yang berbeda, sebagian besar berdasarkan asal kota (mis. Penyelesaian acak vs. posisi militer terorganisir).

Saya berasumsi Anda sedang mencari pemukiman yang lebih alami / kacau.

Untuk ini saya akan mencoba pendekatan seperti ini:

• Mulailah dengan jalan utama dari satu ujung ke ujung yang lain (dan idealnya menghubungkan beberapa permukiman lain. Jika Anda mau, buat jalan ketiga sehingga Anda mendapatkan persimpangan untuk memulai pemukiman Anda.
• Tempatkan beberapa rumah di sepanjang jalan (di satu sisi saja).
• Sekarang perluas jalan itu di sepanjang rumah dan tambahkan tengara utama di sisi lain (biasanya sebuah gereja, tetapi ini juga bisa berupa pabrik atau sejenisnya). Ini akan menjadi pusat / pasar Anda.
• Sekarang pilih dua posisi di luar area dengan rumah-rumah dan buat jalan baru yang menutupi rumah-rumah.
• Opsional buat beberapa sekutu yang lebih kecil antara rumah yang menghubungkan jalan lama dan baru.
• Sekarang ulangi sampai Anda puas dengan "inti" Anda:
  • Tambahkan beberapa rumah lagi.
  • Tambahkan jalan lain yang melampirkannya.
  • Tambahkan lorong belakang yang menghubungkan jalan.
• Setelah Anda puas dengan itu, Anda sudah selesai. Jika itu seharusnya sebuah kota, kelilinginya dengan tembok dan ulangi langkah terakhir beberapa kali lagi, tambahkan rumah-rumah tambahan di luar tembok.

Pertama-tama, ada banyak cara untuk melakukan generasi prosedural dan tidak ada yang mudah sama sekali, saya akan membuat semacam pendekatan bagaimana Anda bisa membuatnya bekerja, terserah Anda mengambilnya, memodifikasi atau membuangnya.

Akan pseudo-code di JS karena lebih mudah dimengerti.

1º menentukan titik masuk, karena Anda ingin membangun kota abad pertengahan, kita akan mulai dengan sebuah persegi, jadi katakanlah kota Anda akan memiliki 300 unit kuadrat dan alun-alun akan berada di tengahnya (diwakili dengan tanda X).

       300
________________
|               |
|               |
|               | 300
|       X       |
|               |
|               |
|_______________|

const square = [ 150, 150 ];

2º sekarang kita akan jalan, akan ada jumlah acak dari mereka, mereka akan lurus dan akan mulai dari alun-alun tengah atau dari jalan lain

let avenues = [] // will contain start and end [[sx,sy],[ex,ey]]
const n_avenues = RANDOM(4, 8); // number of avenues
const n_av_from_square = RANDOM(0, avenues); // starting in the square

for av in av_from_square
  avenues.push(square, [RANDOM(0, 200) + 100, RANDOM(0, 200) + 100])
  // we want avenues to have, at least 100 units length, thats why we randomize just te last 200 units of the whole town size

Ini akan memberi Anda jalan utama persegi dan pasangan

       300
________________
|   \\          |
|    \\         |
|     \\        | 300
|       X=====  |
|               |
|               |
|_______________|

Sekarang kita harus mengatur jalan yang tidak dimulai di alun-alun, mereka akan memotong jalan lain

for av in (n_avenues - av_from_square){
  const av_to_intersect = avenues[RANDOM(0,avenues.length)];

  //check av_to... and get a perpendicular vector (explained bellow)
  av[0] = [ av_to_intersect[0][1], - av_to_intersect[0][0] ];
  av[1] = [ av_to_intersect[1][1], - av_to_intersect[1][0] ];

}

Untuk mendapatkan vektor tegak lurus Anda harus menukar x, y cords dan meniadakan y baru:

swiped == x: noswiped.y, y: -1 * (noswiped.x)

Saat ini Anda harus memiliki sesuatu yang mirip dengan ini, bukankah itu terlihat seperti kota? : P

       300
________________
|   \\  //      |
|    \\//  ||   |
|     \\   ||   | 300
|    //\X=====  |
|   //     ||   |
|          ||   |
|_______________|

3º sekarang Anda hanya perlu menghubungkan jalan dengan jalan-jalan pendek, juga, Anda dapat menelurkan kotak acak di sepanjang kota dan membuat yang sama seperti di atas untuk semuanya, atau hanya menelurkan jalan-jalan kecil dari beberapa kotak sekunder, terserah Anda.

Ingat, jalan terpendek Anda adalah, kekacauan kota terlihat seperti.