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

21

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:

Bildbeschreibung hier eingeben

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:

Bildbeschreibung hier eingeben

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?

Hallo alle
quelle
Nur um zu überprüfen, fragen Sie, wie dies getan werden könnte, und nicht, wie Nintendo es tatsächlich getan hat, oder?
Ixrec
@lxrec du hast recht, nur an einer möglichen Möglichkeit interessiert, es zu tun, nicht so, wie sie es getan haben .
Hallo an alle
Das Spiel muss keine Lösung finden. Wenn Sie den Feuerknopf drücken, kennt das Spiel Ihre Position und Richtung bereits und verwendet nur diese Informationen. Es wird die Flugbahn verfolgen und wenn es den feindlichen Panzer auf dem Weg findet, wird es getroffen, sonst nicht.
Mandrill
2
Obwohl es unendlich viele Winkel gibt, können Sie diese leicht auf wenige Äquivalenzklassen reduzieren. Nicky Cases Sight and Light ist eine coole Demo zum Rendern von Schatten zwischen Polygonen - was genau Ihr Problem ist, außer dass Sie statt Lichtstrahlen Kugelpfade verwenden und Ihre Strahlen möglicherweise zweimal reflektiert werden. Beachten Sie, dass die Reflexion für die KI keine Rolle spielt - die Reflexion erweitert lediglich die Sichtlinie, obwohl dies bedeutet, dass dasselbe Objekt aus mehreren Winkeln sichtbar sein kann.
amon
@Mandrill Ich fürchte, Sie haben meine Frage nicht ganz verstanden. Ich habe gefragt, wie der feindliche Panzer einen Kugelpfad entwickeln kann, der auf den Panzer des Spielers trifft.
Hallo an alle

Antworten:

9

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:

um ecken schießen

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.

amon
quelle
Ich verstehe nicht, wie "Strahlen nur an den Rand von Hindernissen werfen" funktioniert. Wollen Sie damit beginnen, Strahlen gegen Ende der Wände und allmählich nach innen zu werfen, bis wir eine Lösung finden? Wenn ja, verstehe ich, dass mit dieser Regel die Lösung schneller gefunden werden kann.
Hallo an alle
Nach einiger Überlegung denke ich, dass dies die beste Antwort ist, da ich mit der mathematischen Antwort, die ich als die beste zuvor markiert habe, offensichtlich nicht direkt mit One-Bounce- und Bounce-freien Lösungen umgehen kann.
Hallo an alle
Das ist brilliant! Irgendwelche Ratschläge, wie Sie eine gespiegelte Darstellung Ihres Niveaus erstellen können, ohne Ihr Spiel zu stark zu beanspruchen?
Retrovius
7

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

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.

Mandrill
quelle
Dies ist ein großartiger mathematischer Ansatz. Aber der Algorithmus benötigt eine Menge Rechenzeit, um die simultanen Gleichungen zu lösen, denke ich? Mit Entfernungen sind viele Quadratwurzeln und Potenzierungen verbunden.
Hallo an alle
3

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.

Diagramm der Gleichung

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.

Karl Bielefeldt
quelle
1

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:

Strahlen

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.

9000
quelle
Nein, nicht unbedingt! Denken Sie an Ihr Diagramm, wenn sich irgendwo zwischen dem roten und dem blauen Kugelpfad ein zusätzliches Hindernis befand. Wenn Sie eine Kugel in einem Winkel genau zwischen dem roten und dem blauen Winkel abfeuern, könnten Sie einen genaueren Treffer auf den Panzer des Spielers erzielen, aber Sie könnten auch völlig daneben gehen, weil die Kugel von einem zufälligen Hindernis abprallen könnte, das dazwischen liegt. Bitte schauen Sie in @ amons Antwort nach, wo er über diese Möglichkeit spricht.
Hallo an alle
Upvoted @ amons Antwort; Ich mag die Idee der geradlinigen Spiegelung. Ich nehme auch an, dass der Algorithmus überprüfen sollte, ob der Trefferpfad tatsächlich passierbar ist, nachdem er auf diese vereinfachte Weise gefunden wurde. Noch interessanter ist eine Möglichkeit, bei der das Ziel nur teilweise verdeckt ist (möglicherweise sogar in zwei sichtbare Bereiche unterteilt). Amons Methode ist für den Umgang damit besser geeignet.
9000,
-3

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

JavaFreak
quelle
1
Ich verstehe die Prinzipien der Reflexion. Sie können meine Antwort auf @ amons Kommentar sehen. Sie haben Recht, dass die Spielerbewegung berücksichtigt werden muss, aber ich denke, dies kann als ein Kriterium für die Auswahl eines Optimums unter mehreren möglichen Pfaden basierend auf der Bewertung bleiben. Dies kann jedoch ignoriert werden, da dies mit der Entfernung des Geschosspfades korreliert, dh je länger der Pfad ist, desto mehr kann sich der Spieler bewegen, bevor das Geschoss das Ziel erreicht.
Hallo an alle