< Day Day Up > |
Applications in Collision DetectionThere will be times in game programming when you'll want to know if and where two lines intersect. The lines might represent the side of a building or the ground or the path of an object. You might need to program a conditional based on the intersection of two such lines. Now that you know how to find the equations of these lines, you can put the two equations together to form a system of linear equations. Then you can solve the system mathematically. This section first discusses the three types of solutions you might find, and then it describes methods of finding the numeric solution. When solving a system of two linear equations, you're really searching for the intersection of two lines. The solution set is the set of all the points that satisfy both equations. Figures 1.17, 1.18, and 1.19 illustrate the three possible outcomes for a system of two linear equations. In Figure 1.17, the two lines
Figure 1.17. Two lines intersecting at one point.intersect at exactly one point. This point is labeled P, and on the graph it looks as if P has the coordinates (3,1). This is easy to verify; just plug these coordinates into each equation to check. The graph doesn't always show the point of intersection so clearly. The next section looks at how to calculate the point of intersection numerically.
Notice that the graphs of these two lines have different slopes. In Figure 1.18, the lines
Figure 1.18. Two lines that coincide.coincide, or overlap. This time the solution set is not just one point; it's the infinite set of all the points on either line. Notice that the graphs of these two equations have the same slope and the same y-intercept. Finally, in Figure 1.19, the two lines
Figure 1.19. Two lines that never intersect.are parallel. The solution set is the empty set, because the two equations have no points in common. They will never intersect. Notice that the graphs of these two equations have the same slope but different y-intercepts. As you can see, the number of solutions for a system of linear equations is related to the slope and the y-intercept of the equations. Let's summarize the three possibilities.
This is a very systematic procedure that can quickly and easily be implemented in code. Here is the algorithm, or step-by-step process, in pseudocode: Find the slope of both lines, m1 and m2.
Example 1.11: A System of Linear EquationsGraph the following system of linear equations (two lines), and state the size of the solution set (specify how many points of intersection exist).
SolutionBoth lines are graphed in Figure 1.20. It looks as though they intersect at one point close to the point (2,0). The graph isn't always so clear, so verify it numerically using the algorithm:
Figure 1.20. A graph of two lines in Example 1.11.Example 1.12: Line-Line Collision DetectionA ball on the screen is moving along the straight path described by the line x + 2y = 2. A wall has been placed along the line 3x 6y = 6. Will the ball ever hit the wall? SolutionYou could graph these two lines like you did in Example 1.11, but the graphs can sometimes be misleading, so go straight to the algorithm.
This algorithm is very important to use when you're expecting two lines to intersect. What would happen if, in the preceding example, you were expecting the ball to hit the wall? That's rightyou'd get stuck in an infinite loop waiting for something that will never happen. This check can save you headaches in the long run, so verify in the code that the two lines will in fact intersect if that's a crucial part of the gameplay. It's a quick check, so why not use it? After you've checked to see that two lines intersect at one point, you might want to know what that point of intersection is. You can find its coordinates using one of two methods: linear combination or substitution. You might have heard the expression "two equations with two unknowns." This refers to two linear equations with two variables you need to findin this case, x and y. Either of these two methods will work anytime you have two equations and two variables for which to solve. Let's discuss linear combination first. Basically, you use the properties of equality to transform the system of equations into an equivalent system that is easier to work with. You do this by multiplying both sides of an equation by the same nonzero number. You want to multiply each equation by some number so that both equations have either the same x coefficient or the same y coefficient. (Remember that the coefficient is the number in front of the x or the y.) Suppose you have the following system of two linear equations:
Try to transform the system so that both equations have the same y coefficient. To do that, you must first multiply both sides of the top equation by 3. That gives you 9x + 6y = 30, which is still equal to 3x + 2y = 10. Then you multiply both sides of the bottom equation by 2 to get 8x + 6y = 12. This gives you an equivalent system (the same two lines), only this time the y coefficients are equal:
The next step is to combine the two equations into one. You do this by subtracting one from the other. Subtract the bottom one from the top one:
The equation x = 18 is called the linear combination of the two original equations. Now you know that the x-coordinate of the solution is 18. All you have to do now is plug 18 back into one of the original equations to find the y-coordinate. If you plug 18 in for x in the top equation, you get
Therefore, the solution to this system of equations is (18,22). What does this mean? Remember that the solution is the point where the two lines intersect. The following summarizes the steps of the linear combination method:
It might help to step through an example using this new method. Example 1.13: Finding the Point of Intersection Using the Linear Combination MethodA car in your game is traveling along a straight-line path defined by 3x + 5y = 8, and a wall is placed along another line defined by x + 3y = 4. If the car continues on the same path, will it hit the wall? If so, at what point will it hit? Solution
Now let's turn our attention to the second method of solving a system of two linear equations, which is substitution. This method requires a lot of simple algebra. You still have to find the solution one coordinate at a time. First you must choose one of the original equations and solve it in terms of one variable, which means that one variable is on one side of the equals sign while everything else is on the other side. Suppose one of the equations in your system is
To solve this equation in terms of x, you must subtract 2y from both sides, which gives you
Then you substitute that equation for x in the system's second equation. So if the second equation is
substituting gives you
This is where all the algebra comes into play. At this point, you want to solve for y. If you perform the algebra properly, you will find that
The final step is the same as it would be with the linear combination method. You must plug 2 in for y in one of the original equations so that you can solve for x. If you plug it into the first equation, you get
This means that the solution is the point (1, 2). Just as we did for linear combination, let's review the steps for the substitution method:
Now let's step through another example. Example 1.14: Finding the Point of Intersection Using the Substitution MethodSolve the following system using the substitution method:
Solution
This means that the solution is the point (25, 67). Both of the methods discussed in this section can be used to solve any system of two linear equations that has exactly one solution. However, it might be easier to use substitution when one of the variables has a coefficient of 1. Otherwise, it might be easier to use the linear combination method. Knowing which method to use in a particular situation can save you a lot of time. That is why it's a good idea to be comfortable with both methods. So we are now confronted with the question of how to define lines and check for collision between them in code. Consider if we define a line by its slope and any point along that line. In that instance, the equation for a line would look as follows:
where m is the slope of the line and (x1,y1) is any point along the line. Rewriting this in terms of y, and looking at two different lines, we get:
By setting the equations equal to each other and solving for x, we get:
So, let's write a function which, when given two lines, will return their point of intersection. This function assumes that we have already established that these lines are not parallel: // purpose: find the point of intersection between two lines // input: L1Point- a 2D point along our first line // L1Slope- the slope of our first line // L2Point- a 2D point along our second line // L2Slope- the slope of our second line // output: our array of float holding our point float *lineIntersect(float *L1Point, float L1Slope, float *L2Point, float L2Slope) { // A temp array for holding our answer float temp[2] = {0, 0}; // Solve for our x value of the solution temp[0] = (L1Slope * L1Point[0] L2Slope * L2Point[0] + L2Point[1] L1Point[1]) / (L1Slope L2Slope); // Use our new-found value to solve for our y value temp[1] = L1Slope(temp[0] L1Point[0]) + L1Point[1]; return temp; } Self-AssessmentGive the slope and y-intercept for each equation and the number of solutions for the system:
Solve the following systems of linear equations using the linear combination method:
Solve the following systems of linear equations using the substitution method:
|
< Day Day Up > |