Was ist ein guter Algorithmus für das fraktalbasierte prozedurale Stadtlayout?

19

Hintergrund

Ich betreibe einen Minecraft-Server, auf dem ich eine Starterstadt von ziemlich großem Umfang entwerfen werde. Ich habe eine Reihe von Dingen, wie Regelzeichen und Mob-Käfige, die ich dort gerne in Gebäuden unterbringen würde. Die Stadt selbst wird extrem groß und verteilt sein, vorzugsweise bis zu 1000 mal 1000 Blöcke groß.

Die Gebäude selbst haben würfelförmige oder rechteckige Grundrisse, die auf einem bestimmten Basiswürfel basieren, wie alle Vielfachen von 3 Blöcken. Die Straßen und der Abstand zwischen den Gebäuden sind je nach Wichtigkeit der Straße vorzugsweise 5 bis 11 Blocks breit.

Wenn ich mit dem Plan für die Stadt beginne, werde ich genau wissen, wie groß die Gebäude sein sollen und wie viele es sein werden.

Das Problem

Das Problem ist, das Layout für die Stadt zu entwerfen. Offensichtlich ist es bei so einer Größenordnung und meiner Erfahrung als Programmierer und nicht als Stadtplaner eine ziemliche Herausforderung, mich überhaupt mit dem Problem auseinanderzusetzen.

Das Problem ist speziell, dass ich möchte, dass die Stadt so natürlich wie möglich aussieht. Natürlich wäre es ziemlich einfach, auf einem einfachen Gittermuster aufzubauen, aber ich möchte ein Gitter oder irgendetwas, das wie ein Gitter aussieht, so weit wie möglich vermeiden.

Die Frage

Welche Algorithmen kann ich anwenden, um sie mithilfe von Code zu entwerfen? Ich dachte, dass es am natürlichsten aussehen würde, wenn ich auf irgendeine Weise Fraktale verwenden würde, da Minecraft Fraktale bereits in seiner Geländegeneration verwendet und eine Stadt auf natürliche Weise in einem Fraktalmuster zu wachsen scheint.

Ich denke, es ähnelt in gewisser Weise einem Tetris-Spielalgorithmus. Wenn also irgendjemand Lösungen hat, die in diese Richtung existieren, würde dies auch helfen. Ich stelle mir etwas vor, in dem ich die Formen definieren kann, die ich verwenden möchte, und die Software iteriert dann, bis sie die "optimale" Lösung für die gleichmäßige Verteilung von Gebäuden findet. Gibt es schon etwas, das mir hilft, dieses Problem mit Python zu lösen, am besten visuell mit Pygame?

Natürlich hat dies auch interessante Auswirkungen auf die Stadtgeneration im Allgemeinen im Spieledesign. Daher bin ich sehr gespannt, welche Lösung die beste ist.

editieren Um es klar zu machen, ich suche an dieser Stelle nur nach dem Layout, da die Gebäude im Spiel entworfen und gebaut werden.

Ken
quelle
3
Minecraft nutzt Fraktale? Ich hatte den Eindruck, dass es nur kontinuierliche Rauschfunktionen verwendet (Perlin oder Simplex, glaube ich).
Martin Sojka
@Martin Sojka Perlin Rauschen ist eigentlich ein Fraktal, also da.
Nevermind
1
@Nevermind: Das bestimmende Merkmal eines Fraktals ist die Selbstähnlichkeit : Wenn Sie einen Teil davon auswählen und auf die Größe des Originals skalieren, ist er "ähnlich" (hat dieselbe Struktur). Insbesondere ist das Frequenzspektrum eines fraktalen Signals nicht skalierbar. Wenn Sie dies mit Perlin-Rauschen tun, erhalten Sie lediglich einen vergrößerten Bereich eines Perlin-Rauschens. das Frequenzspektrum verschiebt sich ebenfalls.
Martin Sojka
@Nevermind Perlin-Rauschen ist eigentlich kein Fraktal, aber Brownsche Bewegung (eine Technik, die Perlin-Rauschen verwenden kann) ist ein Fraktal und wird allgemein als Perlin-Rauschen bezeichnet.
Elva
Ja, tut mir leid, ich korrigiere immer Leute, wenn sie Perlin-Rauschen und Pink-Rauschen verwechseln, aber hier mache ich selbst den gleichen Fehler. Meine einzige Verteidigung ist, dass Minecraft tatsächlich auch rosa (braune Bewegung) Rauschen verwendet, IIRC.
Nevermind

Antworten:

20

Ich habe kürzlich einen Algorithmus für ein prozedurales Stadtlayout implementiert. Es ist noch sehr viel in Arbeit, aber es scheint mir vielversprechend. Schau mal:

prozedurales Stadtbeispiel

Der zur Erstellung dieses Layouts verwendete Algorithmus basiert lose auf L-Systems . Ich habe eine Basisklasse Element, die ein Rechteck hat, das ihren Platz auf der Karte markiert, und eine Methode Grow, die andere Elementsinnerhalb des Rechtecks ​​erzeugt und / oder einige Objekte auf der Karte erzeugt. Dann gibt es tatsächlich Elemente von dieser Basisklasse geerbt: City, Street, Buildingusw.

Die Generierung beginnt mit einer Reihe von "Startobjekten" (in meinem Fall nur ein einzelnes CityElement, das zufällig auf der Karte platziert wurde). Dann iteriert das System über alle Elemente und ruft sie auf Grow, bis alle Elemente inaktiv werden ( Growzurückkehren false) oder eine große Anzahl von Iterationsdurchläufen.

Die Stadt im Bild wird nach wenigen einfachen Regeln gebaut:

  • Citywird zu einem StreetElement, das den Bereich irgendwo aufteilt.
  • Alle Streets bauen 0-3 Seitenstraßen an und teilen das Gebiet weiter auf.
  • Außerdem Streetversuchen wir ständig, eine zufällige Größe Buildingan der Seite anzubringen.

Das Ergebnis ist nicht besonders interessant, aber auch nicht schlecht. Das System kann leicht erweitert werden und ist einfach genug, um zu verstehen, was vor sich geht (-8

Keine Ursache
quelle
Liebe die Einfachheit. Städte sind, denke ich, eigentlich organisch, weil sie von einer organischen Einheit kontrolliert werden - die Perfektion schaffen will, wie es der Verstand sieht -, was L-Systems wahrscheinlich zur besten Annäherung an diesen Prozess macht.
Jonathan Dickinson
Ich mag das. =) Jetzt in Pygame implementieren ...
Ken
8

Es gibt diesen Vortrag der GDC über die Erstellung von Verfahren vor ein paar Jahren. Es dient zum Erstellen einzelner Gebäude auf der Grundlage einer Reihe von Vorlagen, jedoch nicht zum Erstellen ganzer Städte (Anlegen von Straßen usw.). Leider gibt es dazu keinen kostenlosen Code. Das im Vortrag beschriebene System ist in Unreal implementiert, obwohl mir nicht klar ist, ob es sich um die kostenlose Version von UDK handelt oder nicht. In jedem Fall könnten Sie einige der gleichen Ideen verwenden, um Ihr eigenes System zu erstellen.

Wenn Sie "prozedurale Gebäude" oder "prozedurale Stadt" googeln, erhalten Sie auch eine ganze Reihe anderer Artikel und Artikel zum Thema.

Nathan Reed
quelle
1

Ich bin vor einiger Zeit auf ein sehr gutes / detailliertes Tutorial zum Erstellen prozeduraler Städte gestoßen. Es gibt ein Video unter http://www.youtube.com/watch?v=-d2-PtK4F6Y. Das Tutorial befindet sich auf dem Blog des Autors: http://www.shamusyoung.com/twentysidedtale/?p=2940 Ich hoffe, das hilft amb

amb
quelle
Sieht aus wie ein großartiges Tutorial von dem, was ich überflogen habe, und es wird einige großartige Hinweise geben, wenn ich mich entscheide, Städte später zu generieren. =)
Ken