Proceduralne generowanie budynku o określonym obszarze

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.

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):

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

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:

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.

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.

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.

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ść.