Zmniejsz liczbę krawędzi wykresu, utrzymując go połączony


10

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.


Twój pomysł to w zasadzie drzewo wyszukiwania binarnego, jeśli chcesz wiedzieć. Użyłem tego; robi raczej ładne lochy i jest łatwe. :)
Kaczka komunistyczna

2
FYI: Pełny wykres ma krawędzie między wszystkimi parami wierzchołków, więc (zakładając, że duplikaty krawędzi nie są dozwolone) nie można usunąć żadnych krawędzi i nadal mieć pełny wykres. Właściwy termin to połączony wykres .
Michael Madsen

Drzewo wyszukiwania binarnego, połączony wykres, prawo. Jestem taki zły z konwencjonalną nazwą rzeczy.
Splo

Odpowiedzi:


13

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.


1
Oczywiście, minimalne drzewo opinające! Dobry pomysł, dzięki.
Splo


0

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.