Ich weiß, dass meine Frage ziemlich vage erscheint, aber ich kann mir keinen besseren Weg vorstellen, um es auszudrücken, also werde ich damit beginnen, zu erklären, was ich versuche zu tun.
Ich arbeite gerade an einem Projekt, bei dem mir eine Karte gegeben wurde und ich ein "Lebewesen" kodiere, das in der Lage sein sollte, sich auf der Karte zurecht zu finden; Das Lebewesen hat verschiedene andere Funktionen, aber diese sind für die aktuelle Frage nicht relevant. Das gesamte Programm und die Lösung werden in C # geschrieben.
Ich kann die Geschwindigkeit des Tieres steuern und seine aktuelle Position auf der Karte abrufen, indem ich seine aktuelle X- und Y-Position zurückgebe. Ich kann auch seine Richtung festlegen, wenn es mit dem Gelände kollidiert, das es blockiert.
Das einzige Problem, das ich habe, ist, dass ich keinen Weg finde, wie ich mich intelligent durch die Karte bewegen kann; Bisher habe ich darauf geachtet, in welche Richtung das Tier sieht, wenn es mit dem Gelände kollidiert, und das ist in keiner Weise eine gute Art, sich auf der Karte zu bewegen!
Ich bin kein Spiele-Programmierer, und das ist für eine Software-Zuweisung, also habe ich keine Ahnung von AI-Techniken.
Hier ist ein Link zu einem Bild von dem, wie die Karten und Kreaturen aussehen:
Ich suche in keiner Weise nach jemandem, der mir eine vollständige Lösung bietet, sondern nur einen Stoß in die allgemeine Richtung der Kartennavigation.
Wenn das einzige Wissen über die Umgebung, das Sie haben, die Position Ihres Lebewesens und seine Geschwindigkeit ist, ist das Beste, was Sie tun können, ein Wandfolgesystem, denke ich. Wenn Sie einige der anderen Dinge in Ihrer Umgebung erkennen können, haben Sie viele weitere Optionen.
Einige der beliebtesten Algorithmen sind ...
Potentielle Felder ist eine phantastische Art zu sagen, dass jedes Hindernis oder jede Wand eine "abstoßende Kraft" hat, während jedes Ziel eine "anziehende Kraft" hat. Die Stärke der Kraft basiert auf der Entfernung vom Objekt und der "Schwere" des Objekts. (Eine Lavagrube ist viel schwerer als eine holprige Straße) Nach dem Aufbau der Kraftfelder kocht der naive Algorithmus auf den Weg des geringsten Widerstands. Bessere Versionen können lokale Minima und Maxima erkennen und diese Wells verlassen.
%Vor%A * Suche
Sehen Sie sich den A * Pathfinding-Algorithmus an. Es ist im Wesentlichen der Standard Ansatz für solche Sachen.
Amit Patels Artikel über Wegfindung für Spiele hat eine ziemlich gute Einführung in A * sowie beliebte Varianten des Algorithmus.
Sie finden eine C # -Implementierung hier und hier
Dynamisches A *
Nehmen wir an, das Terrain, nach dem Sie suchen, ist nicht vorher bekannt, sondern wird entdeckt, wenn der Agent seine Umgebung erkundet. Wenn Ihr Agent auf ein zuvor unbekanntes Hindernis stößt, können Sie einfach die Geländekarte des Agenten aktualisieren und dann A * erneut ausführen, um einen neuen Pfad zu dem Ziel zu finden, das um das Hindernis herumführt.
Obwohl es sich um eine praktikable Lösung handelt, führt der erneute Ausführen des Planungsalgorithmus von Grund auf jedes Mal, wenn Sie ein neues Hindernis finden zu einer beträchtlichen Menge redundanter Berechnungen. Zum Beispiel, wenn Sie sich in der Nähe des Hindernisses befinden, könnte es sein, dass der effizienteste Weg zum Ziel demjenigen folgt, den Sie planen, bevor Sie das Hindernis entdeckt haben. Wenn Sie A * erneut ausführen, müssen Sie diesen Abschnitt des vorherigen Pfads erneut berechnen.
Sie können dies vermeiden, indem Sie Dynamic A * (D *) verwenden . Da der Agent die zuvor berechneten Pfade verfolgt, muss der Agent nur neue Routen in der Umgebung des Hindernisses berechnen, wenn der Agent ein neues Hindernis findet. Danach kann es einfach vorhandene Pfade wiederverwenden.
Ich würde einen zielorientierten Ansatz verwenden. Ihre Frage besagt, das Ziel ist, als die Karte zu erkunden und Hindernisse zu vermeiden, deshalb machen wir unser Ziel. Aber wie erkunden wir die ganze Karte? Wir erforschen, was unerforscht ist.
Von Anfang an haben Sie nur einen unerforschten Bereich, das Quadrat, auf dem Sie sich befinden. Der Rest der Karte ist als nicht erkundet markiert. Sie wählen einen unerforschten Ort und machen es zu Ihrem Ziel, ihn zu erkunden. Aber wie kommst du dahin? Sie erstellen ein Unterziel, um den Standort zu ermitteln. Und wie machst du das - erforsche das Quadrat daneben und so weiter, bis dein ursprüngliches Ziel in eine Sequenz von Erkundungen zerlegt wird, beginnend mit deinem aktuellen Quadrat und navigierend zum Zielquadrat.
Wenn Sie auf Hindernisse stoßen und Merkmale der Karte entdecken, müssen möglicherweise einige der Teilziele geändert werden. Z.B. Wenn Sie auf eine Wand treffen, muss das Unterziel, das Quadrat zu erkunden, geschrubbt werden und Sie erstellen einen neuen Plan, um eine alternative Route zu finden. Dies wird als Backtracking bezeichnet.
Das ist im Grunde für die Beschreibung auf hoher Ebene. Ich hoffe es hilft!
Ich schein mich auf der Party zu verspäten. Wenn dein Tier ein GPS und die gesamte Karte zur Hand hat, ist das richtige Ding definitiv A *, und wenn die Karte klein genug ist, würde ein einfaches BFS genauso gut funktionieren, wenn du nicht Lust hast, A * zu kodieren (A * hat einige Ecken Fälle, die Sie richtig behandeln wollen).
Eine andere Frage ist jedoch, was passiert, wenn Ihr Lebewesen nur die Richtung des Ziels kennt und nur lokal beobachten kann, was um ihn herum ist? Was ist, wenn dein Tier die vollständige Karte nicht kennt?
In diesem Fall möchten Sie den "Bug-Algorithmus" für die Navigation implementieren. Link: Ссылка
Es ist ein süßes Stück Algorithmus, das für alle unbekannten Karten funktioniert, du würdest es verdammt gut finden. Ich bin mir sicher.
Tags und Links algorithm c# artificial-intelligence path-finding
