In einem Spiel sollen sogenannte Skills eingesetzt werden können, welche individuelle Bewegungsmuster haben. Beispielsweise eine Axt, die in einer Parabel nach unten fällt, oder ein Feuerball der sich in einer Kurve bewegt.
Die KI soll in der Lage sein, Skills intelligent einzusetzen und vorauszusehen, ob sie ihren Feind treffen wird. Aktuell wird das Problem gelöst, indem während der Entwicklung jeder Skill von Hand getestet wird, und ein Distanz-Gebiet bestimmt wird, in welchem der Bot sich aufhalten kann, um zu treffen. Diese ideale Distanz (maximaler und minimaler Abstand vom Feind) beinhaltet aktuell jeder Skill als feste Zahl, welche von Bots verwendet werden kann.
Diese Lösung ist nicht nur relativ aufwändig (von Hand alle Distanzwerte bestimmen), sondern vernachlässigt auch die Y-Koordinate: Aktuell verwendet sie nur auf den horizontalen Abstand eines Bots zu seinem Feind und hofft, das die Höhe stimmt.
Ehrlich gesagt ist die Lösung aktuell ziemlich zuverlässig und ich bin nicht auf weitere Verbesserungen angewiesen. ABER gleichzeitig ist sie langweilig und ich bin interessiert an neuen kreativen Wegen, Kollisionen vorauszuschätzen. Ich habe selbst etwas über die Problematik nachgedacht und kann nicht mehr aufhören über mögliche Lösungsstrategien nachzudenken
Kurz noch ein paar Infos zu der Bewegung eines Skills: Jeder Skill hat folgende Eigenschaften:
Feste Höhe h und Breite w (können deutlich voneinander abweichen: Keine quadratische Form garantiert)
Startpunkt (x_0, y_0)
Startgeschwindigkeit (v_x_0, v_y_0)
Konstante Beschleunigung (a_x, a_y)
Mein erster Ansatz war eine iterative Vorgehensweise:
Am Startpunkt (t=0) beginnen
Auf Kollision prüfen
Position zum Zeitpunkt t_(n+1) = t_n + delta t bestimmen
Nicht am Ende angekommen? Zurück zu Schritt 2
Allerdings gibt es hier folgende Schwierigkeit: Welcher Zeitabstand delta t wird gewählt?
Bei manchen Bewegungen (Ausnahme: Bewegung parallel zu einer Koordinatenachse) kommt es zwangsläufig zu Ungenauigkeiten, es sei denn der Zeitabstand wird tatsächlich so klein gewählt, dass jeder Pixel berücksichtigt wird (weil irgendwann der Fehler so klein wäre), was unnötig wäre und die Performance verschlechtern würde.
Ein weiterer Lösungsansatz wäre, den Mittelpunkt des Feindes zu betrachten und den kleinsten Abstand des Bewegungsgraphen zu diesem Punkt zu bestimmen. Hier würde es allerdings zu Fehlern kommen, wenn Höhe und Breite des Skills sich deutlich unterscheiden.
Ich werde morgen nochmal genauer auf die Thematik eingehen, allerdings ist es heute bereits wieder viel zu spät, und ich muss morgen sehr früh aufstehen, weswegen ich den Beitrag jetzt vorerst hektisch beende. Ich hoffe die Problemstellung und Thematik sind klar geworden und der Beitrag ist in der Eile nicht zu unübersichtlich geworden.
Über eure Lösungsideen und Strategien bin ich sehr gespannt!
Ein paar Punkte sind da nicht ganz klar. Z.B. die „Parabel“, du erwähntest, und was diese Schlangenlinien damit zu tun haben.
Etwas allgemein: Im wesentlichen gibt es zwei Ansätze, um sowas zu lösen, nämlich iterativ oder analytisch.
Die analytische Lösung ist theoretisch schön und ggf. auch effizient. Das Problem bei der analytischen Lösung ist aber: Mathe! Schon für den einfachsten Fall einer perfekten Schulbuch-Wurfparabel wird das etwas frickelig. Es ist natürlich interessant, und … deswegen bin ich mal für eine Stackoverflow-Antwort die „extra mile“ gegangen, und habe da etwas gebastelt:
Man kann den Start- und Zielpunkt (Grün und Blau) herumschieben, und sowohl den Schusswinkel als auch die Schusskraft einstellen. Dabei wird angezeigt:
Wie viel „Power“ man bräuchte, um das Ziel zu treffen (wenn man den Winkel gleich ließe)
Mit welchen (beiden!) Winkeln man das Ziel treffen könnte (wenn man die Power gleich ließe)
Dabei sind einige Formeln involviert, die man etwas versteckt auf Wikipedia findet, aber … andere hatte ich mir damals selbst mit WolframAlpha zuammengeklöppelt
Das ganze liegt hier rum:
Wenn die Flugbahn etwas anderes sein kann, als eine perfekte Wurfparabel, wird das mit der generischen, analytischen Lösung schwierig.
Und ein wichtiger Punkt kommt noch dazu: Es bewegt sich ja nicht nur das Projektil, sondern auch der Gegner! Das ist dann praktisch nicht mehr analytisch lösbar.
(OT: Provot hat für den 3D-Fall die Berechnung des Zeitpunktes, wann 4 sich bewegende Punkte in einer Ebene liegen, auf die Suche nach den Nullstellen eines kubischen Polynoms zurückgeführt, und die Berechnung der Koeffizienten erfordert (so, wie es in den SIGGRAPH course notes stand) 188 Additionen und 192 Multiplicationen - in meiner Diplomarbeit hatte ich das dann auf 50 Additionen und 48 Multiplikationen reduziert…).
Für beliebige Pfade würde sich darum eine iterative Lösung anbieten.
Da tritt ein anderes klassisches Problem der diskreten Kollisionserkennung auf, nämlich die Frage nach der „Schrittweite“, die du schon angesprochen hast: Wenn sich ein Objekt schnell bewegt, und die Schrittweite zu groß ist, fliegt das Objekt ggf. durch das andere durch. Da gibt es verschiedene Abhilfen (bzw. Workarounds). Das hängt dann aber ein bißchen davon ab, wie der „Pfad“ denn berechnet wird - sowohl des Projektils, als auch des Gegners.
Du hast ja schon eine Animation im Spiel, d.h. es gibt ja schon eine „Schrittweite“ - nämlich gegeben durch den Zustand, der jeweils gerendert wird. Aber … ist der Pfad etwas, was darüber hinaus „im Voraus“ berechnet wird oder werden kann? Z.B. als eine List<Point2D> oder so? (Für Projektil und Gegner!?!). Da könnte man dann ja durchlaufen, und dabei sicherstellen, dass die Schrittweite nie zu groß wird (da hatte ich auch mal was gebastelt: Geom/DeltaPathIterator.java at master · javagl/Geom · GitHub ).
Alternativ dazu könnte man „empirisch“ die Schrittweite abhängig von der Geschwindigkeit der Objekte wählen. Ich würde aber eigentlich vermuten, dass die Schrittweise gar nicht sooo winzig sein muss: Die Geschwindigkeit der Objekte sollte ja nicht zuuu groß sein, und die Objekte selbst sind ja nicht nur Punkte. Also, eine „Kollision“ heißt ja nährungsweise, dass sich die Bounding Boxes der Objekte überschneiden, und wenn die so ~100x100 Pixel haben, sollte man doch mit <100 Schritten durch den Pfad laufen können?!
(Ein „Mittelding“ könnte noch sein: Man betrachtet zwar den Zustand an (wenigen) diskreten Zeitpunkten, aber dann auch jeweils Anfang und Ende des Schrittes - d.h. man überprüft das sogenannte „Swept Volume“ auf Kollisionen, das sich aus der Bounding Box und ihrer Bewegung in diesem Schritt ergibt - aber das ist nur ein Ansatzpunkt, für die Umsetzung gäb’s dann ein paar Freiheitsgrade…)
Zuerst vielen Dank für die sehr schnelle und extrem ausführliche Antwort
Die Bewegung eines jeden Skills ist vorgegeben durch Startgeschwindigkeit und Beschleunigung. Es gibt keine allgemeine Gravitationskraft. Stattdessen wird die Beschleunigung in Y-Richtung verwendet, um einen ähnlichen Effekt zu erzielen.
Hier sind ein paar Bewegungsbeispiele: https://youtu.be/SNvfuy3m7FI
Anhand der Bewegungsgleichung sollte sich zu jedem Zeitpunkt eine „eindeutige“ Position (Abweichungen der Realität sollten vernachlässigbar sein) bestimmen lassen:
Die tatsächliche Bewegung und Kollisionserkennung funktioniert bereits. Die Bewegung wird nicht im voraus ausgerechnet, sondern in Echtzeit anhand von Geschwindigkeit und Beschleunigung simuliert. Die Aufgabe, die ich aktuell versuche zu lösen, ist das Vorausschätzen von Kollisionen (muss nicht perfekt sein, aber sollte eine geringe Fehleranfälligkeit haben). Ich möchte den Bots im Spiel ermöglichen, zu erkennen, bei welchem Abstand und Zeitpunkt ein Skill eingesetzt werden kann, um den Feind mit einer hohen Wahrscheinlichkeit zu treffen.
Das klingt interessant, wäre eine Idee für den iterativen Ansatz. Blöde Frage nebenbei: Gibt es irgendwas, das du noch nicht gemacht hast?
Habe ich mir auch schon überlegt… Die Distanz, welche zwischen zwei Punkten zurückgelegt wird, müsste für jeden Schritt neu bestimmt werden, da Beschleunigung auch eine Rolle spielt. Zuerst habe ich versucht, die Entfernung zwischen zwei Schritten zu ermitteln, in welcher es noch keinen Fehler gibt, allerdings ist mir dann sehr schnell aufgefallen, dass bei einer diagonalen Bewegung das Delta eigentlich unendlich klein sein müsste.[quote=„Marco13, post:2, topic:19295“]
Ich würde aber eigentlich vermuten, dass die Schrittweise gar nicht sooo winzig sein muss: Die Geschwindigkeit der Objekte sollte ja nicht zuuu groß sein, und die Objekte selbst sind ja nicht nur Punkte. Also, eine „Kollision“ heißt ja nährungsweise, dass sich die Bounding Boxes der Objekte überschneiden, und wenn die so ~100x100 Pixel haben, sollte man doch mit <100 Schritten durch den Pfad laufen können?!
[/quote]
Wahrscheinlich hast die Recht und die Methode würde bereits tadellos funktionieren.
Ich habe mir auch bereits überlegt, auf Bisektion zurückzugreifen und schrittweise das aktuelle Intervall (beginnend mit Anfangs- und Endpunkt) zu halbieren und stets die Intervallgrenzen auf das Teilintervall zu verschieben, welches näher am Gegner ist (wie würde ein Intervall bewertet werden? Nach dem Mittelpunkt? Mehrere Probepunkte?). Sobald irgendwann ein sehr naher Punkt bestimmt ist, kann hier auf Kollisionen geprüft werden. Allerdings könnte es hier bei Skills zu Problemen kommen, welche ihre Richtung ändern (z.B. wie ein Bumerang zurückfliegen): Sobald ein falsches Teilintervall gewählt wird, wird das andere vernachlässigt, auch wenn es in späteren Schritten evtl. besser wäre.
Das Thema ist auf jeden Fall spannend! Werde etwas an den Ideen herumprobieren.
^ Genau, das war nur um nochmal zu betonen: Analytisch kann sehr schnell sehr kompliziert werden.
So weit so klar. Die meisten sahen ja trotzdem nach einer relativ normalen Wurfparabel aus, wo also grob ax==0 und ay==gravitiation ist. Ins Auge gestochen ist mir die „Bumerang-Bewegung“ ganz am Ende, die du ja auch noch erwähnst, und wo ich mich frage, wo die Beschleunigung herkommt. Aber selbst wenn man das weiß, ist eine analytische Lösung da nicht wirklich praktikabel.
Und was ist mir höheren Schwierigkeitsstufen? Naja, egal: Wenn man die iterative Lösung einigermaßen allgemein macht, kann man sowas wohl relativ leicht einbauen.
Hm. Mal einen Schritt zurück: Die Bewegung der Gegner und der Spielfigur wird mit der o.g. Bewegungsgleichung simuliert. Die einzige Variable dabei ist die Beschleunigung. Und so, wie ich es verstanden hatte, wird die Bewegung der Projektile AUCH mit dieser Gleichung simuliert (aber eben mit anderen Beschleunigungen, z.B. für den Bumerang). Dann sehe ich nicht, warum es nicht möglich sein sollte, die Bewegung „mal kurz“ für 100 Schritte im Voraus zu berechnen, und die Positionen als Liste von Punkten zu speichern… Dann bleibt noch die Frage nach der Schrittweite.
Die Schrittweite bezieht sich für die Simulation ja erstmal auf die Zeit - und nicht auf die Distanz zwischen den Positionen. D.h. ich vermute, dass du irgendwo versteckt GROB sowas hast wie
(versteckt, und komplizierter, aber das ist ja im Prinzip die Bewegungsgleichung von oben - oder, wenn man’s kompliziert haben will: Ein Schritt im Euler-Verfahren zur Lösung einer partiellen Differentialgleichung).
Dieser „Zeitschritt“ dort hängt dann ja von der Framerate ab. Bei 30 FPS ist die „deltaT“ also 1/30 Sekunde. Und natürlich könnte ein schnelles Objekt in dieser Zeit 500 Pixel zurücklegen. Wenn man (für die Kollisionserkennung) einfach fix deltaT=1.0/100 setzt, sollte die Abtastung ja fein genug sein. (Ich kann mir aber vorstellen, dass sowas nur schwer (nachträglich) in ein bestehendes System eingebaut werden kann. Die Positionen zu speichern und darauf rumzurechnen ist ja was anderes, als einfach jeden Schritt zu rendern…)
Unendlich? Warum das? Die maximale Distanz zwischen zwei Positionen ergibt sich aus der maximal auftretenden Geschwindigkeit (die sich aus der Beschleunigung ergibt). Aber … das sollte doch alles „im Rahmen“ bleiben, sonst würde ja in einem Frame der Gegener eine Axt werfen, und im nächsten Schritt wäre der Spieler schon tot… !?
Bisektion ist sicher ein möglicher Baustein. Aber IMHO kann der nur sinnvoll auf ein einzelnes Intervall (mit einer Linearen Bewegung) angewendet werden. Und für ein einzelnes Intervall ist die Bisektion dann recht straightforward.
double min = 0;
double max = 1;
double current = 0.5;
while (max - min > epsilon) {
if (isBeforeCollision(current)) { max = current; current = centerOf(min, max); }
if (isAfterCollision(current)) { min = current; current = centerOf(min, max); }
}
Man könnte es für beliebige Kurven verallgemeinern, das wäre dann aber ggf. sehr kompliziert: Man bräuchte eine Methode wie Point getPositionForTime(double t), in der dann im Prinzip die Bewegungsgleichung (wieder schrittweise!) bis zu t ausgeführt werden müßte…
Ich bedanke mich erneut für die ausführlichen und guten Antworten Marco
Jeder Skill hat sobald er erstellt wird direkt eine vorgegebene Beschleunigung und Geschwindigkeit, welche im Endeffekt bei jedem Einsatz das selbe Bewegungsmuster erzeugen.
Solche Anpassungen erfolgen dann in der nächsten Stufe
Eine iterative Lösung ist vermutlich praktikabel.[quote=„Marco13, post:5, topic:19295“]
Hm. Mal einen Schritt zurück: Die Bewegung der Gegner und der Spielfigur wird mit der o.g. Bewegungsgleichung simuliert. Die einzige Variable dabei ist die Beschleunigung. Und so, wie ich es verstanden hatte, wird die Bewegung der Projektile AUCH mit dieser Gleichung simuliert (aber eben mit anderen Beschleunigungen, z.B. für den Bumerang). Dann sehe ich nicht, warum es nicht möglich sein sollte, die Bewegung „mal kurz“ für 100 Schritte im Voraus zu berechnen, und die Positionen als Liste von Punkten zu speichern… Dann bleibt noch die Frage nach der Schrittweite.
Die Schrittweite bezieht sich für die Simulation ja erstmal auf die Zeit - und nicht auf die Distanz zwischen den Positionen. D.h. ich vermute, dass du irgendwo versteckt GROB sowas hast wie
(versteckt, und komplizierter, aber das ist ja im Prinzip die Bewegungsgleichung von oben - oder, wenn man’s kompliziert haben will: Ein Schritt im Euler-Verfahren zur Lösung einer partiellen Differentialgleichung).
Dieser „Zeitschritt“ dort hängt dann ja von der Framerate ab. Bei 30 FPS ist die „deltaT“ also 1/30 Sekunde. Und natürlich könnte ein schnelles Objekt in dieser Zeit 500 Pixel zurücklegen. Wenn man (für die Kollisionserkennung) einfach fix deltaT=1.0/100 setzt, sollte die Abtastung ja fein genug sein. (Ich kann mir aber vorstellen, dass sowas nur schwer (nachträglich) in ein bestehendes System eingebaut werden kann. Die Positionen zu speichern und darauf rumzurechnen ist ja was anderes, als einfach jeden Schritt zu rendern…)
[/quote]
Die Bestimmung der Bewegungen der Spielfiguren erfolgt in Echtzeit: Spieler und Bots bestimmen selbstständig zu „jedem Zeitpunkt“, welche Aktion oder Bewegung sie ausführen möchten. Allerdings ist für die Bewegung von Skills das Verhalten der Spieler vorerst nicht relevant. Die Bewegung für mehrere Schritte im Voraus zu berechnen sollte machbar sein und benötigt - abhängig vom Verfahren - nicht mal das Zwischenspeichern der Schritte in eine Liste. Stattdessen könnte für jeden Schritt auf eine mögliche Kollision geprüft werden und bei Erfolg direkt ein ‚wahr‘ als Rückgabewert geliefert werden. Die Schritte hängen wie du erwähnt hast von der Zeit ab. Der geeignete Zeitabstand könnte ja beispielsweise anhand der maximalen Geschwindigkeit, welche die Bewegung an irgendeiner Stelle hat, durch bestimmen des globalen Maximums der Funktion der absoluten Geschwindigkeit, näherungsweise errechnet werden.
Die aktuelle Framerate reicht aus, um die Kollisionen der Elemente, welche im Spiel vorkommen, fehlerfrei zu bestimmen.[quote=„Marco13, post:5, topic:19295“]
Unendlich? Warum das? Die maximale Distanz zwischen zwei Positionen ergibt sich aus der maximal auftretenden Geschwindigkeit (die sich aus der Beschleunigung ergibt). Aber … das sollte doch alles „im Rahmen“ bleiben, sonst würde ja in einem Frame der Gegener eine Axt werfen, und im nächsten Schritt wäre der Spieler schon tot… !?
[/quote]
Bei einer diagonalen Bewegung führt jeder kleinste Schritt in der Theorie zu einem Fehler (weil die zwei Ecken nach jedem Schritt an einer neuen Position sind, an der kein vorheriges Rechteck getestet wurde)
:
in der Realität ist der Fehler irgendwann natürlich vernachlässigbar.
Bei den meisten Bewegungen sollte Bisektion sogar relativ erfolgsversprechend sein, allerdings bräuchte man wohl für Skills wie dem Bumerang eine aufwändigere Methode, wie von dir angesprochen. Hier verstehe ich allerdings nicht ganz, wieso die Position zu einem bestimmten Zeitpunkt schrittweise errechnet werden muss… Die Bewegungsgleichung bildet näherungsweise (mit sehr geringem Fehler) die tatsächliche Bewegung ab.
Bevor das Thema durch die ganzen Zitate und Teilantworten viel zu unübersichtlich wird, hier eine kurze Zusammenfassung aus meiner Sicht:
Aktueller Stand
Bewegungen der Skills sind durch ihre Startgeschwindigkeit und -Beschleunigung definiert. Sie werden in Echtzeit simuliert (die Bewegungsgleichung bildet die tatsächliche Bewegung nur nach). Kollisionen mit anderen Skills oder Spielern werden auch bereits in Echtzeit ermittelt und funktionieren problemlos.
Ziel
Bots sollen in der Lage sein, vorauszuschätzen, ob ein Skill den Feind treffen würde, wenn er von ihnen eingesetzt werden würde. Die Kollisionsvorausschätzung muss nicht exakt sein, sollte allerdings 1. Möglichst effizient sein 2. Einen möglichst geringen Fehler haben.
Mögliche Methoden
Analytische Vorgehensweise
(vermutlich nicht praktikabel, viel zu aufwändig)
Iterative Lösung:
Iterativ Teilaufenthaltsorte bestimmen und dort nach einer Kollision mit dem Feind prüfen
Ermitteln der Aufenthaltsorte durch die Bewegungsgleichung als Funktion der Zeit
Schwierigkeit: Geeignete Wahl der Zeitschritte (evtl. angepasst an die maximal mögliche Geschwindigkeit des jeweiligen Skills?)
Relativ hoher Aufwand bei einer großen Schrittzahl
Bisektion
Bestimmen des Ortes, an welchem der Skill dem Feind maximal nahe kommt; Dort nach Kollision prüfen
Verfahren: Beginnen bei Start- und Endpunkt. Halbieren des Intervalls in der Hälfte. Wählen des besseren Intervalls (z.B. durch bestimmen mehrerer Probepunkte und deren Distanz zum Feind innerhalb der Intervalle) und wiederholen der Methode für das gewählte Intervall
Problem: Fehleranfällig: Sobald ein Skill in irgendeiner Weise seine Richtung wechselt kann es vorkommen, dass durch Bisektion das „falsche“ Intervall gewählt wird (wenn z.B. ein Bumerang erst über den Feind fliegt, danach umdreht und ihn noch erwischt)
Ziemlich effizient
Nach aktuellem Stand werde ich es vorerst mit der iterativen Variante versuche
Das war eigentlich nur ein kleiner Nebengedanke mit geringer Relevanz… Ich versuche kurz die Situation zu erklären:
Unabhängig davon, wie die Kollision von zwei Rechtecken berechnet wird, befindet sich bei einer Bewegung das Rechteck zu verschiedenen Zeiten an verschiedenen Positionen. Auch bei geringem Delta werden manche (es gibt schließlich unendlich) Positionen vernachlässigt. Dadurch eben auch manche Pixel. Wenn Delta gering genug ist, ist dieser Fehler in der Praxis natürlich vernachlässigbar.
Nun, wenn dieser spezifische und vermeintlich irrelevante Punkt Einfluß auf die übergeordneten Fragen hat, ist eber eben nicht mehr irrelevant. Aber zumindest glaube ich nun, zu verstehen, was du meintest:
Das stimmt natürlich. Aber es ist so gesehen nur eine weitere Ausprägung des Diskretisierungsproblems. Bei größerer Geschwindigkeit würde das Projektil ja ggf. komplett durch den Gegner durchhüpfen, egal, ob die Bewegung horizontal oder vertikal oder diagonal ist.
Wie schon weiter oben erwähnt gibt es da mögliche Workarounds. Ein sehr suggestiver Ansatz wäre: Man betrachtet die Bewegungslinien der Eckpunkte (im Bild in Grün, aber natürlich für alle 4 Ecken), und prüft, ob diese Linien die Bounding Box des Gegeners schneiden. Aus den Schnittpunkten kann man dann sogar den genauen Zeitpunkt der Kollision bestimmen.
Als alternative könnte man die Kanten betrachten, und schauen, zu welchen Zeitpunkten die Kanten den gleichen x- bzw. y-Wert haben. Das bedeutet dann (ähnlich wie bei dem oben erwähnten Fall von Provot) die Nullstellen eines Polynoms zu finden, aber da es hier nur um die Kanten von AABBs geht, ist das deutlich einfacher. An den entsprechenden Zeitpunkten muss man dann aber nochmal einen “echten” Überschneidungstest der Boxes machen.
Bei einer sehr geringen Schrittweite würde dieses Problem nur eine geringe (bis keine) Rolle spielen, allerdings finde ich deine erste Idee ziemlich gut:
Das probiere ich mal aus, allerdings kann sich ein Gegner auch innerhalb der Bewegungslinien der Eckpunkte befinden, ohne diese zu schneiden.
Zu prüfen, ob sich etwas innerhalb dieser Bewegungslinien befindet wird vermutlich knifflig, da die Wahl der Eck-Verbindungen von den Positionen der Rechtecke abhängt: Mein erster Ansatz wäre, zwei Verbindungen auszuwählen (hier z.B. für das mittlerere und obere Rechtseck würden rot und grün ausgewählt werden) und zwischen ihnen eine Testfläche „aufzuspannen“, welche auf Schneiden mit dem Gegner überprüft wird. Nach welchen Kriterien bestimmte Linien ausgewählt werden, habe ich noch nicht durchdacht. Natürlich könnten stattdessen auch alle Linienpaare betrachtet werden (6 Kombinationen), was aber deutlich aufwändiger wäre (v.a. weil alle Operationen bei jedem Schritt ausgeführt werden).
Edit: Bei kleiner Schrittweite könnte vernachlässigt werden, ob sich ein Gegner komplett innerhalb der Bewegungslinien befindet, da das dann wohl ziemlich unwahrscheinlich wäre.
Du hättest immer eine vollständige Abdeckung der Fläche, wenn du die vier Paare rot/blau, rot/gelb, grün/blau und grün/gelb prüfen würdest.
Ob etwas innerhalb der Fläche liegt, lässt sich leicht analytisch ermitteln, indem man einen Vektorzug beschreibt, der über die Kantenvektoren zum zu überprüfenden Punkt führt.
Beispiel mittlere und obere Box, Fläche rot/blau. Dann müsstest du den roten Vektor bestimmen (sagen wir mal, der geht von links unten nach rechts oben) und den Vektor vom Fußpunkt des roten Vektors zum Fußpunkt des blauen Vektors.
Für jeden Punkt innerhalb der Fläche gilt, dass er sich mittels Addition der beiden Vektoren, die um jeweils einen Koeffizienten gestaucht werden, errechnen lässt. Wenn beide Koeffizienten innerhalb des Intervalles [0, 1] liegen, ist der Punkt in der Fläche.
Das sich ergebende Gleichungssystem ist in 2D immer eindeutig lösbar, sodass du es einmalig allgemein lösen kannst. Die sich ergebenden Formeln kannst du dann “fest verdrahten”, sodass nicht viel Rechenleistung für die Bestimmung der Koeffizienten benötigt wird.
Irgendwie werd’ ich aus deinen Bildern immer nicht ganz schlau (auch oder gerade in Kombination mit dem Geschriebenen). Über den Aufwand zum Testen von ein paar Linienpaaren würde ich mir aber keine Gedanken machen. Sofern nicht Kollisionen von 100 Objekten untereinander überprüft werden, sollte das kein Problem sein.
@cmrudolph
Danke dafür, das ist eine wirklich praktische Idee
@Marco13
Das meine Bilder etwas verwirrend sind ist mir jetzt auch aufgefallen, nachdem ich sie nochmal angeschaut habe. Das versuche ich jetzt zu verbessern. Teilweise entwickle ich viele neue Gedanken, während ich eine Antwort schreibe und ändere die dann mehrfach um, wodurch sie nicht unbedingt übersichtlicher wird
So, nach diesen ausführlichen Ideen würde ich den Thread erstmal als gelöst markieren. Aktuell muss ich mich noch viel auf Prüfungen vorbereiten, aber ich werde so früh wie möglich den iterativen Weg (inklusive Kantenvektoren) umsetzen. Dann poste ich hier ein kurzes Video über das Resultat.
Schon für den einfachsten Fall einer perfekten Schulbuch-Wurfparabel wird das etwas frickelig. Es ist natürlich interessant, und … deswegen bin ich mal für eine Stackoverflow-Antwort die „extra mile“ gegangen, und habe da etwas gebastelt:
Naja, egal: Wenn man die iterative Lösung einigermaßen allgemein macht, kann man sowas wohl relativ leicht einbauen.
(auch oder gerade in Kombination mit dem Geschriebenen). Über den Aufwand zum Testen von ein paar Linienpaaren würde ich mir aber keine Gedanken machen. Sofern nicht Kollisionen von 100 Objekten untereinander überprüft werden, sollte das kein Problem sein.