2d Collision Detection With Rotating Rectangles... anyone?

[keeling]

OK, I have never done an arcade style game before (most of my experience has been in 'practical' programming) so I am coming here on bended knees seeking advice.

Since this is my first 'arcade' game, I thought I'd do something simple. The code below should be obvious to anyone above the age of 25. :-) What I need help on is collision detection of two objects in bounded rectangles. I've seen a lot of the algorithms online for this and they are simple, but they don't seem to work for this instance because the rectangles I am working with are rotating.

My first idea was to take the object rectangle, rotate it back to the zero angle, move it to the origin, rotate all other objects by the same angle, translate them by the same amount, and then check vertices. If there is a collision, negate the move (or register a hit). This seems like it might be a little slow.

Any wise words of experience here? Is this the way to go, or is there a better way?

Code:

option explicit
'$include once: "fbgfx.bi"
const kScreen_Width = 800
const kScreen_Height = 600
const TankScale = kScreen_Width / 40
const FALSE = 0
const TRUE  = NOT FALSE
const Pi = 3.14159265359
const FR = 60  'target Frame Rate
const IFR = 1/FR  'inverse Frame Rate
Type Tank
   tx as single   'x coord
   ty as single   'y coord
   ta as single   'angle
   ts as single   'speed
   tr as single   'turn rate
   tf as byte     'has a live bullet i.e. IsFired
   th as byte     'is the tank hit?
   tc as integer  'tank's color
   tn as integer  'tank's score
   bx as single   'bullet's x
   by as single   'bullet's y
   ba as single   'bullet's angle
   bs as single   'bullet's speed
   bm as integer  'number of frames bullets live
   bl as integer  'frames bullet has left
end type
  
declare sub DrawTank   (ByRef tTank as Tank)
declare sub AdjustTank (ByRef tTank as Tank)

SCREENRES kScreen_Width,kScreen_Height, 32, 2 ,1

dim Tank1 as Tank
dim Tank2 as Tank

'Initalize Tanks
with Tank1
   .tx = kScreen_Width * .75
   .ty = kScreen_Height / 2
  
   .ta = Pi
   .ts = kScreen_Width/(FR*10)  'full screen in 10 seconds
   .tr = 2*Pi/(FR*3)            'a full rotation every 3 seconds
  
   .tf = FALSE
   .th = FALSE
  
   .tc = RGB(255,0,255)
   .tn = 0
  
   .bs = .ts * 2              'bullets move twice as fast as tank
   .bm = FR * 2               'bullets live for approx 2 seconds
end with

with Tank2
   .tx = kScreen_Width * .25
   .ty = kScreen_Height / 2
  
   .ta = 0
   .ts = kScreen_Width/(FR*10)  'full screen in 10 seconds
   .tr = 2*Pi/(FR*3)            'a full rotation every 3 seconds
  
   .tf = FALSE
   .th = FALSE
  
   .tc = RGB(255,255,0)
   .tn = 0

   .bs = .ts * 2              'bullets move twice as fast as tank  
   .bm = FR * 2               'bullets live for approx 2 seconds
end with  

dim m as double
dim t as double


SCREENSET 1, 0

'just to check fps
dim f as integer
f=0
m = timer
do
   'to hold around 60 fps
   t = timer

   'tank1 controls
   with Tank1
      if MULTIKEY(SC_UP) then
         .tx += cos(.ta) * .ts
         .ty += sin(.ta) * .ts
      end if
      if multikey(SC_LEFT) then
         .ta -= .tr
      end if
      if multikey(SC_RIGHT) then
         .ta += .tr
      end if
   end with
  
   'uhm..... well... Tank2 controls
   with Tank2
      if MULTIKEY(SC_W) then
         .tx += cos(.ta) * .ts
         .ty += sin(.ta) * .ts
      end if
      if multikey(SC_A) then
         .ta -= .tr
      end if
      if multikey(SC_D) then
         .ta += .tr
      end if
   end with

'draw screen  
   cls
   DrawTank Tank1
   DrawTank Tank2
   AdjustTank Tank1
   AdjustTank Tank2
   SCREENCOPY


   f += 1
   do while t + IFR > timer: loop
LOOP WHILE NOT MULTIKEY(SC_ESCAPE)

t = f/(timer-m)
cls
? t
screencopy
do while inkey$<>"":loop
sleep
end  

sub DrawTank (ByRef tTank as Tank)
  
   'Draw the tank on a 16x16
  
   dim P(15,1) as single
   dim i as integer
   dim c as single
   dim s as single
   dim tmpX as single
   dim tmpY as single
  
   P(0,0)  =     -TankScale: P(0,1)  = -7/8*TankScale
   P(1,0)  =  5/8*TankScale: P(1,1)  = -7/8*TankScale
   P(2,0)  =  5/8*TankScale: P(2,1)  = -3/8*TankScale
   P(3,0)  =  3/8*TankScale: P(3,1)  = -3/8*TankScale
   P(4,0)  =  3/8*TankScale: P(4,1)  = -1/8*TankScale
   P(5,0)  =      TankScale: P(5,1)  = -1/8*TankScale
   P(6,0)  =      TankScale: P(6,1)  =  1/8*TankScale
   P(7,0)  =  3/8*TankScale: P(7,1)  =  1/8*TankScale
   P(8,0)  =  3/8*TankScale: P(8,1)  =  3/8*TankScale
   P(9,0)  =  5/8*TankScale: P(9,1)  =  3/8*TankScale
   P(10,0) =  5/8*TankScale: P(10,1) =  7/8*TankScale
   P(11,0) =     -TankScale: P(11,1) =  7/8*TankScale
   P(12,0) =     -TankScale: P(12,1) =  3/8*TankScale
   P(13,0) = -5/8*TankScale: P(13,1) =  3/8*TankScale
   P(14,0) = -5/8*TankScale: P(14,1) = -3/8*TankScale
   P(15,0) =     -TankScale: P(15,1) = -3/8*TankScale
  
   c = cos(tTank.ta)
   s = sin(tTank.ta)
  
   'used lines over images because it is easier to rotate
   'using an elementary matrix
   for i = 0 to 15
      tmpX = c*P(i,0) - s * P(i,1)
      tmpY = s*P(i,0) + c * P(i,1)
      P(i,0) = tmpX + tTank.tx
      P(i,1) = tmpY + tTank.ty
   next i

   line (P(15,0),P(15,1)) - (P(0,0),P(0,1)),tTank.tc
  
   for i = 1 to 15
      line - (P(i,0),P(i,1)),tTank.tc
   next i
   'paint (tTank.tx,tTank.ty),tTank.tc
end sub

sub AdjustTank (ByRef tTank as Tank)
      with tTank
         if .tx < -TankScale then .tx = kScreen_Width + TankScale
         if .tx > kScreen_Width + TankScale then .tx = -TankScale
        
         if .ty < -TankScale then .ty = kScreen_Height + TankScale
         if .ty > kScreen_Height + TankScale then .ty = -TankScale
        
         if .ta > 2*Pi then .ta -= 2*Pi
         if .ta < 0 then .ta += 2*Pi
         if .tf then
            if .ba > 2*Pi then .ba -= 2*Pi
            if .ba < 0 then .ba += 2*Pi
         end if
      end with

end sub

[Dusky_Joe]

Did I understand you right?
In your program, there are some objects (rotating rectangles). As they're rotating, treat them as circles.
So you only had to calculate the distance of any point to the middle of your object:

Code:

TYPE Object
x1 AS INTEGER
y1 AS INTEGER
x2 AS INTEGER
y2 AS INTEGER
END TYPE
DIM abc AS Object

...

'Calulate middle of your object
'Perhaps you'd like to use Integer-Divs...
xm = (abc.x1 + abc.x2) / 2
ym = (abc.y1 + abc.y2) / 2

'Now calculate the radius of the circle:
tmpDistX = xm - abc.x1
tmpDistY = ym - abc.y1
radius = SQR(xm^2 + ym^2) 'Phythagoras

Now, you only need to check, if any point (x|y) is inside the radius.
For this, you have to calculate the distance of (x|y) to (xm|ym) by using the Phythagoras.

Hope it helped you!
PS:
I'm 16, UNDER the age of 25 8)


Have a nice day!
Ciao


/Edit:
Of course, your object will have much more elements in the TYPE-Block. For simplicity, I only postet the coordinates of the opposite corners.
It could be something like this:

Code:

Q
          / \
         /   -
(x1|y1) P     \
         \ M   R (x2| y2)
          -   /
           \ /
            S

(I know, It doesn't really look like a rectangle...)

Q and S must be definded by the angle, or by own coordinates. In this case, R should have the coordinates (x3| y3), to give it mathematical correctnes 8)

The disadvantage of this method is, that the Collision is detected, although the two elements aren't touching. Big rectangles will have a big "dummy-Space"...
But: It's QUITE easy to implement, and the size of the dummy-space should be abidable...

Example:
x1 = 100
y1 = 100
x2 = 150
y2 = 150

=>
xm = 125
ym = 125
radius = 35.36
dummySpace = ~10


Users won't detect this little mistake, if the game is only fast enough *g*

[keeling]

The age joke was about the subject of the game. Combat isn't as popular now as it was back in 78 or so. :-)

I thought about circle-circle detection, but it doesn't seem appropriate given the blockish nature of the game. If I have too I will use it, but I want to see if there is a better way.

Perhaps a circle-circle detection followed by a pixel-by-pixel follow up? This is all a little new to me.

[shiftLynx]

I sat down and figured a lot of things out about how to detect whether 2 finite lines in 2D space could intersect, but there's a lot of maths to it and it is probably overkill. It does give perfect collision detection, however. If you're interested, I can reply with the working for it.

As it is quite expensive, as far as calculations are concerned, you could do as you say: use circle-collision detection (cheap on CPU cycles) and then detect whether the lines itersect or not (expensive on CPU cycles).

-shiftLynx

[keeling]

I am sure the math isn't going to be a problem. :-)

I would be interested in seeing it. I am currently looking at fast equations for points in a convex polygons (Modern Geometry flash backs here) and at line segment intersections.

I have a feeling that points in a poly might be the answer if I am correct in my memory of a prove I did long ago (for the aforementioned nightmare inducing modern geometry class) that when two convex polys intersect that a vertex must pass through first (seems obvious though).

If that is the case, do a fast circle-circle check, followed by a check of each vertex of the objects vs. all polys in the area of the circle's radius?

[aetherfox]

I don't think the circle method is a bad way at all. Unless your rectangles are very long, it will be fine. In fact, the more squarish your sprites, the most effective it will be.

Pixel perfect collision detection is very possible, and very doable, but a little CPU intentsive. With FB you shouldn't have speed problems.

I'll dig up oooooooooold VB code.

[shiftLynx]

Okay, first of all, the edges must be defined as lines in vector form. Let the lines be:

p = a1 + m1d1
q = a2 + m2d2

(p/q = any point on the line, ax = a known point on the line, mx = some scalar magnitude, dx = direction vector)

Now let's assume a few more things:

1) an is the position vector of the start of the line.
2) dn (the direction vector of the line) has been normalised.
3) We have 2 more scalar values: max1 and max2, which define the maximum values of m1 and m2 (hence allowing us to make this line finite; we'll also assume that max1 >= 0 and max2 >= 0).

Before we do -any- calculations, we can check whether the lines will never intersect simply by checking if they are parallel (since lines on a 2D plane -always- intersect unless they're parallel... I hadn't really thought of it like this until I started thinking about these collision equations!); the dot product of the direction vectors of the two lines should be equal to the product of the magnitude of the two direction vectors. Seeing as we're assuming that the direction vectors have been normalised, the product of the magnitude of the two direction vectors will always be 1. Hence, if d1 . d2 = 1, the lines will never intersect so we can stop processing.

Also note that it is possible for the lines to be parallel and going in the opposite direction, so we have to check for d1 . d2 = -1 as well.

Now, for the lines to intersect, they must share a common point. Thus:

a1 + m1d1 = a2 + m2d2

At this point, I wish vector division was defined, but it's not, so we have to go a long, horrible route. Here is the plan for the road ahead: we calculate the value of m1 and m2 for where the lines intersect, then check these values against max1 and max2. If (m1 < max1) and (m2 < max2) then the lines are intersecting.

So, into cartesian mode:

a1_x + m1d1_x = a2_x + m2d2_x ---(1)
a1_y + m1d1_y = a2_y + m2d2_y ---(2)

From eq. 1:
m2 = (a1_x + m1d1_x - a2_x) / d2_x

Substitute into eq. 2:
a1_y + m1d1_y = a2_y + d2_y((a1_x + m1d1_x - a2_x) / d2_x)
=> m1d1_y - (m1d1_xd2_y / d2_x) = a2_y - a1_y + d2_y((a1_x - a2_x) / d2_x)
=> m1 = (a2_y - a1_y + d2_y((a1_x - a2_x) / d2_x)) / (d1_y - (d1_xd2_y) / d2_x)

Multiply by d2_x / d2_x:
m1 = (d2_x(a2_y - a1_y) + d2_y(a1_x - a2_x)) / (d2_xd1_y - d1_xd2_y)


Okay, now we need to do the same for m2...

From eq. 1:
m1 = (a2_x + m2d2_x - a1_x) / d1_x

Substitute into eq. 2:
a1_y + d1_y((a2_x + m2d2_x - a1_x) / d1_x) = a2_y + m2d2_y
=> m2d2_y - (m2d2_xd1_y / d1_x) = a1_y - a2_y + d1_y((a2_x - a1_x) / d1_x)
=> m2 = (a1_y - a2_y + d1_y((a2_x - a1_x) / d1_x)) / (d2_y - (d2_xd1_y / d1_x))

Multiply by d1_x / d1_x:
m2 = (d1_x(a1_y - a2_y) + d1_y(a2_x - a1_x)) / (d1_xd2_y - d2_xd1_y)


Okay. In summary:-

m1 = (d2_x(a2_y - a1_y) + d2_y(a1_x - a2_x)) / (d2_xd1_y - d1_xd2_y)
m2 = (d1_x(a1_y - a2_y) + d1_y(a2_x - a1_x)) / (d1_xd2_y - d2_xd1_y)

Now all you have to do is check that:

0 <= m1 < max1
0 <= m2 < max2

(Note: it's not <= max1; imagine if you had a line of length 1 - it should occupy only 1 pixel, which would make the magnitude of the line 0)

Here is what happens if you try to put it back into vector form:
Let g = a2 - a1
Let h = a1 - a2
Let x = (1, 0)
Let y = (0, 1)

m1 = ((d2 . x)(g . y) + (d1 . y)(h . x)) / ((d2 . x)(d1 . y) - (d1 . x)(d2 . y))

m2 = ((d1 . x)(h . y) + (d2 . y)(g . x)) / ((d1 . x)(d2 . y) - (d2 . x)(d1 . y))


It looks a little neater. And that's it. Maybe it is possible to optimise it, I'm not sure.

These might be a couple of helpful structures to have:

[syntax="QBASIC"]
TYPE Vec2D
x AS SINGLE
y AS SINGLE
END TYPE

TYPE Edge2D
start AS Vec2D
dir AS Vec2D
length AS SINGLE
END TYPE
[/syntax]

Just make sure that dir is normalised; length represents the maxn values I used here...

Hope this helps. At least all that scribbling and thinking I did didn't go to waste.

-shiftLynx

P.S. I started thinking about what you should do after the objects are found to intersect in order to make the collision realistic... I haven't thought of anything good at the moment, maybe you'll think of that (or have thought of that) anyway. Maybe you don't even need the objects to bounce off of eachother!

[shiftLynx]

Some untested code:

[syntax="QBASIC"]
TYPE Vec2D
x AS SINGLE
y AS SINGLE
END TYPE

TYPE Edge2D
start AS Vec2D
dir AS Vec2D
length AS Vec2D
END TYPE

...

FUNCTION DoEdgesCollide%(a AS Edge2D, b AS Edge2D)
IF (a.dir.x * b.dir.x) + (a.dir.y * b.dir.y) = 1 THEN
DoEdgesCollide% = 0
EXIT FUNCTION
END IF

p! = ((b.dir.x * (b.start.y - a.start.y)) + (b.dir.y * (a.start.x - b.start.x))) / ((b.dir.x * a.dir.y) - (a.dir.x * b.dir.y))
q! = ((a.dir.x * (a.start.y - b.start.y)) + (a.dir.y * (b.start.x - a.start.x))) / ((a.dir.x * b.dir.y) - (b.dir.x * a.dir.y))

IF p! >= 0 AND q! >= 0 AND p! < a.length AND q! < b.length THEN
DoEdgesCollide% = 1
EXIT FUNCTION
END IF

DoEdgesCollide% = 0
END FUNCTION
[/syntax]

-shiftLynx

[keeling]

Ok, I've looked at your code and there are a few questions....

The assumption that if the slopes of the lines are the same then they are parallel is faulty... what if the lines are on top of each other.

Have you checked this for speed? There are a lot of multiplications and divisions in here.... and that is before you find the direction of the line segment and normalize it.

It is a place to start from though.

[shiftLynx]

Good point about the parallel check; just exclude it from the routine.

I know it is slow and could probably be optimised; I have said this from the beginning. If you only check these collisions after the objects are within close proximity of eachother (using the circle-circle intersection method), that would save the calculations to only be done once a collision between two objects is quite likely.

The function isn't -too- strenuous; there are 2 divisions, 8 multiplications and several addition/subtractions per edge to be done per probably-intersecting-object. This will occupy very little processing time on a modern computer, really.

About finding the direction and normalising - I have been assuming that all of your rectangles are described using vector notation, so that when you need to rotate a rectangle, you must modify the 4 related vector line directions. Rotations will hopefully not be done every cycle, so you can afford to spend a few cycles on normalisation.

I am curious about trying to squeeze some more power out of the fact the direction vector is normalised; the intersection code uses this normalised vector a lot.

-shiftLynx