Placeholder Image

Subtitles section Play video

  • Hello.

  • 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.

  • If they press the up or down keys, I create a unit vector based upon the angle.

  • Using co sign and sign on displaced the shapes position by an amount along that unit vector a scale it to 60 here, which is the equivalent of setting the speed of movement.

  • Of course, if they press book that goes one way, and if they press down, it goes in the opposite direction.

  • I do exactly the same for shape, too.

  • Once I've got the user input sorted out and I've updated the shapes position, I then need to transform the shapes model into world space.

  • And that's done through this little auto four loop so iterated through all of the shapes.

  • And then for each point in the shapes model, I calculate its transformed position on.

  • This is just a combined two D matrix transform so we can see here with the Coast signs and the signs I'm handling the rotation based on the angle on, I'm offsetting the final position by the center corner.

  • I'm also going to take this opportunity, since I'm going through all of the shapes to set the overlap flags to false.

  • Finally, I want to draw the shapes.

  • So again I iterated through all of the shapes.

  • Using a little auto for loop on dhe, I draw a line between successive purse of points, and I can access these points through the index I.

  • That's why I'm not using an auto loop here because I know that successive points are I and II plus one.

  • I just need to be careful, though, because I want my shape to be closed on.

  • I don't want to access points that don't exist.

  • So when I'm taking on the neighboring point, I used the module ISS function with size of the number of points in the point vector.

  • This will ensure it wraps back around and closes the shape for me.

  • Finally, depending on the overlap flag, I choose the color of the shape.

  • If it is overlapping, I'm going to color it red, if not white.

  • It's quite convenient to know what direction the shapes are facing in, so you can control them sensibly.

  • So I draw a single line from the middle of the shape to the first point, and that's really it.

  • For the startup code, I update the shapes position based on user input, and I draw them to the screen.

  • At the moment, I'm not checking for any overlap, but let's take a look to make sure that this works.

  • So there are my three shapes, the Arrow Keys control shape, one, which was the Pentagon and the W S and D keys control shape.

  • To which was the triangle good to create a function called shape, overlap, separated, access their, um, and this will return true.

  • If the shapes indeed overlap, we're going to pass it to polygon.

  • Arguments on this function will return.

  • Are they overlapping?

  • The algorithm has a lot of repetitive code on.

  • I have to test each edge of both shapes, but I don't want to have lots of repetitive code in this function.

  • I also don't want to do any vector trickery, such as merging the two sets of points together.

  • So I'm going to create two pointers at Poly One and Polly to and set those to the address of our shapes.

  • Andi.

  • Well, first of all, test one shape against the other.

  • Then we'll swap these pointers around to test the other shape against the original one.

  • It'll become a bit clearer when we start writing some code.

  • I know that for this function, I'm only going to be testing two shapes to see if they interact.

  • So I create a small four loop just to select each shape.

  • If the shape is zero, I'm happy with Polly.

  • One equaling are one.

  • But if the shape is one I want to swap them around.

  • So a quick little check for that now it doesn't matter which shape Polly one represents.

  • We know we want to go through each edge of that shape and create a projected access on in much the same way I drew the shapes.

  • I'm going to use the index off the point in that vector on the index plus one.

  • Of course, making sure I wrap around using these two indices, I can extract the points that the ends of an edge segment on our polygon.

  • So here I've got it for the y axis.

  • And here I've got it for the x axis.

  • Subtracting these two points.

  • Well, of course, Give me a vector along that edge.

  • However, I want a normal to that edge.

  • And that's why when I'm constructing my access projection vector, I'm passing the wise into the ex location on inverting it and passing the exes into the why location?

  • This will give me a normal to the edge.

  • Firstly, I want to project all of the points of the first polygon onto that axis of projection.

  • But I also want to work out where the minimum and maximum extents of the projection lie.

  • So I create two variables.

  • Men are one and Max are one.

  • I've said them to infinity and minus infinity and you'll see why in a minute.

  • So with the one axis of projection, I'm now going to iterated through all of the points on the first polygon.

  • And I simply calculate the dot product between that point and the access of projection.

  • This gives me a scale of value.

  • Don't forget now, Instead of storing all of the scale of values, all of the points of the polygon, I am only interested in the minimum on the maximums.

  • So as I go, I'm going to calculate the minimum on the maximum.

  • Once I have the extents of the projection for shape one, I do exactly the same, but with shape too.

  • And finally And this is why I wanted to introduce a BB in a very similar way.

  • I checked to see if those extents overlap.

  • If they do overlap, I just want the loop to continue.

  • If they don't overlap, then the shapes are not colliding.

  • I can abort now and just return false.

  • If, however, I get overlapped for all axes.

  • I get to this point and I can return.

  • True that shapes must be overlapping.

  • If this is the case, just a quick little summary of what we're doing.

  • We're going to test two shapes against each other for collision.

  • But we need to test one against the other and then flip them around and test one against the other.

  • This ensures that we create an access of projection for all edges of both shapes.

  • Once we've got that access of projection, we take the points for shape one on dhe work out where the shadow lies along that axis.

  • Then we take the points for shape too, and also work out where the shadow lies along that axis on.

  • Then we check to see Do the shadows overlap If there is any access where the shadows don't overlap, we returned false because the shapes are not in collision.

  • However, if on all axes that shape shadows do overlap, then they are in collision.

  • So we returned True.

  • All that's left to do now is to call this function.

  • So for the particular shape that I'm testing, I'm going to call our shape overlap separated access theory and function on passing the two shapes.

  • One little point about this pair of loops there set up in such a way that shapes cannot be tested against themselves.

  • It's also set up in a way that we only test a perv Shapes wants.

  • So let's take a look.

  • I'm going to drive my Pentagon into the quadrilateral.

  • We could see the shape turned red, and we can get it.

  • Let's have a look how accurate it is.

  • The edges are probably not touching there, but let's just back it off a little bit.

  • There we go.

  • It is quite accurate, so that's very nice.

  • Let's go and test without triangle.

  • Oh dear, we see it's not overlapping with the triangle.

  • Why is this?

  • Well, simply put, it's because of the order of tests that were performing.

  • We're basically testing.

  • Is the Pentagon interacting with the triangle and then is it interacting with the quadrilateral?

  • And so even though it clearly waas overlapping the triangle when it was tested against the quadrilateral, it returned false.

  • So that reset the overlap flag of our Pentagon.

  • So I'm going to just accumulate with the logic or here.

  • So if any of the shapes cause an overlap with the Pentagon, then it remains set.

  • So let's try it now so we can try a triangle that we go.

  • It gets set to read, and we can try a quadrilateral on that gets set to read.

  • Let's also move our triangle around.

  • There We go very nice.

  • Depending on your application, you may want to structure the order of collisions in a slightly different manner.

  • It really is application dependent.

  • And so that is separated.

  • Access their, um, Now it's a bit of a bonus.

  • Two for one video.

  • This when I first started thinking about collisions between convex polygons, of course, I knew separated access theorem existed and was readily used by a lot of people.

  • But as a program, I feel it's important to try and think about things from first principles sometimes, you know, just to keep the brain ticking over.

  • And so I wanted to develop an algorithm which would give the same effect, separated access through, but approach it from a different perspective.

  • Now, full disclosure, this algorithm that I'm about to show could well exist.

  • It could be used by lots of people.

  • I don't know.

  • I've not researched it.

  • I don't have a name for it.

  • If it does have a formal name, please leave a comment below.

  • But for now, I'm doing it diagonals.

  • One of the properties of a convex polygon is nothing.

  • Conf it inside it I The boundary of the polygon is equal to its convex hole.

  • In contrast, a concave polygon isn't the convex.

  • Whole wood require this edge too.

  • Therefore, if I draw a line from the midpoint of the polygon to one of its external points, I'm doubling these the diagonals.

  • I can be sure that the diagonals never leave the boundary of the polygon.

  • This is not the same, of course.

  • For a concave polygon, I take some midpoint.

  • That one's fine.

  • Who This one?

  • The day Neil has left the boundary of the shape.

  • Not good.

  • And this one than this one than this one.

  • By knowing that all of the diagonals lie within the boundary of the shape anything that into sex, those diagonals must mean that something has entered the shape.

  • Knowing this, we contest the diagonals of one shape against the edge segments of another.

  • This means we can use a very common line segment into section algorithm to test the two lines.

  • The output of a line segment into section algorithm is usually a parametric value that represents the distance along that line, typically normalized to the location where that intersection occurs, and this is usually denoted by t till have t one for that line and t too.

  • For that line in this instance, T would begin at zero here and end at one here and begin a zero here on end of one here.

  • And this gives us some incredibly useful information.

  • We know that this intersection point along this diagonal we've intersected with another shape who will call that distance?

  • T one.

  • But because we know that the length of this diagonal is always going to be one, we know how far the diagonal has penetrated the shape.

  • It's simply one minus t one.

  • This means we can displace the shape backwards by one minus t one multiplied by the length of the diagonal.

  • Very simply weaken statically resolve.

  • That collision, now in much the same way, is separated access through.

  • Once we've tested one shape, we have to flip them around and test the other shape because we can see in this situation.

  • None of the original triangles diagonals intersect with any of the edges of the second shape, but this time one of the second shapes diagonals into sex with an edge of the triangle On depending on how we want the response toe work, we can either displace the quadrilateral backwards bye this distance, or we can push the triangle forwards by that distance.

  • This will depend on the application.

  • So with this diagonals edge intersect approach, not only do we get overlap information, we also is a byproduct.

  • Get information on how to statically resolve it, and I feel it's also a little bit more intuitive than doing vector projections, though admittedly not as mathematically clever.

  • So let's coat the soap.

  • I'm actually just going to copy the method we've already created because the outline code is pretty much the same.

  • I want to check one shape and then the other.

  • Except this time I'm going to call the function diag.

  • I'm going to remove the separated access theory component, so in principle, we're going to have to nested four loops.

  • The first is going to check the diagonals of polygon, one against the edges of polygon to now.

  • Specifically, I'm interested in line segments, not lines.

  • So a line segment is defined by starting an end point and for clarity.

  • I'm going to add these in and label them slightly differently.

  • So for our Dagnall, I'm going to take the midpoint of the shape as being the starting point of our line segment on a point on the boundary of the shape as the end point of the line segment.

  • In much the same way, I'm going to create a line segment that represents the edge of the second shape.

  • This time I'm taking a point from the edge on I'm taking its neighboring point, remembering to wrap around to close the polygon.

  • I've covered line segment into sections in several other videos on you can Google it and get it straight away.

  • But this is the equation for it, and this will give me T one and T two values.

  • I know that if both my t one and T two values lie between zero and one, then the line segments are crossing each other.

  • If one of these values is outside of 01 then the lines are crossing each other certainly, but not within the boundaries of the line segments startin end points.

  • So if the line segments cross, I'm going to return.

  • True, I don't need to do any further tests.

  • I know I've got a collision.

  • If nothing returns true, then I can return false.

  • I know that no segments have crossed each other, and so that's it.

  • It's very simple.

  • We take the diagonal of one shape tester intersection against the edge of another, and if he returns true, we're going to set the overlap flag of our first shape to True.

  • So we were testing for overlaps.

  • I'm going to copy that line, paste it in comment out the 1st 1 and change this to Diack.

  • Let's take a look.

  • We've got our shapes.

  • Pentagon will go down to the quadrilateral straightaway.

  • It behaves in a very similar way to the separated access their, um and it's a little bit beyond my mathematical abilities, but I'm fairly certain you could prove that this is a very accurate method.

  • But let's not forget that because we have generated T one and T two values.

  • We've also got the information to resolve this collision.

  • Statically.

  • Instead of modifying this function, I'm going to copy it and create a new one.

  • I'm going to call it diag static.

  • So this function will test for collision and try to resolve it.

  • It doesn't matter which polygon we're testing.

  • We will want to create a vector that represents the displacement to set the original polygons of position to to get it out of the collision.

  • Now the polygons could be overlapping in such a way that there are multiple Dagnall online into sections occurring.

  • If I want to displace the polygon accurately, I don't want to just abandon it At the first attempt.

  • It might detect an intersection and say the shapes are overlapping, but it won't displace it accurately to stop that overlap from occurring.

  • So I'm going to accumulate displacement depending on how many intersections occur.

  • So here we can see the one minus t one value and I'm going to displace along the diagonal, which we can represent is a vector by subtracting the two points of the end of the diagonals line segment.

  • If we make an assumption that shape one is the one we always want to respond to static collisions.

  • Then, during the first round of tests, the shape pulls itself out of the body it's collided with.

  • But during the second round of tests, the body pushes the shape out.

  • So this displacement vector we need to change the polarity off, depending on the order of the perv shapes were testing.

  • And so I'm doing that here, using the shape index from our original four loop to determine whether we multiply by minus one or plus one on.

  • I directly change the original shapes location because we have statically resolved the collision, there is no chance of overlap occurring, so this function now will always return false again.

  • Let's test the theory creates copy coming that line out, and this time we're going to statically result.

  • The collision.

  • Let's take a look.

  • I've got my pent again.

  • I'm going to try and crash it into the quadrilateral, and I can't.

  • The diagonal of the Pentagon is pushing into the edge segment of the quadrilateral.

  • Let's try it the other way around on.

  • We'll use the diagonal of the quadrilateral to push into the edge segment of the Pentagon, and you can see the static resolver pushes the Pentagon out of the way again.

  • This comes down to the order of priority.

  • In fact, there's no way I can make these shapes overlap each other.

  • Now, because of the order of priority, successive shapes become more dominant.

  • So here, instead of the triangle being the shape that gets resolved, the Pentagon is, but the triangle gets resolved against the quadrilateral.

  • Nothing could move the quadrilateral.

  • Let's park the Pentagon down there and we'll try and shove a wedge in between the two.

  • Very nice.

  • And don't forget.

  • Right now, the collisions are purely being statically resolved.

  • There's no physics at play here, so they might not resolve in in a way that feels quite right.

  • But it seems quite accurate against multiple shapes.

  • I'm pleased with that.

  • I think it's a good idea for programmers to occasionally go back to first principles and try and work out algorithms for themselves.

  • They might not be the most efficient or the most optimal, but it's a very useful thinking exercise and, to be honest, part of the fun of programming.

  • So is it possible to add static collision response to the separated access theory?

  • Well, of course it is.

  • Let's start by duplicating the separated access theory function on, I'll call this one static.

  • The aim here is to choose the minimum amount of distance that has to be displaced for one of the shapes to get out off collision.

  • The information we have at hand is how much the shapes overlap on the projected axes.

  • So perhaps it makes sense to store the amount of overlap and use the minimum overlap to influence how we displaced that shape.

  • So I've created a variable called Overlap and set it to a very large number.

  • Once we've worked out the shadow extents of both shapes along the projected access, we can calculate their overlap, which will give us a scale of value.

  • I'm always keeping the minimum here.

  • So that's why I'm testing against the overlap calculation on the previous value of overlap.

  • We know if it any point this returns false.

  • There is no overlap, so we only need to displace the shape.

  • If we get here.

  • There's a variety of ways to displace the shape, but the one I'm going to choose is to displace it along the vector between the two center points off the shapes.

  • And I'm calling that Victor de I'm going to need the length of D so I can normalize it on.

  • I'm simply going to take our overlap value and multiply it by the unit Vector between the two shapes.

  • Center points again.

  • If we're statically resolving a collision, this function should always return false.

  • That can't be any collisions.

  • Let's test this function separated.

  • Access their, um, static.

  • Take a look.

  • Let's let's try our triangle into the Pentagon.

  • The older priorities is still the same as before, so the triangle is the dominant shape.

  • Can the Pentagon and to the square?

  • No, it count.

  • What happens if I try to push the triangle into the square?

  • Well, there was no solution it could find.

  • So the Pentagon has gone somewhere, but I don't know where.

  • And so there you have it.

  • A work in progress, perhaps, but a variety of methods.

  • Toe handle collisions between convex polygons on Quadra laterals.

  • Particularly useful if you're building a top down city based car crime game.

  • Anyway, if you've enjoyed this video a big thumbs up, please have a think about subscribing.

  • The source code is available on Get hope.

  • Come and have a chat on the discord server on.

  • I'll see you next time.

Hello.

Subtitles and vocabulary

Click the word to look it up Click the word to find further inforamtion about it