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?
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 .
źródło
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.
źródło
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ę.
źródło