Algorithmus zur Berechnung eines Geschosspfades zu einem Ziel mit max. 2 Abpraller

Entschuldigen Sie den schlechten Titel, aber ich hatte keinen besseren Weg, ihn auszudrücken ...

Es gibt also dieses erstaunliche Spiel von Nintendo (yes!) Auf der Wii namens WiiPlay . Es gibt 9 Minispiele, und mein Lieblingsspiel heißt Tanks! . Es geht darum, gegnerische Panzer zu zerstören, ohne sich selbst zu zerstören. Hier ist ein Screenshot eines Levels:

Eine Möglichkeit, Panzer zu zerstören, besteht darin, Kugeln abzufeuern. Es gibt diesen hellgrünen feindlichen Panzer, der Hochgeschwindigkeitskugeln abfeuert, die zweimal (gegen die Wände und Blöcke) prallen. Sie können sehen, wie der Panzer des Spielers sofort zerstört wird, wenn er dort bleibt, wo er jetzt ist, da dieser Kalkpanzer in der Mitte eine Kugel abfeuern kann, die dem grünen Pfad folgt, den ich auf dem Bild gezeichnet habe.

Als Amateur-Programmierer habe ich mich gefragt, wie der Kalk-Panzer bestimmen kann, in welche Richtung er feuern soll, um den Spieler-Panzer zu schlagen.

Ich habe selbst darüber nachgedacht, aber keinen möglichen Algorithmus gefunden. Ich werde meine Schlussfolgerungen erklären, falls sie jemanden inspirieren. Nur der Einfachheit halber in meiner Erklärung, nehme ich an eine Wand zu sein , jede Oberfläche , gegen die eine Kugel abprallen kann . Ein isoliertes Rechteck von Blöcken bildet somit vier Wände.

Ich bin zu dem Schluss gekommen, dass die beiden Punkte, an denen die Kugeln abprallen, immer entweder auf einer Seite eines Parallelogramms liegen oder entgegengesetzte Eckpunkte eines Parallelogramms werden. Der schießende feindliche Panzer und der Spielerpanzer, auf den er abzielt, sind nicht unbedingt die anderen 2 Eckpunkte, sondern liegen definitiv auf den Linien, die zu einer der vier Seiten des Parallelogramms kollinear sind. Hier ist eine Illustration der 4 Möglichkeiten, wie ein Parallelogramm erstellt werden kann:

HOR-VER bedeutet, dass die Kugel zuerst auf eine horizontale Wand trifft, dann auf eine vertikale Wand.

Und dann stecke ich fest. Ich überlegte, ob ich mich auf einer Linie, die den feindlichen Panzer und den Spielerpanzer verbindet, auf der Karte bewegen sollte, um herauszufinden, ob bei zwei Treffern mit einer beliebigen Wand ein Parallelogramm entsteht müssen mit den Eckpunkten des Parallelogramms übereinstimmen.

Ich bin mir auch des allgemeinen Ablaufs des Algorithmus nicht sicher. Nimmt der Algorithmus eine der folgenden 2 Strukturen an oder bin ich mit beiden falsch?

• Finden Sie mögliche Wege heraus und markieren Sie immer einen als den besten (kann der kürzeste, der dunkelste, der unvermeidlichste sein oder eine kombinierte und gewichtete Bewertung basierend auf mehreren Kriterien) und vergessen Sie den Rest. Die verbleibende Berechnung ist die beste.
• Bestimmen Sie zuerst alle Wände, die mit der Kugel erreichbar sind (die Kugel muss nicht gegen eine andere Wand prallen, um jede dieser Wände zu erreichen), und bestimmen Sie dann alle erreichbaren Bereiche an jeder dieser Wände (manchmal ist es unmöglich, einen entfernten Punkt zu erreichen) Eine Wand ohne Abpraller (wenn eine andere Wand in Ihrer Nähe steht), bestimmen Sie erneut alle erreichbaren Wände mit einem Abpraller und alle Reichweiten, die auf diesen Wänden erreichbar sind. Diese 4 Prozesse können auf ähnliche Weise wie Raytracing durchgeführt werden. Wenn der Panzer des Spielers während jedes Vorgangs von einem Strahl getroffen wird, ermitteln Sie den Kugelpfad entsprechend diesem Strahl.

Meiner Meinung nach ist dieser Algorithmus schwer herauszufinden, weil:

• eine Kugel kann in jede Richtung abgefeuert werden; und
• Es gibt unendlich viele Punkte an jeder Wand, wie in der Mathematik, wo es unendlich viele Punkte auf einer Linie gibt.

Aber Nintendo-Leute haben es trotzdem geschafft, also ... hat jemand eine Idee?

Bei direkter Sicht ist das Problem offensichtlich trivial. Wir haben es jedoch mit Reflektion zu tun. Es ist eine Herausforderung, herauszufinden, welche Teile der Szene gesehen werden können, wenn die Reflexion als Teil eines Ray-Tracers implementiert wird, da hierbei möglicherweise einige Öffnungen fehlen. Eine „binäre Suche“ zwischen zwei vielversprechenden Winkeln ist ebenfalls nicht durchführbar: Aufgrund der Reflexionen ist der tatsächlich sichtbare Raum nicht durchgehend, sodass die Heuristik „Wenn es rechts von A und links von B ist, muss es ein Ziel geben Eine Lösung zwischen A und B ist nicht zulässig und es fehlen „kreative“ Lösungen. Ich würde stattdessen empfehlen, die Reflexion zu implementieren, indem Sie den Tracer von einer virtuellen Position aus erneut ausführen - der Position, an der sich unser Feuerungspanzer im Spiegel zu befinden scheint :

target |obstacle
   X   |
    \  |  X real position
     \   /
      \ /
   ----------- mirror surface
        \
         \
          X virtual position

Der Vorteil ist, dass der gespiegelte Strahl nun eine gerade Linie ist, die von der virtuellen Position ausgeht. Ich habe versucht, die Technik in der folgenden Skizze zu veranschaulichen:

X markiert die Schussposition, (X) das Ziel. Die farbigen Bereiche sind sichtbar.

1. Direkte Sichtlinie: Das Ziel ist nicht sichtbar. Wir können jedoch die Flächen (1) und (2) treffen.

2. Ein Spiegelbild. Innerhalb der Hindernisse gibt es zwei virtuelle Schusspositionen. Die untere Position hat einen direkten LOS zum Ziel, daher haben wir unsere erste Schusslösung: Der Geschossweg ist der Teil des Strahls zwischen dem Ziel und der unteren Spiegelfläche sowie zwischen dem Strahl-Spiegel-Kollisionspunkt und der tatsächlichen Schussposition.

3. Zwei Reflexionen: Die obere virtuelle Position von der ersten Reflexion kann einen Teil des unteren Hindernisses durch seine Spiegelfläche sehen. Da zwei Reflexionen erlaubt sind, können wir diese Position in das untere Hindernis spiegeln. Die Positionen werden als (I) die reale Position, (II) die virtuelle Position von der ersten Reflexion und (III) die virtuelle Position von der zweiten Reflexion markiert.

   Ausgehend von (III) haben wir eine direkte LOS zum Ziel (X), sodass wir eine andere Brennlösung gefunden haben. Der Geschossweg verläuft entlang der Linie X-III bis zum zweiten Spiegelkollisionspunkt, dann entlang der Linie III-II zwischen den Spiegelkollisionspunkten und schließlich entlang der Linie II-I vom ersten Spiegelkollisionspunkt bis zur tatsächlichen Position I.

   Tatsächlich könnte die untere virtuelle Position von der ersten Reflexion auch in das obere Hindernis reflektiert werden, aber dies führt zu keinen direkten Lösungen.

Sobald Sie herausfinden können, welche Teile der Hindernisse sichtbar sind (und daher zum Reflektieren der Kugel verwendet werden können), erscheint die Implementierung der Spiegelung über eine Tiefensuche unkompliziert. Um geeignete Spiegeloberflächen zu finden, können die in Nicky Cases Sight & Light beschriebenen Techniken verwendet werden: Anstatt 360 Vektoren auszuprobieren, die Öffnungen verpassen könnten und auch verschwenderisch sind, lenken wir Strahlen nur an die Kanten von Hindernissen.

Gerade erweiterte Karl Bielefeldt Idee für ein 2-Wände-Spiegelbild:

A und B sind gegeben (die Panzer). Sie müssen zuerst alle Wände auflisten, die A sehen kann, und eine Liste aller Wände, die B sehen kann. Dann bilden Sie Paare, bei denen sich die erste Wand in der ersten Liste und die zweite Wand von der ersten Wand und der zweiten Liste unterscheidet. Sie müssen diesen Test für alle möglichen Wandpaare durchführen (es sei denn, Sie finden einen Weg, um Kandidaten zu eliminieren). Sobald Sie R und S für ein bestimmtes Paar von Wänden gefunden haben, überprüfen Sie

1) wenn A eine direkte Sicht auf R hat

2) Wenn R zur Wand1 gehört (die Wand ist nur ein Segment, nicht die ganze Linie)

3) wenn R direkten Zugang zu S hat

4) Wenn S zu wall2 gehört (die Wand ist nur ein Segment, nicht die ganze Linie)

5) wenn S direkten Zugang zu B hat.

Um R und S zu finden : Da Sie wall1 kennen, können Sie die Geradengleichung Tangens an wall1 bestimmen. Da R zur Geraden Tangens an wall 1 gehört, haben Sie eine Beziehung zwischen den 2 Koordinaten von R (mit einem Freiheitsgrad für R) Ähnlich wie bei S (Sie haben eine Beziehung zwischen S-Koordinaten, da dieser Punkt zur Tangentenlinie von wall2 gehört). Jetzt haben Sie 2 Freiheitsgrade und müssen 2 zusätzliche unabhängige Gleichungen haben, um eine Lösung zu bestimmen. Eine Gleichung lautet:

(AA')/(RA')=(SS')/(RS')

Die andere Gleichung lautet:

(BB')/(SB')=(RR')/(SR')

Beachten Sie, dass in den obigen Gleichungen A, A ', B, B' bekannt sind oder direkt berechnet werden können. R 'und S' sind Funktion der Koordinaten von R und S und der Wandgleichungen. Ich habe die Mathematik nicht beendet, daher weiß ich nicht, wie die Gleichungen aussehen werden.

Sie können die Tatsache ausnutzen, dass der Winkel, der den Abpraller verlässt, mit dem Winkel übereinstimmen muss, der in ihn eintritt. Für eine gegebene horizontale Wand mit y-Koordinate cund zwei festen Tanks mit Koordinaten (a,b)und (d,e)gibt es nur einen Winkel, der die nachstehende Gleichung erfüllt.

Lösen Sie einfach, xum den Abstand entlang der Wand zu ermitteln, auf den Sie zielen müssen. Zwei Wände funktionieren gleich. Sie haben nur zwei Gleichungen und zwei Unbekannte.

Sie haben ordentliche Diagramme, die zeigen, wie Sie Strahlen lenken. Ich werde also die Details zur Bestimmung eines Paares reflektierender Oberflächen belassen.

Nennen wir die Fläche, die zuerst getroffen werden muss, A und die zweite Fläche B .

Versuchen Sie, die (sichtbaren) Kanten von B zu treffen, indem Sie auf A schießen . Mit anderen Worten, bestimmen Sie die Punkte, an denen die Enden von B reflektiert werden, wenn Sie das spiegelglatte A betrachten . Dies muss einfach zu bewerkstelligen sein. Sie müssen nur einen Reflexionspunkt handhaben.

Jetzt kennen Sie zwei Strahlen, die auf die (sichtbaren) Kanten von B treffen . Nennen wir sie Kantenstrahlen. Berechnen Sie ihre Reflexionen aus B; Sie müssen irgendwo hinter Ihrem Ziel sein. Sie können bestimmen, ob das Ziel zwischen ihnen liegt, dh links von einem Strahl, aber rechts von dem anderen, oder umgekehrt. Dies ist unter Verwendung der allgemeinen Gleichung der geraden Linie trivial .

Befindet sich das Ziel nicht zwischen den Randstrahlen, können Sie es offensichtlich nicht mit einem Zwischenstrahl treffen. Wählen Sie ein anderes Paar von Oberflächen.

Wenn das Ziel ist , zwischen den Strahlen, suchen Sie nach dem Zwischen hitting ray binäre Suche. Sie haben zwei Schusswinkel, die den Randstrahlen entsprechen, Ihr Schlagwinkel liegt dazwischen. Vorausgesetzt, dass der Winkeldurchmesser Ihres Ziels vom Schusspunkt aus gesehen nicht zu klein ist, benötigen Sie einige Iterationen, bis Sie die Richtung eines Schlagstrahls finden.

Hier ist ein Bild:

Hier sind die beiden Randstrahlen in rot und blau dargestellt. Anscheinend können Sie einen Strahl finden, der in einem kleineren Winkel als der rote ausgestrahlt wird, aber größer als der rote, so dass dieser Strahl das grüne Ziel trifft.

Erinnern Sie sich an den Physikunterricht, als Sie über Lichtbrechung sprachen? Nun, Ihr Problem kann mit diesen Prinzipien gelöst werden. Der Einfallswinkel ist gleich dem Reflexionswinkel. Daher muss der feindliche Panzer für den ersten Abprall alle möglichen Winkel durchlaufen, damit der zweite Abprall den Spieler treffen kann. Machen Sie auch mit der Raytracing-Idee weiter. Das wird jetzt kompliziert, wenn sich der Spieler bewegt, aber es sollte eine gute Idee sein, mit einem Algorithmus zu beginnen