Upewnij się, że labirynt na mapie domu z windami można rozwiązać?


13

W mojej grze widzimy podłogi domu z boku, a bohater może podnosić windy - winda albo idzie w górę (do następnej windy w górę), albo w dół (do następnej windy w dół), w zależności od strzałki jako pokazano, i zawsze są połączone dokładnie dwie windy. To jedyny sposób, w jaki bohater może poruszać się w pionie, chociaż może swobodnie poruszać się w poziomie. Mapa domu to losowa siatka 11 x 5 z różnymi przedmiotami i nieprzekraczalnymi ścianami po lewej stronie, po prawej stronie, a czasem w jednej z dwóch pozycji środkowych:

podnosi przykład

Moje pytanie: w jaki sposób mogę się upewnić, że mapa jest zawsze losowa, ale zawsze możliwa do rozwiązania i że bohater, zaczynając od lewej strony dolnej podłogi, zawsze może ją opuścić dowolną windą skierowaną do góry na najwyższym piętrze?

Do tego, co warto, używam języka Lua do programowania. Dzięki wielkie!

Odpowiedzi:


14

To, co chcesz zrobić, to utworzyć wykres , w którym każdy węzeł jest pozycją windy, a krawędzie między nimi oznaczają, że możesz tam chodzić / podnosić. Po utworzeniu wykresu możesz użyć dfs / bfs, aby sprawdzić, czy możesz dostać się z węzła początkowego do węzła końcowego.

Korzystając z powyższego przykładu, zrobiłem zdjęcie, jak będzie wyglądał wykres. Zielone kółka oznaczają, że jest tam winda, a zielone linie oznaczają, że możesz podróżować od węzła do węzła.

węzły


Dzięki, to bardzo przydatne! Powinienem był bardziej podkreślić w swoim pytaniu, że mapa musi być generowana przede wszystkim. Zastanawiam się teraz nad tym, czy może nie być łatwiej - zamiast generować w pełni losowe kombinacje podnoszenia / ściany w kółko i sprawdzać ich zdolność do rozwiązania - aby algorytm przechodził przez dom, tak jak zrobiłby to bohater i w ten sposób generuj losowe windy i drzwi (na przykład biorąc losowe odległości wind i skręty w lewo-prawo, a także dodając ściany). Jak w „Idź w prawo o 0, 4 lub 8 zakrętów; stwórz windę w górę, idź od 1 do 4 pięter ...”
Philipp Lenssen

@PhilippLenssen Jest to w zasadzie podejście do generowania labiryntu na wykresie metodą „losowego wyszukiwania od pierwszej głębokości”.
Kevin Reid,

5

Różnica między tym, co masz, a normalnym labiryntem polega na tym, że ma on niesąsiadujące ze sobą połączenia w pionie. Myślę, że powinieneś przyjrzeć się algorytmom generowania labiryntu opartym na grafie . Musisz po prostu mieć większy zestaw „sąsiednich pokoi” lub „możliwych ścian” niż zwykły labirynt 2D, w tym, że każda pionowo wyrównana para ogniw podłogowych z komórkami, która nie ma jeszcze windy pośredniej, sąsiaduje. Możesz modelować to jako wykres, na którym dodanie określonych krawędzi podnoszenia powoduje przypadkowe usunięcie innych możliwych krawędzi podnoszenia; niektóre algorytmy mogą być przez to mylone, ale nie inne.

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.