Breakout Clone - Line Segment Intersection Algorithm

Sunday, April 19, 2009 by gradbot

For my next game Breakout, I need to detect collisions for a moving object. I choose line segments to represent object borders and motion. Calculating line segment intersections is a simple and fast algorithm and there are more advanced scan line algorithms to speed it up if needed. In order to use it, I take the ball's position and old position as the line segment for the ball.

The hard part of any collision algorithm is of course dealing with the collision. Detection is always easy because it's been done before. I'm doing collision with a simple reflection of the velocity off of the line segment it's intersecting. This works great until you collide close to another line segment and you happen to reflect to the other side of it. To fix this, I made the intersection and reflection algorithm recursive. This works great except for possible race conditions. Also, you no longer have a constant speed for your ball. A quick fix for the race condition is to check to make sure you can't intersect with the same line segment twice in a row. Having the ball move a little faster is acceptable.

Project Homepage

Here's a burn test where I had set the ball to a very high speed to see if it could escape it's enclosure or enter one of the other objects. In order to make any errors apparent, I added a line trail of a random colors behind the ball. This ends up filling in all of the movable area.

I must say it's pretty cool to see the ball travel to every little nook and cranny of the board. This must be how particle chaos works. Like a fragrance filling the room.

Filed under , , , having