Zeitpunkt geringster Distanz zweier sich bewegender Punkte

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	Fetze Betreff: Zeitpunkt geringster Distanz zweier sich bewegender Punkte	So, Dez 10, 2006 0:37 Antworten mit Zitat
Hi Ich habe mal wieder ein Problem, diesmal ein mathematisches. Zwecks Kollisionswahrscheinlichkeitsprüfung für eine NPC-KI, die rechtzeitig ausweichen kann, benötige ich eine Funktion, die mir errechnet, zu welchem Zeitpunkt die Entfernung zweier linear aber jeweils unterschiedlich schnell bewegter Punkte ausgehend von der derzeitigen Position und Geschwindigkeit minimal ist. Mithilfe dieses Zeitpunktes könnte ich die konkrete Distanz ausrechnen und somit wüsste ich, ob bei den beiden punkten eine Kollisionsgefahr besteht oder nicht. Mein erster Ansatzpunkt war es, eine mathematische Funktion d aufzustellen, die in abhängigkeit von der Zeit t die Distanz der beiden Punkte zurückliefert.. jedoch erwies sich der Versuch, diese Funktion korrekt abzuleiten, um die Ableitung Null zu setzen und die Minima zu errechnen als nicht praktikabel, da die vier Zusatzparameter während der nötigen Umformungen eine Masse von geschätzt 196 Termen anhäuften. Diese Möglichkeit fällt also weg, sofern ich keinen groben Fehler begangen habe. Ich bräuchte einen guten Alternativvorschlag.. wie erfahre ich nun, zu welchem Zeitpunkt die Distanz der beiden linear bewegten Punkte minimal ist? Ich würde mich auch damit zufrieden geben, wenn ich direkt die dortige Distanz hätte. Dabei ist jedoch zu beachten: Das hier ist keine simple Schnittpunktbestimmung zwischen zwei geraden, da es sich hier nicht um Gerade nim eigentlichen Sinne handelt, weil die Geschwindigkeit der einzelnen Punkte eben auch noch eine Rolle spielt. Wäre für jede Hilfe dankbar.

Fetze

Betreff: Zeitpunkt geringster Distanz zweier sich bewegender Punkte

So, Dez 10, 2006 0:37
Antworten mit Zitat

Hi

Ich habe mal wieder ein Problem, diesmal ein mathematisches. Zwecks Kollisionswahrscheinlichkeitsprüfung für eine NPC-KI, die rechtzeitig ausweichen kann, benötige ich eine Funktion, die mir errechnet, zu welchem Zeitpunkt die Entfernung zweier linear aber jeweils unterschiedlich schnell bewegter Punkte ausgehend von der derzeitigen Position und Geschwindigkeit minimal ist. Mithilfe dieses Zeitpunktes könnte ich die konkrete Distanz ausrechnen und somit wüsste ich, ob bei den beiden punkten eine Kollisionsgefahr besteht oder nicht.

Mein erster Ansatzpunkt war es, eine mathematische Funktion d aufzustellen, die in abhängigkeit von der Zeit t die Distanz der beiden Punkte zurückliefert.. jedoch erwies sich der Versuch, diese Funktion korrekt abzuleiten, um die Ableitung Null zu setzen und die Minima zu errechnen als nicht praktikabel, da die vier Zusatzparameter während der nötigen Umformungen eine Masse von geschätzt 196 Termen anhäuften. Diese Möglichkeit fällt also weg, sofern ich keinen groben Fehler begangen habe.

Ich bräuchte einen guten Alternativvorschlag.. wie erfahre ich nun, zu welchem Zeitpunkt die Distanz der beiden linear bewegten Punkte minimal ist? Ich würde mich auch damit zufrieden geben, wenn ich direkt die dortige Distanz hätte. Dabei ist jedoch zu beachten: Das hier ist keine simple Schnittpunktbestimmung zwischen zwei geraden, da es sich hier nicht um Gerade nim eigentlichen Sinne handelt, weil die Geschwindigkeit der einzelnen Punkte eben auch noch eine Rolle spielt.

Wäre für jede Hilfe dankbar.

	Rone	So, Dez 10, 2006 3:28 Antworten mit Zitat
moin, dein Ansatz scheint mir logisch. Wenn das mit dem ableiten nicht klappt, kann man auch die Distanzen in ein Array speichern und anschließend vergleichen an welcher stelle die Distanz am niedrigsten ist. Zusätzlich könnte man eine genauigkeit festlegen, z.B. G=0.1...dann wäre array[1] = 0.1s und array[2]=0.2s usw. Is zwar nicht exakt, aber bei nicht übertriebener Genauigkeit, simpel und schnell... Hab mal grad so ähnlich einen test gemacht: CeckMinDistance:Float(p1:Tpoint, p2:TPoint, genauigkeit:Float=0.1) gibt die Sekunden bis zum minimum an... Code: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict Graphics 800 , 600 Type TPoint Field Xpos:Float Field Ypos:Float Field SpeedX:Float Field SpeedY:Float Method Create:TPoint(x:Int,y:Int,speedx:Float,speedY:Float) Self.Xpos = x Self.Ypos = y Self.SpeedX = SpeedX Self.SpeedY = SpeedY Return Self End Method Method Move() Xpos:+(SpeedXframetime) Ypos:+(SpeedYframetime) End Method Method Move2() Xpos:+(SpeedX) Ypos:+(SpeedY) End Method Method Draw() DrawOval Xpos-10,Ypos-10,20,20 End Method Method Distance:Float(p:TPoint) Return Sqr((Self.xpos-p.xpos)(Self.xpos-p.xpos)+(Self.ypos-p.ypos)(Self.ypos-p.ypos)) End Method Function CeckMinDistance:Float(p1:Tpoint, p2:TPoint, genauigkeit:Float=0.1) Local d:Float = p1.Distance(p2) Local newD:Float = d,count:Int=0 Local tmpP1:Tpoint = New TPoint.Create(p1.Xpos,p1.Ypos,p1.SpeedXgenauigkeit,p1.SpeedYgenauigkeit) Local tmpP2:Tpoint = New TPoint.Create(p2.Xpos,p2.Ypos,p2.SpeedXgenauigkeit,p2.SpeedYgenauigkeit) While newD<=d count:+1 tmpP1.Move2() tmpP2.Move2() d=newD newD=tmpP1.Distance(tmpP2) Wend If count > 1 Then Return countgenauigkeit Else Return -1 EndIf End Function End Type Local p1:TPoint = New TPoint.Create(50,50,20,20) Local p2:TPoint = New TPoint.Create(750,550,-20,-20) Global frametime:Float Global time:Int = MilliSecs() Global timer:Int Repeat timer = MilliSecs() - time time = MilliSecs() frametime = timer 0.001 Cls p1.Move() p2.Move() p1.Draw() p2.Draw() DrawText ("fps: "+1.0/frametime),10,10 DrawText ("Time to minimum: "+Tpoint.CeckMinDistance(p1,p2)+" sec"),500,580 DrawText ("P1-speed: "+Sqr(p1.speedX^2+p1.speedY^2)+" pix/sec"),10,540 DrawText ("P2-speed: "+Sqr(p2.speedX^2+p2.speedY^2)+" pix/sec"),10,560 DrawText ("Distance: "+p1.Distance(p2)+" pix"),10,580 Flip 0 Until KeyHit(KEY_ESCAPE) EndGraphics mfg

Rone

So, Dez 10, 2006 3:28
Antworten mit Zitat

moin,

dein Ansatz scheint mir logisch. Wenn das mit dem ableiten nicht klappt, kann man auch die Distanzen in ein Array speichern und anschließend vergleichen an welcher stelle die Distanz am niedrigsten ist. Zusätzlich könnte man eine genauigkeit festlegen, z.B. G=0.1...dann wäre array[1] = 0.1s und array[2]=0.2s usw.
Is zwar nicht exakt, aber bei nicht übertriebener Genauigkeit, simpel und schnell...

Hab mal grad so ähnlich einen test gemacht:

CeckMinDistance:Float(p1:Tpoint, p2:TPoint, genauigkeit:Float=0.1) gibt die Sekunden bis zum minimum an...

Code: [AUSKLAPPEN]

SuperStrict
Graphics 800 , 600

Type TPoint

Field Xpos:Float
Field Ypos:Float

Field SpeedX:Float
Field SpeedY:Float

Method Create:TPoint(x:Int,y:Int,speedx:Float,speedY:Float)
   Self.Xpos = x
   Self.Ypos = y
   Self.SpeedX = SpeedX
   Self.SpeedY = SpeedY
   Return Self
End Method

Method Move()
   Xpos:+(SpeedX*frametime)
   Ypos:+(SpeedY*frametime)
End Method

Method Move2()
   Xpos:+(SpeedX)
   Ypos:+(SpeedY)
End Method

Method Draw()
   DrawOval Xpos-10,Ypos-10,20,20
End Method

Method Distance:Float(p:TPoint)
   Return Sqr((Self.xpos-p.xpos)*(Self.xpos-p.xpos)+(Self.ypos-p.ypos)*(Self.ypos-p.ypos))
End Method

Function CeckMinDistance:Float(p1:Tpoint, p2:TPoint, genauigkeit:Float=0.1)
   Local d:Float = p1.Distance(p2)
   Local newD:Float = d,count:Int=0

   Local tmpP1:Tpoint = New TPoint.Create(p1.Xpos,p1.Ypos,p1.SpeedX*genauigkeit,p1.SpeedY*genauigkeit)
   Local tmpP2:Tpoint = New TPoint.Create(p2.Xpos,p2.Ypos,p2.SpeedX*genauigkeit,p2.SpeedY*genauigkeit)


   While newD<=d
      count:+1
      tmpP1.Move2()
      tmpP2.Move2()
      d=newD
      newD=tmpP1.Distance(tmpP2)
   Wend

   If count > 1 Then
      Return count*genauigkeit
   Else
      Return -1
   EndIf
End Function

End Type

Local p1:TPoint = New TPoint.Create(50,50,20,20)
Local p2:TPoint = New TPoint.Create(750,550,-20,-20)

Global frametime:Float
Global time:Int = MilliSecs()
Global timer:Int
Repeat

timer = MilliSecs() - time
time = MilliSecs()
frametime = timer * 0.001

Cls

p1.Move()
p2.Move()

p1.Draw()
p2.Draw()

DrawText ("fps: "+1.0/frametime),10,10
DrawText ("Time to minimum: "+Tpoint.CeckMinDistance(p1,p2)+" sec"),500,580
DrawText ("P1-speed: "+Sqr(p1.speedX^2+p1.speedY^2)+" pix/sec"),10,540
DrawText ("P2-speed: "+Sqr(p2.speedX^2+p2.speedY^2)+" pix/sec"),10,560
DrawText ("Distance: "+p1.Distance(p2)+" pix"),10,580

Flip 0

Until KeyHit(KEY_ESCAPE)

EndGraphics

mfg

	Fetze	So, Dez 10, 2006 10:03 Antworten mit Zitat
Das habe ich mir auch schon überlegt, hat aber den entscheidenden Nachteil, dass extrem viele Distanzberechnungen gemacht werden müssen, die auch mit den besten performance-Verbesserungen einiges an Zeit brauchen - zumal ich diese Berechnungen pro Frame im Ernstfall um die 600 Mal durchführen muss (Wenn wir annehmen, dass ich 60 Raumschiffe habe, von denen jedes 10 Stück um sich hat, die auf Kollisionswahrscheinlichkeit geprüft werden). Das ganze ließe sich natürlich noch mit bestimmten Suchmustern anreichern, um die Prüfungszahl zu verringern aber letztendlich wird es wohl länger dauern als mit konkreter Formel - und ich habe mir doch sehr vorgenommen, das Spiel so prozessorfreundlich wie möglich zu halten.

Fetze

So, Dez 10, 2006 10:03
Antworten mit Zitat

Das habe ich mir auch schon überlegt, hat aber den entscheidenden Nachteil, dass extrem viele Distanzberechnungen gemacht werden müssen, die auch mit den besten performance-Verbesserungen einiges an Zeit brauchen - zumal ich diese Berechnungen pro Frame im Ernstfall um die 600 Mal durchführen muss (Wenn wir annehmen, dass ich 60 Raumschiffe habe, von denen jedes 10 Stück um sich hat, die auf Kollisionswahrscheinlichkeit geprüft werden).

Das ganze ließe sich natürlich noch mit bestimmten Suchmustern anreichern, um die Prüfungszahl zu verringern aber letztendlich wird es wohl länger dauern als mit konkreter Formel - und ich habe mir doch sehr vorgenommen, das Spiel so prozessorfreundlich wie möglich zu halten.

	Fetze	So, Dez 10, 2006 13:40 Antworten mit Zitat
Okay, dank Omnibrain (Nicht hier aus dem Forum) habe ich nun die Lösung. Vielleicht hilfts ja sonst noch jemandem, daher hier die Functions: Code: [AUSKLAPPEN] [EINKLAPPEN] 'Liefert den Zeitpunkt in Frames zurück, an dem die Distanz der zwei angegebenen, sich linear bewegenden Punkte 'minimal ist. Wird der Wert negativ, war die Distanz bereits zu einem früheren Zeitpunkt minimal und wird im 'folgenden höchstens noch größer. Function TPLMinDistTime:Float(fParX1:Float, fParY1:Float, fParXSpeed1:Float, fParYSpeed1:Float, fParX2:Float, fParY2:Float, fParXSpeed2:Float, fParYSpeed2:Float) Local fTime:Float = -((fParY1 - fParY2) * (fParYSpeed1 - fParYSpeed2)) - ((fParX1 - fParX2) * (fParXSpeed1 - fParXSpeed2)) fTime:/ ( ((fParXSpeed1 - fParXSpeed2) * (fParXSpeed1 - fParXSpeed2)) + ((fParYSpeed1 - fParYSpeed2) * (fParYSpeed1 - fParYSpeed2)) ) Return fTime End Function 'Basierend auf 2PLMinDistTime liefert diese Funktion die zukünftige minimale Distanz der beiden sich linear 'bewegenden Punkte zurück. Ist der Rückgabewert -1, hat der Zeitpunkt minimaler Distanz bereits stattgefunden. 'Das ist insofern sinnvoll, dass schließlich keine Kollisionswarnungen rausgegeben werden sollen, wenn die 'mögliche Kollision in der Vergangenheit oder nur bei umgekehrter Zeitlinie stattfindet. Ohne diese hier 'zu sehende fTime-basierte Fallunterscheidung würde diese Funktion einfach immer die korrekte Minimaldistanz 'zurückliefern. Function TPLMinDist:Float(fParX1:Float, fParY1:Float, fParXSpeed1:Float, fParYSpeed1:Float, fParX2:Float, fParY2:Float, fParXSpeed2:Float, fParYSpeed2:Float) Local fTime:Float = TPLMinDistTime(fParX1, fParY1, fParXSpeed1, fParYSpeed1, fParX2, fParY2, fParXSpeed2, fParYSpeed2) If fTime < 0.0 Then Return -1.0 Else Return Distance(fParX1 + fParXSpeed1 * fTime, fParY1 + fParYSpeed1 * fTime,.. fParX2 + fParXSpeed2 * fTime, fParY2 + fParYSpeed2 * fTime) End If End Function 'Gibt die Entfernung zwischen den beiden angegebenen Punkten zurück. Function Distance:Float(fParX1:Float, fParY1:Float, fParX2:Float = 0, fParY2:Float = 0) Return Sqr((fParX1 - fParX2) * (fParX1 - fParX2) + (fParY1 - fParY2) * (fParY1 - fParY2)) End Function

Fetze

So, Dez 10, 2006 13:40
Antworten mit Zitat

Okay, dank Omnibrain (Nicht hier aus dem Forum) habe ich nun die Lösung. Vielleicht hilfts ja sonst noch jemandem, daher hier die Functions:

Code: [AUSKLAPPEN]

'Liefert den Zeitpunkt in Frames zurück, an dem die Distanz der zwei angegebenen, sich linear bewegenden Punkte
'minimal ist. Wird der Wert negativ, war die Distanz bereits zu einem früheren Zeitpunkt minimal und wird im
'folgenden höchstens noch größer.
Function TPLMinDistTime:Float(fParX1:Float, fParY1:Float, fParXSpeed1:Float, fParYSpeed1:Float, fParX2:Float, fParY2:Float, fParXSpeed2:Float, fParYSpeed2:Float)
Local fTime:Float = -((fParY1 - fParY2) * (fParYSpeed1 - fParYSpeed2)) - ((fParX1 - fParX2) * (fParXSpeed1 - fParXSpeed2))
fTime:/ ( ((fParXSpeed1 - fParXSpeed2) * (fParXSpeed1 - fParXSpeed2)) + ((fParYSpeed1 - fParYSpeed2) * (fParYSpeed1 - fParYSpeed2)) )
Return fTime
End Function

'Basierend auf 2PLMinDistTime liefert diese Funktion die zukünftige minimale Distanz der beiden sich linear
'bewegenden Punkte zurück. Ist der Rückgabewert -1, hat der Zeitpunkt minimaler Distanz bereits stattgefunden.
'Das ist insofern sinnvoll, dass schließlich keine Kollisionswarnungen rausgegeben werden sollen, wenn die
'mögliche Kollision in der Vergangenheit oder nur bei umgekehrter Zeitlinie stattfindet. Ohne diese hier
'zu sehende fTime-basierte Fallunterscheidung würde diese Funktion einfach immer die korrekte Minimaldistanz
'zurückliefern.
Function TPLMinDist:Float(fParX1:Float, fParY1:Float, fParXSpeed1:Float, fParYSpeed1:Float, fParX2:Float, fParY2:Float, fParXSpeed2:Float, fParYSpeed2:Float)
Local fTime:Float = TPLMinDistTime(fParX1, fParY1, fParXSpeed1, fParYSpeed1, fParX2, fParY2, fParXSpeed2, fParYSpeed2)
If fTime < 0.0 Then
   Return -1.0
Else
   Return Distance(fParX1 + fParXSpeed1 * fTime, fParY1 + fParYSpeed1 * fTime,..
               fParX2 + fParXSpeed2 * fTime, fParY2 + fParYSpeed2 * fTime)
End If
End Function

'Gibt die Entfernung zwischen den beiden angegebenen Punkten zurück.
Function Distance:Float(fParX1:Float, fParY1:Float, fParX2:Float = 0, fParY2:Float = 0)
Return Sqr((fParX1 - fParX2) * (fParX1 - fParX2) + (fParY1 - fParY2) * (fParY1 - fParY2))
End Function

Übersicht

BlitzMax, BlitzMax NG

Allgemein

Nach Oben

BlitzBasic Portal

Zeitpunkt geringster Distanz zweier sich bewegender Punkte

Fetze

Betreff: Zeitpunkt geringster Distanz zweier sich bewegender Punkte

Rone

Fetze

Fetze