Wyszukiwanie ścieżek na nierównej powierzchni planety


16

Moje pytanie brzmi: jakie byłoby najlepsze podejście do poszukiwania ścieżki na nierównej powierzchni planety?


Informacje podstawowe

Stworzyłem planetę z mapowania przemieszczeń 6 rzutowanych sfer. Płaszczyzny początkowo tworzyły sześcian, zanim zostały rzutowane na kształt kuli.

wprowadź opis zdjęcia tutaj

Zastanawiam się, czy można zastosować każdą „rzutowaną ścianę sześcianu” jako siatki i użyć prostego algorytmu A * w celu znalezienia najlepszej możliwej trasy. Chciałbym również wziąć pod uwagę wysokość przemieszczenia, aby ścieżka nie wspinała się góry itp. (Myślę, że to byłaby tylko heurystyka w ramach algorytmu A *). Inną sprawą jest to, że osiągnąłem ruch planetarny, wykorzystując silnik fizyki Unity3d, zastosuj grawitację w kierunku środka planety. Czy moje proponowane rozwiązanie wymagałoby niezależnej kontroli ruchu agentów w fizyce grawitacyjnej.

Aby lepiej sformułować moje pytanie, oto moje obecne ciało planetarne:

wprowadź opis zdjęcia tutaj


2
Możesz być zainteresowany tym filmem z Planetary Annihilation. Wygląda na to, że robią to samo, co owijanie świata z sześcianu i szukania ścieżki wokół niego. To naprawdę nie jest odpowiedź, ale widać, że używają A * wraz z innymi strategiami optymalizacji wyszukiwania ścieżek na kuli. Bit odnajdywania ścieżki zaczyna się o 24:30 .
MichaelHouse

@ Byte56 Dzięki za ten link naprawdę interesujące podejście do kalkulacji kosztów, nie mogę się doczekać, aby zobaczyć tę grę, gdy zakończy się!
Caius Eugene

Odpowiedzi:


12

Wygląda na to, że już odpowiedziałeś na swoje pytanie. * Jest prawdopodobnie najlepszym podejściem. Tak, oczywiście, można go używać w opisany sposób, w tym używając informacji o wysokości, aby uniknąć gór. Tak długo, jak jesteś w stanie uzyskać dostęp do informacji o dowolnej siatce na powierzchni twojego świata, nie ma powodu, dla którego nie możesz użyć jej w heurystyce A *.

Wreszcie, mylisz wyszukiwanie ścieżek z podążaniem ścieżką na końcu pytania. Szukanie ścieżki nie ma znaczenia dla grawitacji, chyba że dodasz ją jako heurystyczną, a ponieważ jesteś na powierzchni planety, grawitacja będzie zasadniczo taka sama na całej powierzchni. Wiele gier ma grawitację i ruch, nie widzę powodu, dla którego nie możesz.

Zasadniczo chcemy, aby mapa zmieniła kolor z czerwonego na niebieski, aby była taka sama na kuli, jak na sześcianie.

wprowadź opis zdjęcia tutaj

Ponieważ A * często zbliża się do swojego obecnego węzła, możesz łatwo stworzyć zestaw funkcji do uzyskiwania sąsiednich węzłów. Na przykład getXPlus(), getXMinus(), getZPlus()i tak dalej. Funkcje te zajmą bieżący węzeł i zwrócą węzeł w kierunku określonym przez nazwę funkcji.

Przez większość czasu funkcje te mogą po prostu zwiększać wartość i być wykonywane na krawędziach, które się zmienią.

Będziesz chciał zmapować powierzchnię sześcianu na układ współrzędnych 2D. Jakkolwiek to zrobisz, zależy od ciebie, nie muszą one ustawiać się w linii, po prostu nadaj każdej przestrzeni siatki unikalną współrzędną X, Y.

Teraz, kiedy znajdujesz się na krawędzi i otrzymujesz sąsiednie pole siatki, niekoniecznie będzie to po prostu zwiększanie współrzędnych. Musimy dowiedzieć się, do której twarzy się poruszamy i przełączyć się na współrzędne tej twarzy.

Na przykład uzyskanie współrzędnej XPlus zmieni zarówno współrzędne X, jak i Y, ponieważ przenosimy się na nowe pole siatki na nowej powierzchni. Zielona linia reprezentuje krawędź między dwiema ścianami.

wprowadź opis zdjęcia tutaj

Teraz są to tylko globalne współrzędne, może być łatwiej użyć wewnętrznego lokalnego układu współrzędnych z trzecim wymiarem, który reprezentuje ścianę sześcianu, na której aktualnie się znajdujesz.

Tak czy inaczej, musisz mieć unikalną współrzędną dla każdego pola siatki na powierzchni sześcianu. Przemieszczanie się między nimi będzie zależeć od sposobu implementacji układu współrzędnych. Musisz wiedzieć, gdzie ta współrzędna jest odwzorowana również na powierzchni kuli.

Wszystko to powinno ostatecznie zostać wyabstrahowane, abyś nawet o tym nie wiedział.


Pozdrawiam za odpowiedź. Myślę, że walczę z tym, że każdy samolot jest izolowaną siatką. Czy masz jakieś sugestie (lub dalsze czytanie) na temat tego, jak radzić sobie ze szwami, domyślam się, że będę matematycznie rozwinąć moją „kostkę”, połączyć wszystkie siatki i obliczyć ścieżkę za pomocą tego zestawu danych?
Caius Eugene

Naprawdę to tylko krawędzie, o które musisz się martwić. Można to łatwo rozwiązać za pomocą funkcji otoki (zawijanie kostki w funkcję otoki, która otacza świat ...). Możesz wyodrębnić sześcian w płaską powierzchnię, która się zawija. Utwórz funkcje do pobierania sąsiedniej przestrzeni siatki, getXPlus () ustawi siatkę w kierunku XPlus, nie ma znaczenia, czy znajdzie się na granicy między ścianami, funkcja po prostu zmieni ściany i zwróci odpowiednie informacje o siatce.
MichaelHouse

Jedyną niedokładnością w znajdowaniu ścieżki na złożonym sześcianie jest to, że wierzchołki są pochylone, a zatem krawędzie mają różne długości. Możliwe, że nie zrobi to zauważalnej różnicy w powstałych ścieżkach, w przeciwnym razie możesz po prostu wziąć pod uwagę długości.
danijar

1
Ważne jest, aby zrozumieć, że A * niekoniecznie działa w samolocie; działa na wykresie. Chociaż w obrębie każdej powierzchni sześcianu węzły są ułożone i połączone w siatkę, istnieją również połączenia węzłów wzdłuż krawędzi kostki.
jmegaffin 16.04.13

1
@ Byte56 Dzięki za świetną odpowiedź, zacząłem wymyślać rozwiązanie, ale natrafiłem na pewną przeszkodę. Może źle zrozumiałem. Zadałem pytanie na stackoverflow, ponieważ czułem, że jest to bardziej problem matematyczny / programowy stackoverflow.com/questions/16089074/...
Caius Eugene
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.