Menggunakan L-Systems untuk menghasilkan kota secara prosedural

10

Saat ini saya sedang membuat aplikasi yang banyak berfokus pada konten yang dihasilkan secara prosedural. Sejauh ini, saya telah berhasil mengimplementasikan generasi prosedural medan dan bentuk peta menggunakan noise simplex. Saya sangat senang dengan tampilannya. Sekarang saya mencoba melakukan hal yang sama untuk kota. Saya hanya perlu membuat tata letak 2D jalan dan bangunan. Saya sudah melihatnya dan sepertinya kebanyakan orang menyarankan menggunakan L-Systems. Namun sepertinya aku tidak bisa membungkus kepalaku dengan mereka. Saya mendapatkan konsep, tetapi tidak implementasi ke dalam kode. Apakah ada yang punya contoh kode L-Systems untuk kota yang dihasilkan secara prosedural, atau saran tentang cara lain untuk menangani kota?

pasawaya
sumber
+1 Hore untuk L-Systems !
luser droog
Cara saya melakukan sesuatu yang serupa adalah dengan membuat kotak node yang mewakili persimpangan, kemudian secara acak menghubungkan node yang berdekatan. Membuat tata letak seperti labirin, tetapi jalan-jalan tidak semuanya terhubung, jadi sebenarnya menavigasi itu tidak mungkin.
user137
Kekerasan yang sering dikutip untuk sistem L yang menghasilkan kota adalah makalah Parish dan Müller: Pemodelan Prosedural Kota . Saya juga menemukan contoh implementasi yang sangat bagus . Ini adalah tempat yang baik untuk memulai, tetapi tergantung pada kebutuhan Anda yang tepat, Anda mungkin harus mengubah beberapa hal.
Anders Ryndel

Jawaban:

20

L-Systems , dari apa yang dapat saya katakan *, adalah seperangkat aturan substitusi seperti tata bahasa yang dapat Anda terapkan secara rekursif untuk mendapatkan hasil "organik" yang menarik.

Tanaman adalah tempat L-Systems sering digunakan, karena mereka menunjukkan banyak pertumbuhan rekursif (yaitu cabang terpecah menjadi lebih banyak cabang). Sebagai contoh sederhana, saya akan menunjukkan pohon "lollipop" yang dihasilkan menggunakan L-System:

variables : | o              (these are the things that will grow)
start  : o
         |                   (this is what we start with)
rules  : (o  o   o)         (these are the substitution rules that we apply
               \ /            one step at a time)

Jadi pada generasi 1, kita baru saja memulai:

o
|

Pada generasi 2, kami mengikuti setiap aturan dan mengganti bagian yang ada sesuai dengan aturan. Kami mengganti "bola" dengan "bola dua tongkat":

o   o
 \ /
  |

Generasi 3:

o o   o o
 \|   |/
   \ /
    |

Kami akan segera memiliki pohon besar yang cantik (jelek)!

Untuk melakukan ini dalam kode, Anda dapat melakukan ini secara rekursif (yaitu DFS), terus menerapkan aturan pada bagian yang sama sampai Anda mencapai akhir yang sewenang-wenang, atau Anda dapat melakukan ini secara iteratif (yaitu BFS) seperti yang telah kami lakukan dalam contoh ini , melakukan satu aturan "lulus" pada semua elemen dan mengulangi sejumlah langkah. Itu adalah:

Secara rekursif:

tree = start
grow(tree, start)

func grow(tree, part)
    if this part of the tree is big enough
        stop
    if part is 'o'
        replace part with 'o\/o'
        grow(tree, the left 'o')
        grow(tree, the right 'o')

Secara berulang:

tree = start
for a number of iterations
    for each part in tree
        if part is 'o':
            replace with 'o\/o'

Banyak penggunaan L-Systems melakukan langkah "tumbuh" menggunakan subdivisi - yaitu, bagian-bagian terus semakin kecil karena mereka "tumbuh", bagian-bagian yang lebih besar baru saja dibagi. Kalau tidak, sistem Anda yang tumbuh mungkin mulai tumpang tindih dengan sendirinya. Anda akan melihat contoh pohon lollipop saya, saya secara ajaib memastikan dua cabang tidak tumpang tindih di tengah dengan mengubah bentuk cabang baru. Mari kita lakukan contoh kota menggunakan subdivisi:

variables: block_vertical block_horizontal road_vertical road_horizontal
start: block_vertical
rules: (block_vertical  block_horizontal road_vertical block_horizontal)
       (block_horizontal  block_vertical road_horizontal block_vertical)

Ini akan masuk akal dalam satu menit.

Generasi 1:

+--------------------+
|                    |
|                    |
|                    |
|        V           |
|                    |
|                    |
|                    |
+--------------------+

Satu blok vertikal tunggal yang membosankan. (The V adalah singkatan dari vertikal.)

Generasi 2: kami mengganti blok vertikal dengan blok horisontal dengan jalan vertikal di tengah

+--------------------+
|       r            |
|       r            |
|       r            |
|   H   r      H     |
|       r            |
|       r            |
|       r            |
+--------------------+

R berarti jalan! Saya sudah membagi spasi secara acak, kami tidak ingin bagian biasa membosankan di PCG.

Generasi 3: kami mengganti blok horizontal dengan blok vertikal yang dipisah dengan jalan horizontal. Jalan yang ada tetap; tidak ada aturan untuk mereka.

+--------------------+
|   V   r            |
|       r            |
|rrrrrrrr            |
|       r      V     |
|   V   r            |
|       rrrrrrrrrrrrr|
|       r      V     |
+--------------------+

Perhatikan bagaimana jalan terhubung satu sama lain, yang bagus. Ulangi ini cukup kali dan Anda akan berakhir dengan sesuatu seperti ini (secara terang-terangan merobek jawaban terkait ):

masukkan deskripsi gambar di sini

Perhatikan bahwa ada banyak detail yang belum saya bahas, dan bahwa hasil ini terlihat "jelas" dihasilkan - kota-kota nyata terlihat agak berbeda. Itulah yang membuat PCG menyenangkan / sulit. Ada hal-hal tak berujung yang dapat Anda lakukan untuk mengubah dan meningkatkan hasil Anda, tetapi karena tidak terkait dengan L-Systems, saya akan meninggalkan jawaban ini di sini; Semoga ini bisa membantu Anda memulai.

* - Saya belum mempelajari L-Systems secara formal, walaupun saya telah menemukan tipe spesifik seperti tata bahasa dan vegetasi PCG; tolong perbaiki saya jika saya salah definisi atau konsep

congusbongus
sumber
1

@congusbongus jawabannya bagus, izinkan saya menambahkan beberapa hal.

Blok perlu dipisah menjadi area bangunan sesuai dengan semua jalan yang berbatasan dengan mereka. Ketika Anda memiliki jalan di sekitar, pola keseluruhan adalah sebuah cincin. Lihat tautan ini misalnya: http://oldurbanist.blogspot.fr/2012/01/city-blocks-spaces-in-between.html

(Tergantung pada kerapatan, mungkin tidak ada ruang di pusat cincin, lihat kowloon).

Setelah Anda selesai membuat blok, Anda harus membuat bangunan. Mereka agak rumit dan membutuhkan generasi dua lulus. Mereka sebagian saling tergantung: generator Anda seharusnya tidak membuat jendela di depan dinding samping bangunan berikutnya.

Dan untuk menambah kehidupan, Anda mungkin ingin mempengaruhi generasi dengan lingkungan seperti medan atau peta ekonomi: Jalan (kecuali di San Francisco) cenderung berputar di sekitar perbukitan besar, bukannya lurus dan jenis rumah sangat berat. dipengaruhi oleh bagian kota tempat mereka berada.

Selamat bersenang-senang.

Lionel Barret
sumber