Wie kann man ein Stadtstraßennetz erzeugen?

Ich möchte einen Stadtgenerator für ein Spiel erstellen, aber ich stehe am Anfang der Generation vor einem Problem: dem Straßensystem.

Da es sich um eine mittelalterliche Welt handelt, möchte ich keinen Rasterplan wie in vielen modernen Städten. Ich würde im Idealfall eine pseudozufällige Generation von großen Alleen und kleineren Straßen bevorzugen, in denen es möglich sein könnte, sich zu verirren, aber mit etwas Logik - kein vollständiges Labyrinth.
Etwas, das wie eine natürlich gewachsene Stadt aussehen würde.

Um es einfach zu halten, nehmen wir an, meine Städte befinden sich auf ebenem und stabilem Gelände, ohne Flussüberquerung oder Hilfsprobleme. Ich könnte versuchen, es später in eine Lösung zu integrieren.

Ich habe mich nicht für eine genaue Größe oder Disposition für meine Städte entschieden. Wenn Sie also eine Lösung haben, die nur für Städte mit einer genauen Form (Quadrat, Kreis, Rechteck usw.) funktioniert, würde ich diese annehmen.

Ein guter Ausgangspunkt für die prozedurale Stadterzeugung ist die prozedurale Modellierung von Städten nach Parish und Müller . Ihre Arbeit stellt ein L-System vor, in dem Regeln bezüglich Bevölkerungsdichte und Straßenmuster (rechteckiges Raster, radiale und geringste Höhenänderung) kombiniert und dann festgelegt werden, um lokalen Einschränkungen wie Wasserfronten und Straßenästhetik Rechnung zu tragen. Obwohl die Ergebnisse dieses Systems beeindruckend sind, wurde es als unnötig kompliziert kritisiert . Barretts alternative Lösung wird in Rudzicz ' Spare Parts Dev Blog wie folgt umformuliert :

• Führen Sie eine Liste der "vorgeschlagenen" Straßen
• bewerte sie in einer bestimmten Reihenfolge
• ob sie akzeptabel sind (mit oder ohne kleinere Modifikationen)
• Speichern Sie jede akzeptierte Straße, während Sie eine Handvoll weitere Abzweigungen "vorschlagen"

Dieser Ansatz beseitigt den größten Teil der in Parish und Müllers L-System vererbten Umschreibung von Symbolen. Eine Demo dieses Ansatzes finden Sie hier .

Ein Vorteil dieses Ansatzes ist, dass es stadtformunabhängig ist - Sie können nach Bedarf Gliederungsbeschränkungen hinzufügen, so dass Ihre Stadtform eher durch Ihre Spieldesignanforderungen als durch den Algorithmus bestimmt werden kann. Abhängig von Ihrer Stadtgröße ist dies möglicherweise ausreichend. Hier ist ein Ergebnis der obigen Demo mit einem Segmentlimit von 100: Wenn Sie jedoch etwas Großes benötigen, haben Sie möglicherweise Probleme. Hier ist ein Ergebnis mit einem Segmentlimit von 500:

Zum Teil können Sie dies anpassen, indem Sie die Straßenverzweigungsregeln ändern, 90-Grad-Winkel usw. vermeiden. Wenn Ihr Layout immer noch zu regelmäßig ist, ist dies meine Korrektur:

Verwandeln Sie Ihr Stadtgitter in einen Graphen, in dem jede Straße eine Kante und jeder Schnittpunkt ein Knoten ist. Verwenden Sie als Nächstes einen beliebigen Algorithmus, um das Diagramm in ein Labyrinth umzuwandeln . Hier ist das letzte Beispiel, das sich in ein Labyrinth verwandelt hat:

Jetzt hat die Ausgabe das gegenteilige Problem, es ist zu labyrinthartig. Aber jetzt können wir ein paar Techniken aus der Geheimarbeit von Jamis Buck's Dungeon Generator anwenden . Erstens, erhöhen Sie die Spärlichkeit, indem Sie einige Sackgassen entfernen. Erhöhen Sie als Nächstes die Konnektivität, indem Sie Straßen hinzufügen, die Schleifen erzeugen (dh dem Diagramm Zyklen hinzufügen). Hier ist ein Beispielergebnis:

Hinweis: Es ist möglich, dasselbe Endergebnis direkt aus der vorherigen rasterorientierten Layoutphase (vor dem Generieren des Labyrinths) zu erzielen, indem nur Randentfernungen auf das Stadtraster angewendet werden. Das Problem bei diesem Ansatz ist, dass Sie sicherstellen müssen, dass das Entfernen einer Kante die Stadt nicht trennt, wodurch Teile unerreichbar werden.

Wenn du suchst bei Google mittelalterlichen / alten Stadtplänen finden Sie viele verschiedene Variationen, hauptsächlich basierend auf der Herkunft der Stadt (z. B. zufällige Siedlung vs. organisierte militärische Position).

Ich nehme an, Sie suchen nach einer natürlicher gewachsenen / chaotischen Siedlung.

Für diese würde ich einen Ansatz wie diesen versuchen:

• Beginnen Sie mit einer Hauptstraße, die von einem Ende zum anderen führt (und idealerweise einige andere Siedlungen miteinander verbindet). Wenn Sie möchten, erstellen Sie eine dritte Straße, sodass Sie eine Kreuzung erhalten, an der Sie Ihre Siedlung beginnen können.
• Stellen Sie einige Häuser entlang der Straße auf (nur auf einer Seite).
• Verbreitern Sie nun diese Straße entlang der Häuser und fügen Sie auf der anderen Seite ein Wahrzeichen hinzu (normalerweise eine Kirche, aber es kann sich auch um eine Mühle oder ähnliches handeln). Dies wird Ihr Zentrum / Marktplatz sein.
• Wählen Sie nun zwei Positionen außerhalb des Bereichs mit den Häusern und erstellen Sie eine neue Straße, die die Häuser umgibt.
• Erstellen Sie optional einige kleinere Verbündete zwischen Häusern, die die alte und die neue Straße verbinden.
• Wiederholen Sie nun, bis Sie mit Ihrem "Kern" zufrieden sind:
  • Fügen Sie noch ein paar Häuser hinzu.
  • Fügen Sie eine weitere Straße hinzu, die sie umgibt.
  • Fügen Sie Gassen hinzu, die die Straßen verbinden.
• Sobald Sie damit zufrieden sind, sind Sie fertig. Wenn es eine Stadt sein soll, umgeben Sie sie mit Mauern und wiederholen Sie die letzten Schritte noch ein paar Mal, indem Sie zusätzliche Häuser außerhalb der Mauern hinzufügen.

Zuallererst gibt es eine Unmenge von Möglichkeiten zur Erstellung von Prozeduren, und keine von ihnen ist überhaupt einfach. Ich werde eine Art Ansatz finden, wie Sie es zum Laufen bringen könnten, ob Sie es annehmen, modifizieren oder verwerfen.

Wird Pseudocode in JS, da es einfacher zu verstehen ist.

1º Definieren Sie einen Einstiegspunkt. Wenn Sie eine mittelalterliche Stadt bauen möchten, beginnen wir mit einem Quadrat. Nehmen wir also an, Ihre Stadt hat 300 quadratische Einheiten und das Quadrat befindet sich in der Mitte (dargestellt mit einem X).

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

const square = [ 150, 150 ];

2º jetzt werden wir die Alleen sehen, es wird eine zufällige Anzahl von ihnen geben, sie werden gerade sein und vom mittleren Platz oder von anderen Alleen ausgehen

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

Dies sollte Ihnen einen Platz und ein paar Hauptstraßen geben

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

Jetzt müssen wir die Alleen festlegen, die nicht auf dem Hauptplatz beginnen, sondern die anderen Alleen kreuzen

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] ];

}

Um senkrechte Vektoren zu erhalten, müssen Sie die x- und y-Schnüre vertauschen und das neue y negieren:

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

Im Moment solltest du etwas Ähnliches haben, sieht es nicht aus wie eine Stadt? : P

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

3º Jetzt müssen Sie nur noch die Alleen mit kurzen Straßen verbinden. Außerdem können Sie überall in der Stadt zufällige Quadrate erzeugen und für alle die gleichen Werte wie oben festlegen.

Denken Sie daran, je kürzer Ihre Straßen sind, desto chaotischer sieht die Stadt aus.