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.
źródło
Odpowiedzi:
bardziej zaawansowane właściwości:
przykład:
przykład łączenia płytek:
może Ci się spodobać gra Tsuro , która używa losowych płytek do generowania losowej planszy.
źródło
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:
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.
źródło
Co powiesz na inne podejście? Zacznij od pustego labiryntu i dodaj takie bloki:
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ą.
źródło