Need help with 2d collision ASAP

Game development specific discussions.
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

leopardpm wrote:in regards to your questions regarding BasicCoders code... what it does is iterate through all 4 corners of one object, comparing each corner to see if it is 'inside' the rectangle of the other object... it does this by seeing if:

Checking Collision for OBJ-A against OBJ-#

is OBJ-A corner #1 x-value between the top two corners of object OBJ-#?
if so, then is OBJ-A corner #1 y-value also between the top and bottom of object OBJ-#?
if so, then corner #1 of OBJ-A is inside of the rectangle which defines OBJ-#
Now calculate the slope from the x & y position values of both objects to determine which direction
Oh I get this solution now :D!

So our character is found within the entity.

We require an angle. That angle will tell us how our character got into the entity.

To define our angle, we require two line segments, which are defined by:
Line segment 1: from the origin (ul corner) of the collision box to character's position in entity,
Line segment 2: to define our second line segment, we require the previous position of our character (the one where it was last seen outside of entity). The line segment is defined from this point to the current point of our character.
Let us call the origin of the collision box A, the previous character position point B, and the current character position point O.

The angle AÔB will define exactly where he came from!

I have now a few queries:

1. There will be four angles where our character will have hit exactly a corner: 0°, which is the UL corner. It is finding the other three which might be an issue, as they will change depending on the size of the entity's collision box. They are important as their range defines the direction of collision, right? EDIT: figured it: just calculate them using each corner as the second line segment from point O.
2. Erm, how to find the value of angle AÔB at all? xD! Some weird black magic or other. I'll also try searching online. EDIT: watching this video from Khan Academy. Hopefully this helps. Feel free to help me on this topic though.
Last edited by datwill310 on May 01, 2017 21:51, edited 1 time in total.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Need help with 2d collision ASAP

Post by leopardpm »

how to find the angle between two points? SLOPE
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

leopardpm wrote:how to find the angle between two points? SLOPE
What is meant by "calculate slope"? Is it like finding the gradient? Would that alone work? It just tells me how steep our character has entered into the entity, not the direction definitively, e.g. if gradient is shallow (if we are defining slope from origin of collision box and up side), then that could mean either up or right side esp. if character position is closer to the right edge.
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Need help with 2d collision ASAP

Post by BasicCoder2 »

Ok.
Looking at the old collision code again the routine returns the corners that are within another rectangle.
In the code below it is telling you which combination of the red rectangle's corners are within the green rectangle.
Hold the space bar down during a collision to keep it moving.
So yes if say the bottom right corner enters the green rectangle you cannot tell if it came from above or from the left however you do know the direction the red rectangle is moving so you can deduce the answer from that.
Later I will write a demo how this can be done and also the angle of collision.
.

Code: Select all

const SCRW = 640
const SCRH = 480
screenres SCRW,SCRH,32

type RECTANGLE
    as integer x
    as integer y
    as integer w
    as integer h
    as integer xd
    as integer yd
    as ulong   c
end type

dim shared as RECTANGLE rec1,rec2
dim shared as integer collision

rec1.x = 10
rec1.y = 10
rec1.w = 150
rec1.h = 150
rec1.xd = -1
rec1.yd = 1
rec1.c  = rgb(255,100,100)

rec2.x = 320
rec2.y = 240
rec2.w = 200
rec2.h = 200
rec2.xd = 1
rec2.yd = -1
rec2.c  = rgb(100,255,100)

function spriteCollision(s1 as RECTANGLE,s2 as RECTANGLE) as integer
    dim as integer hit
    hit = 0
    'top/left corner
    if s1.x > s2.x and s1.x < (s2.x+s2.w) then
        if s1.y > s2.y and s1.y < (s2.y+s2.h) then
            hit = hit or 1
        end if
    end if
    'top/right corner
    if s1.x+s1.w > s2.x and s1.x+s1.w < (s2.x+s2.w) then
        if s1.y > s2.y and s1.y < (s2.y+s2.h) then
            hit = hit or 2
        end if
    end if
    'bottom/left corner
    if s1.x > s2.x and s1.x < (s2.x+s2.w) then
        if s1.y+s1.h > s2.y and s1.y+s1.h < (s2.y+s2.h) then
            hit = hit or 4
        end if
    end if
    'bottom/right corner
    if s1.x+s1.w > s2.x and s1.x+s1.w < (s2.x+s2.w) then
        if s1.y+s1.h > s2.y and s1.y+s1.h < (s2.y+s2.h) then
            hit = hit or 8
        end if
    end if
    return hit
end function

sub moveRectangle(rec as RECTANGLE)
    rec.x = rec.x + rec.xd
    rec.y = rec.y + rec.yd
    'check for border collision
    if rec.x + rec.w > SCRW or rec.x < 0 or rec.y+rec.h > SCRH or rec.y<0 then
        rec.x = rec.x - rec.xd  'undo move
        rec.y = rec.y - rec.yd
        rec.xd = int(rnd(1)*3)-1
        rec.yd = int(rnd(1)*3)-1
        while rec.xd = 0 and rec.yd = 0
            rec.xd = int(rnd(1)*3)-1
            rec.yd = int(rnd(1)*3)-1
        wend
    end if
end sub


sub update()
    dim as integer hit = 0
    screenlock
    cls
    'draw rectangles
    line (rec1.x,rec1.y)-(rec1.x+rec1.w,rec1.y+rec1.h),rec1.c,b
    line (rec2.x,rec2.y)-(rec2.x+rec2.w,rec2.y+rec2.h),rec2.c,b
    'move rectangles
    moveRectangle(rec1)
    moveRectangle(rec2)
    hit = spriteCollision(rec1,rec2)
    print hit
    print rec1.xd,rec1.yd
    screenunlock
    if hit<>0 then sleep
end sub


do
    update

    sleep 10
loop until multikey(&H01)

leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Need help with 2d collision ASAP

Post by leopardpm »

datwill310 wrote:
leopardpm wrote:how to find the angle between two points? SLOPE
What is meant by "calculate slope"? Is it like finding the gradient? Would that alone work? It just tells me how steep our character has entered into the entity, not the direction definitively, e.g. if gradient is shallow (if we are defining slope from origin of collision box and up side), then that could mean either up or right side esp. if character position is closer to the right edge.
Wiki: https://en.wikipedia.org/wiki/Slope

Basically, the change in Y over the change in X so:

slope M = (x1-x2)/(y1-y2)

I believe that returns the angle in radians... possibly, have forgotten
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

leopardpm wrote:
datwill310 wrote:
leopardpm wrote:how to find the angle between two points? SLOPE
What is meant by "calculate slope"? Is it like finding the gradient? Would that alone work? It just tells me how steep our character has entered into the entity, not the direction definitively, e.g. if gradient is shallow (if we are defining slope from origin of collision box and up side), then that could mean either up or right side esp. if character position is closer to the right edge.
Wiki: https://en.wikipedia.org/wiki/Slope

Basically, the change in Y over the change in X so:

slope M = (x1-x2)/(y1-y2)

I believe that returns the angle in radians... possibly, have forgotten
I'm pretty sure that gives us the gradient of the line, I am unaware of angles returned by that equation change in y over change in x. However, I'll grant that some theta stuff is going on with the linear line and and x-axis to produce the angle theta (gradient = tan(theta), you could probably rearrange this formula to get theta). As far as I can tell though, it still wont definitively state direction because it doesn't root itself to the previous position. Why calculating that angle would work is because it defines itself in terms of the character's previous position.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Need help with 2d collision ASAP

Post by leopardpm »

the direction can be determined by a combination of looking at the gradient AND its sign (+ or -) for both the top and bottom of the formula.

write a little test program with the mouse point as one point and screen center as the other point.. print out the gradient (my 'slope') and the sign of the delta x and sign of the delta y... then you can easily see how to deal with it. I always do things by trial and error, my maths memory being very very old and crusty... am at work now so can't really whip out FB and type it up...
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: Need help with 2d collision ASAP

Post by MrSwiss »

Sorry, to butt in but, the quoted function of *m* is different, than on Wikipedia:

m = (y2 - y1) / (x2 - x1)
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

MrSwiss wrote:Sorry, to butt in but, the quoted function of *m* is different, than on Wikipedia:

m = (y2 - y1) / (x2 - x1)
Also, the page states that:

m = tan(θ)

Where θ is the angle defined by the x axis and linear line drawn on the Cartesian plane.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Need help with 2d collision ASAP

Post by leopardpm »

MrSwiss wrote:Sorry, to butt in but, the quoted function of *m* is different, than on Wikipedia:

m = (y2 - y1) / (x2 - x1)
I told ya I was old n crusty, don't I get a break? lol... never trust code or logic from an old n crusty man
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Need help with 2d collision ASAP

Post by BasicCoder2 »

Here you can move the red rectangle around using the arrow keys while the values are printed.
The direction of the red rectangle is given by rec1.xd and rec1.yd so if it is moving from the left xd=1 and yd=0 and if moving down xd=0 and yd=1.
The angle is between the centroids of the rectangles.

Code: Select all

'some useful defines
Const Pi = 4 * Atn(1)
Dim Shared As single TwoPi = 8 * Atn(1)
Dim Shared As single RtoD = 180 / Pi   ' radians * RtoD = degrees
Dim Shared As single DtoR = Pi / 180   ' degrees * DtoR = radians

const SCRW = 640
const SCRH = 480
screenres SCRW,SCRH,32

type RECTANGLE
    as integer x
    as integer y
    as integer w
    as integer h
    as integer xd
    as integer yd
    as single  xc   'centroid of rectangle
    as single  yc
    as ulong   c
end type

dim shared as RECTANGLE rec1,rec2
dim shared as integer collision

rec1.x = 10
rec1.y = 10
rec1.w = 150
rec1.h = 150
rec1.xd = -1
rec1.yd = 1
rec1.c  = rgb(255,100,100)

rec2.x = 320
rec2.y = 240
rec2.w = 200
rec2.h = 200
rec2.xd = 0
rec2.yd = 0
rec2.c  = rgb(100,255,100)

function spriteCollision(s1 as RECTANGLE,s2 as RECTANGLE) as integer
    dim as integer hit
    hit = 0
    'top/left corner
    if s1.x > s2.x and s1.x < (s2.x+s2.w) then
        if s1.y > s2.y and s1.y < (s2.y+s2.h) then
            hit = hit or 1
        end if
    end if
    'top/right corner
    if s1.x+s1.w > s2.x and s1.x+s1.w < (s2.x+s2.w) then
        if s1.y > s2.y and s1.y < (s2.y+s2.h) then
            hit = hit or 2
        end if
    end if
    'bottom/left corner
    if s1.x > s2.x and s1.x < (s2.x+s2.w) then
        if s1.y+s1.h > s2.y and s1.y+s1.h < (s2.y+s2.h) then
            hit = hit or 4
        end if
    end if
    'bottom/right corner
    if s1.x+s1.w > s2.x and s1.x+s1.w < (s2.x+s2.w) then
        if s1.y+s1.h > s2.y and s1.y+s1.h < (s2.y+s2.h) then
            hit = hit or 8
        end if
    end if
    return hit
end function

sub moveRectangle(rec as RECTANGLE)
    rec.x = rec.x + rec.xd
    rec.y = rec.y + rec.yd
    'check for border collision
    if rec.x + rec.w > SCRW or rec.x < 0 or rec.y+rec.h > SCRH or rec.y<0 then
        rec.x = rec.x - rec.xd  'undo move
        rec.y = rec.y - rec.yd
    end if
end sub


sub update()
    dim as integer hit = 0
    dim as single angle,xx,yy
    screenlock
    cls
    'draw rectangles
    line (rec1.x,rec1.y)-(rec1.x+rec1.w,rec1.y+rec1.h),rec1.c,b
    line (rec2.x,rec2.y)-(rec2.x+rec2.w,rec2.y+rec2.h),rec2.c,b
    'move rectangles
    moveRectangle(rec1)
    moveRectangle(rec2)
    hit = spriteCollision(rec1,rec2)
    print hit
    print rec1.xd,rec1.yd
    rec1.xc = rec1.x+(rec1.w)/2
    rec1.yc = rec1.y+(rec1.h)/2
    rec2.xc = rec2.x+(rec2.w)/2
    rec2.yc = rec2.y+(rec2.h)/2
    line (rec1.xc,rec1.yc)-(rec2.xc,rec2.yc),rgb(255,255,0)
    xx = rec1.xc-rec2.xc
    yy = rec1.yc-rec2.yc
    angle = RtoD*(atan2(yy,xx))+180
    print angle
    screenunlock
end sub

do
    update
    'ARROW KEYS
    rec1.xd = 0
    rec1.yd = 0
    If MultiKey(&H4B)  Then rec1.xd = - 1:rec1.yd =  0
    If MultiKey(&H4D)  Then rec1.xd = + 1:rec1.yd =  0
    If MultiKey(&H48)  Then rec1.xd =   0:rec1.yd = -1
    If MultiKey(&H50)  Then rec1.xd =   0:rec1.yd = +1
    sleep 10
loop until multikey(&H01)

leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Need help with 2d collision ASAP

Post by leopardpm »

playing with your demo makes me think that a line-line intersection test, using each of the sides of the rectangle and the line formed between the two objects would give the direction (Top, Bottom, Left, RIght) pretty easy...

i luv your little demos, BC
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

BasicCoder2 wrote:Here you can move the red rectangle around using the arrow keys while the values are printed.
The direction of the red rectangle is given by rec1.xd and rec1.yd so if it is moving from the left xd=1 and yd=0 and if moving down xd=0 and yd=1.
The angle is between the centroids of the rectangles.
Thanks for the example! As leopard says;
leopardpm wrote:playing with your demo makes me think that a line-line intersection test, using each of the sides of the rectangle and the line formed between the two objects would give the direction (Top, Bottom, Left, RIght) pretty easy...

i luv your little demos, BC
The trick would be drawing the line relative to the upper left corner of the moving square so I can compare positional data easier. I'll see if I can adapt the program.

Thanks for all the help guys. This gradient method seems a lot simpler than the method I was getting to, and I should learn to be a bit more humble when asking for help ;).

Who knew: maths is actually useful. I've got a maths exam in a few days actually. What a coincidence :D
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

I have implemented your code into the engine, BasicCoder2 ;) things are working great! There's only one issue which occurs when walking straight to a platform: it appears our character likes to teleport onto the tops of platforms at the moment ;) but once I get that fixed, collision should, for now, be an issue no longer!
Have given credit in a readme file of the game. I think it is only fair, no? ;)
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

BasicCoder2 wrote:The angle is between the centroids of the rectangles.
Btw, does it have to be the centre points of the sprites, or can it be say from the UL points on both sprites?
Post Reply