Non-Image Collisions

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|739\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Blitz -> Non-Image Collisions
Tue, 28 Aug 2007, 09:11
mike_g	Do you mean when the point hits the line, or when the point passes one side of it? For both you will probably be best off starting with a line drawing function. You can make one yourself fairly easily if you know the formula of a straight line. Then you just check each pixel along the line to see if it overlaps any of the 'point's.
Tue, 28 Aug 2007, 09:25
JL235	I can't remember how exactly (I was doing this over a year ago) but you can find the formula to the line and then input the points co-ordinates to find out if it is on the line or not. Why do you need to do this?
Tue, 28 Aug 2007, 10:26
mike_g	You could have a 2d array that for the screen that will hold a 1 or 0 dependant on if that point is on a line or not, then for each 'point' you and 1 with the co-ords on the array to see if its a hit or not. It would take a bit of time to draw the array each loop, but the collision detection would be way faster as you only need to check each 'point' once as opposed to checking each 'point' against each pixel of each line. This could be made better in a language (like C++ or something) where you could use a 1 byte int, instead of Blitz where all integers are 4 Bytes. to make it even faster you could build the array 1/4 of the screen size. EG: 640480 resolution would have a 320240 array. It would be a little innacurate, but probably unnoticable to whoever is watching it. I hope this doesnt sound too confusing. If you want I could try make a little demo prog of what I mean.
Tue, 28 Aug 2007, 10:40
Jayenkai	For invisible munky I did the following.. 1. Static 1 pixel image.. "CollisionCheck" 2. Copyrect the area directly around the point you're checking.. In this case a 32x32 area, x-15,y-15, "AreaCheck" 3. Check collision between CollisionCheck and AreaCheck. So long as you have a black background (or use an imagebuffer for floors, then draw that onto the actual background), you can check the pixel against anything.. Unless you move too fast.. In which case, check between "WasHere X,Y" and "AmHere X,Y" -=-=- ''Load, Next List!''
Tue, 28 Aug 2007, 12:03
shroom_monk	Depending on how you eventually plan to do this, just a word of caution (I hope this makes sense!)... When you're doing physics simulations, objects tend to move in decimals, and at speeds not equal to 1 pixel per update. Therefore, the object may actually cross the line, but not be detected. That's something to be wary of. -=-=- A mushroom a day keeps the doctor away... Keep It Simple, Shroom!
Tue, 28 Aug 2007, 12:29
JL235	Ok, my suggestion is to use a Linear Equation. First, this could probably be easier used in languages such as Haskell and Ruby where you can create anonymous functions. That means you could find the equation of your line and wrap all the calculations into it's own function just for that line. I also had several problems with Blitz, like can you check for infinity? I had to trick the Blitz compiler into allowing me to create my own infinity constant (although it's actually a global because you cannot use variables when setting constants). Just crazy. Anywho, here it is. It uses some very basic maths, but it doesn't work very well on lines at an angle. I'm thinking it's a rounding error. Maybe if I could use doubles instead it'd have worked better, but this is the general idea I had. Graphics 640, 480, 0, 2 SetBuffer BackBuffer() Cls() Global ZERO# = 0.0 Global INFINITY# = 1 / ZERO# Const POINT_SIZE = 10 ; for the record, it's called a 'vector' because 'line' was taken Type Vector Field x1 Field y1 Field x2 Field y2 Field m# ; the gradient Field c End Type Type Point Field x Field y End Type newVector(60, 50, 250, 50) newVector(50, 60, 50, 250) newVector(60, 60, 250, 250) newVector(80, 70, 240, 80) point.Point = newPoint(20, 20) While Not KeyDown(1) Cls point\x = MouseX() point\y = MouseY() collision = False Color(255, 255, 255) For vector.Vector = Each Vector drawVector(vector) If isPointOnVector(point, vector) And (Not collision) collision = True EndIf Next Color(255, 255, 255) Text 10, 12, "collision?: " + collision Color(255, 0, 0) drawPoint(point) Flip Wend End Function newVector.Vector(x1, y1, x2, y2) vector.Vector = New Vector vector\x1 = x1 vector\y1 = y1 vector\x2 = x2 vector\y2 = y2 vector\m# = Float(y2-y1) / Float(x2-x1) vector\c = vector\y1 Return vector End Function Function newPoint.Point(x, y) point.Point = New Point point\x = x point\y = y Return point End Function Function isPointOnVector(point.Point, vector.Vector) If vector\m# = INFINITY# Return (vector\x1 = point\x) And (vector\y1 < point\y And point\y < vector\y2) Or (vector\y2 < point\y And point\y < vector\y1) Else Return point\y = Int(vector\m# * point\x + vector\c) EndIf End Function Function drawVector(vector.Vector) Line vector\x1, vector\y1, vector\x2, vector\y2 End Function Function drawPoint(point.Point) Line point\x-POINT_SIZE, point\y, point\x+POINT_SIZE, point\y Line point\x, point\y-POINT_SIZE, point\x, point\y+POINT_SIZE End Function --v If you want to look further at my solution I'd recommend you practice your maths skills with linear equations. It's pretty basic stuff so it should be pretty easy to learn through the internet.
Tue, 28 Aug 2007, 15:44
mike_g	Diablo: I'm a little skeptical about the effectiveness of your code. First off in you program it dosent seem to detect collisions correctly on the second line: Also for each point it needs to run through all the lines checking each point against it for a collision. I still think would be much faster to check an array for each point only, or even use ReadPixel if the boundaries are actually drawn to the screen.
Tue, 28 Aug 2007, 15:54
JL235	That's why I said it didn't work with lines at angles. I'm sure the maths is right, I've got my A-level book next to me. Plus it might be better to put a range on the result, so if y is within 1 or 2 pixels it is a collision. I also think rounding errors are causing it to be off!
Tue, 28 Aug 2007, 16:07
mike_g	Yeah Blitz rounding errors suck. Badly. It would be so much better if you could use double precision floats.
Tue, 28 Aug 2007, 16:08
JL235	Yes bear in mind my code is more of an idea rather then a solution. A fast idea, but still only an idea.
Tue, 28 Aug 2007, 17:45
mike_g	Tikihead: Your VX and VY variables indicate that you plan on moving your points at angles. I hope you are aware that by doing this they will be able to seep through the boundaries via the diagonals. Using a rough matrix like I suggested before, or checking a range like diablo said should fix this tho. But you wont have pixel-perfect collision detection.
Tue, 28 Aug 2007, 19:21
Jayenkai	Lay in bed with pen and paper. Then tested it. Wasn't perfect. So played "Trial and Error" with it for a little while. Graphics 800,600,32,2 SetBuffer BackBuffer() Dim coord(4,2) For n=1 To 4 coord(n,1)=Rand(0,800) coord(n,2)=Rand(0,600) Next move=0 Repeat Cls For n=2 To 5 If KeyDown(n) Then move=n-1 Next If move>0 Then coord(move,1)=MouseX():coord(move,2)=MouseY() If MouseDown(1) Then move=0 ;"Debug mode" is the 1, right at the end of this line! collision=LinesCollide(coord(1,1),coord(1,2),coord(2,1),coord(2,2),coord(3,1),coord(3,2),coord(4,1),coord(4,2),1) Color 255,255,255 If collision=0 Then Text 0,0,"No Collision" Color 255,0,0 If collision=1 Then Text 0,0,"Wow! That worked!! A Collision!" Color 125,125,0 If collision=1 Then Color 255,255,0 Line coord(1,1),coord(1,2),coord(2,1),coord(2,2) Color 0,125,125 If collision=1 Then Color 0,255,255 Line coord(3,1),coord(3,2),coord(4,1),coord(4,2) Flip Until KeyDown(1) Function LinesCollide(x1s#,y1s#,x1e,y1e#,x2s#,y2s#,x2e#,y2e#,debugme=0) out=0 ;Step 1. Find "triangle of collision" away from Point 1 of Line 2. TempDX#=x2s-x1s TempDY#=y2s-y1s TOCAng1#=(ATan2(0-TempDX,TempDY)+360) Mod 360 If debugme=1 Color 125,0,0 Line x2s,y2s,x2s+Sin(TOCAng1)1000,y2s-Cos(TOCAng1)1000 EndIf TempDX#=x2s-x1e TempDY#=y2s-y1e TOCAng2#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 125,0,0 Line x2s,y2s,x2s+Sin(TOCAng2)1000,y2s-Cos(TOCAng2)1000 EndIf ;Fix angle messups. A1Fix=0 ;This bit took pissing AGES! ;Lots of trial and error stuff! If Abs(TOCAng1-TOCAng2)<=180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1:TOCAng1=TOCTemp If Abs(TOCAng1-TOCAng2)>180 And TOCAng1<TOCAng2 Then TOCAng2=TOCAng2-360:A1Fix=1 If Abs(TOCAng1-TOCAng2)>180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1-360:TOCAng1=TOCTemp:A1Fix=2 If Abs(TOCAng1-TOCAng2)<=180 And TOCAng1>TOCAng2 Then TOCTemp#=TOCAng2:TOCAng2=TOCAng1:TOCAng1=TOCTemp ;Step 2. Find "triangle of collision" away from Point 2 of Line 2. TempDX#=x2e-x1s TempDY#=y2e-y1s TOCAng3#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 0,0,125 Line x2e,y2e,x2e+Sin(TOCAng3)1000,y2e-Cos(TOCAng3)1000 EndIf TempDX#=x2e-x1e TempDY#=y2e-y1e TOCAng4#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If debugme=1 Color 0,0,125 Line x2e,y2e,x2e+Sin(TOCAng4)1000,y2e-Cos(TOCAng4)1000 EndIf ;Fix angle messups. A2Fix=0 If Abs(TOCAng3-TOCAng4)<=180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3:TOCAng3=TOCTemp If Abs(TOCAng3-TOCAng4)>180 And TOCAng3<TOCAng4 Then TOCAng4=TOCAng4-360:A2Fix=1 If Abs(TOCAng3-TOCAng4)>180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3-360:TOCAng3=TOCTemp:A2Fix=2 If Abs(TOCAng3-TOCAng4)<=180 And TOCAng3>TOCAng4 Then TOCTemp#=TOCAng4:TOCAng4=TOCAng3:TOCAng3=TOCTemp ;Step 3. Find the angles of Line 2.. That is from point 1 to 2 and then point 2 to 1 TempDX#=x2s-x2e TempDY#=y2s-y2e Angle1to2#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If A1Fix>0 And Angle1to2>180 Then Angle1to2=Angle1to2-360 ;This bit, too, was trial and error! TempDX#=x2e-x2s TempDY#=y2e-y2s Angle2to1#=(ATan2(0-TempDX,TempDY) +360) Mod 360 If A2Fix>0 And Angle2to1>180 Then Angle2to1=Angle2to1-360 ;Step 4. If Angle from Point 1 to 2 is between TOC1+2, and Angle from 2 to 1 is between TOC3+4, then we've collided. (Hopefully!) If Angle1to2=>TOCAng1 And Angle1to2<=TOCAng2 And Angle2to1=>TOCAng3 And Angle2to1<=TOCAng4 Then out=1 Return out End Function --v WOOOOOHOOOOOOOOO!!!!! Now that's gonna come in handy! Oh yeah, um.. 1,2,3,4 to select a point.. Move point with mouse. \|edit\| Slight bugfix! Feel free to stresstest \|edit\| -=-=- ''Load, Next List!''
Wed, 05 Sep 2007, 16:14
Dabz	Could you check the rgb value of the pixels that form the line e.g. const PINK_RGB = $FFFF00FF color 255,0,255 ;Pink drawline 10,10,20,20 color 255,255,255 mx = mousex() my = mousey() lockbuffer backbuffer() pixel = readpixelfast(mx,my) unlockbuffer backbuffer() if pixel = PINK_RGB Text 0,0,"Line hit" end if --v Or something similar? Dabz -=-=- Intel Core i5 6400 2.7GHz, NVIDIA GeForce GTX 1070 (8GB), 8Gig DDR4 RAM, 256GB SSD, 1TB HDD, Windows 10 64bit
Wed, 05 Sep 2007, 16:23
Jayenkai	If you're checking a collision between 2 known lines, wouldn't you already know what color both those lines are? -=-=- ''Load, Next List!''
Wed, 05 Sep 2007, 16:28
Dabz	Here is a better example (working) Graphics 800,600,32 ;Note, RGB_PINK value may change at lower depth settings ;e.g. Graphics 800,600,16 will show the pink pixel value $FFF800F8 (RGB Values; 248,0,248) Const RGB_PINK = $FFFF00FF SetBuffer BackBuffer() Repeat Cls Color 255,0,255 Line 30,30,300,300 Color 255,255,255 mx = MouseX() my = MouseY() LockBuffer BackBuffer() pixel = ReadPixelFast(mx,my) UnlockBuffer BackBuffer() If pixel = RGB_PINK Text 0,20,"Line hit" Else Text 0,20,Hex$(pixel) End If ;Draw dot Rect mx,my,1,1 Flip Until KeyDown(1) --v Dabz -=-=- Intel Core i5 6400 2.7GHz, NVIDIA GeForce GTX 1070 (8GB), 8Gig DDR4 RAM, 256GB SSD, 1TB HDD, Windows 10 64bit
Wed, 05 Sep 2007, 16:40
mike_g	I was always of the impression that the lines were not drawn. Also you would also need to draw more than one line to make sure the pixels don't leak through the diagonals.
Wed, 05 Sep 2007, 23:48
Dabz	Also you would also need to draw more than one line to make sure the pixels don't leak through the diagonals That is true, but the concept is there. Dabz -=-=- Intel Core i5 6400 2.7GHz, NVIDIA GeForce GTX 1070 (8GB), 8Gig DDR4 RAM, 256GB SSD, 1TB HDD, Windows 10 64bit
Wed, 05 Sep 2007, 23:58
JL235	Another alternative, you could make the lines out of a string of points. Like a string of pearls. Going through each point in turn, you do a very approximate check if there is a point between the point your checking and the next point. If points are really close to each other then the check only has to be very approximate. That's how I did the collision detection on Space Snake. \|edit\| Although it should be noted I only check the head of the snake against the rest of the body. But I doubt it would be slow to check more points and Blitz would be faster at that sort of thing then Ruby. \|edit\|
Thu, 06 Sep 2007, 01:47
Jayenkai	My code works just fine!