Proceduralne generowanie budynku o określonym obszarze


15

Ja i zespół pracujemy nad grą budowniczą fabryk, która daje graczowi losową fabrykę na początku gry. Aby upewnić się, że istnieje poczucie „uczciwości”, idealnie losowo wygenerowana fabryka miałaby obszar w obrębie kilku jednostek (wartość zastępcza) 30.

Stosunkowo prosty jest napisanie prostego generatora losowych prostokątów, aby spełnić te specyfikacje, ale naszym celem jest, aby fabryka była bardziej złożona, być może złożona z 2, 3 lub nawet 4 przecinających się prostokątów, tworząc bardziej złożone kształty (pomyśl o L, Budynki w kształcie litery U i O).

Próbowałem wygenerować losowy prostokąt, a następnie użyć podstawowej algebry do wypełnienia drugiego prostokąta, ale jak dotąd nie miałem szczęścia wdrożyć więcej niż 2 prostokąty, a nawet wtedy nie jestem zadowolony z wyników dla projektu tylko 2 prostokątów .

Kilka bardziej istotnych informacji: 2D z góry na dół Niektóre mechaniki są w stylu factorio, więc pokoje powinny mieć rozsądną długość i szerokość, aby umożliwić miejsce na maszyny Obecnie w Javie i Lua (w razie potrzeby można użyć wbudowanych bibliotek)

Z góry dziękuję!

EDYCJA: Kiedy mówię „dobre” lub „złe” wyjścia, złym wyjściem byłoby każde wyjście, na którym odtwarzacz nie ma miejsca. Fabryczne granice kształtu, w których gracz może umieszczać maszyny fabryczne, takie jak przenośniki taśmowe. Idealnie, fabryka nie powinna mieć obszarów o szerokości tylko 1-2 bloków, kształt nie powinien być jednym lub dwoma dużymi prostokątami z linią 1-2 bloków „zwisającymi” na bok. Dobrym wyjściem byłoby, gdy cała powierzchnia podłogi jest „wykonalna”, więc wszystkie obszary mają szerokość co najmniej 3-4 bloków. Dobry wynik nie zawsze musi być złożony (1 lub 2 prostokąty są w porządku), ale powinien mieć spore szanse, jeśli składa się z więcej niż 1-2 prostokątów.

Odpowiedzi:


7

Możesz użyć wstępnie wygenerowanych poliominoesów jako meta-kształtów, aby zbudować asortyment budynków.

Powiedzmy, że twoja minimalna akceptowalna odległość to 3 bloki. Najmniejszą akceptowalną jednostką budowlaną, którą weźmiemy pod uwagę, jest 3x3. Dla wygody zamierzam nazwać to komórką i daje ona obszar 9 bloków. Następnie weź docelowy obszar początkowy i podziel go przez obszar komórki. Używając podanej wartości początkowej, otrzymujemy 3,333; więc 3 komórki dadzą ci trochę mniej niż chcesz, a 4 komórki dadzą więcej.

Stąd masz kilka opcji. Jeśli jesteś elastyczny w obszarze początkowym, użyj dowolnej metody, która najlepiej ci odpowiada, aby wybrać liczbę komórek, która daje akceptowalną ilość (tj. Zaokrąglić do najbliższej wartości, zaokrąglić w górę itp.). Nazywam to liczbą komórek.

Następnie losowo wybierz poliomino z żądaną liczbą komórek. Zastąp każdy kwadrat na poliomino komórką budującą i uzyskasz swój ostateczny kształt.

Aby to zilustrować, powiedzmy, że zdecydowaliśmy się zaokrąglić w dół. Oto wszystkie polominoy wielkości 3 (bez rotacji / flipów):

wprowadź opis zdjęcia tutaj

Załóżmy, że losowo wybieramy kształt L i stosujemy losowy obrót, twój budynek miałby następujący układ:

wprowadź opis zdjęcia tutaj

Kilka problemów. Po pierwsze, istnieje ograniczenie liczby komórek, których możesz użyć. Wikipedia da Ci wszystkie poliomino do rozmiaru 8 ( oktomino ). Zawiera dane podsumowujące dla rozmiaru do 12, ale nie wiem, czy jest dla nich lista online. Po drugie, powyższe rozwiązanie działa tylko w przypadku rozmiarów budynków, które są wielokrotności 9. Istnieje kilka sposobów obejścia niektórych z tych problemów:

1) Użyj innej wielkości komórki. Na przykład 3x4, 4x4 itp.

2) Dodaj dodatkowe komórki do wyjściowego poliomino. Może to być trudne, jeśli musisz upewnić się, że wszystkie kształty są jednakowo prawdopodobne, ale dla większości twórców gier są szanse, że nie potrzebujesz naprawdę jednolitego rozkładu kształtów budynków.

3) Wysuń budynek, aby go powiększyć. Wracając do przykładu, jeśli użyjesz 3 komórek, twój budynek będzie miał powierzchnię 27 kwadratów, co pozostawi cię niedokończonym o 3. Możesz następnie zeskanować obwód w poszukiwaniu miejsca, w którym skleisz grupę kwadratów o rozmiarze 1x3. Tak długo, jak twoja grupa makijażu jest co najmniej AxB, gdzie A jest co najmniej minimalną akceptowalną odległością, twój wynik nie naruszy twojego minimalnego akceptowalnego ograniczenia odległości. W oparciu o powyższy przykład, oto ilustracja możliwego wyniku:

wprowadź opis zdjęcia tutaj

4) Zamiast wypełniać zbyt mały budynek, możesz przyciąć zbyt duży budynek. Zapewnienie przestrzegania minimalnego dopuszczalnego ograniczenia odległości jest bardziej złożone niż opcja wypełniania, ale dałoby więcej możliwości do rozważenia.

Kilka innych komentarzy:

To, że możesz użyć wszystkich możliwych poliominoów o danym rozmiarze, nie oznacza, że ​​powinieneś. Jeśli niektóre z nich nie są fajne, przerwij motyw, bądź obraźliwe dla odbiorców (wzorce swastyki) lub spowoduj inny problem, usuń je. Możesz również wyważyć procedurę wyboru, jeśli niektóre wzorce są interesujące, ale zbyt dziwne, aby rutynowo się pojawiały. Wreszcie możesz użyć tego rozwiązania w połączeniu z bieżącą strategią. Może 70% czasu generujesz prostokątne budynki i 30% czasu używasz podejścia polyomino. A może zaczynasz od prostokątnego budynku i przyklejasz małe poliomino na zewnątrz.


16

Prostym sposobem na zbudowanie generatora proceduralnego jest:

  1. Losowo buduj rzeczy
  2. Uruchom funkcję, która sprawdza, czy dane wyjściowe są dobre
  3. Jeśli wyjście nie jest dobre, przejdź do kroku 1

Nawet jeśli ukończenie wymaga tysięcy przebiegów, większość prostych generatorów radzi sobie dobrze z tym podejściem. Zaletą jest to, że w generatorze nie trzeba wiele inteligentnych rozwiązań, a ponieważ sprawdzenie, czy coś jest dobre, jest znacznie łatwiejsze niż zbudowanie czegoś, co jest dobre w 100% przypadków, takie podejście jest bardzo łatwe.

Wymieniłeś niektóre obiektywne miary, czy wynik jest dobry; to powinno wystarczyć, aby stworzyć szybki i brudny generator. Umieść losowo prostokąty w obszarze i odrzuć wydruk, jeśli na przykład istnieją obszary o szerokości tylko 1-2 bloków.

Zacznij od tego, następnie ulepsz i zoptymalizuj.


Dziękuję Ci! Pamiętam, że zastanawiałem się nad tym, ale zatrzymała mnie myśl, że istnieje szansa na kilka sekund + czas ładowania. Teraz zdaję sobie sprawę, jak niesamowicie mała jest ta szansa. Będę musiał to wypróbować, ale najpierw mogę poczekać, aby sprawdzić, czy ktoś ma bardziej bezpośrednie rozwiązanie.
user2129189,

@ user2129189 Po uruchomieniu generatora nadal można dostosować jego zakresy liczb losowych, aby uniknąć generowania układów, które prawdopodobnie nie przejdą testu. Możliwe jest także zrównoleglenie tego algorytmu generowania prób i błędów na wielu rdzeniach, dzięki czemu każdy rdzeń będzie generował jeden układ na raz.
Philipp

3
Sam nie jestem fanem metod generowania odrzucania i ponownej próby. Są wystarczająco szybkie, gdy generator wykonuje tylko jedną prostą rzecz, ale w przypadku poziomów gry zwykle zaczynamy nakładać kolejne warstwy i etapy generowania, aby tworzyć bogatsze mapy. W tym momencie prawdopodobieństwo trafienia w realną mapę jest iloczynem prawdopodobieństwa powodzenia każdego kroku, który może gwałtownie się zmniejszyć. To nie jest tylko kwestia akademicka - rozmawiałem z deweloperami, którzy musieli wdrożyć dobry / zły system buforowania nasion, aby uniknąć nadmiernego czasu generowania, gdy prostszy generator z pojedynczym przejściem byłby łatwiejszy.
DMGregory

@DMGregory tak, zdecydowanie to widzę. Podstawowy generator losowy działałby w moim przypadku przez 99% czasu, ale jeśli chcę później zwiększyć złożoność, może znacznie zwolnić. Czy ktoś wie o prawdziwych aplikacjach do programowania / gier typu zgadywanka i model czekowy?
user2129189

Być może mogą istnieć poziomy funkcji i kontroli pokoleń, starając się dopasować frazowanie warunków do obecnego poziomu generacji. W ten sposób cały poziom nie musi być generowany ponownie po prostu z powodu błędu polegającego na nieznacznym nieprawidłowym umieszczeniu elementu.
Pysis

7

Biorąc pod uwagę ograniczenie „wszystkie obszary mają co najmniej 3-4 bloki szerokości”, pierwszy pomysł, który przychodzi mi do głowy, wygląda następująco:

  1. wybierz jedną z 3x3, 3x4, 4x3 lub 4x4
  2. umieść blok tego rozmiaru na środku siatki
  3. wybierz kierunek (w górę, w lewo, w prawo, w dół)
  4. spróbuj umieścić blok 3x3 obok wcześniej umieszczonych bloków w tym kierunku
  5. jeśli się powiedzie, z pewnym prawdopodobieństwem spróbuj rozszerzyć blok do bloku 4x3 w jednym z kierunków, których nie tylko wybrałeś
  6. z pewnym prawdopodobieństwem przesuń losową krawędź wypełnionych bloków
  7. powtarzaj kroki od 3 do 6, aż obszar będzie wystarczająco duży

Podstawową ideą jest to, że biorąc pod uwagę, że chcesz, aby wszystkie obszary miały co najmniej dany rozmiar, działają tylko w obszarach o tym rozmiarze. Mówiąc bardziej ogólnie, jeśli chcesz, aby coś było prawdą dla wszystkich generowanych wyników, sprawdź, czy można to zrobić dla wszystkich częściowo wygenerowanych wyników.


4
Uprościłbym wszystko, zawsze zaczynając od bloku 3x3, a następnie dodając bloki 3x1 w losowych pozycjach, gdzie każdy kwadrat sąsiaduje z istniejącym. Dodając do bloku 3x3, istnieją cztery możliwe pozycje. Wszystkie dają blok 3x4, z sześcioma możliwymi pozycjami dla następnego. Stamtąd staje się bardziej skomplikowane, ale nie takie złe.
JollyJoker

0

Rozważ użycie booleanów NOT i UNION i wybieranie między nimi losowo.

  1. Umieść losowy prostokąt.
  2. Umieść drugi losowy prostokąt.
  3. Losowo wybierz, czy je ZWIĄZKUĆ, czy SUBTRAKTOWAĆ drugi od pierwszego.
  4. Powtórz dla wielu prostokątów. Chociaż tylko dwa lub trzy mogą dać wystarczająco rozsądne wyniki.

Następnie obliczyłem obszar i przeskalowałem go w górę lub w dół, aby dokładniej dopasować przybliżony rozmiar, którego szukasz, a następnie przetestować, czy nie ma wymiarów mniejszych niż wymagana minimalna ilość.


Twój pomysł skalowania, aby uzyskać pożądany obszar, jest naprawdę cichy i sprytny. Mogę zaimplementować coś tak cichego trochę tak.
user2129189,
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.