Najdłuższy algorytm ścieżki do generowania labiryntu roguelike

Mam prostą mapę opartą na siatce złożoną z pokoi, takich jak ta (A = wejście, B = wyjście):

   0 1 2 3
  #########
0 # B # #####
  #########
1 # ### #
  #########
2 # # #
  # # #
3 # # #
  #########
4 # ### #
  #########
5 ### A #
  ### #
6 ### #
  #########

I utknąłem próbując stworzyć odpowiedni algorytm, aby stworzyć ścieżkę drzwi między pokojami, w taki sposób, że gracz musi zbadać większość mapy przed znalezieniem wyjścia.

Innymi słowy, staram się znaleźć najdłuższą drogę z punktu A do B .

(Zdaję sobie sprawę, że ten problem można rozwiązać w przypadku wykresów acyklicznych; jednak w tym przypadku mogą istnieć cykle).

EDYCJA: Kolejny przykład, w którym pokoje są połączone za pomocą wypełnienia zalewowego, a wyjście jest wybierane jako najdalsze pomieszczenie od wejścia:

   0 1 2 3
  #########
0 # B # #
  # # - #####
1 # | # #
  ### # #
2 ### # #
  ### - # - ###
3 # | ###
  # - #######
4 #A | #
  # # #
5 # # #
  # # #
6 # # #
  #########

Zauważ, że ścieżka do wyjścia nie jest wcale najdłuższą możliwą ścieżką.

Myślę, że podchodzisz do tego niewłaściwie. Maksymalna ścieżka na wykresie z cyklami jest technicznie niezdefiniowana, ponieważ jest nieskończona, jeśli cykl leży między początkiem a końcem. Prawdopodobnie istnieją sprytne sposoby na rozszerzenie / ograniczenie definicji maksymalnej ścieżki, ale nie sądzę, że jest to najlepsze podejście tutaj.

Nie próbujesz modelować rzeczywistej długiej ścieżki (np. Robot próbuje eksplorować jak najwięcej obszaru na mapie). Próbujesz tylko zmusić gracza do eksploracji wielu pokoi.

Więc, dokonać szansę gracz znajdzie wyjście proporcjonalne do procentu mapie zbadane dotychczas . Załóżmy, że na poziomie jest X pokoi, a postać gracza zbadała Y. Następnym razem postać wejdzie do pokoju, umieść tam wyjście z prawdopodobieństwem f (Y, X). Trywialnym przykładem f może być (Y * Y) / (X * X) - np. Dla 10 pokoi istnieje 100% szansy na wyjście z ostatniego pokoju, 81% szansy, że znajdzie się w przedostatnim pokoju - i tylko 1% szansy, że jest w pierwszym pokoju.

Możesz dostosować równanie, jednak chcesz, aby gra była w porządku, a może nawet dać graczowi pewne umiejętności, aby zwiększyć prawdopodobieństwo jego wygenerowania. Kluczowe jest to, że nie generuj wyjścia, dopóki postać nie wejdzie do pokoju. Ta metoda jest również odporna na znajomość algorytmu generowania lochów; nawet jeśli gracz ma dziwne wzorce ruchu, takie jak skok rycerza w NetHacku lub teleportacja, będzie musiał zbadać więcej pokoi, aby znaleźć wyjście.

Jeśli musisz statycznie wygenerować wyjście, możesz użyć tego samego pomysłu z wirtualną postacią. Wyobraź sobie wypełnienie zalewowe, zaczynające się od pozycji postaci, przesuwające się po komórce w każdej iteracji. Ostatnie pomieszczenie do wypełnienia to pomieszczenie, do którego należy wyjście (w rzeczywistości ostatnia komórka do wypełnienia to komórka, w której znajduje się ona najdalej od gracza). Jednak w tym przypadku gracz ma więcej informacji o wyjściu - jeśli jest po lewej, najprawdopodobniej po prawej - i jeśli mogą się teleportować, mogą faktycznie być w stanie dotrzeć tam szybciej niż normalny losowy spacer.

W końcu właśnie skończyłem roguelike, w którym wyjście pojawiło się po drugiej stronie mapy od postaci gracza, a następnie wędrowałem losowo. Niektóre przedmioty w lochach czyniły go widocznym na mapie, kosztem szybszego głodu. Nie przeprowadziłem żadnej analizy, ale zdecydowanie czułem, że muszę odkryć więcej mapy, aby ją znaleźć, a to nadało poziomom wyjątkowy charakter.

Możliwą alternatywą byłoby utworzenie (maksymalnego?) Drzewa opinającego za pomocą Prim / Kruskal (w celu wyeliminowania cykli) i zastosowanie tradycyjnego najdłuższego algorytmu ścieżki na drzewie opinającym.

Martwię się jednak, że algorytm drzewa opinającego będzie miał tendencję do tworzenia ślepych gałęzi, zmuszając gracza do ciągłego cofania się.

EDYCJA: Wynik użycia algorytmu opartego na Kruskalu i umieszczenia wyjścia na końcu najdłuższej gałęzi:

   0 1 2 3
  #########
0 #A | #
  # ##### - #
1 # # #
  ### #
2 ### #
  ### #
3 ### #
  ### - #####
4 # | #
  # - ##### - #
5 # ### #
  # - #######
6 # # B #
  # # - #
7 # | #
  #########

Oto coś, z czym można się bawić:

Connect each room with a door to another room.
N = 0.75*TotalNumberOfRooms
Until (pathSize > N) {
  Use A* pathing to get a path from A to B. (G being size of room, or # of monsters)
  if (pathSize < N) remove a connection/door
  if (noPath) choose a different door/connection
  if (room.doors < 1) choose a different door/connection
}

Usuwałbym drzwi losowo wzdłuż ścieżki, w przeciwnym razie otrzymujesz 1 drzwi przy wyjściu i mnóstwo drzwi na początku.

Myślę, że to O(n^2)nie jest świetne dla dużych map.

2 posty przepełnienia stosu podobne do tego: wykres najdłuższa ścieżka , referencja z tego samego postu .

Wierzę, że masz już świetne odpowiedzi, ale oto moje 0,02 $ teoretycznego rozwiązania problemu.

To, czego chcesz, nie jest najdłuższą ścieżką, ale najdłuższą najkrótszą ścieżką. Chcesz pokoju, który jest najdalej, biorąc pod uwagę, że rozważasz najkrótszą drogę do pokoju. Brzmi to prawdopodobnie myląco, ale bardzo łatwo to obliczyć.

1. Zacznij od swojego pokoju startowego. Zaznacz każdego z sąsiadów 1. Są w odległości 1 od pokoju początkowego.
2. Dla każdego pokoju oznaczonego 1, odwiedź każdego z NIEZNACZONYCH sąsiadów i oznacz ich 2. Są 2 odległości od początku.
3. Kontynuuj, aż pokryjesz wszystkie pokoje. Pokój o maksymalnej liczbie jest najdalej od początku.

Obliczenie najdłuższej ścieżki (nie zajmie to zbyt długo, powiedzmy 10 pokoi) nie będzie działać, ponieważ nie możesz zmusić gracza do wybrania najdłuższej ścieżki. Tak więc umieszczenie wejścia i wyjścia w dwóch oddalonych od siebie pokojach jest najlepszym wyborem. Aby to znaleźć, obliczyć najdalszy pokój z przypadkowego pokoju. Następnie z tego pokoju znajdź najdalszy pokój. Nazywa się to określaniem średnicy wykresu, proszę go Google.