Generacja lochów bez korytarzy i zależności między pokojami

Tworzę grę z generowanym proceduralnie światem utworzonym na początku gry, składającym się z kilku obszarów reprezentowanych przez siatki (powiedzmy 8x8, 9x6, rozmiary byłyby idealnie dowolne). Te obszary powinny być ze sobą połączone za pomocą listy zależności.

Połączenie istnieje, gdy co najmniej 3 przestrzenie tej siatki są odsłonięte między tymi dwoma obszarami. W środkowej komórce tego 3 obszaru połączenia kosmicznego jest przejście między obszarami:

Próbowałem znaleźć sposób ich połączenia, ale staje się to coraz bardziej złożone, im więcej obszarów musisz wziąć pod uwagę w tym samym czasie.

Próbowałem prototypowania papieru i chociaż jest to bardzo prosty proces, gdy robię to wizualnie, nie znalazłem dobrego zestawu wyrażeń matematycznych, które pozwalają mi umieszczać pokoje o tej samej wydajności według kodu.

Oto „prosty” przykład, z którym obecnie mam problem:

• Obszar „a” należy połączyć z „b” i „c”
• Obszar „b” należy połączyć z „a” i „d”
• Obszar „c” musi być połączony z „a” i „d”
• Obszar „d” należy połączyć z „b” i „c”

Rozważmy, dla uproszczenia, umieszczamy pokoje według kolejności pojawiania się na liście (próbowałem już innych). Podchodzę więc do tego jako do standardowego algorytmu proceduralnego generowania lochów.

Umieszczamy „a” w dowolnym miejscu na planszy, ponieważ jest to pierwszy obszar. Następnie losowo wybieramy ścianę, a ponieważ nic nie jest z nią połączone, możemy umieścić tam „b”:

Teraz musimy umieścić „c”, ale „a” jest już na planszy i ma zajmowaną ścianę, więc postanawiamy umieścić ją na innej ścianie. Ale nie każde miejsce docelowe wystarczy, ponieważ pojawi się litera „d” i należy ją również połączyć z literą „b” i „c”:

Wypróbowałem możliwe ograniczenie, że 2 pokoje z tym samym zestawem zależności nie mogą znajdować się na przeciwległych ścianach, ale nawet to nie gwarantuje sukcesu:

A w innych przypadkach, gdy obszary mają różne rozmiary, znajdowanie się na przeciwległych ścianach może działać:

Nieuwzględnienie użytej ściany jest błędnym założeniem, ponieważ wyklucza prawidłowe rozwiązania:

Próbowałem szukać badań nad innymi algorytmami generowania procedur lub podobnymi, takimi jak optymalne pakowanie prostokątów i algorytmy układu wykresów, ale zwykle algorytmy te nie uwzględniają wszystkich ograniczeń tego problemu i trudno je ze sobą łączyć.

Myślałem o wielu podejściach, w tym o umieszczeniu obszaru i cofnięciu się do znalezienia odpowiedniego miejsca docelowego, ale wydają się one bardzo zależne od prób i błędów i są kosztowne pod względem obliczeniowym. Ale biorąc pod uwagę szeroko zakrojone badania dwóch ostatnich problemów, o których wspomniałem, może to być jedyne / najlepsze rozwiązanie?

Chciałem tylko sprawdzić, czy ktoś miał podobne problemy w przeszłości lub jest gotów pomóc mi to rozgryźć i podać kilka wskazówek, od czego powinienem zacząć od algorytmu. W przeciwnym razie będę musiał rozluźnić ograniczenia, które nałożyłem.

To fajny problem. Wierzę, że można to rozwiązać za pomocą planowania działań w miejscu umieszczenia pokoju.

Zdefiniuj stan świata w następujący sposób:

//State:
//    A list of room states.
//    Room state:
//      - Does room exist?
//      - Where is room's location?
//      - What is the room's size?

Zdefiniuj ograniczenie jako:

 // Constraint(<1>, <2>):
 //  - If room <1> and <2> exist, Room <1> is adjacent to Room <2>

Gdzie „przylegający” jest jak opisano (dzielenie co najmniej 3 sąsiadów)

Wiązanie mówi się unieważnione , gdy dwa pokoje nie sąsiadują ze sobą, i istnieją zarówno pokoje.

Zdefiniuj stan, który będzie ważny, gdy:

// foreach Constraint:
//        The Constraint is "not invalidated".
// foreach Room:
//       The room does not intersect another room.

Zdefiniuj akcję jako umiejscowienie pokoju, biorąc pod uwagę bieżący stan. Akcja jest ważna , gdy stan wynikający z działania jest prawidłowy. Dlatego możemy wygenerować listę akcji dla każdego stanu:

// Returns a list of valid actions from the current state
function List<Action> GetValidActions(State current, List<Constraint> constraints):
    List<Action> actions = new List<Action>();
    // For each non-existent room..
    foreach Room room in current.Rooms:
        if(!room.Exists)
            // Try to put it at every possible location
            foreach Position position in Dungeon:
                 State next = current.PlaceRoom(room, position)
                 // If the next state is valid, we add that action to the list.
                 if(next.IsValid(constraints))
                     actions.Add(new Action(room, position));

Teraz pozostaje ci wykres , na którym stany są węzłami, a akcje są linkami. Celem jest znalezienie stanu, który jest zarówno ważny, jak i wszystkie pokoje zostały umieszczone. Prawidłowe umiejscowienie możemy znaleźć, przeszukując wykres w dowolny sposób, być może wykorzystując wyszukiwanie w pierwszej kolejności. Wyszukiwanie będzie wyglądać mniej więcej tak:

// Given a start state (with all rooms set to *not exist*), and a set of
// constraints, finds a valid end state where all the constraints are met,
// using a depth-first search.
// Notice that this gives you the power to pre-define the starting conditions
// of the search, to for instance define some key areas of your dungeon by hand.
function State GetFinalState(State start, List<Constraint> constraints)
    Stack<State> stateStack = new Stack<State>();
    State current = start;
    stateStack.push(start);
    while not stateStack.IsEmpty():
        current = stateStack.pop();
        // Consider a new state to expand from.
        if not current.checked:
            current.checked = true;
            // If the state meets all the constraints, we found a solution!
            if(current.IsValid(constraints) and current.AllRoomsExist()):
                return current;

            // Otherwise, get all the valid actions
            List<Action> actions = GetValidActions(current, constraints);

            // Add the resulting state to the stack.
            foreach Action action in actions:
                State next = current.PlaceRoom(action.room, action.position);
                stateStack.push(next);

    // If the stack is completely empty, there is no solution!
    return NO_SOLUTION;

Teraz jakość wygenerowanego lochu będzie zależeć od kolejności, w jakiej rozważane są pokoje i akcje. Możesz uzyskać interesujące i różne wyniki, prawdopodobnie losowo zezwalając na działania podejmowane na każdym etapie, a tym samym wykonując losowy przegląd wykresu stanu działania. Skuteczność wyszukiwania będzie w dużej mierze zależeć od tego, jak szybko można odrzucić nieprawidłowe stany. Może to pomóc w generowaniu poprawnych stanów z ograniczeń, ilekroć chcesz znaleźć prawidłowe działania.

Priorytety waszego pokolenia są w konflikcie. Podczas generowania poziomów twoim pierwszym celem powinna być sieć płaskich (nie nakładających się), połączonych punktów , niezależnie od skali. Następnie przejdź do tworzenia pokoi z punktów w tej sieci. Ogólnie rzecz biorąc, tworzenie najpierw kształtów pokoju jest błędem. Najpierw utwórz łączność, a następnie sprawdź, jakie formy pokoju można w nim pomieścić.

Ogólny algorytm

1. Utwórz skwantyzowaną siatkę podłogową o wystarczających rozmiarach, aby obsłużyć swój poziom, korzystając z tablicy 2D lub obrazu.

2. Rozrzucaj losowo punkty na tej pustej powierzchni podłogi. Możesz użyć zwykłego losowego sprawdzenia na każdym kafelku, aby zobaczyć, czy uzyska on punkt, lub użyć standardowego rozkładu Gaussa do rozproszenia punktów. Przypisz unikalny kolor / wartość liczbową do każdego punktu. To są identyfikatory. (PS Jeśli po tym kroku poczujesz, że musisz zwiększyć przestrzeń, zrób to.)

3. Dla każdego takiego generowanego punktu, kolejno, stopniowo zwiększaj granice okręgu lub granice prostokąta o jeden krok (zwykle z szybkością 0,5-1,0 komórek / piksele na krok) w xi y. Możesz albo wyhodować wszystkie granice równolegle, wszystkie zaczynając od wielkości zero na tym samym etapie, lub możesz zacząć hodować je w różnych czasach i przy różnych szybkościach, dając stronniczość wielkości tych, które zaczynają się wcześniej (wyobraź sobie, że sadzonki rosną, gdzie niektóre zacznij późno). Przez „wzrost” mam na myśli wypełnienie nowo zwiększonych granic kolorem / identyfikatorem unikalnym dla punktu początkowego tych granic. Metaforą tego byłoby trzymanie pisaków na grzbiecie kartki papieru i obserwowanie, jak plamy atramentu w różnych kolorach rosną, aż się spotkają.

4. W pewnym momencie granice pewnego punktu i innego punktu zderzą się podczas etapu wzrostu. W tym momencie powinieneś przestać zwiększać granice dla tych dwóch punktów - przynajmniej w jednolitym znaczeniu opisanym w kroku 3.

5. Po przekroczeniu granic wszystkich punktów i zatrzymaniu wszystkich procesów wzrostu, będziesz mieć mapę, która powinna być w dużej mierze, ale nie do końca wypełniona. Możesz teraz spakować puste miejsce, które, jak zakładam, jest białe, jak gdyby kolorowało na kartce papieru.

Wypełnianie przestrzeni po procesie

W kroku 5 można zastosować różne techniki, aby wypełnić puste / białe pola, które pozostały:

• Niech jeden sąsiadujący, już zabarwiony obszar zajmie miejsce, zalewając go tym kolorem, aby wszystko się połączyło.
• Zalewaj nowe, jeszcze nieużywane kolory / liczby / identyfikatory, tak że tworzą one zupełnie nowe obszary.
• Okrągłe podejście robin, tak że każdy już wypełniony sąsiedni obszar „rośnie” trochę w pustą przestrzeń. Pomyśl o zwierzętach pijących wokół wodopoju: wszyscy dostają trochę wody.
• Nie wypełniaj całkowicie pustej przestrzeni, po prostu przejdź przez nią, aby połączyć istniejące obszary za pomocą prostych przejść.

Perturbacja

Ostatnim krokiem, aby sprawić, że wszystko będzie wyglądać bardziej organicznie, możesz wywołać zaburzenia krawędzi w różnym stopniu na krawędziach komórek obszarów. Pamiętaj tylko, aby nie blokować kluczowych tras ruchu.

Teoria, dla zainteresowania

Jest to podobne do podejścia zastosowanego w diagramach Voronoi / triangulacji Delaunaya , z tym wyjątkiem, że powyżej nie tworzysz wyraźnie krawędzi - zamiast tego, gdy zderzają się obszary graniczne, wzrost ustaje. Zauważysz, że diagramy Voronoi wypełniają przestrzeń; dzieje się tak dlatego, że nie przestają wzrostu jedynie poprzez dotyk, ale raczej w pewnym nominalnym stopniu nakładania się. Możesz spróbować podobnie.