Jak wygenerować sieć ulic miasta?

Chciałbym stworzyć generator miasta do gry, ale na samym początku generacji mam do czynienia z problemem: systemem drogowym.

Ponieważ jest to średniowieczny świat, nie chcę planu siatki, jak wiele współczesnych miast. Idealnie wolałbym pseudolosową generację dużych alejek i mniejszych ulic, w których można się zgubić, ale z pewną logiką - nie kompletnym labiryntem.
Coś, co wyglądałoby jak miasto naturalnie wyhodowane.

Aby uprościć sprawę, powiedzmy, że moje miasta byłyby na płaskich i stabilnych terenach, bez problemów z przeprawą przez rzekę lub z ulgą. Mógłbym później spróbować zintegrować to z rozwiązaniem.

Nie zdecydowałem o dokładnym rozmiarze ani rozmieszczeniu dla moich miast, więc jeśli masz rozwiązanie, które działałoby tylko z miastami o precyzyjnej formie (kwadrat, okrąg, prostokąt itp.), Wziąłbym to.

Dobrym miejscem na rozpoczęcie od proceduralnego generowania miast jest Parafialne i proceduralne modelowanie miast przez Müllera . W artykule przedstawiono system L, w którym zasady dotyczące gęstości zaludnienia i wzorów dróg (siatka prostokątna, zmiana promieniowa i najmniejsza zmiana wysokości) są łączone, a następnie ustalane w celu uwzględnienia lokalnych ograniczeń, takich jak fronty wodne i estetyka drogi. Chociaż wyniki tego systemu są imponujące, zostało skrytykowane jako niepotrzebnie skomplikowane . Alternatywne rozwiązanie Barretta znajduje się w Rudziczu części zamiennych następujący sposób:

• prowadzić listę „proponowanych” dróg
• oceń je w jakiejś kolejności
• jeśli są dopuszczalne (z niewielkimi modyfikacjami lub bez)
• przechowuj każdą zaakceptowaną drogę, „proponując” jeszcze kilka odgałęzień

Takie podejście usuwa większość przepisanych symboli odziedziczonych w Parish i L-System Müllera. Tutaj możesz zobaczyć demonstrację tego podejścia .

Zaletą tego podejścia jest to, że jest niezależny od kształtu miasta - w razie potrzeby można dodawać ograniczenia konspektu, aby kształt miasta można było określić na podstawie potrzeb projektowych, a nie algorytmu. W zależności od wielkości miasta może to być wystarczająco dobre. Oto wynik powyższej wersji demonstracyjnej z limitem segmentu 100: Ale jeśli potrzebujesz czegoś dużego, możesz mieć problemy; oto wynik z limitem segmentu 500:

Częściowo możesz to zmienić, zmieniając zasady rozgałęzienia drogi, unikając kątów 90 stopni itp. Jeśli twój układ jest nadal zbyt regularny, oto moja korekta:

Przekształć siatkę miasta w wykres, na którym każda ulica jest krawędzią, a każde skrzyżowanie jest węzłem. Następnie użyj dowolnego algorytmu, który chcesz przekształcić wykres w labirynt . Oto ostatni przykład zamieniony w labirynt:

Teraz wyjście ma odwrotny problem, jest zbyt labiryntowy. Ale teraz możemy zastosować kilka technik z tajnego działania generatora lochów Jamisa Bucka . Po pierwsze, zwiększ rzadkość, usuwając niektóre ślepe korytarze. Następnie zwiększ łączność, dodając drogi tworzące pętle (tj. Wprowadzaj cykle do wykresu). Oto przykładowy wynik:

Uwaga: ten sam wynik końcowy można osiągnąć bezpośrednio z wcześniejszego etapu układu zorientowanego na siatkę (przed wygenerowaniem labiryntu), stosując jedynie usuwanie krawędzi na siatce miasta. Problem z tym podejściem polega na tym, że usunięcie krawędzi nie dzieli miasta, przez co części są niedostępne.

Jeśli szukasz średniowiecznych / starych planów miasta w Google , znajdziesz wiele różnych odmian, głównie opartych na pochodzeniu miast (np. Losowa osada vs. zorganizowana pozycja wojskowa).

Zakładam, że szukasz bardziej naturalnej / chaotycznej osady.

Dla nich spróbuję takiego podejścia:

• Zacznij od głównej drogi prowadzącej z jednego końca na drugi (i idealnie łączącej inne osady. Jeśli chcesz, utwórz trzecią drogę, aby uzyskać skrzyżowanie, na którym można rozpocząć osadę.
• Umieść kilka domów wzdłuż drogi (tylko z jednej strony).
• Teraz poszerz tę drogę wzdłuż domów i dodaj główny punkt orientacyjny po drugiej stronie (zazwyczaj kościół, ale może to być również jakiś młyn lub podobny). To będzie twoje centrum / rynek.
• Teraz wybierz dwie pozycje poza obszarem z domami i stwórz nową drogę otaczającą domy.
• Opcjonalnie stwórz mniejszych sojuszników między domami łączącymi starą i nową drogę.
• Teraz powtarzaj, aż będziesz zadowolony ze swojego „rdzenia”:
  • Dodaj jeszcze kilka domów.
  • Dodaj kolejną otaczającą je drogę.
  • Dodaj zaułki łączące drogi.
• Gdy będziesz z tego zadowolony, skończysz. Jeśli ma to być miasto, otocz je murami i powtórz ostatnie kroki jeszcze kilka razy, dodając dodatkowe domy poza murami.

Po pierwsze, istnieje wiele sposobów na generowanie procedur i żaden z nich wcale nie jest łatwy. Podejdę do tego, w jaki sposób możesz sprawić, by działał, od ciebie zależy, czy go zmodyfikujesz, czy odrzucisz.

Będzie pseudo-kod w JS, ponieważ jest łatwiejszy do zrozumienia.

1º zdefiniuj punkt wejścia, ponieważ chcesz zbudować średniowieczne miasto, zaczniemy od kwadratu, więc powiedzmy, że twoje miasto będzie miało 300 kwadratowych jednostek, a kwadrat będzie na środku (reprezentowany przez X).

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

const square = [ 150, 150 ];

2º teraz będziemy alejami, będzie ich losowa liczba, będą proste i zaczną się od środkowego kwadratu lub od innych alej

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

To powinno dać ci kwadrat i kilka głównych ulic

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

Teraz musimy ustawić ścieżki, które nie zaczynają się na głównym placu, przecinają one inne ścieżki

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

}

Aby uzyskać wektory prostopadłe, musisz zamienić kable x, y i zanegować nowy y:

przesunięty == x: noswiped.y, y: -1 * (noswiped.x)

Teraz powinieneś mieć coś podobnego do tego, czy to nie wygląda na miasto? : P

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

3º teraz musisz tylko połączyć alejki z krótkimi uliczkami, możesz też odradzać losowe kwadraty w całym mieście i robić to samo jak wyżej dla wszystkich z nich, lub po prostu odradzać małe uliczki z niektórych zewnętrznych placów, to zależy od ciebie.

Pamiętaj, że najkrótsze są twoje ulice, chaotyczne miasto wygląda.