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.