Projektuję grę z losowo generowanymi lochami. Chciałbym zobaczyć to jako połączony, niekierowany wykres, na którym węzły to pokoje, a krawędzie to drzwi lub korytarze. Następnie wybieram „boczny” węzeł jako wejście do lochu, obliczam odległość między tym wejściem a wszystkimi innymi węzłami i stwierdzam, że jeden z najdalszych węzłów jest „celem” lochu (lokalizacja skarbu, bossa, księżniczka itp.).
Widziałem 2 sposoby generowania ostatecznej topografii lochów:
- Wygeneruj najpierw losowy wykres, a następnie spróbuj wypełnić świat 2d pokojami w losowych lokalizacjach, uwzględniając połączenia krawędzi. Uznałem, że czasami będzie to trudne, ponieważ generowanie pokoju może być „zablokowane”, próbując dopasować pokoje w niemożliwych miejscach.
- Generuj pierwsze pokoje, umieszczając je losowo tam, gdzie pasują, a następnie mapuj wynik do węzłów i krawędzi. Postanowiłem spróbować.
Mój pomysł polega na:
- Najpierw stwórz duży pokój, który zawierałby cały loch.
- Umieść ścianę w dużym pokoju, w przypadkowym miejscu, dzieląc duży pokój na 2 mniejsze pokoje o różnej powierzchni.
- Następnie nadal dzielę każdy pokój na 2, aż będą one zbyt małe lub całkowita liczba pokoi osiągnie maksimum (lub jakikolwiek inny warunek). Każdy nowy pokój jest węzłem.
- Po zakończeniu sprawdzam każdy pokój i znajduję wszystkie sąsiednie inne pokoje, zaznaczając 2 węzły jako połączone krawędzią.
W ten sposób upewniam się, że wszystkie pokoje mają możliwą lokalizację w świecie 2D i są poprawnie odwzorowane przez podłączony wykres.
Mój problem polega na tym, że jest zbyt wiele drzwi i korytarzy łączących pokoje.
Chciałbym więc algorytmu, który redukuje liczbę krawędzi połączonego niekierowanego wykresu , ale utrzymując go w połączeniu (wszystkie węzły pozostają osiągalne) na końcu.
Odpowiedzi:
Użyj algorytmu Prim, aby uzyskać minimalne drzewo rozpinające dla twojego wykresu (dodaj losowe ciężary lub dodaj wyższe ciężary w pobliżu wejścia lub wykonaj wybrany algorytm) i ponownie dodaj losowo niektóre drzwi / krawędzie. W ten sposób będziesz mieć połączone wszystkie pokoje i kilka dodatkowych redundantnych ścieżek.
źródło
Możesz także wypróbować algorytm Kruskala
źródło
Niektóre generatory lochów na tej liście z Inkwell Ideas są oprogramowaniem typu open source lub dostarczają dokumentację dotyczącą ich algorytmów. Google obdarzy Cię również wieloma hasłami „generator programowania lochów]. Niestety mojej ulubionej nie można znaleźć żadną z tych metod, mimo że jest to najlepiej udokumentowana, jaką kiedykolwiek spotkałem, i nie pamiętam jej nazwy, ponieważ niedawno straciłem ją na skutek awarii dysku twardego. Zaktualizuję tę odpowiedź po przeprowadzeniu odzyskiwania na tym dysku.
źródło