collision detection

[ShadowDust]

can any1 offer a collision detection example/tutorial??

[cha0s]

Code: Select all

Function CheckBounds ( door_check As Integer, _ 
                       ByVal x1 As Integer, _ 
                       ByVal y1 As Integer, _ 
                       ByVal x2 As Integer, _ 
                       ByVal y2 As Integer, _ 
                       ByVal w1 As Integer = 16, _ 
                       ByVal h1 As Integer = 16, _ 
                       ByVal w2 As Integer, _ 
                       ByVal h2 As Integer _ 
                     ) As Integer
  

  Dim As Integer xm, ym

  If ((x1 + w1) > x2) And x1 < x2 + w2 Then xm = Not 0
  If ((y1 + h1) > y2) And y1 < y2 + h2 Then ym = Not 0

  If xm And ym Then 
    Return door_check 
  
  Else 
    Return -1

  End If


End Function

[anonymous1337]

can any1 offer a collision detection example/tutorial??

What kind? 2-d or 3-d?

I'm real sorry. Agh! I should have worked on the tutors more. I don't think I'd be anywhere near good collision detection yet, but still. I'd be close ^_~

[arenth]

Well finding the distance between two objects to collide then checking if its less then a certain value is a good way, its actually really simple, although it is slightly slower then if x>x2 then etc.

Code: Select all

function distFromPoints(byval x1 as single, byval y1 as single, byval x2 as single, byval y2 as single) as single

   dim C as single

   C = SQR ( (abs(X1 - X2)^2) + (abs(y1-y2)^2) )

   'A^2+b^2=C^2

    'Pyhtagorean theorum I think
    'C will return the distance in pixels between x1,x2 and y1,y2

   return C

end function


if distFromPoints(man1.x,man1.y,man2.x,man2.y)< 10 then 

'10 is the distance in pixels with which you want them to collide after, eg if you have 2 balls with a radius of 5 then at 10 pixels they should collide.

   'Do collide stuff here

end if

--Edit--Stupid code tags--Edit--

[Dr_D]

I'm going to write a tute someday.. I just haven't got around to it yet. I think rel might have already made one.... Look around on Genso's Junkyard. ;)

[Thrawn89]

If your Images are just rectangular shaped objects then you dont have to use all of those processor intesive ^ and SQR().

If they are circular then you have no choice but to use arenth's way if you want exact match...that is an EXACT match and they have to be circular.

In most cases just defining an imaginary rectangular box around a circle ((x-r, y-r)-(x+r, y+r))...or even ellipse ((x-w/2, y-h/2)-(x+w/2, y+w/2)) will be a satisfactory trade off between speed and accuaracy, and wont be noticed by the user in real time.

Basically my algo to dectect if two rectangles are touching is a maximum of 9 conditionals with little adding and subtracting. All that you are doing is checking each corner of each rectangle to see if it lies inbounds with the other rectangle. If one does then the rectangles MUST be touching in a 2D plane, else they MUST NOT be touching at all. To do this (and to optimize code) you check to see if any of the first Rectangle's X coordinated of its four corners lie inside the other's, if non dont then the MUST NOT be touching. If they are, then you do the same for ys, if ANY of the ys, regaurdless of the corner that had the good X is in bounds of the other's ys then you got a hit.

Code: Select all

'Compare Rect1 X1, Y1, Height1, Width1 To Rect2 X2, Y2, Height2, Width2

Dim As Integer CheckY = 0

If X1 >= X2 And X1 <= X2 + Width2 Then CheckY = -1
If X1 + Width1 >= X2 And X1 + Width1 <= X2 + Width2 Then CheckY = -1
If X2 >= X1 And X2 <= X1 + Width1 Then CheckY = -1
If X2 + Width2 >= X2 And X2 + Width2 <= X1 + Width1 Then CheckY = -1

If CheckY Then
  If Y1 >= Y2 And Y1 <= Y2 + Height2 Then WEGOTAHIT
  If Y1 + Height1 >= Y2 And Y1 + Height1 <= Y2 + Height2 Then WEGOTAHIT
  If Y2 >= Y1 And Y2 <= Y1 + Height1 Then WEGOTAHIT
  If Y2 + Height2 >= Y2 And Y2 + Height2 <= X1 + Height1 Then WEGOTAHIT
End If

~Thrawn~

[Deleter]

Circle collision:

Code: Select all

'ripped from tera.bas by Deleter
'circle collision detection.
'give coordinates and radii of two circles and it returns whether collision is true or false
DECLARE FUNCTION Collision (x1 AS INTEGER,y1 AS INTEGER,r1 AS INTEGER,x2 AS INTEGER,y2 AS INTEGER,r2 AS INTEGER) AS BYTE
DECLARE FUNCTION Distance (x1 AS INTEGER, y1  AS INTEGER, x2  AS INTEGER, y2  AS INTEGER)  AS INTEGER

FUNCTION Collision (x1 AS INTEGER,y1 AS INTEGER,r1 AS INTEGER,x2 AS INTEGER,y2 AS INTEGER,r2 AS INTEGER) AS BYTE
    IF Distance(x1,y1,x2,y2) <= (r1+r2) THEN RETURN True
    RETURN False
END FUNCTION

FUNCTION Distance (x1 AS INTEGER, y1  AS INTEGER, x2  AS INTEGER, y2  AS INTEGER)  AS INTEGER
    FUNCTION=INT(SQR( ( x1 - x2 ) * ( x1 - x2 ) + ( y1 - y2 ) * ( y1 - y2 ) ))
END FUNCTION 

edit: @thrawn, you dont need ^, just SQR. But I do agree that which one you use is dependant on the shapes of your objects.

[Dr_D]

Here's a little demo I made one day. I didn't comment the code at all... guess it's a bad habit. It isn't hard to figure out how it works though. ;)

Code: Select all

'$Include: "FBGFX.BI" 
DEFINT A-Z 
Option Explicit 
ScreenRes 640,480,8,2,1 
ScreenSet 0,1 

Const FALSE=0, True = NOT FALSE 


TYPE Vector2D 
   X as Single 
   Y as Single 
END Type 


DECLARE Sub Vec_2D_Normal(a as Vector2D, b as Vector2D,rn as Vector2D,ln as Vector2D) 
DECLARE Function ClosestPointOnLine(Va as Vector2D, Vb as Vector2D,vPoint as Vector2D) as Vector2D 
DECLARE Sub Vec_2D_Normalize(v as Vector2D) 
DECLARE Function Vec_2D_Len(V as Vector2D) as Single 
DECLARE Function Vec_2D_Dot(a as Vector2D, b as Vector2D) as Single 
DECLARE Function Vec_2D_Dist(vA as Vector2D, vB as Vector2D) as Single 

Dim Pl as Vector2D, Pld as Vector2D, Radius as Single 
Dim Ero as Vector2D, Cent as Vector2D, tDist as Single 
Dim i, iAnd1, Ang, Num_Verts, In as String*1 

Pl.X = 50 
Pl.Y = 50 
Radius=10 

Read Num_Verts 
Dim Lines(Num_Verts) as Vector2D 

For i = 0 to UBOUND(Lines) 
 Read Lines(i).X, Lines(i).Y 
Next 



Do 
    In = Inkey$ 
    CLS 
    
    If MultiKey(Sc_Left) then PlD.X -=.15 
    If MultiKey(Sc_Right) then PlD.X +=.15 
    If MultiKey(Sc_Up) then PlD.Y -=.15 
    If MultiKey(Sc_Down) then PlD.Y +=.15    
    
    PlD.X*=.95 
    PlD.Y*=.95 
    
    Pl.X+=PlD.X 
    Pl.Y+=PlD.Y 

    For i=0 to UBOUND(Lines)-1 step 2 
        iAnd1 = i+1 
        Vec_2D_Normal Lines(i), Lines(iAnd1), Cent, Cent 
        Ero = ClosestPointOnLine(Lines(i), Lines(iAnd1), PL) 
        tDist=Vec_2D_Dist(Pl, Ero) 
        
        If tDist<Radius Then 
            Pl.X+=(Cent.X*(Radius-tDist)) 
            Pl.Y+=(Cent.Y*(Radius-tDist)) 
        End If 
        
        Line(Lines(i).X, Lines(i).Y)-(Lines(iAnd1).X, Lines(iAnd1).Y),14 
        Line(Ero.X, Ero.Y)-(Ero.X + (Cent.X*Radius), Ero.Y + (Cent.Y*Radius)),7 
        Circle(Ero.X, Ero.Y),Radius,14 
    Next 
    

    Circle (Pl.X,Pl.Y),Radius, 1 
    PSET (Pl.X,Pl.Y), 4 

    Wait &H3da,8 
    Flip 
Loop Until In=CHR$(27) 

End 



Function ClosestPointOnLine(Va as Vector2D, Vb as Vector2D, vPoint as Vector2D) as Vector2D 
    Dim tVector1 as Vector2D, _ 
        tVector2 as Vector2D, _ 
        vReturn as Vector2D, _ 
        d as Single, _ 
        t as Single 

    tVector1.X = VPoint.X - Va.X 
    tVector1.Y = VPoint.Y - Va.Y 
    
    tVector2.X = Vb.X - Va.X 
    tVector2.Y = Vb.Y - Va.Y 
    
    Vec_2D_Normalize tVector2 
    
    d = Vec_2D_Dist(VA, VB) 
    t = Vec_2D_Dot(tVector2, tVector1) 
    
    If t<=0 Then Return Va 
    
    If t>=d Then Return Vb 
    
    vReturn.X = Va.X + (tVector2.X * t) 
    vReturn.Y = Va.Y + (tVector2.Y * t) 
    Return vReturn 
End Function 


Function Vec_2D_Dist(vA as Vector2D, vB as Vector2D) as Single 
    Dim Dx as Single, _ 
        Dy as Single 
    Dx = Va.X - Vb.X 
    Dy = Va.Y - Vb.Y 
    Vec_2D_Dist = SQR(Dx^2+Dy^2) 
End Function 


SUB Vec_2D_Normalize(v as Vector2D) 
    Dim VecLen as Single 
    VecLen = Vec_2D_Len (V) 
    v.x = v.x / VecLen 
    v.y = v.y / VecLen 
END SUB 


Function Vec_2D_Len(V as Vector2D) as Single 
    Dim TLen as Single 
    TLen = SQR(v.x^2 + v.y^2) 
    If TLen = 0 then TLen = 1 
    Vec_2D_Len = TLen 
End Function 


FUNCTION Vec_2D_Dot(a as Vector2D, b as Vector2D) as Single 
    Vec_2D_Dot = a.x*b.x + a.y*b.y 
END Function 


SUB Vec_2D_Normal(a as Vector2D, b as Vector2D, rn as Vector2D, ln as Vector2D) 
    Dim VecLen as Single, _ 
        D as Vector2D    
    
    D.x = b.x - a.x 
    D.y = b.y - a.y 
    
    VecLen = Vec_2D_Len(D) 
    
    'The reason this sub returns two values... 

    'Rn is clockwise winding... 
        Rn.x = (-D.y) / VecLen 
        Rn.y = (D.x) / VecLen 
    
    'Ln is anti-clockwise winding, which is what we're using... 
        Ln.x = (D.y) / VecLen 
        Ln.y = (-D.x) / VecLen 
END SUB 



Data 21 

Data 0,0 
Data 0,240 

Data 0,240 
Data 100,340 

Data 100,340 
Data 125,400 

Data 125,400 
Data 300,450 

Data 300,450 
Data 450,470 

Data 450,470 
Data 600,370 

Data 600,370 
Data 550,300 

Data 550,300 
Data 625,250 

Data 625,250 
Data 500,0 

Data 500,0 
Data 320,50 

Data 320,50 
Data 0,0

[Thrawn89]

@Deleter:
Well, I was specifically refering to the pythag code posted above me with the ^. However even with out the ^, I still think that the rectangle algo is faster.

Yes the rectangle code is dependant on the shapes of the objects...but then again so is the circle one.

I just think the rectangle algo is better. Like I said it you can specify it for a circle by having each side of the rectangle as a tangent of the circle. Yes its not entirely accurate...its like a 20% drop or something, but its so much faster and dynamic, and in most cases that 20% drop is unoticed by the user. What if you have an ellipse? A rectangle algo would be better for that. What if you have a wall? A rectangle aglo would be better.

The only thing I can think of is that the circle one is better is for other dimensions besides 2D.

And yet, I remember having this debate back in Quickbasic news.

EDIT:
@DrD:
Thats sweet

~Thrawn~

[cha0s]

if you need precise calcs, just do a simple bounds check first, and if the object is within the bounds, then do a distance calc. compromise ;)

[ShadowDust]

im gonna use both the distance(^) collision, and the rectangle collision.. plus a poly collision, which is an advance version of rectangle :D

I'll leave it to the library user to decide..

[Deleter]

@Thrawn, I do realize it is more processor heavy, but there are times where it is better to use for your game. For example, my game I ripped that code out of was just circles, so circle collision was pefect for it. It all depends on how many objects you are going to have, and how precise the collision needs to be for the game to be fun.

[anonymous1337]

@deleter:
Yeah, deleter, your game was rather nice :D

It really wouldn't be fun if you couldn't get that close tolerance to those circles without getting hurt.

[Thrawn89]

I agree with cha0s, if it is absolutly imperitive that you need precise detection on a circle to do that way.