Abfangkursberechnung, review please

Ich denke wir hatten das Thema hier selbst noch nicht im Detail. Nur einmal in diesem Projektforum damals, aber das existiert ja nicht mehr.
Und da ich mich lang genug davor gedrückt habe und nun nach zwei Jahren Pause mal schaue, ob ich nicht doch mal wieder eine zeitgemäße Variante meines BGs bastle, die schon ewig geplant ist, steht das Thema Abfangkursberechnung wieder an.
Es gibt sicherlich viele Wege dies zu lösen, sei es mit Differentialgleichungen oder was auch immer, wo man dann auch unterwegs wechselnde Geschwindigkeiten bzw. Beschleunigung einberechnen kann. Mir reicht dann doch die trigonometrische Berechnung.
en.wikipedia.org/wiki/Torpedo_Data_Computer
TDC Functional Description + Figure 3
en.wikipedia.org/wiki/Image:Intercept.png
Das ist mir eine nette Hilfe gewesen.
Hier mein aktueller Code. Sicher noch nicht wirklich sauber und der %perl Block wird später auch noch ordentlich ausgelagert, aber es geht ja nur darum, dass es erstmal technisch funktioniert. Habe mal versucht es möglichst ausführlich und Schritt für Schritt zu machen, das ist also sicher kein Beweis, ob es auch mit 5 LoC geht. Wenn etwas überflüssig ist oder besser geht, bin ich aber auch gern offen für Kritik.
Meine Frage im speziellen dabei:
- ist das so korrekt und funktioniert einwandfrei?
- habe ich mögliche Szenarien vergessen, die nicht abgedeckt werden?
- gehen einige Dinge schöner, schneller, eleganter oder sonstwie toller?
- wie lässt sich das im Code markierte Problem mit Kursen, die quasi auf einer Linie liegen am effizientesten lösen (da kein Dreieck vorhanden) - das ist vor allem noch ein Problem mit Rundung oder Präzision, da die Sinusfunktion mir bei einigen werten ungenaue Resultate liefert, so dass ich nicht einfach schauen kann ob $asin == 0...
- was gibt es sonst für Möglichkeiten das Problem zu lösen? bzw. show me your code
- ich brauche nur 2d, andere vielleicht auch 3d, helft denjenigen ^^ (hmm da müsste man nur die Ebene entsprechend anders definieren/umrechnen, oder? So dass es quasi wieder 2d ist)

<%args>
$s1x => 0;
$s1y => 0;
$s1v => 10;
$d1x => 100;
$d1y => 0;
$s2x => 30;
$s2y => 30;
$s2v => 8;
<%perl>
use strict;
use warnings;
use diagnostics;
use Math::Trig;
# is it possible to intercept?
my $can_intercept = 0;
# squad 2 destination x, y
my $d2x = -1;
my $d2y = -1;
# time to travel
my $t = 0;
my $dist1 = sqrt(($d1x-$s1x)**2 + ($d1y-$s1y)**2);
my $dist2 = sqrt(($d1x-$s2x)**2 + ($d1y-$s2y)**2);
# check for impossible calculations
# s2 not moving
if($s2v == 0)
{
$d2x = "error, s2 not moving.";
}
# s1 not moving or s1 and s2 at same position
elsif(($s1v == 0) || ($s1x == $s2x && $s1y == $s2y))
{
$d2x = $s1x;
$d2y = $s1y;
$can_intercept = 1;
}
# s2 not faster than s1 but further away from target
elsif(($dist1 < $dist2) && ($s1v >= $s2v))
{
$d2x = "error, will never catch up.";
}
#######################################################################
########## can this be optimized? check bottom if $asin == 0 ##########
########## problem: rounding errors due to scalar precision ##########
#######################################################################
# s2 "in line" with s1's course and course delta x or delta y == 0
elsif(($d1x-$s1x == 0 && $s1x == $s2x) || ($d1y-$s1y == 0 && $s1y == $s2y))
{
$d2x = "error, in line and 90 degree angle.";
# TODO code to check whether it can catch up and where...
}
# s2 "in line" with s1's course
elsif(($d1x-$s1x != 0) && ($d1y-$s1y != 0) && ($s2x-$s1x)/($d1x-$s1x) == ($s2y-$s1y)/($d1y-$s1y))
{
$d2x = "error, in line.";
# TODO code to check whether it can catch up and where...
}
#######################################################################
########## can this be optimized? check bottom if $asin == 0 ##########
#######################################################################
# normal calculation
else
{
# angle bow
my $aA = -1;
# angle deflection
my $aB = -1;
# angle at collision point
my $aC = -1;

# vectors
my $v1x = $d1x - $s1x;
my $v1y = $d1y - $s1y;
my $v2x = $s1x - $s2x;
my $v2y = $s1y - $s2y;
# vector length
my $absv1 = sqrt($v1x * $v1x + $v1y * $v1y);
my $absv2 = sqrt($v2x * $v2x + $v2y * $v2y);
# normalization to length 1
$v1x /= $absv1;
$v1y /= $absv1;
$v2x /= $absv2;
$v2y /= $absv2;
# scalar product
my $sp = $v1x * $v2x + $v1y * $v2y;
# intersection angle for vectors
# only acos(sp) since the vectors are normalized
$aA = pi - acos($sp);
# this is just for varying velocity, if it is equal, $aB equals $aA of course
# law of sines
# $s2v * sin($aB) = $s1v * sin($aA)
# => ($s1v * sin($aA)) / $s2v = sin($aB)
my $asin = $s1v * sin($aA) / $s2v;
if($asin >= -1 && $asin <= 1)
{
$can_intercept = 1;
$aB = asin($asin);
$aC = pi - $aA - $aB;
# law of sines
# b = c * sin(beta) / sin(gamma)
my $dist = sqrt(($s2x-$s1x)**2 + ($s2y-$s1y)**2) * sin($aB) / sin($aC);
# time required
$t = $dist / $s1v;
# collision point = squad 2 destination
$d2x = $s1x + $t * $v1x * $s1v;
$d2y = $s1y + $t * $v1y * $s1v;
if($t > $dist1 / $s1v)
{
$can_intercept = 0;
$d2x = "error, s2 too slow to intercept.";
}
}
else
{
$d2x = "error, s2 too slow to intercept.";
}
}
% if ($can_intercept) {
interception possible!
dx: <% $d2x %>
dy: <% $d2y %>
time until interception: <% $t %>
% } else {
interception not possible!
reason: <% $d2x %>
%}

also erstmal: schönes problem, nicht? hab ich auch lange dran gesessen
dann noch der Hinweis an alle, die mehr als 2D machen: Da wir es hier mit 2 idR. lin. unabh. Vektoren zu tun haben die sich beide auf das ziel beziehen lassen haben wie immer ein Dreieck in einer wie auch immer gelagerten Ebene. Somit lässt sich die 2d-lösung auch auf den nD-Raum übertragen, indem man einfach nur die vektoren vergrößert und die Vektoroperationen anpasst.
So. Nun zu meiner Lösung. Am besten ist ich leide das nochmal her, sonst versteht man das kaum.
Nehmen wir an wir haben das Dreieck FTE (Feind, Treffpunkt, Eigen), dann können wir folgende sachen aussagen (t = zeitdiff bis zur ankunft, v = flugrichtung F, |w| = unsere geschwindigkeit):

a) |FE| = |F-E| (Strecke zwischen F und E ist einfach die Länge des differenzvektors)
b) T-F = v*t (Strecke vom Feind bis zum treffpunkt ist v*t)
c) |ET| = |w|*t
Wie wir sehen brauchen wir an sich nur die zeit berechnen und alles ist trivial lösbar.
Eine Bedingung ergibt sich noch: der Kosinus des Winkels gamma zwischen FE und FT ist auch noch am anfang gegeben und konstant und kann über das skalarprodukt errechnet werden.
Das ganze schmeissen wir nun in den Kosinussatz:

c^2 = a^2 + b^2 - 2ab cos gamma
=> |w|*t = |F-E|^2 + (|v|*t)^2 - 2*|F-E|*|v|*t*((F-E)*v)/|F-E|/|v|
=> |w|*t = |F-E|^2 + |v|^2 *t^2 - 2*t*((F-E)*v)
Das ganze ding stellen wir mal etwas um und erhalten:

t^2 - t*(2*((F-E)*v) - |w|)/|v|^2 + |F-E|^2/|v|^2 = 0
Das sieht ja verdächtig nach pq-formel aus, die wir auch prompt anwenden:

t = -((F-E)*v - |w|)/|v|^2 +- sqrt( ((F-E)*v - |w|)^2/|v|^4 - |F-E|^2/|v|^2)
Einsetzen, ausrechnen, fertig hat man die 2 Zeiten. Ist aber unter garantie nen fehler drin, weil ich in meinem script eine vollkommen andere formel hab. Aber die Herleitung hab ich grad nicht mehr zur hand - der weg ging auf jede fall so. Ich denke der fehler liegt beim einsetzen des Skalarproduktes in den Kosinussatz und die darauf folgende umstellung bis zur pq-formel.. wer will kann da ja ncohmal nachrechnen..
Noch zur erklärung:
- Kein wunder, dass es 2 mögliche zeiten sind. Die zeit ist linear und wenn man sich fückwärts bewegt gibt es logischerweise auch einen treffpunkt
- Die Bedingung, obwir abfangen können steht unter der Wurzel. Ist die determinante < 0 gibt es keinen treffpunkt.
- man sollte aufpassen, was man einsetzt. der PC ist nicht deterministisch und wenn sich |v| und |w| ähnlich sind, dann kann man schnell zu ergebnissen jenseits von gut und böse kommen. Falls sie Identisch sind hat man in der Formel untern ein div/0! Also muss das explizit abgefangen werden und in eine weitere Formel eingesetzt werden, die unter der Prämisse |v| = |w| hergeleitet wurde (die ist einfacher zu errechnen
).
umsetzung in php:
(ownX/Y = eigene position, maxv =abfanggeschwindigkeit, enemyX/Y = feindkoord, vX/Y = flugrichtung feind)

static function captureLinMoving($ownX,$ownY,$maxV, $enemyX, $enemyY, $vx, $vy) {
//1. calculate time
if (abs(pow($maxV,2) - pow($vx,2)-pow($vy,2)) < 0.1) {
/* both are nearly at same speed */
if (abs(2*($vx*($ownX-$enemyX)+$vy*($ownY-$enemyY))) < 0.1) /*course is nearly orthogonal to dist-vector => no meeting*/
return false;
$time = (pow($ownX-$enemyX,2)+pow($ownY-$enemyY,2))/(2*($vx*($ownX-$enemyX)+$vy*($ownY-$enemyY)));
$treffX = $enemyX+$vx*$time;
$treffY = $enemyY+$vy*$time;
if ($time < 0 OR $treffX > 10000 OR $treffX < 0 OR $treffY > 10000 OR $treffY <0)
return false;
$courseX = ($treffX-$ownX)/$time;
$courseY = ($treffY-$ownY)/$time;
return array('vx' => $courseX,'vy' => $courseY,'time' => $time,'treffX' => $treffX,'treffY' => $treffY);
}
//calc determinante. if < 0 no course is possible
$det = (pow($ownX-$enemyX,2)+pow($ownY-$enemyY,2))
/(pow($maxV,2)-pow($vx,2)-pow($vy,2))
* (pow($vx*($ownX-$enemyX)+$vy*($ownY-$enemyY),2)
/((pow($ownX-$enemyX,2)+pow($ownY-$enemyY,2))*(pow($maxV,2)-pow($vx,2)-pow($vy,2)))
+1);
if ($det < 0)
return false;
else {
$t = ($vx*($ownX-$enemyX)+$vy*($ownY-$enemyY))
/ (pow($maxV,2)-pow($vx,2)-pow($vy,2));
$t1 = $t + sqrt($det);
$t2 = $t - sqrt($det);
if ($t1 > 0 && $t2 > 0)
$time = min($t1,$t2);
elseif ($t1 < 0 && $t2 > 0)
$time = $t2;
elseif ($t1 > 0 && $t2 < 0)
$time = $t1;
else
$time = 0;
}
if ($time == 0)
return false;
//2. calculating position & course
$treffX = $enemyX+$vx*$time;
$treffY = $enemyY+$vy*$time;
if ($treffX > 10000 || $treffX < 0 || $treffY > 10000 || $treffY <0)
return false;
return array('vx' => $courseX,'vy' => $courseY,'time' => $time,'treffX' => $treffX,'treffY' => $treffY);
}

Danke schonmal für's reply und die Offenheit.
Hmm finde deinen Code aber ungleich komplizierter zu verstehen, auch wenn er kompakter ist. Mag auch an der widerlichen Syntax von PHP liegen, aber z.B.

$det = (pow($ownX-$enemyX,2)+pow($ownY-$enemyY,2))
/(pow($maxV,2)-pow($vx,2)-pow($vy,2))
* (pow($vx*($ownX-$enemyX)+$vy*($ownY-$enemyY),2)
/((pow($ownX-$enemyX,2)+pow($ownY-$enemyY,2))*(pow($maxV,2)-pow($vx,2)-pow($vy,2)))
+1)
Um so etwas nachzuvollziehen brauch ich 5 Minuten und muss mir rausschreiben, was genau jeder Teil bedeutet... dann lieber Zeile für Zeile, aber auf einen Blick verständlich.
Allerdings hast du durch dein "ungefähres" Errorhandling paar Fehler drin. Kann sein, dass die bei dir durch die Spielmechanik nicht auftreten (wenn es z.B. fest definierte Geschwindigkeiten gibt, die sich immer so unterscheiden, dass dieses "< 0.1" auch wirklich dieselbe Geschwindigkeit bedeutet, aber es ist auf jeden Fall keine 100% akkurate Lösung.
z.B. bei Geschwaderposition 0/0 mit Geschwindigkeit 100, Ziel 10000/0, Verfolger auf 0/5 mit Geschwindigkeit 100.0001 gibt es bei dir keine Kollision. In Wirklichkeit sollte das aber bei 3535.53 passieren. Das ist nur ein Beispiel von vielen, bei geringerem Y-Abstand, wäre die Kollision weit früher.
Auch wenn sich beide Geschwader ähnlich "schnell" und zugleich hinreichend langsam bewegen gibt dein Algorithmus immer false aus.
if (abs(2*($vx*($ownX-$enemyX)+$vy*($ownY-$enemyY))) < 0.1)
Ist ja nichts anderes als
if (abs(($vx*($ownX-$enemyX)+$vy*($ownY-$enemyY))) < 0.05)
D.h. wenn vx und vy sich 0 annähern, wird das Ergebnis auch kleiner als 0.05, egal wie die Koordinaten sind.
Das gleiche gilt für Abfragen wie
if ($time < 0 OR $treffX > 10000 OR $treffX < 0 OR $treffY > 10000 OR $treffY <0)
return false;
Es sind halt alles Dinge, die in direkter Abhängigkeit zur Spielmechanik stehen. Das mag funktionieren, kann aber auch nicht klappen. Und wenn du eines Tages etwas an der Spielmechanik änderst - kannst du dann noch garantieren an jeder Codestelle zu wissen, was funktioniert und was nicht?
Da ich mit genau so etwas (Überreste meiner Vorgänger) zuletzt ein paar Probleme hatte, ist mir das definitiv zu riskant und daher suche ich eine 100% valide Lösung und keine grobe Annäherung, vor allem beim Errorhandling. Zudem kann man dann eben auch ne Library draus basteln, die wirklich generisch ist und auch bei anderen Projekten wieder zum Einsatz kommen kann (<3 CPAN).
Btw:
aquaphobia.de/ic.html
Auf die Schnelle hingehackt und das erste mal mootools angetestet, um es ein wenig besser testen zu können. Kannst ja paar Testwerte ausprobieren, wäre vielleicht hübsch das für verschiedene Algorithmen zu haben, um vor allem Extreme testen zu können. Mit Taschenrechner und den Formeln zieht es sich ein wenig hin.

Original von Kallisti
Um so etwas nachzuvollziehen brauch ich 5 Minuten und muss mir rausschreiben, was genau jeder Teil bedeutet... dann lieber Zeile für Zeile, aber auf einen Blick verständlich.

Ja.. ich habs auch irgendwo nochmal ordentlich aufgeschrieben .. hab die formel in ein matheprogramm geworfen und den output gennommen.

Allerdings hast du durch dein "ungefähres" Errorhandling paar Fehler drin. Kann sein, dass die bei dir durch die Spielmechanik nicht auftreten (wenn es z.B. fest definierte Geschwindigkeiten gibt, die sich immer so unterscheiden, dass dieses "< 0.1" auch wirklich dieselbe Geschwindigkeit bedeutet, aber es ist auf jeden Fall keine 100% akkurate Lösung.
wie gesagt. Sind die identisch hab ich nen div/0 und für meine zwecke reicht eine solche abschätzung. die kann man bei bedarf noch feiner machen. Hab mir eben angewöhnt floats niemals mit == zu vergleichen, sondern immer abzuschätzen. Da die geschwinigkeit bei mir ohnehin nur ints sind, ist das genau genug. Da kommt der Fall |v| < 0.05 eben nicht vor.

Das gleiche gilt für Abfragen wie
if ($time < 0 OR $treffX > 10000 OR $treffX < 0 OR $treffY > 10000 OR $treffY <0)
return false;
Es sind halt alles Dinge, die in direkter Abhängigkeit zur Spielmechanik stehen. Das mag funktionieren, kann aber auch nicht klappen. Und wenn du eines Tages etwas an der Spielmechanik änderst - kannst du dann noch garantieren an jeder Codestelle zu wissen, was funktioniert und was nicht?
bei mir sind valide zielkoordinaten nur in dem bereich und an denen wird auch niemals gerüttelt.

Da ich mit genau so etwas (Überreste meiner Vorgänger) zuletzt ein paar Probleme hatte, ist mir das definitiv zu riskant und daher suche ich eine 100% valide Lösung und keine grobe Annäherung, vor allem beim Errorhandling. Zudem kann man dann eben auch ne Library draus basteln, die wirklich generisch ist und auch bei anderen Projekten wieder zum Einsatz kommen kann (<3 CPAN).
Naja.. bedenke nur, dass der PC nie genau rechnet. und wenn du mit sinus und == arbeitest, dann hast du da acuh immer fehler drin.
Edit:
Kann es sein, dass dein ding falsch rechnet?
bei 0|0 -> 1000|0 mit 100 abgefangen von 0|5 mit 100.1 dauerts 1.1
bei 100|0 -> 1000|0 mit 100 abgefangen von 0|5 mit 100.1 dauerts 0.5
eigentlich müsste das beim 2. mal nen paar einheiten länger dauern?!
Außerdem wieso ist dx = 150 und dy = 0 (=150 "lang") bei angegebener geschwindigkiet von 100.1?

d steht für destination, nicht delta
Aber ja, hast Recht, da fehlt auf jeden Fall noch eine Fehlerabfrage. Wäre in dem Fall nicht möglich abzufangen.
Kleiner Edit oben, jetzt müssten die errechneten Werte in deinem Beispiel stimmen und es müsste abgefragt werden, ob der Kollisionspunkt innerhalb der Strecke liegt.
Hoffe ich hab mich nicht vertan und nix anderes kaputt gemacht. xD

Entweder verstehe ich die Eingabe nicht, oder es existiert ein Fehler:
Geschwindigkeit der beiden Flotten = 0:
Abfang möglich?

Danke Wieder ein fehler gefunden. Klar, schön blöd erst zu gucken ob s1 still steht und dann zu sagen, wenn das der Fall ist, kann man immer abfangen und das Ziel ist die Posi von s1, bevor man guckt, ob sich s2 bewegt. Hab's umgedreht.

Und noch einer?!
Das Abfangschiff (2) ist schneller als das abzufangende. Daher ist ein Abfangen IMHO immer möglich. Insbesondere, wenn das 1. Schiff direkt auf das 2. zufährt.
Daraus folgend auch folgendes Problem:
Schiff 2 kann ruhig 0 fahren, Schiff 1 fährt direkt in 2 rein.

Ersteres ist " $d2x = "error, in line and 90 degree angle.";
# TODO code to check whether it can catch up and where...", also noch in Mache und nur noch nicht fertig. ^^
Das war ja der eigentliche Grund des Threads - ich wollte wissen wie ich das am effizientesten loese, weil ich in dem Fall kein Dreieck mehr habe und die andere Berechnung nicht funktioniert.
Zweiteres kann man diskutieren, ob manoevrierunfaehige Schiffe in der Lage sind ein sich bewegendes Geschwader abzufangen.

Naja, das andere würde dann wohl einfach "außen rum" fliegen, so 2cm weiter weg als deren Waffenreichweite und würden über gigantische Lautsprecher ein "Haha" von Nelson loslassen.
Ist doch recht einfach.

WENN(a sich nicht bewegt)
WENN (b am standpunkt von a vorbeikommt)
Explodiere();

Natuerlich ist es einfach, aber ich finde es nicht realistisch. Das ganze ist ja nur ein Realitaetsmodell. Nur weil auf dem Papier "0 Einheiten" Entfernung steht, heisst das nicht, dass da nicht einige Meter dazwischen sind bzw. dass es kein Terrain etc. gibt, dass man nicht ein wenig nutzen koennte.
Eine Geschwindigkeit von 0 haben bei uns nur komplett manoevrierunfaehige Schiffe, und die koennen sich nicht einmal in Richtung des Ziels ausrichten. ^^ und Kamikatze-Geschwader sind das auch nicht.
Trotzdem auf jeden Fall schonmal danke fuer die Ideen und das Ausprobieren, vielleicht findet sich ja noch die ein oder andere Luecke oder Loesung.

so jetzt hab ich mich auch mal in Info damit beschäftigt
also wenn man die Position des Zieles mit Z (eig. Vektor OZ) bezeichnet, und das Schiff, dessen Kurs gefunden werden soll mit F (wieder OF). Für den Treffpunkt ist es OT.
Der Kurs d. Zieles ist:
Vektor x = Vektor OZ + Vektor der Geschwindigkeit vom Ziel * Zeit t
Der Kurs d. anderen Schiffes (im Folgenden Schiff 2) ist:
Vektor x = Vektor OF + Vektor der Geschwindigkeit des Schiffes * Zeit t
Daraus folgt, dass das Schiff 2 aufhohlen muss, nämlich die Strecke um die FT größer ist als ZT, also Betrag von FZ (da bin ich mir aber net 100% sicher).
Betrag(OZ-OF) = (Betrag von Geschwindigkeit 1 - Betrag von Geschwindigkeit 2) * t
dabei sind die Beträge als die Beträge der Vektoren anzusehen
Der Betrag von Geschwindigkeit 2 ist bekannt (gegeben) und man kann so t ausrechnen. Dabei überprüfen ob
Betrag(OZ-OF) == 0 --> gleiche Position (--> gleichen Kurs setzten wie Ziel)
(Betrag von Geschwindigkeit 1 - Betrag von Geschwindigkeit 2) <= 0 (und 1. Fall nicht true EDIT: Je nach dem Design ist Fall 1 egal, nämlich dann wenn das Schiff sozusagen schon den Zug verpasst hat, zwar auf der gleichen Pos. steht aber im nächsten "Tick" oder sowas schon keine Chance mehr hat) --> Schiff 2 chancenlos
dann einfach aus der Formel t berechnen.
Den Treffpunkt kann mann dann durch Vektor x = Vektor OZ + Vektor der Geschwindigkeit vom Ziel * Zeit t berechnen. Daraus kann man dann ja simpel den Kurs von Schiff 2 (und somit deren nötigen Geschwindigkeitsvektor) berechnen.
Also eigentlich total simple. Aber ich weiß leider net ob die Annahme mit der "mehr zurückzulegenen" Strecke stimmt... aber ich denke schon
EDIT: wie solls anders sein, stimmt natürlich nicht... ich werd mal weiter an ner Lösung tüfteln...

Ist zwar noch weit davon entfernt perfekt zu sein (grad der symbolexport, Fehlerabfrage und oop Aspekt), aber auch mein erstes Perl Modul seit zwei Jahren und verrichtet seine Arbeit. Die Berechnung sollte nun komplett sein. Wenn nicht sagt bitte was falsch ist oder fehlt.
Vielleicht hilft es ansonsten dem ein oder andern als Anregung, wenn er selbst das Problem hat (merke, das hier unterliegt derweil keiner Open Source Lizenz).
Rechenzeit dafuer auf meinem aktuellen Rootserver (neuer DS 3000 bei Hetzner) ist im gruenen Bereich.
0.00012x sec fuer die reine Kursberechnung
0.00017x sec inkl. Laden des Perlmoduls

package Aquaphobia::Algorithms::Intercept;

use strict;
use warnings;
use diagnostics;
use Math::Trig;
use vars qw(@ISA @EXPORT $VERSION);
our @ISA = qw(Exporter);
our @EXPORT = qw(calc_ic);
our $VERSION = '0.10';
# squad 1/2 coords and velocity
my $s1x;
my $s1y;
my $s1v;
my $s2x;
my $s2y;
my $s2v;
# squad 1 destination
my $d1x;
my $d1y;
# interception point eq squad 2 destination
my $d2x;
my $d2y;
# time to travel
my $t;
# distance from squad 1/2 to squad 1 destination
my $dist1;
my $dist2;
sub new {
my $package = shift;

return bless({}, $package);
}
sub calc_ic {
my $self = shift;
reset_vars();
$s1x = shift;
$s1y = shift;
$s1v = shift;
$s2x = shift;
$s2y = shift;
$s2v = shift;
$d1x = shift;
$d1y = shift;
if(check_vars())
{ return (-1, -1, -1); }

return calc_course();
}
# reset variable values
sub reset_vars
{
$d2x = 0;
$d2y = 0;
$t = -1;
undef($s1x);
undef($s1y);
undef($s1v);
undef($s2x);
undef($s2y);
undef($s2v);
undef($d1x);
undef($d1y);
}
# all variables defined?
sub check_vars
{
return !(
defined($s1x) &&
defined($s1y) &&
defined($s1v) &&
defined($s2x) &&
defined($s2y) &&
defined($s2v) &&
defined($d1x) &&
defined($d1y)
);
}
# and now the real calculation
sub calc_course
{
# distances from s1/s2 to s1 destination
$dist1 = sqrt(($d1x-$s1x)**2 + ($d1y-$s1y)**2);
$dist2 = sqrt(($d1x-$s2x)**2 + ($d1y-$s2y)**2);
# check for impossible calculations / special cases
# s2 not moving
if($s2v == 0)
{
$d2x = "error, s2 not moving.";
}
# s1 not moving or s1 and s2 at same position
elsif(($s1v == 0) || ($s1x == $s2x && $s1y == $s2y))
{
$d2x = $s1x;
$d2y = $s1y;
$t = sqrt(($s2x-$s1x)**2 + ($s2y-$s1y)**2) / $s2v;
}
# s2 not faster than s1 but further away from target
elsif(($dist1 < $dist2) && ($s1v >= $s2v))
{
$d2x = "error, will never catch up.";
}
# s2 "in line" with s1's course and course delta x or delta y == 0
elsif((($d1x-$s1x == 0 && $s1x == $s2x) || ($d1y-$s1y == 0 && $s1y == $s2y)) ||
(($d1x-$s1x != 0) && ($d1y-$s1y != 0) && ($s2x-$s1x)/($d1x-$s1x) ==
($s2y-$s1y)/($d1y-$s1y)))
{
# some imaginary calculation, put s1 to (0/0)
# put s2 to (dist s1 s2/0) if s2
# 0 + $s1v * x = $sdist - $s2v * x
# $s1v * x + $s2v * x = $sdist
my $sdist = sqrt(($s2x-$s1x)**2 + ($s2y-$s1y)**2);
if($dist1 < $dist2 && $sdist < $dist1)
{
$t = (-1) * $sdist / ($s1v - $s2v);
}
else
{
$t = $sdist / ($s1v + $s2v);
}
# vectors
my $v1x = $d1x - $s1x;
my $v1y = $d1y - $s1y;
# vector length
my $absv1 = sqrt($v1x * $v1x + $v1y * $v1y);
# normalization to length 1
$v1x /= $absv1;
$v1y /= $absv1;
$d2x = $s1x + $t * $v1x * $s1v;
$d2y = $s1y + $t * $v1y * $s1v;
}
# normal calculation
else
{
# angle bow
my $aA = -1;
# angle deflection
my $aB = -1;
# angle at collision point
my $aC = -1;

# vectors
my $v1x = $d1x - $s1x;
my $v1y = $d1y - $s1y;
my $v2x = $s1x - $s2x;
my $v2y = $s1y - $s2y;
# vector length
my $absv1 = sqrt($v1x * $v1x + $v1y * $v1y);
my $absv2 = sqrt($v2x * $v2x + $v2y * $v2y);
# normalization to length 1
$v1x /= $absv1;
$v1y /= $absv1;
$v2x /= $absv2;
$v2y /= $absv2;
# scalar product
my $sp = $v1x * $v2x + $v1y * $v2y;
# intersection angle for vectors
# only acos(sp) since the vectors are normalized
#if($dist1 > $dist2)
#{ $aA = pi - acos($sp); }
#else
#{ $aA = pi - acos($sp); }
$aA = pi - acos($sp);
# this is just for varying velocity, if it is equal, $aB equals $aA of course
# law of sines
# $s2v * sin($aB) = $s1v * sin($aA)
# => ($s1v * sin($aA)) / $s2v = sin($aB)
#print " ++ taking asine of: ".($s1v * sin($aA) / $s2v)."\n";
my $asin = $s1v * sin($aA) / $s2v;
if($asin >= -1 && $asin <= 1)
{
$aB = asin($asin);
$aC = pi - $aA - $aB;
# law of sines
# b = c * sin(beta) / sin(gamma)
my $dist = sqrt(($s2x-$s1x)**2 + ($s2y-$s1y)**2) * sin($aB) / sin($aC);
# time required
$t = $dist / $s1v;
# collision point = squad 2 destination
$d2x = $s1x + $t * $v1x * $s1v;
$d2y = $s1y + $t * $v1y * $s1v;
}
else
{
$d2x = "error, s2 too slow to intercept.";
}
}
if($t > $dist1 / $s1v)
{
$d2x = "error, s2 too slow to intercept.";
$t = -1;
}
my @result;
$result[0] = $d2x;
$result[1] = $d2y;
$result[2] = $t;
return @result;
}
1;
__END__