Bewegen / Ausweichen vor Hindernissen

12

Ich würde gerne ein "Spiel" schreiben, in dem Sie ein Hindernis platzieren können (rot), und dann versucht der schwarze Punkt, es zu umgehen und zum grünen Ziel zu gelangen.
Ich benutze einen sehr einfachen Weg, um dies zu vermeiden. Wenn der schwarze Punkt in der Nähe des roten ist, ändert er seine Richtung und bewegt sich für eine Weile vorwärts zum grünen Punkt.
"Unrealistischer" Pfad

Wie kann ich einen "reibungslosen" Pfad für den computergesteuerten "Player" erstellen?
Edit: Nicht die Glätte ist das Wichtigste, sondern die rot blockierende "Wand" zu meiden und nicht hinein zu krachen und dann zu meiden.

Wie könnte ich einen Pfadfindungsalgorithmus implementieren, wenn ich nur 3 Punkte habe?
(Und was würde die Sache noch komplizierter machen, wenn Sie mehrere Hindernisse platzieren könnten?)
Glatter Weg

ai path-finding Benutzer
quelle

Antworten:

9

Ein sehr verbreiteter und allgemeiner Ansatz besteht darin, den Weltraum in Gitter zu unterteilen und Algorithmen wie A * zu verwenden.

Über diesen Link konnte ich den A * -Algorithmus verstehen und implementieren.

Bearbeiten :

Ein einfacherer Gedanke, der mir einfällt, ist ... wenn man die Welt in Gitterzellen hat. Lassen Sie den schwarzen Punkt immer der Entfernung von Manhattan zum grünen Punkt folgen. Anschließend können Sie jeder Zelle eine Gewichtung zuweisen. Hindernisse können ein hohes Gewicht auf der Gitterzelle haben und sich frei bewegen kann (sagen wir mal) ein Gewicht von 0 haben. Überprüfen Sie bei jeder Bewegung entlang der Manhattan-Distanz, ob das Gewicht der nächsten Zelle nicht höher ist als das Gewicht der aktuellen Zelle. Wenn es höher ist, überprüfen Sie das Gewicht der benachbarten Zelle und fahren Sie fort.

Hoffe das hilft

Brainydexter
quelle
Dieser A * -Algorithmus Artikel scheint zu sein , was ich suchte, aber leider , was ich weiß noch nicht, wie meine „Welt“ zu unterteilen in Netze: S
Benutzer
Es kommt wirklich darauf an. Denken Sie: Teilen Sie Ihre Welt in ein Raster von 32 x 32, das dann Positionen in einem 2D-Array darstellt. In Ihrem Fall liegt der rote Punkt beispielsweise bei 120, 120 Pixel (oder 120/32 x 120/32: 3,75 x 3,75). 3,75 x 3,75 steht für eine Position in Ihrem Weltgitter (oder 2D-Array). Da Arrays durch Ganzzahlen indiziert werden, möchten Sie nur einen ganzzahligen Teil davon. Daher wäre der rote Punkt 3 x 3. Hoffe, das hilft
Brainydexter
18

Das Lenkverhalten ist genau auf dieses Problem ausgelegt.

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

Grundsätzlich würden Sie das Hindernisvermeidungsverhalten mit dem Such- oder Verfolgungsverhalten kombinieren. Diese Seite enthält eine Reihe von Java-Animationen der verschiedenen Verhaltensweisen und ihrer Funktionsweise. Es gibt verschiedene Open-Source-Implementierungen von Lenkverhalten. Hier ist eins.

Tetrade
quelle
Hierfür ist das Lenkverhalten perfekt.
25.
2

Ein einfacher Versuch besteht darin, einen unsichtbaren Punkt zu haben, der dem schwarzen Punkt vorausgeht und den Pfad in Ihrem ersten Bild ausführt. Der schwarze Punkt folgt dann in geringem Abstand hinter dem unsichtbaren Punkt.
Ich habe diese Arbeit mit guten Ergebnissen gesehen, aber natürlich könnte sie nicht Ihren Bedürfnissen entsprechen.

Paulo Pinto
quelle