Kollisionen (in 2D)

**Mars**

Moin,

Überall tauchen immer mal wieder die Probleme auf: Ich möchte wissen, ob mein Mauszeiger in folgendem Viereck/Dreieck/Kreis/ usw. ist.
Wie stelle ich das an ?

Meistens werden große Gebilde mit Lokalen Variablen und mehreren If Abfragen angeboten, die das Problem meistens lösen, allerdings weder elegant noch schnell.

Deshalb habe ich mir überlegt eine Sammlung anzufertigen, die ausschließlich Kollisionskontrollen enthält an denen (erstmal nur) ein Punkt beteiligt ist.
(d.H. Kollisionen 2er Kreise/Vierecke, Kreis/Viereck usw sind nicht dabei, folgen aber irgendwann...)

Ist nix großes jetzt, aber ich denke es kann helfen, wenn man eigene Buttons erstellt, oder kleine Spiele schreibt in denen etwas zusammenstößt (z.B Schüsse auf Gegner).
Vllt gibts auch Sachen die ich übersehen habe, und die Praktische Anwendungen haben...

Beispiel

[autoit]

[/autoit] [autoit][/autoit] [autoit]

#include <GDIPlus.au3>

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Opt('GUIOnEventMode', 1)
Opt('MouseCoordMode', 2)

[/autoit] [autoit][/autoit] [autoit]

Global Const $iB = 640, $iH = 480

[/autoit] [autoit][/autoit] [autoit]

Global $hGUI, $hGFX, $hBuf, $hBmp, $aPos[2], $hBru, $hBr2, $hPen, $hPe2

[/autoit] [autoit][/autoit] [autoit]

_Main()

[/autoit] [autoit][/autoit] [autoit]

Func _Main()

[/autoit] [autoit][/autoit] [autoit]

Local $Rect[4] = [Int($iB / 8), Int($iH / 8), Int($iB / 4), Int($iH / 16)]
Local $Circ[3] = [Int($iB / 2), Int($iH / 2), Int(($iB ^ 2 + $iH ^ 2) ^ 0.5 / 4)]
Local $Elli[4] = [Int($iB * 0.75), Int($iH * 0.75), Int($iB / 3), Int($iH / 5)]
Local $Tria[6] = [Int($iB * 0.3), Int($iH * 0.7), Int($iB / 9), Int($iH / 2), Int($iB / 4), Int($iH * 0.9)]
Local $Line[4] = [Int($iB*0.75),Int($iH*0.2),Int($iB*0.85),Int($iH*0.5)]

[/autoit] [autoit][/autoit] [autoit]

Local $nWidth = Int(($iB ^ 2 + $iH ^ 2) ^ 0.5 / 16)

[/autoit] [autoit][/autoit] [autoit]

Local $aPoints[4][2]
$aPoints[0][0] = 3
For $i = 0 To 2 Step 1
$aPoints[$i + 1][0] = $Tria[$i * 2]
$aPoints[$i + 1][1] = $Tria[$i * 2 + 1]
Next

[/autoit] [autoit][/autoit] [autoit]

$hGUI = GUICreate('Kollisionen', $iB, $iH)
GUISetBkColor(0x000000, $hGUI)

[/autoit] [autoit][/autoit] [autoit]

_GDIPlus_Startup()
$hGFX = _GDIPlus_GraphicsCreateFromHWND($hGUI)
$hBmp = _GDIPlus_BitmapCreateFromGraphics($iB, $iH, $hGFX)
$hBuf = _GDIPlus_ImageGetGraphicsContext($hBmp)
$hBru = _GDIPlus_BrushCreateSolid(0xFFA0A0A0)
$hBr2 = _GDIPlus_BrushCreateSolid(0xFFFFFFFF)
$hPen = _GDIPlus_PenCreate(0xFFA0A0A0, $nWidth)
$hPe2 = _GDIPlus_PenCreate(0xFFFFFFFF, $nWidth)

[/autoit] [autoit][/autoit] [autoit]

_GDIPlus_GraphicsSetSmoothingMode($hBuf, 4)

[/autoit] [autoit][/autoit] [autoit]

GUISetOnEvent(-3, '_Exit', $hGUI)
GUIRegisterMsg(0xF, 'WM_PAINT')
OnAutoItExitRegister('_Ende')
GUISetState(@SW_SHOW, $hGUI)

[/autoit] [autoit][/autoit] [autoit]

While Sleep(10)
_GDIPlus_GraphicsClear($hBuf)

[/autoit] [autoit][/autoit] [autoit]

$aPos = MouseGetPos()

[/autoit] [autoit][/autoit] [autoit]

If _Kollision_Rechteck_Punkt($Rect[0], $Rect[1], $Rect[2], $Rect[3], $aPos[0], $aPos[1]) Then
_GDIPlus_GraphicsFillRect($hBuf, $Rect[0], $Rect[1], $Rect[2], $Rect[3], $hBr2)
Else
_GDIPlus_GraphicsFillRect($hBuf, $Rect[0], $Rect[1], $Rect[2], $Rect[3], $hBru)
EndIf

[/autoit] [autoit][/autoit] [autoit]

If _Kollision_Kreis_Punkt($Circ[0], $Circ[1], $Circ[2], $aPos[0], $aPos[1]) Then
_GDIPlus_GraphicsFillEllipse($hBuf, $Circ[0] - $Circ[2] / 2, $Circ[1] - $Circ[2] / 2, $Circ[2], $Circ[2], $hBr2)
Else
_GDIPlus_GraphicsFillEllipse($hBuf, $Circ[0] - $Circ[2] / 2, $Circ[1] - $Circ[2] / 2, $Circ[2], $Circ[2], $hBru)
EndIf

[/autoit] [autoit][/autoit] [autoit]

If _Kollision_Ellipse_Punkt($Elli[0], $Elli[1], $Elli[2], $Elli[3], $aPos[0], $aPos[1]) Then
_GDIPlus_GraphicsFillEllipse($hBuf, $Elli[0] - $Elli[2] / 2, $Elli[1] - $Elli[3] / 2, $Elli[2], $Elli[3], $hBr2)
Else
_GDIPlus_GraphicsFillEllipse($hBuf, $Elli[0] - $Elli[2] / 2, $Elli[1] - $Elli[3] / 2, $Elli[2], $Elli[3], $hBru)
EndIf

[/autoit] [autoit][/autoit] [autoit]

If _Kollision_Dreieck_Punkt($Tria[0], $Tria[1], $Tria[2], $Tria[3], $Tria[4], $Tria[5], $aPos[0], $aPos[1]) Then
_GDIPlus_GraphicsFillPolygon($hBuf, $aPoints, $hBr2)
Else
_GDIPlus_GraphicsFillPolygon($hBuf, $aPoints, $hBru)
EndIf

[/autoit] [autoit][/autoit] [autoit]

If _Kollision_Strecke_Punkt($Line[0], $Line[1], $Line[2], $Line[3], $aPos[0], $aPos[1], $nWidth) Then
_GDIPlus_GraphicsDrawLine($hBuf, $Line[0], $Line[1], $Line[2], $Line[3], $hPe2)
Else
_GDIPlus_GraphicsDrawLine($hBuf, $Line[0], $Line[1], $Line[2], $Line[3], $hPen)
EndIf

[/autoit] [autoit][/autoit] [autoit]

WM_PAINT()

[/autoit] [autoit][/autoit] [autoit]

WEnd

[/autoit] [autoit][/autoit] [autoit]

EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _Kollision_Dreieck_Punkt($x1, $y1, $x2, $y2, $x3, $y3, $px, $py)
Return ((($x1 - $px) * ($x2 - $px) + ($y1 - $py) * ($y2 - $py)) / ((($x1 - $px) ^ 2 + ($y1 - $py) ^ 2) ^ 0.5 * (($x2 - $px) ^ 2 + ($y2 - $py) ^ 2) ^ 0.5) + (($x2 - $px) * ($x3 - $px) + ($y2 - $py) * ($y3 - $py)) / ((($x2 - $px) ^ 2 + ($y2 - $py) ^ 2) ^ 0.5 * (($x3 - $px) ^ 2 + ($y3 - $py) ^ 2) ^ 0.5) + (($x3 - $px) * ($x1 - $px) + ($y3 - $py) * ($y1 - $py)) / ((($x3 - $px) ^ 2 + ($y3 - $py) ^ 2) ^ 0.5 * (($x1 - $px) ^ 2 + ($y1 - $py) ^ 2) ^ 0.5)) <= -1
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _Kollision_Ellipse_Punkt($x, $y, $b, $h, $px, $py)
Return ((($px - $x) * 2 / $b) ^ 2 + (($py - $y) * 2 / $h) ^ 2) <= 1
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _Kollision_Kreis_Punkt($x, $y, $d, $px, $py)
Return (($x - $px) ^ 2 + ($y - $py) ^ 2) ^ 0.5 <= ($d / 2)
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _Kollision_Rechteck_Punkt($x, $y, $b, $h, $px, $py)
Return ($px > $x And $py > $y And $px < $x + $b And $py < $y + $h)
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _Kollision_Strecke_Punkt($x1, $y1, $x2, $y2, $px, $py, $nAbs = 1)
Local $x = (($y2 - $y1) / (($x2 - $x1)^2 + ($y2 - $y1)^2)^0.5) * $nAbs / 2, $y = (($x2 - $x1) / (($x2 - $x1)^2 + ($y2 - $y1)^2)^0.5) * $nAbs / 2
Return _Kollision_Dreieck_Punkt($x1 - $x, $y1 + $y, $x1 + $x, $y1 - $y, $x2 + $x, $y2 - $y, $px, $py) Or _Kollision_Dreieck_Punkt($x1 - $x, $y1 + $y, $x2 - $x, $y2 + $y, $x2 + $x, $y2 - $y, $px, $py)
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _Round($n, $a)
Return Round($n*10^$a,0)/10^$a
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func WM_PAINT()
_GDIPlus_GraphicsDrawImage($hGFX, $hBmp, 0, 0)
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _Exit()
Exit
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _Ende()

[/autoit] [autoit][/autoit] [autoit]

_GDIPlus_PenDispose($hPe2)
_GDIPlus_PenDispose($hPen)
_GDIPlus_BrushDispose($hBr2)
_GDIPlus_BrushDispose($hBru)
_GDIPlus_GraphicsDispose($hBuf)
_GDIPlus_BitmapDispose($hBmp)
_GDIPlus_GraphicsDispose($hGFX)
_GDIPlus_Shutdown()

[/autoit] [autoit][/autoit] [autoit]

EndFunc

[/autoit]

Bisher vorhanden:

_Kollision_Rechteck_Punkt - Kollision mit einem Rechteck. (x und y beschreiben die obere Linke Ecke, b und h sind Breite und Höhe)
_Kollision_Kreis_Punkt - Kollision mit einem Kreis. (x und y beschreiben den Kreismittelpunkt, d den Durchmesser)
_Kollision_Ellipse_Punkt - Kollision mit einer Ellipse. (x und y beschreiben den Ellipsemittelpunkt, b und h die Breite und Höhe)
_Kollision_Dreieck_Punkt - Kollision mit einem beliebigen Dreieck (xn und yn beschreiben die Koordinaten der Eckpunkte)
_Kollision_Strecke_Punkt - Kollision mit einer beliebigen Strecke (xn und yn beschreiben die Koordinaten der Punkte)

Edit: 05.11.2012
Überarbeitung der Strecke Punkt Kollision.
Vorher: Mathematisch korrekte Lösung, die aber nicht alltagstauglich ist. Die Linie wurde als unendlich dünn angenommen und konnte nur durch "Zufall" getroffen werden.
Nachher: Die Linie wird als Fläche statt als Linie interpretiert. Diese Fläche wird in 2 Dreiecke unterteilt und per _Kollision_Dreieck_Punkt analysiert. Diese Methode ist relativ rechenintensiv. Linien erhalten hiermit einen Parameter um die Breite der Linie anzugeben.

lg
M

chrisatack

hiho

Hier ich habe für ein Projekt auch mal eine Kollisionsüberwachung benötigt
Ist zwar für Rechtecke, die du auch schon hast aber vielliecht kann man es
auch benötigen...

_sharing2D_RectCollision()
https://autoit.de/index.php?page…5031#post175031

MFG chris

**Xorianator**

Coole Sache, das hast du ja oft gepostet.
Ich versteh aber immernoch nicht was das "Return (a < b And c < d)" (also so halt nach dem Motto) macht ..

Wäre nett wenn du das mal erklärst, danke

stayawayknight

Zitat von Xorianator

Ich versteh aber immernoch nicht was das "Return (a < b And c < d)" (also so halt nach dem Motto) macht ..

Ist im Prinzip wie eine if-Abfrage, nur in verkürzter Version - der Inhalt der Klammer liefert einen Wahrheitswert zurück, der dann zurückgegeben wird.
Ist soweit ich weiß von C(++) abgeleitet...

Gruß stay

**Mars**

Hab dazu mal kurz ein Beispiel gemacht mit 2 Zufallszahlen, die vergleichen werden sollen.

Spoiler anzeigen

[autoit]

_Main()

[/autoit] [autoit][/autoit] [autoit]

Func _Main()

[/autoit] [autoit][/autoit] [autoit]

Local $r, $s

[/autoit] [autoit][/autoit] [autoit]

For $i = 0 To 9 Step 1
$r = Random(0, 3, 1)
$s = Random(0, 3, 1)
ConsoleWrite('Test: ' & $r & ' = ' & $s & ' ?' & @CRLF & 'a: ' & _a($s, $r) & @CRLF & 'b: ' & _b($s, $r) & @CRLF & @CRLF)
Next

[/autoit] [autoit][/autoit] [autoit]

EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _a($a, $b)
If $a = $b Then Return True
Return False
EndFunc

[/autoit] [autoit][/autoit] [autoit]

Func _b($a, $b)
Return $a = $b
EndFunc

[/autoit]

Klappt natürlich mit den anderen Operatoren auch. ( And, Or, <, >, =, <> )

lg
M

name22

Gute Sache. Alternativ geht das auch so:

Spoiler anzeigen

[autoit]

#include <GDIP.au3>
#include <GUIConstants.au3>
#include <Misc.au3>

[/autoit] [autoit][/autoit] [autoit]

Opt("GUIOnEventMode", 1)

[/autoit] [autoit][/autoit] [autoit]

$iGUIColorBG = 0xFFFFFFFF
$iGUIWidth = 400
$iGUIHeight = 400

[/autoit] [autoit][/autoit] [autoit]

$hWnd = GUICreate("Test", $iGUIWidth, $iGUIHeight)
GUISetState()

[/autoit] [autoit][/autoit] [autoit]

_GDIPlus_Startup()

[/autoit] [autoit][/autoit] [autoit]

$hGraphic = _GDIPlus_GraphicsCreateFromHWND($hWnd)
$hBitmap = _GDIPlus_BitmapCreateFromGraphics($iGUIWidth, $iGUIHeight, $hGraphic)
$hBuffer = _GDIPlus_ImageGetGraphicsContext($hBitmap)
_GDIPlus_GraphicsSetSmoothingMode($hBuffer, 2)

[/autoit] [autoit][/autoit] [autoit]

$hPenRed = _GDIPlus_PenCreate(0xFFFF0000)
$hPenGreen = _GDIPlus_PenCreate(0xFF00FF00)

[/autoit] [autoit][/autoit] [autoit]

$hPath = _GDIPlus_PathCreate()
_GDIPlus_PathAddLine($hPath, 50, 50, 100, 50)
_GDIPlus_PathAddLine($hPath, 100, 50, 75, 100)
_GDIPlus_PathAddLine($hPath, 75, 100, 50, 50)

[/autoit] [autoit][/autoit] [autoit]

_GDIPlus_GraphicsDrawPath($hGraphic, $hPath)

[/autoit] [autoit][/autoit] [autoit]

$hRegion = _GDIPlus_RegionCreateFromPath($hPath)

[/autoit] [autoit][/autoit] [autoit]

GUISetOnEvent($GUI_EVENT_CLOSE, "_Exit")

[/autoit] [autoit][/autoit] [autoit]

While Sleep(20)
_GDIPlus_GraphicsClear($hBuffer, $iGUIColorBG)

[/autoit] [autoit][/autoit] [autoit]

$aMousePos = GUIGetCursorInfo()
Switch _GDIPlus_RegionIsVisiblePoint($hRegion, $aMousePos[0], $aMousePos[1], $hBuffer)
Case True
_GDIPlus_GraphicsDrawPath($hBuffer, $hPath, $hPenGreen)
Case False
_GDIPlus_GraphicsDrawPath($hBuffer, $hPath, $hPenRed)
EndSwitch

[/autoit] [autoit][/autoit] [autoit]

_GDIPlus_GraphicsDrawImageRect($hGraphic, $hBitmap, 0, 0, $iGUIWidth, $iGUIHeight)
WEnd

[/autoit] [autoit][/autoit] [autoit]

Func _Exit()
_GDIPlus_GraphicsDispose($hGraphic)
_GDIPlus_GraphicsDispose($hBuffer)
_GDIPlus_BitmapDispose($hBitmap)
_GDIPlus_RegionDispose($hRegion)
_GDIPlus_PathDispose($hPath)
_GDIPlus_PenDispose($hPenGreen)
_GDIPlus_PenDispose($hPenRed)
_GDIPlus_Shutdown()
Exit
EndFunc

[/autoit]

Aber dein Script ist da flexibler und von der Rechnung her effizienter.

BinDannMalWeg

Ich dachte ich steuere auch einfach mal eine Funktion bei... _Kollision_Strecke_Punkt()
Hier einmal in kurz:

[autoit]

Func _Kollision_Strecke_Punkt($Px, $Py, $Ax, $Ay, $Bx, $By)
Return (Sqrt(($Ax - $Bx) ^ 2 + ($Ay - $By) ^ 2) = (Sqrt(($Ax - $Px) ^ 2 + ($Ay - $Py) ^ 2) + Sqrt(($Bx - $Px) ^ 2 + ($By - $Py) ^ 2)))
EndFunc

[/autoit]

und hier nochmal in lang:

Spoiler anzeigen

[autoit]

Func _Kollision_Strecke_Punkt__Lang($Px, $Py, $Ax, $Ay, $Bx, $By)
;wenn
; strecke zwischen a und p
;plus
; strecke zwischen b und p
;gleich
; strecke zwischen a und b
;dann
; return 1
$Strecke_AP = _Distance($Ax, $Ay, $Px, $Py) ; --> Sqrt(($Ax-$Px)^2+($Ay-$Py)^2)
$Strecke_BP = _Distance($Bx, $By, $Px, $Py) ; --> Sqrt(($Bx-$Px)^2+($By-$Py)^2)
$Strecke_AB = _Distance($Ax, $Ay, $Bx, $By) ; --> Sqrt(($Ax-$Bx)^2+($Ay-$By)^2)
If $Strecke_AB = ($Strecke_AP + $Strecke_BP) Then
Return True
Else
Return False
EndIf
EndFunc ;==>_Kollision_Strecke_Punkt__Lang

[/autoit] [autoit][/autoit] [autoit]

Func _Distance($_Ax, $_Ay, $_Bx, $_By)
Return Sqrt(($_Ax - $_Bx) ^ 2 + ($_Ay - $_By) ^ 2)
EndFunc ;==>_Distance

[/autoit]

**Mars**

Moin,

Habe mir die Funktion angeschaut.
Mathematisch ist sie auch korrekt, aber in AutoIt wird die Anwendung relativ schwierig, da die Linie "unendlich" dünn ist.
Sie ist wesentlich schmaler als ein Pixel. Es muss also ein glücklicher Zufall eintreten, dass man mit der Maus einen Pixel erwischt, der Rechnerisch exakt auf der Linie liegt.

Das ist bei meinem Test nur der Fall, sofern entweder eine 45 Grad Neigung genutzt wird (dann ist jeder Pixel ein Treffer), oder wenn man Vertikale und Horizontale Linien nimmt. (Natürlich nur mit Integer Koordinaten).

Um diese Funktion für die Interaktion mit dem Nutzer verfügbar zu machen muss man die Ergebnisse beider Rechnungen vor dem Vergleich runden.
Je mehr man rundet, desto ungenauer wird die Abfrage und desto "breiter" die Linie.

Da besteht sicherlich ein berechenbarer Zusammenhang zwischen dem Runden und der Linienstärke.
Zudem funktioniert die Round() Funktion von AutoIt nicht für diesen Zweck, da sie nur auf ganze Nachkommastellen runden kann. Für eine Stufenlose Berechnung der Linienbreite bedarf es aber Rundungen auf allgemeine Werte wie z.B. 1.525.

Ich habe die Funktion mal angepasst (damit das mit x1, x2 usw konform ist) und aufgenommen.

Edit:
Habe grade herausgefunden, dass sich durch runden eine Ellipse ergibt. Damit fällt runden weg und eine "einfache" (d.h. schnell berechenbare) Anpassung der Funktion, sodass die Linienstärke mit berücksichtigt wird fällt mir nicht ein. Vermutlich muss ein anderer mathematischer Ansatz her...

name22

Am besten ist es bei Kollisionschecks in Systemen begrenzter Präzision nicht nur den Ort eines Objekts sondern auch seinen Geschwindigkeitsvektor mit einzubeziehen.
Ich mache es lieber so, dass ich überprüfe ob die Strecke die sich aus Orts- und Bewegungsvektor des Objekts zusammensetzt die Strecke des Hindernisses schneidet (Bevor die Frame in der die Kollision sich abspielen würde generiert wird).
Beim Mauszeiger könnte man stattdessen den Vektor nehmen der von seiner vorherigen und seiner aktuellen Position beschrieben wird. Allerdings ist das auch eine potenztielle Fehlerquelle wenn man den Mauszeiger zu schnell über die Linie und wieder zurück bewegt.

**Mars**

Die hier benutzten Funktionen sollen eine eindeutige Lösung für ein Problem geben.
Wenn der Mauszeiger an Pos xy ist, ist er dann im Rechteck/Kreis/...
Dabei darf nicht berücksichtigt werden wie der Mauszeiger da hin kam, oder wo er als nächstes hingeht.
Sonst ist nicht mehr in jeder Situation eine eindeutige Lösung möglich, und die Berechnungen werden keine extrem schnellen Einzeiler mehr sein.

Das Problem bei der Linie ist, dass sie nicht 2 Dimensional ist.
Sie besitzt keine Fläche in der sich der Mauszeiger aufhalten kann.

Man kann aus der Linie jetzt künstlich ein Gedrehtes Rechteck machen über die Linienstärke.
Dann ist auch eine Aussage möglich wo sich der Zeiger befindet.
(dafür denke ich mir noch eine Funktion aus. eventuell !!)