Situationsbewusstsein bei der Wegfindung

Angenommen, Sie mussten den kürzesten Weg durch ein Verlies finden, in dem bestimmte Passagen erst geöffnet werden, nachdem bestimmte Gegenstände wie verschlossene Türen und Schlüssel gesammelt wurden.

Die normale Darmreaktion auf die Worte "kürzester Weg" wäre offensichtlich A *. Aber A * würde in einer solchen Umgebung versagen, da ich viele Probleme bei der Definition einer zuverlässigen Heuristik sehe und es außerdem sehr wahrscheinlich ist, dass ein Knoten mehrmals besucht werden muss, was auch bei herkömmlichem A * nicht möglich ist und auch wäre Machen Sie die Heuristik schwieriger.

Ich dachte nur daran, nach einem Weg vom Anfang des Verlieses bis zum Ende zu suchen und blockierte Türen zu ignorieren. Nachdem dieser Weg gefunden wurde, wird für jede der Türen, die uns den Weg versperren, ein zusätzlicher Weg gesucht und durchquert, bevor die Tür überhaupt erreicht ist. Das gleiche System würde verwendet, um eine Situation zu bewältigen, in der der Weg zu einem Schlüssel, der zum Öffnen einer Tür benötigt wird, erneut durch eine andere Tür blockiert wird, die zuerst geöffnet werden muss.

Ein großes Problem, das ich bei meiner Lösung sehe, besteht darin, dass nach dem Auffinden aller Pfade, einschließlich der Pfade für die Artikelerfassung, die vom Agenten zurückgelegte Gesamtstrecke möglicherweise nicht die kleinstmögliche ist, da möglicherweise andere blockierte Türen weiter vom Ziel entfernt sind aber haben ihren entsprechenden Schlüssel viel leichter verfügbar. Ein * hätte diese Türen beim ersten Durchgang vernachlässigt, bei dem blockierte Türen einfach ignoriert werden.

Ich bin sicher, dass ich nicht der erste bin, der versucht, dieses Problem zu lösen, und ich würde mich über Beiträge zu diesem Problem freuen.

Der Weg, um eine solche Situation mit einfachem A * optimal zu handhaben, besteht darin, den Suchraum zu erweitern. Stellen Sie sich vor, es gibt eine separate Kopie des Dungeons für jede Kombination von Gegenständen, die Ihr Charakter möglicherweise trägt.

In jeder Kopie des Dungeons sind die Türen, die passierbar sind, genau diejenigen, die mit den entsprechenden Gegenständen passiert werden können. Die einzige Möglichkeit, von einer Dungeon-Kopie zur nächsten zu gelangen, besteht darin, sich an die Position eines Gegenstands zu stellen und ihn aufzuheben.

Sie können diesen Trick um andere Statusänderungen erweitern, z. B. Schalter, mit denen Türen geöffnet und / oder geschlossen werden können. Sie können dem Spieler sogar erlauben, Gegenstände fallen zu lassen, obwohl dies kompliziert werden kann, da der Status dann die Position jedes fallengelassenen Gegenstands enthalten muss, was den potenziellen Suchraum enorm vergrößert.

Eine sehr nützliche Optimierung besteht darin, die kürzesten Wege von jeder Tür (tatsächlich jeder Seite jeder Tür) und jedem Gegenstand zu jeder anderen erreichbaren Tür / jedem Gegenstand vorab zu berechnen, vorausgesetzt, alle Türen sind verriegelt . Sobald Sie diese Pfade haben, können Sie sie einfach als gewichtete Kante in einem Diagramm behandeln, das diese wichtigen Positionen verbindet miteinander verbindet, und alle anderen Positionen ignorieren.

Angenommen, Ihr Dungeon hat zehn Türen und fünf Schlüssel. Dann gibt es 2 * 10 + 5 = 25 signifikante Positionen und 2 ^ 5 = 32 mögliche Elementkombinationen für insgesamt 25 * 32 = 800 Knoten im gesamten Suchraum. Dies ist eine sehr bescheidene Zahl, insbesondere angesichts der Tatsache, dass ein Großteil des Suchraums wahrscheinlich nicht erreichbar ist.

Aus realer Sicht: Wenn Sie von A nach B gehen und eine verschlossene Tür D auf Ihre Weise finden würden, würden Sie erkennen, dass Sie Schlüssel D finden müssen. Wenn Ihre KI also so wenig weiß wie der typische Mensch Dies würde das Suchen nach dem Schlüssel beinhalten, bei dem es sich um eine Reihe winziger Schritte zur Wegfindung an und für sich handelt. Auf der anderen Seite möchten Sie vielleicht, dass Ihre KI bereits vor dem Versuch eines Pfades weiß, dass sich auf dieser Route eine verschlossene Tür befindet, und in diesem Fall wird sie wahrscheinlich auch wissen, wo sich der Schlüssel befindet.

In beiden Fällen geht es um Konnektivität auf zwei Ebenen. Auf der Ebene "am Boden" wissen Sie, dass Sie sich immer sicher innerhalb einer ungeteilten Zone bewegen können ... also ungeteilt durch verschlossene Türen. Hier können Sie Ihre aktuelle A * -Pfadfindungsimplementierung frei verwenden. (In einem vereinfachten Beispiel könnten Sie eine Zone als einen einzelnen Raum sehen. Sie können keinen anderen Raum erreichen, ohne eine Tür aufzuschließen. In Wirklichkeit könnte es sich um eine ganze Region Ihres Dungeons handeln.) Dies ist das Fundament Ihres Entitätsbewegung, aber es ist ein bisschen so, als würde man mit niedergeschlagenen Augen herumlaufen, anstatt zuerst den Bereich um Sie herum zu überblicken - Sie werden wahrscheinlich auf einen Laternenpfahl stoßen. Oder in diesem Fall eine verschlossene Tür. Daher müssen Ihre Karten auf Bodenhöhe, auf denen Ihr A * ausgeführt wird, den Spieler auf Bewegungen nur innerhalb der aktuellen Zone beschränken.

Als nächstes gibt es eine Karte auf höherer Ebene, die eher topologischer als topografischer Natur ist. Es kümmert sich nicht wirklich um die Details von Hindernissen vor Ort und so weiter, sondern nur um die Konnektivität zwischen Zonen. Diese topologische Karte enthält Verbindungen zwischen geraden Zonen, zwischen denen sich derzeit eine verschlossene Tür befindet, da sie die ideale Konnektivität aller Zonen in Ihrem Dungeon zeigt. In den Kanten - jede repräsentiert eine Tür zwischen den Zonen - wird gespeichert, welcher Schlüssel noch benötigt wird, um diese Tür zu öffnen, andernfalls wird sie als offen betrachtet. Wenn Sie dieses Diagramm nach dem kürzesten Pfad durchsuchen, sollte dieser gefundene Pfad nur auf bereits geöffnete Routen beschränkt sein , indem die Daten an den Rändern während der Suche überprüft werden. Konnektivität bedeutet hier keine Offenheit, sondern potenzielle Offenheit.

Wenn Sie sich zu einem Punkt bewegen möchten, der in eine separate Zone fällt, durchsuchen Sie zuerst Ihre übergeordnete Karte, um einen Pfad zu finden. (Ein * oder ein anderer Algorithmus für kürzeste Pfade kann auf dieser Ebene verwendet werden.) Sobald Sie einen Pfad gefunden haben, sollte diese Karte auf höherer Ebene auch Informationen darüber enthalten, welche Tür Sie verwenden müssen, um von Ihrer aktuellen Zone in die andere Zone zu gelangen. Jetzt können Sie in der lokalen Zone eine bodennahe KI ausführen, um zu dieser Tür zu navigieren. Sobald die Tür erreicht ist, kann Ihr Charakter durch diese Tür / dieses Portal gehen. Er befindet sich jetzt in Zone B. Wenn dies die Zielzone ist, kann er die Bodennavigation verwenden, um zur Taste zu gelangen. Ist dies nicht der Fall, müssen Sie Schritt 1 wiederholen, bis Sie die Zielzone erreicht haben.

Es besteht die Möglichkeit, dass sich ein gesuchter Schlüssel selbst hinter einer verschlossenen Tür befindet ... und dass der Schlüssel zu dieser Tür ebenfalls ... ist und so weiter ad nauseum. Dies ist im Wesentlichen ein Problem der Abhängigkeitsauflösung, und es gibt einige Möglichkeiten, dies zu beheben, darunter Petri-Netze. Sehen Sie das ausgezeichnete Papier.

PS. Wenn Sie Ihren Dungeon prozedural erstellen, können Sie dabei Informationen zur Abhängigkeitsreihenfolge speichern, sofern Sie die Startposition des Spielers bereits kennen.

Die normale Darmreaktion auf die Worte "kürzester Weg" wäre offensichtlich A *. Aber A * würde in einer solchen Umgebung versagen, da ich viele Probleme bei der Definition einer zuverlässigen Heuristik sehe und es außerdem sehr wahrscheinlich ist, dass ein Knoten mehrmals besucht werden muss, was auch bei herkömmlichem A * nicht möglich ist und auch wäre Machen Sie die Heuristik schwieriger.

Erstens muss eine zulässige Heuristik nicht perfekt sein. Es muss nur eine Unterschätzung sein und es muss besser sein als nichts. Angesichts der Tatsache, dass Sie mit tatsächlichen Entfernungen arbeiten, ist es wahrscheinlich, dass A * zumindest hilfreich ist, und selbst wenn die Heuristik die Suche nicht wesentlich verbessert hat, ist sie wahrscheinlich immer noch besser als eine Standard-Breitensuche o.ä.

Zweitens kann A * einen Knoten so oft besuchen, wie Sie möchten. Denken Sie daran, dass A * kein Pfadfindungsalgorithmus, sondern ein Suchalgorithmus ist. Es durchsucht Zustände. In Spielen setzen wir einen Zustand oft mit einer Position gleich, weil es uns egal ist, wie Sie diesen Zustand erreicht haben - wie kurz der Weg dorthin war. Bei einem solchen Problem ist der Status jedoch eine Kombination aus der Position und jedem anderen relevanten Status, z. B. gehaltenen Tasten.

Es ist jedoch wahr, dass diese Komplikationen A * von den Bereichen "sehr effizient" zu "erfolgreich" bewegen werden, aber wahrscheinlich nicht in der von mir geforderten Zeitspanne. Was ist der Zeitrahmen, den Sie benötigen? Warum müssen Sie das tun - brauchen Sie wirklich den kürzesten Weg oder würde ein vernünftiger Weg ausreichen?

Ich dachte nur daran, nach einem Weg vom Anfang des Verlieses bis zum Ende zu suchen und blockierte Türen zu ignorieren. Nachdem dieser Weg gefunden wurde, wird für jede der Türen, die uns den Weg versperren, ein zusätzlicher Weg gesucht und durchquert, bevor die Tür überhaupt erreicht ist.

Es ist leicht zu beweisen, dass ein solches System nicht optimal wäre. Wo würden Sie den zusätzlichen Pfad beginnen? Wenn von Anfang an, dann haben Sie Ihre Zeit damit verschwendet, den ursprünglichen Weg zur Tür zu planen. Wenn am Ende ein Schlüssel in der Nähe des Starts platziert wird, bedeutet dies, dass der Pfad die Karte zweimal durchquert, wenn einmal ausreichen würde. Wenn Sie versuchen, optimale Zusammenführungspunkte für die Pfade zur und von der Tür und den ursprünglichen Pfad zu berechnen, führt dies zu einem optimalen Ergebnis, ist jedoch aufgrund der Anzahl der Permutationen und der Schwierigkeit, eine Heuristik zur Vereinfachung der Suche zu erstellen, ressourcenintensiv. Wenn Sie dem Problem mehrere Schlüssel hinzufügen, liegt das Problem des reisenden Verkäufers vor, das nicht einfach effizient zu lösen ist.

Was ich versuchen würde, wenn es möglich ist, das Kriterium des kürzesten Weges zu lockern, ist Folgendes:

• Erstellen Sie ein übergeordnetes Diagramm, das nur wichtige Positionen enthält - Schlüsselpositionen, Türpositionen, Positionen in gesperrten Bereichen, und notieren Sie die geradlinigen Abstände zwischen ihnen. Wenn sich Ihre Karte bereits in Räume oder andere diskrete Orte aufteilt, ist das großartig.
• Verwenden Sie A *, um einen Pfad durch dieses Diagramm vom Anfang bis zum Ende zu finden. Die normale kartesische Distanzheuristik sollte ausreichen, um sie überschaubar zu halten.
• Verwenden Sie nun mit diesem vereinfachten Pfad zwischen diesen Wegpunkten erneut A *, um einen Pfad auf niedriger Ebene von einem Wegpunkt zum nächsten zu zeichnen.
• Verbinden Sie diese Pfade auf niedriger Ebene, um Ihren gesamten Pfad zu bilden.

Sobald ich das zum Laufen gebracht habe, würde ich einige kleinere Optimierungen in Betracht ziehen - z. Gewichtung der Bereiche mit Schlüsseln milder, so dass die Pfadbildung auf niedriger Ebene mit größerer Wahrscheinlichkeit kleine Umwege zum Sammeln von Schlüsseln macht.

Mit den von Ihnen angegebenen Informationen können Sie A * mit nur einer kleinen Änderung verwenden. In einem normalen A * -Algorithmus markieren Sie jeden Knoten beim Überfahren, um sicherzustellen, dass Sie ihn nie wieder passieren. Das ist genau der Teil, der Probleme mit den Gegenständen macht. Die Schlüsseländerung besteht darin, sich daran zu erinnern, was Ihre Elemente waren, als Sie zuvor von einem Knoten übergeben wurden. Hier ist ein Sudo-Code, der erklärt, was ich meine:

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

Mit diesem Algorithmus überprüfen Sie zunächst alle Knoten ohne Element. Es besteht eine hohe Wahrscheinlichkeit, dass Ihre erste Suchgruppe durch einige Türen blockiert wird. Aber es wird einen Schlüssel für diese Tür finden, bevor es alle Räume durchsucht. Von diesem Schlüssel aus starten Sie eine neue Suche mit diesem bestimmten Schlüssel. Dieses Mal, wenn Sie die Tür erreichen, können Sie daran vorbeikommen. Die gleiche Routine wird fortgesetzt, bis Sie den Weg aus dem Dungeon finden. Das einzige Problem kann der Speicherverbrauch sein, wenn viele Türen und Schlüssel vorhanden sind. obwohl es für mindestens 10 oder 15 Schlüssel kein Problem sein wird.

Warum verwenden Sie nicht einfach normales A * und modellieren verschlossene Türen als unpassierbare Bereiche? Sobald Sie den Schlüssel abholen (auf dem Schlüsselplättchen gehen?), verwandelt sich diese bestimmte verschlossene Tür in einen passablen Bereich.

Dies bedeutet, dass Ihr Pfadfinder die kürzeste schlüssellose Route wählt. Wenn er unterwegs Schlüssel findet, nimmt er diese in seinen Pfad auf, wenn dies hilft.

Das erscheint mir ziemlich vernünftig. Es ist nicht perfekt, aber es ist eine einfache Lösung für das Problem.