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

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:

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!

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.

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.