This assignment has been closed on October 09, 2023.
You must be authenticated to submit your files

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

In the figure, you see three different trajectories:

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.

  1. Download the handin of the tutorial CSE201-td2-1-handin.zip.
  2. Extract the handin of the tutorial. This will create the folder CSE201-td2-1-handin.
  3. 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 file td2.pro.

At this point you should be able to:

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:

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!):

Upload form is only available when connected

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
    in >> x; // DO NOT CHANGE
    in >> y; // DO NOT CHANGE
}

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:

2. Generate a target and an obstacles

Implement the functions:

void generate_target(double &x1, double &y1);
void generate_obstacle(int &i, int &j);

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);

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 = target_ptr + 1; // or just use 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:

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