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

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ę 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.

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

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.