Jak mogę znaleźć izolowane grupy pokoi, mając listę pokoi ze swoim połączeniem ze sobą?

Próbuję stworzyć małego roguelike i posunąłem się do losowo generujących pokoi i korytarzy. Każdy pokój jest obiektem instancji i zawiera zestawienie pozostałych pomieszczeń połączonych korytarzem.

Mogę wyodrębnić niepołączone pokoje, ale skąd mam wiedzieć, które pokoje są połączone tylko ze sobą, ale nie z większością innych, tworząc wyspę?

Aby lepiej zilustrować problem, tutaj jest obraz z konsoli na zapadniętym poziomie. Pokoje 5 i 6 są połączone tylko ze sobą. Jakiego algorytmu mogę użyć do wykrycia tego?

wprowadź opis zdjęcia tutaj

java algorithm

— petervaz
źródło

Masz problem z użyciem obrazu? Ten link do pastebin potrwa tylko miesiąc.

— MichaelHouse

Tak, na początku nie do końca rozumiałem, co tu zrobiłeś. Przepraszam, cofnąłem twoją zmianę.

— petervaz

Dlaczego nie skonstruujesz go tak, aby w ogóle nie było oddzielnych pokoi? A może chcesz mieć izolowane zestawy?

— AlbeyAmakiir,

@AlbeyAmakiir, jak powiedziałem w innym komentarzu poniżej, generuję pokoje oddzielnie metodą prób i błędów, aż do wypełnienia mapy, tylko wtedy uruchamiam procedurę łączenia, a następnie uruchamiam inną, aby połączyć te wyspy. Wiem, że jest to prawdopodobnie zbyt skomplikowane, ale nie mogłem wymyślić innej drogi.

— petervaz

Odpowiedzi:

Zacznij od pełnej listy pokoi. Wybierz pokój początkowy. Przejdź z tego pokoju do wszystkich połączonych pokoi. Dla każdego pomieszczenia, które odwiedzasz, usunąć go z listy pokoi i dodać go do listy A . Po odwiedził wszystkie swoje połączenia, wszystkie pozostałe pokoje na liście nie są podłączone do pokoju wyjścia lub którykolwiek z pokoi na liście A .

Następnie możesz kontynuować, wybierając pokój z resztek pełnej listy i ponownie nawigując. Tym razem dodając do listy B . Kontynuuj ten proces, aż nie będzie już żadnych pokoi na oryginalnej liście. Masz teraz listę wszystkich połączonych zestawów pokojowych.

Tego rodzaju problemy można łatwo dostosować do problemów teorii grafów. Na przykład opisany powyżej problem dotyczy bezpośrednio łączności .

— MichaelHouse
źródło

dowolny algorytm drzewa wyszukiwania powinien działać. To lub możesz zmienić algorytm generowania, aby uniknąć tego problemu. Jeśli zmienisz algorytm generowania, po prostu wygeneruj losową liczbę pokoi dołączonych do pokoju początkowego, a następnie losową liczbę pokoi dołączonych do każdego z poniższych elementów, możesz dodać losowe połączenia między istniejącymi pokojami, aby nieco urozmaicić skróty oraz taki. Osobiście zrobiłbym tylko algorytm drzewa wyszukiwania.

— Benjamin Danger Johnson

To bardzo logiczne. Muszę być zmęczony Dzięki za pomoc. Przyjmę, gdy tylko pozwoli.

— petervaz

@BenjaminDangerJohnson Twój komentarz wydaje się bardziej odpowiedni dla pytania, a nie tej odpowiedzi.

— MichaelHouse

@petervaz Nie ma problemu. Wydaje mi się, że mój dyplom z CS ma swoje zastosowanie.

— MichaelHouse

@BenjaminDangerJohnson mój algorytm generujący po prostu umieszcza losowe pokoje, aż wypełni przestrzeń i szuka połączeń później. = P Spróbuje naprawić połączenia przed uciekaniem się do zmiany stworzenia.

— petervaz

Twoja kolekcja pokoi jest zasadniczo wykresem, a twój problem sprowadza się do znalezienia połączonych komponentów („wysp”) na tym wykresie.

Prostym sposobem na znalezienie połączonych komponentów jest wykonanie BFS (wyszukiwanie szerokości od pierwszego) z każdego wierzchołka. Wykonanie BFS z wierzchołka A da ci wszystkie wierzchołki w połączonym komponencie, do którego należy wierzchołek A.

Zasadniczo zaczynasz od dowolnego wierzchołka, wykonujesz BFS i zaznaczasz każdy napotkany wierzchołek jako członek 1. „wyspy”. Następnie przechodzisz do następnego nieoznakowanego wierzchołka i ponownie robisz BFS, tym razem etykietowanie napotkało wierzchołki jako członków drugiej „wyspy” i tak dalej.

Możesz wyobrazić sobie pokoje jako wierzchołki na ukierunkowanym wykresie . W ten sposób będziesz w stanie zastosować dobrze znane algorytmy, aby rozwiązać swój problem.

Na przykład algorytm Dijkstry tworzy najkrótsze drzewo ścieżki dla danego wierzchołka początkowego na wykresie. To drzewo będzie zawierać wszystkie osiągalne wierzchołki od punktu początkowego. Następnie możesz wywnioskować, że wierzchołki nieobecne w drzewie są częścią innych wysp. Możesz zastosować algorytm do tych wierzchołków, aby uzyskać drzewa reprezentujące każdą wyspę.

— Asakeron
źródło

Nawet nieukierowany wykres by to zrobił ... z wyjątkiem tego, że masz trasy tylko w jedną stronę.

— Aron_dc,

@Aron_dc, masz rację, możesz wyobrazić sobie pokoje jako wierzchołki na niekierowanym wykresie i uzyskać podobne wyniki za pomocą algorytmu Kruskala. Właśnie zasugerowałem wyobrażenie go jako ukierunkowanego wykresu ze względu na sposób, w jaki petervaz reprezentował połączenia - tj. Pokój 1> 3

— Asakeron