Świadomość sytuacyjna w poszukiwaniu ścieżki

Załóżmy, że musisz znaleźć najkrótszą ścieżkę przez loch, w którym niektóre przejścia są dostępne dopiero po zebraniu określonych przedmiotów, na przykład zamkniętych drzwi i kluczy.

Normalną reakcją jelit na słowa „najkrótsza ścieżka” byłoby oczywiście A *. Ale A * zawiódłoby w takim środowisku, ponieważ widzę wiele problemów z określeniem wiarygodnej heurystyki, a ponadto bardzo prawdopodobne jest, że węzeł musi być odwiedzany wiele razy, co również nie jest możliwe w konwencjonalnym A * i również utrudnić heurystykę.

To, o czym myślałem, to po prostu szukanie ścieżki od początku lochu do końca, ignorując zablokowane drzwi. Po znalezieniu tej ścieżki, dla każdych drzwi blokujących naszą drogę, dodatkowa ścieżka szukająca odpowiedniego klucza i z powrotem do drzwi będzie poszukiwana i przemierzana, zanim jeszcze dojdzie do drzwi. Ten sam system zostałby wykorzystany do obsługi sytuacji, w której ścieżka do klucza potrzebnego do otwarcia drzwi jest ponownie blokowana przez inne drzwi, które należy otworzyć najpierw.

Dużym problemem, jaki widzę w moim rozwiązaniu, jest to, że po znalezieniu wszystkich ścieżek, w tym ścieżek pozyskiwania przedmiotów, całkowity dystans pokonany przez agenta może nie być najmniejszy z możliwych, ponieważ mogą istnieć inne zablokowane drzwi, które są dalej od celu ale ich odpowiedni klucz jest znacznie łatwiej dostępny. A * zlekceważyłby te drzwi przy pierwszym przejściu, w którym zablokowane drzwi są po prostu ignorowane.

Jestem pewien, że nie jestem pierwszym, który spróbuje to rozwiązać i byłbym wdzięczny za wkład w rozwiązanie tego problemu.

Sposobem optymalnego radzenia sobie z taką sytuacją przy użyciu prostego A * jest rozszerzenie przestrzeni wyszukiwania. Wyobraź sobie, że istnieje osobna kopia lochu dla każdej kombinacji przedmiotów, które może nosić Twoja postać.

W każdej kopii lochu drzwi, które można przejechać, są dokładnie tymi, które można przejść za pomocą odpowiedniego zestawu przedmiotów. Jedynym sposobem na przejście z jednej kopii lochu do drugiej jest stanie na miejscu przedmiotu i podniesienie go.

Możesz rozszerzyć tę sztuczkę o inne zmiany stanu, takie jak przełączniki, które mogą otwierać i / lub zamykać drzwi. Możesz nawet pozwolić graczowi na upuszczanie przedmiotów, chociaż może to się skomplikować, ponieważ stan musi wtedy zawierać lokalizację każdego upuszczonego przedmiotu, znacznie zwiększając potencjalną przestrzeń poszukiwań.

Bardzo przydatną optymalizacją jest wstępne obliczenie najkrótszych ścieżek z każdych drzwi (właściwie każdej strony każdych drzwi) i przedmiotu do każdego innego dostępnego drzwi / przedmiotu, przy założeniu, że wszystkie drzwi są zamknięte . Po utworzeniu tych ścieżek możesz traktować każdą z nich jako ważoną krawędź na wykresie łączącym te znaczące lokalizacje ze sobą i ignorować wszystkie inne lokalizacje.

Załóżmy na przykład, że twój loch ma dziesięć drzwi i pięć kluczy. Wtedy będą 2 * 10 + 5 = 25 znaczących lokalizacji i 2 ^ 5 = 32 możliwe kombinacje przedmiotów, co daje w sumie 25 * 32 = 800 węzłów w pełnej przestrzeni wyszukiwania. Jest to bardzo skromna liczba, szczególnie biorąc pod uwagę, że duża część przestrzeni wyszukiwania prawdopodobnie będzie niedostępna.

Z rzeczywistego punktu widzenia: jeśli zmierzałeś z A do B i znalazłeś na drodze zamknięte drzwi D, zdasz sobie sprawę, że musisz znaleźć klucz D. Więc jeśli twoja AI jest tak nieświadoma, jak typowy człowiek , wymagałoby to poszukiwania klucza, który sam w sobie jest zestawem małych kroków w poszukiwaniu ścieżki. Z drugiej strony możesz chcieć, aby twoja sztuczna inteligencja wiedziała, zanim nawet spróbuje podążać ścieżką, że na tej trasie są zamknięte drzwi, i w takim przypadku prawdopodobnie będzie wiedział, gdzie znaleźć klucz.

Tak czy inaczej, problemem jest łączność na dwóch poziomach. Na poziomie „na ziemi” wiesz, że zawsze możesz bezpiecznie poruszać się w obrębie jednej niepodzielnej strefy ... to znaczy niepodzielnej przez zamknięte drzwi. Tutaj możesz swobodnie korzystać z bieżącej implementacji odnajdywania ścieżek A *. (W uproszczonym przykładzie możesz zobaczyć strefę jako pojedynczy pokój. Nie możesz dostać się do żadnego innego pokoju bez odblokowania drzwi. W rzeczywistości może to być cały region twojego lochu.) To podstawa twojego ruch bytu, ale to trochę jak chodzenie ze spuszczonymi oczami, zamiast najpierw badać obszar wokół ciebie - prawdopodobnie wejdziesz do latarni. Lub w tym przypadku zamknięte drzwi. Tak więc twoje mapy naziemne, na których działa Twój A *, muszą ograniczać ruch gracza tylko w obrębie bieżącej strefy.

Następnie znajduje się mapa wyższego poziomu, która jest bardziej topologiczna niż z natury topograficzna. Tak naprawdę nie zależy mu na szczegółach naziemnych przeszkód itp., Zależy tylko na łączności między strefami. Ta mapa topologiczna zawiera połączenia między nawet strefami, które obecnie mają między sobą zamknięte drzwi, ponieważ pokazuje idealną łączność wszystkich stref w lochu. Na krawędziach - każda reprezentuje drzwi między strefami - przechowuje klucz, który jest jeszcze potrzebny, jeśli taki istnieje, aby otworzyć te drzwi, w przeciwnym razie jest uważany za otwarty. Przeszukując ten wykres w poszukiwaniu najkrótszej ścieżki, należy ograniczyć tę znalezioną ścieżkę tylko do tras, które są już otwarte , sprawdzając dane na krawędziach podczas wyszukiwania. Łączność tutaj nie oznacza otwartości, a raczej potencjalnej otwartości.

Kiedy chcesz przejść do punktu znajdującego się w oddzielnej strefie, najpierw przeszukaj mapę wyższego poziomu, aby znaleźć ścieżkę. (Na tym poziomie można użyć A * lub dowolnego innego algorytmu najkrótszej ścieżki.) Po znalezieniu ścieżki ta mapa wyższego poziomu powinna również zawierać informacje na temat drzwi, których należy użyć, aby przejść z bieżącej strefy do drugiej strefy. Teraz w strefie lokalnej możesz wykonać sztuczną inteligencję na poziomie gruntu, aby przejść do tych drzwi. Po osiągnięciu drzwi twoja postać może przejść przez te drzwi / portal. Znajduje się teraz w strefie B. Jeśli jest to strefa docelowa, może użyć nawigacji na poziomie gruntu, aby przejść do klawisza. Jeśli tak nie jest, musisz powtórzyć krok pierwszy, aż dotrzesz do strefy docelowej.

Istnieje możliwość, że klucz jest poszukiwany za zamkniętymi drzwiami ... i że klucz do tych drzwi jest podobnie ... i tak dalej w ad nauseum. Jest to zasadniczo problem rozwiązywania zależności i istnieje kilka sposobów rozwiązania tego problemu, jednym z nich jest sieć Petriego. Zobacz ten znakomity papier.

PS. Jeśli tworzysz lochy w sposób proceduralny, możesz w ten sposób przechowywać informacje o porządkowaniu zależności, pod warunkiem, że znasz już pozycję początkową gracza.

Normalną reakcją jelit na słowa „najkrótsza ścieżka” byłoby oczywiście A *. Ale A * zawiódłoby w takim środowisku, ponieważ widzę wiele problemów z określeniem wiarygodnej heurystyki, a ponadto bardzo prawdopodobne jest, że węzeł musi być odwiedzany wiele razy, co również nie jest możliwe w konwencjonalnym A * i również utrudnić heurystykę.

Po pierwsze, dopuszczalna heurystyka nie musi być idealna. To musi być niedocenianie i musi być lepsze niż nic. Biorąc pod uwagę fakt, że pracujesz na rzeczywistych odległościach, wydaje się prawdopodobne, że A * przynajmniej przydałby się, a nawet jeśli heurystyka nie poprawiłaby znacznie wyszukiwania, prawdopodobnie nadal byłaby lepsza niż standardowe wyszukiwanie na szerokość lub podobne.

Po drugie, A * może odwiedzić węzeł tyle razy, ile chcesz. Pamiętaj, że A * nie jest algorytmem poszukiwania ścieżki, ale algorytmem wyszukiwania. Przeszukuje stany. W grach często utożsamiamy stan z pozycją, ponieważ nie obchodzi nas, w jaki sposób osiągnąłeś ten stan - jak krótka była droga do jego osiągnięcia. Jednak w takim problemie stan jest kombinacją pozycji oraz dowolnego innego istotnego stanu, takiego jak trzymane klucze.

Prawdą jest jednak, że powikłania te spowodują, że A * z dziedzin „bardzo wydajnych” do „odniesie sukces”, ale prawdopodobnie nie w wymaganym przeze mnie czasie. Jakiego czasu potrzebujesz? W rzeczywistości, dlaczego musisz to zrobić - czy naprawdę potrzebujesz najkrótszej ścieżki, czy może wystarczyłaby jakakolwiek rozsądna ścieżka?

To, o czym myślałem, to po prostu szukanie ścieżki od początku lochu do końca, ignorując zablokowane drzwi. Po znalezieniu tej ścieżki, dla każdych drzwi blokujących naszą drogę, dodatkowa ścieżka szukająca odpowiedniego klucza i z powrotem do drzwi byłaby poszukiwana i przemierzana, zanim jeszcze drzwi zostaną osiągnięte.

Łatwo jest udowodnić, że taki system byłby nieoptymalny. Od czego zaczniesz dodatkową ścieżkę? Jeśli od samego początku zmarnowałeś czas na zaplanowanie oryginalnej ścieżki do drzwi. Jeśli od końca, to umieszczenie klucza w pobliżu początku oznacza, że ​​ścieżka przemierza mapę dwa razy, gdy raz wystarczy. Jeśli spróbujesz obliczyć optymalne punkty scalania dla ścieżek do i od drzwi i oryginalnej ścieżki, da to optymalny wynik, ale będzie wymagało dużych zasobów ze względu na liczbę permutacji i trudności w tworzeniu heurystyki w celu uproszczenia wyszukiwania. Jeśli dodasz wiele kluczy do problemu, pojawi się problem Traveling Salesman, który nie jest łatwy do skutecznego rozwiązania.

Jeśli spróbuję rozluźnić kryterium „najkrótszej ścieżki”, spróbuję:

• Utwórz wykres wysokiego poziomu, który zawiera tylko ważne lokalizacje - kluczowe pozycje, pozycje drzwi, pozycje w zablokowanych obszarach i zwróć uwagę na odległości między nimi w linii prostej. Jeśli twoja mapa już dzieli się na pokoje lub inne dyskretne lokalizacje, to świetnie.
• Użyj A *, aby znaleźć ścieżkę przez ten wykres od początku do końca. Normalna heurystyczna kartezjańska odległość powinna wystarczyć, aby utrzymać ją w zarządzaniu.
• Teraz, dzięki tej uproszczonej ścieżce między tymi punktami, ponownie użyj A *, aby narysować ścieżkę niskiego poziomu od jednego punktu do drugiego.
• Połącz te ścieżki niskiego poziomu razem, tworząc całą swoją ścieżkę.

Gdy już zacznę działać, rozważę kilka drobnych optymalizacji - np. ważenie obszarów z kluczami w bardziej łagodny sposób, tak aby ścieżki niskiego poziomu byłyby bardziej podatne na małe objazdy w celu odebrania kluczy.

z podanych przez ciebie informacji myślę, że możesz użyć A * z niewielką modyfikacją. w normalnym algorytmie A * zaznaczasz każdy węzeł, gdy go przechodzisz, aby mieć pewność, że nigdy go nie przepuścisz. To jest dokładnie ta część, która sprawia problem z Przedmiotami. Kluczową zmianą jest zapamiętanie, jakie były twoje przedmioty, kiedy wcześniej przeszedłeś z węzła. oto kod sudo wyjaśniający, co mam na myśli:

if (nodestoCheck.notempty())
    newNode = nodeToCheck.first;
    if (notpassed(newNode.pos, newNode.items))
        if (room(newNode).containItem)
            add NewNode + room(NewNode).items 
        else
            do normal A* algorithm for new Node

za pomocą tego algorytmu najpierw zaczynasz sprawdzać wszystkie węzły bez elementu. istnieje duże prawdopodobieństwo, że twoja pierwsza grupa poszukiwaczy zostanie zablokowana przez niektóre drzwi. ale znajdzie klucz do tych drzwi, zanim przeszuka wszystkie pokoje. od tego klucza rozpoczyna się nowe wyszukiwanie z tym konkretnym kluczem. tym razem, gdy dotrzesz do drzwi, możesz je przejść. ta sama procedura trwa, dopóki nie znajdziesz wyjścia z lochu. jedynym problemem może być zużycie pamięci, ilekroć jest dużo drzwi i kluczy. chociaż nie będzie to problemem dla co najmniej 10 lub 15 kluczy.

Dlaczego po prostu nie użyjesz normalnego A * i zamodelujesz zamknięte drzwi jako regiony nieprzejezdne; po podniesieniu klucza (spacer po kafelku klucza?) zmienia to konkretne zamknięte drzwi w przejezdny region.

Oznacza to, że twoja wyszukiwarka ścieżek wybierze najkrótszą bezkluczykową trasę , a jeśli znajdzie klucze po drodze, włączy to do swojej ścieżki, jeśli to pomoże.

To wydaje mi się dość rozsądne. To nie jest idealne, ale jest to proste rozwiązanie problemu.