Jump to content

  • Log In with Google      Sign In   
  • Create Account

Handling Collisions Between Rectangles


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 destructivArts   Members   -  Reputation: 205

Like
0Likes
Like

Posted 20 May 2012 - 02:48 PM

Hey Guys!
I've posted a lot on here about this game, and I'm starting to feel like I might have to give this forum credit for large parts of the game.
And now I need help again.
This whole post has to do with collisions.

First/Second problem:
Each object in my game has an array of rectangles that encase the sides of the object. (ie. top, left, right, bottom) This unfortunately results in the side boxes being 'activated' when the player hits a platform because they overlap the bottom box. Is this an effective arrangement for collision detection? I have seen methods that used circles, and that seemed very good, but I'm making a side scroller, and I feel like the way they handled the collisions would result in the player sliding down off a flat platform because of a round collision circle. Has anyone heard of other collision detection shape arrangements? And if this is one of the better methods, how can I prevent the overlap of boxes? (This seems like it should be fairly obvious but I've been trying for a while and I can't seem to figure it out.)

Third problem:
I have a collision checker method in my game that effectively checks the collisions between two objects. (Two nested for loops check each of the player's boxes against each of object b's boxes.) After the check, I have the player respond to the collisions. The problem however, lies in his speed. Because in one frame he could be moving up to 30 pixels (his terminal velocity), he can pass through an object and never have it be detected. What happens more often is that he ends up half in half out of a platform, activating 3 of his collision boxes. I've tried telling the player to automatically move up to rest on the platform, but that results in the player constantly jumping between a point inside the platform, and the point that I want him to be at. Any suggestions to solve this?

Any help is greatly appreciated.
Thanks for all the help so far,
Peter
-------------------------------------
"Other than that, I have no opinion."
My Blog - Check it Out

Sponsor:

#2 Moonkis   Members   -  Reputation: 273

Like
1Likes
Like

Posted 20 May 2012 - 03:59 PM

Now I'm no expert in collision-detection but wouldn't it suffice with only one box for the platform or is the platform in an irregular shape? I.E Not a rectangle type?
Also your problem could be solved by a simple X and Y coordinate check when you do your collision?

If the Players X is in between the platforms edges it's likely the player is colliding either the top or bottom hit-box ( If both top and bottom triggers ( Which they shouldn't according to your description, check if players Y is above or below the platform to determine if it was the hit-box of the bottom or top was triggered. ). If the player y coordinate is not between the edges it's most likely a collision of either edges.

Something like that?

Third problem:


I have a collision checker method in my game that effectively checks the collisions between two objects. (Two nested for loops check each of the player's boxes against each of object b's boxes.) After the check, I have the player respond to the collisions. The problem however, lies in his speed. Because in one frame he could be moving up to 30 pixels (his terminal velocity), he can pass through an object and never have it be detected. What happens more often is that he ends up half in half out of a platform, activating 3 of his collision boxes. I've tried telling the player to automatically move up to rest on the platform, but that results in the player constantly jumping between a point inside the platform, and the point that I want him to be at. Any suggestions to solve this?


I have never used this method before so I don't know if it works this way but couldn't you use a line collision check from point A where he starts and point B where he is after the movement, if the line collides you know you have a collision in the movement path move the player to that location and if you want check the collision as normal.

Edited by Moonkis, 20 May 2012 - 04:01 PM.


#3 destructivArts   Members   -  Reputation: 205

Like
0Likes
Like

Posted 22 May 2012 - 01:59 PM

wouldn't it suffice with only one box for the platform

Sorry, that's what I meant. Every object has an array for rectangular bounding boxes. The platforms only have one bounding box. The player uses four so I can tell which side is being hit.

And for your second solution:
So are you saying have a loop that translates the players bounding boxes and checks at each step?
I'd never thought of that but that would be more effective than moving the player and then checking for collisions and shifting backwards to find the right spot.

Thanks for your help!
Peter
-------------------------------------
"Other than that, I have no opinion."
My Blog - Check it Out

#4 freakchild   Members   -  Reputation: 557

Like
1Likes
Like

Posted 22 May 2012 - 04:38 PM

Using a circle vs a box, yes if that is programmed correctly it should result in a player sliding off the edge of a box. There are games where this is a very desired effect though.

Unless there is some absolute need to use four bounding boxes for your player, I would reduce this to one and solve the idea you need to know which side is being hit by another method. It will at least be easier to debug with one box and get all your box collision working very robustly that way first. You can scale up to 4 if you really need that when all is good.

I’ve done pure box collision like this and I’ve done it both badly and very accurately with predictive as well as moving/overlap then rewind methods…and a mixture of them all.

My preferred simple method checks for overlap first (after the box has moved) between my Box A and other box Box B. If there is no overlap, then there is no collision…nothing more to do.

If there is overlap though, I know I should be spending the extra time doing more detailed calculations. As such, I move Box A back to where it was and cast lines out from the corners in the direction of movement, sized by the amount of movement in order to see which one hits which side if Box B first.

I don’t do unnecessary calculations, so if I am moving down and right I only cast lines out (in the direction of movement) from the top-right, bottom-right, and bottom-left corners of the box A and I only test against the top and left sides of Box B.

I would also focus on the bottom-right corner first because in theory, if that corner hits first then the others I don’t need to worry about because that was the ‘leading corner’. Testing the line from the bottom right corner of box A against the top and left sides of B tells me which side of Box B I hit (if any) and should slide along.

Again, note that I don’t test against the right and bottom sides of Box B in the moving down and right scenario. They are on the other side of the box so I can’t possibly hit them without hitting the near side first. I don’t cast lines from the top left corner of Box A for the same reason.

If the leading corner did not hit the top or left side of box B, I then check to see if the other two corners that might have. This would occur if bottom right leading corner of Box A might have gone below the left side of Box B (missing the side) or past the right side of the top of Box B (again, missing that top side). It’s entirely possible for the non-leading corners to be the point of first contact so this is why you do this.

Note that using lines is effectively a ‘sweeping’ technique…you won’t miss collisions by moving past them if you only use lines, because you’re checking along the line of movement and will hit anything in the way. If you use the box overlap first as I suggested above, you may still get that problem though, which will arise if Box A moves past Box B entirely – there’ll be no overlap, so you’ll not bother doing the sweep.

In that case you could sweep a box over the entire region of movement…or just use a box that encompasses the start point of the box and the end point. I’ve also just used a bigger box for the overlap detection too and all that does is make sure I undertake the sweeping line tests when there might have been a collision.

You may find that you collide with multiple objects in all these scenarios, particularly those that involve some sweeping…so you have to find which is the nearest. A lazy way of doing this is of course to just test against them all and always keep the results of whatever the current nearest candidate is as you iterate through all possibilities.

The other thing to watch out for…boxes of different sizes. A large box can pass over a box of a smaller size without any corner intersections. This may show up as a potential collision when sweeping a box…but your more detailed line intersection tests may still fail. There are a number of solutions to this…an easy one involves doing line casting checks not from the corners, but from part way along the sides.

What you will see from above is that good collision detection usually involves a number of techniques mixed and matched.

#5 freakchild   Members   -  Reputation: 557

Like
1Likes
Like

Posted 22 May 2012 - 04:52 PM

Also...I've tried to give you a more or less complete solution there, but keeping it as simple as possible in explaining it. Those two goals sort of work against each other, so feel free to ask for clarification.

Also bear in mind many platformer collisions just don't use anything accurate (or don't need to). I once did a platformer almost exclusively using one point on the character for collision - generally between his feet but when moving...the front of the feet. I would support this with a point at the top of the head when jumping and if I knew I was walking against a wall, then I'd reach out beyond the feet...at least to a point representing the extremity of the character (but still out from the feet/along the floor).

#6 destructivArts   Members   -  Reputation: 205

Like
1Likes
Like

Posted 22 May 2012 - 07:35 PM

freakchild: Wow. Thats a lot to take in. Thank you for the advice. I still see one problem with your approach.

If there is no overlap, then there is no collision…nothing more to do.

This is part of the problem I was having. My character can move fast enough (downward) to move completely through a platform in one frame and it seems your method wouldn't check for that. I can always solve this by making all platforms have a minimum height equal to his terminal velocity... actually I think I'll go with that. I honestly just needed to talk that one out.

And your explanation was quite thorough.
Thank you so much for your help.
Peter
-------------------------------------
"Other than that, I have no opinion."
My Blog - Check it Out

#7 freakchild   Members   -  Reputation: 557

Like
0Likes
Like

Posted 23 May 2012 - 09:28 AM

Just to clarify, but this is why I went on to mention that there could still be a case where you miss a collision if you rely solely on checking for overlap...

If you use the box overlap first as I suggested above, you may still get that problem though, which will arise if Box A moves past Box B entirely – there’ll be no overlap, so you’ll not bother doing the sweep.


Sorry, those last seven words probably could have highlighted the issue further but hey you saw it yourself anyway. As you can see, the basic point is that if you rely on overlap alone as a means of determining if there was a collision then you do stand a chance of missing some.

I do explain a little about getting around this problem above, but today is a new day so I can maybe focus a little more on it.

One solution is that you can avoid this issue by not doing overlap checking. If you do the line of motion from corners tests alone then that shouldn't fail you at all because it checks the path of motion - anything in the way is thrown up as a potential collision without fail.

The reason most people don't do that though is because it can result in a lot of potential collisions that involve deeper and more expensive collision tests. This isn't really that expensive in a 2D box line vs line case to be honest, but even so I think it's better to prune out collisions via a broad phase collision pass anyway, which is really just pulling together a list of potential collisions using a less accurate/cheaper technique before you do the detailed work.

A reasonably accurate way of doing this is by sweeping the box volume along it's path of motion. This sounds complex, but really to obtain this volume you just consider the start location and the end location of the moving box and connect the two boxes together. In the case of a box moving down and right, it's shape would be defined by the top-left, top-right and bottom-left corners of the box when at the starting point and the top-right, bottom-right and bottom-left corners of the box when at the end point.

This gives you a six sided 2D object, which you can test for intersection against other objects to give you a pruned and very accurate list of potential collisions, which you then subject to further scrutiny with more detailed checks to find which ones you did actually hit and eventually...the one you hit first.

This is accurate, but I would recommend you use an even broader phase collision sweep just to keep things easier instead. Rather than establish a six-sided object then work with that, just derive your pruned list from the bounding box encompassing the start and the end boxes. In the down right moving example, the top left of this box would be the top left of the original collision box at it's start point and the bottom right of the new bounding box would be the bottom right of the original collision box at it's end point.

(side note: The description above is really a way of describing the geometry of the new box and not really an algorithm. Don't write a function to create the new box by considering the direction it was travelling to pinpoint the new top-left and bottom right. Yes, you could do that...but really it's best to write a general purpose function that creates a new box from the extents of two boxes regardless of where they are located. This is a 'best fit' algorithm which can be complex with other geometry but in the case of oriented boxes is actually very simple.)

This bigger box is less accurate than a true swept volume (the six sided object) because it covers a larger area. So you'll get a pruned list of potential collisions sampled from the same region some of which may not even represent a collision because they are 'off' the swept path. Generally, you'll get a longer list then...but the cost of obtaining this data will be a little cheaper than testing for intersections on a six-sided object and the code is easier and typically will be quicker.

Note that any broad phase pass does prune and offer a list of 'potential' collisions. As I hint at above...some will not actually be collisions, they'll just be pulled in via the broad phase pass. The key point...any broad phase pass is going to be inaccurate and subsequent tests or passes should be aware that some of the potential collisions are not that. Plan to discard these. All will have to be processed to find if they are a collision or not...and to find which one of them is the first collision.

Bear in mind that you could (if you wish) use this box based broad phase pass to get the least accurate list and then further prune that list via deriving the six sided object. It's not uncommon for collision detection functions to do this. I wouldn't recommend it for you, but at least you can if you want. I say it more to pass on some theory. You would generally do this sort of thing if your final intersection tests on your final pruned list are very expensive and you want to make sure you're spending your processing resources on the absolutely minimal set.

Either way, the above will solve the sweeping problem you saw. You can likely combine this with a first 'overlap' test because if that does get a positive, it will be your first potential collision. Detecting for overlap, then broad phasing and finding 0 other candidates would be an appropriate 'early out'...really you'd be saying 'I have found one collision in the easiest cheapest manner and I have proven nothing has been missed out, so I'm okay to rely on the overlap'.

If I were you, then if you are doing all this I would still focus on initial overlap and rewind/cast lines first before adding the broad phase in. Don't get me wrong...you will likely need the broad phase, but there's a logical sequence to follow in order to make all this easier to develop. Just make sure you consider the idea you're dealing with multiple objects, so you'll always want to be iterating through some list even if the first overlap test puts only one potential collision in that list. In that way, you're broad phase pass can just insert objects into the same list. Make sure your object to object collision tests are strong and detects the first point of collision between the two objects and make sure you can keep the results of that around, so you can compare with other objects in the list. You can optimize the memory wasted by keeping results around...by only keeping the most relevant one around, which is really a case of discarding anything other than what you know to be the nearest collision, which at any one time is the only candidate for the first collision (when iterating through many potentials).

I'll just add one more point too. What I've described here is really a test and rewind initially, with sweeping added - really it's now simple test, sweep/broad test then rewind and sweep forward with lines (based on a pruned list). Bear in mind that there is an alternative to sweeping forward...I have actually moved objects and then cast the lines backwards along the lines of motion in the past. It's really the same thing just in the other direction...but some people can find this convenient it depends on how they've set things up.

Edited by freakchild, 23 May 2012 - 10:06 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS