Need help with 2d collision ASAP

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

Need help with 2d collision ASAP

Post by datwill310 »

Hi all at the forum,

I'm currently very busy with programming a new game, all programmed in Free BASIC (except some of the actual libraries I use etc. :P). And have hit a dead-end concerning collision.

Our game is a 2D platformer. The .stg files (stage info) store a list of entities in the stage, and some other allocation info. From the data there, the game calculates the collision box (called "bones" in the code, and are stored as the two opposite points of a rectangle) which is used for collision, obviously ;).

I'm unable to even get my head around some concepts of collision, let alone program it to actuality.
I do understand the basics of collision: it is when the playable character hits an entity, or multiple entities. Then my code is supposed to respond to that. Finding out if our character is in an entity is not the issue:
it's figuring out from which side our character is colliding with an entity. That's the issue.

I require to know if our character is colliding with an entity from with the TOP, LEFT, BOTTOM, or RIGHT side for the physics, esp. with platforms: the character is supposed to respond differently depending on if they hit the TOP (stand on), LEFT (unable to move RIGHT), BOTTOM (hits head on platform, and falls down), or RIGHT (unable to move LEFT) side of an entity. With enemies, this at the moment is not so much of an issue, but I realise that we also require this info if we are to make our character "bounce" off of an enemy when they collide with one, should we choose to implement such physics.

I've got the physics working, would you believe it! It's just that darn collision that's been bugging me (read: me tearing my hair out, almost literally) since a few days.

What I'm asking for help with is this: the ideas behind identifying if our character has collided with the top, bottom, left, or right side of an entity.

1. I'm not really asking for help with code directly, i.e. you don't have to program the idea for me: it's just getting my head round it. If I could understand the process, I could implement it fine, is my reckoning. Also the fact that I would have to post >100K code on a public forum (probably less as only a small fraction of that is the actual game engine as it stands now): I am still unsure if I should keep the code for the game closed-source or not, and as the game has no official first version yet, I would prefer to keep my code off the web.
2. I would like to avoid relying on pre-made game engines or libraries as I have already programmed the framework for one (i.e. gravity is working, as is jumping, moving, and lot's more like loading, graphics effects, menus etc.).

OK, I'll perhaps need to tell you a few things about the way our character moves:

1. He does not move one pixel at a time. If that were the case, then collision would be a lot easier generally. But he does not :(.
2. All entities at the moment are oblongs; better definition: rectangles. Circular entities may be introduced, but they are not present right now.

If you need any other info, you can ask.

Thanks for your time.
Last edited by datwill310 on May 01, 2017 23:33, edited 2 times in total.
thesanman112
Posts: 538
Joined: Jul 15, 2005 4:13

Re: Need help with 2d collision ASAP

Post by thesanman112 »

if player doesn't move one pixel at a time then just add the actual movement to player before actually displaying it on screen and check for collision, like use

collision_result=0
if playerx+10>=collisionx and playerx-10<=collisionx then collision_result=1
...
...
...
do this will all axis available and it will check all around the player to check for collision.


collisionx will be what your checking player against...which you should narrow down quickly will a precheck of a specific area on the screen instead of having to check entire screen. the best way is to use predimensioned plots that are dimension as (x,y) and have it stored as either a collision posibble state or not collision possible state, like 0 or 1

what your looking to do is the heart of any interface engine...hence why some games work way better then others...
you want to be able to scan areas and check for collision fast, its hard to explain a good way for your program to check collision
without knowing how you handle the objects that collision can happen with.

a good starting point is to imagine if your player is actually bigger that it is by using < and > to allow some distance so you can scan faster...
the for/next loop can "step" by the same amount you allow between the < and >.

if players angle of collision is needed then obviously you will need a reference of how the object that its colliding with is set.
example....object if either horizontal or verticle...then check players angle against the object angle.

the angle formula of deflection is probably a math equation with PI...or negative/opposite of referenced angle of movement....
if not then assign a predefind deflection type...
if object is horizontal the deflection is left and right....or y...or negative current y movement..or *-1
if object is verticle the deflection is top and bottom....or x...or negative current x movement..or *-1
badidea
Posts: 2586
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Need help with 2d collision ASAP

Post by badidea »

If it is acceptable the represent your character and the enemies as circles, things are maybe easier.
Distance between them smaller then the two radii together? Then collision.
Next step, check if mostly above, below, left or right using dx and dy (where dx = player.x-enemy.x and dy=player.y-enemy.y).
Sign of dx determines left or right, sign of dy determines above of below.
If if can only be above, below, left or right then compare absolute values of dx and dy (|dx|, |dy|)
The exact angle and possible (bouncing) forces between them can be easily calculated with vector calculation, without the need to work with sin, cos, atan etc.
And if you have 100 enemies, you have to check collision against all of them every time, or do something complex/smart.
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

thesanman112 wrote:if player doesn't move one pixel at a time then just add the actual movement to player before actually displaying it on screen and check for collision, like use

collision_result=0
if playerx+10>=collisionx and playerx-10<=collisionx then collision_result=1
...
...
...
do this will all axis available and it will check all around the player to check for collision.


collisionx will be what your checking player against...which you should narrow down quickly will a precheck of a specific area on the screen instead of having to check entire screen. the best way is to use predimensioned plots that are dimension as (x,y) and have it stored as either a collision posibble state or not collision possible state, like 0 or 1
Thanks for your reply.
(Wow, I just realised, I think you added another paragraph or I just didn't read it! I'll reply to that in my next post after this one).

I don't exactly calculate movement before drawing, I draw FIRST. But it follows that control input is scanned, and our character moves, then collision is checked, before redrawing in the next iteration of the loop.

Your example is correct: by scanning each axis, or side, I should be able to detect it, right? Unfortunately, I have found one or two problems with using this: collision will work on a general scale, but still doesn't necessarily help me find the direction of collision definitively.
Note the ASCII diagrams ;)

Code: Select all

+--------------+
|              |
|              |
|              |
|              |
+--------------+
At the sides (|s and -s) we can definitely say that the character is colliding with the oblong to the right, or left etc.
HOWEVER, it's the CORNERS (+s) that get tricky!
Say our character is jumping in from the side into the corner of our entity. He could end up scanning as positive for TWO directions, for example:

Code: Select all

+----|-------------|----+
| C  |      T      |  C |
|----|-------------|----|
| L  |             |  R |
|    |             |    |
|----|-------------|----|
| C  |      B      |  C |
+----|-------------|----+
*Note: there are oblong areas because this accounts for the max amount our character can move into the entity, and not just one pixel.
T = we can definitely say he is colliding with TOP
R = definitely say he is colliding with RIGHT
B = colliding with BOTTOM
L = colliding with LEFT
C = annoying corners which could mean either of the two directions which overlap!
But because of how code executes, one direction will have priority over the other. For instance, if we scan for the top side FIRST, and our character is within the corner, it could return TOP, when really the character moved in from the LEFT! This could result in a situation where our character is supposed to have missed the platform, but then suddenly transports to the top of the platform because we scan for top first and apparently he came in through the top.
I am currently having such issues, and they are BAD, locking the scrolling engine, can't move etc. Idk why :/

One way I thought of conquering the corner problem was to record our character's previous position, and calculate from that.
From our previous example, we will know if our character is moving in from the LEFT because his previous position states that he is technically too far away to have landed on the platform (for instance, too far down and/or too far left).
But I am having issues with that :( I feel like this is an answer to the problem, but I can't get it to work and don't know the calculations I should make (I seem to be just calculating one of the axis for this movement, but to me now it makes sense that I should scan for both?). It's confusing me lol :(.
badidea wrote:If it is acceptable the represent your character and the enemies as circles, things are maybe easier.
I will bare in mind your reply if I will introduce circular entities. But as it stands now, all platforms are of an oblong form. To have circular collision boxes (lol did I really just write that :D) for such oblong-shaped entities wouldn't turn out so good :(. Soz about that dude I should have put that in my OP, I'll do it now.
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Need help with 2d collision ASAP

Post by BasicCoder2 »

In one game demo I used this to return which side was hit,

Code: Select all

function spriteCollision(s1 as SPRITE,s2 as SPRITE) 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
'example of hero jumping on top of mole enemy,

Code: Select all

    hit = spriteCollision(hero,mole)
    if hit<>0 then
        if hit = 4 or hit = 8 then  'test for bottom hit spots
            mole.alive = 0
        end if
    end if
However thinking about it now maybe a simple collision combined with comparing the positions of the two sprites should also tell you which side they collided.

I use this to test for overlap of rectangles.

Code: Select all

'========================================================================================
function testCollision(b1 as AGENT,b2 as AGENT) as boolean
    return b2.y < b1.y+b1.h and b2.y+b2.h > b1.y and b2.x < b1.x+b1.w and b2.x+b2.w > b1.x
end function
'=========================================================================================

.
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

thesanman112 wrote:what your looking to do is the heart of any interface engine...hence why some games work way better then others...
you want to be able to scan areas and check for collision fast, its hard to explain a good way for your program to check collision
without knowing how you handle the objects that collision can happen with.
OK, I'll try to cover in as much detail as possible, how my current system works:

For each entity in the stage, there is an element in the H_ENTITY internal object of the H_STAGE class: which stores all stage code. Here is the H_ENTITY class as it stands now (little snippets like this I wont mind posting):

Code: Select all

'the class used for the entities
type H_ENTITY
	as ushort entity_type
	as long x
	as long y
	as boolean bonesflag
	as fb.IMAGE ptr texture
	as long bones(3)
	'0 = x of ul
	'1 = y of ul
	'2 = x of lr
	'3 = y of lr
	as boolean hostile_flag
end type
entity_type stores the type of entity. This is basically an index which defines how entities are set-up in construction, how they are handled, if they have additional moving or AI etc.
x and y store the entity's position relative to the UL of the whole stage graphic.
bonesflag, if TRUE means that the entity can be collided with. If FALSE, the entity can be walked through.
texture is the image for the entity
hostile_flag states whether the entity can hurt you or not.
bones() is the array which is most important in collision. They define two points:
bones(0) = x, x of UL
bones(1) = y, y of UL
bones(2) = x+entity_width, x of LR
bones(3) = y+entity_height, y of LR
The width and height of an entity are defined by the texture dimensions. These bones are constantly updating through a method. They draw the collision rectangle around the entity. I intend to add a single pixel in the updating method to this size to make the game look a bit nicer during collision with a wall for instance. I am [trying to] doing this in the collision checking method at the moment, but I think it would be better if we did this in the bones updating method.
If there is anything else specific you would like to know, I'll get back to you.
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

BasicCoder2 wrote:In one game demo I used this to return which side was hit,
Thanks for your input. I will look over the code you have posted now.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Need help with 2d collision ASAP

Post by leopardpm »

for the direction, use the slope comparison method described above - it will basically tell you the angle between the two objects (you will still have to figure out what you want to happen at exactly 45 degrees though - your 'corner' issue) and from the angle you can figure out how to react.

One question: You stated first that you were just doing straight/fast rectangle collision checks... but then you specified that the entities were oblong (oval?)... do you want to check collisions based on the exact shape or just approximate with rectangles?
thesanman112
Posts: 538
Joined: Jul 15, 2005 4:13

Re: Need help with 2d collision ASAP

Post by thesanman112 »

FWIW, you should also be able to read the screen and check for collision around player....which is fairly easy in 2d...
thesanman112
Posts: 538
Joined: Jul 15, 2005 4:13

Re: Need help with 2d collision ASAP

Post by thesanman112 »

I believe qbasic preset(pixel_x,pixel_y) was the command.
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Need help with 2d collision ASAP

Post by leopardpm »

thesanman112 wrote:FWIW, you should also be able to read the screen and check for collision around player....which is fairly easy in 2d...
the command in FB is 'Point' which is itself very slow, and such perimeter checking is laboriously slow as well. Definitely do a basic rectangle check first, and if there is a rectangle collision then you can go ahead and do the pixel-perfect collision... saves ALOT of time/processing
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

(I will respond to in-coming posts).
BasicCoder2 wrote:In one game demo I used this to return which side was hit,
Forgive me for my noobish questions here, but...
I'm not sure if I understand how the code finds out where sprite one has collided with sprite two.

For instance, take the checking for the top/left corner:

Code: Select all

'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
AFAIK, this states that:
If sprite 1's x is within sprite 2's x range and if sprite 1's y is within sprite 2's y range, then denote that sprite 1 has collided with sprite 2 at the top left hand corner? But doesn't that just mean sprite 1 is overlapping sprite 2? And what about if sprite 1's x is outside of sprite 2's x range, but sprite 1's width means that it overlaps sprite 2?
Also, take bottom/left corner checking:

Code: Select all

'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
It states that:
If sprite 1's x is within sprite 2's x range and if sprite 1's lower-right y is within sprite 2's y range, then denote that sprite 1 has collided with sprite 2 at the bottom left hand corner?
I'm pretty sure I am understanding these calculations wrong in terms of their task to accomplish, as that does not find out if sprite 1 has collided with sprite 2's bottom left hand corner? It just says if all of sprite 1 is drawn within sprite 2, right?
But maybe the values combine. I see that you bitwise-or values to the return variable, so I am assuming different byte states denote which sides or corners or something?
But from your usage example (using = signs instead of ANDs), it suggests that this is not the case and the return value has to be a definite value:

Code: Select all

'example of hero jumping on top of mole enemy,
hit = spriteCollision(hero,mole)
if hit<>0 then
    if hit = 4 or hit = 8 then  'test for bottom hit spots
        mole.alive = 0
    end if
end if
So this means that, there are two possible values to denote bottom collision (in terms of sprite 1 landing on sprite 2)? But what if, say, 4 was returned and really sprite 1 didn't jump on sprite 2, but walked straight towards it from the left? That would return 4, am I right in thinking such?
datwill310
Posts: 355
Joined: May 29, 2015 20:37

Re: Need help with 2d collision ASAP

Post by datwill310 »

leopardpm wrote:for the direction, use the slope comparison method described above - it will basically tell you the angle between the two objects (you will still have to figure out what you want to happen at exactly 45 degrees though - your 'corner' issue) and from the angle you can figure out how to react.

One question: You stated first that you were just doing straight/fast rectangle collision checks... but then you specified that the entities were oblong (oval?)... do you want to check collisions based on the exact shape or just approximate with rectangles?
OH dear lol xD I got mixed up on the definition of "oblong" I thought it meant just rectangle. Sorry about that, I do mean flat rectangle collision.

Right now, pixel-perfect collision shouldn't be required. However, if there are other shapes involved (such as circles ;]), I will adopt other methods as well, such as the circle idea posted by badidea. As a rectangle collision box with a circular object = deceptive to the player ;).
EDIT: actually, since the character has a more rectangular shape, treating them as both circles wouldn't be a good idea. Maybe a mask is in order?

EDIT: just found this when Googling!:
http://dictionary.cambridge.org/dictionary/english/oblong wrote: a flat shape with four sides and four angles of 90° and opposite sides of equal length
Compare
square noun

US any object or shape that is longer than it is wide
I live in the UK, so I guess I didn't know oblong had such a broad definition xD
leopardpm
Posts: 1795
Joined: Feb 28, 2009 20:58

Re: Need help with 2d collision ASAP

Post by leopardpm »

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
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: Need help with 2d collision ASAP

Post by BasicCoder2 »

datwill310 wrote:Forgive me for my noobish questions here, but...
I'm not sure if I understand how the code finds out where sprite one has collided with sprite two.
The code was old and i haven't used it for some time so I will have to digest your question and reply later.
Just wrote this to try and implement my thoughts about using the simple overlap test and the check the spatial relationships between the two colliding rectangles. This compares top/left corners but you could compare the centroids or as suggested the angle between centroids.

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 rec(1 to 2)
dim shared as integer collision

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

rec(2).x = 320
rec(2).y = 240
rec(2).w = 150
rec(2).h = 90
rec(2).xd = 1
rec(2).yd = -1
rec(2).c  = rgb(100,255,100)


'========================================================================================
function testCollision(b1 as RECTANGLE,b2 as RECTANGLE) as boolean
    return b2.y < b1.y+b1.h and b2.y+b2.h > b1.y and b2.x < b1.x+b1.w and b2.x+b2.w > b1.x
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 moveRectangles()
    collision = 0
    for i as integer = 1 to 2
        moveRectangle(rec(i))
        'hit any other rectangle?
        for j as integer = 1 to 2
            if j<>i then
                if testCollision(rec(i),rec(j)) then
                    rec(i).x = rec(i).x - rec(i).xd  'undo move
                    rec(i).y = rec(i).y - rec(i).yd
                    rec(i).xd = int(rnd(1)*3)-1
                    rec(i).yd = int(rnd(1)*3)-1
                    while rec(i).xd = 0 and rec(i).yd = 0
                        rec(i).xd = int(rnd(1)*3)-1
                        rec(i).yd = int(rnd(1)*3)-1
                    wend 
                    screenunlock
                    locate 2,2
                    print "COLLISION"
                    if rec(1).x > rec(2).x then print "RED HIT RIGHT OF GREEN" else print "RED HIT LEFT SIDE OF GREEN"
                    if rec(1).y > rec(2).y then print "RED HIT BELOW GREEN" else print "RED HIT ABOVE GREEN"
                    print "HIT KEY TO CONTINUE..."
                    sleep
                    screenlock
                end if
            end if
        next j
    next i
end sub

sub drawRectangles()
    for i as integer = 1 to 2
        line (rec(i).x,rec(i).y)-(rec(i).x+rec(i).w,rec(i).y+rec(i).h),rec(i).c,bf
        line (rec(i).x,rec(i).y)-(rec(i).x+rec(i).w,rec(i).y+rec(i).h),rgb(0,0,0),b
    next i
end sub

sub update()
    screenlock
    cls
    drawRectangles()
    moveRectangles()
    screenunlock
end sub


do
    update

    sleep 10
loop until multikey(&H01)

Post Reply