in Uncategorized

Intersections in Video Games

Hello, welcome to my very first blog post.

There are a bunch of primitives while making video games. I think, one of them is intersections. This topic is very significant because you need it to make collision detection in video games. If you are using a programming language that needs performance, you should make some optimization or use some shortcuts as me. When I didn’t use any engine that makes it for me, I used to write my own functions to find the intersections on game scene. Of course, I’ve written just one time, and I used it in other projects.

In this topic, we can clarify these headings with a little math;

  • Line-Line intersection
  • Circle-Circle intersection
  • Rectangle-Rectangle intersection
  • Line-Circle intersection
  • Circle-Rectangle intersection

 LINE-LINE Intersection

We are starting with line-line intersection. Actually, we mostly don’t need to find this. We need the intersection of two line segments. It’s not as easy as finding the line-line intersection. It needs some chained calculations but we don’t need them. Our algorithm is just two step. The first step is finding the intersection point of two lines with formula. Then we check that point is on that line, or not. While finding the intersection point, we can see, there are many approaches applying.  According to the Wikipedia, I got a nice formula.

Intersection point of two lines

Intersection point of two lines

We are thinking our line segments as lines. If we apply this formula to our points which is starting and ending points of our line segments, we find the intersection point of them. Of course, we have to test the point that is the result of the formula above. If this point is on our line segments the line segments intersect at that point. Well, how will we test it?

We can test the intersection point using a rectangle

We can think the line segments’ scope as a rectangle.

As you see the picture above we can pretend there was a rectangle behind this line segments and we can test the intersection point of the two lines using this rectangle. It is enough to test that the intersection point is in the rectangle, or not. If it is in the rectangle, they intersect. Unless, they don’t.

CIRCLE-CIRCLE Intersection

This intersection type is useful most of the times. I’m using this when I want to test two circle-like objects. If you making a shooter game, you don’t have to control all the time the bullet is in the object that is the target. You can pretend bullet and target are circles. Sometimes this method won’t be effective but If we think about rapid prototyping, this method would be useful.

You know geometry is the most cheerful friend while making games. That friend says that ‘You don’t have to find the exact point that the circles intersect. If circles’ radius total is bigger than the distance which is the difference of circles’ centers, they intersect. It’s that simple.

 

Circle-Circle intersection

We don’t find the exact intersection point, we just test the circles and give a result as Boolean.

 

RECTANGLE-RECTANGLE Intersection

Rectangle-Rectangle intersection is like the Circle-Circle intersection. This intersection type is useful for lots of types of games. Let’s imagine two rectangles. They have corners and sides. Every rectangle is combined with four line segments. We can try the line-line intersection for every side of the rectangles. Or there is another way which I used to find the intersection. Let’s imagine two rectangles again. We know the exact coordinate of the upper-left corner of the Rectangle A. We find the coordinates of every corner of the Rectangle B then we test that points with Rectangle A. If a point is inside the rectangle A, then rectangles intersect, else they don’t. Let’s examine the picture below;

 

Rectangle Rectangle Intersection

We don’t have to find the exact intersection points, we just test the corners of one rectangle is in the other rectangle, or not.

 

LINE-CIRCLE Intersection

Line-Circle Intersection isn’t always useful, most of the time this can be turned into a Rectangle-Circle intersection but we will consider it anyway. Let’s imagine we are shooting balloons with an arrow, so have to make collision detection between balloons and arrow. We can use this intersection method for it.

Okay. Let’s turn to our most cheerful friend. Geometry says that there can be only three situations between a line and a circle; They don’t intersect. They intersect at one point. And they intersect at two points.

We draw a line to the center of the circle which is perpendicular to the line. If this line is bigger than the radius of the circle; they don’t intersect. If this line is equal to the radius; they intersect at one point. And finally, if it is smaller than the radius, they intersect at two points. Simple is the easiest one.

Line-Circle Intersection

If length of the MN line intersection smaller or equal to the radius, they intersect otherwise not.

CIRCLE-RECTANGLE Intersection

Most of the shapes are similar to circles and rectangles. I believe that we can draw everything using circles and rectangles. So according to me, this intersection is the most usable one. And here is the thing. Like everything in nature, there exists 146 way to accomplish it.

We can find the closest side of the rectangle to the center of the circle than apply a line-circle intersection.

We can find the absolute distances between the center of circle and center of the rectangle respectively x and y. If this x distance is smaller than the width/2+radius or y distance is smaller than the height/2+radius, they intersect. If we use this method we should consider a case which they intersect at the corner of the rectangle. I will explain it in the code.

We can draw four orthogonal line to the every side of the rectangle from the center of the circle and one of them is smaller than the radius they intersect. We can find so many solutions for this.

Circle-Rectangle Intersections

Of course I might miss lots of important points and ignore some of the case but I am sure of that you won’t miss them during the coding.

 

Don't be selfish guys, let people know!

It's not hard to say something !

Comment