ENGGEN 131, Semester Two, 2020 - 1 - C Programming Project ENGGEN 131 – Semester Two – 2020 C Programming Project Traffic Jam Deadline: 11:59pm, Saturday 31st October Worth: 12% of your final grade ENGGEN 131, Semester Two, 2020 - 2 - C Programming Project A note before we begin… Welcome to the C Programming project for ENGGEN131 2020! This project is organized around a series of tasks. For each task there is a problem description, and you must implement one function to solve that problem. In addition to the required function, you may define other functions which the required function calls upon (i.e. so-called helper functions). Using helper functions is often a useful way to organize your code, as several simpler functions can be easier to read and understand than one complex function. Do your very best, but don’t worry if you cannot complete every task. You will get credit for each task that you do solve (and you may get partial credit for tasks solved partially). IMPORTANT - Read carefully This project is an assessment for the ENGGEN131 course. It is an individual project. You do not need to complete all of the tasks, but the tasks you do complete should be an accurate reflection of your capability. You may discuss ideas in general with other students, but writing code must be done by yourself. No exceptions. You must not give any other student a copy of your code in any form – and you must not receive code from any other student in any form. There are absolutely NO EXCEPTIONS to this rule. Please follow this advice while working on the project – the penalties for plagiarism (which include your name being recorded on the misconduct register for the duration of your degree, and/or a period of suspension from Engineering) are simply not worth the risk. Acceptable Unacceptable Describing problems you are having to someone else, either in person or on Piazza, without revealing any code you have written Asking for advice on how to solve a problem, where the advice received is general in nature and does not include any code Discussing with a friend, away from a computer, ideas or general approaches for the algorithms that you plan to implement (but not working on the code together) Drawing diagrams that are illustrative of the approach you are planning to take to solve a particular problem (but not writing source code with someone else) Working at a computer with another student Writing code on paper or at a computer, and sharing that code in any way with anyone else Giving or receiving any amount of code from anyone else in any form Code sharing = NO The rules are simple - write the code yourself! OK, now, on with the project… ENGGEN 131, Semester Two, 2020 - 3 - C Programming Project Task One: “Build it and they will come” (10 marks) It’s time to build the road! The road is represented by a 2-dimensional grid. The size of the grid is given by two constants: NUM_ROWS and NUM_COLS. As the names of these constants suggest, the first constant indicates how many rows the grid contains, and the second constant indicates the number of columns. Initially, these two constants are set to the following values: #define NUM_ROWS 8 #define NUM_COLS 8 In addition, there are three other constants that have been defined: #define SPACE 0 #define WALL -1 #define EXIT -2 These three constants represent possible states for a particular location on the grid. For this task, you should define a function that initializes the grid. The grid should be initialized according to the following three rules: 1) Every element on the outer border of the grid should be a wall 2) Every element within the grid should be an empty space 3) There should be one special element, somewhere on the wall, which is the exit The prototype declaration of this function is as follows: void InitialiseRoad(int road[NUM_ROWS][NUM_COLS], char side, int pos) The function takes three inputs: A two-dimensional array that represents the road – this is the array that should be initialized by the function (i.e. the function should modify the array). Typically, the array would be declared in the main() function for the program (i.e. that is where the space would be allocated), and then passed to the InitialiseRoad() function as input. A character that indicates which of the four walls should contain the exit (this character will be ‘N’, ‘E’, ‘W’ or ‘S’ representing the four compass directions). An integer that indicates how many rows down from the top (or columns across from the left) the exit position should be placed on the specified wall. ENGGEN 131, Semester Two, 2020 - 4 - C Programming Project For example, if the InitialiseRoad() function was called as follows: InitialiseRoad(road, 'E', 3); then the two-dimensional array (called road) should be initialized to contain the following values: { { -1, -1, -1, -1, -1, -1, -1, -1 }, { -1, 0, 0, 0, 0, 0, 0, -1 }, { -1, 0, 0, 0, 0, 0, 0, -1 }, { -1, 0, 0, 0, 0, 0, 0, -2 }, { -1, 0, 0, 0, 0, 0, 0, -1 }, { -1, 0, 0, 0, 0, 0, 0, -1 }, { -1, 0, 0, 0, 0, 0, 0, -1 }, { -1, -1, -1, -1, -1, -1, -1, -1 } } Notice how every internal value is 0, and how every value on the outer border is -1. In addition, the value -2 appears exactly 3 rows down from the top (counting from 0) on the eastern wall of the grid. Assumptions You can assume that the input values to the function will be sensible. That is, the array will already have been declared, the direction will be a capital letter that is either ‘N’, ‘E’, ‘W’ or ‘S’, and the position of the exit will be a valid value such that the exit is positioned on one of the walls (note – it will not be in a corner, such as row 0 and column 0). ENGGEN 131, Semester Two, 2020 - 5 - C Programming Project Task Two: “Bird’s eye view” (10 marks) Now that you are able to initialize the road, it is time to display it. For this task you should define a function that prints the grid. It won’t look very nice to print out the numbers that are stored in the array, so they should be stylized appropriately. The prototype declaration of this function is as follows: void PrintRoad(int road[NUM_ROWS][NUM_COLS]) The function takes just one input, which is the two-dimensional array containing the data for the road. When displaying the grid, you should use the ‘#’ character to represent a wall, the ‘ ’ (space) character to represent a space and the ‘O’ (capital O) character to represent the exit. Each row of the grid that is printed out should be followed by a single newline character. You should not print any additional spaces either before or after a row. For example, the following code which initializes and then prints the grid: InitialiseRoad(road, 'N', 6); PrintRoad(road); should produce the following output: ######O# # # # # # # # # # # # # ######## Notice that the exit is positioned on the North wall, and in column 6 (counting from 0). ENGGEN 131, Semester Two, 2020 - 6 - C Programming Project Task Three: “Grid lock” (10 marks) It will be useful to have some measure of how bad the traffic is. One possible measure would be the percentage of usable road space that is currently occupied by cars. For this task, you should define a function to compute this percentage. Now, because we haven’t yet added any cars to the road, the percentage will be 0%. However, when we start adding cars to the road, this percentage will increase. If all available space on the road is occupied by a car, then the percentage will be 100%. The prototype declaration of this function is as follows: double PercentUsed(int road[NUM_ROWS][NUM_COLS]) The function takes just one input, which is the two-dimensional array containing the data for the road. This will be more interesting once we have cars on the road, however let’s look at an example now. For example, consider the following code which initializes and then prints the grid, and then calls the PercentUsed() function: InitialiseRoad(road, 'S', 2); PrintRoad(road); printf("Percent used: %f\n", PercentUsed(road)); The code above should produce the following output: ######## # # # # # # # # # # # # ##O##### Percent used: 0.000000 Notice that the exit is positioned on the Sorth wall, and in column 2 (counting from 0). Also note that the PercentUsed() function returned 0.0. This is because currently, there are no cars on the road (i.e. in the internal part of the grid). ENGGEN 131, Semester Two, 2020 - 7 - C Programming Project Task Four: “Send in the cars” (10 marks) Now it’s time to add cars to the road. Cars will be added one at a time, one after another. The first car added will be car ‘A’, the second car added will be car ‘B’ and so on. Cars are either oriented horizontally or vertically on the grid, and can be various sizes (i.e. each car may occupy a different number of places on the grid). The minimum size of a car is 2 (or else it isn’t possible to see which way it is oriented!). When a car is added, its location on the grid is specified with a row and column position – this row and column position represents the left-most or upper-most part of the car. The size of a car is specified by an integer – the magnitude of the integer represents the length of the car. If the size is a positive integer, then the car is oriented horizontally. If the size is a negative integer, then the car is oriented vertically. The prototype declaration of this function is as follows: void AddCar(int road[NUM_ROWS][NUM_COLS], int row, int col, int size) The function takes four inputs: The two-dimensional array representing the road The row and column position of the location of the car (remember, for a vertical car this is the upper-most part and for a horizontal car this is the left-most part) The size of the car (either positive or negative, representing a horizontal or vertical orientation for the car, respectively) For example, the following code adds two cars to the road by calling the AddCar() function twice: InitialiseRoad(road, 'E', 3); AddCar(road, 3, 1, 2); AddCar(road, 2, 4, -4); PrintRoad(road); printf("Percent used: %f\n", PercentUsed(road)); and this code would produce the following output: ######## # # # B # #AA B O # B # # B # # # ######## Percent used: 16.666667 ENGGEN 131, Semester Two, 2020 - 8 - C Programming Project Note how the cars are labelled with letters based on the order they were added to the road. The first car added to the road is car ‘A’, and is represented by that symbol when the road is printed. Likewise, the second car is car ‘B’ and is represented by that symbol. Handling collisions Collisions are not good! When implementing the AddCar() function, you must perform error checking to prevent collisions. If the AddCar() function is called and it would add a car to the grid that would collide (i.e. intersect) with an existing car on the grid, then the new car must not be added – in essence, in such a case the function call will have no effect. For example, consider the following code which attempts to add four cars to the road: InitialiseRoad(road, 'E', 3); AddCar(road, 3, 1, 2); AddCar(road, 2, 4, -4); AddCar(road, 5, 3, 3); AddCar(road, 6, 3, 3); PrintRoad(road); printf("Percent used: %f\n", PercentUsed(road)); In this case, the output would be the following: ######## # # # B # #AA B O # B # # B # # CCC # ######## Percent used: 25.000000 Notice that in the code above, the third call to AddCar() attempts to add a horizontal car starting at location (5, 3) and with length 3. This would cause a collision with car ‘B’ and so it is not added to the road. Therefore, the fourth function call to AddCar() in the code – which places a horizontal car of size 3 at location (6, 3) – actually generates the car labelled ‘C’. In a similar fashion, if the AddCar() function is called and it would place a car outside the grid, or overlapping or intersecting with a wall or the exit, then it must not be added. Only if the car can be added to the internal part of the grid, and without colliding with another car, should it be added. Assumptions Given the way the cars are labelled, you can assume there will be no more than 26 cars on the road at any one time. You can also assume that the minimum size for a car will be specified as 2 (either “2” for a horizontal car or “-2” for a vertical car). ENGGEN 131, Semester Two, 2020 - 9 - C Programming Project Task Five: “Dude, where is my car?” (10 marks) Ultimately, we want to be able to move the cars on the road. To help with this, it will be useful to have a way to easily locate the position of any car. We will do this with a function called FindCar(). For this task, you must define the FindCar() function. The prototype declaration of this function is as follows: void FindCar(int road[NUM_ROWS][NUM_COLS], char move, int *rowStart, int *colStart, int *rowEnd, int *colEnd) The function takes six inputs: The two-dimensional array representing the road The letter representing the car being searched for (e.g. ‘A’ or ‘C’) Four pointer variables which will be used to store the result of the function call The FindCar() function will locate the specified car, and it will store the location of the left- most or upper-most part of the car in rowStart and colStart, and it will store the location of the right-most or lower-most part of the car in rowEnd and colEnd. For example, consider the code below: int rowA, colA, rowB, colB; InitialiseRoad(road, 'E', 3); AddCar(road, 3, 1, 2); AddCar(road, 2, 4, -4); AddCar(road, 5, 3, 3); AddCar(road, 6, 3, 3); PrintRoad(road); printf("Percent used: %f\n", PercentUsed(road)); FindCar(road, 'A', &rowA, &colA, &rowB, &colB); printf("Car A is at: (%d, %d) - (%d, %d)\n", rowA, colA, rowB, colB); FindCar(road, 'B', &rowA, &colA, &rowB, &colB); printf("Car B is at: (%d, %d) - (%d, %d)\n", rowA, colA, rowB, colB); FindCar(road, 'C', &rowA, &colA, &rowB, &colB); printf("Car C is at: (%d, %d) - (%d, %d)\n", rowA, colA, ENGGEN 131, Semester Two, 2020 - 10 - C Programming Project rowB, colB); The output produced by this code would be: ######## # # # B # #AA B O # B # # B # # CCC # ######## Percent used: 25.000000 Car A is at: (3, 1) - (3, 2) Car B is at: (2, 4) - (5, 4) Car C is at: (6, 3) - (6, 5) Notice that the last three lines of output show the locations of the three cars. In each case, the first coordinate shown is the upper-most or left-most part of the car, and the second coordinate is the right-most or lower-most part. Here is one more example. Consider the code below: int rowA, colA, rowB, colB; InitialiseRoad(road, 'E', 3); AddCar(road, 1, 1, 6); AddCar(road, 2, 1, 6); AddCar(road, 3, 1, 6); AddCar(road, 4, 1, 6); PrintRoad(road); printf("Percent used: %f\n", PercentUsed(road)); FindCar(road, 'A', &rowA, &colA, &rowB, &colB); printf("Car A is at: (%d, %d) - (%d, %d)\n", rowA, colA, rowB, colB); FindCar(road, 'B', &rowA, &colA, &rowB, &colB); printf("Car B is at: (%d, %d) - (%d, %d)\n", rowA, colA, rowB, colB); FindCar(road, 'C', &rowA, &colA, &rowB, &colB); printf("Car C is at: (%d, %d) - (%d, %d)\n", rowA, colA, rowB, colB); FindCar(road, 'D', &rowA, &colA, &rowB, &colB); printf("Car D is at: (%d, %d) - (%d, %d)\n", rowA, colA, rowB, colB); ENGGEN 131, Semester Two, 2020 - 11 - C Programming Project This time, the output would be as follows: ######## #AAAAAA# #BBBBBB# #CCCCCCO #DDDDDD# # # # # ######## Percent used: 66.666667 Car A is at: (1, 1) - (1, 6) Car B is at: (2, 1) - (2, 6) Car C is at: (3, 1) - (3, 6) Car D is at: (4, 1) - (4, 6) ENGGEN 131, Semester Two, 2020 - 12 - C Programming Project Task Six: “Where do you think you’re going?” (10 marks) Now, finally, we are ready to drive! If only there wasn’t so much traffic! For this task, you will write a function called MoveCar(). This function is responsible for updating the position of a car that moves. All cars follow a very simple set of three rules when they move: 1) Cars always move left or up if they can. That is, a horizontal car will always move to the left if there is space to its left, and a vertical car will always move up if there is space above it. 2) If a car can’t move left or up, then it moves right or down, as long as there is space. 3) Cars always move as far as they possibly can. That is, when a car moves, it moves as many spaces as possible until it hits a wall or another car. The prototype declaration of this function is as follows: int MoveCar(int road[NUM_ROWS][NUM_COLS], int r0, int c0, int r1, int c1) The function takes five inputs (and returns one output): The two-dimensional array representing the road Four integer values representing the position of the car to move – these values will be the result returned by the FindCar() function. That is, the first two values specify the location of the upper-most or left-most part of the car, and the second two values specify the location of the right-most or lower-most part of the car. To see the MoveCar() function in action, consider the following example which places two cars on the road, then prints the road, then moves car ‘B’, then prints the road again: int rowA, colA, rowB, colB; int result; InitialiseRoad(road, 'E', 3); AddCar(road, 3, 1, 2); AddCar(road, 3, 4, -3); PrintRoad(road); // Move car B: FindCar(road, 'B', &rowA, &colA, &rowB, &colB); result = MoveCar(road, rowA, colA, rowB, colB); printf("Result = %d\n", result); PrintRoad(road); ENGGEN 131, Semester Two, 2020 - 13 - C Programming Project The output produced by the code above is as follows: ######## # # # # #AA B O # B # # B # # # ######## Result = 0 ######## # B # # B # #AA B O # # # # # # ######## Notice that in this case, the car labelled ‘B’ has moved as far upwards on the grid as possible – in accordance with the rules laid out previously. If the car labelled ‘B’ was moved again, it would move all the way down to the bottom of the grid, as follows: ######## # # # # #AA O # B # # B # # B # ######## Basically, and summarizing the previous rules, cars move as far as possible (and will move left or up if there is space to do so, otherwise down or right). Notice also that the MoveCar() function returns an output value. In the example above it returned the output value 0. The goal is to try to move a car so that it reaches the exit location. If the MoveCar() function is called, and the car that is moved reaches the exit location, then the function should return 1. In this case, if the road is printed again, there will be a car immediately next to the exit. ENGGEN 131, Semester Two, 2020 - 14 - C Programming Project To illustrate this, consider the following code: int rowA, colA, rowB, colB; int result; InitialiseRoad(road, 'E', 3); AddCar(road, 3, 1, 2); PrintRoad(road); // Move car A: FindCar(road, 'A', &rowA, &colA, &rowB, &colB); result = MoveCar(road, rowA, colA, rowB, colB); printf("Result = %d\n", result); PrintRoad(road); This time, the output is as follows: ######## # # # # #AA O # # # # # # ######## Result = 1 ######## # # # # # AAO # # # # # # ######## The car labelled ‘A’ is moved, and it moves towards the right (because it wasn’t possible to move to the left). When it hits the wall, it has actually reached the exit position – and for this reason, the MoveCar() function returns the value 1. Basically, the MoveCar() function returns 1 only if the car that is moved travels towards the exit position and reaches the exit. In all other cases, the MoveCar() function returns 0. ENGGEN 131, Semester Two, 2020 - 15 - C Programming Project Task Seven: “Nothing is constant” (10 marks) Actually, you may already be finished! You should have implemented all of the previous functions so that they work correctly on any sized rectangular grid. If you modify the constant definitions: #define NUM_ROWS 8 #define NUM_COLS 8 to different values other than 8, then the simulation should still work exactly as described. For this final task, you should check that this is indeed the case. For example, consider the following constant definitions: #define NUM_ROWS 7 #define NUM_COLS 18 and the code below which creates a road and adds three cars, and then prints the road: InitialiseRoad(road, 'S', 6); AddCar(road, 2, 6, -3); AddCar(road, 4, 14, -2); AddCar(road, 5, 3, 9); PrintRoad(road); This would produce the following output: ################## # # # A # # A # # A B # # CCCCCCCCC B # ######O########### In this case, in order for car ‘A’ to be able to reach the exit, car ‘B’ must be moved first, followed by car ‘C’. The following sequence of moves would be required in order to have car ‘A’ reach the exit: B, C, C, A, A Note, cars ‘C’ and ‘A’ need to be moved twice. The first time car ‘C’ is moved, it would move to the left. Likewise, the first time that car ‘A’ is moved, it would be move up. ENGGEN 131, Semester Two, 2020 - 16 - C Programming Project Resource files You should begin by downloading the resource file from Canvas: “Project2Resources.zip”. Inside this archive you will find two source files: project2.c traffic_simulation.c You should begin with “project2.c”. This program contains a very simple main() function which does the following: int road[NUM_ROWS][NUM_COLS]; /* Simple test code for Tasks 1 and 2 */ InitialiseRoad(road, 'E', 3); PrintRoad(road); If you compile and run this program, you will see the following output: C:\MyFiles\Project2Resources> project2 Define the InitialiseRoad() function Define the PrintRoad() function If you examine the source file, you will see that the InitialiseRoad() and PrintRoad() functions have been defined, but both definitions are incorrect. You should correctly implement these two functions so that the output produced is as follows: C:\MyFiles\Project2Resources> project2 ######## # # # # # O # # # # # # ######## When you have finished all of the tasks, you should place your function definitions into the “traffic_simulation.c” file. This program provides a more complete main() function, which gets input from the user and allows you to move the cars around the road. This will provide a more robust program with which to test your function definitions. That’s it - good luck!
欢迎咨询51作业君