Apa algoritma yang baik untuk tata ruang kota prosedural berbasis fraktal?

19

Latar Belakang

Saya menjalankan server minecraft di mana saya akan merancang kota pemula dengan skala yang cukup besar. Saya memiliki serangkaian hal, seperti tanda peraturan dan kandang gerombolan, saya ingin menempatkan bangunan di sana. Kota itu sendiri akan sangat besar dan menyebar, lebih disukai hingga 1000 oleh 1000 blok dalam ukuran.

Bangunan itu sendiri akan memiliki jejak kaki kubus atau persegi panjang yang didasarkan pada kubus dasar tertentu, seperti semua kelipatan dari 3 blok. Jalan-jalan dan jarak antara bangunan akan lebih disukai 5-11 blok lebar, tergantung pada pentingnya jalan.

Ketika saya memulai rencana untuk kota, saya akan tahu persis seberapa besar saya ingin bangunan dan berapa banyak akan ada.

Masalah

Masalahnya adalah merancang tata letak kota. Tentunya dengan sesuatu skala seperti itu, dan saya datang dari latar belakang pemrograman daripada latar belakang perencana kota, cukup sulit untuk bahkan mulai membungkus kepala saya di sekitar masalah.

Masalahnya secara khusus adalah bahwa saya ingin kota terlihat sealami mungkin. Tentu saja ini akan cukup mudah dibangun di atas pola kisi sederhana, tetapi saya ingin menghindari kisi, atau apa pun yang terlihat seperti kisi, sebanyak mungkin.

Pertanyaan

Algoritme apa yang mungkin dapat saya kejar agar dapat membantu saya mendesainnya menggunakan kode? Saya berpikir bahwa itu akan terlihat paling alami jika saya menggunakan fraktal dalam beberapa cara, karena minecraft sudah menggunakan fraktal dalam generasi medannya, dan sebuah kota tampaknya tumbuh dalam pola fraktal secara alami.

Saya pikir itu mirip dalam beberapa hal dengan algoritma tetris playing, jadi jika ada yang punya solusi yang ada di arah itu maka itu akan membantu juga. Saya membayangkan sesuatu di mana saya dapat menentukan bentuk yang ingin saya gunakan, dan perangkat lunak kemudian beralih hingga menemukan solusi yang paling "optimal" untuk pemerataan bangunan. Apakah ada yang sudah ada untuk membantu saya memecahkan masalah ini menggunakan python, lebih disukai secara visual menggunakan pygame?

Secara alami ini juga memiliki implikasi yang menarik untuk generasi kota secara umum dalam desain game, jadi saya sangat senang melihat apa solusi terbaiknya.

sunting Untuk lebih jelas, saya hanya mencari tata letak pada titik ini karena bangunan akan dirancang dan dibangun dalam gim.

python terrain-rendering pygame minecraft-modding fractal Ken
sumber
3
Minecraft menggunakan fraktal? Saya mendapat kesan itu hanya menggunakan fungsi noise terus menerus (Perlin atau Simplex, saya percaya).
Martin Sojka
Kebisingan @Martin Sojka Perlin sebenarnya fraktal, jadi di sana.
Nevermind
1
@Nevermind: Karakteristik yang menentukan dari fraktal adalah kemiripan diri : Jika Anda memilih bagian dari itu dan skala ke ukuran aslinya, itu akan "mirip" (memiliki struktur yang sama). Secara khusus, spektrum frekuensi dari sinyal fraktal tidak sama dengan skala. Jika Anda melakukannya dengan noise Perlin, Anda hanya akan mendapatkan area peningkatan noise Perlin; spektrum frekuensi akan bergeser juga.
Martin Sojka
@Nevermind Perlin noise sebenarnya bukan fraktal, namun gerak Brown (yang merupakan teknik yang dapat menggunakan Perlin noise) adalah fraktal dan biasanya disebut sebagai Perlin noise.
Elva
Ya, maaf, saya selalu memperbaiki orang ketika mereka membingungkan Perlin noise dan pink noise, tetapi di sini saya membuat kesalahan yang sama sendiri. Satu-satunya pertahanan saya adalah bahwa Minecraft juga benar-benar menggunakan noise pink (gerakan brown), IIRC.
Nevermind

Jawaban:

20

Saya baru-baru ini mengimplementasikan algoritma untuk tata kota prosedural. Ini masih banyak pekerjaan yang sedang berjalan, tetapi tampaknya menjanjikan bagi saya. Lihatlah:

contoh kota prosedural

Algoritma yang digunakan untuk membuat tata letak ini secara longgar didasarkan pada L-Systems . Saya memiliki Elementkelas dasar , yang memiliki persegi panjang menandai tempatnya di peta dan metode Grow, yang membuat lainnya Elementsdi dalam persegi panjang, dan / atau memunculkan beberapa objek di peta. Lalu ada elemen yang sebenarnya, yang diwarisi dari kelas dasar ini: City, Street, Buildingdll

Generasi dimulai dengan sejumlah objek "seed" (dalam kasus saya, hanya satu Cityelemen yang ditempatkan secara acak di peta). Kemudian sistem mengulangi semua elemen, memanggil Grow, hingga semua elemen menjadi tidak aktif ( Growkembali false), atau sejumlah besar iterasi berlalu.

Kota dalam gambar dibangun hanya menggunakan beberapa aturan sederhana:

  • Citymenjadi Streetelemen yang membelah area di suatu tempat.
  • Semuanya Streettumbuh di sisi jalan 0-3, semakin membelah daerah tersebut.
  • Juga, Streets terus mencoba untuk menyesuaikan ukuran acak Buildingdi samping.

Hasilnya tidak terlalu menarik, tetapi juga tidak buruk. Sistem dapat diperluas dengan mudah, dan cukup sederhana untuk memahami apa yang terjadi (-8

Lupakan
sumber
Suka kesederhanaan. Kota-kota, saya kira, sebenarnya organik karena mereka dikendalikan oleh entitas organik - yang berupaya menciptakan kesempurnaan seperti yang dilihat oleh pikirannya - membuat L-Systems mungkin merupakan perkiraan terbaik dari proses ini.
Jonathan Dickinson
Saya suka itu. =) Sekarang untuk menerapkan di pygame ...
Ken
8

Ada pembicaraan GDC ini tentang generasi pembangunan prosedural dari beberapa tahun yang lalu. Ini untuk membuat bangunan individu berdasarkan seperangkat templat, tetapi tidak untuk membuat seluruh kota (menata jalan-jalan dan sebagainya). Sayangnya, tidak ada kode gratis untuk menggunakannya. Sistem yang dijelaskan dalam ceramah diimplementasikan dalam Unreal meskipun saya tidak jelas apakah itu dalam versi gratis UDK atau tidak. Bagaimanapun, Anda dapat menggunakan beberapa ide yang sama untuk membangun sistem Anda sendiri.

"Gedung prosedural" Google atau "kota prosedural" juga akan memberi Anda beberapa makalah dan artikel lain tentang topik tersebut.

Nathan Reed
sumber