Generowanie proceduralnych lochów: czy istnieje prosty algorytm, aby upewnić się, że wszystkie te pokoje są połączone za pomocą minimalnych korytarzy?

Czy można uzyskać strukturę przypominającą ul, łączącą wszystkie pokoje bez zbyt wielu korytarzy? (Zbyt wiele to 3-4 + korytarze wychodzące z jednego pokoju)

Poniżej znajduje się wynik tego, jak wyglądają moje pokoje, w zasadzie losowo rozmieszczone.

Mam nadzieję, że rozwiążę sprawę korytarza.

Cóż, najprostszy sposób, jaki mogę wymyślić, zaczyna się od upewnienia się, że wszystkie pokoje są połączone przynajmniej jednym korytarzem:

1. Zacznij od ostatniego lub pierwszego pokoju.
2. Chwyć losowy pokój w odległości 1 odległości, który nie jest jeszcze połączony z jakimś pokojem (wszystkie pokoje zaczynają się rozłączać, więc będziesz śledził to podczas podróży).
3. Jeśli nie ma takiego pokoju, idź na odległość +1. Jeśli tunelowanie nad / pod innym pokojem jest w porządku, jest to łatwiejsze, zakładając, że nie chcesz łączyć korytarzy.
4. Poruszaj się pseudolosowo, aż wszystkie pokoje zostaną połączone.

Teraz wiemy, że możesz dostać się do wszystkich pokoi, ale teraz, jeśli chcesz więcej niż ten ściśle liniowy labirynt, możesz po prostu przejść przez pokoje i losowo utworzyć nową ścieżkę łączenia pokoi, do limitu na pokój 2-3, lub dopóki określony procent pokoi nie osiągnie maksymalnej liczby połączeń - itp.

Ostatnim krokiem jest dodanie reguł, które zmieniłyby wyniki w zależności od różnych sytuacji. Na przykład można zauważyć, że każdy pokój z tylko 1 korytarzem jest z definicji ślepą uliczką; Możesz zrobić więcej ślepych zaułków lub możesz je wszystkie wyeliminować, upewniając się, że wszystko ma co najmniej 2 połączenia. Możesz sprawić, że ślepe zaułki mają tajne przejście. Możesz upewnić się, że pokój szefa jest ślepym zaułkiem. Możesz upewnić się, że Twój pokój początkowy jest ślepy, ale upewnij się, że drugi pokój ma minimum X połączeń. Ad infinitum.

Każde założenie i zasada może radykalnie zmienić wygląd twoich poziomów, ale to część zabawy! Powinno to przynajmniej zacząć od stworzenia pomieszczeń przypominających jaskinie / jaskinie.

Po prostu zbuduj pokoje już połączone. Zacznij od jednego pokoju, a następnie zbuduj 1-3 korytarze do innych pomieszczeń. Następnie powtarzaj, aż dodasz wystarczającą liczbę pokoi.

Ponieważ te pokoje są wierzchołkami grafu osadzonymi na równinie 2d, teoretycznie można to zrobić, rozwiązując problem podróżnego sprzedawcy (co byłoby w porządku, gdyby było tylko kilka pokoi). Oczywiście prosta heurystyka byłaby w porządku i umożliwiałaby rozsądną skalowalność.

Obliczasz krawędzie (długości korytarza) między wszystkimi pokojami. Sortujesz je według długości. Dodajesz najkrótszy korytarz, chyba że tworzy on cykl lub nie zwiększa stopnia wierzchołka (pomieszczenia) powyżej pożądanej wartości maksymalnej (3-4) (Powtórz). Aby sprawdzić cykle, możesz zastosować UnionFind lub wykonać szybki BFS na małych danych.