2d rectangle collision response

BlitzMax Forums/BlitzMax Programming/2d rectangle collision response

Warner(Posted 2010) [#1]
I'm working on a collision system, which tries to avoid that two rectangles overlap.
Both rectangles can be rotated, and they are not square, although I'm thinking of using formats in the order of 32: 32x32, 64x32, 64x64 etc.

The method I'm using now is: if a rectangle moves, the movement is done one pixel at a time in a loop. Before each step, I look ahead if an overlap would occur. If so, the loop is aborted.

Is there a faster way of doing that? Is there a method where the endpoint of the route could be calculated on beforehand?

Here is a quick example I knocked up to demonstrate this:

Click with the mouse to move the square. It should not be able to go through the other square.


Jesse(Posted 2010) [#2]
the collision part is as effective as it is going to get. although I would not check for pixel collision every pixel movement. the best method is to use bounding box collision first sense that would be magnitude faster and only do single pixel movement collision if the two shapes collided in the bounding box test.
side note:
have you tried to run your code in debug mode? it doesn't run. A BlitzMax array of three elements would be n[3] and is base 0. That is, it would be indexed between 0 and 2, not 0 and 3. You just need to change your array dimensions to n[4] for four elements.


Warner(Posted 2010) [#3]
Thanks for pointing that out. I didn't run it in debug mode. I corrected the posted code.
I'm thinking of using a boolean search instead of a linear search. However that wouldn't prevent shape 1 from jumping over shape 2.
Also, I was thinking about how each side of shape 1 is translated. Those sides and their translated counterparts form a polygon that could be checked for overlapping shape 2. I believe that would be called 'sweeping'?
It would be nice if I could somehow trace back how far shape 1 can move based on the collision points it finds in such a swept collision.
For now I'm planning on combining both the boolean search and the sweeping method, and a bounding box check as you suggested.


Jesse(Posted 2010) [#4]
I believe warpy posted a line intersection formula in the code archives which you might find useful for determining exactly where the collision happened or if it happened.


TaskMaster(Posted 2010) [#5]
For the first check to see if it should be more detailed you could also just take half of a diagonal through the rectangle and use it in a distance check.

In other words:

Half of the length from the top left to the bottom right is basically the radius of a circle that the rectangle will never leave, no matter how it is rotated.


Jesse(Posted 2010) [#6]
I don't think that the radius check should be the first check because depending on the speed it has the possibility to fail. there is the possibility to fail even with the bounding box check if the speed is bigger than the size of the object but the radius check will fail for objects that are moving at smaller speed then the size of the object.


Warner(Posted 2010) [#7]
I tried combining the boolean search with the sweeping technique.
However, when I run some tests with it, it seems to be quite a bit slower than my first attempt :(
Well, anyway, here is the (slower) code:

Thank you for your advice, I will look into it further.


Jesse(Posted 2010) [#8]
a while a go I converted some code to BlitzMax from Blitzbasic that I have found some good use for. It is a polygon vector code. it might help you solve some problems you are having:



TaskMaster(Posted 2010) [#9]
Obviously, if your objects are moving fast enough to pass through each other, then any single check is not the solution.

How fast are your objects moving? The issue of objects travelling fast enough to pass all the way through each other is a pain to deal with.

What I usually do is set my update routine (logic, not drawing) to run fast enough that that no two objects can pass through each other. If this isn't possible, then I would say you still don't need to check every pixel, unless you have objects that are only 1 pixel in size. What is the smallest object and how far can they move in one update? Divide that size down to get the minimum collision check distance. If it is just "per pixel" then obviously you will have to check every pixel or do some sort ray or line intersection technique.


Warner(Posted 2010) [#10]
I'm designing some sort of a general-purpose 2d engine. So I can't predict how fast objects will move. That is the reason why I chose this approach.
Indeed, there should be much to gain trying to improve the search algorithm by taking bigger steps based on the object's radius.
But I was thinking: since both objects are squares, and I know their size, isn't there a clever line/ray intersection technique that I could use?
@Jesse, thanks for the npoly translation