Proceduralny… dom z generatorem pomieszczeń

Patrzyłem na niektóre algorytmy i artykuły dotyczące proceduralnego generowania lochów. Problem polega na tym, że próbuję wygenerować dom z pokojami, które wydają się nie spełniać moich wymagań.

Po pierwsze, lochy mają korytarze, w których domy mają sale. I choć początkowo mogą wydawać się takie same, korytarz jest niczym więcej niż obszarem, który nie jest pokojem, podczas gdy korytarz jest specjalnie zaprojektowany do łączenia jednego obszaru z drugim.

Inną ważną różnicą w domu jest to, że masz określoną szerokość i wysokość, i musisz wypełnić całą rzecz pokojami i korytarzami, podczas gdy w lochach jest pusta przestrzeń.

Myślę, że korytarze w domu to coś pomiędzy korytarzem lochu (prowadzi do innych pomieszczeń) a pustą przestrzenią w lochu (nie jest to wyraźnie zdefiniowane w kodzie).

W szczególności wymagania są następujące:

• Jest zestaw predefiniowanych pokoi
  , których nie mogę tworzyć ścian i drzwi w locie.
• Pokoje można obracać, ale nie można ich zmieniać.
  Ponownie, ponieważ mam predefiniowany zestaw pokoi, mogę je tylko obracać, a nie zmieniać ich rozmiar.
• Wymiary domu są ustawione i muszą być całkowicie wypełnione pokojami (lub korytarzami)
  To znaczy, chcę wypełnić dom 14x20 dostępnymi pokojami, upewniając się, że nie ma pustej przestrzeni.

Oto kilka zdjęć, aby to trochę wyjaśnić:

Jak widać, w domu „pusta przestrzeń” jest jeszcze dostępna dla pieszych i prowadzi z jednego pokoju do drugiego.

Powiedziawszy to wszystko, może dom jest naprawdę bardzo ciasno wypełnionym lochiem z korytarzami. Lub jest to coś łatwiejszego niż loch. Może coś tam jest i nie znalazłem tego, bo tak naprawdę nie wiem, czego szukać.

Oto gdzie chciałbym twojej pomocy: czy mógłbyś mi dać wskazówki, jak zaprojektować ten algorytm? Wszelkie przemyślenia na temat tego, jakie kroki podejmie? Jeśli stworzyłeś generator lochów, jak zmodyfikowałbyś go, aby spełniał moje wymagania? Możesz być tak szczegółowy lub tak ogólny, jak chcesz. Naprawdę chcę wybrać twój mózg.

Myślę, że jest to dobry przypadek dla użycia partycji binarnej lub trójskładnikowej.

Przy pierwszym przejściu podziel przestrzeń domu na korytarze i {bloki pokoi}. Zdobądź następny duży kawałek, podziel go na {hall and chunk} lub {2 kawałki i hall między nimi}. Na każdym kroku obróć kierunek krojenia o 90 stopni. Zatrzymaj się, gdy {nie będzie już więcej dużych kawałków} lub {całkowita powierzchnia hali osiągnęła limit}.

Przy drugim przejściu podziel pozostałe fragmenty na pokoje. Zdobądź kolejny duży kawałek i podziel go. Pomiń losowo kilka niezbyt dużych kawałków, aby mieć duże pokoje.

Jeśli jakakolwiek hala jest skierowana do znacznie starszej hali, umieść tam ścianę (lub ścianę z drzwiami).

Połącz pokoje z salami bezpośrednio lub poprzez inne już połączone pokoje.

Na przykład możesz zobaczyć mój ręcznie spreparowany wynik lub C ++ - podobnie jak częściowo wykonany pseudo-kod . Końcowy strzał:

Możesz skorzystać z faktu, że pożądany projekt łączy pokoje w prostokątnych pokojach otoczonych korytarzami. Mając to na uwadze, zrobiłbym to:

1. Zaprojektuj korytarze i „duże przestrzenie” pomieszczeń
2. Wypełnij każdą „dużą przestrzeń” pokojami

Wypełnianie dużych pomieszczeń pokojami można łatwo zrobić, jeśli zaczniesz od pokoi na granicach - mają one określone ograniczenia, na przykład pokoje od strony korytarza mogą mieć drzwi na tej ścianie, ale pokoje od strony „ścian zewnętrznych” nie może (być może mogą mieć okna). Pokoje „wewnątrz” dużych bloków będą wymagały co najmniej jednego wejścia.

Oto, jak rozwiązałem ten problem. Ale najpierw chciałbym podziękować zarówno @Shadows In Rain, jak i @egarcia za ich odpowiedzi. Dali mi dobry kierunek, który pomógł mi uzyskać pewne wyniki.

Użyłem partycji kosmicznej Shadows In Rain, aby wygenerować podstawowy dom, a następnie postępowałem zgodnie z radą Egarcia, aby wypełnić pokój pokojami.

Partycjonowanie przestrzeni było dość proste, ponieważ 90% kodu zostało wykonane przez Shadows. Część „wypełnij pokoje” była nieco trudniejsza. Zdecydowałem się użyć pseudo systemu AI, który używa A * do odpowiedniego ustawiania pomieszczeń. Dobrą rzeczą w korzystaniu z planowania zamiast tylko A * jest to, że warunki wstępne znacznie zmniejszają przestrzeń wyszukiwania.

Oto kilka zrzutów ekranu z wynikami:

Faza generowania planu piętra

Faza umieszczenia pokoju

Teraz z połączonymi drzwiami!

Dahl i Rinde mają rozprawę doktorską na temat Proceduralnego generowania środowisk wewnętrznych, która wykorzystuje szkielet i regiony do wypełniania wnętrz budynków pokojami i korytarzami. Artykuł zawiera schematy klas dla ich prototypu. W ich bibliografii jest też kilka dobrych odniesień, w tym wspomniany język wzorców .

Ich praca została zaprojektowana w oparciu o następujące założenia upraszczające:

• dotyczy tylko budynków mieszkalnych
• brak podzielonych poziomów
• ograniczenie kształtu budynków (obwiedni) musi być wielokątne
• brak otworów w kopercie
• podobna lub zmieniająca się liniowo grubość obwiedni (IE bez kształtów klepsydry)
• dotyczy tylko budynków wymagających korytarzy

Oto krótki przegląd ich procesu:

• Znajdź szkielet koperty. Korytarze są następnie umieszczane wzdłuż szkieletu na podstawie odległości od obwiedni, odległości od drzwi lub schodów oraz odległości od wcześniej umieszczonych korytarzy.
• Następnie pozostała przestrzeń bez korytarza jest dzielona na maksymalnie połączone obszary, z których każdy ma jedną ciągłą granicę. W niektórych przypadkach będzie to wymagać wstawienia ściany.
• Regiony te są następnie dzielone na mieszkania próbujące przydzielić co najmniej jedno okno na mieszkanie. W niektórych przypadkach mniejsze dywizje połączą się, aby uniknąć zbyt małych mieszkań. Regiony bez okien są po prostu ignorowane.

• Na koniec apartamenty są podzielone na pokoje przy użyciu ważonego schematu podobnego do Voronoi:

  • Ciężary nasion mają wpływ na wielkość pomieszczenia. Nasiona są dodawane do drzwi i okien. Dodaje się dodatkowe nasiona, na ogół jedno na pożądany pokój; choć nie zostało to wyraźnie określone, wygląda na to, że nasiona są umieszczone wzdłuż zewnętrznych ścian mieszkania.
  • Zaczynając od najdalszego punktu, obliczana jest linia między danym nasionem a wszystkimi pozostałymi punktami, a następnie podzielona na dwie części w stosunku do odpowiednich wag punktów końcowych (np. Jeśli A i B miałyby ciężary 1 i 4, punkt przecięcia byłby 1/4 drogi od A do B). Zbiór przecinających się linii wraz ze ścianą zewnętrzną tworzy następnie komórkę dla nasion.
  • Następnie tworzy się szkielet ściany S-Space (zgodnie z Peponis i in. 1997) poprzez podzielenie obszaru liniami rozpoczynającymi się prostopadle od punktów środkowych między sąsiednimi parami elementów ściany zewnętrznej (okna lub drzwi).
  • Wreszcie, ściany wybiera się ze szkieletu S-space, który „najlepiej odpowiada ścianom komórkowym Voronoi”.