Automatic Rectangle-Rectangle collision and response using sweep

I love side-scrolling platformers and have built my game engine, GrehGameEngine, focusing it. We all know first layer of collision detection is always rectangle based because its faster than other geometrical shapes.

While developing games I tried to Google as much as I can regarding rectangle collisions. But I couldn't find single-complete algorithm for finding collisions and deciding response. So after many models and calculations in 2012 I developed this method. It is actually a sweep collision method. So will be helpful for most of game developers.

Using the following illustration I will describe the method.

We have a player R1 and a platform R2. R1 has to move dx,dy from START (x1,y1) and reach STOP ( x2,y2 ). But collision with R2 must stop it to remain at EXPECTED (x3,y3).

Here we have constructed a situation, but in reality we don't know where expected would be. This is what this method is for. Below is the step-wise approach to calculate x3,y3.

STEP #1:

Get the distance between R1 & R2 and also check which projection axis already collides. In our case, no axis collides. What does this mean? Look from any sides around these rectangles they will not be overlapping. They are separate.

Distance has to be calculated between their sides which face each other. In our case R1.right and R2.left face each other.

DistX = R2.left – R1.right , DistY = R2.top – R1.bottom

STEP #2:

Convert the distance into rational values by dividing them with their DELTA movement values. In our case it will be.

distX_percent = DistX / dx , distY_percent = DistY / dy

NOTE: handle divide by zero dx = 0, dy = 0 before it.

Why rational / percent?, have a look at this -

STEP #3:

Check which projections were colliding. If both projections were already colliding then R1 and R2 are already collided, STUCK situation!, what is the point of moving dx,dy now. Figure out how to avoid this stuck state!, it happens when R1 is created overlapped with R2 OR a failed last collision response which should not happen.

STEP #4:

Now the final step. Look again at figure 2, and then figure 1. Assume Point A of figure one as EXPECTED position in figure 1. Means db = DistX, dp = DistY and dh = EXPECTED delta move.

Imagine R1 is slowly moving towards R2 with dx,dy and collides with R2 at expected. This is visual!, how to get it by maths?. The answer is already in our hands. We have to test which projection satisfies collision in both axis.

We take the DistX_percent values first and apply the formula dp% = db% = dh%.

new_DistX = DistX_percent * DX. (Its not needed because new_DistX = DistX already)

new_DistY = DistX_percent * DY. ( db% = dp%, getting db% of DY ).

Translate R1 to the new values and check if it collides with R2. If collides then expectedXY = new_DistXY. If it doesn't collides. Try DistY_percent to get new_DistX.

new_DistY= DistY_percent * DY. (Its not needed because new_DistY = DistY already)

new_DistX= DistY_percent * DX. ( db% = dp%, get dp% of DX ).

Again translate R1 to these new X,Y, if it collides with R2 then expectedXY = new_DistXY. If it doesn't collides. This means there is no collision in this delta move.

Here is the method in action. Its HTML5 version which can easily be converted to C++/Java etc. Whole code can be found inside the JavaScript section of this html file.

Download Or Open rect-collision.html

In the above demo, Green rectangle is R1 (start), Blue rectangle is platform R2, Brown is STOP and red is the expected result rectangle. Left click / Drag to move STOP position and Right click to set START position.

Cleaner illustration:

Figure 3


In above figure, we can see the distance between R1 (green) and R2 (blue). How do we calculate EXPECTED position i.e. DistH.

We take DistX as our dx delta move and find dy using db% = dp% relation.
new_DX = DistX% * DX
new_DY = DistX% * DY

Now translate R1 to this new position and check collision If it collides then this is our DistH. Otherwise we take DistY as dy delta move and find dx using distY.
new_DX = DistY% * DX
new_DY = DistY% * DY

Then same collision check again. if collides we get DistH => new_DX, new_DY.
If it doesn't collide again then the DX,DY delta move is considered safe delta move without collision.


Below is HTML5 collision in action. Mouse input was getting lost so i coded rect movement around corners. Green is start. Blue is obstacle. Dark red is target position where green has to reach. Light red is auto-calculated position if collided.