Name collision

Transcription

This is Coding Math Episode 14: Collision Detection Today's subject, collision detection, is also sometimes known as hit testing. Collision detection is the term most commonly used in game programming, while hit testing is probably seen more often in relation to application UI programming. But basically they amount to the same thing: determining when an object hit something, or when two objects have hit each other. Collision detection is a broad topic and there is no single technique or method that handles all collision detection. It's more of an art than a science, and often you'll need to trade off between accuracy and performance. There's no way I could cover all possible collision detection methods in a single video. But I'll cover the overall concept and a few of the most used methods here, and we'll probably look at some more specialized ones on down the line. Basically, collision detection or hit testing is what its name implies - an on-screen object has collided with, or hit, another object. Sometimes this means that a single object has moved into or onto a certain area of the screen, like the right edge, for example. We've pretty much covered that in Episode 12 on Edge Handling. But usually people think of collision detection as checking to see if two objects have hit each other. Sometimes one of those objects is stationary, sometimes both are in motion. And sometimes one of those "objects" is the mouse pointer. In screen terms, we want to know of any of the pixels of this object overlap any of the pixels of that object. Now, generally speaking there are two ways to figure out collision detection. Mathematically and graphically. Mathematically means that you have some kind of structural definition for each of the objects. Some mathematical model that describes their positions and shapes. And so you can do some calculations to see if those two shapes are intersecting. Graphical collision detection means that you are actually using the defined screen pixels of each object to see if they overlap. This is usually dependant on some kind of built-in method of the bitmaps you are using in a specific system. For example, in ActionScript, the language used by Adobe Flash, there is a BitmapData class that has a hitTest method. You can use this to directly compare two bitmaps to see if any of the non-zero pixels overlap, even specifying how much transparency they can have and still register a collision. This is very powerful, as it allows you to test complex irregular shapes to see if they are colliding. It would often be completely impractical to do mathematical collision detection on such objects with the same amount of accuracy. Unfortunately, for HTML5's Canvas object, nothing like this has been implemented yet. There are some cool features on the way, such as hit regions and paths, but for now, you'd have to do any pixel-level graphical collision detection by rolling your own methods. This can be complex and CPU-intensive, or involve various tricks. So, we'll stick to mathematical detection in this video. But I'll probably do another video at some point that covers canvas pixel checking. OK, so on to the mathematical testing. So again, we need some kind of mathematical model of the object or objects we are testing. Of course, you can have objects with all kinds of shapes, and these can usually be defined mathematically in one way or another. But the more complex your object model, the more complicated it is to do collision detection with it. So, rather than always trying to exactly model an object, first see if you can roughly represent it by one of these three: - a circle - a rectangle - a point These are the objects we'll cover in this video. Of course, you'll find objects that these just won't be adequate for, so I'll probably have to do an advanced collision detection episode some time later. But you'd be surprised how many use cases these three object types will cover. So, let's deal with four types of collisions: circle-circle, circle-point, rectangle-rectangle, and rectangle point. First, circle circle. In Mini #5, we covered the Pythagorean theorem and distance. This is vital for this type of collision detection. We'll define a circle as an object having an x, y point and a radius. Now, say we have two circles on screen and we want to know if they are touching. First, we calculate the distance between them, using the distance function we created in Mini #5. Now, the radius of this circle is this line segment here. And the radius of this circle is this segment here. If you add these two radii together, you can obviously see that they add up to less than the distance between the two circles. And these circles are obviously not colliding. But what about these two. Here's the distance. Here's one radius, and here's the other radius. If you add these radii, the sum is obviously larger than the radius. So there's your algorithm for determining circle-circle collision: is the sum of the radii greater than or equal to the distance between the centers of the circles? If so, they are hitting. In our utils.js file, I've added the distance and distanceXY methods. I'm now going to add a circleCollision method. This will take two objects. We'll assume that these objects are circles and have x, y and radius properties. In here, we can say; return distance(c0, c1) < c0.radius + c1.radius; To save time, I've already created a test file for this, called circle-circle.js. It creates two circle objects with random positions and radii. Then it sets up a mousemove handler. In that handler, it moves circle1 to the position of the mouse. And then it checks for a circle-circle collision. If it finds one, the fill style is red, if not, it's gray. Then it draws the two circles. So, we run this, and move that second circle around. And when the two overlap, bingo, they both turn red. Next up, circle-point collision. This is really exactly what we did in the code example in Mini #5. But we'll generalize it here into a reusable function. Back in utils.js, we add a circlePointCollision method. This takes an x, a y, and a circle object. This method is almost the same as the circleCollision method, but it just compares distance to the one radius. If you think of it, a point is really just a circle with a radius of zero, so this makes sense. I've set up a test file for this as well. Again, essentially the same thing as the Mini #5, but we start with a circle object and use the util method we just created. Again, if the mouse touches the circle, it's red. If not, it's gray. And we can quickly look at that in action. Now, onto rectangle collisions. Rectangles aren't quite as elegant as circles. A rectangle can be defined by two points, or by one point plus a width and a height. In the latter case, the width and height are really just offsets from the first point to the second. We'll go with width, height since that's the convention used by several other JavaScript methods. So, we can make a rect object that has x, y, width and height properties. Let's start with the rectangle-point collision. Say we have a point here and we want to know if it is in this rectangle. If so, it will need to satisfy four two conditions. 1. the x position of this point must be within the range defined by the x positions of the two points making up the rectangle. 2. the y position of the point must be within the range of the y positions of those two points. Seems pretty simple, so let's try to implement it. We'll create a pointInRect method. It takes an x, a y, and a rect object. Now we could just do a straightforward implementation here, making sure that the point's x is greater than or equal to rect.x and less than or equal to rect.x + rect.width. And then do the same for y. But I'm going to use this opportunity to make another utility function called inRange. inRange will take a value and a range defined by a min and max and return whether or not that value is within that range. Simple enough. We just say return value >= min && value <= max. I could have made a whole mini episode about that, but it would have been a stretch. Now, back in the pointInRect function, we can say return inRange(x, rect.x, rect.x + rect.width) && inRange(y, rect.y, rect.y + rect.width); So if x is in range and y is in range, then the point is in the rectangle. If either one fails, it's outside the rectangle. I've created another file, rect-point.js that creates a rect and listens to mouse move and checks pointInRect using the mouse position. We can test that and it seems fine. Roll over the rect, it turns red. Otherwise gray. But take a look at this case. Here we have an x, y of 100, 100, a width of -20, and a height of -10. In this case, this point here is obviously in the rectangle, but it will fail the test since its x is less than rect.x and its y is less than rect.y. We can go back into our code and change these width and height values to negative... And see that, yeah, this is broken. So, there are a few ways to handle this. One is to just say that width and height always need to be positive. This is an arbitrary rule that will only make this method less useful and more error prone. Another solution is to make a smart rectangle object that automatically adjusts its internal properties so that the x, y point is always the top left and width and height are always positive. This is possible, but I'd rather just have the pointInRect function be more robust. And that translates into having this inRange method be more robust. Right now we're checking to see if value >= min. This is assuming that min is less than max. What breaks it is when max is the smaller of the two. What we really want to know is if value >= the smallest of min and max. Well, we can use the Math.min function for that and say if value >= Math.min(min, max) And for the other side of it, we want to know if value <= the larger of min and max. So we check if value <= Math.max(min, max) Now it occurred to me while I was doing this, that the clamp method suffers from the same problem. You should be able to clamp a value to an inverted range, but as it is, that won't work. Well, we might as well go ahead and fix that now, the same way, using Math.min to get the smaller of min and max, and Math.max to get the larger of them. It's beyond the scope of this video to do a test case for this change, but I did test it out on my own and it works just fine. Now, just changing this inRange function should have fixed up this inverse rectangle use case. Let's test it... ok, that looks good. Next up is the rectangle-rectangle collision. You can mentally struggle for a simple mathematical rule that defines when two rectangles are overlapping. Here's how I like to think of it. The left and right x values of a rectangle form a range. We've seen this with our use of the inRange function we just created. With two rectangles, we have two x ranges. In the same way, we have two y ranges. Now, if the two x ranges overlap each other AND the two y ranges also overlap each other, then the rectangles are intersecting. If either the x ranges or the y ranges don't overlap, then the rectangles are separate. So first we'll need to know how to tell if two ranges overlap. It might be easier to say when they don't overlap. If the max value of range A is less than the min value of range B, then there's no way they overlap. So max of A has to be greater than or equal to min of B. But say A over here, if the min value of A is greater than the max value of B, there's no overlap possible. So, min of A has to be less than or equal to max of B. And so we can start to write a function function rangeIntersect(min0, max0, min1, max1) { return max0 > min1 && min0 < max1; } And this will work fine... sometimes. Remember our old reverse range problem. We need to account for the possibility that either one of these mins may be greater than its corresponding max. So we toughen this function up my wrapping everything in Math.min and max calls. function rangeIntersect(min0, max0, min1, max1) { return Math.max(min0, max0) > Math.min(min1, max1) && Math.min(min0, max0) < Math.max(min1, max1); } Now I realize that this starts to read like some crazy tongue twister. So if you're not totally clear on it, I urge you to take a break and work it out with some examples. Now we can use this to create a rectIntersect function. In this, we call rangeIntersect twice. Once with the two x ranges, and again with the y ranges. If both of those are true, then the two rectangles are intersecting. And of course, we have a test case for this. It creates two rectangles. One is stationary, the other one will move with the mouse. We listen for a mousemove event, get the clientX and Y and set the second rectangle's position offset from that. Then we call rectInteresect on the two rectangles. If that's true, red. False? gray. And we run this... Looks to work fine. Try this with one or both of the triangles having a negative width and/or height to make sure that works as well. OK, well, this episode has gone on long enough, and as you can see, we've only covered the bare minimum of this subject. I'm sure we'll be coming back to other strategies for collision detection in the future.