Jak znaleźć ścieżkę przez przeszkodę?


10

Jak najlepiej przedstawić następującą sytuację - agent ( @) musi dotrzeć do celu ( $). Ścieżka jest blokowana przez fosę ( ~~~). Dostępna jest grabie (lub inne urządzenie, takie jak buty do chodzenia po wodzie), które umożliwi przekroczenie przeszkody.

.....~~~...   . ground
...=.~~~...   = rake
.....~~~.$.   ~ water
.@...~~~...   @ agent
.....~~~...   $ goal

Jak prawidłowo znaleźć ścieżkę @do, $pod warunkiem że nie ma natychmiast dostępnej ścieżki? Czy moja ścieżka powinna nie tylko kosztować, ale także spełniać warunki wstępne?

UPD : Problem polega na tym, że cel nie jest dostępny, a grabie to tylko jeden z wielu możliwych obiektów na mapie. Pytanie brzmi zatem: „jak sprawić, by agent zrozumiał, że potrzebuje prowizji?”


Myślę, że powinieneś wyjaśnić swój przypadek użycia, ponieważ wpłynęłoby to na podejście stosowane do rozwiązania tego problemu. Na przykład, jeśli przypadkiem użycia jest obliczenie ścieżek dla wrogów, prawdopodobnie powinieneś najpierw sprawdzić, czy cel można obecnie osiągnąć, jeśli nie, aby wrogowie otrzymali prowizję (tj. Prowizja JEST celem), a następnie znajdź ścieżkę do pierwszego cel ponownie.
jhocking

Odpowiedzi:


6

Myślę o stosie celów, znalezienie ścieżki będzie musiało zostać opatrzone adnotacją :

  • Zacznij od celu get $
  • Spróbuj znaleźć ścieżkę do $- istnieje ścieżka z wymaganą możliwością chodzenia po wodzie.
  • Pchnij bramkę get waterwalking.
  • Stos bramek jest teraz get waterwalking, get $
  • Jakoś odkryć, że prowizja daje możliwość chodzenia po wodzie, zmieńmy nazwę na łódź.
  • Ścieżka do grabienia. Top cel osiągnięty, pop go ze stosu, celem jest get $.
  • Ścieżka do $- teraz mamy możliwości i możemy osiągnąć cel.

1
+1 Zrobiłem coś podobnego z moją grą i napisałem o tym jakiś czas temu w dziale Zadania Jednostek i poszukiwanie ścieżek .
MichaelHouse

@ byte66 nie obsługuje specjalnego przypadku, gdy istnieje ścieżka bez użycia prowizji, ale użycie prowizji powoduje krótszą ścieżkę
Ali1S232

@Gajet masz rację. Zgadnij, do tego potrzebne będzie inne podejście.
zzandy

1
To tylko kwestia dodania dodatkowych kosztów. Kiedy napotkasz wodę, dodaj koszt doprowadzenia przedmiotu idącego po wodzie na ścieżkę. A * pominie chodzenie po wodzie, aż stanie się najtańszą ścieżką.
MichaelHouse

3

Całe szukanie ścieżki jest po prostu szukaniem najkrótszej ścieżki na wykresie. aby rozwiązać problem, jedyną zmianą, którą musisz zastosować, jest dodanie dodatkowych krawędzi (reprezentujących ścieżkę, którą może wziąć łódź) i wykonanie prostego algorytmu znajdowania ścieżki. nie ma znaczenia, czy używasz BFS, Dijkstra czy A *, po prostu zaimplementuj zwykły algorytm wyszukiwania ścieżki z dodatkowymi krawędziami. aby uzyskać więcej informacji o wyszukiwaniu ścieżek na stronie wiki sprawdź wykres


+1 Uczyń swoją prowizję łączem jednokierunkowym z wodą, a także łącznikami łączącymi wodę z ziemią.
Laurent Couvidou

Nie mam jasnego zrozumienia, jak połączyć wyszukiwanie geometryczne i wyszukiwanie funkcji. Jak przejść od no path from @ to $do goto rake, bring it to water, place it, goto $.
zzandy

@zzandy podczas wyszukiwania ścieżki, dla każdego kafelka przechodzisz do najbliższych kafelków, jeśli to możliwe. wystarczy dodać warunek, że jeśli bieżący węzeł jest prowizją, możesz bezpośrednio dodać węzeł z drugiej strony rzeki, aby otworzyć listę.
Ali1S232

Ale co, jeśli możesz nosić urządzenie? Myślałem, że o to mu chodzi (i stąd moja odpowiedź.)
kaoD

Tak, mam na myśli, że urządzenie może (i musi) być przenoszone. @kaoD, twoja odpowiedź nie obejmuje kroku, kiedy agent wpadnie na pomysł, że potrzebuje prowizji.
zzandy

2

Zrobiłbym to z jakimś rozwiązaniem drzewa zachowań - ty podążasz do celu i zwracasz uwagę na wszystkie przeszkody, które blokowały twoje A *. Jeśli ci się nie uda, sprawdzisz, czy istnieją obiekty, które mogą pomóc pokonać te przeszkody, w takim przypadku ścieżka do tego obiektu. Powtarzać. Oznacza to, że agent musi spróbować dotrzeć do celu i ponieść porażkę, zanim wpadnie na pomysł użycia narzędzi, co może zająć trochę czasu, zwłaszcza jeśli istnieje ogromny świat płytek, które należy sprawdzić. Nie może jednak wydawać się zbyt nie na miejscu, aby agent zastanawiał się, jak rozwiązać problem.

Mogę sobie jednak wyobrazić prawdziwe, hardkorowe rozwiązanie. Dodaj kolejny wymiar do siatki wyszukiwania ścieżek. Tak więc w przypadku mapy 2D siatkę wyznaczania ścieżek tworzy się w 3D. W tym prostym przykładzie ten nowy wymiar miałby tylko głębokość dwa, ale w prawdziwej grze szybko stałby się duży.

Przy z = 0 mapujesz teren w normalnych warunkach, co oznacza, że ​​płytki wodne są uważane za nieprzejezdne.

Przy z = 1 odwzorowujesz teren tak, jak jest, mając prowizję, co oznacza, że ​​płytki wodne są uważane za możliwe do przejścia (ale jeśli masz na przykład płytki ścienne, mogą one pozostać twarde).

Znalezienie ścieżki to zwykła A * w wymiarach x i y, co oznacza, że ​​każda komórka siatki ma dostęp do swoich sąsiadów. Jednak w wymiarze Z A * NIE może się rozprzestrzeniać.

Z wyjątkiem tego, gdzie jest prowizja. Obiekt grabi działa jako otwór między z = 0 a z = 1 w siatce wyszukiwania ścieżki.

Oznacza to, że A * zalej wypełnienie na zewnątrz w z = 0, uderzy w wodę i zabraknie opcji - wtedy rozprzestrzeni się do z = 1 przez płytkę grabi, a przy z = 1 (tam, gdzie można chodzić po wodzie) znaleźć drogę do celu. Skutkuje to tym, że NPC bez wahania przesuwa się na prowizję, a następnie przesuwa najkrótszą ścieżkę do celu.


W moim przykładzie traktowałem prowizję bardziej jak „buty do chodzenia po wodzie”, co oznacza obiekt, który, jeśli go masz, umożliwia podróżowanie po kafelkach wody. Jeśli prowizja musi być „zbudowana” jako kawałek terenu i obejmuje ograniczoną liczbę płytek, które mogą lub nie wystarczą, aby dosięgnąć wody, problem jest trudniejszy. Moje rozwiązanie zezwala jednak na przedmioty jednorazowego użytku, jeśli wykonasz ruch w z = 1, automatycznie spadnie do z = 0.
Joar Jakobsson,
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.