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.

GIMP for digitalization of sketches

GIMP is a very powerful graphics software. I use it for 95% of my graphics work. In this article i will show how to digitalize a sketch. I discovered this method when i wanted a digital pen to work. So decided to use raw sketches since they are natural and powerful way of sketching what we have in our mind. Also i always prefer doing natural way to work, being away from screen whenever possible. I am also in favor of saving power so try to utilize methods which are not dependent on electricity.

Things and skills needed:

• My setup is: ArtistX Linux (modified Ubuntu). Acer e-cmachin EMD-644 AMD APU
  powered laptop. It has less than 25 watts of power consumption.
• GIMP 2.8 or above if available. 2.6 will also work.
• Basics of GIMP.

Below are the methods in steps.

• Take a picture of your sketch using good camera as clean as possible with big contrast ratio (means dark and bright should have higher difference).
• To get good contrast use plain white paper and black ink.
• To get regular, uniform surface try putting a glass panel over the paper. Make sure that reflection does not disturb the shot Or simply use a scanner if you have one.

Now the digitization process. To let this process success even in worse cases i am using low quality sketch in resource constraint state of work. This image is bit blurred and has thick pen. Still we will achieve our goal.

Start GIMP and load your sketch. Make a copy of original layer, set original invisible and locked. Work on copy.

Method #1:

1. Click: Colors => Threshold => Move the slider to choose the best output you need.
2. Try to remove noise/unwanted colors by using other options like Brightness-Contrast, Levels, Curves, Desaturate. Then try step 1 again.

Method #2:

• Click Filters => Artistic => Photocopy.
• Play with mask radius to get how much sketch ink you want in output.
• Keep sharpness higher but its not a rule in every case.
• Keep % black and % white higher to almost 100%. i.e. 1.0

Extra Methods for enhancement of output. Apply before using Methods 1 & 2:

• Color => Auto => White balance, normalize, Stretch contrast, HSV.
• Color => Color to Alpha => Select the color of paper. Find color of paper using color picker.
• Filters => Enhancement => Unsharp Mask. Play with radius and little bit of other options.
• For some cases: Filters => Blur => Pixelize and unsharp mask (above) can be used in respective order to get nice results.

We should only rely on Extra methods to enhance the sketch to get best results from Methods 1 & 2. Below is the output of using above techniques.

I hope this helps in your sketch work. If it helped please say thanks to GIMP first :), its opensource and needs lots of support and funds. Least we can do is to make it grow!.

Download this tutorial in PDF format for offline use and printing:GIMP_for_digitalization_of_sketches.pdf.7z

Search TAGS:
How to convert sketch into digital image, convert paper into digital black and white format, sketch digitization, digitalization.