Jaki jest dobry algorytm dla proceduralnego układu miasta opartego na fraktali?


19

tło

Prowadzę serwer Minecraft, na którym zamierzam zaprojektować miasto początkowe o dość dużej skali. Mam szereg rzeczy, takich jak znaki reguły i klatki mobów, chciałbym tam postawić budynki. Samo miasto będzie bardzo duże i rozproszone, najlepiej do 1000 na 1000 bloków.

Same budynki będą miały sześciany lub prostokątne ślady, które są oparte na określonej kostce podstawowej, podobnie jak wszystkie wielokrotności 3 bloków. Ulice i odległość między budynkami będą miały korzystnie szerokość 5-11 bloków, w zależności od znaczenia ulicy.

Kiedy zacznę plan miasta, będę dokładnie wiedział, jak duże mają być budynki i ile będzie.

Problem

Problemem jest zaprojektowanie układu dla miasta. Oczywiście z czymś na taką skalę, a ja pochodzę ze środowiska programistycznego, a nie ze środowiska urbanisty, trudno jest nawet zacząć owijać się wokół problemu.

Problem polega konkretnie na tym, że chcę, aby miasto wyglądało tak naturalnie, jak to możliwe. Oczywiście byłoby to dość łatwe do zbudowania na prostym wzorze siatki, ale chcę uniknąć siatki lub czegokolwiek, co wygląda jak siatka, w miarę możliwości.

Pytanie

Jakie algorytmy mogę zastosować, aby pomóc mi zaprojektować je za pomocą kodu? Myślałem, że wyglądałoby to najbardziej naturalnie, gdybym w jakiś sposób używał fraktali, ponieważ Minecraft wykorzystuje fraktale już w trakcie generowania terenu, a miasto wydaje się naturalnie rosnąć w strukturze fraktalnej.

Myślę, że pod pewnymi względami jest podobny do algorytmu odtwarzania tetris, więc jeśli ktoś ma rozwiązania, które istnieją w tym kierunku, to też by pomogło. Wyobrażam sobie coś, w czym będę w stanie zdefiniować kształty, których chcę użyć, a następnie oprogramowanie iteruje, dopóki nie znajdzie najbardziej „optymalnego” rozwiązania dla równomiernego rozmieszczenia budynków. Czy istnieje już coś, co pomogłoby mi rozwiązać ten problem za pomocą Pythona, najlepiej w formie wizualnej za pomocą pygame?

Oczywiście ma to również interesujące implikacje dla generowania miast w ogóle w projektowaniu gier, więc jestem bardzo podekscytowany, aby zobaczyć, jakie jest najlepsze rozwiązanie.

edytuj Żeby było jasne, właśnie szukam układu w tym momencie, ponieważ budynki zostaną zaprojektowane i wbudowane w grę.


3
Minecraft używa fraktali? Miałem wrażenie, że po prostu używa funkcji ciągłego szumu (jak sądzę Perlin lub Simplex).
Martin Sojka

@Martin Sojka Perlin hałas to tak naprawdę fraktal, więc jest.
Nevermind

1
@Nevermind: Cechą charakterystyczną fraktala jest samopodobieństwo : jeśli wybierzesz jego część i przeskalujesz ją do rozmiaru oryginału, będzie ona „podobna” (ma taką samą strukturę). W szczególności widmo częstotliwości sygnału fraktalnego jest niezmienne w skali. Jeśli zrobisz to z hałasem Perlina, dostaniesz tylko powiększony obszar hałasu Perlina; spektrum częstotliwości również się zmieni.
Martin Sojka

@Nevermind Hałas Perlina w rzeczywistości nie jest fraktalem, jednak ruch Browna (technika, która może wykorzystywać hałas Perlina) jest fraktalem i jest powszechnie określany jako hałas Perlina.
Elva

Tak, przepraszam, zawsze poprawiam ludzi, kiedy mylą hałas Perlina i różowy, ale tutaj popełniam ten sam błąd. Moją jedyną obroną jest to, że Minecraft faktycznie używa również szumu różowego (ruch Browna), IIRC.
Nevermind

Odpowiedzi:


20

Niedawno zaimplementowałem algorytm dla proceduralnego układu miasta. Nadal jest to w toku, ale wydaje mi się obiecujące. Spójrz:

przykład miasta proceduralnego

Algorytm użyty do stworzenia tego układu jest luźno oparty na L-Systems . Mam Elementklasę podstawową , która ma prostokąt zaznaczający swoje miejsce na mapie i metodę Grow, która tworzy inne Elementswewnątrz prostokąta i / lub spawnuje niektóre obiekty na mapie. Następnie są elementy rzeczywiste, odziedziczone po tej klasie bazowej: City, Street, Buildingitd.

Generowanie rozpoczyna się od szeregu „nasion” obiektów (w moim przypadku tylko jeden Cityelement losowo umieszczony na mapie). Następnie system dokonuje iteracji po wszystkich elementach, wywołując Grow, aż wszystkie elementy staną się nieaktywne ( Growpowrót false) lub upłynie pewna liczba iteracji.

Miasto na zdjęciu jest zbudowane według kilku prostych zasad:

  • Citystaje się Streetelementem dzielącym gdzieś obszar.
  • Wszystkie Streetrosną w bocznych ulicach 0-3, dodatkowo dzieląc obszar.
  • Ponadto Streetstale staramy się dopasować Buildingz boku losowy rozmiar .

Wynik nie jest strasznie interesujący, ale też nie jest zły. System można łatwo rozszerzyć i jest wystarczająco prosty, aby zrozumieć, co się dzieje (-8


Uwielbiam prostotę. Miasta są, jak sądzę, w rzeczywistości organiczne, ponieważ są kontrolowane przez organiczną istotę - która dąży do stworzenia doskonałości tak, jak widzi ją oko umysłu - co czyni L-Systems prawdopodobnie najlepszym przybliżeniem tego procesu.
Jonathan Dickinson

Lubię to. =) Teraz do zaimplementowania w grze pygame ...
Ken

8

Jest to rozmowa GDC na procesowego generacji budynku z kilka lat temu. Służy do tworzenia pojedynczych budynków na podstawie zestawu szablonów, ale nie do tworzenia całych miast (wytyczania ulic itp.). Niestety nie ma wolnego kodu. System opisany w dyskusji jest zaimplementowany w Unreal, chociaż nie jestem pewien, czy jest to darmowa wersja UDK, czy nie. W każdym razie możesz użyć tych samych pomysłów do zbudowania własnego systemu.

Googling „budynki proceduralne” lub „miasto proceduralne” dostarczy również sporo innych artykułów i artykułów na ten temat.


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.