Wie kann ich A * -Agenten dazu bringen, andere Agenten zu meiden?

Ich implementiere einen Multi-Agent-A * -Algorithmus auf einer Kachelkarte. Agenten bewegen sich nur in der X- und Y-Achse. Ich vermeide Kollisionen zwischen ihnen, indem ich bei der Berechnung der Pfade überprüfe, wo sich die anderen befinden.

Es funktioniert einwandfrei, außer in Situationen, in denen Agenten dasselbe Plättchen aus verschiedenen Richtungen passieren müssen. In Situationen wie diesen wäre es eine optimale Lösung, wenn ein Agent auf die Übergabe des anderen Agenten wartet:

Auch wenn es keinen nördlichen Korridor gibt, schlägt die Wegfindung fehl.

Wie könnte ich einen solchen Algorithmus implementieren?

Sie können beginnen, indem Sie die Pfadfindung fehlschlagen lassen. Wählen Sie bei einem Fehler eine zufällige Zeit in der Zukunft, um die Pfadfindung erneut zu versuchen. Einige Low-Level-Netzwerkprotokolle funktionieren auf diese Weise recht gut. Sie müssen nur Pfade nacheinander erstellen und alle Kacheln, die ein Agent durchläuft, als verwendet markieren. Wenn weitere Pfade fehlschlagen, hilft der zufällige Zeitgeber beim Neustart, die neuen Pfadsuchen zu verteilen und Schleifenfehler aufzulösen.

Der zweite Teil Ihres Problems könnte gelöst werden, indem zwei Pfade zurückgegeben werden. Der erste Pfad ist die reguläre Rückkehr, auch wenn sie von einem Block fehlschlägt. Der zweite Pfad ist ein Pfad, der alle Agenten vollständig ignoriert. Anhand der Erkenntnisse aus diesen beiden Pfaden können Sie dann entscheiden, ob es besser ist, zu warten oder den langen Weg zu gehen. Die Heuristik für diese Entscheidung wird einige Arbeit in Anspruch nehmen, aber es ist besser, als überhaupt nichts zu versuchen.

In dem sehr schlimmen Fall, dass Ihre Agenten häufig durch einfach breite Korridore wie diese blockiert werden, müssen Sie möglicherweise sichere Stellen hinzufügen, an denen Agenten schnell auf ihren tatsächlichen Pfad zugreifen und auf ihn warten können (so dass der Agent dies nicht tut) Warten Sie und blockieren Sie einen Korridor.

Anstatt Ihr Problem zu lösen, können Sie hier Zitronen zubereiten und Limonade zubereiten.

Vor vielen Jahren arbeitete ein Freund von mir an einem sehr bekannten FPS, das genau das von Ihnen beschriebene Problem hatte: Ein eingeschränkter Bereich hatte eine Reihe von AI-Zeichen, die bestimmte gewünschte Positionen hatten, und der Pfadfindungsalgorithmus stieß ständig gegen sie in einander. Insbesondere würde der Spieler beispielsweise eine Granate in einen kleinen Raum voller Feinde werfen, und die KI-Charaktere in dem Bereich würden versuchen, zu ihrem Ausgang zu rennen, aber ineinander rennen und am Ende innehalten und sich umdrehen. jemanden schlagen, sich umdrehen und so weiter. Das sieht sehr unrealistisch aus.

Versuche, einen besseren Pfadfindungsalgorithmus zu entwickeln, der angesichts des knappen Rechenbudgets erfolgreich ausgeführt werden konnte, schlugen fehl. Anstatt das Problem der Wegfindung zu lösen, fügte mein Freund der KI einen sehr billigen Scheck hinzu: Wenn eine KI in kurzer Zeit zweimal auf eine andere KI gestoßen ist, hören Sie auf, den Ausgang zu finden, und gehen Sie stattdessen in Deckung. Was jetzt passiert, ist, dass der PC die Granate schlägt und sieht, wie ein Haufen Feinde zu den Ausgängen rennt. Diejenigen, die sich schlagen, drehen sich um und es sieht so aus, als würden sie feststellen, dass sie nicht raus können. Deshalb ducken sie sich und bedecken ihre Köpfe, bevor sie in die Luft fliegen. Dies sieht sowohl realistisch aus als auch ist für den Spieler sehr befriedigend.

Gibt es eine ähnliche Möglichkeit, den Nachteil Ihres kollisionserzeugenden Algorithmus in einen Vorteil umzuwandeln?

Ich finde es normalerweise am besten, das A * -Pfading mit anderen Formen der Pfadfindung für andere lokalisierte Szenarien zu erweitern. Die Vermeidung von Einheiten ist normalerweise eine davon, insbesondere in einer Welt, in der sich mehrere Agenten gleichzeitig bewegen und so dynamische Blocker erzeugen.

Im Allgemeinen kann eine Kantenfolgetechnik dafür funktionieren. Wenn Sie einem Pfad folgen oder einem Blocker begegnen, der nicht Teil der ursprünglichen Pfadberechnung war, wählen Sie im Grunde eine Richtung (im oder gegen den Uhrzeigersinn) und versuchen, den Blocker zu durchqueren, indem Sie ihn in dieser Richtung umfahren. Wenn dies nicht möglich ist, warten Sie, bis sich der Blocker aufgelöst hat (dies kann jedoch zu einem Deadlock führen).

Sie können auch die Fähigkeit für Einheiten implementieren, kooperativ zu pfaden. Das heißt, eine Einheit kann eine andere Einheit auffordern, sich leicht zur Seite zu bewegen, damit sie an der Blockiereinheit vorbeikommt. Dies funktioniert in einem Spiel mit Kacheln nicht gut, in dem Sie sich nur mit Kacheln bewegen können, da Sie in einfach breiten Korridoren wie in Ihrem Beispiel immer noch festsitzen können. In diesem Fall können Sie vorsehen, dass die Einheiten sich gegenseitig auffordern, die Position zu wechseln, was die meiste Zeit zu einer Auflösung führt. Gelegentlich führt dies jedoch dazu, dass Einheiten sich gegenseitig überholen.

"Vermeiden von Einheiten" ist ein weit verbreitetes Thema bei der Diskussion der Wegfindung in Spielen. Es gibt eine Menge Hits dafür. Insbesondere können Sie prüfen wollen , diese Frage auf dem „Strömungsfeld“ Wegfindung in Supreme Commander 2. RTSs in der Regel läuft in dieses Problem eines benutzt viel und löst es in allen möglichen interessanten Möglichkeiten.

Wenn Sie ein rundenbasiertes / tickbasiertes Bewegungssystem haben, können Sie ein 3D-Diagramm erstellen, in dem jeder Übergang den Agenten dahingehend bewegt, wie die Karte in Zukunft aussehen würde. Lassen Sie dann jeden Agenten die Kacheln beanspruchen, auf denen sie sich zu diesem Zeitpunkt in der Zukunft befinden würden, und markieren Sie sie als unzugänglich. Jeder Agent hat dann die zusätzliche Option, zum nächsten Häkchen zu springen, um auf dem dritten Weg durch das Diagramm zu wechseln. Dies ist schwieriger für Ihr System, sollte jedoch bessere Ergebnisse liefern als das zufällige Warten. Noch besser, wenn Sie 2 Agenten erlauben, miteinander zu kommunizieren, indem einer von ihnen die Nachricht "Ich möchte Sie überholen" sendet, wenn der kürzeste Weg durch diesen Agenten führt.

Wenn Sie einen Algorithmus wie A * verwenden, haben Sie den größten Spielraum beim Arbeiten mit der Kostenheuristik.

In diesem speziellen Fall könnten Sie die Heuristik anpassen, um die Kosten für Bewegungen zu erhöhen, die einen Agenten in die Nähe eines anderen Agenten bringen. Das Problem besteht darin, dass wahrscheinlich beide versuchen, die obere Route einzuschlagen, und Sie könnten dazu führen, dass sie oszillieren zwischen den Pfaden hin und her, während sie sich gegenseitig schließen, abhängig vom genauen Zeitpunkt.

Eine andere Möglichkeit besteht darin, geplante Routen von Agenten zu verfolgen und die Kosten entlang der geplanten Pfade anderer Agenten nach oben anzupassen. Dies ermöglicht es den Agenten effektiv, sich in begrenztem Umfang aufeinander abzustimmen. Das Hauptproblem hierbei ist, ob alle Routen blockiert sind und die Suche nach Pfaden für den zuletzt bewegten Agenten möglicherweise weiterhin fehlschlägt.

In dem Fall, dass es nur einen Pfad gibt, schlägt die Pfadsuche entweder fehl oder sie schreiten aufeinander zu, bis sie festsitzen.

Wenn beides nicht ausreicht, müssen Sie auch bei der Berechnung Ihrer Kosten den Überblick über die Zeit behalten. Die Kosten für den zweiten Agenten sollten der Zeit entsprechen, die der erste Agent für die Klärung benötigt, zuzüglich der normalen Traversalkosten. Auf diese Weise kann Ihr Agent korrekt entscheiden, wann er warten soll, anstatt den anderen Weg einzuschlagen.

Die Abstimmung des Timings kann erheblich aufwändiger sein, sodass sich die meisten Leute damit begnügen, das Ebenenlayout und die Kosten so lange zu ändern, bis die Dinge gut genug sind.

Normalerweise würde ich adivse Sie verwenden Lenkverhalten Probleme wie diese während der Pfadverfolgung zu lösen. Und vielleicht müssen Sie noch viel unternehmen, um Inspiration für das Gruppierungsverhalten zu erhalten. Leider ist es für einfache Bewegungen auf Fliesenbasis nicht direkt anwendbar.

Da Sie in den meisten Situationen bereits über eine funktionierende Kollisionsvermeidung verfügen, sollten Sie sich auf diese konzentrieren. Ich nehme an, Sie wiederholen die Wegfindung jedes Mal, wenn ein Agent umziehen möchte, oder ich kann nicht sehen, wie er auf andere reagiert, die sich während des Umzugs bewegen. Zweitens denke ich, dass diese Agenten freundlich zueinander sind.

Sie schlagen vor, dass ein Agent auf den anderen wartet, und ich rate Ihnen, genau das zu tun. Geben Sie den Agenten die Möglichkeit, auf die Pfade der anderen zuzugreifen, suchen Sie die erste Kachel Ihres eigenen Pfades, die nicht Teil des anderen Pfades ist, und navigieren Sie dorthin. Probleme mit dieser Technik können sein:

1. Wie entscheiden Sie, ob es einen anderen akzeptablen Weg um den anderen Agenten gibt oder nicht? Sie möchten nicht auf den anderen Agenten warten, wenn genügend Platz vorhanden ist, um ihn zu umgehen. Ein Pfadfindungsfehler, wenn Sie den anderen Agenten in Betracht ziehen, ist ein deutliches Zeichen für die Situation, die Sie beheben möchten. In dem Beispiel, das Sie angesprochen haben, liegt jedoch kein Pfadfindungsfehler vor. Sie können jedoch mit ein wenig Rechenaufwand entscheiden, ob der alternative Pfad A * den anderen Agenten nur in einem kleinen Kreis umgeht oder einen völlig anderen Pfad wie den nördlichen Korridor verwendet.

2. Ich weiß nicht, wie weit ein Agent während einer Runde / Operation reisen kann, aber wenn das nicht weit genug ist oder wenn sich alle Agenten parallel bewegen, würden beide Agenten entscheiden, am anderen Ende des Pfades zu warten. Dies kann behoben werden, indem dem anderen Agenten signalisiert wird, dass Sie seinen Pfad freigeben.

Eine der möglichen Lösungen wäre, die Kollision von Einheiten an so engen Stellen zu deaktivieren.

Zum Beispiel kollidieren im Starcraft-Spiel Arbeiter (SCVs, Sonden, Drohnen) nicht miteinander, wenn sie Kristalle abbauen.