Collisions Without a Physics Library! (Coding Challenge 184)

they're not colliding very often come on Collide welcome to a coding challenge today I am going to look at something that I refer to in my new version of the nature of code book which is coming out on September 3rd 2024 the first half of the book is largely dedicated to a stepbystep process of building your own physics engine there is a part of the book where I stop and look at what does it mean to use a thirdparty library there are a variety of reasons why you might want to use a physics library or not use a physics library but in the book I make the argument that a key reason to go over and use another physics library is if what you need in your p5js sketch is rigid body collisions all right let me see if I can give you a quick summary of everything in chapters 1 through five just to get us up to this point and of course you can watch all my other nature Cod videos which go through all this stuff in much more detail all right I have a P5 canvas I have a particle in that canvas that particle presumably has a position and the particle also has a velocity the velocity is a vector an arrow that's providing instructions as to where the next position of the particle should be so after some amount of time typically referred to as DT or Delta time the new position often written as position Prime equals the current position I plus the velocity times Delta time but I make the argument in the nature of code book that life is short we don't need to over complicate things we have a draw Loop in P5 one frame is one cycle through draw we can also consider that the change in time so Delta time as a simplification can just be the value one in which case we're saying the new position equals the current position plus the velocity now there's also this concept of an acceleration which is additionally a vector that changes velocity and this forms the basis of the physics engine that I walk slowly through and build and use for a variety of scenarios including the flocking system in the nature of code there's additional Concepts like the particle might have a mass it's important to note that these are all Vector quantities with an X and Y component but the mass is a scalar and there's also the concept of forces forces being some external or internal factor that causes an object with mass to accelerate or the force equals mass time acceleration being Newton's second law of motion so why are we here I would like to expand the material in the nature of codebook to consider the following scenario let's say I have particle a and I have particle B particle B is moving this way particle a is moving this way at some point the two of them will meet how do I know when these two particles Collide this is called Collision detection this is something I cover in the book and have countless examples in videos over the years where I determine if two objects are intersecting that's the easy part the difficult part is what's known as Collision resolution when these two particles Collide when they're intersecting how do I solve for their new velocities so this is a very important moment in your life where where you're going to have to make a decision do you want to stick with me and continue watching this video where I am going to look at the math for solving for these new velocities you could just stop right now if you read chapter 6 I look at a wonderful Library called matter.js which does all of the Collision math for you resolving detecting everything and in fact what I'm going to do in this video will not get nearly as far as what matter.js does because for example what if these two particles aren't circles what if they're squares or some other arbitrary irregular polygon this is why these physics libraries exist there's no reason for me to reinvent the proverbial rigid body collision wheel I don't know but I do think it's really interesting to learn about the vector math and see how far we can get just baking it into our own P5 sketch and I imagine that you know I've got this passenger showcase thing that if you continue watching follow the code you might be able to create something wonderful that I can't even imagine right now and so that's why I'm going to keep going here's the sketch I'm going to start with it's one of my nature of code examples it's got two particles in it the particle class has all those things I talked about position velocity acceleration the velocity is set randomly the acceleration is zero I won't actually be using acceleration in this particular demonst rtion but it could come into play into the things that you might build on top of what I'm doing here in combination with other examples each particle has a mass which is a random value between one and six and then I am setting the particles radius to the square root of that mass because the area of a circle is p pi r squ and then just scaling it up so they can have smaller values Draw Bigger circles the update method has velocity Changed by acceleration position Changed by velocity and then I quickly cooked up this edges function so this is actually already a perfectly elastic collision between a circle and a wall so this is a very similar scenario to what I need to do I've got Collision detection does the position along the x axis reach either Edge and if so perform Collision resolution by inverting the polarity of the X component of velocity for the horizontal edges and the Y well those are the vertical edges I guess and the Y component of the velocity for the horizontal edges the top and the bottom we're finally there all of that exposition to get to the part that I'm here to talk about in this video let's do a little warmup and first just look at Collision detection between two circular bodies the first thing I need to do to determine if those two circles are colliding is look at the distance between the two of them once I have that distance I can compare it to the sum of those two radi so I've written a Boolean expression here distance is less than the sum of radius one and Radius 2 let's think about what does it mean for that distance to be less than the sum of those two radi look at this case if the two circles are overlapping that distance is going to be less than radius 1 Plus radius 2 if the two circles are not overlapping and not intersecting that distance is going to be much greater than or not much greater than just simply greater than the sum of radius 2 Plus radius one let's add Collision detection now to this sketch Let's uh I don't know write a function I mean not write a function I will write a function called Collide where I say particle a Collide particle B and the way I'm thinking about this right now is it would be the same either way I could say particle B Collide particle a or vice versa that means I need a new uh function and the argument in that function I'll call other referring to the other particle that this particle is checking whether it's colliding with so what do I need first distance ah there's a vector function in P5 I can say this. position. distance other. position I'm pretty sure that will give me the distance between two vectors if that distance is less than what this R plus other R then what should we do just to know that it's working let's just console log something all right moment of truth I think that worked yeah it's working you can see whenever those two circles are colliding the choo choo number goes up and up and up we've got Collision detection that was the easy part it's time for the really hard part Collision resolution to talk about Collision resolution I need to introduce some new Concepts Concepts that I don't actually get into in the nature of code book are you glad that you stuck with me so far in this video I hope so so I probably said at some point earlier the word elastic and I I certainly wrote it on the board here what do I mean by an elastic Collision versus an inelastic collision first let me talk about the concept of momentum momentum is a vector quantity and it is the product of the mass times the velocity a massive object with a small velocity has just as much momentum as a small object with a lot of velocity there is also the concept of kinetic energy the kinetic energy of an object is one half of the mass times the speed the scalar magnitude of the Velocity squared the reason why I'm talking about these two concepts is because in an elastic a perfectly elastic idealized elastic Collision both the total momentum and the total kinetic energy are conserved meaning let's say I have particles again A and B they have a mass the mass of a the mass of b as well as a velocity which I'll just use V for velocity a and velocity B and remember the reason I'm doing this is because if I have object a and object B that are colliding and maybe they have these velocities I need to solve for the new velocities velocity a prime velocity B Prime if this Collision is elastic and it conserves the momentum and the kinetic energy of the system that means that the momentum before Collision and after Collision are equal additionally in an elastic Collision there is no loss of kinetic energy meaning the total sum of the kinetic energy before and after the Collision must be equal conservation of momentum conservation of kinetic energy now in an inelastic collision some kinetic energy would be lost and that usually manifests itself in the form of heat or sound this would be quite interesting to model and uh if you're interested if this video goes at all well and anybody actually watches it and uh enjoys it or makes something with it or if it works out in any way whatsoever I would be glad to come back and try to add the concept of inelastic collisions into another example but right now I want to solve for these new velocities based on these two equations I'm not actually going to do that in this video I'm just going to tell you what the solution is and show you some resources into how it could be derived so my first stop before recording this video was to review this Wikipedia page for elastic collisions you can see this nice animated demonstration of atoms in a thermal agitation system that are undergoing essentially perfectly elastic collisions these same equations that I've covered for you on the Whiteboard are here on the page as well as some animated demonstrations of how this plays out in one dimension so onedimensional collisions which I looked at briefly in my Pi Day video where I calculated the digits of pi with elastic one-dimensional collisions based off of the work of three blue one Brown now what I'm hoping to do is model those same elastic collisions but in two dimensions and here is a nice visual demonstration that shows you the primary components and aspects of the vectors that you need to solve for that Collision resolution the key element here being the line of impact the line of impact is a vector or line that connects the centers of both particles in this case it becomes an axis you can think of it as the horizontal axis of a new coordinate system so why is this line of impact important well remember the objects have velocities velocity a and velocity B typically speaking when you take a velocity vector and divide it into its components you get the X component along the horizontal axis and the Y component along the vertical axis what if you were to unpack and get the compon components of these vectors according to the line of impact and that is in fact what's necessary for calculating the new velocities this is very much related to the section in chapter five of the nature of code book where I talk about the dot product and the concept of scalar projection scrolling down on the Wikipedia page you'll actually find the result of all of that math the new velocity for uh particle one or in my case I'm calling it a and velocity 2 Prime now interestingly enough the Wikipedia page doesn't have a full derivation of the formula if you want to learn more I'm going to point you to two additional resources this is an article called twood dimensional elastic collisions without trigonometry it is from a piece of software from 2009 called Bounce scope from ven. comom and includes additional explanation on finding the new velocities of two objects after a collision code train viewer and contributor D pom who is very helpful to me in preparing for this video created a PDF called elastic collisions which goes through one-dimensional elastic collisions and the derivation of the new velocities as well as two-dimensional elastic collisions and how to resolve the velocities along the line of impact as well as covering another key component here which is the vector that is tangent to that line of impact at the point of impact the place where those two circles meat and here again are the final formulas which I don't know how long it took me to get here but I'm now actually going to implement in the code okay I have printed out the formulas here and I'm going to put them into the code now all right I can kind of think about this formula in different components for example I want the sum of the masses why I call it m sub M sum I also need the line of impact which which is my particle B will be uh position two or x2 in the formula and I'm considering particle B to be the other again these are somewhat arbitrary decisions then I need the velocity difference velocity B minus velocity a now the change in this velocity so I'm going to call this Delta V equals 2 * the other mass divided the mass sum plus the dot product between V diff and the line of impact divided by I'm doing this in a kind of a clunky way let's do it let me let me let me change this a little bit where's the where did the plus come in there's no plus I'm going to do the top the top of the formula the numerator then divided by by the denominator let's call it the numerator numerator a just going to call it numerator a is 2 * the other's mass times the vector velocity difference dot the line of impact and the denominator a equals m sum times the magnitude I'm going to call that that's the distance that's the distance the magnitude of that line of impact is D time D * D so the change in that velocity I should make a copy of the line of impact and then multiply it by the numerator a divided by the denominator a and then this do velocity changes by that Delta V I don't know what's going to happen when they Collide oh one of the okay that it's kind of working but only off of one of them okay this is good I think I did my math right there I'm sure I could write this in a clearer way maybe I'll come back to that let me just do the other one so particle a this and now for particle B which is other it is 2 * this Mass denominator is the same so I don't need a separate denominator a or denominator B this should be Delta VA Delta VB Delta VB multiplied by the ah wait a second so the polarity changes because for B I need to take the difference between X1 - X2 instead of X2 - X1 which means just multiply this by -1 so that should work and then other velocity add Delta VB okay are you ready for this we're about to see my implementation of the formulas Works they're not colliding very often come on Collide here we go it's gonna happened there that looks pretty good okay I actually have a mistake here V diff needs to be reversed for the other one because it's V1 minus V2 also the line of impact should like let me just reverse them here and then instead of doing that here that should be fine now somehow it worked before because it's really just a matter of I I somehow got the negative in the right place by accident but really if I look at these formulas I've got V1 minus V2 do X1 - X2 for the second particle so both of those need to be reversed before I compute that dot product let's run it again just to make sure will they ever Collide I really hope so Collide again please yes okay looking good all right so it worked by accident before it still works now now I'm realizing I could actually simplify this further because ultimately it's just about the numerator being positive in the top formula for particle one and negative in the bottom so actually we just have a numerator forget about this and then then there is only a numerator and then the numerator is negative here and I don't need this second one so that's simplifying it oh wait what's going on oh I know what's going on okay I'm gonna have to fix something from okay it freaked out okay I thought it was working but what did I get wrong here I think to make this more clear let's calculate the line of impact here and we'll call this or I'll just call it impact vector and then the distance is the magnitude of that impact vector and that should also save one small calculation and simplify a few things oh what did I get wrong ah this is called impact Vector why is it speeding up like crazy I've been writing this a lot I'm encountering two issues one is for some reason sometimes I seem to be manufacturing kinetic energy out of thin air the balls keep going faster and faster as they Collide they also are getting stuck on each other this is because and it goes back to that question of the time step there's a certain inaccuracy here of having a large time step of one as two particles are approaching each other when I detect that they Collide they might actually end up looking something like this they could easily have moved quite a bit into the same space this is something I can correct for right here what I need to look at is what is the difference between that distance and the actual sum of the radi in a perfect world of perfect elastic collisions those two values would be equal I'll call it overlap along that line of impact I need to move each particle half of that difference so let me make a copy of that Vector set its magnitude to half of the overlap and then particle a which is this should be offset by that direction and then particle B should alsoo be offset but in the other direction so I should subtract that vector and then when I use the distance in the calculation I should correct it as well to be the sum of the radi now that I've added this overlapping correction let's take a look at the total momentum and total kinetic energy of the system and see if it's being conserved let's start with just the kinetic energy that's a scalar quantity that'll be a little easier to track kinetic energy of a is equal to 0.5 times particle a is mass let's get speed a to be particle A's uh speed the magnitude of its velocity and speed B and let's console log the total kinetic energy kinetic energy a plus kinetic energy B now I don't expect this to be perfect the large time steps of Oiler integration JavaScript rounding there's all sorts of reasons why this could go wrong but let's at least see how close it is to being accurate so far the total kinetic energy is not changed but they haven't collided yet oh boy it doubled it haved it doubled okay that's way off something must be wrong let's go back and look at my formulas two oh oh when I did this simplification of only one numerator ah I forgot that I have to change the this can change this part of the numerator can change its to positive to negative but I need to use Mass one not mass two that was the error a I tried to simplify this code and I made it worse we're going to fix this numerator the numerator is just going to be this and what I'm going to do is I'm going to say two times other dot Mass time the numerator and this one is -2 * this do mass time the numerator Moment of Truth we lost a little kinetic energy but just a tiny bit that's a rounding error maybe I'm curious about not correcting this distance I'm just curious to see what that does yeah let's not correct that distance okay so correcting that distance felt like it should be something I should do but apparently uh I should not look at look at how beautifully this kinetic energy is being maintained now slight now it's just rounding errors why did I think I wanted to do that I moved them apart ah but I didn't actually change I see I moved them apart but I didn't actually change the length of the impact vector and I'm using that here so if I wanted to correct that distance I think I might also need to just adjust the impact Vector to be that correct length let's see if this yeah so I just needed to be consistent I just if I'm going to correct that distance maybe I should maybe I shouldn't doesn't really matter so much but I just need to be consistent so I'm going to do that correction I'm going to move them apart and I'm going to consider that impact ve Vector to be slightly elongated uh if need be okay let's have some fun now let's put a lot of these particles onto the screen comment out this kinetic energy calculation now I'm going to have an array of particles let's try just adding five of them just to start at random locations now they're all on screen and all updating bouncing off the edges and drawing themselves let me make them a little bit smaller and let's try making uh 10 of them great now let's see if we can get them to collide with each other so I'm going to do that in a separate Loop so particle a is every single particle in the array but now when I want to look at the other particles I'm going to start from particle I + one the idea being that I want every particle to check every other particle but I don't want particles to check against themselves and I don't want a particle to recheck against another one later so if I have 10 particles zero checks one all the way to the end one checks two all the way to the end two checks three all the way to the end and so on and so forth particle B is particles index J and then I can say particle a collide particle B here we go I love it already let's make a lot more and there you have it coding challenge complete so I'm curious to see what you might do with this I don't have any ideas I'm exhausted from recording this whole video I'm sure you'll have some share them with me in the passenger showcase I do want to say one more thing though I'm going to make these particles briefly much much smaller and then I am going to add 400 of them into the canvas well that's amazingly still working let's do a thousand of them this is actually running much faster than I would expect because I'm able to start J at I + 1 but technically it is still an N squared algorithm and it's going to get quite slow if I were to get up to let's say three ,000 particles so I believe this can run quite fast with 3,000 particles with a particular kind of optimization this is something that I cover in guess what chapter five of the nature of code under optimization and is something that I've explored quite extensively in my coding challenge quad Tree video series so I have I'm I mean I haven't made it right now but after I finish recording this I'm going to make a version of what you're seeing right here that uses a quad tree to optimize those Collision checks I will release that as part of this video take a look if uh you're interested I could come back and unpack that further in a live stream or make another video about it I don't know what should I do next was this helpful was this interesting are you at least mildly interested in the nature of code book now I hope so thanks for watching and I'll see you next time on the coding train [Music]

Channel: The Coding Train

Views: 39,280

Keywords:

Id: dJNFPv9Mj-Y

Length: 31min 5sec (1865 seconds)

Published: Sat Jul 13 2024