Wie baue ich eine „Verkehrs-KI“ auf?

In einem Projekt, an dem ich gerade arbeite, gibt es viel "Verkehr" im Sinne von Autos, die sich auf Straßen bewegen, Flugzeugen, die sich um ein Vorfeld bewegen usw.

Ab sofort werden die verfügbaren Pfade vorberechnet, sodass Knoten automatisch für Kreuzungen generiert werden, die selbst durch Kanten miteinander verbunden sind. Wenn ein Charakter / Agent in die Welt kommt, beginnt er an einem bestimmten Knoten und findet mithilfe eines einfachen A * -Algorithmus einen Pfad zu einem Zielknoten. Der Agent folgt dem Pfad und erreicht schließlich sein Ziel. Bisher kein Problem.

Jetzt muss ich den Agenten ermöglichen, Kollisionen zu vermeiden und komplexe Verkehrssituationen zu bewältigen. Da ich neu auf dem Gebiet der KI bin, habe ich einige Artikel zum Lenkverhalten nachgeschlagen, aber festgestellt, dass sie zu niedrig sind. Mein Problem besteht weniger in der tatsächlichen Kollisionsvermeidung (was in diesem Fall ziemlich einfach ist, weil die Agenten genau definierten Pfaden folgen), sondern in Situationen, in denen ein Agent eine Sackgasse verlässt, während ein anderer genau dieselbe eingeben möchte. Oder zwei Agenten, die sich zu einem Engpass treffen, bei dem jeweils nur ein Agent passieren kann, beide ihn jedoch bestehen müssen (entsprechend der zuvor ermittelten optimalen Route), und sie müssen einen Weg finden, um den anderen zuerst passieren zu lassen. Der Hauptaspekt des Problems wäre also die Vorhersage der Verkehrsbewegung, um Dead-Locks zu vermeiden.

Schwer zu beschreiben, aber ich denke du verstehst was ich meine. Haben Sie Empfehlungen für mich, wo ich anfangen soll zu suchen? Irgendwelche Papiere, Beispielprojekte oder ähnliche Dinge, die mir den Einstieg erleichtern könnten?

Ich schätze Ihre Hilfe!

Es gibt so viele Möglichkeiten, dieses Problem anzugehen, dass ich Schwierigkeiten habe, hier eine anständige und umfassende Antwort zu geben. Aber hier sind einige wichtige Designpunkte.

• Sie erstellen hier eine Agentensimulation. Die Wegfindung ist nur eine Eingabe in das System - der Agent hat ein Ziel, und die Wegfindung ist nur eine Möglichkeit, dieses Ziel zu erreichen. In Wirklichkeit hat der Agent zwei Ziele: Das wichtigste Ziel eines Fahrers ist "Don't Crash", gefolgt von "Get Where I Wanted Go".

• Ihre Systeme sollten auf realen Parallelen aufbauen. Der Grund, warum die meisten Straßen zwei oder mehr Fahrspuren haben, ist, dass es mit diesem System viel einfacher ist, den Verkehr zu organisieren, und niemand viel nachdenken muss. In einem einspurigen Szenario müssen die Fahrer verschiedene Probleme lösen:

  Erkennung - Erkennen, dass Sie und das entgegenkommende Auto abstürzen, wenn Sie einander nicht ausweichen

  Reaktion - Verlangsamung und Eintritt in eine Verhandlungsphase.

  Verhandlung - einer der Fahrer muss die Führung übernehmen, der andere muss nachgeben. Die Regeln, wie dies entschieden werden soll, sind vage, aber im Grunde möchten Sie etwas, bei dem ein Fahrer willkürlich (oder basierend auf einer Heuristik über die Anzahl der Autos in die andere Richtung) entscheidet, Priorität zu haben. Beispiel: A hat zum Zeitpunkt 1 Priorität, B sieht, dass A Priorität hat, und gibt nach (indem es aus dem Weg geht und anhält). Wenn sowohl A als auch B versuchen, Priorität einzunehmen, sollten sie beide anhalten, eine zufällige Zeit warten (oder sich gegenseitig signalisieren) und es erneut versuchen. Irgendwann wird einer dem anderen nachgeben.

  Das Schöne an dieser Implementierung ist, dass künstliche Warteschlangen oder andere gefälschte Konstrukte vermieden werden müssen. Die Verhandlungen werden unter Berücksichtigung der tatsächlichen Wahrnehmung geführt. Sobald sich beide Parteien in der Verhandlungsphase befinden, kann jede bedeutende Vorwärtsbewegung leicht als Versuch erkannt werden, Priorität zu erlangen. Es sollte auch angemessen auf den Benutzer reagieren, der sich höchstwahrscheinlich nicht an gute Fahrregeln hält.

• Das Schlimmste annehmen. Selbst in einem perfekten System können merkwürdige Situationen auftreten, und Ihre Schauspieler sollten vernünftig handeln. Dies ist umso wahrscheinlicher, wenn der Spieler stören kann (künstliche Sperrung von Bereichen usw.). Oft ist das vollständige Anhalten die einzig sinnvolle Reaktion (Stillstand!). Das Drehen an Ort und Stelle oder offensichtlich ein gebrochener Zustand ist ein Fehler der KI. Insgesamt anzuhalten ist zumindest in der Realität plausibel.

  Je näher Sie die KI Ihres Schauspielers an der einfachen Logik der realen Welt modellieren, desto einfacher wird es, überzeugende KI zu erstellen. Echte Menschen halten nicht an und pendeln nicht hin und her, wenn sie ihr Ziel nicht erreichen können. Wenn die einzige Straße zum Ziel der KI blockiert ist, sollten sie dies erkennen und eine Antwort wählen (insgesamt anhalten, aufgeben und nach Hause fahren, aufgeben und woanders fahren).

• Ebenenverhalten, um das zu erhalten, was Sie wollen. Denken Sie daran, 1. Ziel ist es nicht, zum Absturz zu bringen. Ausweichlogik (Lenklogik) sollte also immer die Handlungen des Fahrers dominieren. Überlagern Sie die Richtungslogik, die aus der Wegfindung stammt ("Ich möchte an der nächsten Kreuzung rechts abbiegen"). Überlagern Sie diese gelegentliche Neubewertung von Pfaden mit übergeordneter Logik ("gehe lieber vorwärts, aber wenn ich keine Fortschritte mache, erlaube einen neuen Pfad, der eine Kehrtwende beinhaltet").

• Wegfindung kommt aus dem Gedächtnis, aber Situationsbewusstsein basiert auf Wahrnehmung. Versuchen Sie nicht, Ihre Agenten perfekt zu machen. Sie kennen den Weg von zu Hause ins Büro, damit sie wissen, welche Wendungen zu machen sind. Aber sie wissen nicht, dass die 2 Meilen entfernte Straße gesperrt ist. Versuchen Sie nicht, Ihre Agenten dazu zu bringen, einen perfekten Pfad zu zeichnen, denn es gibt keinen - auch wenn dieser perfekt beginnt, können andere Faktoren ihren Pfad blockieren. Agenten sollten nur ein paar Straßen vorausplanen müssen, wohin sie gehen.

• Informationsqualität. Ihr Verhalten sollte einfach sein, aber um dies zu erreichen, benötigen Sie eine gute Abfragefunktion. Sie müssen in der Lage sein, Fragen an Ihre Umgebung zu stellen wie "Ist das entgegenkommende Auto auf meiner Fahrspur?", "Wie viele Autos sind entgegenkommend?", "Befinden sich irgendwelche Autos hinter mir?" .

Nachdem ich einige schreckliche Fehler in veröffentlichten Spielen gesehen habe, habe ich ein paar Vorschläge:

1) Wenn es keinen triftigen Grund gibt, zweispurig zu fahren und aus KI-Gründen für eine normale Flussrichtung Vorrang zu haben - beidseitiges Fahren zulassen, aber wenn etwas in die andere Richtung kommt, muss der Typ immer auf der falschen Straßenseite sein gibt nach.

2) Eine Art Logik, um einen Stau zu beseitigen, falls er auftritt. Ich habe Situationen beobachtet, in denen die Stauhandhabung nur für Fahrzeuge galt, die versuchten, ineinander zu rennen, aber bei der Konfrontation mit einem -> -> <- <- Muster völlig versagten. Ich erinnere mich an eine Karte, die dafür anfällig war - es war ein Chokepoint, der den Angriff auf die KI-Basis erschweren sollte, aber früher oder später kamen zwei Resource Harvester, während eine Angriffsgruppe aufbrach, und das war es. Die Einheiten, die in Kontakt standen, drehten sich um und versuchten, eine Route herauszufinden, aber sie hatten keine legalen Schritte. Es wurde nicht zurückverfolgt und herausgefunden, dass sich eine andere Einheit zuerst bewegen musste, und daher ergriff die KI keine nützlichen Maßnahmen, bis die Straßensperre beseitigt war. (Sie könnten beobachten, wie sich die Einheiten im Kontakt drehen und nichts anderes tun.)

Ich glaube, dies könnte gelöst werden, indem eine feststeckende Einheit benachbarten Einheiten befiehlt, aus dem Weg zu gehen - dies würde sich ausbreiten, bis sie eine nicht feststeckende Einheit erreicht, die sich zurückziehen könnte. Dies müsste eine Art Logik beinhalten, um sie fernzuhalten, bis das Problem behoben ist.

Beachten Sie, dass die Suche nach einem alternativen Pfad oft eine schlechte Antwort ist. Ich habe eine Livelock-Situation dieser Art gesehen - Einheit A stellt fest, dass B die Straße vor sich blockiert und sich umdreht, um eine andere Route zu verwenden. Dies blockiert jetzt die Straße für B, der sich umdreht. Jetzt ist die Straße nicht mehr blockiert, sodass beide sich wieder umdrehen. In jeder Runde wechseln sie zwischen Vorwärts- und Rückwärtsbewegung.

Im selben Spiel habe ich eine andere Version gesehen, auch wegen des Kriegsnebels. An einem Chokepoint befand sich eine feindliche Einheit. Bei der automatischen Bewegung würde die Wegfindung nur dann kämpfen, wenn sie tatsächlich auf die feindliche Einheit gerichtet ist. Es würde sich vorwärts bewegen und sehen, dass die Straße blockiert war. Es bewegte sich dann zurück, es konnte den Blocker nicht mehr sehen und es bewegte sich wieder vorwärts. Wiederholen, bis der Mensch merkt, dass er nicht dahin kommt, wo er hin soll.

Ich bin nicht sehr erfahren mit Verkehrssimulationen, aber ein paar Dinge fallen mir ein.

Erstens, um Engpässe zu vermeiden, hätte ich zwei Fahrspuren, auf denen die Fahrzeuge in entgegengesetzte Richtungen fahren können. auf der gleichen "Straße".

Zweitens für Kollisionen , die auftreten können, Sie sollten ein Kollisionsvermeidungslenkverhalten haben einen massiven Stapel zu verhindern , auf. Das Lenkverhalten ist zwar gering, aber es ist sehr nützlich, um ein realistisch wirkendes Verhalten zu erzeugen.

Wenn Sie nicht mehr als eine Spur haben möchten, müssen Sie mehr Informationen in der Grafik speichern. Wenn Agent A auf einer Straße (dargestellt als Graph Flanke) und Mittel B auf der gleichen Straße ist beispielsweise in die entgegengesetzte Richtung bewegt zu A dann sie wird collide / Deadlock / was auch immer Sie codiert haben mit diesem Verhalten umgehen.

Befindet sich Agent A jedoch auf einer Straße, kann er den Besitz dieser Straße anfordern. Der Besitz der Straße würde bedeuten, dass kein anderer Agent entlang dieser Kante reisen kann (Sie können dies ganz einfach tun, indem Sie die Kantenkosten in eine massive Zahl ändern, um sicherzustellen, dass A * die Straße bei der Berechnung eines Pfades nicht auswählt). Wenn dann Agent A von dieser Straße frei ist, gibt er das Eigentum auf.

Ehrlich gesagt, es ist eine hackige Lösung, die ich nicht besonders mag, und die meisten Verkehrssimulationen (wenn nicht alle?), Die ich gesehen habe, verwenden einen mehrspurigen Ansatz.

Sie sagten, Sie hätten einige Artikel zum Lenkverhalten nachgeschlagen, aber für alle Fälle, haben Sie den folgenden Artikel nachgeschlagen?

http://www.red3d.com/cwr/steer/

Andernfalls erhalten Sie möglicherweise einige Antworten, da einige der von Ihnen genannten Probleme behandelt werden, z. B. das Engpassproblem (Queuing).

Ich denke, was Sie tun müssen, ist einen Pfadfindungsalgorithmus zu implementieren.

Teilen Sie Ihre Karte in so kleine Teile wie möglich auf (z. B. Quadrate), aber nur für gültige Orte, an denen der Verkehr fahren kann. Sie würden dann bestimmen, wo sich das Fahrzeug befindet und wohin es fährt, und einen Weg finden, vielleicht den kürzesten oder direktesten. Der Pfad wird ein Array von Quadraten sein, jeder Schritt auf dem Weg zur Destimation. Sie möchten dann nicht nur die aktuelle Position aller Fahrzeuge, sondern auch die zukünftigen Positionen der Fahrzeuge für ein paar Schritte in der Zukunft berechnen. Wenn sich in Zukunft zwei Fahrzeuge auf demselben Feld befinden, müssen Sie die Geschwindigkeit von einem oder beiden ändern.

A * (A - Stern) ist ein sehr einfaches Wegfindung Algorithmus , dass Sie wahrscheinlich können nur leicht den Pseudo - Code in Wikipedia in der Sprache Ihrer Wahl übersetzen und es wird funktionieren: http://en.wikipedia.org/wiki/A*_search_algorithm

Als ich Enemy Nations einführte, war mein letzter Fehler, dass ich ein Fahrzeug, das länger als 2 Sekunden feststeckte, auf seinem Weg nach vorne sprang. Als sie stecken blieben, wurde eine Einheit im Grunde genommen transportiert. Niemand hat sich jemals beschwert, also schätze ich, dass in den wenigen Fällen, in denen es passiert ist, niemand zugesehen hat und es nicht gesehen hat.