Circle Vs Rectangle Collisions (and TransformedView PGEX)

hello and the one loan coder channel is back after the small christmas break that i desperately needed and i thought we would start 2021 with a really fantastic algorithm video let's take a look whether you're building games or simulations collision detection is really important to get your head around and it's so important in fact that quite a number of videos on this channel have been dedicated to nothing but collision detection of different forms and it occurred to me that throughout all of these videos the one form that we haven't covered is perhaps the simplest it's circle versus rectangle collision detection with the old console game engine platform game we did rectangle versus rectangle in a tile-based world and that was fine we've even done arbitrary polygon collisions we've done balls colliding with other balls start giggling and i even demonstrated a way to perfectly handle rectangle versus rectangle collisions and so i felt it was rather remiss of me to miss out this essential yet powerfully and beautifully simple algorithm now i know some of you will be thinking oh but javid we expected mmo part four well don't be too disappointed because this is vitally important to the mmo part 4 video i was prototyping over the christmas break using the raycast world to demonstrate the client server setup that we've created so far and even though as an end result that's exactly what i want as a vehicle for demonstrating the algorithms it really doesn't work at all there's simply not enough field of view you can't see enough of what's going on so instead we're going to create this 2d lightweight top-down framework which we'll see in the rest of the series the demonstration program we'll quickly create today is going to demonstrate this technique and it's also going to use something called a peg x which is a pixel game engine extension in this case it's a transformed view peg x which allows us to manipulate all of the drawing to the screen it scales and offsets it for us and we can see by zooming right into the collisions that it really is absolutely perfect it's spot on isn't that really nice and wonderful this highlighted area is the area of search so we're only going to try testing for collisions with the circle and the tiles in that area now my tiles are unit size and my circle is unit circle but they needn't be the tiles could be arbitrary size rectangles i can press the spacebar and we can automatically follow the object we can still change the zoom with the mouse wheel and this will be a nice and quick video because this technique is really simple but it has countless advantages you can't get caught on the edges if you've got an ai character some description and your ai mapping's a bit dodgy it doesn't matter it can bump into the corner of things and sort itself out see look i'll just position it here and i'll move right see it automatically squeezes itself out the way it's an absolutely essential form of collision detection for your toolbox now the reason we're going to need this for the mmo is we can see the entire world we can envisage a situation where the other players are going to be circles in a world of tiles like this and we'll be able to see them moving around when i was doing this with the raycast world extension everything was in a first person perspective you just couldn't see what was going on so this is a much better approach and it's important that we know how to do this before carrying on with the mmo series so let's get started i'm willing to bet that if you've ever tried to create a two-dimensional game at some point you have considered circle versus rectangle collisions and i'll go even further and say that when you did you probably didn't see the forest for the trees one popular method is to take your circle and your rectangle but to treat your circle like another rectangle and then using a technique a a b b axis aligned bounding box you instead solve rectangle versus rectangle collisions and this is fine in some circumstances the only problem is the corner of your circle is now a rectangle so the circle can effectively collide with thin air another approach i've seen people try is to take the circle and the rectangle and then think to themselves well i'm really clever and i'm going to use math so if i represent the corners of my rectangle with the same radius as my circle and i join up these edges and then i reduce my circle down to a single point and then i can work out which particular sector of the rectangle is my point going to be lying in and i can do an appropriate static resolution in order to try and resolve all of this mess well this is rubbish don't bother instead we're going to exploit one of the best properties of a circle and i'm going to define my circle as a point with a radius r come to think of it that's how everybody defines a circle and the nice thing about a circle defined this way is that all of the points along the circumference or the perimeter are the same distance away from the point in the middle this is a uniquely circular property and one we will exploit to implement circle versus rectangle collisions just before we jump into the collision side of things i want us to be familiar with a term called clamping and given two numbers in this case 10 and say 35 i can take a third number let's say n and clamp it to somewhere within that range so if n was 17 17 sits somewhere in the middle that's fine however if n was 8 well n lies outside of our range so we're going to clamp it to 10. i.e the minimum value n can have is the bottom end of our range therefore i can say that n is equal to the max of 10 the bottom of our range and n which will only allow n to be larger than or equal to 10. at the same time i want to clamp the upper end too so i can say n equals the minimum of the top of our range in this case 35 which means n must be less than or equal to 35 we can actually implement this as a one-liner because it doesn't matter which order we perform these assignments in so i'm going to replace this n with all of this which means i've now got n equals the maximum of 10 comma the minimum of 35 comma n therefore for any value n it must lie between 10 and 35 inclusively clamping is a very useful thing in fact in the most recent versions of c plus it even exists now in the standard library as standard clamp but i'm going to keep it open like this so well we're learning something so why is clamping useful for rectangle versus circle collisions here i have my circle defined as point p and radius r and i have my rectangle defined as x and y as the top left and the bottom right is going to be x plus width and y plus height implying of course that this length here is width and this length here is height my circular object is also associated with a velocity vector the direction it is moving so i'm going to throw that in it's moving in a direction towards this tile i'll just extend that velocity vector so we can see the trajectory the circle is going to take we can see quite clearly at some point it's going to collide with this tile but notice that point of collision is not on the velocity vector in this case it isn't exactly the three o'clock position of the circle it's aligned with the x-axis in fact that point of collision is the closest point that exists within the rectangle to the center of our circle if i just back the circle off a little bit so that they're not touching we can see the closest point on the rectangle is still directly in line with the x-axis i want to take the distance between the middle of my circle and the closest point and because of that unique property of circles i also happen to know the distance from the center of my circle along that line to the edge of my circle it's simply my radius what i observe here is the circle is not in collision with the rectangle and the length of the line from the center of the circle to the nearest point on the rectangle is greater than the radius of my circle let's consider the case where the circle is now very close to the rectangle in fact it clearly overlaps the nearest point of the rectangle to the middle of my circle is clearly less than the radius of my circle therefore if the distance from the center of the circle to the nearest point on the rectangle is less than or equal to my radius of the circle then i am in collision and i'm in a situation where i want to resolve that collision statically i want to move the circle away from the rectangle so it no longer overlaps well again due to this unique property of the circle i happen to know how much i'm overlapping it's my radius of the circle subtracted from the distance of that vector to the nearest point i'll label that overlap therefore to resolve this static collision i need to move my circle back away from the rectangle the same distance as the overlap this two is very simple because my d vector is already normal to the side of the rectangle i've collided with so if i invert it and normalize it i get a unit direction vector in the direction i want to displace my circle i can simply take this unit vector scale it by my overlap and use this new vector to displace my circle so that is no longer overlapping the rectangle so what has this got to do with clamping well perhaps some of you already realized if i take the midpoint of my circle anywhere in this 2d space for now let's just say the x-axis so in this direction the nearest point on my rectangle is defined by the size of my rectangle i've effectively taken the x location of this point and clamped it to the bounds of the rectangle and what i do for x i also do for y so just to recap if we want to check if a circle is overlapping a rectangle we need to create a vector to the nearest point that lies on that rectangle to our circle here i feed in the midpoint of our circle into our clamping equations which gives me a vector that represents the nearest point somewhere on the surface of the rectangle to the middle of my circle we can check to see if the magnitude of that vector is less than or equal to the radius of our circle which tells us if a collision has occurred we can then update our circle's mid position by normalizing our nearest point vector to give us a normal vector of size 1 we can flip that so it's away from the rectangle and we can scale it by the amount we've overlapped and it's as simple as that that will give us these lovely accurate collisions between circles and rectangles now since this is the first video of the year there may be some people that are new to the channel not that familiar with what goes on here i'm going to be using a tool called the olc pixel game engine which allows me to very simply draw pixels to the screen on this channel i try to show things in such a way that you can port them and implement them in other languages so don't feel that because this is a c video using the olc pixel game engine that that's the only way to do it and so as usual i'm going to be using a blank pixel game engine application here i've created a class called circle versus rect which is derived from the pixel game engine and the user has to override two functions on user create is called once at the start of our application and on user update is called every frame in our main function i'm creating an instance of this class i'm using the construct function on the object to create a 640x480 pixel game engine where each in-game pixel is 2x2 screen pixels and then i'm starting the engine now i mentioned at the start that this particular demonstration is using what's called a pixel game engine extension this is a new one that i've created over the break called transformed view and the purpose of this extension is to wrap up all of the things that we usually spend time doing by hand in videos so if we've got a world that we can pan around and zoom in and out of well normally we would write the code for that but now it's all captured within this extension and i'll quickly demonstrate just how simple this extension is to use i'm going to create an instance of a tile transformed view object the extension provides two types of transformed view one is a native transform view which is just raw and the other is this tile transform view which offers convenience functions when working with tile based environments for example in on user update i'm going to clear the world to very dark blue and then i'm going to call the draw circle routine of the transformed view not the pixel game engine but the arguments passed to this draw circle function are exactly the same as those that you would pass through to the pixel game engine so this is just for a test i'm going to draw a circle at the origin of our world i'm going to give it a radius of 20 pixels and that's all i'm going to do in on user create i'm going to initialize the transformed view with some starting parameters i'm going to give it the size of the screen and i'm going to give it the definition of how many screen pixels constitute one tile in our world i've just added in this return true to one user create so it doesn't close down the application prematurely let's compile and take a look what we see is a very large circle but not much else of any use it would be very useful if we could pan and zoom around this world and this is exactly what the transformed view objects are for we've covered panning and zooming in a separate video and we've used it in quite a few for panning i'm going to be sensitive to the middle mouse button being pressed released and held and you can see that we call methods directly on the transformed view related to start pan update pan and end the pan and all we need to pass in is the current mouse position the transform view will handle the rest for us we can also use the mouse wheel to zoom so if we scroll with the mouse wheel we get a positive or a negative number and we can tell the transform view to zoom at a particular location so when we're zooming in i want everything to multiply by two and when we're zooming out everything is divided by two it will zoom centered around the mouse location so this gives you that nice intuitive feel like the one you get in google maps so let's run the same application now we've added panning and zooming we can see our big circle i'm going to hold down the middle mouse button and i can drag the world around which makes us drag the circle around in fact i can zoom out now and drag things around bear in mind i'm not moving the circle i'm moving the world transform view provides analogous functions for all of the pixel game engine functions so you can use sprites text decals drawing lines and even some of the new bonus features we've added over christmas quite happily our circle starts off really huge because we've defined our world as having tiles of 32 by 32 pixels well when it's a tile transformed view all of the coordinates that you specify are in tile space so effectively we're drawing our circle at location 0 0 but with a radius of 20 tiles and that's 20 times 32 pixels naturally this all assumes the zoom level is one of course anyway i just wanted to squeeze in transformed view because i think we'll be seeing a lot of it this year but let's get back to the video in question circle versus rectangle collisions i'm going to represent an object in our world as a world object struct that contains a position and a velocity and a radius so by default our radius of the circle is going to be half a tile that would mean our circle when drawn is the equivalent of one whole unit tile in our world and since i've got a definition for the object i'm going to need an actual object itself object again for newcomers to the channel it's very common for me to use ascii or text to represent in-game data now i know people have mixed opinions about that but it actually is a really convenient way to edit things quickly and so i'm going to represent the world as a string there we go where empty space in the world is represented by the period symbol and walls or in this case occupied tiles are represented by the hash i need to know the size of this world when i'm doing calculations on it so i'm going to store that in a vi 2d now you've seen vf2d vi 2d is another vector2d type except this one stores integers the vector2d types are provided by the pixel game engine in fact if you see olc in front of something that is a pixel game engine namespace so now that we have defined our object and we have defined the world let's draw them i'm going to start the object off at location 3 3 in the world and you'll notice i've given the world a boundary so our player should never be able to escape let's draw the tiled world and again this is something we've done plenty of in the past i'll get rid of this draw circle for now but now we've got the transformed view it provides some functions to help us draw things like tiled worlds because we can zoom and pan around we don't necessarily know which part of the world we're looking at at any one time fortunately the transformed view does and can give us that information so we can only draw what we can see here i request of the tile transform view to give me the top left visible tile on the screen and the bottom right visible tile on the screen of course these tiles may be far bigger than the world that we've defined so i can use the maximum and minimum functions of the vector2d type to clamp to the world size this makes sure that we can't index a particular tile in our world that isn't defined within our world string above i'm then going to create a temporary v tile variable and have two nested for loops to iterate through all of these visible tiles for each tile x and y coordinate i'm going to use that information to index into our string now we've done this on every one lone coder video we have y times width plus x this is converting our 2d coordinate which tile we are interested in using the width of the world to change that 2d coordinate into a 1d index so we can access our string therefore we can test if a tile at a particular location in the string should be visible or not if it is visible i'm going to draw its outline with the drawrect function i'm going to draw it in white and i'm going to assume that all of our tiles are unit in size now i know this is circle versus rectangle and you can use arbitrary rectangle sizes but for tiles all my tiles are going to be one by one and rather than fill them in because that looks a bit boring i'm going to draw the diagonals of the tile too using the draw line functions now notice i'm using the transformed view versions of these functions so let's take a look here we can see with not very much code now we're starting to render that string that we defined earlier and i can pan and zoom with the mouse convenient huh when we called the get top left and get bottom right functions of the transform view it's returning coordinates up here for example right now that would be negative that's why we clamped them with the vector min and max functions so we're never sort of accessing bits of world that don't exist we can zoom right out and we can zoom in to obscene levels too in fact there's no limit well there's a floating point precision limit well drawing the tiled world wasn't very difficult at all it's now time to draw our circle which will be under user control drawing a circle well we've just did that before it's quite trivial but this time i'm going to draw the circle at the location of our object and i'm going to give it the radius of our object too i also want to draw some sort of directional indicator to show what the velocity of our object currently is well firstly i want to make sure that it does actually have a velocity so i can use the mag squared function to see if that's greater than zero that will tell me if the length of the velocity vector well is anything but zero if it is then well there is a velocity to draw at which point i'll call the drawline function again and the starting coordinate of my line will be the middle of my object the middle of the circle and the ending coordinate of the line will be the middle of the circle plus the velocity vector normalized times the radius so this will draw a nice line from the middle of the circle to the circumference of the circle in the direction of the velocity vector and i'm coloring that magenta let's take another look well there's certainly a circle and we said start it at location three three and we can count the tiles in zero one two three and zero one two three down happens to be the middle of our circle i suppose it would have made more sense if we wanted the circle to line up with the tiles that we specify to be at 3.5 however i'm happy with where it is currently we can't move the circle around so let's add some player control each frame i'm going to reset the object's velocity to zero so it's not moving then i'm going to test the w s a and d keys and use the pressing to modify the velocity vector instead of setting the velocity vector explicitly depending on the key i'm adding to it with this unit direction vector this allows me to hold down two keys and move in diagonals but we've got to be careful when we're moving in diagonals in this way because in a game moving diagonals and adding the velocities like this will mean that moving diagonally is faster than moving left or right or up or down therefore i can check to see if the velocity has been set to anything at all and if it has i'm going to normalize that velocity and then scale that velocity direction vector by a constant to give us a speed and i'm going to throw in this sneakery little ternary operation that if you're holding the shift key down we're going to be moving at five tiles per second and if we're not holding the shift key we're going to be moving at two tiles per second so these speeds are relative to our transformed views tile space the act of normalizing the vector will make sure that when we're traveling diagonally in fact in any direction that we're going to be traveling at the same speed once we've got an up-to-date velocity vector we'll need to update the object's position vector now i'm going to do it slightly differently than usual i'm going to create an intermediate variable called a potential position vector which is the current position plus the velocity modulated by f elapsed time don't forget in any application that has a frame rate that frame rate is inconsistent but you want your movement to appear consistent and one way to approximate that is to use the time it took for the previous frame to elapse and right now i'm just going to set the object actual position vector to this potential position vector let's take a look there's our circle and if i press the w a s and d keys we can see the circle moves around however there is no collision detection yet it can go through the walls but we can still pan and zoom and all of this loveliness but we need the collision if i hold down shift we can see the object moves much faster at the moment though it's quite fiddly to follow the object and drag and pan with the mouse so i'm going to add in a facility where we can have the camera automatically follow the object for us to the class i'm going to add a private boolean variable b follow object and i'll set up in on user update that if the space key is pressed that we flip the value of the follow object variable if we're following the object then i don't want the mouse to be panning the screen i've left the zoom out of this condition because zooming is fine i'm going to put a little on-screen visual prompt so we know that we're in following object mode this does however mean i have to position this block of code after we clear the screen or else we'll never see that prompt there we go now we can use the transformed view as if it were a camera following a particular location i can set the world offset explicitly so let's just take a look and see how that works so there we go we've got the object moving normally and if i press the spacebar we're now in following object mode it says so at the top but we can see that it has displaced the world relative to the top left corner i think it would be more convenient if the circle was in the middle of the screen we need to adjust our offset relative to that distance in screen space but when we're setting a world offset screen space is no good to us we need to know how much is that in world space so we can use the transformed views scale to world function which will take in a coordinate and scale it to the world it won't do any offset and to that function i'm passing in half the screen size in screen space let's take a look go into follow mode and now we can see the circle is bang on in the middle of the screen and the transform view is handling the camera for us we can still zoom in and out very nice still no collisions let's do that it is of course no coincidence that i have left this gap here because when we're doing collisions we don't want to set the position of the object directly if we do that then all we've done is potentially detect collisions but we haven't resolved it as we move objects we know potentially where they're going to be if it's going to overlap with a tile then we need to change this potential position so we can set the object's actual position accurately and make sure it's not in collision this is static collision resolution we could of course and i have shown in other videos use this information to also then handle a dynamic collision response we could get the circle to bounce off the squares accurately the first problem i'm going to need to solve here is which tiles am i actually testing against it would be rather inefficient to test against every tile in the world i could have a lot of objects and a lot of tiles and if we had to check every object with every tile we could have a huge amount of computation to perform so instead it's better to work out what's the only possible region of tiles that the circle can interact with well this is defined by its current position and its potential position the world is divided up into 2d tiles and i know that for one frame my circle exists here the circle of course has a velocity so i can predict where it's going to be if it moves and doesn't collide with anything therefore i know that in reality checking anything beyond this small region is a complete waste of time the circle can't possibly interact with the tile at those locations we can easily determine this boundary by looking at the floor and ceiling of the points of these two circles so here if i take this coordinate and i truncate it i effectively find this location in my tile space this is the floor if i take the other point and find the ceiling i find this location in the 2d tile space the circles however are not just points they also have a radius and in my example here i know that my circles are the same size of my tiles therefore i know that if i extend this region by one in all directions i've guaranteed that my circles still remain within the boundary i can determine this boundary by looking at the current cell where the circle is starting from and the target cell well which tile contains the potential position these are in floating point domain and we'll be truncating by converting them to integer i can then very quickly sort these into that boundaries top left and boundary's bottom right because that's easier to scroll through this is exactly the same thing we did when we drew the world in fact it's very similar because we're also using the max and min functions on the vector2d type to clamp to our world size again and just as we did when we were drawing the object i'm now going to have two nested for loops to go through this small boundary region firstly i'm going to check is the cell at that location actually a solid cell if it is then i'm going to create a vector called nearest point which is going to represent the nearest point on that tile to my circle and this is just an implementation of the equations we saw on the slides earlier because all of my tiles are unit size the width and height values are just set to 1. once i know the nearest point i can create a ray to the nearest point which is a vector from the circle center to that point on the rectangle it's important that i have this vector because i'm going to need to get its magnitude and by comparing the magnitude of that vector to the radius of our object i can determine has the object overlapped with the tile there is a strange condition and a quick shout out to dan destine for helping me discover this last year that should the circle be directly on the perimeter of the tile then the magnitude of this ray to nearest vector will have a 1 divided by 0 somewhere in it and give us an invalid number so it's worth checking to see if the overlap value is indeed not a number we know that if we do have some overlap well then a collision has occurred and we should statically resolve it and this is the easy bit because all we're going to do is update our potential position backwards by the amount we've overlapped i think it's useful to visualize this little collision checking boundary so once i've drawn the world and before i draw the object i'm going to use a decal again using the transformed view to draw that boundary we know where it's top left and bottom right coordinates are and i'm going to draw it in a cyan colour but with a large degree of transparency let's take a look so now we can see the circle in a lighter blue rectangle that blue rectangle represents the area of cells being checked for collision and there we go we've got collision in the x-axis is certainly working just fine let's try the other side no problems at all up is fine and down let's have a look just go straight down there we go the nice thing about this collision is just how well it hugs the corners see it's absolutely spot on and we've not had to do any complicated circular mathematics it's just fine and i really like the fact that if you can clumsily crash your circle into the rectangle it will automatically align it with the tiles see very nice this means we can have tunnels which are just one tile in size and we're not getting stuck on the walls as we're sliding along zoomed out a bit too far there let's hold down the shift key and move a bit quicker in fact let's also follow the object so we can see what's going on i'm not going to win any oscars for directing in this am i in fact there is no way to make these circle enter any of the solid tiles well there is a way you may have noticed that this particular technique doesn't do any sweeping which means there is a potential as if the object is traveling fast enough i.e per frame which is traveling more than one whole tile then yes the collision's not going to work but that's a small price to pay for something which is so brilliantly and elegantly simple as this and yet gives such a satisfying result too it really really is nice absolutely spot-on precise i really like it and that's why i thought it was worthy of a video in its own right and so there you have it a nice and quick look at using a very simple algorithm to detect and handle static resolution of circles versus tiles or rectangles this technique plus the transformed view peg x is going to be quite important to understand for the rest of the mmo networking series now just as a little extra bonus the pixel game engine itself has undergone some upgrades over the christmas break i'll talk about some of the specifics of those in a later video but one of the ones i wanted to start using straight away this year was the ability to actually try these demos in real time for yourself without needing to compile the c plus plus code the pixel game engine is now compilable to webgl you can take your c plus program and just run it straight in the browser and i've provided a link for this demonstration in the uh well description below if you've enjoyed this video give me a big thumbs up please and have a think about subscribing i'll put the source code on the github come and have a chat on the discord server i wish you a very happy new year it's starting 2021 let's make it better than the last one and i'll see you next time take care

Channel: javidx9

Views: 29,578

Keywords: one lone coder, onelonecoder, learning, programming, tutorial, c++, beginner, olcconsolegameengine, command prompt, ascii, game, game engine, pixelgameengine, olc::pixelgameengine

Id: D2a5fHX-Qrs

Length: 34min 5sec (2045 seconds)

Published: Fri Jan 29 2021