LineIntersect -> Kollision zweier Strecken(nicht Geraden)

Übersicht

BlitzBasic

Codearchiv

	TimBo Betreff: LineIntersect -> Kollision zweier Strecken(nicht Geraden)	Mi, Dez 03, 2008 18:08 Antworten mit Zitat
Hi, hier mein zweiter Codearchiv-Eintrag. Wenn man wissen möchte, ob sich zwei Linien schnieden, kann man diese Funktion benutzen. BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Function Line_intersect(x1#,y1#,x2#,y2#, x3#,y3#,x4#,y4#) ;Steigung ausrechnen m1# = (y1#-y2#)/(x1#-x2#) m2# = (y3#-y4#)/(x3#-x4#) ;Y-Achsen Abschnitt ausrechnen b1# = y1# - m1#x1# b2# = y3# - m2#x3# ;Term umformen x# = (b2# - b1#) / (m1# - m2#) y# = x# * m1# + b1# ;schauen, ob der Punkt auf einer Linie liegt abstand# = Abs (x1#-x2#) If Abs (x#-x1#) <= abstand # Then If Abs (x#-x2#) <= abstand # Then abstand# = Abs (y1#-y2#) If Abs (y#-y1#) <= abstand # Then If Abs (y#-y2#) <= abstand # Then abstand# = Abs (x3#-x4#) If Abs (x#-x3#) <= abstand # Then If Abs (x#-x4#) <= abstand # Then abstand# = Abs (y3#-y4#) If Abs (y#-y3#) <= abstand # Then If Abs (y#-y4#) <= abstand # Then Return 1 EndIf EndIf EndIf EndIf EndIf EndIf EndIf EndIf End Function wenn man möchte, dass auch Senkrechte Strecken funktionsfähig sind, muss man diese beiden Zeilen am Anfang der Funktion einfügen. Dadurch wird das Programm allerdings langsamer (unmessbar). BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] If x1#-x2# =0 Then x1#=x1#-.0001 If x3#-x4# =0 Then x3#=x3#-.0001 Sie basiert auf der linearen Funktion F(x) = y = mx + b . Beispielprogramm: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Graphics 1024,768,24,2 SetBuffer BackBuffer() timer=CreateTimer(60) Repeat mx = MouseX() my = MouseY() ;Beispielkordinaten x1 = 100 y1 = 100 x2 = 250 y2 = 400 x3 = mx+200 y3 = my+250 x4 = mx-150 y4 = my-50 ;Zeichne die Beispiellinien Line x1,y1,x2,y2 Line x3,y3,x4,y4 ;Führe die Funktion aus Locate 0,0 Print Line_intersect(x1,y1,x2,y2, x3,y3,x4,y4) WaitTimer(timer) Flip(0):Cls Until KeyHit(1) Function Line_intersect(x1#,y1#,x2#,y2#, x3#,y3#,x4#,y4#) ;Steigung ausrechnen m1# = (y1#-y2#)/(x1#-x2#) m2# = (y3#-y4#)/(x3#-x4#) ;Y-Achsen Abschnitt ausrechnen b1# = y1# - m1#x1# b2# = y3# - m2#x3# ;Term umformen x# = (b2# - b1#) / (m1# - m2#) y# = x# * m1# + b1# ;schauen, ob der Punkt auf einer Linie liegt abstand# = Abs (x1#-x2#) If Abs (x#-x1#) <= abstand # Then If Abs (x#-x2#) <= abstand # Then abstand# = Abs (y1#-y2#) If Abs (y#-y1#) <= abstand # Then If Abs (y#-y2#) <= abstand # Then abstand# = Abs (x3#-x4#) If Abs (x#-x3#) <= abstand # Then If Abs (x#-x4#) <= abstand # Then abstand# = Abs (y3#-y4#) If Abs (y#-y3#) <= abstand # Then If Abs (y#-y4#) <= abstand # Then Return 1 EndIf EndIf EndIf EndIf EndIf EndIf EndIf EndIf End Function Vorteil: diese Funktion ist (glaube ich) verdammt schnell. Sie "verbraucht" bei 10.000.000 Aufrufen gerade mal 1496 millisekunden. Umgerechnet sind das dann 0,0001496ms pro Aufruf ! Ich brauche sie für ein Jump n Run game, damit ich Kollisionen mit Tiles besser verwalten kann. Viele Grüße TimBo

TimBo

Betreff: LineIntersect -> Kollision zweier Strecken(nicht Geraden)

Mi, Dez 03, 2008 18:08
Antworten mit Zitat

Hi,

hier mein zweiter Codearchiv-Eintrag.

Wenn man wissen möchte, ob sich zwei Linien schnieden, kann man diese Funktion benutzen.

BlitzBasic: [AUSKLAPPEN]

Function Line_intersect(x1#,y1#,x2#,y2#, x3#,y3#,x4#,y4#)
	;Steigung ausrechnen
	m1# = (y1#-y2#)/(x1#-x2#)
	m2# = (y3#-y4#)/(x3#-x4#)
	
	;Y-Achsen Abschnitt ausrechnen
	b1# = y1# - m1#*x1#
	b2# = y3# - m2#*x3#
	
	
	;Term umformen
	x# = (b2# - b1#) / (m1# - m2#)
	y# = x# * m1# + b1#
	
	;schauen, ob der Punkt auf einer Linie liegt
	abstand# = Abs (x1#-x2#)
	If Abs (x#-x1#) <= abstand # Then
		If Abs (x#-x2#) <= abstand # Then
			
			abstand# = Abs (y1#-y2#)
			If Abs (y#-y1#) <= abstand # Then
				If Abs (y#-y2#) <= abstand # Then
			
					abstand# = Abs (x3#-x4#)
					If Abs (x#-x3#) <= abstand # Then
						If Abs (x#-x4#) <= abstand # Then
							
							abstand# = Abs (y3#-y4#)
							If Abs (y#-y3#) <= abstand # Then
								If Abs (y#-y4#) <= abstand # Then
									
									Return 1
									
									
								EndIf
							EndIf
						EndIf
					EndIf
				EndIf
			EndIf
		EndIf
	EndIf
End Function

wenn man möchte, dass auch Senkrechte Strecken funktionsfähig sind, muss man diese beiden Zeilen
am Anfang der Funktion einfügen. Dadurch wird das Programm allerdings langsamer (unmessbar).

BlitzBasic: [AUSKLAPPEN]

If x1#-x2# =0 Then x1#=x1#-.0001 
If x3#-x4# =0 Then x3#=x3#-.0001

Sie basiert auf der linearen Funktion F(x) = y = mx + b .

Beispielprogramm:
BlitzBasic: [AUSKLAPPEN]

Graphics 1024,768,24,2
SetBuffer BackBuffer()
timer=CreateTimer(60)


Repeat
	mx = MouseX()
	my = MouseY()
	
	;Beispielkordinaten
	x1 = 100
	y1 = 100
	x2 = 250
	y2 = 400
	
	x3 = mx+200
	y3 = my+250
	x4 = mx-150
	y4 = my-50
	
	;Zeichne die Beispiellinien
	Line x1,y1,x2,y2	
	Line x3,y3,x4,y4
	
	;Führe die Funktion aus
	Locate 0,0
	Print Line_intersect(x1,y1,x2,y2, x3,y3,x4,y4)
	
	WaitTimer(timer)
	Flip(0):Cls
	
Until KeyHit(1)

Function Line_intersect(x1#,y1#,x2#,y2#, x3#,y3#,x4#,y4#)
	;Steigung ausrechnen
	m1# = (y1#-y2#)/(x1#-x2#)
	m2# = (y3#-y4#)/(x3#-x4#)
	
	;Y-Achsen Abschnitt ausrechnen
	b1# = y1# - m1#*x1#
	b2# = y3# - m2#*x3#
	
	
	;Term umformen
	x# = (b2# - b1#) / (m1# - m2#)
	y# = x# * m1# + b1#
	
	;schauen, ob der Punkt auf einer Linie liegt
	abstand# = Abs (x1#-x2#)
	If Abs (x#-x1#) <= abstand # Then
		If Abs (x#-x2#) <= abstand # Then
			
			abstand# = Abs (y1#-y2#)
			If Abs (y#-y1#) <= abstand # Then
				If Abs (y#-y2#) <= abstand # Then
			
					abstand# = Abs (x3#-x4#)
					If Abs (x#-x3#) <= abstand # Then
						If Abs (x#-x4#) <= abstand # Then
							
							abstand# = Abs (y3#-y4#)
							If Abs (y#-y3#) <= abstand # Then
								If Abs (y#-y4#) <= abstand # Then
									
									Return 1
									
									
								EndIf
							EndIf
						EndIf
					EndIf
				EndIf
			EndIf
		EndIf
	EndIf
End Function

Vorteil: diese Funktion ist (glaube ich) verdammt schnell.
Sie "verbraucht" bei 10.000.000 Aufrufen gerade mal 1496 millisekunden.
Umgerechnet sind das dann 0,0001496ms pro Aufruf !

Ich brauche sie für ein Jump n Run game, damit ich Kollisionen mit Tiles besser verwalten kann.

Viele Grüße
TimBo

Zuletzt bearbeitet von TimBo am Do, Sep 16, 2010 14:07, insgesamt 5-mal bearbeitet

	ZaP	Mi, Dez 03, 2008 18:40 Antworten mit Zitat
Eine lineare Funktion ist eine Gerade...
Starfare: Worklog, Website (download)

ZaP

Mi, Dez 03, 2008 18:40
Antworten mit Zitat

Eine lineare Funktion ist eine Gerade...

Starfare: Worklog, Website (download)

	DjDETE	Mi, Dez 03, 2008 18:45 Antworten mit Zitat
jop, wäre i-wie komisch wenn sie auf einer exponentiellen Funktion beruhen würde
Aktuelles Projekt: XXX \|XXX \| 3% der v1b fertig www.emu-soft.de.vu Für die Homepage suche ich noch Linktauschpartner, bei Interesse einfach melden.

DjDETE

Mi, Dez 03, 2008 18:45
Antworten mit Zitat

jop, wäre i-wie komisch wenn sie auf einer exponentiellen Funktion beruhen würde Wink

Aktuelles Projekt: XXX |XXX | 3% der v1b fertig
www.emu-soft.de.vu Für die Homepage suche ich noch Linktauschpartner, bei Interesse einfach melden.

	Noobody	Mi, Dez 03, 2008 18:59 Antworten mit Zitat
Gerade für Jump'n'Runs solltest du aber noch einen Spezialfall betrachten Ist nämlich eine der beiden Linien senkrecht, funktioniert die Funktion nicht (eigentlich logisch, da die Steigung dann unendlich wird). Wenn ich in einem Jump'n'Run still stehe, geht mein Geschwindigkeitsvektor senkrecht nach unten und ich kann prompt mit keinem Tile mehr kollidieren. Solltest du also noch ausbessern.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

Noobody

Mi, Dez 03, 2008 18:59
Antworten mit Zitat

Gerade für Jump'n'Runs solltest du aber noch einen Spezialfall betrachten Wink

Ist nämlich eine der beiden Linien senkrecht, funktioniert die Funktion nicht (eigentlich logisch, da die Steigung dann unendlich wird).
Wenn ich in einem Jump'n'Run still stehe, geht mein Geschwindigkeitsvektor senkrecht nach unten und ich kann prompt mit keinem Tile mehr kollidieren.
Solltest du also noch ausbessern.

Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun

	tedy	Mi, Dez 03, 2008 18:59 Antworten mit Zitat
ZaP hat Folgendes geschrieben: Eine lineare Funktion ist eine Gerade... vieleicht meint er parralelen

tedy

Mi, Dez 03, 2008 18:59
Antworten mit Zitat

ZaP hat Folgendes geschrieben:

Eine lineare Funktion ist eine Gerade...

vieleicht meint er parralelen

	BladeRunner Moderator	Mi, Dez 03, 2008 19:06 Antworten mit Zitat
Da ich gerade (Wortwitz!) an etwas ähnlichem gebastelt habe kann ich wohl erklären was er meint: Es werden keine Geraden betrachtet sondern Strecken, d.h. sollte der Kollisionspunkt ausserhalb der Strecken liegen wird false zurückgegeben. Prinzipieller weise ein schöner Code, allerdings hat Hectic natürlich mit dem Spezialfall recht.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Mi, Dez 03, 2008 19:06
Antworten mit Zitat

Da ich gerade (Wortwitz!) an etwas ähnlichem gebastelt habe kann ich wohl erklären was er meint: Es werden keine Geraden betrachtet sondern Strecken, d.h. sollte der Kollisionspunkt ausserhalb der Strecken liegen wird false zurückgegeben.
Prinzipieller weise ein schöner Code, allerdings hat Hectic natürlich mit dem Spezialfall recht.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	Xaymar ehemals "Cgamer"	Mi, Dez 03, 2008 19:19 Antworten mit Zitat
geht einigermaßen schnell(45ms...). Aber nette Idee wie zuvor gesagt fällt man spezialfall(wahrscheinlich) dann durch den Boden. Ich hab ne andere Version die mit Mathematik arbeitet. Ob der Spezialfall bei meiner Funktion funzt, kann ich beantworten: ja(lässt sich aber optimieren). Hier mal Code: [AUSKLAPPEN] [EINKLAPPEN] Function LineIntersect(x1,y1, x2,y2, u1,v1, u2,v2) b1# = (y2 - y1) / Float(x2 - x1) b2# = (v2 - v1) / Float(u2 - u1) a1# = y1 - b1# * x1 a2# = v1 - b2# * u1 xi = - (a1-a2)/(b1-b2) yi = a1+b1xi If Y1 <> Y2 And V1 <> V2 If (x1 - xi)(xi-x2)> -1 And (u1-xi)(xi - u2)> 0 And (y1-yi)(yi-y2)>-1 And (v1-yi)*(yi-v2)>-1 Return 1 Else Return 0 EndIf ElseIf Y1 = Y2 If Y1 < Y2 For A = Y1 To Y2 If A > V1 And A < V2 Return 1 EndIf Next Else For A = Y1 To Y2 Step -1 If A > V1 And A < V2 Return 1 EndIf Next EndIf Return 0 ElseIf V1 = V2 If V1 < V2 For A = V1 To V2 If A > Y1 And A < y2 Return 1 EndIf Next Else For A = v1 To V2 Step -1 If A > Y1 And A < Y2 Return 1 EndIf Next EndIf EndIf End Function Funktioniert genauso und braucht bei mir nur 68ms. Mfg
Warbseite

Xaymar

ehemals "Cgamer"

Mi, Dez 03, 2008 19:19
Antworten mit Zitat

geht einigermaßen schnell(45ms...). Aber nette Idee

wie zuvor gesagt fällt man spezialfall(wahrscheinlich) dann durch den Boden.

Ich hab ne andere Version die mit Mathematik arbeitet. Ob der Spezialfall bei meiner Funktion funzt, kann ich beantworten: ja(lässt sich aber optimieren). Hier mal Code: [AUSKLAPPEN]

Function LineIntersect(x1,y1, x2,y2, u1,v1, u2,v2)
b1# = (y2 - y1) / Float(x2 - x1)
b2# = (v2 - v1) / Float(u2 - u1)
a1# = y1 - b1# * x1
a2# = v1 - b2# * u1
xi = - (a1-a2)/(b1-b2)
yi = a1+b1*xi
If Y1 <> Y2 And V1 <> V2
   If (x1 - xi)*(xi-x2)> -1 And (u1-xi)*(xi - u2)> 0 And (y1-yi)*(yi-y2)>-1 And (v1-yi)*(yi-v2)>-1
      Return 1
   Else
      Return 0
   EndIf
ElseIf Y1 = Y2
   If Y1 < Y2
      For A = Y1 To Y2
         If A > V1 And A < V2
            Return 1
         EndIf
      Next
   Else
      For A = Y1 To Y2 Step -1
         If A > V1 And A < V2
            Return 1
         EndIf
      Next
   EndIf
   Return 0
ElseIf V1 = V2
   If V1 < V2
      For A = V1 To V2
         If A > Y1 And A < y2
            Return 1
         EndIf
      Next
   Else
      For A = v1 To V2 Step -1
         If A > Y1 And A < Y2
            Return 1
         EndIf
      Next
   EndIf
EndIf
End Function

Funktioniert genauso und braucht bei mir nur 68ms.

Mfg

Warbseite

	tix	Mi, Dez 03, 2008 19:43 Antworten mit Zitat
bin jetzt n bisl verwirrt wie meinst das jetzt mit 45ms und bei dir 68ms haste dich da verschrieben oder soll das bedeuten die funktion benötigt wirklich 68ms das is ja ne schrecklich hohe zahl

tix

Mi, Dez 03, 2008 19:43
Antworten mit Zitat

bin jetzt n bisl verwirrt
wie meinst das jetzt mit 45ms und bei dir 68ms

haste dich da verschrieben oder soll das bedeuten die funktion benötigt wirklich 68ms
das is ja ne schrecklich hohe zahl

	Xaymar ehemals "Cgamer"	Mi, Dez 03, 2008 19:54 Antworten mit Zitat
ja verschrieben-.- Ich meinte eigentlich: Auf 32bit braucht die funktion bei mir 41ms und auf 24bit 68ms Ich mag meine Enter taste jetzt nicht mehr
Warbseite

Xaymar

ehemals "Cgamer"

Mi, Dez 03, 2008 19:54
Antworten mit Zitat

ja verschrieben-.-
Ich meinte eigentlich:
Auf 32bit braucht die funktion bei mir 41ms
und auf 24bit 68ms

Ich mag meine Enter taste jetzt nicht mehr

Warbseite

	TimBo	Mi, Dez 03, 2008 21:06 Antworten mit Zitat
Hi, danke für euer Feed-Back!! also ich meine "Strecken"-Kollision. mit Ergänzung folgender Zeilen kann man die Senkrechte wieder weg-tricksen Code: [AUSKLAPPEN] [EINKLAPPEN] If x1#-x2# =0 Then x1#=x1#-.0001 If x3#-x4# =0 Then x3#=x3#-.0001 Edit: 41ms für einen Aufruf oder mehrere ? 41 ms sind wirklich erschreckend hoch ! Ist doch schon fast nicht mehr real time fähig. Ich weiß nicht, was haltet ihr von meinem Speed, ist er in Ordnung ? Da habe ich leider nicht so wirklich viel Erfahrung. Viele Grüße TimBo
mfg Tim Borowski // CPU: Ryzen 2700x GPU: Nvidia RTX 2070 OC (Gigabyte) Ram: 16GB DDR4 @ 3000MHz OS: Windows 10 Stolzer Gewinner des BCC 25 & BCC 31 hat einen ersten Preis in der 1. Runde beim BWInf 2010/2011 & 2011/12 mit BlitzBasic erreicht.

TimBo

Mi, Dez 03, 2008 21:06
Antworten mit Zitat

Hi,

danke für euer Feed-Back!!

also ich meine "Strecken"-Kollision.

mit Ergänzung folgender Zeilen kann man die Senkrechte wieder weg-tricksen

Code: [AUSKLAPPEN]

If x1#-x2# =0 Then x1#=x1#-.0001
If x3#-x4# =0 Then x3#=x3#-.0001

Edit: 41ms für einen Aufruf oder mehrere ?
41 ms sind wirklich erschreckend hoch !
Ist doch schon fast nicht mehr real time fähig.

Ich weiß nicht, was haltet ihr von meinem Speed, ist er in Ordnung ?
Da habe ich leider nicht so wirklich viel Erfahrung.

Viele Grüße
TimBo

mfg Tim Borowski // CPU: Ryzen 2700x GPU: Nvidia RTX 2070 OC (Gigabyte) Ram: 16GB DDR4 @ 3000MHz OS: Windows 10
Stolzer Gewinner des BCC 25 & BCC 31
hat einen ersten Preis in der 1. Runde beim BWInf 2010/2011 & 2011/12 mit BlitzBasic erreicht.

Übersicht

BlitzBasic

Codearchiv

Nach Oben

BlitzBasic Portal

LineIntersect -> Kollision zweier Strecken(nicht Geraden)

Betreff: LineIntersect -> Kollision zweier Strecken(nicht Geraden)