Losowo generuj ukierunkowany wykres na siatce

Próbuję losowo wygenerować ukierunkowany wykres w celu stworzenia gry podobnej do łamigłówek z pokemonami.
Zasadniczo to chcę generować losowo: http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory .

Muszę być w stanie ograniczyć rozmiar wykresu w wymiarze xiy. W przykładzie podanym w łączu byłby ograniczony do siatki 8x4.
Problem, na który wpadam, nie polega na losowym generowaniu wykresu, ale na losowym generowaniu wykresu, który mogę poprawnie odwzorować w przestrzeni 2d, ponieważ potrzebuję czegoś (jak skała) po przeciwnej stronie węzła, aby to zrobić wizualnie ma sens, gdy przestaniesz się ślizgać. Problem polega na tym, że czasami skała trafia na ścieżkę między dwoma innymi węzłami lub ewentualnie w innym węźle, co powoduje uszkodzenie całego wykresu.

Po omówieniu problemu z kilkoma osobami, które znam, doszliśmy do kilku wniosków, które mogą doprowadzić do rozwiązania.

• Uwzględnianie przeszkód na siatce jako części wykresu podczas jego tworzenia.
• Zacznij od w pełni wypełnionej siatki i po prostu narysuj losową ścieżkę i usuń bloki, które sprawią, że ta ścieżka będzie działać.

Problem polega na tym, aby dowiedzieć się, które z nich usunąć, aby uniknąć wprowadzenia dodatkowej, krótszej ścieżki. Myśleliśmy również, że algorytm programowania dynamicznego może być korzystny, chociaż żaden z nas nie jest zbyt wykwalifikowany w tworzeniu algorytmów programowania dynamicznego z niczego. Wszelkie pomysły lub referencje na temat tego, jak oficjalnie nazywa się ten problem (jeśli jest to oficjalny problem z grafem), byłyby najbardziej pomocne.

Oto kilka przykładów tego, co dotychczas osiągnąłem, po prostu losowo umieszczając bloki i generując wykres nawigacyjny z wybranego początku / końca. Idea (jak opisano w poprzednim linku) polega na tym, że zaczynasz od zielonej litery S i chcesz dostać się do zielonej litery F. Robisz to, przesuwając w górę / w dół / w lewo / w prawo i kontynuujesz ruch w wybranym kierunku, dopóki nie trafisz Ściana. Na tych zdjęciach szary to ściana, biały to podłoga, a fioletowa linia to minimalna długość od początku do końca, a czarne linie i szare kropki przedstawiają możliwe ścieżki.

Oto kilka złych przykładów losowo generowanych wykresów:

Oto kilka dobrych przykładów losowo generowanych (lub ręcznie modyfikowanych) wykresów:

Wydaje mi się również, że zauważyłem trudniejsze, gdy gra się w tę układankę, ponieważ mają wiele węzłów wysokiego stopnia na minimalnej ścieżce.

• jest lód, poruszysz się, chyba że uderzysz w skałę.
• jedynym sposobem zmiany kierunku jest uderzenie kamieniem.
• jeśli uderzysz w skałę, musisz zmienić kierunek.
• cykle są dobre, z oczywistych powodów.
• może istnieć wiele początków i wiele końców.

bardziej zaawansowane właściwości:

• komórki bez sąsiadujących skał są nieosiągalne (niektóre można przejść)
• ściany też są kamieniami, jeśli je usuniesz, możesz zdecydować się na zawijanie.
• możesz używać podsiatek jako wzorów („kafelki” 3x3, 3x4, 5x5 itd.)
• możesz nałożyć puzzle MxN na nieobrotowy obszar MxN i dodać kamień, aby przekierować go do środka.
• interesujący może być obrót lub symetria płytki
• możesz rozwinąć kafelek, wstawiając lodowate wiersze / kolumny

przykład:

S=start, E=end, o=rock, .=ice

3 . 2 o        3 . . 2 o         . . . . . o o
4 . . E   ~=   4 . . . E   ~=    . . . . . 2 E
o . . .        o . . . .         . . . . . . .
S . 1 o        S . . 1 o         S . . . . 1 o

przykład łączenia płytek:

3 . . 2 o       o 2 . . 3      3 . . 2 o 7 . . 6
4 . . . E   +   E . . . 4  =   4 . . . . . . . 5
o . . . .       . . . . o      o . . . . . . . o
S . . 1 o       o 1 . . S      S . . 1 o 8 . . E

może Ci się spodobać gra Tsuro , która używa losowych płytek do generowania losowej planszy.

Może inżynieria odwrotna może ci pomóc, jeśli masz na to ochotę.

Jeśli istnieje tylko jedno rozwiązanie każdego problemu, prawdopodobnie możesz wygenerować wykres oparty na unikalnej odpowiedzi. Nie będzie to wymagać programowania dynamicznego, a nawet pominięcia brutalnej siły i wyboru metodycznego generowania.

Możesz to zrobić przez:

1. Utrzymywanie gotowości wykresu MxN
2. tworzenie jednego / wielu rozwiązań
3. zadając sobie pytanie, czy jest to pojedynczy problem
4. jeśli istnieje wiele rozwiązań tego problemu, możesz powtórzyć powyższą procedurę w taki sposób, aby bieżąca iteracja nie hamowała innego rozwiązania.

Musisz jednak wybrać sposób zgodny ze złożonością problemu i rozmiarem problemu, który wygeneruje to pytanie. Nie szukaj brutalnej siły. Zamiast tego wypróbuj losowy algorytm. To może ci pomóc.

Co powiesz na inne podejście? Zacznij od pustego labiryntu i dodaj takie bloki:

1. Losowo blok początkowy i blok końcowy.
2. Wykonaj 1-3 „przesuwane” kroki w losowym (ale nie powracającym) kierunku i o losowej długości (*). Umieść blok po każdym kroku (aby zatrzymać slajd).
3. Znajdź najkrótszą drogę do wyjścia. Jeśli jest za mało segmentów (trudność na niskim poziomie), weź losowy segment ścieżki i podziel go blokiem. W przeciwnym razie umieść blok jak w kroku 1 i wyjdź.
4. Powtórz 1 ostrożnie (*): po wybraniu długości przesuwanego kroku ustaw go tak, aby wstawiany blok nie zamykał poprzedniej ścieżki.

Kończymy: znajdź najkrótszą trasę za pomocą podanego algorytmu. Zanotuj wszystkie używane komórki i zacznij losowo wypełniać resztę za każdym razem, upewniając się, że najkrótsza droga nie ulegnie skróceniu.

Jest zastrzeżenie na drugim etapie, kiedy nie można umieścić ostatniego bloku, aby nie przecinał on używanych ścieżek, ale widzę dwa rozwiązania tego: przesuń blok końcowy wcześniej lub cofnij kilka kroków i spróbuj ponownie.

I jeszcze jedna myśl dotycząca losowej długości przesuwnych kroków - możesz wybrać ją tak, aby blok umieszczony wcześniej był ponownie używany, o ile ścieżki się nie pokrywają.