In this video, I'm going to be introducing several techniques toe handle collisions between convex polygons on.

I'll even look at handling collisions in a static fashion to, but I've got two things to mention just before we get started.

Firstly, anything you can do to a convex polygon, you can also do tow a quadrilateral.

So those of you with tile based systems using rectangles and scores all of this material should be very relevant to.

Secondly, it may seem like a horribly complicated thing.

Convex polygon, collision detection.

But it isn't.

I want to focus on the algorithms rather than the code for this video.

And so the coding sections may go a bit quicker than usual.

However, I encourage you to download the source file from the get hub and study it for yourselves.

Let's get some of the very basics out of the way first, as my regular viewers will know by now, I draw everything by hand, so technically nothing you'll see on the screen is a poly go.

A polygon is defined by points connected by straight edges, and as you can see, I'm no good at drawing straight things on my screen.

on what I have here is called a concave polygon and concave polygon presents all sorts of problems I'm not going to discuss in the video simply because they have something like this.

And a concave polygon can be identified because it has at least one internal angle that is greater than 180 degrees.

And so for this video, we're not interested in con que Fala guns were interested in convex polygons, which means all of the internal angles are less than 100 and 80 degrees.

Now I know that a large part of my audience build simple to D games and so we mustn't forget that rectangles and squares are also convex polygons on the algorithms.

I'm going to show today there are some explicit optimization is you could make if your system only contains quadrille actuals such as this, But the code I'm going to show is for arbitrary sided convex polygons.

However, I just want to get out of the way.

One little thing which deals with just rectangles only, and you may have heard of it.

It's called a B B, which stands for axis aligned bounding box on.

This is an incredibly simple collision detection routine just for squares and rectangles on specifically for squares and rectangles that haven't been rotated.

And this means given an axis of the world in our X and Y directions, the sides of the quadrilateral a parallel to those axes, checking to see if two axis aligned Quadra laterals overlap is very trivial if I label this one pee on this one.

Q.

We can intuitively see that in the X axis.

If this side of P is less than this side of Q, and this is just for X axis, then there is potential for overlap.

Because if this highlighted side of P was greater than the right hand side of Q, clearly they wouldn't be overlapping.

We can confirm this with another check that if this side off P is greater than this side of Q, then in the X axis, these two Quadra laterals are overlapping.

And so if I label this as X on, this point is X plus wit for that rectangle, and the same applies for Q.

We know that there's overlap in the X axis if P X is less than que x plus w and p x plus W is greater than Q X on because our quadrille actuals axis aligned.

Whatever applies in the X axis also applies in the Y axis.

So we can simply duplicate the formula, replacing Xs on W's for wise on H S.

H being height.

Of course, I'm not even going to code this up because it's so simple and quite obvious.

But I felt it needed a place somewhere in this presentation, as usual.

Before we get stuck into the algorithms, I'd like to just demonstrate the kind of thing I'm going to be building today.

And this is just a little program that demonstrates to alternative methods for detecting overlap between convex polygon.

So we'll see.

We've got a selection of convex polygons on the screen.

I've got a Pentagon, which I can move around The line from the middle of the Pentagon to the outside just helps with the direction, so I know how to steer it with the arrow keys.

I could move the Pentagon around with the W S and D keys.

I can move the triangle around.

I can't move the square around in the bottom corner and with the function keys, I can choose between four different options of the algorithms.

The first is called separated Access Theory on As you'll see as I move the Pentagon into the square, it's changed.

Read that indicates that overlap has occurred, in fact, and go over the triangle and the same thing happens.

And it's very, very precise for now, the the alternative algorithm that where I look at diagonals versus edges gives exactly the same result.

I can move the triangle into the quadrilateral as well.

Detecting whether two polygons overlap is very useful.

But if we wanted to actually constrain them from overlapping, we need to apply some sort of static collision resolution.

And so I can press F two to select static for the separated access their version, and we'll see what happens so I can control the Pentagon.

We can see it doesn't go between the shakes, but it Judd is a little bit.

I can't force it into the other shapes.

Now the shapes have a degree of priority, so if I push the triangle, I can push the other shape around.

But I can't push the quadrille national around with the triangle.

We can see the collision is quite robust.

There's no dynamic response is implemented here.

So the feel of what's going on may look a little strange because you'd expect it to rotate and bounce accordingly.

This is just static resolution.

It's just a way of stopping the shapes from overlapping the alternative method.

Using the shapes diagonals on, we will go into some detail about these methods during this video, I feel is a little bit more numerically stable.

So if I take the Pentagon this time, what we noticed is, well, I set it up.

There's actually less juddering as part off the resolution.

The diagonal method approach is a little bit more computational intensive, but fractionally so.

But I think the results on the stability are just a little better.

So let's get started with the rather traditional separated access their, um, here I have a polygon, and here I have a number.

Firstly, we can see they're both convicts, and secondly, we can see they're not access aligned in any way.

This approach involves looking at the shadows off the shape along an axis and checking if for that axis, the shadows overlap.

In fact, we're going to check against several different axes And if the shadows overlapped for all of those axes, we know that the two shapes have collided.

One overlaps the other.

So what are these mythical axes?

Well, I'm going to create an axis relative to each edge of each polygon on.

I'm going to do that by simply taking the normal oven edge.

So taking this edge of this triangle, I'm going to create an axis relative to that.

Normal.

Now, it doesn't matter where that axes actually exists in space, as long as we have something that is parallel to it.

So I'm going to translate that access down here just makes the drawing a bit clearer.

And now I'm interested in the normal to that axis, which is, of course, the original direction of the edge of the polygon.

To begin with and somewhere in space appear, I'm going to turn a light on.

And this is a special light because it transmits light globally, but in a single direction.

This means that all of our points will cast a shadow onto this axis.

And we look at all points on both shapes.

Farid shape.

We then work out the minimum and maximum extent of that shadow.

So for the quadrilateral here we can see the two big red points on the axis.

And for a triangle, we've got the two big blue points.

We've got the two shadows of the two shapes on What do we see?

Well, the shadows overlap and using a method very similar to the Axis aligned bounding box I've just described, we can consider that for this particular access, we've got overlap, and so far our shapes must be overlapping.

This algorithm requires that we repeat this process for every edge of both shapes.

In fact, it will be for every edge of all shapes who want to test collisions between.

So let's consider two shapes that are not overlapping on.

We'll start with this edge, so we'll take the normal of this edge to create our access on.

This is called the projected access.

I'm not going to translate it this time.

I don't need to use the lightbulb analogy anymore.

I think you can see how we can crush these points onto this access.

When we project the point onto this access we can see.

In this instance, there's no overlap between the two shapes, and if we find one axis that has no overlap, then the shapes can't be in collision.

They are indeed separated along that access.

Things get a little strange when we try to assign numeric values to what's going on here.

But ultimately, the numeric values of things is quite irrelevant because it's all relative to one particular system.

So how do we actually do these projections?

Well, quite simply, it's just the dot product between two vectors, one of which is our access of projection, and the other is a vector to the point.

Now, these two points naturally, are at 90 degrees to our normal on when you do the dot product between two factors, you get a scaler value.

In this case, the scale of value is zero.

Because don't forget our doc product in this case is going to be p x times X plus P y times and why.

And we've done dot product as projections quite a number of times on this channel.

And in the past, I've referred to this method of dot product as being an indication of how similar to factors are.

If I just quickly describe two vectors here, this one is going to 10 on this one is going to 01 and we apply the above formula.

We've got to zero times one plus one time zero, which is zero.

The vectors are not similar.

A tall and this is quite right because they're at 90 degrees to each other.

If, on the other hand, we had a point going to 11 we end up with one times one plus one time, zero clearly a one on we can see here if we were to drop a shadow down from that particular point.

Of course, the result is one.

This also applies to vectors going in the opposite directions.

Except this time you have minus signs.

And so, for this simple polygon, the one outlier is, of course, this point.

And if we take the dot product between this point on the normal, we end up with the projection along the normal access.

Our access off projection on this gives us some value.

Let's call it Q naturally thes.

Two other points also were projected in exactly the same way on they gave a zero in this case, but that doesn't mean we should ignore them.

It just means we've got another per values in this case, both equal to zero, which I'll call Q prime.

We can then test queue and queue prime toe workout.

What's the length of the shadow along the projected vector is And if the shadow for a particular axis off all points tested between both shapes being tested, if they overlap, then for that access there in collision.

If for any of the axes we test, there is no overlap, then the shapes are not in collision and we can have bought the algorithm.

And that's really it were taking all of the points, crushing them from two dimensions toe one dimension and then comparing the extent of those points per shape to see if they overlap.

So let's take a look at implementing separated access theory in code.

But before we can start testing whether polygons overlap, we need some system of actually representing a polygon, manipulating it on drawing it to the screen.

And, of course, I'm going to use the pixel game engine for this.

And as I mentioned at the start of the video, I'm already going to use some code I've created.

But I will just talk you through what's going on here.

So in the main function, I'm creating a pixel game engine of resolution to 56 by 2 40 each pixel size is going to be four by four screen pixels in the game engine class.

I've created a simple struck that represents a point in two dimensions.

On I've created a simple polygon structure, which contains a vector of points because a polygon can have any number of points.

But I've also included a central position point for that polygon andan angle on.

I'll use thes two variables to transform the shape from the local space of the shape to the world space.

And that's what these vectors are.

So here's another vector off to D points on This is the original model off the shape.

This vector P will be updated every frame with the translated version off the model of the shape.

And we did exactly this many times for the console game engine in video, such as code it yourself asteroids on the code it yourself worms.

Siri's where we had wire frame models.

So we taken original model use thes values to translate that model into world space on the model in world space is represented by this vector of two D points.

Finally, we've got the flag which represents whether it overlaps.

I'm using that to color the shapes.

I only use three shapes for this demonstration, but I could have many.

So I'm going to store those in a vector of polygons called Vac shapes in on user create.

I'm going to define my three shapes.

The first is a Pentagon, so that's got five sides.

And so I looked through all five points and using co sign and sign, I can work out where those points are relative to the origin of the object.

00 I could do exactly the same for a triangle, but this has only got three points, of course.

So the angle I'm passing in is to pi divided by three.

Finally, my third shape is a quadrilateral on just to be a bit different, I'm handcrafting the coordinates again.

It's relative to the origin, So this is minus 32 plus 30 around the center, 300.0 on when we translate for model space into world space, that origin will be translated to 5200 and will rotate the model is necessary depending on the angle value.

You'll also notice that I'm pushing these coordinates to the oh Vector, which represents the original model.

But I'm also pushing them to the P vector.

That's just to initialize the P vector to the same number of points and to make sure that the points are the same.

Finally, I add the three shapes to my vector of shapes in on user updates.

I've got a little bit of user input code, so this is just a handle the keys.

Now I'm using the arrow keys to control shape one on amusingly W A S and D case to control shape, too, if the user presses left or right or a or D.

I just want to increment or deck Ament the angle for that shape, and I modulate my F elapsed time to account for variability in the frame rate.