Arbitrary Rectangle Collision Detection & Resolution - Complete!

hello in this video I'm going to start looking at rectangular based collision systems the kind of collision systems you would use on tile maps and you may think well I've covered that sort of thing before and you would be right to an extent however looking at the discord users recently and just general the feedback and getting a lot of you still seem to be having difficulty when it comes to tile based collision systems and I must admit that even I am fed up of coding the same thing over and over again whenever I'm implementing some 2d tile based game so this video is about creating a suite of utility functions which we can just reuse in the future for all of our rectangle collision based needs now there's something important to get out of the way at the start and that is that yes in this instance all of my rectangles are going to be axis aligned and that means the rectangles won't rotate in any way but that's okay most 2d games don't require rectangle rotations now there will be a little bit of mathematics in this video but if you're not entirely comfortable with the maths don't worry we'll be looking at it in code too and I know for many people seeing it written out in code suddenly makes it understandable well at least I'll try my best and finally for those following along with the progress of my lockdown goatee it's doing very well thank you so let's get started and I thought we'd start by going old-school one lone coda just for a moment this is a little project I'm working on in the background the video isn't going to be generating this project but it demonstrates nicely what it is we're trying to achieve so here I have a big red rectangle in the screen and you can see it's colliding with a tile map of smaller rectangles in the background and I have a character with some very basic rudimentary physics but the collisions are quite robust let's go down and find somewhere else to collide with here we go I will be talking about this project at some point in the future it's actually a little bit of groundwork for a future video I'm hoping to make about networking but it also happens to describe collisions very nicely so we can see the tiles in the background that are detected as being in collision with the red rectangle are highlighted yellow it does also collide vertically but because the frame rates very quick and the collision is incredibly brief you don't see it illuminate on the top axis of the rectangle many 2d games are structured this way and it's a great way for beginners to get started with games programming but coming up with a robust tile collision protocol isn't the most simple of programming tasks so I hope that this video will sort of describe a nice suite of utility functions that we can come back to time and time again so we don't have to keep recoding this stuff over and over since this is a video about all things rectangle collision I thought we'd just get started straight away with some code and get the easy ones out of the way as usual I'm using a blank pixel game engine project to start you don't have to use the pixel game engine to use any of these routines and the algorithm should be quite transferable to whatever language you choose to use we're going to be working with rectangles so I'm going to create a simple rectangle struct to represent a rectangle and bonus points for those that count how many times I say rectangle during this video for my system I'm going to describe a rectangle as being a point that defines the top left of the rectangle for that I'm going to be using the vector floating-point 2d type which is provided by the pixel game engine but that's just a pair of x and y variables I'm going to call that pause and the rectangle will be defined by a width and a height its dimensions I'm going to use another V F 2d type for that and call it size the very first function I'm going to create is to check whether a point lies inside a rectangle and yes this is very basic stuff if you've seen it before if the point lies in the rectangle it's going to return a boolean point versus rect and will pass in a point and will also pass in a reference to the rect ah to check if a point lies within a rectangle we just need to make sure that the point lies within the four sides of the rectangle so take the points x-coordinate is that greater or equal to the VEX position and what we do for X will always do for y so that's checking that we're within the top left of the rectangle we also need to make sure that all within the bottom right of the rectangle which is of course the rectangles position plus its size and that's that let's test it very quickly I'm going to use the mouse coordinate to be my point and in the pixel game engine we get the mouse coordinate by calling the get Mouse X and get Mouse Y functions however these are going to be returned as integers so I'm casting them to floats we will need of course a rectangle to test this with so I'm going to define a rectangle that begins with a position of 100 by 100 and has a size of well let's say 50 by 30 now if you're not familiar with this notation I've used an initializer list structure to define my rectangle because I've not defined any sort of constructor for my rectangle struct so this is the position and this is the size I'm going to call the function we've just created passing in the mouse coordinate and our rectangle and if that's true I'm going to draw the rectangle taking its position its size and I'll specify the color as being yellow so we can see it if I'm not in collision with the rectangle I'm just going to draw it white because I'm changing what I'm drawing to the screen each frame I want to make sure that I actually clear the screen so I'm going to clear it - let's say dark blue it's more interesting on the video than black all right let's take a look so here we can see our rectangle being drawn on the screen and when I put my mouse over it and anywhere within the rectangle it turns to yellow next up I'm going to create an equally simple function to detect if a rectangle overlap another rectangle I'm going to call this one rect versus rect and passing two references to rect this implementation is conceptually similar to the one we've just done except now we're working with sides of the rectangles I actually talked about this in a little bit more detail in my polygon collisions video earlier this year I'll put a little link above fundamentally we're now checking the sides of the rectangle so considering the x axis let's test that the left-hand side of rectangle 1 is to the left of the right-hand side of rectangle 2 if that's not true then rectangle 1 is entirely to the right of rectangle 2 there can't be a possibility of collision if it's to the left we need to make sure it's not too far to the left and so the right-hand side of rectangle 1 must be on the right-hand side of the left-hand side rectangle 2 this is gonna be a fun video this one isn't it I can already tell and what we do for X we also do for y the principle is exactly the same except left and right is replaced with top and bottom unless we fall we'll just do a very quick test to make sure this works I'll keep the existing rectangle but I'm going to need a new rectangle I'll call that s and its position is going to be V Mouse and we'll give it the size very narrow 10 wide by a tall 40 high instead of testing the point this time I'm going to call our new function rect versus rect change the V Mouse to an S but we need to know where our mouse related rectangle is so I need to draw that rectangle too and I'll draw that in green why not let's take a look so those aren't green narrow rectangle and if I overlap it we see that the original rectangle turns yellow and so then we have two very basic functions to Detective a point or a rectangle overlaps with another rectangle we'll use these again later in the video but some of you might be thinking hang on Javed you've already created a platform game before you've made a video about it and that had a tile-based collision system in it and he didn't look any like this and you'd be right but for those of you that haven't watched that video let me just do a very brief recap on how that system worked it did take advantage of a few tricks of the properties of binary numbers in that demonstration the world was broken down to a single two dimensional array which began at zero zero and each element of the array represented whether a tile was solid or not there was other information to to decide what the tile was drawn like but principally we could determine if we should be able to pass through a tile or not the principle was very simple here I've outlined four tiles as being solid and my point within the world let's say it exists here has a floating point coordinate which according to my crude drawing is about two point six in the x axis and one point four in the y axis assuming that all of our tiles take up one unit and by one unit I mean that the dimensions across the tile are equal to one we can always determine which tile we are in within the array simply by truncating the coordinate we can simply lose the information after the decimal point and this will highlight which particular cell we need to interrogate in our array to see if it's solid or not this is a technique I've used many times on this channel now let's assume I have a player character sprite which is also one unit in size I can check the four corners of the sprite to see if they land in a cell which is considered solid here we can see we're certainly in conflict with one of the solid cells and so we need to position the sprite in such a way that is it out of conflict and with this approach you always adopt a protocol firstly we'll always resolve collisions in the x-axis and then we will always resolve them in the Y and using these unit dimensions makes the resolution very simple we know we are in conflict with this cell we know where that cell Lopes within the world along our x-axis we also know that the size of our sprite is equal to the size of a cell therefore to resolve this conflict in the x-axis sprite must be positioned an entire cell to the left so here is the sprite result in the x-axis we can see it's no longer in conflict in the y-axis there's nothing further to do and calculating the position to place it was very simple we can use truncation the sprite was originally here which is about three point five we can ditch the point five because we know we're in conflict and were automatically aligned in the correct position along the x-axis here is a slightly more complicated collision we've detected that the left-hand side of our unit sprite is in conflict with the tiles well if it's the left-hand side then we need to move it to the right so we can take the position of our sprite and truncate it that will move us to four in this instance but we want to move to the right one hole cell so we can add one to it to determine the correct location in the x-axis to be out of conflict we can now do a very similar set of operations to resolve the conflict in the y-axis this time we can see that our y-coordinate would be about one point five we truncate to tell us that it's just a one which magically resolves the sprite to the correct location this approach is very simple and very effective and the detailed implementation is provided in the code at yourself simple platformer game video so why do we need anything more sophisticated at all well there are scenarios where that approach has limitations it required that the sprite we were using existed in unit space it was one by one in relation to the tiles in the background that can be quite a restrictive thing what if you want a bigger sprite the problem you have then is you're testing against tiles which are smaller and may have caps for example since we were only testing the corners a tile that lies within the middle of the sprite rectangle simply isn't detected at all we could resolve this by adding more test points to our sprite but again it relies on these points all being a unit distance apart from each other in short it's not a very flexible way to do things but that's okay Javits isn't it you've shown us a way to detect if two rectangles or laughing surely we can use that well yes and no even that method has its limitations since we can now work with rectangles of any size we don't necessarily have to have things aligned to tile boundaries and in this instance we can easily detect that the two rectangles are overlapping and we could go one step further and actually resolve this collision if we know that they're overlapping we can sort of determine how they're overlapping and perform the necessary resolution to make sure that they are no longer overlapping in this case the green rectangle would move to the left by the amount it's overlapped and that is a particular policy adopted by what is known as a ABB collision detection routines and it works just fine for most simple scenarios tricky scenarios such as corner detection again rely on a bit of a protocol which way should the tile be resolved in this instance in order to be out of collision it's not that easy to tell so one policy is that you measure the distance that it's overlapped in each axis so here we've got it in our Y and here we got it in our X and whichever is the smallest is the direction we resolved the collision in and again this works quite well and may be completely sufficient for your needs but in say an action-platformer style game you may end up with some slightly unpredicted behavior when you clip the corners of the rectangles let's say the character jumps onto a Ledge but misses slightly well have they missed or have they not missed it's undetermined the spike could miss and fall down or it could not miss and walk along the ledge displacing by this minimum overlap is a very useful strategy but there's still a problem with it and this becomes apparent when we start taking frames into account we've got an object moving per frame it's moving closer and closer to the rectangle on this frame it's in collision and we can rightly assume we can resolve this collision by displacing the rectangle to the left good let's consider a different scenario our object is now moving much faster between frames following the rules we just established now in order to resolve this collision we would displace this rectangle to the right it would no longer be in collision which is good that's what we wanted but it's had to go through the original object that's not good and so fast-moving objects have the potential to penetrate through solid objects which they shouldn't and this problem isn't just restricted to fast-moving objects what if the object were potentially colliding with is very thin the object could be moving slowly but in proportion to the width of the object that we're colliding with you still have the possibility of passing through it so far I've presented a variety of ways to handle rectangle versus rectangle collisions and resolution and it's up to you to choose which one is appropriate for you at the time however this video is about creating a one-size-fits-all solution something I can just continuously reuse in future videos and future projects and that's something we should strongly have to do as programmers and the method I'm going to introduce next goes by several different names some know it as swept AABB I know it as projected rectangle collision and what we'll see is yes it's a little bit more involved but it does cater for all solutions so that's typically the trade-off we often pay when we look at abstraction we're going to make it very simple for us to use in lots of projects but it's going to be a little less performant however I think for almost all scenarios this approach is probably the best approach to take before we can determine our general purpose collision detection resolution routine we're going to need to know if a ray intersects with a rectangle now I did a video previously about the essential mathematics required for games development at least what I think is required and a great portion of that video was dealing with vectors and we can define a ray as being a starting point and a direction vector I'm going to call that starting point P and our direction vector can be determined by some end point along that Ray let's call it Q so our direction vector becomes d equals Q take P it could very well be that D is some normalized unit vector but in this case it isn't I'm going to we can provide a start and an end point and use that to define our array this means we can define any point along this ray using parameter T so if I take T equals our starting point plus our direction vector multiplied by T then for different values of T I can get any point along this line for example if T equals zero then I end up at just the starting point if T equals one then I'm 1 whole Direction vector added to my original point which would give me the end and therefore if T is equal to not 0.5 I get a point directly in the middle of my line in fact I can specify any value for T I can specify negative values and go backwards I can specify infinitely positive values and just keep going on forever and ever and ever my rectangle is also defined with some vectors so up here I'm going to have R P for my rectangles position and as we did with the structure at the start of the program I'm going to define the size of my rectangle as being our S so this point is in fact our S Plus R P now I want to do things a little bit backwards I want to work out at what value T along my ray have I intersected with the rectangle and as you can see I can intersect with the rectangle in well two locations and this is where we get to the rather odd notation of presuming that T is time even though it's nothing to do with time at all but from the Rays perspective we encounter one point before we encounter the other one is nearer to the origin of the Ray and one is further away therefore thinking of it in terms of time means we get to the first point before we get to the second point so time is just a convenient form of language to describe this effect and we can consider this point to be the time of our near-collision relative to the origin of the ray and this point to be far one of our fundamental assumptions is that our rectangles are by definition axis aligned they will never be rotated therefore they will always have edges at 90 degrees to each other parallel to the axes of our world therefore I'm going to extend the edges of our rectangle infinitely long along its edges and I want to determine what is the time to the near and far collisions in both axes so now we can forget for a moment that it's actually a vector and deal with the components of the vector individually so let's just take the x-axis as an example forgetting any Y component of the Ray I know that my T along the x axis here is equal to 0 and my t along the x axis here is equal to 1 therefore this near point in time can be calculated in the following way T along in our x axis is equal to the rectangles position dot X minus our points position dot X which gives us this length here but we want that as a percentage of the whole length and the whole length was our direction vector dot X this gives us our near-collision time our far collision time should be fairly obvious how to compute its this distance here so our far T at X is equal to our rectangles position dot X plus the rectangles size now dot X minus our original points dot X again divided by the whole length to give us that percentage here's a percentage because it's between 0 & 1 so we can determine the T values for near and far a longer x axis and what we do for X we do for y I'm not going to draw all those out they're the same equations but replace the exit with wise once we have established the near and far times for the intersections of the axes of the rectangle we can sort them to see if the Ray does indeed intersect with the rectangle so let's start with a very basic example what we're going to go right through the diagonal of the rectangle or square in this case there's our ray and we know that our Nia time in the x axis will be here and our far time in the x axis will be here they're also the same for the wire this up with a little X&Y next to those it's a draw in another ray parallel to the one that we had before now in this instance our new time in the x-axis is here and our far time in the x-axis is here near time in the y-axis and far time in the y-axis and I'll draw in a third ray parallel but the other side this time and we again can label our near time in the x axis and far time in the x axis near time in the y axis and far time in the y axis and at this point we can observe something interesting our distance to the near time in the x axis is always less than our far time in the y axis that here is the distance to the near time in the x axis and our distance to the far time in the y axis this is even true for the Ray in the middle so let's start by assuming there is an intersection if our near time in the x axis is less than the far time in the y axis we can also observe that our near time in the y axis must be less than the far time in the x axis let's draw in another ray and see if that adheres to these rules to start it here draw it along it clearly doesn't intersect with the rectangle now the intersection point with the x axis requires the time to go backwards that's quite strange but it's legitimate it's got to align with the left hand side of our rectangle so near X is up here far X is here near Y is here and far Y is here is near X less than far Y well it is good is near y less than far X no it isn't that's because we've not had an intersection so these look like some good rules to follow to see if the Ray has intersected with the rectangle but let's test it a bit further this time let's have a ray going from down here and up here is our near time intersection with the x-axis and our far time intersection with the x-axis and rather strangely here is our near time intersection with the y-axis and our far time intersection with the y-axis but this doesn't make any sense from this origins perspective clearly be far and near times are the wrong way round so we'll swap those and see if it obeys the rules well n X will be less than F Y and n Y is less than F X there is an intersection so it's important that we sort near and far in the respective axes to make sense before doing this check let's look at an odd ball one here is the origin of my ray and it's going perfectly horizontally through the rectangle here is our near time crossing in the x axis and our far time crossing in the x axis but we don't get any crossings in the y axis and the maths will actually resolve to infinity in this case our near time crossing of the y axis is minus infinity it's that way and the far time crossing in the y axis is plus infinity hey it never happened so do our rules still hold true in this case our near X is less than positive infinity and done near Y which is negative infinity is less than our far X that holds true let's consider it from up here clearly it doesn't intersect with the rectangle anymore our near X and far X are the same as before but our near Y is now positive infinity and in fact so is our far Y so is our near X less than positive infinity yes it is good but is our near Y which is positive infinity less than our FX no it isn't there is no intersection and so it looks like sorting the values along the Ray to be sensible followed by this couple of checks will give us an accurate assessment of whether the Ray intersects the rectangle once we know array does in two to rectangle we can work out were here is our NX and our far ex and this is our NY and far Y in this instance we can see that the intersection is occurring at n X and n X is larger than n y in this instance let's put in our NX and our FX now NY and our F Y which is down here somewhere if we carry on with that ray we can see that the intersection occurs at NY which is larger than NX so I will make the assumption that the maximum of NX and NY is actually the distance along the Ray to the first collision point so T near is the maximum NX and NY likewise we can actually work out the far collision point although it's less useful far collision point will be the minimum of FX and FY we now have sufficient information to do a ray versus rectangle intersection test so for now I'll create a function which takes in a Ray's origin point the Rays Direction vector and a rectangle now even though I'm using vector notation in these next two lines I'm not actually calculating them as vectors I'm using them as a convenience package to do the same calculations in both the X and Y axis so this division becomes an element-wise division all of this is happening for the X component and all of this is happening for the Y component and using the parametric line equations we talked about earlier we can calculate our near and far points in time for both the x and y axes if we end up in a situation where our far point is actually closer than our near point then we want to swap things around it doesn't make any sense to have something that is technically further away classified as being closer so we'll sort them and we know that we haven't got an intersection if the two conditions are not met if we haven't rejected at this point we can now calculate the actual x to the near and far collisions using the maximum and minimum functions for my implementation I'm not interested in collisions that may take place entirely behind the Ray direction and so I'm also going to reject the collision if my farthest hit point is negative that does imply that my closest hit point may also be negative this is required because the maths works out it says yes there is a collision but it's in the direction completely opposite to the raid erection specified that might be useful for things but not for this once I know the actual collision points in time along my Ray I can put that time back into my original Ray equation to give me precisely this point I can do one final line of filtering to give me just an extra piece of useful information in this instance I know that my direction vector was positive in both axes and I can observe that if my near X time is greater than my near Y time and my direction vectors X component is positive then the normal to the surface I'm colliding with must be in the negative x direction I can construct a unit normal vector along the same lines but the other way round if my near Y time is greater than my near X time then I can assume my normal vector is in that direction if my direction vector happened to be in the opposite directions I can also calculate normals for the other two sides knowing the point of collision and the normal of the surface collided with is going to be necessary to resolve the collision I want to pass these points back through the arguments so I'll add some more arguments to my function this is the contact point where the Ray intersected with the rectangle and this is the contact normal I'm also going to pass out one additional piece of information and that is the time to the point of contact that's now coming in as an argument I can calculate my collision point using the parametric line equation and using a couple of nested if statements I can construct the normal vector to the contact point if I've gone this far I need to return true for my function and so here in entirety we have the bones of array intersecting with a rectangle and we're going to need that in order to handle rectangle versus rectangle collisions properly we should test this to see if it works I'm going to use my mouse cursor to define array from a fixed starting point and I'll just choose that arbitrarily at something like 2020 my ray Direction is going to be the mouse's current location minus the starting point now instead of drawing a rectangle this time I'm going to draw a line from the race starting point and I'll draw it to the mouse location and we'll color that green the ray versus rect function we've just created passes back additional information through its arguments we're going to get a contact point and a contact normal we're also going to get a time to the point where there is a hit so now I'll call the function we've just created pass in the Rays origin the Rays Direction the rectangle were testing against and then the contact point the contact normal and the time of the collision this function returns true if the collision has occurred well let's just test that to begin with and see what happens so here we've got a ray and a rectangle and as the ray intersects with the rectangle all across we see it turns yellow oh but it also turns yellow when we're not intersecting that's interesting but it does seem to only turn yellow when it's within the direction of the ray the T that is returned will be one at the point of the mouse and so we can ensure that T should be less than one for a collision this time no collision until the Ray touches the rectangle I'll now also draw in the collision point I'll draw a small circle where the collision occurs specify radius of three pixels and we'll draw that in red let's take a look very nice and also visualize the normal I know it exists at the collision point and I will draw it to the collision point plus the collision normal I'll pick a number times 10 just to scale that unit normal and we'll draw that in yellow - so no collision and now we can see a quick little normal telling us which side of the rectangle we have collided with so why have we gone to all of this trouble to determine if a ray intersects with a rectangle when we care about if rectangles intersect with rectangles well recall before that there were problems if the rectangle is moving it could penetrate the target rectangle in an appropriate way I'll await the comments in YouTube below but now if we know the direction the source rectangle is moving in and we know where it should be on the next frame we can determine we'll hang on during that movement there was a collision this means we can no longer move through objects we know a collision has occurred our T value is less than 1 and the function returned true but if we simply displaced our rectangle to this collision point we see actually we're still in collision this is no good we need to take into account the source rectangles dimensions to resolve this collision properly the simplest and easiest way to do this is to expand the target rectangle by half the dimensions of the source rectangle again these are all tricks we can exploit because everything is axis aligned so if I take the width of this rectangle and expand the target rectangle I width over to that way and width over to that way and do the same for height we generate a temporary artificial expanded rectangle around our original target rectangle now if we perform the collision check with the source rectangle and this expanded rectangle the collision point occurs here and when we resolve the collision our original rectangle is directly aligned with the target rectangle they're no longer overlapping at all now we've introduced raise with the rectangle we've made an assumption that our rectangles have some sort of movement capability potentially they have a velocity which changes their position and so to our very basic rectangle structure I'm going to add an additional vector velocity now I'll add another function for checking a dynamic rectangle versus a rectangle this implies that the rectangle is moving and it's arguments are quite similar to before we take in the source rectangle the target rectangle and we'll get out of it a contact point of contact normal and the time of the collision for the sake of this video I'm going to assume that none of my rectangles start off in collision therefore if it has a velocity of 0 the input rectangle can't be in a collision after calling this function it's not moved I need to expand the size of the target rectangle based on the dimensions of the input rectangle and now I can call our ray versus rect function based on a point from the middle of our input rectangle our rays origin is the center point of the input rectangle the Rays Direction is going to be the input rectangles velocity the target rectangle is our new expanded target and our contact point and normal are the same as before if the Ray intersects and the length of the Ray is less than 1 then I'll return true otherwise I'll return false a collision didn't occur I'm going to modify the prototype of this function slightly at the moment we're passing in F time which is a return value of the contact time I'm going to actually change that to contact time so it's clear but I'm also going to pass in the elapsed time value of the simulation and this is quite important as we're doing things frame by frame the velocity will be far larger than the actual displacement required for the rectangle so I'm going to multiply that velocity by F elapsed time we've seen this before in quite a few other videos where we update the position of an object by adding in velocity multiplied by F elapsed time because F elapsed time can be very small the actual length of the Ray that we want to test will also be quite small relative to the velocity associated with that rectangle now we need to add in some dynamics to the simulation as this simulation develops I'm going to need lots of rectangles so I'm going to create a vector filled with our rectangle structures and for this video I'm going to assume that the zeroth element of this vector is the one that's under control from the user so we need to establish a few rectangles here first the player rectangle I'm going to start out at 10:10 and give it a size of 30 by 20 the velocity will be defaulted to zero I then need to add another rectangle to the scene I'll position that at 100 by 100 and set it to 80 by 50 I'm going to make it so that whenever the user holds down the mouse button that the rectangles velocity vector is set towards the mouse so I'll take the raid erection we calculated earlier I'll normalize it for now just so it's the sensible value we can play with scale it so it's not very slow then also modulate it with F elapsed time and I'll use a little auto for loop to draw all of the rectangles in the vector I want to perform a collision test between the zeroth element which is the player rectangle and the other rectangles in the vector so I'll just iterate through those manually not including the zeroth good I don't want to test that against itself and I'll test against all of the rectangles here X 0 is the player we wrecked I at this iteration of the loop is the target that we're testing against and I'm going to be getting a contact point of contact normal and a contact time but I also want to pass in the elapsed time for this frame if that returns true for now all I'm going to do is simply set the player rectangles velocity to zero we can get rid of all of this finally I actually need to update the position the player rectangle let's take a look here we've got the two rectangles and as I hold down the mouse button I can change the velocity of this player rectangle so let's see if it crashes into the rectangle if it didn't good and I can move it back off let's try that again that seems quite nice let's try it from this side yep didn't seem to do it good collision is working nicely just clipped it and we can come back off I'm going to try really fast velocity into the rectangle this time we really smashed it in and now I can't click it off that's because yes we've detected the collision but all we've done is stopped the velocity of the object we didn't resolve any collision here and consequently the two rectangles are still overlapping and if they're overlapping then the velocity just gets set to zero so these are permanently stuck together now what we need to implement is proper resolution of this collision to resolve the collision properly instead of just stopping at zero I want to cancel out the velocity in the direction of the contact normal consider this source rectangle coming into contact with this target rectangle it's overlapped slightly we know that this displacement is equal to the length of our Ray therefore the time of the full displacement is 1 and because we're dealing with axis aligned rectangles we can take any point on the rectangles perimeter look at the corresponding point on the next frame and the distance will be the same so we know that this whole travel here is equal to 1 when we called the Ray vs. rect function we were able to return the actual time of the collision which has to be less than 1 so we know that this duration here is T therefore this little duration here must be 1 minus T whatever velocity was specified on the rectangle to put it into collision I want to work out a little bit of reverse direction velocity to move it back out of collision well at least stop the rectangle from colliding in the first place well this little portion of velocity can easily be calculated as velocity scaled by one take T but I only want that to apply in the direction of the contact normal so I can element-wise multiply that by the contact normal see n I'll change this dead stop to be a modification of the velocity take the contact normal element wise multiplied by the velocity now I'm going to do something a bit strange here I'm going to take the absolute values of the original velocity because I only want to take the polarity of the contact normal into account if you want a more mathematically pure way to do this you can do it with the dot product but this is a nice little hack and finally I'll multiply that by 1 minus our contact time this gives us the situation as if the dynamic rectangle intersects with the static rectangle its velocity is altered as such that it can't penetrate the static rectangle at all the nice bonus side-effect of this is we don't alter the velocity in the opposing axis to the one that we've come into collision with which gives us the ability to slide along the edge of the static rectangle so let's take a look well my sauce rectangle some velocity and we see when it came into collision it now starts to slide nicely along the surface let's try it along this edge too we're no longer in a situation where the rectangle is getting stuck in the static rectangle I can come back off it nor do I lose velocity in the axis I'm not in collision with which means I can have a character or an object and run across the top of the rectangle for example very nice I've gone ahead and added a bunch of rectangles to our playground let's take a look so here I've got the player rectangle in the top corner and we'll try it in different configurations I've got two large overlapping rectangles forming this plus shape and it seems good against the inner corners here I've got a little spurious rectangle sticking out and we can quite happily see that the player rectangle collides against both and doesn't allow any further movement this is what we would expect at the bottom I've got a scenario where I might have something like a character running across a set of tile objects so I'll pull the object over here it's good gets very fast very nice let's go back try again and you'd be fooled into thinking that well we've done it this is easy enough the problem we've got is when I attempt to slide in the opposite direction it just doesn't like it what's going on here it's as if the player objects is getting snagged on the corners of these tiles and this is quite an interesting bug but it's one that's vital that we squash because we can't just have games with our characters always running in the same direction it's also quite a complicated bug to work out and it's bugs like this that give collision detection a reputation for being hard you think we're done with the complicated maths and physics and then all of a sudden you get a nasty bug like this the problem is the order of testing is insufficient when I've constructed the rectangles for that platform at the bottom I've constructed them in this order in our vector as the player object is moving along the surface it's being affected by velocity in two directions it's being moved along but there's also gravity pulling it down this means as each frame is progressing we're actually checking for a collision of the player object in a location like this and we can see it collides with the tile that it is sat upon and it gets resolved appropriately it gets nudged back and it's moved along it's exactly what we want then we hit this situation that's an edge between the two tiles the player object is tested against the tiles in the order that they were put into the vector so it's tested against number one there's no collision nothing to worry about test it against number two it gets resolved appropriately its velocity has changed so that's put it in the right location then it gets tested against number three there's no collision anymore the velocity was resolved with square number two and so moving in this direction things work as intended when we're moving in the opposite direction the same applies gravity is pulling it down and the character has a leftward facing velocity but we check against the order the tiles are stored in the vector so the first thing we'll do is check collision against this tile well in this instance the collision has resolved to push the tile this way that's okay I suppose but it means we've not traveled as far left as we should have done then when we check against tile number two we correct vertically at high frame rates this gives us the impression of just simply sticking at the corners of tiles at low frame rates what you may see is we move across the tile at the expected velocity and then we take a sudden slowdown as we go over that transition it doesn't move smoothly to compensate for this we need to check collisions in order of their proximity from the source rectangle and to determine the proximity we need to have calculated the collision there's a bit of a chicken and egg thing going on here so clearly the first thing we should be checking against in this instance is tile two and then potentially tile one and then tile three since our array intersect function returns a collision time we can assess the collision times for all of the rectangles that were testing at one instance sort them and then perform the collision resolutions in the sorted order and as soon as you mentioned sort people start to groan because you think well hang on that's going to be really computationally intensive and to be fair those people would be correct however we can do a broad phase pass first to determine which tiles were likely to be in collision with in my little example here I'm testing the player rectangle against every other rectangle in the scene and it's happening quite fast and we don't notice any difference but if you're showing potentially a thousand tiles on the screen and you're checking against all of them there's literally no point your framerate will drop to nothing so we need a way to quickly discount tiles that we know we're not going to be in collision with but first let's deal with our sorting problem and I'm simply going to brute force this typically this is something you would hide away and yet another layer abstraction but I'm going to keep it open here so we can understand the algorithm the first thing I'll create is a vector of pears now pear is just a very quick and convenient data structure to hold to items of data in this case it's going to hold an int and a float and when I detect a collision instead of resolving it I'm going to store into my vector the index of the rectangle I collided with and the contact time I'm then going to use the standard sort function from the standard library which has a quick little lambda function in it to sort my vector of pears based on the contact time so the lowest contact time will be resolved first now I'm going to iterate through this sorted vector of pears this time calling again my dynamic rect versus rect function but passing in the index associated with the pear I'm currently processing this is clearly redundant and I'm hoping you can see there are ways to tidy this up when you're dealing with a selection of rectangles being tested for collision at a time now I know the time colliding with the rectangles in distance away from the player rectangle I can resolve them appropriately so a quick recap we do a first pass of the collisions to work out what is the appropriate order the collisions need to be performed in we sorts the results to make sure that we're dealing with the closest collisions first and then we actually perform the collision resolution by adjusting the player object velocity so let's take a look so as before it doesn't affect our normal way of performing collisions that seems ok and I can move the player to the left and I can move the player to the right left and right and we see we don't now stop at the corners of the tile gravity is inferred because I'm holding the mouse button below the row of tiles but there is one final little problem this looks all well and good but when I release the mouse button it stops on the next corner what's going on for that frame the velocity in that direction is being instantaneously set to zero we don't notice it when I hold down the mouse button because each frame we reset the velocity based on the mouse's location this took quite a bit of debugging to figure out but the answer lies here and you should always be aware when you're dividing numbers there's a potential here four divided by zero now I'm quite sure there are super elegant ways to deal with that situation but I'm just going to simply check that if a divide by zero has occurred therefore resulting in an invalid number to simply say no collision has occurred at all our algorithm actually relies on divide by zero to give us the plus or minus infinity x' that we required during the Ray casting operation however in the event of the velocity being zero and we divide that by zero then the floating point standard dictates that the result is not a number it feels a bit hacky that's probably because it is but it works very nicely now we can see the character with me not holding down the mouse button is no longer prompted to stop when it hits the corners of the tiles I just wanted to try this one out just to make sure yes there we go very nice now as usual I always provide the source code for every video that I make and in this instance the source code is a little bit different to the video code in that I've wrapped up these functions in a convenient to use way and the a lot more comments too so if you've not fully understood this video do have a look through the source code and you'll see that I've also included a way to know which rectangles you have collided with this could be very useful for example if you wanted the behavior to change depending on what you have become in collision with but it's also useful to know in case you want to handle the collision response differently depending on the side of the rectangle you've touched I've got two little notes I just want to finish the video off with if you've still constructed your world using tiles then it makes sense to extract each solid tile as a rectangle and use it in the algorithm and I briefly mentioned that it would be inappropriate to test your moving rectangle against every possible tile however we can exploit some of the properties of tile grids that I showed at the start of this video to determine an appropriate region of tiles to select in order to generate rectangles from here in green I have my sauce sprite on one frame and because I know the velocity of that rectangle I can determine where it's going to be in the next frame because I know the position of the rectangle before and after the movement I can surround this with one large rectangle and I can use the truncation properties that we discussed earlier in the video to determine a far smaller subset of tiles which are the only possible candidates for this collision in practice this subset will be much smaller than your overall tile map and this is a great optimization you must perform if however your level is constructed out of arbitrary rectangles then you will need a different spatial separation structure in order to optimally cool the rectangles you needn't bother checking and I think this will be the topic of a future video and so there you have it quite a tangled video this one but nonetheless I feel quite important we've handled pretty much every possible type of rectangle collision that there is it's important to remember to choose the most appropriate form of collision detection for your application now this may be the first of couple of videos regarding rectangle collisions because it might be interesting to look at now dynamic rectangles versus dynamic rectangles and how we can shift mass about like we did with the programming ball's videos regardless the source code is available on the github if you've enjoyed this video give me a big thumbs up please have a think about subscribing and I'll see you next time take care

Channel: javidx9

Views: 120,189

Keywords: one lone coder, onelonecoder, learning, programming, tutorial, c++, beginner, olcconsolegameengine, command prompt, ascii, game, game engine, pixelgameengine, olc::pixelgameengine, rectangles, collision detection, collision resolution, overlapping, tile collision, platform games, 2d games

Id: 8JJ-4JgR7Dg

Length: 54min 43sec (3283 seconds)

Published: Sun Jul 12 2020