----------------------------------- richcash Sun Oct 08, 2006 2:02 pm Collision Detection ----------------------------------- Collision Detection Tutorial What is collision detection? Collision detection is a programming technique used to determine whether two objects or pictures on a screen are touching (or have collided!). It is especially used in games to check if two balls, two characters, or two of anything have collided. While there may be unlimited methods of checking for collision, the two main ones that we will be discussing are known as rectangular collision detection and circular collision detection. Rectangular Collision Detection The method referred to as rectangular collision detection determines whether or not two rectangles have collided (hence, the name!). In order to use rectangular collision detection, you must have these pieces of information about both of your rectangles : lowest x value of the rectangle lowest y value of the rectangle greatest x value of the rectangle greatest y value of the rectangle These are often referred to as : x1, y1, x2, and y2. If you draw a rectangle (box) in Turing, you automatically know these pieces of information, because the first four parameters for drawbox are x1, y1, x2, and y2. (If you're using an imported picture, read this. Otherwise, you can skip it.) For an imported picture, you only know x1 and y1 and those are the first two parameters to your Pic.Draw. However, we can easily find x2 and y2 by adding a function known as Pic.Width ("picture_name") to our x1 value. For y2, we simply add Pic.Height ("pic_name") to y1. Simple enough. Now, to check if two rectangles on the screen have collided or are touching (some might even say they are overlapping!), we have to check for the following conditions. Let's use box #1 and box #2 to represent our two rectangles and assume that they have the 4 parameters needed. box #1's x1 (lowest value) has to be LESS than box #2's x2 (greatest value) box #1's x2 (greatest value) has to be GREATER than box #2's x1 (lowest value) box #1's y1 (lowest value) has to be LESS than box #2's y2 (greatest value) box #1's y2 (greatest value) has to be GREATER than box #2's y1 (lowest value) So, if all of those conditions are met, then box #1 and box#2 have collided. But why are these the conditions? Well, in your mind, suppose if one of the conditions above wasn't true. Why wouldn't the boxes have collided if any of those conditions weren't true. Think about it for each condition. Well, it's fairly simple if you can picture it like below. Look at the x-axis only, in the first diagram you can see that the the first box has a right end and this is obviously its greatest value. The second box has a left end and this is its lowest value. The second box's left end is to the left of the first box's right end, which means the second box's lowest value (left end) is less than the first box's greatest value (right end). The second diagram shows what would happen if this wasn't so. Picture it the same way for the y-axis except (of course!) up and down instead of left and right. _____ _____ |___|__ |___| _____ |___| |___| Now that we fully comprehend rectangular collision detection, let's use it in some code! %declare some variables for box1 and box2 var box1_x1, box1_y1, box1_x2, box1_y2 : int var box2_x1, box2_y1, box2_x2, box2_y2 : int %assign our variables to values for boxes. These can be anything. box1_x1 := 100 box1_y1 := 100 box1_x2 := 150 box1_y2 := 150 box2_x1 := 300 box2_y1 := 125 box2_x2 := 350 box2_y2 := 175 loop %draw the boxes cls drawbox (box1_x1, box1_y1, box1_x2, box1_y2, 9) drawbox (box2_x1, box2_y1, box2_x2, box2_y2, 12) delay (20) %move our first box horizantally box1_x1 += 1 box1_x2 += 1 %check for all four of our conditions! if box1_x2 > box2_x1 and box1_x1 < box2_x2 and box1_y2 > box2_y1 and box1_y1 < box2_y2 then put "They have collided!" exit end if end loop One other thing. Rectangular collision detection can sometimes also be used with non-rectangular shapes, but in this case you make your own theoretical rectangle (x1, y1, x2, y2) around the object and use this as a rectangle. Obviously, it is inaccurate, but if the shape is rectangular enough it will work considerably well. And that's all for rectangular collision detection! Circular Collision Detection Circular collision detection detects collision between (you guessed it!) two circles. (Please note that this type of collision detection does not work with non-circular ovals!). The method of doing it is actually quite simple. In order to use this method, you must know the following about both of the circles colliding : co-ordinates of the centre point (x and y) of both circles radius of both circles In order to use drawoval (or drawfilloval), you have to use these values as your parameters anyway. To clarify, the x- and y- radii are the same in our case because we are using circles. Now, the actual method to check for collision between the two circles has three steps (well, kind of one!). These three steps are : Find the distance between the centres of the two circles. Add the two radii of the circles (radius of one circle + radius of the other circle). Check if the distance between the centres of the circles is less than the sum of the two radii and, if it is, then the two circles have collided or are overlapping. Why does this method work? Think of it this way. How would we detect collision if the circles were just dots and had no radii. We would just check if the distance between them was 0 (they would be equal). But, since we do have circles and actual radii, the distance between the centres doesn't have to be 0, it can be more. How much more? It can be one circle's radius + the other circle's radius more. If the distance between the centres of the circles is less than or equal to the two radii added up, then that means the "circles" are theoretically on top of each other, which means a collision has happened. So, now we know the method to detect circular collision, but there is one thing we are missing. How do find the distance between the two circles' centres? Well, we use the distance formula (or the distance-between-two-points formula!) that is learned in high school math and is derived from the pythagorean theorem. For more information about the distance formula in specific (and the derivation of it), you can search on the internet or go distance := sqrt ((x2 - x1) ** 2 + (y2 - y1) ** 2) And, for our case of circular collision detection, x1 would be the x coordinate of the centre of circle 1, y1 would be the y coordinate of the centre of circle 1, x2 would be the x coordinate of the centre of circle 2, and y2 would be the y coordinate of the centre of circle 2. Now, let's implement our collision detection system into a program! %declare our variables var circle_1_x, circle_1_y, circle_1_radius : int var circle_2_x, circle_2_y, circle_2_radius : int var distance_between_centres : real %give our two circles values. These can obviously be changed. circle_1_x := 100 circle_1_y := 100 circle_1_radius := 5 circle_2_x := 210 circle_2_y := 190 circle_2_radius := 20 %main program loop %draw our circles. Remember, the x-radius and y-radius are the same! cls drawoval (circle_1_x, circle_1_y, circle_1_radius, circle_1_radius, 12) drawoval (circle_2_x, circle_2_y, circle_2_radius, circle_2_radius, 9) delay (20) %Move the first oval diagonally circle_1_x += 1 circle_1_y += 1 %calculate the distance between the centres of the circles distance_between_centres := sqrt ((circle_2_x - circle_1_x) ** 2 + (circle_2_y - circle_1_y) ** 2) %Our collision detection method if distance_between_centres = (x2-x1)^2 + (y2-y1)^2. sorry if im sounding so harsh, but there is no need for another sub-par collision detection tutorial. perhaps, i'll write a tutorial on collision detection. i was thinking of writing an intro tutorial to 3D but i think more people will benefit from a good collision detection tutorial... ----------------------------------- richcash Sun Oct 08, 2006 11:19 pm ----------------------------------- I don't know, guys. I had my tutorial approved by a mod (and indirectly by another mod). It was only meant to be a replacement for the current one from three years ago. Now that I read it over again I realize that it's not as good as I thought it was when I originally wrote it. This is not a good display of my best work. furthermore, your code examples show poor programming practice. read the records tutorial if you havent done so already. I'm offended! Just joking, but on a serious note I wanted to keep this very simple. I just thought that if someone doesn't know the concept of collision detection, then how will they know records. Perhaps I should've made it with more advanced coding. ie you can omit the costly sqrt call and just check if (rad1 + rad2)^2 >= (x2-x1)^2 + (y2-y1)^2. Yeah, I know, or you can just ^0.5, but these are just things you simplify by yourself. I'm trying to relate the code to the distance formula learned in math class. I took a conceptual approach, I tried to explain everything like I was talking to somebody who just learned loops and for loops. perhaps, i'll write a tutorial on collision detection. i was thinking of writing an intro tutorial to 3D but i think more people will benefit from a good collision detection tutorial... While I certainly couldn't compete with a tutorial by you, I want to finish what I started. Please, let me re-attempt this tutorial. I'll go from scratch and include much more advanced algorithms. Let me prove myself. Just name some of the things you want included and I'll try to do them. I'm starting all over so it will be a while before I finish. ----------------------------------- Cervantes Mon Oct 09, 2006 12:26 am ----------------------------------- Fixing up the BBCode would go a long way to fixing this tutorial. I think the content is good, but maybe I should read it more closely. I think the presentation (aside from the BBCode issues) is good. Try posting the version you sent me (and that I sent back to you a little while ago). It's got good BBCode. Feel free to use this thread while you're making changes. When we're all satisfied, I'll delete this thread and you can post it fresh. ----------------------------------- zylum Mon Oct 09, 2006 12:31 am ----------------------------------- ie you can omit the costly sqrt call and just check if (rad1 + rad2)^2 >= (x2-x1)^2 + (y2-y1)^2. Yeah, I know, or you can just ^0.5, but these are just things you simplify by yourself. I'm trying to relate the code to the distance formula learned in math class. I took a conceptual approach, I tried to explain everything like I was talking to somebody who just learned loops and for loops. the point isnt that you could use exponentiation rather than the sqrt() function. ^0.5 is the same as the sqrt function which is a very costly operation compared to addition, subtraction or multiplication. that is why you use my method which involves multiplication and addition and no square roots which can slow down you program. if i were going to write a collision detection tutorial i would go roughly like this (though i find writing tutorials is a very dynamic process): - intro: - brief intro to topic - discuss what your tutorial will cover - background info needed to comprehend tutorial - perhaps a preview of what you can accomplish or something to motivate reader - basics: simple collision detection - rectangle - rectangle - circle - circle - circle rectangle - intermediate: - line - line - circle - line - bounding boxes - advanced: - arbitrary polygonal shapes - time based collision detection to prevent over lap and increase precision (used in games like pool where collision detection is very important) - conclusion (at the end of each section) - review key concepts - practice problems - solutions basically thats it. i would add stuff if i saw the need. if you dont have the knowledge to do all that or you just dont have the time/ dont feel like it, make your tutorial the "basics of collision detection" and ill continue the series. ----------------------------------- Tony Mon Oct 09, 2006 12:38 am ----------------------------------- The sqrt comment was kind of harsh. Although valid, it has to do with optimization, not the concept of collision. sqrt conveys the message better at a simpler level. (optimized version could be mentioned in the comments) The formatting throws things off... a lot. The language could use some improvement. Well, in your mind, suppose if one of the conditions above wasn't true. Why wouldn't the boxes have collided if any of those conditions weren't true. Think about it for each condition. Learning is best achieved when the students comes up with the answer on their own. Here you throw out the answer, and tell them "think about why I'm right". A better approach would be to provide an illustration (it's a tutorial for graphical application - use some graphics), ask what conditions describe the situation (collision) presented, and follow through with that. There are some technical points to address as well * lowest x value of the rectangle * lowest y value of the rectangle * greatest x value of the rectangle * greatest y value of the rectangle These are often referred to as : x1, y1, x2, and y2. If you draw a rectangle (box) in Turing, you automatically know these pieces of information, because the first four parameters for drawbox are x1, y1, x2, and y2. x1/y1, x2/y2 are just two opposing corners, not neccessary the lowest/greatest. Draw.Box(200,200,100,100,blue) If you are making an assumption that the values will always be in a more convinient order, do state that assumption. It will clear up any possible confusions. When writing a tutorial on an existing subject, do make sure to take it a step higher. Try to address the weaker points of the existing material, and answer applicable questions from follow-up comments. ----------------------------------- richcash Mon Oct 09, 2006 12:48 am ----------------------------------- Alright, thanks to everyone for pointing out my weakness. I'll see what I can finish in the next couple of weeks, and if it is too much for me then I'll just cover the basics. The version I sent Cervantes was a bit better, but still subpar seeing what you guys have pointed out. I'll just make my adjustments and revisions in this thread as advised. ----------------------------------- zylum Mon Oct 09, 2006 12:56 am ----------------------------------- yeah i realise i was sort of harsh, i was sort of in a hurry and wanted to write down as somethings before i had to go. sorry about that :wink: i find it takes a lot of skill to write a good tutorial. there are always ways you can improve an existing tutorial, whether it is to improve the language, add an image to explain something better or to simply add more colour for visual appeal. when i write a tutorial i always write an outline, then a rough copy. as i go over the rough copy i add extra info and try to clarify ideas. even now when i go through some of my old tutorials, i find ways i could improve them (but of course am to lazy to update them :lol: ) maybe someone should write a tutorial on how to write a tutorial :wink: oh wait... http://compsci.ca/v2/viewtopic.php?t=9619 :P ----------------------------------- ZeroPaladn Mon Oct 16, 2006 1:32 pm ----------------------------------- I've ben reading thru this thread and there seems to be no mention of dual layer collision detection (the one with the collision layer drawn before the actual stuff to be seen by the user, usually is done by comparing colours). Perhaps you can add this? It works well with tile-based games, and it's pretty simple (though is a hog for computing power) ----------------------------------- Cervantes Mon Oct 16, 2006 2:46 pm ----------------------------------- I've ben reading thru this thread and there seems to be no mention of dual layer collision detection (the one with the collision layer drawn before the actual stuff to be seen by the user, usually is done by comparing colours). Perhaps you can add this? It works well with tile-based games, and it's pretty simple (though is a hog for computing power) You're talking about is whatdotcolour. And as for whatdotcolour with tile based games... I'm shocked. The collision detection in tile-based games is as easy as it can possibly get. Using whatdotcolour totally obfuscates things. ----------------------------------- ZeroPaladn Tue Oct 17, 2006 12:21 pm ----------------------------------- ...The collision detection in tile-based games is as easy as it can possibly get. Using whatdotcolour totally obfuscates things. To each his own. I personally prefer to use whatdotcolour collision detection over conventional co-ordiante collision detection. I think whatdotcolour could make a small appearance in the tutorial (if even just a link to a whatdotcolour tutorial) to give people choice on what they want to do. ----------------------------------- Cervantes Tue Oct 17, 2006 1:12 pm ----------------------------------- I'm interested in hearing why you think whatdotcolour is superior in tile-based games. Heck, I'm interested in hearing why you think whatdotcolour is superior in any situation. There is a fundamental flaw in whatdotcolour collision detection: What the program draws determines what the program draws in the next iteration. Ideally, drawing is based solely on the state of the variables, not on the state of the output buffer. Another fundamental flaw of whatdotcolour is how limited it is. Consider a situation in which there are two balls both moving a great many pixels per frame. It is conceivable that, in one frame, the balls could pass through each other. If we could slow things down, we would see that the balls actually should have collided. Whatdotcolour only sees two snapshots of the balls, and in neither snapshot have they collided. Solving this using math would show us that they do collide. It would be like doing whatdotcolour an infinite number of times. What's more, the math will tell us properties of the collisions, such as the positions of both balls exactly when they collide. ----------------------------------- ZeroPaladn Wed Oct 18, 2006 11:50 am ----------------------------------- I've just never used basic collision detection for my programs, i was taught to use whatdotcolour, and what is what i use to this day. i prefer to use what i allready know (even if it does suck) instead of learning something else, when they both serve the same purpose (depending on useage). one day ill learn normal collision detection, and this conversation would be pointless... time to learn. ----------------------------------- Andy Thu Oct 19, 2006 2:59 am ----------------------------------- I've just never used basic collision detection for my programs, i was taught to use whatdotcolour, and what is what i use to this day. i prefer to use what i allready know (even if it does suck) instead of learning something else, when they both serve the same purpose (depending on useage). one day ill learn normal collision detection, and this conversation would be pointless... that is the dumbest justification you could've possibly gave. if that is your attitude, then we dont need your input. your job, as a student is to learn, and we are here to help you learn how to complete your tasks the most efficient way. and cervantes, whatdotcolor is superior in every situation. i'd like to see your math detect collision in the situation you mentioned with convex polygons ----------------------------------- Cervantes Thu Oct 19, 2006 9:00 am ----------------------------------- and cervantes, whatdotcolor is superior in every situation. i'd like to see your math detect collision in the situation you mentioned with convex polygons I doubt I could do it, but I believe it can be done. I'd like to see whatdotcolour do the collision detection in that situation. Or even in the situation using circles instead of convex polygons. And remember, maintaining a good execution speed is important here. ----------------------------------- blaster009 Sat Oct 28, 2006 6:44 pm ----------------------------------- God forbid you should be able to use decent looking pictures in your program with various different colours. I mean, thinking that far outside of the box would completely nullify whatdotcolour! ----------------------------------- [Gandalf] Sat Oct 28, 2006 6:52 pm ----------------------------------- God forbid you should be able to use decent looking pictures in your program with various different colours. I mean, thinking that far outside of the box would completely nullify whatdotcolour! Ah but it's you who are not thinking outside the box. What if there was a collision detection layer, underneath your colourful pictures, which you used whatdotcolour on? I'm sure there's tons of other tricky stuff that can be done with whatdotcolour. ----------------------------------- Cervantes Sat Oct 28, 2006 10:51 pm ----------------------------------- "]Ah but it's you who are not thinking outside the box. What if there was a collision detection layer, underneath your colourful pictures, which you used whatdotcolour on? Then you'd be doing far more drawing than necessary, and your code would be that much slower. Drawing is a hefty task. ----------------------------------- [Gandalf] Sat Oct 28, 2006 11:09 pm ----------------------------------- Then you'd be doing far more drawing than necessary, and your code would be that much slower. Drawing is a hefty task. The point is that using multi-coloured pictures doesn't "completely nullify" whatdotcolour. Indeed, using math is almost always faster and more flexible, but it's not the only way. ----------------------------------- Andy Sun Oct 29, 2006 4:55 am ----------------------------------- cervantes, i am not suggesting a pure whatdotcolor approach. more like a combined effort between wdc and math. With whatdotcolour detection, you only need to traverse through the outer perimeter of the given shape. and when lines cross, you get a different colored pixel than you expect, thus signifying a collision. the perimeter of anyshape can be expressed as a first degree function, so your algorithm would be O(n), its really not that slow. blaster009, no offence, but who the hell do you think you're talking to? ----------------------------------- vertozia Fri Dec 29, 2006 12:06 am ----------------------------------- I frankly understand the picture/rectangle collision. How is colour to picture collision performed. e.g. I'm making a Mario game, Mario is a pic, the pipe is a color? How? ----------------------------------- Cervantes Fri Dec 29, 2006 5:27 pm ----------------------------------- Did you read the [url=http://www.compsci.ca/v2/viewtopic.php?t=2381]whatdotcolour tutorial? That would be a good place to start. ----------------------------------- richcash Fri Mar 16, 2007 9:40 pm Re: Collision Detection ----------------------------------- More Advanced Collision Detection To get the most out of this tutorial, you will need to understand the following : if and for loop constructs types records functions circular collision detection rectangular collision detection Circle vs Rectangle Assume that : (x1, y1) is the lower left corner of the rectangle (x2, y2) is the upper right corner of the rectangle (x, y) is the center of the circle r is the radius of the circle The first way we can check if the circle and rectangle are intersecting is to check if any of the rectangle's four corners are inside of the circle. We already have two of the rectangle's corners (x1, y1) and (x2, y2). The other two corners will obviously be (x1, y2) and (x2, y1). if (x1 - x)^2 + (y1 - y)^2 y1 and y < y2 and (x + r > x1 and x + r < x2 or x - r > x1 and x - r < x2) then there is an intersection These cases above do not cover all intersections of a circle and a rectangle, though. Can you think of a scenario where none of the four corners of the rectangle are inside of the circle and the highest, lowest, furthest left, or furthest right points of the circle are not inside the rectangle? Imagine a circle and a square with the same center and the square's corners sticking out of the circle. If this is happening, then the center of the circle must be inside of the rectangle, so we can check for that last condition. if x > x1 and x < x2 and y > y1 and y < y2 then the rectangle and circle are intersecting So, we have created four expressions (that can all be combined into one expression using or if we really want to). If any of these expressions are true, then there is an intersection. If none of them are true, then there is no collision between the rectangle and the circle. View.Set ("offscreenonly") var x1, y1, x2, y2, x, y, b, r : int x1 := 100 y1 := 100 x2 := 200 y2 := 200 r := 60 fcn circleRectangle (x, y, r, x1, y1, x2, y2 : real) : boolean if x > x1 and x < x2 and (y + r > y1 and y + r < y2 or y - r > y1 and y - r < y2) then result true end if if y > y1 and y < y2 and (x + r > x1 and x + r < x2 or x - r > x1 and x - r < x2) then result true end if if (x1 - x) ** 2 + (y1 - y) ** 2 x2 + c or y1 + b < y2 - d or y1 - b > y2 + d then result false end if %if the original discriminant failed, check if it was because there 4 real intersection %points among the two ellipses by moving one so that it will ensure to have two intersection %points if it previously had 4, and still have 0 if it previously had 0 if x2 - c < x1 and x2 + c > x1 and i = 2 then x2 := x1 + c end if if x1 - a < x2 and x1 + a > x2 and i = 2 then x1 := x2 + a end if %the constant at the end of the quartic var a0 :=a**4*c**4*y2**4+a**4*d**4*x2**4+a**4*c**4*d**4+c**4*b**4*x1**4+c**4*a**4*y1**4+c**4*a**4 *b**4-2*c**4*b**4*x1**2*a**2-2*c**4*a**4*y1**2*b**2-2*c**4*a**4*y1**2*d**2+6*c**4*a**4* y1**2*y2**2-2*c**4*a**4*b**2*d**2-2*c**4*a**4*b**2*y2**2-2*a**4*c**2*d**4*x2**2-2*a**4* c**4*d**2*y2**2-4*c**4*y2*a**4*y1**3-4*c**4*y2**3*a**4*y1+2*c**4*b**2*x1**2*a**2*y1**2 +2*c**4*b**2*x1**2*a**2*d**2-2*c**2*b**2*x1**2*a**2*d**2*x2**2+2*c**4*b**2*x1**2*a**2*y2 **2+2*c**2*a**4*y1**2*d**2*x2**2+2*c**2*a**4*b**2*d**2*x2**2+2*c**2*a**4*d**2*x2**2*y2 **2-4*c**4*y2*a**2*y1*b**2*x1**2+4*c**4*y2*a**4*y1*b**2+4*c**4*y2*a**4*y1*d**2-4*c** 2*y2*a**4*y1*d**2*x2**2 %the coefficient of the x^4 term in the quartic var a4 := c**4*b**4+a**4*d**4-2*c**2*b**2*a**2*d**2 %the coefficient of the x^3 term var a3 := 4*c**2*b**2* a**2*d**2*x2+4*c**2*b**2*x1*a**2*d**2-4*a**4*d**4*x2-4*c**4*b**4*x1 %the coefficient of the x^2 term var a2 := 6*a**4*d** 4*x2**2-2*c**2*b**2*a**2*d**2*x2**2+2*c**2*a**4*d**2*y2**2-2*c**4*b**4*a**2+2*c**4*b**2 *a**2*y1**2-4*c**4*y2*a**2*y1*b**2+2*c**4*b**2*a**2*d**2+6*c**4*b**4*x1**2+2*c**2*a**4 *y1**2*d**2-2*c**2*b**2*x1**2*a**2*d**2+2*c**2*a**4*d**2*b**2-4*c**2*y2*a**4*y1*d**2-2 *c**2*a**4*d**4+2*c**4*b**2*a**2*y2**2-8*c**2*b**2*x1*a**2*d**2*x2 %the coefficient of the x term var a1 := -4*c**4*b**2 *x1*a**2*d**2+4*c**4*b**4*x1*a**2+4*c**2*b**2*x1*a**2*d**2*x2**2+8*c**4*y2*a**2*y1*b **2*x1-4*c**2*a**4*d**2*x2*y2**2-4*c**2*a**4*d**2*x2*y1**2-4*a**4*d**4*x2**3-4*c**4*b **2*x1*a**2*y1**2+4*c**2*b**2*x1**2*a**2*d**2*x2-4*c**4*b**4*x1**3-4*c**4*b**2*x1*a**2 *y2**2+4*c**2*a**4*d**4*x2+8*c**2*y2*a**4*y1*d**2*x2-4*c**2*a**4*d**2*x2*b**2 %the discriminant of the quartic; will be negative if there are exactly two roots var D := ((a1*a2*a3)**2 - 4*(a1*a3)**3 - 4*a1**2*a2**3*a4 + 18*a1**3*a2*a3*a4 - 27*a1**4*a4**2 + 256*(a0*a4)**3) + a0*(-4*a2**3*a3**2 + 18*a1*a2*a3**3 + 16*a2**4*a4 - 80*a1*a2**2*a3*a4 - 6*a1**2*a3**2*a4 + 144 * a1**2 * a2 * a4**2) + a0**2*(-27*a3**4 + 144*a2*a3**2*a4 - 128*(a2*a4)**2 - 192*a1*a3*a4**2) %check if the discriminant is less than 0 %also check for trivial intersections that the discriminant may not pick up %due to rounding errors using the similar ellipse - similar ellipse expression if D < 0 or ((x2 - x1) / (a + c)) ** 2 + ((y2 - y1) / (b + d)) ** 2