Circle/Circle Kollisionsprüfung - Geht's auch schneller?

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	Fetze Betreff: Circle/Circle Kollisionsprüfung - Geht's auch schneller?	Mo, März 20, 2006 17:29 Antworten mit Zitat
Hi Ich arbeite derzeit an einem kleinen Kollisionssystem, das zwei "ColShapes" - so heisst der Type - auf Kollision prüft und Kollisionspunkte sowie resultierenden Vektor (Den Vektor, mit dem eines der ColShapes verschoben werden müsste, damit es keine Überlappung der ColShapes mehr gibt) zurückliefert. Ein ColShape hat eine beliebige Anzahl an Kreisen, d.h. Punkten mit Radien sowie eine derzeitige Position. Bei einer Kollisionsprüfung wird jeder Kreis von ColShape A mit jedem Kreis von ColShape B auf Kollision, d.h. entsprechende Entfernung geprüft. Das funktioniert auch alles so weit, allerdings bin ich mit der Geschwindigkeit noch nicht hundertprozentig zufrieden, aber ich hab keine Ahnung, wie ich das hier noch schneller bekommen soll (Ja, ich rufe das auch nur auf, wenn unbedingt notwendig). Falls jemand eine Idee hat, bitte posten. Ansonsten können Mathe-Phobiker das hier gerne als Denkanstoß verwenden, mit Ausnahme der Kollisionspunkte, die sind bisher ungetestet ^^ Code: [AUSKLAPPEN] [EINKLAPPEN] 'cspParShape -> ColShape, mit dem Self geprüft werden soll 'fVarColX[] -> KollisionsPunkt X 'fVarColY[] -> KollisionsPunkt Y 'fVarResXVec -> Resultierender Vektor, X-Richtung. 'fVarResYVec -> Resultierender Vektor, Y-Richtung. Method CollidedWith2:Byte(cspParShape:ColShape, fVarColX:Float[] Var, fVarColY:Float[] Var, fVarResXVec:Float Var, fVarResYVec:Float Var) Local iLoop:Int Local iLoop2:Int Local iMaxDistTemp:Int 'Summe zweier zu prüfender Radien Local fDistTemp:Float 'Distanz zweier Kreise, manchmal im Quadrat Local bCollision:Byte 'Hat eine Kollision stattgefunden? Local fXDif:Float 'X-Differenz zweier Kreise Local fYDif:Float 'Y-Differenz zweier Kreise 'Rückgabewerte nullen. fVarResXVec = 0.0 fVarResYVec = 0.0 fVarColX = New Float[0] fVarColY = New Float[0] For iLoop = 0 To iCircleNum - 1 For iLoop2 = 0 To cspParShape.iCircleNum - 1 iMaxDistTemp = (iCircleRadius[iLoop] + cspParShape.iCircleRadius[iLoop2]) fXDif = ((cspParShape.fX + cspParShape.fCircleX[iLoop2]) - (fX + fCircleX[iLoop])) fYDif = ((cspParShape.fY + cspParShape.fCircleY[iLoop2]) - (fY + fCircleY[iLoop])) If Abs(fXDif) < iMaxDistTemp And Abs(fYDif) < iMaxDistTemp Then fDistTemp = (fXDif * fXDif) + (fYDif * fYDif) If fDistTemp < (iMaxDistTemp * iMaxDistTemp) Then fDistTemp = Sqr(fDistTemp) fVarResXVec:+ (fXDif / fDistTemp) * -(iMaxDistTemp - fDistTemp) fVarResYVec:+ (fYDif / fDistTemp) * -(iMaxDistTemp - fDistTemp) fVarColX = fVarColX[..fVarColX.length + 1] fVarColY = fVarColY[..fVarColY.length + 1] fVarColX[fVarColX.length - 1] = (fXDif / fDistTemp) * (Float(iCircleRadius[iLoop]) - ((iMaxDistTemp - fDistTemp) / 2.0)) fVarColY[fVarColY.length - 1] = (fYDif / fDistTemp) * (Float(iCircleRadius[iLoop]) - ((iMaxDistTemp - fDistTemp) / 2.0)) bCollision = True End If End If Next Next Return bCollision End Method

Fetze

Betreff: Circle/Circle Kollisionsprüfung - Geht's auch schneller?

Mo, März 20, 2006 17:29
Antworten mit Zitat

Hi

Ich arbeite derzeit an einem kleinen Kollisionssystem, das zwei "ColShapes" - so heisst der Type - auf Kollision prüft und Kollisionspunkte sowie resultierenden Vektor (Den Vektor, mit dem eines der ColShapes verschoben werden müsste, damit es keine Überlappung der ColShapes mehr gibt) zurückliefert.
Ein ColShape hat eine beliebige Anzahl an Kreisen, d.h. Punkten mit Radien sowie eine derzeitige Position. Bei einer Kollisionsprüfung wird jeder Kreis von ColShape A mit jedem Kreis von ColShape B auf Kollision, d.h. entsprechende Entfernung geprüft.
Das funktioniert auch alles so weit, allerdings bin ich mit der Geschwindigkeit noch nicht hundertprozentig zufrieden, aber ich hab keine Ahnung, wie ich das hier noch schneller bekommen soll (Ja, ich rufe das auch nur auf, wenn unbedingt notwendig). Falls jemand eine Idee hat, bitte posten. Ansonsten können Mathe-Phobiker das hier gerne als Denkanstoß verwenden, mit Ausnahme der Kollisionspunkte, die sind bisher ungetestet ^^

Code: [AUSKLAPPEN]

'cspParShape -> ColShape, mit dem Self geprüft werden soll
'fVarColX[] -> KollisionsPunkt X
'fVarColY[] -> KollisionsPunkt Y
'fVarResXVec -> Resultierender Vektor, X-Richtung.
'fVarResYVec -> Resultierender Vektor, Y-Richtung.
Method CollidedWith2:Byte(cspParShape:ColShape, fVarColX:Float[] Var, fVarColY:Float[] Var, fVarResXVec:Float Var, fVarResYVec:Float Var)
Local iLoop:Int
Local iLoop2:Int
Local iMaxDistTemp:Int 'Summe zweier zu prüfender Radien
Local fDistTemp:Float 'Distanz zweier Kreise, manchmal im Quadrat
Local bCollision:Byte 'Hat eine Kollision stattgefunden?
Local fXDif:Float 'X-Differenz zweier Kreise
Local fYDif:Float 'Y-Differenz zweier Kreise

'Rückgabewerte nullen.
fVarResXVec = 0.0
fVarResYVec = 0.0
fVarColX = New Float[0]
fVarColY = New Float[0]

For iLoop = 0 To iCircleNum - 1
   For iLoop2 = 0 To cspParShape.iCircleNum - 1
      iMaxDistTemp = (iCircleRadius[iLoop] + cspParShape.iCircleRadius[iLoop2])
      fXDif = ((cspParShape.fX + cspParShape.fCircleX[iLoop2]) - (fX + fCircleX[iLoop]))
      fYDif = ((cspParShape.fY + cspParShape.fCircleY[iLoop2]) - (fY + fCircleY[iLoop]))
      If Abs(fXDif) < iMaxDistTemp And Abs(fYDif) < iMaxDistTemp Then
         fDistTemp = (fXDif * fXDif) + (fYDif * fYDif)
         If fDistTemp < (iMaxDistTemp * iMaxDistTemp) Then
            fDistTemp = Sqr(fDistTemp)

            fVarResXVec:+ (fXDif / fDistTemp) * -(iMaxDistTemp - fDistTemp)
            fVarResYVec:+ (fYDif / fDistTemp) * -(iMaxDistTemp - fDistTemp)

            fVarColX = fVarColX[..fVarColX.length + 1]
            fVarColY = fVarColY[..fVarColY.length + 1]
            fVarColX[fVarColX.length - 1] = (fXDif / fDistTemp) * (Float(iCircleRadius[iLoop]) - ((iMaxDistTemp - fDistTemp) / 2.0))
            fVarColY[fVarColY.length - 1] = (fYDif / fDistTemp) * (Float(iCircleRadius[iLoop]) - ((iMaxDistTemp - fDistTemp) / 2.0))

            bCollision = True
         End If
      End If
   Next
Next

Return bCollision
End Method

	klepto2	Mo, März 20, 2006 17:47 Antworten mit Zitat
Also das wäre das einfachste was mir einfällt (momentan) Code: [AUSKLAPPEN] [EINKLAPPEN] 'cspParShape -> ColShape, mit dem Self geprüft werden soll 'fVarColX[] -> KollisionsPunkt X 'fVarColY[] -> KollisionsPunkt Y 'fVarResXVec -> Resultierender Vektor, X-Richtung. 'fVarResYVec -> Resultierender Vektor, Y-Richtung. Method CollidedWith2:Byte(cspParShape:ColShape, fVarColX:Float[] Var, fVarColY:Float[] Var, fVarResXVec:Float Var, fVarResYVec:Float Var) Local iLoop:Int Local iLoop2:Int Local iMaxDistTemp:Int 'Summe zweier zu prüfender Radien Local fDistTemp:Float 'Distanz zweier Kreise, manchmal im Quadrat Local bCollision:Byte 'Hat eine Kollision stattgefunden? Local fXDif:Float 'X-Differenz zweier Kreise Local fYDif:Float 'Y-Differenz zweier Kreise 'Rückgabewerte nullen. fVarResXVec = 0.0 fVarResYVec = 0.0 fVarColX = New Float[0] fVarColY = New Float[0] For iLoop = 0 To iCircleNum - 1 For iLoop2 = 0 To cspParShape.iCircleNum - 1 iMaxDistTemp = (iCircleRadius[iLoop] + cspParShape.iCircleRadius[iLoop2]) fXDif = ((cspParShape.fX + cspParShape.fCircleX[iLoop2]) - (fX + fCircleX[iLoop])) fYDif = ((cspParShape.fY + cspParShape.fCircleY[iLoop2]) - (fY + fCircleY[iLoop])) If Abs(fXDif) < iMaxDistTemp And Abs(fYDif) < iMaxDistTemp Then fDistTemp = (fXDif * fXDif) + (fYDif * fYDif) If fDistTemp < (iMaxDistTemp * iMaxDistTemp) Then fDistTemp = Sqr(fDistTemp) fVarResXVec:+ (fXDif / fDistTemp) * -(iMaxDistTemp - fDistTemp) fVarResYVec:+ (fYDif / fDistTemp) * -(iMaxDistTemp - fDistTemp) fVarColX = fVarColX[..fVarColX.length + 1] fVarColY = fVarColY[..fVarColY.length + 1] fVarColX[fVarColX.length - 1] = (fXDif / fDistTemp) * (Float(iCircleRadius[iLoop]) - ((iMaxDistTemp - fDistTemp) / 2.0)) fVarColY[fVarColY.length - 1] = (fYDif / fDistTemp) * (Float(iCircleRadius[iLoop]) - ((iMaxDistTemp - fDistTemp) / 2.0)) bCollision = True Return bCollision End If End If Next Next Return bCollision End Method Ich hab an der Stelle, wo du bCollision auf True setzt ein Return BCollision gesetzt. Denn solbald die Kollision registriert wurde, brauchst du ja nicht mehr weiterprüfen. Sprich die restlichen Segmente können ausgelassen werden.
Matrix Screensaver Console Modul für BlitzMax KLPacker Modul für BlitzMax HomePage : http://www.brsoftware.de.vu

klepto2

Mo, März 20, 2006 17:47
Antworten mit Zitat

Also das wäre das einfachste was mir einfällt (momentan)
Code: [AUSKLAPPEN]

'cspParShape -> ColShape, mit dem Self geprüft werden soll
'fVarColX[] -> KollisionsPunkt X
'fVarColY[] -> KollisionsPunkt Y
'fVarResXVec -> Resultierender Vektor, X-Richtung.
'fVarResYVec -> Resultierender Vektor, Y-Richtung.
Method CollidedWith2:Byte(cspParShape:ColShape, fVarColX:Float[] Var, fVarColY:Float[] Var, fVarResXVec:Float Var, fVarResYVec:Float Var)
Local iLoop:Int
Local iLoop2:Int
Local iMaxDistTemp:Int 'Summe zweier zu prüfender Radien
Local fDistTemp:Float 'Distanz zweier Kreise, manchmal im Quadrat
Local bCollision:Byte 'Hat eine Kollision stattgefunden?
Local fXDif:Float 'X-Differenz zweier Kreise
Local fYDif:Float 'Y-Differenz zweier Kreise

'Rückgabewerte nullen.
fVarResXVec = 0.0
fVarResYVec = 0.0
fVarColX = New Float[0]
fVarColY = New Float[0]

For iLoop = 0 To iCircleNum - 1
For iLoop2 = 0 To cspParShape.iCircleNum - 1
iMaxDistTemp = (iCircleRadius[iLoop] + cspParShape.iCircleRadius[iLoop2])
fXDif = ((cspParShape.fX + cspParShape.fCircleX[iLoop2]) - (fX + fCircleX[iLoop]))
fYDif = ((cspParShape.fY + cspParShape.fCircleY[iLoop2]) - (fY + fCircleY[iLoop]))
If Abs(fXDif) < iMaxDistTemp And Abs(fYDif) < iMaxDistTemp Then
fDistTemp = (fXDif * fXDif) + (fYDif * fYDif)
If fDistTemp < (iMaxDistTemp * iMaxDistTemp) Then
fDistTemp = Sqr(fDistTemp)

fVarResXVec:+ (fXDif / fDistTemp) * -(iMaxDistTemp - fDistTemp)
fVarResYVec:+ (fYDif / fDistTemp) * -(iMaxDistTemp - fDistTemp)

fVarColX = fVarColX[..fVarColX.length + 1]
fVarColY = fVarColY[..fVarColY.length + 1]
fVarColX[fVarColX.length - 1] = (fXDif / fDistTemp) * (Float(iCircleRadius[iLoop]) - ((iMaxDistTemp - fDistTemp) / 2.0))
fVarColY[fVarColY.length - 1] = (fYDif / fDistTemp) * (Float(iCircleRadius[iLoop]) - ((iMaxDistTemp - fDistTemp) / 2.0))

bCollision = True
Return bCollision
End If
End If
Next
Next

Return bCollision
End Method

Ich hab an der Stelle, wo du bCollision auf True setzt ein Return BCollision gesetzt. Denn solbald die Kollision registriert wurde, brauchst du ja nicht mehr weiterprüfen. Sprich die restlichen Segmente können ausgelassen werden.

Matrix Screensaver
Console Modul für BlitzMax
KLPacker Modul für BlitzMax

HomePage : http://www.brsoftware.de.vu

	Fetze	Mo, März 20, 2006 17:50 Antworten mit Zitat
Doch, muss ich in dem Fall schon. Da ich ja nicht nur prüfe, ob eine Kollision stattgefunden hat, sondern auch einen resultierenden Vektor zurück haben will, muss ich tatsächlich alle Kreise prüfen, denn sonst vernachlässige ich alle Überlappungen mit eventuell noch folgenden Kreisen.

Fetze

Mo, März 20, 2006 17:50
Antworten mit Zitat

Doch, muss ich in dem Fall schon. Da ich ja nicht nur prüfe, ob eine Kollision stattgefunden hat, sondern auch einen resultierenden Vektor zurück haben will, muss ich tatsächlich alle Kreise prüfen, denn sonst vernachlässige ich alle Überlappungen mit eventuell noch folgenden Kreisen.

	klepto2	Mo, März 20, 2006 17:55 Antworten mit Zitat
Stimmt, hab ich eben auch gemerkt, als ich mir das nochmal genauer angeguckt habe. Sorry.
Matrix Screensaver Console Modul für BlitzMax KLPacker Modul für BlitzMax HomePage : http://www.brsoftware.de.vu