Unit 7Collision Detection

Agenda

• 5 minIntroduction

• 10 min1D Distance

• 20 minThe Distance Formula

• 10 minCollision

• 30 minnext-world

• 15 minGame Brainstorming

Product Outcomes:

• Students will write the distance function

• Students will write the is-collision function

• Students will use different Ask branches to identify collisions in the Ninja Cat games

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.

Length: 90 minutes

Glossary:

• dot-accessors: A way to extract values from a data structure

• hypotenuse: the side opposite the 90-degree angle in a right triangle

Materials:

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

• Class poster (List of rules, design recipe, course calendar)

• Editing environment (Pyret Editor)

• Student workbooks

• Language Table

• Cutouts of Cat and Dog images

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

Preparation:

• Seating arrangements: ideally clusters of desks/tables

Types	Functions
Number	+ - * / num-sqr num-sqrt num-expt
String	string-append string-length
Image	rectangle circle triangle ellipse radial-star scale rotate put-image
Boolean	= > < string-equal and or

Introduction

Overview

Learning Objectives

Evidence Statements

Product Outcomes

Materials

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

• Class poster (List of rules, design recipe, course calendar)

• Editing environment (Pyret Editor)

• Student workbooks

• Language Table

• Cutouts of Cat and Dog images

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

Preparation

• Seating arrangements: ideally clusters of desks/tables

Introduction (Time 5 minutes)

• Right now in the Ninja Cat game, nothing happens when the player collides with another game character. We need to write a function change that. This is going to require a little math, but luckily it’s exactly the same as it was in Bootstrap:1.

  • In the image above, how far apart are the cat and dog?

  • If the cat was moved one space to the right, how far apart would they be?

  • What if the cat and dog switched positions?

  In one dimension, such as on a number line, finding the distance is pretty easy. If the characters are on the same line, you just subtract one coordinate from another, and you have your distance. However, if all we did was subtract the second number from the first, the function would only work half the time!

  When the cat and dog were switched, did you still subtract the dog’s position from the cat’s, or subtract the cat’s position from the dog’s? Why?

  Draw the number line on the board, with the cutouts of the cat and dog at the given positions. Ask students to tell you the distance between them, and move the images accordingly. 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.

1D Distance

Overview

Learning Objectives

Evidence Statements

Product Outcomes

Materials

Preparation

1D Distance (Time 10 minutes)

• Distances cannot be negative, so we have to make sure we are always subtracting the smaller number from the bigger one. That means we have two conditions: (1) the first number is bigger, and (2) the second is bigger.

  • What kind of function do we need, when we have multiple conditions?

  • Turn to Page 27.

  • What is the Name of this function? Domain? Range?

  • Write two examples for line-length so that it subtracts the smaller number from the bigger one. Start with an example using the numbers 23 and 5, then do a second example with 5 and 23 in the other order.

   examples: line-length(23, 5) is 23 - 5 line-length(5, 23) is 23 - 5 end

• Now we have an idea of the results for the ask statement, but an ask expression also needs tests. We want to test to see whether the first number given to line-length is greater than the second number.

  • How would you write that test in Pyret code?

  • And what would the result for that test be? If a is greater than b, which number would we subtract from which?

  • How could you include a test for wheather the two numbers are equal, without adding a third ask branch?

  • Write down the definition for line-length.

   fun line-length(a, b): ask: | a > b then: a - b | b >= a then: b - a end end

  It is possible to replace the second test with otherwise, because there will only be two options: line-length will either subtract b from a, or a from b. (If the numbers are equal, it doesn’t matter which is subtracted.) However, having students write out the full test and result gets them thinking about what exactly is being tested in each branch of the function. It is possible to avoid using a conditional entirely by taking the absolute value of the difference (the function num-abs does this); if you are working with older students who already know about absolute value you could show it. Using ask, however, emphasizes how code structure arises from examples.

The Distance Formula

Overview

Learning Objectives

• Reinforce their understanding of the distance formula

Evidence Statements

Product Outcomes

• Students will write the distance function

Materials

Preparation

The Distance Formula (Time 20 minutes)

• Unfortunately you don’t have any code to calculate the distance in two dimensions. All you have so far is something that tells you the length in only the x- or y-dimension.

  • How could you find the distance between the two points shown in this image?

  • How could you find the length of the C, also called the Hypotenuse?

  Let’s start with what we do know: if we treat the x- and y-intercepts of C as lines A and B, we have a right triangle.

  What is the line-length of A? Would it be different if the triangle pointed downward, and intercepted the point (0, -4)?

  To make your life easier, you can use the function you already wrote: line-length. In this example, line-length(A) is 4 and line-length(B) is 3, but we still don’t know C.

  Draw this image on the board, with the lines labeled "A", "B", and "C".

• 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 hypotenuse 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

  Everyone will have a packet with the same materials, but each group’s triangles are a little different. The activity workes with triangles of all sizes, so each pair will get to test it out on their own triangles. Draw the diagram on the board.

• For 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 $side * side$, then the area of the white space is $C^{2}$.

  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.

• The smaller square has an area of $A^{2}$, and the larger square has an area of $B^{2}$. 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:

  $A^{2} + B^{2} = C^{2}$

  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:

  $\sqrt{A^{2} + B^{2}} = C$

  Pythagoras proved that you can get the square of the hypotenuse by adding the squares of the other two sides. In your games, you’re going to use the horizontal and vertical distance between two characters as the two sides of your triangle, and use the Pythagorean theorem to find the length of that third side.

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

• • Turn to Page 28 of your workbook - you’ll see the formula written out.

  • Draw out the circle of evaluation, starting with the simplest expression you can see first.

  • Once you have the circle of evaluation, translate it into Pyret code at the bottom of the page, starting with  check: distance(4, 2, 0, 5) is... end

  Now you’ve got code that tells you the distance between the points (4, 2) and (0, 5). But we want to have it work for any two points. It would be great if we had a function that would just take the x’s and y’s as input, and do the math for us.

• • Turn to Page 29, and read the problem statement and function header carefully.

  • 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.

  • When finished, type your line-length and distance functions into your game, and see what happens.

  • Does anything happen when things run into each other?

  You still need a function to check whether or not two things are colliding.

  Pay careful attention to the order in which the coordinates are given to the distance function. The player’s x-coordinate (px) must be given first, followed by the player’s y (py), character’s x (cx), and character’s y (cy). Inside the body of the function, line-length can only calculate lengths on the same axis (line-length(px, cx) and line-length(cx, cy)). Just like with making data structures, order matters, and the distance function will not work otherwise. Also be sure to check that students are using num-sqr and num-sqrt in the correct places.

Collision

Overview

Learning Objectives

Evidence Statements

Product Outcomes

• Students will write the is-collision function

Materials

Preparation

Collision (Time 10 minutes)

• So what do we want to do with this distance?

  How close should your danger and your player be, before they hit each other?

  At the top of Page 30 you’ll find the Word Problem for is-collision.

  • Fill in the Contract, two examples, and then write the code. Remember: you WILL need to make use of the distance function you just wrote!

  • When you’re done, type it into your Ninja Cat game, underneath distance.

  Using visual examples, ask students to guess the distance between a danger and a player at different positions. How far apart do they need to be before one has hit the other? Make sure students understand what is going on by asking questions: If the collision distance is small, does that mean the game is hard or easy? What would make it easier?

next-world

Overview

Learning Objectives

• Identify collision as yet another sub-domain which requires different behavior of the next-world function

Evidence Statements

Product Outcomes

• Students will use different Ask branches to identify collisions in the Ninja Cat games

Materials

Preparation

next-world (Time 30 minutes)

• Now that you have a function which will check whether something is colliding, you can use it in Ninja World.

  Out of the four major functions in the game (next-world, draw-world, keypress, and big-bang), which do you think you’ll need to edit to handle collisions?

  We’ll need to make some more branches for ask in next-world. When the cat collides with the dog, we want to put the dog offscreen so that he can come back to attack again.

• • Start with the test: how could you check whether the cat and dog are colliding? Have you written a function to check that?

  • What do the inputs need to be?

  • How do you get the catY out of the world? catX?

  • How do you get the dogX out of the world? dogY?

   | is-collision( current-world.catX, current-world.catY, current-world.dogX, current-world.dogY) then: ...result... Remember that next-world produces a world, so what function should come first in our result?  | is-collision( current-world.catX, current-world.catY, current-world.dogX, current-world.dogY) then: world( ...dogX..., ...dogY..., ...coinX..., ...catX..., ...catY...)

  And what should happen when the cat and dog collide? Can you think of a number that puts the dog off the screen on the left side? What about the dog’s y-coordinate? We could choose a number and always place it at the same y-coordinate each time, but we know a function that can place him at a random y-coordinate...

   | is-collision( current-world.catX, current-world.catY, current-world.dogX, current-world.dogY) then: world( -100, num-random(480), ...coinX..., ...catX..., ...catY...)

  Does the coinX change when the dog and cat collide? How about catY? How do you get each of those things out of the world?

   | is-collision( current-world.catX, current-world.catY, current-world.dogX, 400) then: world( -100, num-random(480), current-world.coinX, current-world.catX, current-world.catY)

  Collision detection must be part of the next-world function because the game should be checking for a collision every time the world is updated. Students may assume that draw-world should handle collision detection, but point out that the Range of draw-world is an Image, and their function must return a new world in order to set the locations of the characters after a collision.

• Take a minute and admire your handiwork: You’ve created your own version of Ninja Cat using Pyret, data structures, and complex functions. This game is already more advanced than your Bootstrap:1 game, and you’ve created it from scratch! Armed with the knowledge of how to create this simple game in Pyret, now it’s time to start thinking about a video game of your own!

Game Brainstorming

Overview

Learning Objectives

Evidence Statements

Product Outcomes

Materials

Preparation

Game Brainstorming (Time 15 minutes)

• Now that you’ve seen the work it takes to create Ninja Cat, you have a good idea about what is needed to create a complex game. For the next exercise, think about the simplest possible version of your game. Once you have that working, you can add advanced features later on. How many characters will you have, and what will you need to have in your World? You can use Numbers to keep track of the score, or the characters’ x- and y-coordinates. You can also store an Image in the world, so that your character can change the way they look or to swap out the background once the score reaches a certain level. Once you have a simple game, it’s easy to add more pieces to the World.

  • Turn to Page 31 in your workbook.

  • Start by drawing a sketch of what your game will look like at the very start, and another sketch of what it will look like one second later, without user input. What elements move on their own?

  • In the table below, list all the images you will need for your game.

  • At the bottom of the page, list all the things that will have changed from one moment to the next. What will you need to keep track of in your world structure? If something moves, will you need to keep track of its x-coordinate, y-coordinate, or both? Will you have a score that changes?

  Remind students that for every single thing that changes in their game, they must have a field in their world structure for it.

• Now that you have a list of everything that changes, it’s time to turn them into a World structure.

  • Turn to Page 32 in your workbooks, and define your world structure, using the changeable things you wrote in the second table of your Game Design page.

  • Underneath your world structure, define two example worlds called worldA and worldB.

  • Finally, write down the dot-accessors you will need to access the fields of worldA.

  Have the class take turns telling their peers about their games. Most importantly, have them tell the class what they have in their World structure.

  • Make sure student names are on page 18

  • Take page 18 itself, or take photos of page 18, to prep game images for the next unit.

  • Images should be in PNG or GIF format. Background images should be 640x480, and character images should generally be no larger than 200px in either dimension. Make sure that the character images have transparent backgrounds!

  • TIP: use animated GIFs for the characters - not only does the animation make the game look a lot better, but these images usually have transparent backgrounds to begin with.

Bootstrap by Emmanuel Schanzer is licensed under a Creative Commons 4.0 Unported License. Based on a work at www.BootstrapWorld.org. Permissions beyond the scope of this license may be available at schanzer@BootstrapWorld.org.