Algorithmen zur Stadterzeugung

In diesem RPG.SE-Beitrag wird eine lange verlorene Seite mit mehreren Online-Generatoren erwähnt.

Ich bin besonders neugierig auf die Art und Weise, wie Städte entstanden sind. Nehmen Sie dieses Bild zum Beispiel:

Obwohl viele Dinge grafisch verbessert werden konnten, war es angesichts der damals verfügbaren Tools (Mitte bis Ende der 90er Jahre) sehr gut:

• Das Straßenlayout scheint ziemlich organisch zu sein (auch wenn alle Straßen orthogonal angeordnet sind).
• Nicht alle Straßen sind notwendigerweise miteinander verbunden, aber es fühlt sich richtig an .
• Gebäude werden an glaubwürdigen Stellen platziert.
• Sogar Bäume scheinen an logischen Stellen platziert zu sein .

Ich denke, es würde Spaß machen, es zu versuchen und es selbst zu versuchen. Zumal meine vorherigen Versuche zu "blockig" waren:

Sie werden feststellen, dass ich viele der Eigenschaften mit nicht ganz messbaren Adjektiven beschreibe ( scheint , fühlt , glaubwürdig usw.), so dass es mir schwer fällt, sie in Anweisungen und letztendlich in einen Algorithmus zu übersetzen.

Gibt es bewährte Algorithmen für die Stadterzeugung?

Ich verstehe, dass dies zu weit gefasst zu sein scheint. Bedenken Sie Folgendes: Wenn ich nach einem Algorithmus zum Generieren von Karten kontinentaler Landmassen fragen würde, würde ich sofort Verweise auf Perlin und andere Rauschalgorithmen erhalten. dicht gefolgt von Voronoi.

Ich habe Fragen wie diese gesehen, aber sie scheinen bereits eine konkretere Idee zu haben (dh: 2x2 Häuser, feste Anzahl von Häusern, Einschränkungen bei der Platzierung von Kanälen und Straßen).

Was ich gerne hätte, ist etwas weniger eingeschränkt. Außer vielleicht für das Rasterlayout, das für einen ersten Versuch viel einfacher sein sollte als beispielsweise das L-System.

Introversion Software hat einen wirklich beeindruckenden Stadtgenerator für das auf unbestimmte Zeit abgesagte Projekt Subversion erstellt :

Der Algorithmus wurde entwickelt, um große, moderne Metropolen zu generieren. Dieselben Techniken können jedoch verwendet werden, um mehr ländliche Siedlungen zu schaffen.

Es handelt sich um einen Top-Down-Algorithmus, der zuerst die groben Umrisse generiert und dann immer mehr Details generiert, die in diese passen (für den entgegengesetzten Bottom-Up-Ansatz zur prozeduralen Generierung überprüfen Sie die Antwort von uliwitness). Hier ist ein Video, das den laufenden Algorithmus visualisiert .

Der Algorithmus scheint wie folgt zu funktionieren (leicht vereinfacht):

1. Stadtzentren: Wählen Sie einige Punkte der noch leeren Karte als Hauptverkehrsknoten aus. Sie sollten gleichmäßig auf der Karte verteilt sein
2. Autobahnen: Verbinden Sie die Hauptverkehrsknoten über Hauptstraßen mit ihren Nachbarn und mit der Außenwelt.
3. Autobahnen: Unterteilen Sie die von den Hauptstraßen erzeugten Zellen, indem Sie einige Nebenstraßen erstellen.
4. Straßen: Wiederholen Sie den Unterteilungsvorgang rekursiv mit immer kleineren Straßen, bis Sie die gewünschte Bausteingröße erreicht haben
5. Blöcke: Legen Sie den Zweck jedes Bausteins fest (Wohnen, Einzelhandel, Unternehmen, Industrie ...). Relevante Faktoren sind die Größe der Nachbarstraßen und die Entfernung vom Zentrum.
6. Zuteilungen: Teilen Sie die Kanten aller Bausteine ​​in Lose ein (dies bedeutet, dass jedes Los mindestens eine Kante hat, die mit einer Straße verbunden ist).
7. Gebäude: Erstellen Sie für jedes Grundstück ein passendes Gebäude.

In Bezug auf die Platzierung von Bäumen: Mein erster Ansatz wäre, diese in den Algorithmus zur Gebäudegenerierung zu integrieren. Ein Gebäude muss sein Grundstück nicht vollständig ausfüllen. Sie können den freien Raum mit geeigneten Dekorationsgegenständen füllen.

Das Problem beim Top-Down-Ansatz besteht darin, dass zwar eine plausible Stadt generiert wird, jedoch möglicherweise keine plausible Stadt mit allem, was Sie möchten . Nehmen wir an, jede Stadt in Ihrem Spiel benötigt einen Waffenladen, einen Rüstungsladen, einen Trankladen und ein Gasthaus. Der obige Algorithmus wählt Gebäude basierend auf den Anforderungen des Grundstücks aus, sodass Sie möglicherweise 12 Rüstungsgeschäfte haben, aber kein einziges Gasthaus. Ich würde dieses Problem in der Phase der Gebäudeerzeugung angehen. Bevor Sie zufällig Gebäude erstellen, gehen Sie Ihre Liste der Gebäude durch, die Sie haben müssen, und wählen Sie für jedes Gebäude das am besten geeignete aus. Dann füllen Sie die restlichen Grundstücke mit zufälligen Gebäuden.

Ich freue mich darauf, die prozedural erzeugten Städte in Ihrem Spiel zu erkunden.

Holen Sie sich Einschränkungen aus dem wirklichen Leben

Oft beginnt die Antwort darauf, wie man den richtigen Algorithmus findet, damit, wie diese Dinge im wirklichen Leben passieren. Hast du dir das angeschaut? Auf den ersten Blick fällt mir Folgendes ein:

• Straßen verbinden Gebäude und andere Sehenswürdigkeiten
• Gebäude werden nach Möglichkeit entlang bestehender Straßen platziert
• Wenn es keine Straße gibt, wird ein Gebäude an einer leeren Stelle platziert und über eine eigene Straße mit einer nahe gelegenen Straße verbunden
• Gebäude werden in der Nähe anderer Gebäude aufgestellt, die für ihre Bewohner von Interesse sind: Menschen ziehen in die Nähe ihrer Arbeitsplätze, Lebensmittel- und Bekleidungsgeschäfte usw.
• Gebäude werden in der Nähe von Ressourcen platziert, die für den beabsichtigten Gebrauch erforderlich sind. Beispielsweise wird ein Sägewerk in der Nähe von Wäldern oder sogar auf einer Waldlichtung aufgestellt. Menschen brauchen Wasser und Nahrung (Pflanzen, Tiere), um irgendwo zu leben.
• Gebäude werden weit entfernt von anderen Gebäuden platziert, die sich nachteilig auf ihren Verwendungszweck auswirken oder denen sie schaden würden. ZB riecht eine Färberei schrecklich, wird also normalerweise nicht in einem Wohngebiet platziert. Ebenso sind Tavernen und Restaurants laut, so dass die Bewohner nicht auf ihnen wohnen wollen, sondern Kunden brauchen, also in der Nähe von Wohngebieten sein müssen.
• Einige Länder haben Zonierungsgesetze, die auch die Platzierung von Gebäuden beeinflussen. In der Regel ist dies eine formalere Methode, um vorauszusehen, welche Arten von Gebäuden sich gegenseitig schädigen können oder welche Ressourcen für das Gebiet einzigartig sind (z. B. ist hochwertiger Boden für Felder bestimmt, nicht für den Bau von Parkplätzen).
• Gebäude sind für Bewohner und ihr persönlicher Stil und ihre Vorlieben spiegeln sich in ihnen wider. Wenn eine Bevölkerung arm ist, teilen sie sich viel häufiger das Gelände (Wolkenkratzer, Wohnhäuser). Wenn es ihnen besser geht, erhalten sie möglicherweise Eigentumswohnungen. Wenn sie reich sind, erhalten sie eine eigenständige Villa. Wenn bestimmte Gruppen andere Gruppen nicht mögen, ist es weniger wahrscheinlich, dass sie zusammenleben. Wenn zwischen bestimmten Gruppen eine Affinität besteht, können sie sich in ähnliche Bereiche bewegen.

Wenden Sie sie auf Ihre Topographie an

Sobald Sie diese Einschränkungen haben, können Sie versuchen, einen Algorithmus darum herum zu erstellen. Generieren Sie beispielsweise Ihre Topografie und verteilen Sie die benötigten Ressourcen auf der Karte (behalten Sie möglicherweise kleine Ablagerungen der wichtigsten Ressourcen im Startbereich im Auge, dann größere Ablagerungen weiter voneinander entfernt). Hier kommen natürlich die Bedürfnisse und die Mechanik Ihres Spiels ins Spiel, aber Sie werden wahrscheinlich auch ein zufälliges Element hinzufügen.

Bauen Sie dann Unternehmen (und ihre Wohngebäude) in der Nähe der Ressourcen, die sie nutzen. ZB ein Steinbruch neben einem großen Berg. Fügen Sie dann die von ihnen benötigte Infrastruktur hinzu. ZB ein Handelsposten mit Post und Taverne, wo sie Geschäfte machen und ihr Produkt verkaufen können, eine Schmiede, um Werkzeuge usw. bereitzustellen.

Um zu entscheiden, was wohin geht, teilen Sie die Karte mithilfe einer Gewichtungsfunktion in Kacheln auf, in denen Sie für jede Kachel eine Zahl berechnen, wie wünschenswert sie für einen bestimmten Zweck ist. Legen Sie die Gebäude in die begehrtesten Fliesen für diese Art von Gebäude. Fügen Sie Regeln wie "Ein Handelsposten kann 50 Unternehmen oder 100 Häuser verwalten" hinzu, die die Wahrscheinlichkeit erhöhen, einen weiteren Handelsposten hinzuzufügen, wenn eine Stadt eine bestimmte Größe erreicht.

Sobald Sie dies haben, sollten Sie einige ziemlich anständige Karten bekommen. Wenn Sie feststellen, dass Karten alle als unnatürliche Formen enden, fügen Sie Ihren Gewichtungsfunktionen für diese Formen Strafen hinzu, z. B. "Wenn meine Straße direkt neben einer anderen Straße endet, -100 Erwünschtheit" oder "Wenn sich meine Straße selbst kreuzt, -100." Erwünschtheit "usw. Sie können jederzeit ein zufälliges Element hinzufügen, um ein ausgefalleneres Gefühl zu erzielen, oder andere Mechaniken wie" Wenn eine Kreuzung mehr als N Gebäude mit ihren Straßen verbunden hat, verwandeln Sie sie in einen Kreisverkehr ".

Sie können diese Einschränkungen sogar verwenden, um verschiedenen Karten ein anderes Gefühl zu verleihen, z. B. wenn ein bestimmtes Land mehr Berge in seiner Topographie hat oder wenn eine bestimmte Kultur mehr kurvenreiche Straßen baut und eine andere gerade Straßen usw. bevorzugt, indem Sie einfach eine Ihrer Karten ändern Gewichtungsfunktionen.

Vereinfachen

Natürlich ist dieser Ansatz zu komplex für Spiele, die keine Handelssimulationen sind, aber arbeiten Sie dies trotzdem aus und sehen Sie, welche Arten von Gebäuden für Ihr Spiel sinnvoll sind, und beseitigen Sie die nicht benötigten. Überlegen Sie sich dann vereinfachte Regeln wie "Städte in der Nähe eines Flusses, eines Berges oder eines guten Bodens platzieren. 1 Gebäude pro 100 Ressourcen, Unternehmen nach Ressourcentyp, 10 Wohngebäude für jeden vollständigen Satz von Lebensmitteln / Handwerksressourcen ... oder einfach". 1 m Fluss / 1 m 2 Boden können 10 Wohngebäude tragen ... was auch immer für ein Spiel sinnvoll ist. Wenn Sie jedoch wissen, wie viel Fläche Sie haben (z. B. keine Gebäude an steilen Berghängen) und wie viele Gebäude die Fläche tragen kann, platzieren Sie einfach mehrere Gebäude in dieser Fläche, bis sie voll ist (z. B. 1 Geschäftsgebäude, 10 Wohngebäude) , 3 Infrastruktur oder was auch immer) und verbinden sie mit Straßen.