Homework #1 : Collision Detection (Due: Tuesday April 3rd at 5:30pm) Prelimniaries
Each week, the homework may begin with a Preliminaries section that contains additional information you’ll need to know in order to complete your homework. Please make sure to ALWAYS read this section and use the lecture slides provided each week in order to successfully complete your assignments.
For this week, the Prelimniaries will demostrate to you a few Haskell features that you’ll need to complete Homework #1.
- One way to represent a rational number is to represent the integer portions as a tuple. For example,
However, the type of myRational (i.e., (Integer,Integer)) could be confusing to a reader because it’s not clear from the type signature that this variable should only be used in expressions that can handle rational numbers. A 2-tuple of Doubles could potentially represent anything.
To provide better type clarification, we can use the type keyword to introduce a new name (a synonym) for an existing type:
Now, we can rewrite the above variable with a better understaning of its use:
- You can easily convert a number type (e.g., Integer, Double, Float, Tuple of atomic types, etc) to a string using the show function:
- Review the slides presented in class. In particular, look over the slides 41-43, and 49-52. Post on Piazza if you have any questions.
- I recommend looking at the practice lab Practice: Haskell Practices. I provide the solutions for that practice assignment. The style and format should look very similiar to the functions you’ll write for this homework assignment.
myRational :: (Integer, Integer) myRational = (1,3)
type Rational = (Integer, Integer)
Note: The type keyword it does not create a new type. It is only an alias for anoter type. We will talk about defining new types in the next lecture.
myRational :: Rational myRational = (1,3)
Prelude> show 4 "4" Prelude> show 4.5 "4.5"
Part 1: Repository Checkout
- Your repository has already been setup on GitLab . You can checkout your repository using this command in the terminal: git clone https://mit.cs.uchicago.edu/mpcs51400-spr-18/yourusername.git
replacing yourusername by your CNet username in lowercase. You will be prompted for your CNet password. If you get a prompt asking you if you would like to accept the certificate, press p (meaning to accept permanently).
(For example, since my username is lamonts, I would type git clone https://mit.cs.uchicago.edu/mpcs51400-spr- 18/lamonts.git.)
If you registered late or not at all, this step may not work for you. Please let me know that you do not have a repository yet. You will need to submit your work through e-mail rather than Git until your Git repository is setup.
You will notice nothing is inside your repository yet. You will begin to add files and directories to your repository in this homework assignment.
- As a git refresher, when you add additional or modify files to your repository you need to ALWAYS use git add followed by the file or directory name. After adding the file to your repository, you need to commit the file/directory to your local repository using git commit -m “A commit message” .
- Once you have compeleted making modification locally, you will need to commit your files/directories to the central repository using git push origin master .
The specific steps for commiting your code is described in Part 5: Submission.
Part 2: Initial Setup
Before you begin implementing your assignment, you will need to perform a few preliminary steps:
- Create a directory called hw1 inside your repository. It must be specifically called hw1 with all lowercase letters.
- Inside your hw1 directory, create a file called CollisionDetection.hs . Again, the name of the file must match exactly as
CollisionDetection.hs .
Note: Failing to name your files and directories as specified in the homework will incur point penalities. - Inside the CollisionDetection.hs file, provide a header documentation that provides the name of the file, your name, and a description of whats inside the file. For example:
Part 3: Collision Detection Types
In this week’s homework assignment, you will develop and test common collision detection algorithms that are used in various applications such as video games, computer animation, and robotics. Collision detection, simply put, is detecting if two (or more) objects are intersecting. Specifically, you will implement algorithms for checking if 2D objects are colliding with each other.
{-
File : CollisionDetection.hs
Copyright : (c) Lamont Samuels, 09/24/17
Contains types for representing 2D objects and collision functions for them.
-}
Note: You are allowed to perform a search for the algorithms described by the functions below. Please just cite your sources website at the top of of CollisionDetection.hs file. Specifically, here are links to helpful sites that provides psuedocode for the following functions: collision detection reference #1 and collision detection reference #2
Note: You code should be modular (i.e., broken down into functions). Don’t try to do everthing in one function. Write helper functions when needed.
rectsIntersect :: BoundingBox -> BoundingBox -> Bool
rectLineIntersect :: LineSegement -> BoundingBox -> Bool
circlesIntersect :: Circle -> Circle -> Bool
circleLineIntersect :: LineSegement -> Circle -> Bool
Before you implementing these algorithms, you need to define a few types at the top of your CollisionDetection.hs file using the type meachism:
Point : A point is a tuple where it’s fields are Doubles that represent its x and y coordinate.
LineSegment : A line segment is a straight line defined by two points (i.e., a starting and ending point). A LineSegment
is a tuple of two Points.
BoundingBox : One way to represent 2D objects is to place them in axis-aligned rectangles, which means that each line segment of the rectangle runs parallel to either the x-axis or the y-axis. It is ideal to represent rectangular objects within a bounding box because it is fast to calculate a collision.
A BoundingBox will be defined by having a left, top, bottom and right edge, which all should have type, LineSegment. Represent a bounding box as a tuple of four LineSegments.
Circle : Similar to bounding-boxes, representing circular 2D objects are circles or spheres (3D) is also a fast way to determine whether they intersect. This representation is usually ideal if accuracy is not important or the objects rotate a fair amount.
A Circle is defined as a tuple that contains a center ( Point ), and radius ( Double ).
Part 4: Collision Detection Functions
Now, lets write a few collision detection functions that uses the data types you defined in the previous part. These will also go inside the CollisionDetection.hs file.
rectsIntersect : This function returns true if two BoundingBoxes collide.
rectLineIntersect : This function returns true if a LineSegment intersects with a BoundingBox.
circlesIntersect : This functions returns true if two Circles collide.
circleLineIntersect : This function returns true if a LineSegment intersects with a Circle.
You do not have to provide test cases for your functions but please make sure you fully test these functions before submitting them. Remember you can test them in the REPL.
Part 5: Submission
Make sure to sumbit your hw1 and collision detection file to your repository. Here are the steps that you could perform to submit the files:
1. Make sure your inside your repository at the root that contains the proj1 directory. 2. git add hw1
3. git commit -m “Adding hw1 directory with the CollisionDetection.hs file”
4. git push origin master
Also make sure to provide a little comment for each collision detection function. Just a one line comment before the type signature will suffice.