Unit 8:   Collision Detection

imageUnit 8Collision Detection
Unit Overview

Students derive, discuss, and prove the Pythagorean theorem, then use this theorem—in conjunction with Booleans—to detect collisions in their games.

Agenda

Product Outcomes:
  • Students write the distance function in their game files.

  • Students add a collide? function to their games to detect when the player and danger have collided

Standards and Evidence Statements:

Standards with prefix BS are specific to Bootstrap; others are from the Common Core. Mouse over each standard to see its corresponding evidence statements. Our Standards Document shows which units cover each standard.

  • 6.NS.5-8: The student performs operations with negative numbers, works with the number line and coordinate plane, order and absolute value of numbers, and solves real-world problems with rational numbers.

    • calculation of distance between points with the same first coordinate or same second coordinate.

  • 8.F.1-3: The student defines, evaluates, and compares functions

    • description of a function as a rule that assigns to each input exactly one output

    • comparison of properties of two functions each represented in a different way (algebraically, graphically, numerically in tables, or by verbal descriptions)

  • 8.G.6-8: The student uses the Pythagorean Theorem to solve real-world and mathematical problems

    • explanation of a proof of the Pythagorean Theorem and its converse

    • application of the Pythagorean Theorem to determine unknown side lengths in right triangles in real-world and mathematical problems in two and three dimensions

    • application of the Pythagorean Theorem to find the distance between two points in a coordinate system

  • A-SSE.1-2: The student interprets the structure of expressions to solve problems in context

    • manipulation of the structure of an expression, for example, writing x4 _ y4 as a difference of squares

  • F-IF.1-3: The student uses function notation to describe, evaluate, and interpret functions in terms of domain and range

    • description of a function using terms domain and range

  • F-IF.4-6: The student interprets the behavior of functions that arise in applications in terms of the context

    • relation of the domain of a function to its graph and, where applicable, to the quantitative relationship it describes

  • BS-DR.3: Given mutiple test cases, the student can define a function

    • given examples and labeled variable(s), define the function

  • BS-PL.3: The student is able to use the syntax of the programming language to define values and functions

    • defining and using functions

  • BS-PL.4: The student is familiar with the syntax for conditionals

    • defining and using functions than involve conditionals

Length: 85 minutes
Glossary:
  • hypoteneuse: the side opposite the 90-degree angle in a right triangle

Materials:
  • Computers w/ DrRacket or WeScheme

  • Student workbook

  • Pens/pencils for the students, fresh whiteboard markers for teachers

  • Class posters (List of rules, basic skills, course calendar)

  • Language Table (see below)

  • All student computers should have their game templates pre-loaded, with their image files linked in

  • Cutouts of Pythagorean Theorem packets [1, 2] - 1 per cluster of students working together

Preparation:

Types

Functions

Number

+ - * / sq sqrt expt

String

string-append string-length

Image

rectangle circle triangle ellipse star text scale rotate put-image

Boolean

= > < string=? and or


1D Distance

Overview

Students act out a collision in their game, and reason about the mathematical behavior of collision detection

Learning Objectives

  • Students learn how to compute the distance between objects in one dimension

Evidence Statements

  • Students will be able to explain how a Number line is used to calculate distance in one dimension

  • Students will be able to explain why the line-length function uses a conditional

Product Outcomes

    Materials

    • Computers w/ DrRacket or WeScheme

    • Student workbook

    • Pens/pencils for the students, fresh whiteboard markers for teachers

    • Class posters (List of rules, basic skills, course calendar)

    • Language Table (see below)

    Preparation

      1D Distance (Time 20 min)

      • Suppose two objects are moving through space, each one having its own (x,y) coordinates. When do their edges start to overlap? They certainly overlap if their coordinates are identical (x1=x2, y1=y2), but what if their coordinates are separated by a small distance? Just how small does that distance need to be before their edges touch?

        Visual aids are key here: be sure to diagram this on the board!

      • imageIn one dimension, it’s easy to calculate when two objects overlap. In this example, the red circle has a radius of 1, and the blue circle has a radius of 1.5 The circles will overlap if the distance between their centers is less than the sum of their radii (1+1.5 = 2.5). How is the distance between their centers calculated? In this example, their centers are 3 units apart, because 4-1=3.

        Would the distance between them change if the circles swapped places? Why or why not?

        Work through a number of examples, using a number line on the board and asking students how they calculate the distance between the points. Having students act this out can also work well: draw a number line, have two students stand at different points on the line, using their arms or cutouts to give objects of different sizes. Move students along the number line until they touch, then compute the distance on the number line. The first few seconds of our Bootstrap video show this exercise in action.

      • Your game file provides a function called line-length that computes the difference between two points on a number line. Specifically, line-length takes two numbers as input and determines the distance between them.

        What answers would you expect from each of the following two uses of line-length:

        • (line-length 2 5)

        • (line-length 5 2)

        Do you expect the same answer regardless of whether the larger or smaller input goes first?

        If you have time and want to reinforce how conditionals arise from examples, you can have students fill in blanks in Examples such as (EXAMPLE (line-length 2 5) ___), circle what’s different, and notice that the circle labels are in different orders depending on whether the first or the second input is larger. This in turn suggests that the code for line-length will need a conditional. In this case, one could avoid the conditional by taking the absolute value of the difference (the function abs does this); if you are working with older students who already know about absolute value you could show it. Using cond, however, emphasizes how code structure arises from examples.

      • Scroll to the line-length and collide? functions in your game file. Notice that line-length uses a conditional so that it subtracts the smaller number from the bigger one.

        Can you explain why line-length needs to use cond? What are the two conditions?

        The two conditions are:

        • A is less than B

        • B is less than or equal to A

      • imageUnfortunately, line-length can only calculate the distance between points in a single dimension (x or y). How would the distance be calculated between objects moving in 2-dimensions (like your game elements)? line-length can calculate the vertical and horizontal lines in the graphic shown here, using the distance between the x-coordinates and the distance between the y-coordinates. Unfortunately, it doesn’t tell us how far apart the two centers are.

      • imageDrawing a line from the center of one object to the other creates a right-triangle, with sides A, B and C. A and B are the vertical and horizontal distances, with C being the distance between the two coordinates. line-length can be used to calculate A and B, but how can we calculate C?

        Students’ gamefiles all have a value called *distances-color*, which is set to the empty string "". By changing this to a color such as "yellow" or "red", the game will draw right triangles between each game character, and fill in the lengths for each side. You may want to demonstrate this using your own game file, and have the students follow along. Hint: to make it as easy as possible to see these triangles, set your background to be a simple, black rectangle and slow down the animation functions.

      • In a right triangle, the side opposite the 90-degree angle is called the hypoteneuse. Thinking back to our collision detection, we know that the objects will collide if the hypoteneuse is less than the sum of their radii. Knowing the length of the hypoteneuse will be essential to determine when a collision occurs.

      2D Distance

      Overview

      Students explore the Pythagorean Theorem using shapes on paper, then reason about the mathematical behavior of collision detection

      Learning Objectives

      • Students learn that two-dimensional distance corresponds to the hypoteneuse of a right triangle

      • Students learn how to compute the distance between objects in two dimensions

      Evidence Statements

      • Students understand that two-dimensional distance needs a different computation than one-dimensional distance

      • Students can draw out the right triangles that compute the distance between two coordinates

      • Students understand that geometric manipulation is a useful tool for figuring out certain computations

      • Some students can use geometric manipulation to derive the Pythagorean Theorem

      • Students can state the Pythagorean Theorem

      • Students can turn the Pythagorean Theorem into code by writing a distance function

      Product Outcomes

      • Students write the distance function in their game files.

      Materials

      • Computers w/ DrRacket or WeScheme

      • Student workbook

      • All student computers should have their game templates pre-loaded, with their image files linked in

      • Cutouts of Pythagorean Theorem packets [1, 2] - 1 per cluster of students working together

      • Pens/pencils for the students, fresh whiteboard markers for teachers

      • Class posters (List of rules, basic skills, course calendar)

      • Language Table (see below)

      Preparation

      2D Distance (Time 35 min)

      • Ancient civilizations had the same problem: they also struggled to find the distance between points in two dimensions! Let’s work through a way to think about this problem: what expression computes the length of the hypoteneuse of a right triangle?

        This exercise is best done in small groups of students (2-3 per group). Pass out Pythagorean Proof materials [1, 2] to each group, and have them review all of their materials:

        • A large, white square with a smaller one drawn inside

        • Four gray triangles, all the same size

      • imageFor any right triangle, it is possible to draw a picture where the hypoteneuse is used for all four sides of a square. In the diagram shown here, the white square is surrounded by four gray, identical right-triangles, each with sides A and B. The square itself has four identical sides of length C, which are the hypoteneuses for the triangles. If the area of a square is expressed by , then the area of the white space is .

        Have students place their gray triangles onto the paper, to match the diagram.

      • By moving the gray triangles, it is possible to create two rectangles that fit inside the original square. While the space taken up by the triangles has shifted, it hasn’t gotten any bigger or smaller. Likewise, the white space has been broken into two smaller squares, but in total it remains the same size. By using the side-lengths A and B, one can calculate the area of the two squares.

        What is the area of the smaller square? The larger square?

        You may need to explicitly point out that the side-lengths of the triangles can be used as the side-lengths of the squares.

      • imageThe smaller square has an area of , and the larger square has an area of . Since these squares are just the original square broken up into two pieces, we know that the sum of these areas must be equal to the area of the original square:

        Does the same equation work for any values of A and B?

      • To get C by itself, we take the square-root of the sum of the areas:

        Turn to Page 27 in your workbook - you’ll see the same formula written out, this time using line-length to calculate the distance along the x- and y-axis. The Circle of Evaluation has already been partially-completed here, but you’ll have to finish it on your own. Once you’re done, convert that circle into code on the bottom of the page.

        Remind students that A and B are the horizontal and vertical lengths, which are calculated by line-length.

      • The code on page 27 will accurately calculate the distance between two objects whose centers are at (3,0) and (0,4). But what about other points? It would be nice to have a function that calculates the distance for any two sets of points.

        Turn to Page 28 in your workbook, and use the Design Recipe to write your distance function. Feel free to use the work from the previous page as your first example, and then come up with a new one of your own.

        WARNING: make sure students are giving line-length the proper coordinates! Many students mistakenly pair px and py together, rather than pairing the x-coordinates. Check student work carefully!

      collide?

      Overview

      Students reason about the mathematical behavior of collision detection

      Learning Objectives

      • Students learn how to use the distance formula to detect collisions in games

      Evidence Statements

      • Students understand that collisions occur when the distance between objects is below some threshhold

      • Students understand how to determine the collision threshhold between two objects

      • Students write a collide? function that determines whether the player and danger elements in their games have collided

      Product Outcomes

      • Students add a collide? function to their games to detect when the player and danger have collided

      Materials

      • Computers w/ DrRacket or WeScheme

      • Student workbook

      • All student computers should have their game templates pre-loaded, with their image files linked in

      • Pens/pencils for the students, fresh whiteboard markers for teachers

      • Class posters (List of rules, basic skills, course calendar)

      • Language Table (see below)

      collide? (Time 25 min)

      • By now, you have defined a function called distance: it has four Number inputs (representing playerX, playerY, dangerX and dangerY) and produces a Number representing the distance between those coordinates. If the player is standing at (320, 240) and the danger is at (400, 159), the distance can be calculated by evaluating (distance 320 240 400 159).

        For each of the following player and danger coordinates, write the expression that uses the distance function to compute the distance between the points. You may write in code or in a Circle of Evaluation:

        • The player is at (100, 225) and the danger is at (174, 300)

        • The player is at (48, 20) and the danger is at (210, 160)

        • The player is at (300, 60) and the danger is at (130, 240)

      • Now that you know how to compute the distance between two objects, you need to decide when two objects have collided. We discussed this earlier in the unit using circles: two circles collide when the distance between them is less than the sum of their radii. If your objects have more interesting outlines than circles, this computation can be hard to do precisely. Fortunately, most games don’t have to be precise (they move too fast for people to see the exact moment of impact). We just need to figure out when items are close enough, and use that to detect collision.

        You can spend additional time on this point by having students think about collision distances between different shapes. The rest of Bootstrap doesn’t require this, but this may be a good point to integrate additional geometry if you are teaching math.

      • Unless the images you chose for your game are very small, 50 is usually a sufficient distance for detecting collisions between your player and danger. If you are using very small images, you might want to detect a collision when the distance between characters is below 20.

        How would you check whether the distance between (320, 240) and (400, 159) is less than 50? How would you check whether the distance between those coordinates is less than 20?

        We are intentionally being vague about the distance units here. The units are in pixels, which is a notion of distance on a computer screen. If you want to explain pixels to your students, you can introduce that terminology and talk in terms of "50 pixels". Otherwise, you can fall back on the number line if you want to explain units for distance.

        If you want your students to compute a more accurate distance threshhold, you can use the functions image-height and image-width, each of which takes an image as input and returns a number. The returned number is the maximal length of the image along the corresponding dimension (diameter for a circle, width or height for a rectangle or bitmap/url image). You can have students develop, code, and experiment with expressions like to compute the horizontal distance between two objects (where stands for the first object width, etc). This is a significant computational exercise in its own right, which could form the basis of an extended classroom exercise or homework assignment.

      • Turn to Page 29 in your workbook, and use the Design Recipe to write a function that produces true if the distance between two coordinates is less than 50. HINT: You should use your distance function!

        Enter your collide? function definition into your game file. Play your game, and make your player collide with the danger. Does your game now do something different than it did before you wrote collide??

      Closing

      Overview

      Learning Objectives

        Product Outcomes

          Materials

            Preparation

              Closing (Time 5 min)

              • Congratulations - your game is complete! Take a minute to scroll through all the code you’ve written, and think back on how much you’ve learned: The Circles of Evaluation, datatypes like Number, String, Image and Boolean, the importance of Contracts and Purpose Statements, and Piecewise functions. You’ve learned a whole new programming language, and even more importantly you’ve learned the Design Recipe, which lets you solve word problems and programming challenges by focusing on just one step at a time, making sure that each step is checked against the one that came before it.

                Once programmers get something working, they always go back over their code and make sure that it’s readable, clear, and easy for other people to understand. A car that runs well might be nice, but if it’s not worth much if it’s impossible for a mechanic to repair or upgrade! Make sure your code is beautiful, inside and out.

                • Does every function have its contract written out correctly?

                • Does every function have a purpose statement that accurately describes what it does?

                • Does every single function have at least two EXAMPLEs?

                • When you click "Run", do all of your EXAMPLEs pass?

                • Have students volunteer what they learned in this lesson

                • Reward behaviors that you value: teamwork, note-taking, engagement, etc

                • Pass out exit slips, dismiss, clean up.