Archived

This topic is now archived and is closed to further replies.

2D Collision Detection Problems!!!

This topic is 4958 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Okay, here''s the dillio: I''ve been working on an oldschool 2D sidescroller engine for a few months now, and most of it is ready to go, but i can''t FOR THE LIFE OF ME figure out a good way to do collision CORRECTION. I can detect collisions, but I haven''t been able to correct them in a reasonable way. This has been driving me crazy, because I know a million and one ways to find out things have collided, but I can''t fix them. I feel pretty stupid because I know it must be simple (because people have been doing it forever), but no one seems to write specifically articles specifically on correcting collisions. If anyone can give me any help/advice/resources/simple code/point me in the right direction, I would be extremely thankful. BTW, I''m dealing with collision correction in a simple Super Mario Bros type game--I just want simple things to happen, like have the characters be able to land on top of bricks or knock coins out of them by hitting them from the bottom. Thank you in advance, Steve

Share this post


Link to post
Share on other sites
It depends what types of collision detection you are using. Rectangles? Circles? Polygons?

If it''s rectangles, it''s a peice of cake. If moving left, get the left most side of the character (charXLeft), and the right most side of the solid object(objXRight. objXRight-charXLeft gives you the distane to move the character to the right to correct the collision.

When using circles or polygons it becomes mroe advanced, but the basic principle is the same. You simply find the distance the character has intersected the geometry by and move said character said distance away from the collision.

Share this post


Link to post
Share on other sites
If you have more complex models, ( a plane with a nose and 2 wings) and don''t want an oversized rectangle, divide the plane into 4 sections: Body sqaure, Wing1 Square, Wing2 Square, and Nose Square. If projectiles only come from one direction, all the better. You end up need to check only between 7 xy positionsto check for a collosion.

-----------------------------
Jammer
Jammer211@comcast.net
http://www.wconline.org : Your Warcraft Source
http://www.fark.com : Laugh, Cry, Photoshop
http://www.natural-selection.org : Online FPS RTS Gaming for Half-Life

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Are you collision testing before or after you move the object?

ie Mario is jumping, will this upward movement cause a collision?
if so
is he jumping towards a moveable object?
if not then stop him
if so then move the object, then move him..

Maybe I have over-simplified ... maybe not...
J.

Share this post


Link to post
Share on other sites
I''m sorry I didn''t really clarify the problem I''ve been having:
Lets say a character is approahing an object diagonally; jumping at a brick from the right, for instance. How do I determine whether the character hits the right side of the brick or comes up from underneath it. This is important because I would like an action to be triggered only if the brick is hit from the bottom. Also, if this were to occur during the game (of course it will), how will I be able to figure out which side to move the character to, the bottom or the right?

Also, I would prefer the simplest solution possible, which implies bounding boxes, but I can''t figure out how to implement them for this.

Thanks,
-Steve

Share this post


Link to post
Share on other sites
I have exactly the same problem you''ve got Smatthew. Unfortunately I haven''t figured it out yet either. I wouldn''t have thought a simple 2D collision check would cause me such a headache.
Are you using a tile based world (2D array of tiles?) or polygons.
I''m using a combination of both and I initially did it like this. I use a bouding rectangle on the character for collisions.
Work out the direction the player is heading. ie. up and left, down and right etc.
If it''s down and right for eg. I use the right and bottom lines of the rectangle for collision checking. If the right line hits a tile, I move the character to the left of that tile. Same deal with the bottom line except you move it above the tile.
This seemed like an easy solution but it still has the same problem you mentioned about landing diagonally on something and whether or not you landed on it or hit it from the side.
The problem is that I''m checking with two lines but they share a common point which can''t be determined as being either one or the other.
I''m going to try using line intersections instead. So for the above collision check, you take the bottom right point and cast a ray out in the direction and length of its velocity vector. Then just get the two lines of the tiles it can possibly intersect and check which one it collides with. You then know whether you landed on top or to the side of a tile.
I only just thought of that then and I think I''ve worked out my own problem. Sweeet. I''ve been thinking about this problem for days and it suddenly just popped into my head. The power of writing out a problem hey.
Once I''ve coded it up, I''ll post it for you Smathew. It should actually be pretty simple.
Jules.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you want to collision test for your ''dude'' jumping up to cause the desired action, and sideways causing the undesired action...

a) test for the greater collision (ie any collision)
if (player.left > object.right
|| player.right < object.right
|| player.top > object.bottom
|| player.bottom < object.top) return(0);// no collision
else ...
b) test if player is moving in an upwards direction
obviously if the player is moving downwards ... he is not moving up, you just have to decide at what angle the collision occurs, like... if (player.velY < -(ABS(player.velX)))

OR you could first test if player has collided with the object then test if player has collided with smaller ''hit zone'' located in the bottom center of the object ... keep in mind that if the player can move a distance greater than the distance from the object top or sides you may have problems...

I have assumed you are in c/c++ ...
j.
aka jetset33@shaw.ca

Share this post


Link to post
Share on other sites
One method of testing ahead is to cast a ray ahead of the moving character. This done _before_ any move. How do you store the background information? Tiles or objects??

ZoomBoy
Developing a iso-tile 2D RPG with skills, weapons, and adventure. See my old Hex-Tile RPG GAME, character editor, diary, 3D Art resources at Check out my web-site

Share this post


Link to post
Share on other sites
Well you might be able to modify this code to check for which side the player hits it from (since I''ve already divided it into up, down, left, and right). It''s simple collision code for a rectangle, assuming you know the x and y positions of both objects involved.


  
bool Collision(GLfloat x1, GLfloat y1, GLfloat x2, GLfloat y2, GLfloat x2right, GLfloat x2left, GLfloat y2up, GLfloat y2down)
{

if (x1 < x2 + x2right && x1 > x2 - x2left && y1 < y2 + y2up && y1 > y2 - y2down)
{
return TRUE;
}
else
{
return FALSE;
}
}

Share this post


Link to post
Share on other sites
Yeah, Joolean knows exactly what problem I'm having. One of the techniques I have tried involved a little bit of raycasting, but it quickly became a big messy nitemare, so I was wondering if there was something simpler I was missing. Also, my engine will be completely tile based, so another problem I was running into was determining what order I should correct the collisions. This is something I had not anticipated, but when you have a sprite flying at a wall of bricks (each brick is a tile, so they have to be tested separatly), it was hard to figure out which brick the sprite was hitting. For instance, if a character is moving diagonally toward a wall of bricks, within any individual frame it can intersect more than one brick, but logically, it would hit the closest one and never make contact with any of the others. If anyone has any pointers or would like to share info about similar problems, please do.

-Steve

[edited by - Smatthew on August 28, 2002 8:34:01 PM]

Share this post


Link to post
Share on other sites
Why not just check each side seperately? That''s how I do collision in my game, and it actually simplified it (since you only have to check the right-side, if you are moving right, ect).
For example,
if(char_top < box_bottom)
then box & character collided (box_bottom-char_top) pixels.
if(char_right > box_left)
then it was the horizontal side, which went over by (char_right-box_left)

Or am I way off here? Hope not..

Jiia

Share this post


Link to post
Share on other sites
Most of what everyone has said is exactly how I started off but then you hit the problem Smatthew has whereby you don''t know which side of a tile you hit. It''s not as easy as simply checking the side of the direction you''re heading in because you can head in two directions at once. You can''t check the vertical side before the horizontal side and vice versa cos you run into the same problem either way.
I''m pretty sure I''ve got it sussed Smatthew but it does involve the line collision check plus a combination of other checks. It''s possible there may be a simple algorithm which, given two rectangles and a vector, can tell you which side of the rectangle it hit, but I don''t know of it. You could possibly ask in the maths section of this forum.
The other problem you mentioned is how to check against multiple tiles cos depending on your sprites bounding box, you could intersect with more than one. I do it like this.
Take this simple map as example.
O = empty space.
X = block
P = the sprite''s bounding box.

OOOO
OOPX
OOPX
OOOX
XXXX

This uses the specific example that we''re heading down and to the right:
Get the direction the sprites heading. down/right.
Do the ray casting bit to determine whether we hit on top of or to the side of a tile.
If we hit to the side of the tile, which we will have in this case, then move it to the left of the tile.
Now we know that the sprite is in the right position horizontally, so we have to then check the vertical. And all you need to do is a standard tile check. If there''s a tile underneath, move the sprite on top of it.
To work out which tiles you could collide with, you get the two points that make up the bottom line. P1 = the left point and P2 = the right point. Work out which tiles are at these points and then check against all the tiles between in a loop and see if any are blocks.
It''s very simple on the surface but like you said, the implementation could get messy. Especially determining which lines to check against.
I''m going to code it up today anyway and if it works, I''ll post the code.
Jules.

Share this post


Link to post
Share on other sites
Hey, I have been TRYING, unsuccesfully, to make that kind of a game engine. I would like to know what programming language it is in, and if I cn have a copy of it when you make it?

rpetz286
Heiroglyphics Entertainment

Share this post


Link to post
Share on other sites
I fail to see why this is difficult, when are you collision testing? If before you move an object, since you can only move one at a time, you test to see if this will cause a collision, if it doesn''t then just move it, if it does then look deeper ...

Maybe you should post some source so we can straighten it out ...

j.

return(0);

Share this post


Link to post
Share on other sites
Smatthew: I ran into the same problem in my breakout-clone, the way I did it was simply to take all the tiles that DO intersect with the ray, then run distance tests on all of the matches and pick the shortest distance from the object. That will logically be the cell the object hits.

Works for me

ByteMe95::~ByteMe95()
My S(h)ite

Share this post


Link to post
Share on other sites
I wrote a small thing a long time ago - it worked the way ByteMe25 mentions.
That does seem to work, but it means some line collision and ray casting.

Put a little more effort in and you can figure out which SIDE of the object the ray hits

The whole problem is not as easy as it looks, but ByteMe25''s method does seem to work well enough to determine :
1) Which tile was actually collided (by distance from starting point of ray cast)
2) Which side of the object was collided (line collision test by ray cast with bounding box of object - the closest collision point on a line means that line (side) of the object was collided ''first'')

Share this post


Link to post
Share on other sites
It seems a lot of people think that just knowing that two sprites have collided and "fixing" the collision is good enough, but Im not clear on how you want me to "fix" it. When an object hits something perfectly horizontally or vertically, this is fine, but if its moving on an angle, the difficulty is in determining WHICH side it is actually hitting.

To joolean: If Im not mistaken, there is a small flaw in your explaination for collision detection against multiple tiles is that it doesnt take into account the time of the collision. The problem is that, from a global sense, the sprite is colliding with one big wall. But when it comes time to check for the collision, you look at each brick individually. The sprite may collide with two separate bricks in that wall, but to someone who isnt writing code, its just hitting one. The first brick it hits would stop the sprite and keep it from hitting the second one. if this was a horizontal wall, then it would be possible that the object hits the first brick horizontally, but then a second one vertically--or so our code thinks. If we check the second brick before the first, the object's horizontal velocity will be zeroed, the object will be moved left or right, then it will collide with the the first brick, zeroing the vertial velocity and shifting it up or down. Hard to explain, but the effect kills the realism of the collision detection.

robp286: Sure, if you want the engine I'll post it. The only thing I'd be cautious of is that its gonna be a "work in progress", not because im gonna post it unfinished, but because i'll probably have forgotten something and I'll be changing it frequently when Im working on a real game.

cultofpurplecabbage: the complexity of this problem comes in when you have to deal with diagonal motion. You say to "just move it" when it collides, but Im having trouble figuring out which way it should be moved.

ByteMe95 & Bwuce_Wee: When I implemented raycasting for the problem, I was tryig to keep track of collision times (a decimal between 0.0 and 1.0) so that i could first make a list of the objects something was colliding with, then go through them from lowest to greatest time to see which one to correct first, but it got hairy. Maybe I should go back to that system and try organizing it differently.

-Steve

[edited by - Smatthew on August 29, 2002 9:13:12 PM]

Share this post


Link to post
Share on other sites
If you just need to know which side the object hit first when 2 directions hit at once, just use the one that is overlapped the most. It will be the one that hit first. If they are both the same, then it hit perfectly diagnal.

I''m not sure what you mean by "fixing" it. If you mean moving the opposite object over that much, then that is just the distance the moving object moved.

Share this post


Link to post
Share on other sites
Hmmm....I think Jiia just gave me the solution I was looking for. I''ll try it out and see if it works the way I need it to. If not, back to the drawing board. Either way, keep the input coming--and thank you all for your help so far.

-Steve

Share this post


Link to post
Share on other sites
Just determining which side is overlapping the most does not tell you which side it hit first. It''s utterly dependent on your velocity. You could be flying totally horizontal and end up with a collision equal on both sides or on one side more than the other.
I sort of understand what you''re saying Smatthew, but it''s not the case. The only problem is the corner point that''s colliding because it shares a vertical and horizontal line. If it wasn''t for this point, you could simply do a vertical and horizontal tile check. So you cast a ray from this point in the direction you''re heading and check it against the lines it can hit from your tiles.

eg.
O=EMPTY SPACE
X=BLOCKS
P=PLAYER

OOOO
OOPX
OOPX
XXXX

Player is heading down and to the right.
We''re casting a line from the right corner on a down and right vector. Therefore the lines I need to check against are:
The left side of tile (4,3) and the top side of tile (3, 4).
So we check against these lines and lets say we intersect the line from tile (4,3). We know it''s vertical so we move our sprite to the left of it. We don''t zero out the y velocity.
Then we do a tile check on the bottom line. If we detect a collision, which we will, then we simply move the sprite to the top of the tile. Doing the raycast negates the need to check a particular side because it''s already been adjusted for.
Now in the case like this:

OOPX
OOPO
OOOO
XXXX

where we''re still heading down and right but our ray cast won''t detect a collision with anything, you simply do a horizontal and vertical tile check. Order of precedence doesn''t matter because the corner point isn''t hitting anything. In this case, we''d detect a hit with tile (4,0) in our side check so just move the sprite to the left of that tile.
The intricacies of it differ I think to the way ByteMe95 did it but either way, I don''t think you can escape using a ray cast to determine which side of a tile it hit. Raycasting will also stop your sprite from going straight through something if its velocity is greater than the width of a tile.
Jules.

Share this post


Link to post
Share on other sites
This might not help, and it''s been like 100 yrs since I played Super Mario, but...

I seem to remember that as long as I was moving in an upward motion, the block would break even if I''m only hitting the corner. As long as my horizontal position was under the block even a little, it counted as a bottom collision.

Also, when moving in a downward direction, it seemed like I would land on a platform as long as my horizontal position was past the edge of it even a little. Again, it didn''t matter that it was on a corner.

Maybe you have to prioritize your checks. If moving upward and you collide with a block, check for a bottom collision first, then a side collision. If moving downward, check for a top collision first, then side. If you hit a corner, you''re always checking for top/bottom first. If you collided with the block, but it wasn''t a top/bottom collision, it was a side collision. Base the action you take on the type of collision (top/bottom/left/right).

Share this post


Link to post
Share on other sites
ray casting is mostly a fancy word. it''s like doing collision detection using segmemts (two end points), but with a ray (pos, dir, with possibly a maximum length), so only slightly different.

You can extend the segment intersection test to do swept volumes collision tests, which is another fancy word, that''s basically your normal collision stuff, but with also using the direction and speed of memvent in the collision test to get more accurate results. Obviouly, the tests become more complicated, since you through some other stuff in the calculations.

there are advantages using, say a segment for a travelling bullet, so that you can catch events when the bullet goes so fast it teleports through objects from one frame to another. A segments would detect that better.

For example, for a travelling bullet the ray-cast in collision detection can be setup like this.

Ray.Pos = Bullet.Position
Ray.Dir = Bullet.Direction;
Ray.MaxLength = Bullet.Speed;

or

Segment.P = Bullet.Position;
Segment.Q = Bullet.Position + Bullet.Direction * Bullet.Speed;

then you do

if (Intersect(Ray, Enemy.BoundingBox)) Enemy.Destroy();

or

if (Intersect(Segment, Enemy.BoundingBox)) Enemy.Destroy();

Share this post


Link to post
Share on other sites
So did you come up with solution to your problem? I''m having the same problem and would love to see some example code that works properly.

Share this post


Link to post
Share on other sites