Wyszukiwanie ścieżki z zamkiem i kluczem?

Pracuję nad grą z mapami przypominającymi zamek i kluczowe łamigłówki . AI musi nawigować do celu, który może znajdować się za zamkniętymi czerwonymi drzwiami, ale czerwony klucz może znajdować się za zamkniętymi niebieskimi drzwiami i tak dalej ...

Ta łamigłówka jest podobna do lochu w stylu Zelda, jak na tym zdjęciu:

Aby dotrzeć do celu, musisz pokonać bossa, który wymaga przejścia przez dół, co wymaga zebrania pióra, które wymaga zebrania klucza

Lochy Zelda są zwykle liniowe. Muszę jednak rozwiązać problem w ogólnym przypadku. Więc:

• Cel może wymagać jednego z zestawu kluczy. Może więc potrzebujesz zdobyć czerwony lub niebieski klucz. Lub mogą być otwarte drzwi na dłuższą metę!
• Może istnieć wiele drzwi i kluczy w swoim rodzaju. Np. Na mapie może znajdować się wiele czerwonych kluczy, a ich zebranie zapewni dostęp do wszystkich czerwonych drzwi.
• Cel może być niedostępny, ponieważ odpowiednie klucze znajdują się za zamkniętymi drzwiami

Jak miałbym wyszukiwać ścieżki na takiej mapie? Jak wyglądałby wykres wyszukiwania?

Uwaga: ostatni punkt dotyczący wykrywania niedostępnych celów jest ważny; Na przykład * jest wyjątkowo nieefektywne, jeśli cel jest niedostępny. Chciałbym poradzić sobie z tym skutecznie.

Załóż, że AI wie, gdzie wszystko jest na mapie.

Standardowe wyszukiwanie ścieżek jest wystarczające - Twoje stany to Twoja bieżąca lokalizacja + Twoje aktualne zapasy. „przeprowadzka” to albo szatnia, albo ekwipunek. Nie ujęta w tej odpowiedzi, ale nie za dużo dodatkowego wysiłku, pisze dobrą heurystykę dla A * - może naprawdę przyspieszyć wyszukiwanie, woląc podnosić przedmioty niż oddalając się od niego, woląc odblokować drzwi w pobliżu celu poszukiwanie długiej drogi itp.

Ta odpowiedź zyskała wiele pozytywnych opinii od samego początku i zawiera wersję demonstracyjną, ale w przypadku znacznie bardziej zoptymalizowanego i wyspecjalizowanego rozwiązania należy również przeczytać odpowiedź „Robienie tego wstecz jest znacznie szybsze” /gamedev/ / a / 150155/2624

W pełni funkcjonalny dowód koncepcji JavaScript poniżej. Przepraszam za zrzut w postaci zrzutu kodu - faktycznie go zaimplementowałem, zanim przekonałem się, że to dobra odpowiedź, ale wydaje mi się dość elastyczny.

Na początek, myśląc o wyszukiwaniu ścieżek, pamiętaj, że dziedziczenie prostych algorytmów wyszukiwania ścieżek to:

• Szerokość Pierwsze wyszukiwanie jest tak proste, jak to tylko możliwe.
• Algorytm Djikstry jest podobny do pierwszego wyszukiwania szerokości, ale ma różne „odległości” między stanami
• A * to Djikstras, w którym masz „ogólne poczucie właściwego kierunku” dostępnego jako heurystyka.

W naszym przypadku po prostu kodowanie „stanu” jako „lokalizacji + ekwipunku” i „odległości” jako „użycia ruchu lub przedmiotu” pozwala nam użyć Djikstry lub A * do rozwiązania naszego problemu.

Oto rzeczywisty kod demonstrujący Twój przykładowy poziom. Pierwszy fragment jest tylko dla porównania - przejdź do drugiej części, jeśli chcesz zobaczyć ostateczne rozwiązanie. Zaczynamy od implementacji Djikstry, która znajduje właściwą ścieżkę, ale zignorowaliśmy wszystkie przeszkody i klucze. (Wypróbuj, możesz zobaczyć, że to tylko linie wykończenia, z pokoju 0 ​​-> 2 -> 3-> 4-> 6-> 5)

function Transition(cost, state) { this.cost = cost, this.state = state; }
// given a current room, return a room of next rooms we can go to. it costs 
// 1 action to move to another room.
function next(n) {
    var moves = []
    // simulate moving to a room
    var move = room => new Transition(1, room)
    if (n == 0) moves.push(move(2))
    else if ( n == 1) moves.push(move(2))
    else if ( n == 2) moves.push(move(0), move(1), move(3))
    else if ( n == 3) moves.push(move(2), move(4), move(6))
    else if ( n == 4) moves.push(move(3))
    else if ( n == 5) moves.push(move(6))
    else if ( n == 6) moves.push(move(5), move(3))
    return moves
}

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

    if (!nextStates.length) return ['did not find goal', history]

    var action = nextStates.pop()
    cost += action.cost
    var cur = action.state

    if (cur == goal) return ['found!', history.concat([cur])]
    if (history.length > 15) return ['we got lost', history]

    var notVisited = (visit) => {
        return visited.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
    };
    nextStates = nextStates.concat(next(cur).filter(notVisited))
    nextStates.sort()

    visited.push(cur)
    return calc_Djikstra(cost, goal, history.concat([cur]), nextStates, visited)
}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, 0)], []))

Jak dodajemy elementy i klucze do tego kodu? Prosty! zamiast każdego „stanu” zaczyna się tylko numer pokoju, teraz jest to krotka pokoju i nasz stan inwentarza:

 // Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }

Przejścia zmieniają się teraz z krotki (koszt, pokój) w kratę (koszt, stan), więc mogą kodować zarówno „przejście do innego pokoju”, jak i „podniesienie przedmiotu”

// move(3) keeps inventory but sets the room to 3
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b))
// pickup("k") keeps room number but increments the key count
var pickup = (cost, item) => {
    var n = Object.assign({}, cur)
    n[item]++;
    return new Transition(cost, new State(cur.room, n.k, n.f, n.b));
};

wreszcie wprowadzamy drobne zmiany związane z typem w funkcji Djikstry (na przykład nadal dopasowuje tylko numer pokoju docelowego zamiast pełnego stanu) i otrzymujemy pełną odpowiedź! Zauważ, że wydrukowany wynik najpierw idzie do pokoju 4, aby podnieść klucz, następnie idzie do pokoju 1, aby podnieść pióro, następnie idzie do pokoju 6, zabija bossa, a następnie idzie do pokoju 5)

// Now, each state is a [room, haskey, hasfeather, killedboss] tuple
function State(room, k, f, b) { this.room = room; this.k = k; this.f = f; this.b = b }
function Transition(cost, state, msg) { this.cost = cost, this.state = state; this.msg = msg; }

function next(cur) {
var moves = []
// simulate moving to a room
var n = cur.room
var move = room => new Transition(1, new State(room, cur.k, cur.f, cur.b), "move to " + room)
var pickup = (cost, item) => {
	var n = Object.assign({}, cur)
	n[item]++;
	return new Transition(cost, new State(cur.room, n.k, n.f, n.b), {
		"k": "pick up key",
		"f": "pick up feather",
		"b": "SLAY BOSS!!!!"}[item]);
};

if (n == 0) moves.push(move(2))
else if ( n == 1) { }
else if ( n == 2) moves.push(move(0), move(3))
else if ( n == 3) moves.push(move(2), move(4))
else if ( n == 4) moves.push(move(3))
else if ( n == 5) { }
else if ( n == 6) { }

// if we have a key, then we can move between rooms 1 and 2
if (cur.k && n == 1) moves.push(move(2));
if (cur.k && n == 2) moves.push(move(1));

// if we have a feather, then we can move between rooms 3 and 6
if (cur.f && n == 3) moves.push(move(6));
if (cur.f && n == 6) moves.push(move(3));

// if killed the boss, then we can move between rooms 5 and 6
if (cur.b && n == 5) moves.push(move(6));
if (cur.b && n == 6) moves.push(move(5));

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))	
return moves
}

var notVisited = (visitedList) => (visit) => {
return visitedList.filter(v => JSON.stringify(v) == JSON.stringify(visit.state)).length === 0;
};

// Standard Djikstra's algorithm. keep a list of visited and unvisited nodes
// and iteratively find the "cheapest" next node to visit.
function calc_Djikstra(cost, goal, history, nextStates, visited) {

if (!nextStates.length) return ['No path exists', history]

var action = nextStates.pop()
cost += action.cost
var cur = action.state

if (cur.room == goal) return history.concat([action.msg])
if (history.length > 15) return ['we got lost', history]

nextStates = nextStates.concat(next(cur).filter(notVisited(visited)))
nextStates.sort()

visited.push(cur)
return calc_Djikstra(cost, goal, history.concat([action.msg]), nextStates, visited)
o}

console.log(calc_Djikstra(0, 5, [], [new Transition(0, new State(0, 0, 0, 0), 'start')], []))

Teoretycznie działa to nawet w przypadku BFS i nie potrzebowaliśmy funkcji kosztu dla Djikstry, ale posiadanie kosztu pozwala nam powiedzieć „wybranie klucza jest łatwe, ale walka z bossem jest naprawdę trudna i wolelibyśmy wrócić 100 kroków zamiast walki z bossem, gdybyśmy mieli wybór ”:

if (n == 4 && !cur.k) moves.push(pickup(0, 'k'))
if (n == 1 && !cur.f) moves.push(pickup(0, 'f'))
if (n == 6 && !cur.b) moves.push(pickup(100, 'b'))

Do tyłu A * załatwi sprawę

Jak omówiono w tej odpowiedzi na pytanie dotyczące wyszukiwania ścieżki do przodu i do tyłu , wyszukiwanie ścieżki do tyłu jest stosunkowo prostym rozwiązaniem tego problemu. Działa to bardzo podobnie do GOAP (Planowanie działań zorientowanych na cel), planowanie efektywnych rozwiązań przy jednoczesnym minimalizowaniu bezcelowego zastanawiania się.

Na dole tej odpowiedzi opisuję, jak radzi sobie z podanym przez ciebie przykładem.

Szczegółowo

Ścieżka od miejsca docelowego do początku. Jeśli podczas szukania ścieżki natkniesz się na zamknięte drzwi, masz nową gałąź do odnajdywania ścieżki, która przechodzi przez drzwi tak, jakby była odblokowana, a główna gałąź nadal szuka innej ścieżki. Gałąź, która przechodzi przez drzwi, jakby była odblokowana, nie szuka już agenta AI - teraz szuka klucza, którego może użyć do przejścia przez drzwi. W przypadku A * nowa heurystyka to odległość do klucza + odległość do agenta AI, a nie tylko odległość do agenta AI.

Jeśli gałąź z odblokowanymi drzwiami znajdzie klucz, to dalej szuka agenta AI.

To rozwiązanie jest nieco bardziej skomplikowane, gdy dostępnych jest wiele wykonalnych kluczy, ale można odpowiednio rozgałęzić. Ponieważ gałęzie mają ustalone miejsce docelowe, nadal pozwala użyć heurystyki w celu zoptymalizowania wyszukiwania ścieżki (A *), a niemożliwe ścieżki zostaną prawdopodobnie szybko odcięte - jeśli nie ma możliwości obejścia zamkniętych drzwi, gałąź, która nie nie przechodzi szybko przez drzwi, a opcje szybko się kończą, a gałąź, która przechodzi przez drzwi i szuka klucza, trwa sama.

Oczywiście tam, gdzie dostępnych jest wiele realnych opcji (wiele kluczy, inne przedmioty do obejścia drzwi, długa ścieżka wokół drzwi), wiele gałęzi zostanie zachowanych, co wpłynie na wydajność. Ale znajdziesz też najszybszą opcję i będziesz mógł z niej skorzystać.

W akcji

W twoim przykładzie odnajdywanie ścieżek od celu do początku:

1. Szybko napotykamy drzwi bossa. Oddział A kontynuuje przejście przez drzwi, szukając teraz bossa do walki. Gałąź B pozostaje w pokoju i wkrótce wygaśnie, gdy stwierdzi, że nie ma wyjścia.

2. Oddział A znajduje bossa i teraz szuka Startu, ale napotyka otchłań.

3. Odgałęzienie A kontynuuje nad jamą, ale teraz szuka pióra i odpowiednio utworzy linię pszczoły w kierunku pióra. Utworzono gałąź C, która próbuje znaleźć sposób na obejście dołu, ale wygasa wkrótce, gdy nie będzie w stanie. To lub zostanie na chwilę zignorowane, jeśli heurystyka A ​​* stwierdzi, że Oddział A nadal wygląda najbardziej obiecująco.

4. Oddział A napotyka zamknięte drzwi i przechodzi przez zamknięte drzwi, jakby były odblokowane, ale teraz szuka klucza. Gałąź D kontynuuje także przez zamknięte drzwi, wciąż szukając pióra, ale wtedy będzie szukać klucza. Dzieje się tak, ponieważ nie wiemy, czy najpierw musimy znaleźć klucz, czy pióro, a jeśli chodzi o znalezienie ścieżki, Start może znajdować się po drugiej stronie drzwi. Oddział E próbuje znaleźć sposób na zamknięcie zamkniętych drzwi i kończy się niepowodzeniem.

5. Oddział D szybko znajduje pióro i nadal szuka klucza. Dozwolone jest ponowne przejście przez zamknięte drzwi, ponieważ wciąż szuka klucza (i działa w czasie do tyłu). Ale kiedy ma klucz, nie będzie w stanie przejść przez zamknięte drzwi (ponieważ nie mógł przejść przez zamknięte drzwi, zanim nie znalazł klucza).

6. Oddział A i D nadal konkurują, ale gdy oddział A dotrze do klucza, szuka pióra i nie uda mu się dosięgnąć pióra, ponieważ musi ponownie przejść przez zamknięte drzwi. Natomiast oddział D po dotarciu do klucza zwraca uwagę na Start i znajduje go bez komplikacji.

7. Oddział D wygrywa. Znalazł odwrotną ścieżkę. Ostateczna ścieżka to: Start -> Klucz -> Pióro -> Szef -> Cel.

Edycja : Jest napisane z punktu widzenia AI, która chce zbadać i odkryć cel, i nie zna wcześniej lokalizacji kluczy, zamków ani miejsc docelowych.

Po pierwsze, załóżmy, że AI ma jakiś ogólny cel. Np. „Znajdź szefa” w twoim przykładzie. Tak, chcesz to pokonać, ale tak naprawdę chodzi o znalezienie. Załóżmy, że nie ma pojęcia, jak dojść do celu, tylko że istnieje. I będzie wiedział, kiedy to znajdzie. Po osiągnięciu celu AI może przestać działać, aby rozwiązać problem.

Ponadto użyję tutaj ogólnego terminu „zamek” i „klucz”, nawet jeśli może to być przepaść i pióro. Tj. Pióro „odblokowuje” „zamek” otchłani.

Podejście do rozwiązania

Wygląda na to, że zaczynasz od sztucznej inteligencji, która była w zasadzie badaczem labiryntu (jeśli myślisz o swojej mapie jak o labiryncie). Eksploracja i mapowanie wszystkich miejsc, do których może się udać, byłaby głównym celem AI. Może być oparty wyłącznie na czymś prostym, na przykład: „Zawsze idź do najbliższej ścieżki, jaką widziałem, ale jeszcze nie odwiedziłem”.

Jednak podczas eksploracji pojawi się kilka zasad, które mogą zmienić priorytet ...

• Wymagałby znalezionego klucza, chyba że miałby już ten sam klucz
• Gdyby znalazł zamek, którego nigdy wcześniej nie widział, spróbowałby każdego klucza, który znalazł w tym zamku
• Jeśli klucz działał na nowym typie zamka, zapamiętuje typ klucza i typ zamka
• Gdyby znalazł zamek, który widział wcześniej i miał klucz, użyłby zapamiętanego typu klucza (np. Drugi znaleziony czerwony zamek, czerwony klucz działał wcześniej na czerwonym zamku, więc wystarczy użyć czerwonego klucza)
• Zapamięta lokalizację dowolnego zamka, którego nie może odblokować
• Nie musiałby pamiętać położenia odblokowanych zamków
• Za każdym razem, gdy znajdzie klucz i znał wszystkie wcześniej odblokowane zamki, natychmiast odwiedzi każdą z tych zablokowanych zamków i spróbuje je odblokować za pomocą nowego znalezionego klucza
• Kiedykolwiek odblokowuje ścieżkę, po prostu wraca do celu eksploracji i mapowania, priorytetem jest wkraczanie na nowy obszar

Uwaga na ten ostatni punkt. Jeśli musi wybrać między sprawdzeniem niezbadanego obszaru, który był widziany wcześniej (ale nie odwiedzonego), a niezbadanym obszarem za nowo odblokowaną ścieżką, priorytetem powinna stać się nowo odblokowana ścieżka. Prawdopodobnie tam są nowe klucze (lub zamki), które będą przydatne. Zakłada to, że zablokowana ścieżka prawdopodobnie nie będzie bezcelowym ślepym zaułkiem.

Rozwijanie pomysłu za pomocą „zamykanych” klawiszy

Możesz mieć klucze, których nie można zabrać bez innego klucza. Albo zablokowane klucze. Jeśli znasz swoje stare Colossal Caves, musisz mieć klatkę dla ptaków, aby złapać ptaka - czego później potrzebujesz na węża. Więc „odblokowujesz” ptaka za pomocą klatki (która nie blokuje ścieżki, ale nie można go podnieść bez klatki), a następnie „odblokowujesz” węża (który blokuje twoją ścieżkę) za pomocą ptaka.

Więc dodając kilka zasad ...

• Jeśli nie można zabrać klucza (jest zablokowany), wypróbuj każdy klucz, który już na nim masz
• Jeśli znajdziesz klucz, którego nie możesz odblokować, zapamiętaj go na później
• Jeśli znajdziesz nowy klucz, wypróbuj go na każdym znanym zablokowanym kluczu, a także na zablokowanej ścieżce

Nie będę nawet wdawał się w to, w jaki sposób noszenie pewnego klucza może negować działanie innego klucza (Colossal Caves, pręt straszy ptaka i musi zostać upuszczony, aby ptak mógł zostać podniesiony, ale jest potrzebny później, aby stworzyć magiczny most) .