Die KI verschiedene Wege zueinander gehen lassen

16

Ich habe ein Top-Down-2D-Spiel, bei dem die KI an den Rändern der Karte erscheint und zur Mitte rennt.

Ich verwende A * und ein Knotennetz, um den Pfad zu finden.

Im Moment spawnt die KI an einem Punkt am Rand der Karte und alle nehmen denselben Weg, der der kürzeste Weg zum Zentrum ist.

Jetzt möchte ich, dass sie überraschender und interessanter sind und unterschiedliche Wege zueinander gehen.

Ich kann mir sofort zwei Ideen dafür ausdenken, wollte aber wissen, ob es andere oder bessere Möglichkeiten gibt, die die Leute oft nutzen?

  1. Wenn ein Feind auftaucht und einen Pfad zur Mitte erzeugt, erhöhen Sie vorübergehend die Kosten aller Knoten auf diesem Pfad und verringern Sie sie im Laufe der Zeit langsam wieder. Dann wird die feindliche KI, die später auftaucht, gezwungen, einen breiteren Weg einzuschlagen.

  2. Der obige Ansatz wird dazu führen, dass AI nur einen immer breiteren Weg einschlägt und dennoch sehr vorhersehbar ist. Daher dachte ich, ich würde auch eine Reihe von Zwischenzielknoten auf der Karte einführen. Wenn die KI erscheint, wählen sie zufällig eines der Zwischenziele aus und gehen zuerst dorthin, bevor sie in die Mitte der Karte gehen. Wenn Sie dies mit dem oben genannten Ansatz kombinieren, die Kosten zu erhöhen, könnte dies ziemlich gut aussehen.

Welche Ansätze haben die Menschen gefunden, um die KI am besten dazu zu bringen, ihre Wege zu variieren, überzeugend und überraschend auszusehen?

TerryB
quelle

Antworten:

7

Ihre zweite Option weist auf einen grundlegenderen Ansatz hin: Stellen Sie sicher, dass sich Gegner Ihrem Spieler aus verschiedenen Richtungen nähern. Die Frage ist, wie weit sie reisen müssen, um sich auf Ihrem Player "zurechtzufinden"? Das Ideal dazu wäre eine Mischung aus

  • Dynamisches Erzeugen von Punkten, die die Position des Spielers eng umgeben (dh ihr folgen);
  • Was Nevermind vorgeschlagen hat, um die Wege zu diesen umgebenden Punkten mehr oder weniger zufällig zu ordnen.

Auf diese Weise können Sie sicherstellen, dass KI nicht unnötig lange Umwege benötigen, um eine realistische Pfadvariation zu erzielen, wenn Sie sich dem Spieler nähern.

Collaborative Diffusion macht implizit das, was Sie wollen, als Teil des Algorithmus. Die Implementierung ist jedoch nicht trivial.

Ingenieur
quelle
Kollaborative Diffusion ist nur eine Überflutung mit einer gewissen Gewichtung. Es ist einfach zu implementieren, vielleicht einfacher als A *. Es erfordert lediglich eine andere Sichtweise auf Ihre Welt - vielleicht eine nicht triviale konzeptionelle Verschiebung, aber kein Implementierungsproblem.
Es ist immer noch nicht trivial zu implementieren, da es sich bei der Verwaltung von KI-Entitäten um eine nicht standardmäßige Sichtweise handelt :)
Ingenieur
Danke Nick. Ich denke, dass das Einrichten einiger Wegpunkte, die den Spieler in der Mitte der Karte umgeben, der Hauptweg sein wird. Zum jetzigen Zeitpunkt bin ich nicht sicher, ob sie dynamisch generiert werden oder ob es sich um Handarbeit für jedes Level für meine spezielle Situation handelt. Danke noch einmal!
TerryB
12

Versuchen Sie zunächst, bei der Pfadfindung einen kleinen Zufallswert zum Gewicht jedes Knotens hinzuzufügen . Auf diese Weise sucht jeder Agent in einer etwas anderen Umgebung nach einem Pfad. Ich bin nicht sicher, ob dies in Ihrem Fall funktionieren wird, aber es sollte wirklich einfach sein, es zu versuchen.

Keine Ursache
quelle
Die Feinde werden am Ende wie Hühner rennen und in einer feinkörnigen Umgebung werden die Wege sowieso nicht so unterschiedlich sein. Es ist eine gute Ergänzung zu anderen Lösungen, aber keine Lösung für sich
Coyote
@Coyote Dies hängt stark von der Struktur des Navigationsnetzes und den Beziehungen zwischen Knotengewichten, Geschwindigkeiten und Zufallskomponenten ab. Aus diesem Grund habe ich die Antwort als Vorschlag, es zu versuchen, und nicht als eindeutige Antwort formuliert.
Nevermind
In der Tat :) Ich bin normalerweise ein Fan von Entropie. Aber das Endergebnis ist selten großartig.
Coyote
Eigentlich glaube ich, dass Nick Wiggills Antwort viel besser ist als meine. Aber irgendwie bekommt es nicht die Stimmen, die es verdient.
Nevermind
Es ist ... Aber deins ist das erste und einfachere ... wir könnten versuchen, es runter zu stimmen: P
Coyote
3

Angesichts der in den Kommentaren beschriebenen Einschränkung mag ich die Antwort von Nevermind jedoch:

  1. Der Algorithmus für eine einzelne Einheit zur Mitte zeichnet die zurückgelegte Gesamtstrecke auf.
  2. Ordnen Sie jeder nachfolgenden Einheit einen zufälligen und geringfügig längeren Abstand zu.
  3. Während Sie das A * für jede Einheit eingeben, fügen Sie ein zusätzliches Gewicht hinzu, das davon abhängt, wie nah Sie sich befinden und wie weit Sie reisen möchten. Das wäre wahrscheinlich so etwas wie (distanceToGoal) + Max(0, desiredDistance - distanceTravelled)).

Dies würde die Einheiten dazu bringen, weiter zu gehen, was wahrscheinlich ein anderer Weg ist, was dazu führen würde, dass sie möglicherweise andere Wege einschlagen.

Sie könnten es auch einfach zu Ihrem Starthuerestic für jede Einheit hinzufügen, aber der zufällige Bereich müsste wahrscheinlich ziemlich viel größer sein.

Jonathan Dickinson
quelle
2

Nick Wiggill wies darauf hin, dass es am einfachsten wäre, einen Kreis um das Ziel zu bilden.

  • Weisen Sie zufällig einen Punkt in der Nähe dieses Kreises als Wegpunkt zu.
  • Alle Pfade im Kreis vom Anfangspfad entfernen (oder den Wert dieser Punkte drastisch erhöhen)
  • Von diesem Wegpunkt gelangt man dann zum Ziel.

Der wichtige Teil ist, alle Pfade im Kreis für den ursprünglichen Wegpunkt zu entfernen, da Sie wahrscheinlich mit Gegnern enden würden, die den Kreis überqueren, um zu ihrem ursprünglichen Wegpunkt zu gelangen.

Daraus können Sie eine beliebige Variante erhalten, indem Sie mit mehreren Werten spielen, indem Sie sekundäre Wegpunkte in den Kreis in der Nähe des ursprünglichen usw. einfügen.

Kojote
quelle
Wenn Ihre Karte dies unterstützt, suchen Sie in diesem Kreis nach „interessanten“ Orten (Türen, Deckung, Bäume, Felsen, Gebäude; jeder Knoten mit einem gewissen taktischen Vorteil) und lassen Sie Ihre Feinde zuerst zu diesen Orten gehen, wenn sie verfügbar sind und nur hereinkommen die öffnen, wenn sie müssen. Dies sieht viel schlauer aus, als nur einen zufälligen Punkt am Rand des Kreises zu treffen.
DampeS8N
Danke Coyote, yep, ich werde mich wahrscheinlich für die Lösung von Nicks entscheiden und, wie von DampeS8N vorgeschlagen, einige wichtige Orte als Wegpunkte. Um das Problem zu vermeiden, dass die KI "den Kreis überquert", werde ich die Kosten für die Knoten im Kreis erheblich erhöhen, sodass A * hoffentlich
darum
2

Ihr Problem hierbei ist im Wesentlichen, dass A * ein Algorithmus zum Ermitteln der schnellsten Route zu einem Ziel ist. Wenn dies Ihr Hauptkriterium für einen guten Weg ist, ist es nicht verwunderlich, dass alle Ihre Akteure die gleichen Entscheidungen treffen.

Sie müssen lediglich Ihre Qualitätskriterien für den Pfad ändern, damit nicht nur der Faktor "Am kürzesten ist am besten" berücksichtigt wird. Das Element der Zufälligkeit spielt dabei eine Schlüsselrolle, jedoch nicht so sehr, dass es die Pfadfindungsintelligenz beeinträchtigt (dh die Akteure gehen auf dummen Umwegen zum Ziel).

Eine * -Pfadfindung ist von Natur aus naiv, da sie normalerweise voraussetzt, dass der Schauspieler die gesamte Route genau kennt, bevor er losfährt. Das wird immer unrealistisch aussehen. Die Lösung schlug vor, dass ausgewählte Zwischenziele einen Schritt davon entfernt sind - die KI versucht, näher an das Ziel heranzukommen, versucht jedoch nur in kleinen Abschnitten gleichzeitig zu navigieren (dies entspricht dem realen Leben, in dem Sie nur so weit navigieren können) Sie sehen, und wenn Sie den Pfad weiter durchqueren, können Sie weiter nach vorne sehen.

Ich würde vielleicht eine einfachere Sichtweise empfehlen. Behalten Sie beim Auffinden von Pfaden nicht nur den besten Pfad bei, den ich bisher gefunden habe. Sammeln Sie stattdessen einen Satz der besten 5 oder 10 Pfade. Verwenden Sie einen Schwellenwert, um offensichtliche Ausreißer zu verwerfen. Wenn beispielsweise der beste Pfad 20u durchquert, um zum Ziel zu gelangen, durchquert der nächstbeste 21u und der nächste danach 50u. Stellen Sie einen um 20% größeren Schwellenwert als den besten Pfad ein und verwerfen Sie den 50u-Pfad, da er dummerweise länger ist. Jetzt können Sie aus mehreren Pfaden auswählen. Durch die zufällige Auswahl dieser Pfade treffen Ihre Akteure unterschiedliche Entscheidungen.

Allerdings erhalten Sie diese Art von Informationen bei der Standard-A * -Suche nicht. Ich denke, Sie müssen den Algorithmus ändern oder etwas anderes verwenden, um die möglichen Pfade zu ermitteln.

MrCranky
quelle
1

Wenn Sie eine kleine Anzahl wiederkehrender Feinde (oder Feindtypen) haben, können Sie versuchen, ihnen Persönlichkeiten zu geben, die ihre Bewegungen beeinflussen. Sie müssen keine großen Dinge sein, nur Dinge, die hin und wieder auftauchen. Ein gutes Beispiel dafür sind die Geister von Pac-Man. Lassen Sie Ihr A * in mehrere Zwischenziele aufteilen. Vielleicht ist ein Feind wirklich dumm und geht leicht verloren, wenn er jeden dritten Knoten (außer direkt rückwärts) in eine zufällige Richtung steuert. Seien Sie kreativ.

Irgendein Typ
quelle