Basic pathfinding mit Hinderniserkennung in einem kontinuierlichen 2D-Raum

Schreibe ich eine simulation, in der eine Kreatur Objekt sollte in der Lage sein sich zu bewegen in Richtung einer anderen beliebigen Objekt in der Umgebung, gleiten um Hindernisse herum, anstatt jede intelligente Wegfindung. Ich versuche nicht, es zu haben plan ein Weg -- nur zu bewegen in einer Allgemeinen Richtung, und hüpfen um Hindernisse herum.

Es ist ein 2D-Umgebung (Ansicht von oben), und jedes Objekt verfügt über ein umschließendes Rechteck für die Kollisionserkennung. Es gibt kein raster, und ich bin nicht auf der Suche nach Einer Lösung.

Ich habe nicht in der Lage zu finden alle tutorials, die auf dieser Art von "dumm" collision-based Wegfindung, so könnte ich nicht beschreiben, diese mit den gängigsten Begriffen.

Irgendwelche Empfehlungen, wie die Umsetzung dieser (oder links zu tutorials)?

InformationsquelleAutor kpozin | 2009-05-17
  1. 6

    Erweitern auf das, was Guillaume meinte etwa Hinderniserkennung, eine Technik, die funktioniert gut für Sie ist anti-Schwerkraft-Bewegung. Sie behandeln die lokalen Hindernisse als Punktquellen von antigravity, das Ziel als die Schwerkraft, und Ihr computer gesteuert ist rutschig (seifig!) um die Hindernisse bis zum Ziel.

    • Auf der minus-Seite, müssen Sie eine anti-Schwerkraft-Feld, das größer ist als das Objekt, zu vermeiden, so dass Sie beginnen sich zu drehen, bevor Sie die Fahrzeug auf das Hindernis. So können Sie eine Konfiguration, wo man eine Beschleunigung, die direkt gegen die gewünschte (zwei Hindernis vor Ihnen -, Lösch-jede Querbeschleunigung, und overridding die vorwärts-Beschleunigung auf das Ziel) auf der plus-Seite, diese Arbeit auch gegen bewegte Hindernisse.
    • Während zwei Hindernisse können sich theoretisch gegenseitig aufheben, in der Praxis unwahrscheinlich und instabil... nur eine kleine änderung in der position und Sie mitgezogen werden, um das Hindernis. Wenn es ein Problem ist, könnte man Zähler mit Rauschen.
    • Die anti-Schwerkraft-Lösung sieht wie eine gute option in meinem Fall. Es ist sehr einfach, und die Berechnungen sind trivial. Ich glaube nicht, verlangen Garantien, dass die Agenten erreichen Ziele beim ersten Versuch, also ist es okay, wenn Sie blockiert sind, durch Hindernisse (obwohl gelegentliche Anwendung von random zusätzliche Kräfte könnte dieses problem lösen, da gut).
    • Ich bin damit einverstanden, dass seine instabile und unwahrscheinlich. Ich nur wissen, weil ich diese Lösung in einem Fall, wo Spieler konnten den Platz "Abwehr" sehr genau, und das war ein cheat, dass unser test zeigte. Ich hatte nicht gedacht, über das hinzufügen von Rauschen 🙁
    • Ah, das ist ein guter Punkt PATRY... danke für den Einblick!
    • Das Objekt könnte sehr leicht selber finden, stecken, zwischen anderen Objekten, wie zwei angrenzenden Wänden. Es wäre nicht gut für die Navigation in einem Labyrinth; eine Bewegung um L-förmige Gebäude und andere Hindernisse. Es würde nicht geeignet sein, in Gebäuden, wie der AIs in einem FPS, in dem Sie Treppen steigen müssen. Es wäre jedoch geeignet für große, offene Räume mit Dünn besiedelten Hindernisse.

    InformationsquelleAutor Paul
  2. 5

    können Sie kombinieren zwei Lenk-Algorithmus :

    suchen : Sie übernehmen die Lenkung der Kraft in der Richtung, die die Differenz zwischen der aktuellen Geschwindigkeit und der gewünschten Geschwindigkeit auf das Ziel zu

    Hindernisvermeidung : Sie rechnet für das Fahrzeug der Zukunft mit einem Feld, dessen Länge eine Konstante Zeit multipliziert mit der aktuellen Geschwindigkeit des Fahrzeugs. Jedes Hindernis, das schneidet diese box ist eine mögliche Kollisionsgefahr. Der nächste solche Bedrohung ist gewählt, der für die Vermeidung. Um zu vermeiden, ein Hindernis, eine seitliche Lenkung der Kraft entgegengesetzt zu dem Hindernis entfernt. Zusätzlich wird eine Bremsung (Verzögerung) Gewalt angewendet wird. Diese Kräfte variieren mit Dringlichkeit (der Abstand von der Spitze der box bis zu dem Punkt der möglichen Kollision). Die Lenkung verhält sich Linear, Bremsen variiert quadratisch.

    Finden Sie mehr auf der website "Steering Behaviors For Autonomous Characters"

    hinsichtlich

    Guillaume

    PS : dies wird vorausgesetzt, dass Sie mit einem Punkt/Geschwindigkeit/Beschleunigung-Methode für die Bewegung des Objekts.

    • Dies sollte schon die Antwort. Zumindest ist es auf der Grundlage der bewährten Konzepte in AAA-Spiele. Plus Craig Reynolds ist genial
    InformationsquelleAutor PATRY Guillaume
  3. 2

    Vielleicht könnten Sie Pledge-Algorithmus

    InformationsquelleAutor Dario
  4. 1

    Wenn deine Kreatur, Reisen in Vektor-Richtung v, kollidiert mit einer Wand, deren Richtung wird repräsentiert durch einen Vektor w die Richtung, die Sie benötigen, um zu "schieben" ist gegeben durch den Vektor, der die Projektion des v auf w. Diese finden Sie über

      v . w
--------- w
 |w|*|w|

    wo . ist die vector dot product und |w| ist die Größe des Vektors w ( = sqrt(w . w)). Wenn w ist ein Einheitsvektor, so wird diese einfach

    (v . w) w

    Verwendung des resultierenden Vektor als Ihre Kreatur Geschwindigkeit bedeutet Ihrem Wesen reist schnell, wenn es nur "Schürfwunden" die Wand, und langsam, wenn es trifft die Wand-fast tot-auf. (Dies ist, wie die meisten first-person-shooter-Spiele verwalten Sie Kollisionen für den menschlichen Spieler.)

    Wenn Sie stattdessen möchten, dass Ihre Kreatur auf Reisen immer mit voller Geschwindigkeit, Sie müssen nur die Zeichen der v . w -- Sie werden immer auf Reisen, entweder in die Richtung der Wand Flächen (w) oder in die entgegengesetzte Richtung (-w).

    Das Problem, das Sie haben, ist, wenn deine Kreatur trifft auf die Wand tot-on. In diesem Fall das projizierte Vektor (0, 0), und Sie müssen einige andere Technik zu entscheiden, welchen Weg (w oder -w) zu gehen. Der übliche Ansatz ist hier, Einen*, auch wenn dies vielleicht unnötig sein, wenn in Ihrer Umgebung besitzt genügend Struktur.

    InformationsquelleAutor j_random_hacker
  5. -1

    Ich habe eine pathfinding-Algorithmus in C# eine Weile zurück

    Hier ist der link

    Können Sie versuchen, und verwenden Sie es als Ausgangspunkt, dh, Sie ändern könnte, die Funktion, die prüft, die nächste Zelle, um zu sehen, wenn es gültig ist, zu prüfen, für die Hindernisse, und man konnte Sie füttern es kleine Intervalle statt der Start-und end-Punkte, ein bisschen wie mehrere mini-pahfinding Routen.

    (Der text ist in Spanisch, aber Sie können die Anwendung herunterladen aus dem link oben)

    InformationsquelleAutor juan
Schreibe einen Kommentar