Programming Balls #1 Circle Vs Circle Collisions C++

hello in this video we're going to be programming balls now yes let's get all the giggling out the way now and I'll show you what I mean when I say balls I really mean they're two D equivalent circles and in this video we're going to be looking at building a collision and the response engine for circle circle interactions so for example in here you can see I've got some circles in the console I can pick up a circle and I can move it around and we can see that it interacts and collides with the other circles in the field the red lines indicate that two circles are in collision and we can see quite happily that circles can push circles in larger chains in addition to just the static responses we see here we're also going to add dynamic responses so by giving the circles some rudimentary physics we can get them to interact with accurate collisions well I say accurate I really mean approximate collisions and we also consider this wrote be a complete physics engine because we're not going to be considering the rotation or angular velocity of the circular objects in this simulation the larger the circle the bigger its mass so if we take a small circle say this one for example and a miss it's a large one at the bottom it bounces off with little effect on the largest circle however if we do it the other way around take the big circle and hit the little one there's a considerably bigger impact now we can impart lots of energy into the system and watch it come to a nice stable conclusion now it's my intention to do several videos while we keep adding to this basic engine because circle versus circle collisions are useful in not just games with also simulations and you'll be surprised where else it can be useful we might see some of that later and there's no getting away from it with these sort of things we need to do some maths however I hope to demonstrate the maths isn't really that complicated and in fact to do this particular program is only a handful of lines of code as usual we're going to use the one line code at console game engine to do the visualization and user input which is a class that we override to particular methods on the on user create which loads the resources and the on user update which is performed once every frame i've subclass the console game engine with a class called circle physics and crater an instance of it and I'm going to construct the console to be 160 characters wide by 120 characters tall where each character is 8 by 8 pixels you may notice this looks a little different from the previous videos because I've also tried to capture the error I've noticed that some of you when you're trying to create consoles on displays which are too small for the size that you're requesting you're getting a rather cryptic error message this should help you out I should also say that over the Christmas break I've made some small changes to the console game engine nothing will stop it being backward compatible with all of the other videos I've just added more features and we'll see those over the coming videos I've touched on physics on quite a few videos already particularly the asteroids game the flappy birds game and decode it yourself worms series so I'm not going to go through all of the basics of kinematics again however most of our objects here are going to be a circle and a circle is represented by a point which we'll call px and py circles also have a radius but I'm also going to add to my circle object a velocity vector VX and V Y and for completeness I'm also going to add an acceleration vector ax and a Y and as before if we integrate the acceleration vector over time we get the velocity and if we integrate the velocity over time we get the position so let's start by creating a structure that represents the circles I'm going to call it ball because I reckon most of my demonstrations will involve some sort of ball physics so I'll add the position vector the velocity vector and the acceleration vector also at the radius you'll notice I'm using floating point for all of these and I'm also going to go ahead and add an integer which is the ID and we'll see why that's useful later on before we get stuck into all of the physics and collision code let's just draw the ball to the screen all of the balls here are going to be represented with wireframe models because the console game engine provides the drawer wireframe functionality and if you remember this is a vector of of floats so the each per contains an x and y coordinates and it will link all of the coordinates together with straight lines so if we want something that represents a circle we've got to build up a circle out of straight line segments we only need one model of a circle because we'll create it as a unit circle and we'll scale it accordingly depending on the radius we'll create the resource in the unused create function so I'm going to start by adding a single point to the center of the circle each circle is going to consist of 20 segments and I'm going to use our old friends cosine and sine to create the x and y coordinates of the points that lie on the circumference of the circle around its middle point of course and because model circle is a vector I can simply just push back the new groups of coordinates our ball simulation will contain many balls so I'm going to create a vector to store them all in and I'm also going to add a utility function to make it more convenient to add balls to this vector so here I specify the location and I set the velocity and acceleration vectors to zero so he's not going to move I'm going to set the ID of the ball based on the current size of the vector so as we add more balls to the vector the ID increases meaning each ball will get a unique ID I'm making an assumption that will never remove balls from the vector and once the ball has been set up we'll put it in the back of the vector so let's add some balls to the simulation for convenience I'm just going to throw in a default radius variable in case we want to change this later on and I'm going to add two balls based on these screen positions they'll be in the middle of the screen are vertically but they'll be offset to the left and right horizontally drawing the balls is very simple as usual the first thing we'll probably want to do is clear the screen because we always want to start from a blank canvas and to draw the balls I'm going to create a little for loop that automatically iterates through all of the elements of the vector and we're going to use the model of the circle that we've created now remember that's a unit circle so we're going to scale it I'll take the current ball's position to offset the wireframe model and if you remember in the worms game the circle actually has a line going from the middle point to the edge of the circle and this we can use as an indication of the velocity or the direction that the ball is traveling in of course we don't want to move this line around manually what we want to do is rotate the entire wireframe model and we can do that quite easily with the atan2 F function using the ball's current velocity components in the y-axis and in the x-axis finally we want to scale the ball by its radius and we're going to draw it as white solid pixels let's take a look so that we have the screen with two balls they look a little small I'm going to make them bigger there we go bigger balls stop giggly let's start with a rather naive implementation of collision detection ie we're going to test every object against every other object so I'll create two little four loops which automatically scroll through the vector of balls and the first one is going to represent the current ball the second one is going to represent the target ball now there's one thing to make sure and that is that we don't test the ball against itself because it will always collide with itself and this might cause interesting results in the physics simulation so it's important that we filter out self collisions so I'm going to use that the IDS that we specified in order to test for this and if the IDS are not the same then we know that we're not testing a ball against itself so the first thing we should check is have the balls actually collided and the way to do this is to see if they overlap and this is quite simple trigonometry because they have overlapped if the sum of the radiuses of the two balls is less than the distance between their centers so we'll calculate this distance and use this radius and this radius and if we know that this condition is true where a distance is less than the radiuses sum together then there is an overlap the balls have collided and in fact we can be really precise by also suggesting that we can tell when the balls are just touching - I feel that knowing whether the two balls overlap is quite a useful utility to have so I'm going to wrap it up in a little lambda function do circles overlap and the parameters we're going to pass through to this lambda function are the coordinates of one of the balls we'll call that x1 and y1 we also need its radius - so r1 then we need the other ball which is x2 y2 and r2 d2 now calculating the distance I could use Pythagoras theorem and I am going to but I'm going to modify it slightly to remove the square root because the square root can be quite costly to compute and we'll be doing a lot of them so normally we would do it like this we would take the difference between the two x-coordinates and square them add it to the distance between the two y-coordinates and square them and we would check that that distance is less than the two radiuses some together as we've just seen in the slides but we can remove this square root if we also then square the radius summation together and instead of doing the square root we look at the absolute value in this case using the fabs function the floating point absolute value which removes the sine will check if the balls are overlapping or touching because if that's the case then we want to respond to that collision so my lambda function is simply going to return a boolean as to whether that condition is true now we can add another clause to our collision detection we can check to see if the circles are in fact in conflict with each other so we'll add the x coordinate of the ball we're currently operating on and it's radius and the same for the target if this condition is true then we've got a collision even though I'm making an attempt to optimize the code now I don't consider it the most important priority and in fact some of the pros out there will notice actually there's a lot more scope for optimization in this program but I want to keep it simple so people can follow along now that we have determined that the balls have collided what can we do about it well the first thing we must do is resolve the static collision and this is what makes the balls obey the laws of physics one bolt cannot exist inside the other we have to resolve this and a sensible way to resolve this is to displace both the ball and the target away from each other by half the distance they overlap so in this case we would want to move the ball slightly this way and the target slightly this way and if we look at the distance at which the overlap holds put a little marker in there let's call that D then the length of this displacement is d over 2 now you may also notice that I've not drawn these balls deliberately actually aligned and that's to make us think about vectors from the Gecko so this displacement has a direction it doesn't just go in the X or the y axis it goes in both and we can determine what that vector is simply by creating a line between the two centers of the objects once we know this vector we can normalize it and use this vector to determine the direction of the displacement so let's first work out the distance between the ball centers now this time there's no getting around it this is straight up Pythagoras theorem square root of the difference between the x and y's of both balls calculating the overlap is the same as our lambda function before but we want to do something a little bit different this time so we can see it as it's the distance between the two points subtracting both the radiuses of each ball however we only want half the overlap because that's how much we're going to displace each ball so I'll put a multiplied by half at the front to resolve the static collision we completely ignore all of the rules of physics we will physically move from one frame to the next the position of the balls they can never overlap so we're going to alter the balls position directly and the current ball will naturally move away from the target ball so we're going to put a minus sign here and it's going to move away by the amount of overlap which is currently half the overlap and it's going to do that in the direction of the vector created between the two Centers of the balls but we need to normalize this so sensible we can just do that by dividing by the distance between them I spell it right though it follows that the Y is very similar to we just look at the Y components of all of the objects involved well we must also displace the target ball as well and it's exactly the same formula just a different object but the target ball will have to be displaced away from the collision so we will add to it instead facility that means we can interact with the ball on the screen I'm going to add a private variable to the class which is a pointer to the currently selected ball we'll just initialize that to null pointer to begin with nothing is selected and I'm going to make it so if the user left clicks on a ball they can basically pick it up and move it around so we'll respond to the left mouse button being pressed which on my system is element zero of the mouse array provided by the console game engine the first thing I'll do is just set this to null pointer because they may click somewhere there isn't a ball and in which case we want it to unselect any previously selected entity to determine if any of the balls have been selected we're going to have to scroll through them all and check their positions against the mouse cursor as we did with the do circles overlap lambda function I'm going to create another little utility lambda function because it might come in handy it's a very similar one but this time instead of checking two circles overlapping it checks whether a point exists within a circle it's much simpler this time so for each ball in the vector of balls I'm going to make that test against the balls position its radius and the current Mouse position in screen space if this function returns true then I'm going to set the selected ball pointer to the address of that ball I'm also going to break then so we don't go and test unnecessarily over the ball we've already hit one it'll do because we're implementing a drag-and-drop like behavior we also need to consider what happens if the user releases the mouse button so we'll check the released flag in this case all we want to do is simply set to the P selected ball pointer back to null again so nothing is selected now I know it's no longer the fashion to use pointers anymore or so I'm told but I quite like the fact that you get two functions for the price of one out of a pointer firstly it points to something interesting and secondly if it sets a null pointer though we know that the point is not valid and I like the fact that we can leverage the validity of a pointer as part of a functional program now we've handled the mouse button being pressed and we've handled the mouse button being released the dragging option requires that the mouse button is held down and by using the validity of the pointer to make sure everything's okay ie were checking if it's not a null pointer we're just going to directly set the PX and py values to the mouse coordinates let's take a look so now I should be able to pick up a ball with the left mouse button and if I push it into the other ball on the screen we can see they don't overlap and they do what they can to avoid overlapping and try it the other way around let's add a few more balls I'm just going to comment these out because they might come in useful later on when we're looking at the dynamic resolutions let's add 10 balls to the screen in random locations what we can see is the balls can interact with multiple static collisions at the same time we cluster them all together we can create chains of balls that push each other a bit like a Newton's Cradle we haven't even considered physics yet and I can already see many uses for this the first thing that comes to my mind is in the game command & Conquer let's see you've got a whole selection of units and you're trying to get them to walk through a narrow opening well now they're wrong to overlap and they'll tussle with each other to form an orderly queue until they're all on the other side we're almost ready to start handling the physics but we only want to do physics for bosses have collided so we're going to record PIRs of colliding balls that we'll deal with for the dynamic collision later on I'm just going to create a vector of pairs of pointers to the two balls and so if two balls have overlapped therefore they have collided I'm just going to add the addresses of those balls to this vector and this means once we've worked out where all their collisions have occurred we can then deal with them with a reasonably accurate approximation to physics by having a vector that contains just the colliding objects we can use a for loop to automatically scroll through these colliding pairs and update them with approximations to physics accordingly we'll come back to that in a minute but first I'd like to draw which balls are in contact with each other and because we have a vector of collisions this is very simple too we just scroll through the vector and we draw a line from the center of one of the colliding pairs to the center of the other and I'm going to draw it as a red line I don't need to empty this vector because when this function returns the vector goes out to scope and it'll be destroyed let's take a look so if I pick up a ball and force it into collision with something else we can see there is a collision line indicator this is quite nice because we can see in certain situations there are trees of collisions that need to be resolved before we can emulate the physical response to a collision we actually need to give the ball some physics now so we need to update the velocities and positions accordingly I'm going to do this just by scrolling through them again in an auto for loop and this is code we've seen time and time before in previous videos I'm going to add in the ability for the balls to rotate around the screen if they go off one side they reappear on the other it's a crude approximation unlike asteroids the ball will simply disappear we're not going to wrap the drawing routines as well and because we're dealing with floating-point numbers and at some point I would like the balls to actually stop moving if their velocity approaches zero I'm actually going to hard-code that in so if the overall scalar speed of the velocity vector is less than no point not one I'm going to clamp it to zero in much the same way as with the static collisions we needed to pick up the ball and push it into others to test the dynamic collisions we need to give the bolts and velocity so I'm going to use the right mouse button to provide a cue like on a pool table to hit the ball in a particular direction at a certain speed I'm going to use the right mouse button to do this and I can use the same code I've already got here because I only want to manipulate the ball that I've currently clicked so I'm just going to add this in using an oar and on my system mouse one is the right click if I'm clicking and dragging with the right mouse button I don't want to move the ball so I'm not interested in an equivalent health state but I am interested in the release state because at this point that's where I want to apply the velocity to the ball and so here if I release the right mouse button I make sure that the ball is indeed selected and I set its velocity vectors directly and in this case all I'm doing is creating a vector from the mouse coordinate on the screen to the center of the ball and multiplying it by five this five is really just an empirical guesstimate just to give the user a chance of understanding how much velocity they're applying to the ball I'm going to draw in well a pool cue or a snooker cue which is just going to be a line from the selected balls current Center position to the mouse coordinates and we have to draw that in blue pixels so let's take a look so as before I can pick up the ball with the left mouse button but now if I hold down the right mouse button we can see a line gets drawn from the cursor to the center of the object that I've selected and if I release the right mouse button the ball moves with velocity and it moves in a rather interesting way because we've not got any form of dynamic collision response but what we see if the static response is still working quite nicely let's set another one off as well there we go now in this system there's no friction the ball will just keep going forever and ever and ever and ever it is really nice but not having any drag will make it quite complicated to understand what's going on so I'm going to add in some drag by setting the acceleration component of the ball to be a proportion of the velocity in the opposite direction so now if I select a ball we can see over time it slows down its give it a little bit of a velocity and it should come to a nice stop and we've capped the velocity to actually clamp to zero and you can see when that happens because the velocity vector becomes 0 the atan2 function which we're using to rotate the wireframe model will just default to zero degrees and we know that because the line is horizontal you can seen right now the velocity vector changes the rotation of the wireframe model we're now in a position to work out dynamic collisions this is where the fun starts handling the dynamic resolution is a little bit more tricky so let's just have a look at what comes into play during this collision firstly let's assume that this ball on the left is moving with a velocity in that direction and this ball on the right is moving with a velocity in this direction we know that the balls don't overlap and we can determine two useful characteristics firstly if we draw a line between the two center points and find the normal to that line ie align ninety degrees to it try and draw it as straight as I can here make sure that's 90 degrees this tangental line that we've just done because it's a tangent to the circumference of the circle effectively represents a solid object for a ball to bounce off I'll just label that one tangental and the line normal to the tangent I'm just simply going to retain the name normal now in a perfect world and assuming that the target ball was at rest I had no initial velocity when this collision occurs we would expect the target ball to travel along the normal vector and we would expect the original ball to travel along the tangential vector ie they'll always be 90 degrees between the two balls as they disappear along their trajectories I think this is true for all cases except for when the original ball is also traveling along that vector ie the balls collide absolutely Bob on dead-center so from this we can assume that we do have something called a tangental response I'll just put this velocity vector back in the problem is we live in the real world and our objects have mass and therefore they have momentum and the lore about conservation of momentum suggests that the momentum of this whole system before the collision should be the same as the momentum after the collision or what's nice in our 2d circle scenario is we really only have to consider momentum in one dimension and we can use the momentum equations to influence a normal response and so each ball will be affected along the normal and tangential vectors so let's code this in the first thing I'm going to need is the distance between the two balls I'm going to needs accurately now I could have stored this in the vector of collisions before when I've already calculated it but I didn't I'm recalculating it here from this of course we can develop a normal vector simply by drawing a line between the two center points and we're going to normalize it with the distance calculating the tangential vector is very simple it's just the normal vector except we flip the y axis and the x axis and make one of them inverted now the tangental response can be very simply described as the dot product between the balls velocity vector and the tangential vector ie how much of the velocity in each direction is going to be transferred towards the tangent and then we can update both the ball and the target balls velocity in this case we're just looking at the tangental response first let's see what happens and don't forget that the result of a dot product is a scalar value so we're taking that scalar value and multiplying it by the normalized tangent vector let's take a look so here are some balls and I will fire this one at that one and we can see it deflected off it at 90 degrees is what we'd expect it's moving along the tangent so the tangental response seems okay although it just doesn't seem very realistic it doesn't seem to impart any energy into the target ball in fact it treats the target ball as if it were a solid object so let's now consider the normal response to in exactly the same way will create the dot products so how much of our velocity vector gets attributed along the normal vector as always Wikipedia is a great resource for all things games programming and it does have a great article on elastic collisions and it shows us here the equations that we will need to use in order to calculate the velocities after a collision assuming the collision is elastic of course now this being the one lone coda Channel I would usually like to try and derive these equations from first principles and so I did but I've decided not to include it in the video simply because it is quite a lot it's quite demanding there's a lot to do so if you fancy the challenge you can have a go at doing that or you can just use the equations directly from Wikipedia but these equations included a new variable that we've not accounted for mass so let's add that into our ball structure which is going to be a floating point value and I'm also going to update our add ball function to set the mass and I'm going to set the mass based upon the radius I'm going to multiply it by 10 therefore the bigger the ball we can assume it's heavier although strictly speaking this is a rubbish way to do this because the density of the ball would have to change for this to be true you will notice that our dot product normal values are used in this equation and these equations yield to more scalar values which we can use to scale our normal response and so the final balls velocity vector is simply the sum of the two responses and so here we can see the tangental response simply summed with the normal response let's take a look so let's add a velocity to a ball and it behaved like a Newton's Cradle in that case let's try a bit of a more angled deflective shot very nice these collisions look and feel legitimate let's now quickly modify our own user create function to add balls with random radiuses and also random masses you see two big ones that's good so let's tie this little tiny one against this big one here you see it deflected right back and bounced and barely moved the big one that's how I would expect it to behave very nice now in the interest of full disclosure I will say that this approach seems a little bit laborious and in fact if we go back to the same Wikipedia article it gives us two functions that calculate exactly the velocity vectors we need for the scenario that we've got so this is the interaction of two circles but you'll see the mass is much simpler well simple can be deceptive and really what it boils down to is that the Wikipedia version is a cleverly deduced version of the same maths where they've looked at all of the redundancies and got rid of them and they've broken it down into just its purest most simple form I'm going to include this in the source file but will be available on the github but there is no functional difference between the two and today a very simple circle versus circle collision and dynamic response system this video is just the start of a largest series on collision detection systems and we'll see in the next part of this series how I implement a pool game now this has been the first video of 2018 and I'm going to do things a little differently this year firstly I'm not going to be producing a video every single week I'm going to aim for every two weeks and I might do smaller little user update videos and featurettes in between and I'd also like to get a few more live streams done regardless all of the code for this video is available on github you can chat with me and lots of other programmers on the discourse server you can follow me on Twitter it's at Javits x9 if you've enjoyed this video a big thumbs up please have a think about subscribing and I'll see you next time take

Channel: javidx9

Views: 93,595

Keywords: one lone coder, onelonecoder, learning, programming, tutorial, c++, beginner, olcconsolegameengine, command prompt, ascii, game, game engine, physics, balls, collision, response, dynamic, static, circles, 2d collision solver, vectors, maths

Id: LPzyNOHY3A4

Length: 32min 29sec (1949 seconds)

Published: Sun Jan 21 2018