# A better Breakout

First, let's take a look how the collision detection might look for the average breakout game.
The typical game will 99% of the time have a grid-based layout, usually made up of several rows and
columns of rectangular bricks.

Above you can see the black lines showing the layout of the board and the colored bricks showing occupied
spaces on that board. (White blocks are empty spaces)

In every frame of the game, the ball is trying to move from **A** to **B**. The ball starts at **A** and moves **X** units
(the ball's velocity) each frame in a specific direction. That destination point is **B**; the starting point **A** plus the velocity
of the ball. Ok, so you move the ball to **B** but then what? There are several collision methods to choose from here. You could take the ball's
new position **B** and loop through all the rectangles in the game to see which one it overlaps with. That's a lot of checks every frame for no
good reason. A better solution would be to divide the coordinates of the ball's position by the size of the bricks to get a grid location. In this
example, the grid is 6 by 3. We'll refer to this as map[6,3]. If each brick is 32x16 pixels and start in the top corner of the screen (otherwise
you just need to factor in an offset value of where the first brick starts), we can quickly extrapolate a grid position for the ball. Let's say **B**
is at 47px on the X-axis and 45px on the Y-axis.

```
x = 47 / 32 = 1.4687
```

y = 45 / 16 = 2.8125

Using only the integer part, we can truncate the decimal value and end up with [1,2]. If your array starts with indices at 1 instead of 0, just add 1 to
whatever your values are. In this example, we'll assume that map[6,3] ranges from 0-5 columns and 0-2 rows. So the ball is at [1,2], which you can see is
occupied by a blue brick.

At this point you might be thinking, yeah this was easy. Simply check the array if that grid position is occupied by a block then simply flag that array element as destroyed or whatever and reflect the ball accordingly. Well, yes it is simple but it's not the most accurate method. As you can see in the illustration, if you haven't picked up on it already, the position of the ball overlapping a specific brick lies on the center position of the ball. Meaning, half the ball overlaps the brick before it registers as a hit. If your ball only had a 1px radius, this might be ok, but most likely you're using something a bit larger. This overlap hurts part of the overall realism of the physics of the game. If you throw a ball at a wall, it doesn't get absorbed half way into it before bouncing back, does it? Of course not, so let's fix it!

Before I tell you how to solve this problem, there's another issue that can be resolved with this solution as well. Let's say the ball is traveling fast,
very fast. Fast enough that point **B** ends up on the other side of a brick. If point **A** didn't overlap anything and point **B** didn't overlap
anything, then there must not have been any collisions, right? Wrong! While it's true that neither position will overlap an occupied space in the grid, the ball
will appeared to have moved right through an existing brick as shown in the image below.

So how do we fix these two issues? We use a sweep test. What will make this even easier is the grid structure of the map. We always know where the vertical
and horizontal lines will be making up the grid. We know where the ball is currently at (**A**) and where we would like to move it (**B**). And we should
also know the radius of the ball. The sweeping method works by checking for collision over time. Is there a collision somewhere between A and B? To do this, let's
first check against the horizontal lines. The last line in the grid, right under the blue bricks, goes from [0,48] to [640,48]. (assuming a 640x480 resolution game area)
Call this line **CD**. What's important to remember is the direction the ball is travling. Subtract the Y-components of B-A. If the value is negative, the ball is
travelling upward and will hit the bottom of bricks. It can not hit the top of a brick unless the ball is travelling downward. Now, translate **CD** towards **A**
by an amount equal to the radius of the ball. When we do an intersection test between AB and CD, this will take into account the radius of the ball and we'll get an actual
point of contact for the outer edge of the ball, not just the center of it.

The translation of line CD is what eliminates the overlap of the ball and a brick and gives us a more realistic appearance. As for the super fast traveling ball skipping bricks?
That is what the line intersection test will solve. If you're unsure of how to translate the line by the ball's radius, you simply add (or subtract depending on the direction the
ball is moving) the ball's radius to the Y-component of **C** and **D**. Next, see if the AB intersects with CD. You can view the intersection algorithm
here. If the result (**t**) is between 0 and 1, the lines intersection and we have a possible collision.
Use linear interpolation to get the coordinates of the intersection point.

```
I.x = A.x + (B.x - A.x)*t
```

I.y = A.y + (B.y - A.y)*t

Once we determine there was indeed a collision at this location, the ball will move to **I** instead. Next step is to determine the point of contact of the ball
at **I** along the line **CD**. To do that, take the intersection point **I** and subtract the normal of the line times the radius of the ball. The normal of a horizontal line
is [0,1].

```
P.x = I.x - radius*0
```

P.y = I.y - radius*1

Remember how we converted point **B** into a grid location? Do the same for point **P** and use that result to lookup in the array for an occupied brick. If there is a brick there,
then indeed there is a collision. Reverse the ball's direction vector along it's Y-axis, destroy the brick at that location by flagging it in the array, and continue on about the game.
If there was no collision, repeat the above process with the rest of the horizontal lines that the ball may have crossed over. From the image above, you can see the ball travelled over two
different lines. That should be the greatest number of collision checks you would ever have to do in that direction.

What's next? We've covered horizontal lines, which deals with the ball travelling up and down, but what about the vertical lines? What if the ball hits the side of a brick before it hits the
top or bottom of one? When you calculate the initial intersection time between AB and CD, store that value. Repeat the process as you did for the horizintal line checks but this time do it with
the vertical lines. AB stays the same, but this time CD will be [x,0] to [x,48] (where x is the position of the vertical lines along the X-axis). If you get a time value from the intersection test
which is less than the previously recorded value (but still greater than 0) then this intersection happens first and is your new target. The calculations for finding the intersection points and
point of contact stay the same as the horizontal check.

That's all there is to it. Offset the horizontal lines by the radius of the ball in the direction against the ball's travel and test for a line intersection between that line and the line formed from
the ball's starting position to it's target position. Record the time of the earliest intersection. Repeat the process for vertical lines and determine if the intersection happens sooner than the
horizontal checks. Find intersection point, convert to grid location to see if a brick occupies that array tile, then reflect the ball's direction vector and destroy the brick.

## Final Notes

After a collision is detected and you position the ball at **I**, the process starts all over. But there's one final issue. If the ball's initial target position was 20px away, but a
collision occured halfway through its travel, positioning the ball and moving on would create the appearance the ball really only moved half it's velocity. It would look as though the ball
very briefly slowed down for a moment every time it hit a brick. Instead of throwing away the remaining velocity, let's use it!

We know the intersection happened along **AB** at time **t**. The distance between **A** and **B** is the velocity **v**. **B** should have been calculated as:

```
B.x = A.x + U.x * v
```

B.y = A.y + U.y * v

Where **U** in this case a normalized direction vector. So think of **t** as a percentage of **v**. The remaining part of the velocity **r** is:

```
r = v * (1-t)
```

Now project that remaining velocity onto the ball in its new direction.

```
B.x = I.x + U.x * r
```

B.y = I.y + U.y * r

There, now you have a complete breakout collision system. It might sound like a lot, but in reality this method uses very few calculations and should be quite efficient while preventing
common problems that arise from the more basic collision methods.