CSE 201 - Tutorial 2 - Functions and parameter passing
Adding multiple obstacles and multiple targets
Today you will extend the shooting game we implemented last week adding obstacles to avoided targets to hit. You will work with arrays, pointers, functions, and parameter passing in C++.
The figure below shows the trajectories for 3 projectiles (blue, green, and orange lines), targets (red points), and obstacles (blue boxes).
![Examples of a trajectories with obstacles and targets](resources/trajectories.png)
In the figure, you see three different trajectories:
- a blue trajectory (the topmost one) hitting a target at position \((80,60)\).
- a green trajectory (the one in the middle) that hits an obstacle (and thus does not hit the target).
- an orange trajectory (the one in the bottom) that hits the ground.
The game is bounded in the square \(x \in [0,100], y \in [0,100],\) and the space is subdivided in a grid with \(10 \times 10\)-size cells. The game will randomly place obstacles in some cells of the grid (e.g., in the figure above, the cells filled with the blue color are the cells containing an obstacle). The game will also randomly place the targets and ask the user to shoot a projectile. A projectile will stop when hitting an obstacle or when hitting a target. The projectile destroys a target that was hit, and the user wins the game when all the targets are hit.
You will program the game gradually implementing several functions.
Setting up the tutorial.
- Download the handin of the tutorial
CSE201-td2-1-handin.zip
. - Extract the handin of the tutorial. This will create the folder
CSE201-td2-1-handin
. - Open QT Creator, then go on the menu “File”, then select “Open File
or Project…”. Navigate to the
CSE201-td2-1-handin
folder and select the filetd2.pro
.
At this point you should be able to:
- compile the project (click on the menu “Build”, then “Build Project td2”, or alternatively click on the hammer icon in the bottom left);
- run the automatic grading (click on the menu “Build, then”Run”, or click on the green triangle in the bottom left).
You will only edit the file td2.cpp
and
td2.hpp
.
Evaluation.
You will be evaluated on all the exercises for a total of 100 points. The different exercises gives the following amount of points:
--------------------------------------------------------------------------------
Scores summary:
--------------------------------------------------------------------------------
1 function_signature: 10
2 random: 5
3 generate_multiple: 5
4 test_sort: 20
5 test_collision_target: 10
test_intersect_obstacle: 5
test_collision_obstacles: 10
6 test_remove_target: 20
7 test_simulate_projectile: 15
Note that each exercise usually extends the previous ones and is also harder: so, work on the exercises in order.
Rules for the evaluation:
- A program that does not compile will receive 0
points: this means that your program cannot contain syntax errors (e.g.,
forgetting the
;
sign after a statement) and typing errors (e.g., assigning an array variable to an integer variable); - Each program will be evaluated running on a set of different inputs. You will receive the points for an exercise if your implementation behaves correctly an all the test cases.
Run the automatic grader on your computer first and submit your solution for each exercise as soon as you have one, so we can track the class progress.
Submitting your Work
You will submit your work, both the files
td2.cpp
and td2.hpp
here (SELECT AND
SUBMIT BOTH FILES!):
The deadline for submitting the exercise is next Sunday, October 2nd, at 23:59 Paris time. The submission site will not accept new solutions after that date.
IMPORTANT: your final grade is the one that the server computes (and not what you see on your machine).
1. Fix the function signature
The function read_point
, compute_distance
,
and td2_max
are already implemented in td2.cpp
but are not correct. The bugs in all the functions are
not in the body of the functions but in their function
signature (i.e., the signature of a function is its name and
the sequence of parameter types of the
function) or their return type.
For example, observe the definition of the function
read_point
(use the comments to know what line you should
change):
void read_point(std::istream &in, // DO NOT CHANGE
double x, // YOU CAN CHANGE THIS LINE
double y) { // YOU CAN CHANGE THIS LINE
>> x; // DO NOT CHANGE
in >> y; // DO NOT CHANGE
in }
Your goal is to change the lines double x
and
double y
to fix the bug in the function. Note that in all
the function you fix the bug changing some of the lines
commented with // YOU CAN CHANGE THIS LINE
.
WARNING: be careful that the the function
read_point
(and all the others) are also declared
in the header file td2.hpp
. In C++ you have to use header
files (.hpp
) to declare that a function is
available so that you can use the function elsewhere (e.g., call the
function from another .cpp
file). Technically, this happens
using the #include
directive: #include td2.hpp
has the effect of “copying” the content of td2.hpp
in place
of the #include
directive (all of this process is
transparent to you and the compilation programs take care of this
step).
What is important for this exercise is that, whenever you change
either the signature or the return type of the function
in the td2.cpp
file, you also have to change the function
declaration in the td2.hpp
file, otherwise you will get an
error when compiling saying something like “symbol not found”.
Here there are some hints about the bugs in the functions you have to fix:
the
read_point
function reads two values of typedouble
from the input streamin
, storing the first value inx
and the second value iny
so that they will contain the stored value after the invocation to the function.However, the function does not change the value of
x
andy
as expected . The current function does not change the value of the variables you would pass as actual parameters for thex
andy
parameters. Theread_point
function could be called by a snipped of code like the following:double x,y; = 0; x = 0; y (x,y); read_point// WRONG: x and y may be different from 0
The automatic grader will report a failed test case like the following:
-------------------------------------------------------------------------------- START TEST - function_signature [FAILURE] read_point called with inputs: 1.000000 2.000000: got first = 0 second = 0 expected first = 1 second = 2
where the expected value of x and y after executing the function is 1 and 2 (the values read from the input), instead of 0 and 0 as computed by the current implementation of
read_point
.the
compute_distance
function incorrectly changes the value of the variables passed for the parametersx1
andy1
(i.e., the function should not have any “side effects”, which means changing the stored values, on the variables that are passed as parameters to the function).Imagine to invoke the
compute_distance
function as follows:int x1,y1,x2,y2; = 1; x1 = 1; y1 = 4; x2 = 4; y2 (x1,y1,x2,y2); compute_distance// WRONG: x1 is not 1 and y1 is not 1 anymore (they should not change after calling compute_distance
the implementation of the
td2_max
function does not return the maximum floating point number (in this case ofdouble
type), but instead an integer. For example:std::cout << max(1.2, 0.3); // WRONG: outputs 1 instead of 1.2
Note that
c++
implicitly converts adouble
number to aninteger
number truncating the decimal part.
2. Generate a target and an obstacles
Implement the functions:
void generate_target(double &x1, double &y1);
void generate_obstacle(int &i, int &j);
generate_target
generates a random target where bothx
andy
are in the range[0,100]
.generate_obstacle
generates a random obstacle. An obstacle occupies a cell in the grid. You will represent an obstacle with the integer coordinates of its bottom left vertex (i
,j
). Using this representation the pair \((0,0)\) represents the obstacle that uses the square with vertices with coordinates (\(0,0\)), (\(0,10\)), (\(10,10\)), and (\(10,0\)). The pair \((5,8)\) represents the obstacle with vertices (\(50,80\)), (\(50,90\)), (\(60,90\)), and (\(60,80\)). The obstacles in the above picture would be representes with the pairs \((5,4),(5,7),(3,6)\).generate_obstacles
generates a random obstacle where bothi
andj
must be assigned to a number in the range[0,9]
.
To generate a random number you can use the function int rand()
defined in the header stdlib.h
(already included in the
td2.cpp
file for you). The function returns a random number
in the range [0, RAND_MAX] (RAND_MAX
is a constant also
declared in the <cstdlib>
header, we included this
already for you). You can use the modulo operator %
in
generate_obstacle
to generate random integers in the range
[0,9]
.
Note that the division operator /
, which you may need to
use, behaves differently if the operands are both integers (integer
division) or if one of the operand is a floating-point number
(double
or float
). For example:
std::cout << 4/10 << std:endl;
std::cout << 4.0/10.0 << std:endl;
Outputs:
0
0.5
You can cast explicitly an int
value to a
double
(or float
) as follows:
std::cout << (double) 4/ (double) 10 << std:endl;
will output Outputs:
0.5
3. Generates multiple targets and obstacles
Implement the functions:
void generate_targets(double *targets, const int num_targets);
void generate_obstacles(int *obstacles, const int num_obstacles);
generate_targets
takes as input a pointer to an arraytargets
of typedouble
containing both thex
andy
coordinates for the targets and an integernum_targets
, the total number of targets stored in the array.IMPORTANT the
targets
array stores thex
andy
coordinates for the target one after the other. For example:- an array containing a single target \((3.5,10.2)\) will be
[3.5,10.2]
(and the number of targets will be 1); - an array with 3 targets \((3.5,10.2)\), \((10,20)\), \((60.5,15)\) will be \([3.5,10.2,10,20,60.5,15]\), and the total number of targets will be 3. We will use this representation for the target during this tutorial.
The function
generate_targets
fills thetargets
array with random targets (just use the functiongenerate_target
to generate a single target).- an array containing a single target \((3.5,10.2)\) will be
generate_obstacles
takes as input a pointer to an array of integers, containing a list of obstacles (i.e., storing thei
andj
coordinates of each left bottom vertex representing each obstacle) and the total number of obstacles (this representation is similar to the representation we use for the targets, with integers instead of floating point numbers).
IMPORTANT: arrays in C++ are represented with
pointers (we will see a more principle representation of an array data
structure using classes later). A pointer does not
carry any information about the size of the array, but it only contains
the address in memory that contains the first element of the array . For
this reason, you cannot know the size of an array only if you have a
pointer variable, like the target
variable in
generate_targets
. Instead, you need to store this size of
the array yourself with an additional integer variable. In the above
function the variable num_targets
stores the number of
targets, and not the total number of elements of the array (since a
target stores two double
numbers, the size of the array is
num_targets * 2
). This is similar for
num_obstacles
).
You can access the elements of the array with the []
operator, for example:
// Prints all the elements of the array targets (note how the loop uses the number of
for (int i = 0; i < num_targets*2; i++)
std::cout << targets[i] << std::endl;
You can also use pointer arithmetic when working with the
target
pointer. For example, you can advance the pointer to
the next element with the expression targets+1
, and
access the element at position 1 using the dereference operator
*(target+1)
:
// Prints all the elements of the array targets
double *target_ptr = target;
for (int i = 0; i < num_targets*2; i++) {
std::cout << *target_ptr << std::endl;
= target_ptr + 1; // or just use target_ptr++;
target_ptr }
4. Sort
Implement the functions:
void sort(double *targets, const int num_targets);
void sort(int *obstacles, const int num_obstacles);
The first function sorts the array targets
by
the coordinate x. For example, the array:
[3.0, 1.0, 1.0, 20.0, 2.0, 0.0]
that contains 3 targets will be sorted as:
[1.0, 20.0, 2.0, 0.0, 3.0, 1.0]
Note how both the coordinates for x
and y
for a single target are moved together!
You can use a simple sorting algorithm like bubble sort to solve this exercise (i.e., we do not check if your code is efficient).
The second function sorts the array obstacles
by
the cell coordinate i. For example, the array
[2, 3, 1, 5]
that contains 2 obstacles will be sorted as
[1,5,2,3]
.
Note also how the two functions have the same name and number of parameters, but it’s ok to declare both of them because the parameters have different types. In practice, also their implementation is almost the same — you will see how to write the implementation of such functions once using templates later in the course.
5. Find collisions with targets and obstacles
Implement the functions:
bool intersect_obstacle(double x1, double y1,
const int i, const int j);
double* find_collision(const double x, const double y,
double *targets, const int num_targets);
int* find_collision(const double x, const double y,
int *obstacles, const int num_obstacles);
The function intersect_obstacle
checks if a projectile
hits an obstacle. A projectile hits an obstacle if it is contained
in the obstacle. For example, the projectile with coordinates \(x=25,y=25\) intersects the obstacle in the
cell \(2,2\). The projectile with
coordinates \(x=20,y=20\) intersects
both the obstacles in the cell \(2,2\)
and \(1,1\).
The function find_collision
applied to targets finds
and returns the first target that collide with the current position
of the projectile x
and y
. The projectile hits
the target if the distance between the projectile and the target is less
or equal than 1. The function find_collision
returns the pointer to the array element that contains
the x
coordinate of the target that was hit.
For example, consider the targets [1.0, 1.0, 5.0, 0.0]
and the projectile at coordinate \(x=4.5,
y=0.5\). The projectile hits the target with coordinate \(5.0, 0.0\) (the distance between that
target and the projectile is less than 1), so the function should return
a pointer to the location containing 5.0 in targets
(i.e.,
targets + 2
). Consider the same targets as above, and the
projectile position \(x=10, y=10\). The
projectile does not hit a target, so the function should return a
“pointer to nothing”. Use the special constant nullptr
in
that case.
Here you need to work with pointer arithmetic to return the address
of the target in the array. For example, the location in the
targets
array for the element starting with 5.0 would be
targets + 2
.
Furthermore, you can assume that the elements in the targets array
are ordered by the x
coordinate of the target, as described
in the previous exercise.
The last find_collision
function finds and returns the
first obstacle that collide with the projectile. As above, the function
can assume that the array is ordered by the i
-th value of
the obstacle pair and returns a pointer to the element in the
obstacles
array that contains the first coordinate of the
obstacle.
For example, the projectile at coordinate \(1.5,1.5\) would intersect the first
obstacle in [1,1,5,5]
, so the function would return just
obstacle
as result.
6. Remove target
Implement the function:
void remove_target(double* targets, int &tot_targets, double* target_to_remove);
that deletes the target stored at target_to_remove
from
the array targets
. That is, the function changes the
targets
array removing the target at
target_to_remove
and decreases the size of the target array
tot_targets
(note that tot_targets
is passed
by reference).
For example, given the target array
[1.0, 1.0, 5.0, 6.0, 10.0, 100.0]
and a pointer to the
element 5.0
as target to remove the function
remove_target
would change the array as
[1.0, 1.0, 10.0, 100.0]
and tot_targets
to
2.
Be careful: target_to_remove
contains an address and not
a value, so you should pay attention when identifying the element in
targets
to remove.
You can further assume tha target_to_remove
is a pointer
to one of the x
coordinates that is in
targets
.
7. Simulate projectiles
Implement the function:
bool simulate_projectile(const double magnitude, const double angle,
const double simulation_interval,
double *targets, int &tot_targets,
int *obstacles, int tot_obstacles)
that simulates the trajectory of a projectile, given its
magnitude
, angle
, and
simulation_interval
, an array of targets, and an array of
obstacles. The function returns true
if the projectile hits
a target and false
otherwise. The function also
removes the hit target from the targets
array.
The function is similar to the function you implemented in the previous tutorial, but this time:
- the projectile trajectory stops if either the projectile hits the ground, or the projectile hits an obstacle, or the projectile hits a target;
- the function further removes the target from the list of targets (the obstacles are not destroyed by the projectile).
Congratulations: now you can play the game yourself.
We implemented a main loop for the game (functions
run_game
and game_loop
): just change the macro
GRADING
to 1
inside the main.cpp
and then re-run the program (this time you will run the game instead of
the automatic grader).