C Programming in Ubuntu Linux. Instructions in PDF file
COMP 2401 A – Assignment #5 Due: Thursday, December 8 at 11:59 pm 1. Goal For this assignment, you will write a program in C, in the Ubuntu Linux environment of the course VM, that simulates a chase between two heroes and some villains. Our heroes, Timmy Tortoise and Prince Harold the Hare, have foolishly stolen the priceless Emerald of the Isles from the Grand Dragon, Lady Cordelia Cinderwing, PhDTM. Now Lady Cordelia has sent her minions, the dwarf orcs (dorcs) and super-stealth Ninja warriors, to retrieve the treasure from our two heroes as they run for their lives across the Vale of Doom. Your program will simulate the attempted escape by our heroes through the Vale of Doom, as they are pur- sued by Lady Cordelia’s henchmen. Your code will use function pointers and multi-threaded techniques to implement this simulation using a character-based graphics interface. 2. Learning Outcomes With this assignment, you will: • write a program that defines and uses function pointers to simulate generic behaviour • practice writing multi-threaded code • implement a program with a character-based graphical user interface (GUI) 3. Instructions 3.1. Understand the provided base code The base code provided in the a5-posted.tar file contains the structure data types and some basic functions that your code is required to use. NOTE: In this program, “runner” refers to any creature that is participating in the chase through the Vale of Doom, including both heroes (Timmy and Harold) and all villains (dorcs and Ninja warriors). 3.1.1. The PositionType structure type represents one runner’s current position in the Vale of Doom as a row and a column. The Vale is organized as 2D grid of rows and columns, with the origin point (0,0) located in the top-left corner of the Vale. 3.1.2. The BehavType structure type represents one of the possible behaviours for a runner. Each behaviour structure is made up of the following: (a) the probability that this behaviour is selected for this runner, during one iteration of the chase (b) a function pointer to the corresponding behaviour function, using the BehavFuncType data type 3.1.3. The RunnerType structure type contains the information for a single runner in the Vale, including the following: (a) the runner’s avatar, which is the character used to represent this runner when the Vale is dis- played on the screen; Timmy Tortoise is depicted with avatar ’T’, Harold the Hare with ’H’, every dorc with ’d’, and each Ninja warrior with ’N’ (b) the runner’s moral character, as an enumerated data type; our heroes are good, and the villains are evil; the neutral option is included for completeness and future expansion (c) the runner’s life status, also as an enumerated data type; heroes are either alive or dead, and villains are always walking dead (d) the runner’s current position in the Vale (e) an array of the runner’s possible behaviours and their probabilities, as found in Table 1, and the number of behaviours in this array NOTE: The Grand Dragon, Lady Cordelia Cinderwing, PhD, is the literary creation of former COMP 2404 student J.Sinclair. ©2022 Christine Laurendeau COMP 2401 A :: Fall 2022 :: Assignment #5 1/6 https://en.wikipedia.org/wiki/Enumerated_type#C 3.1.4. The ChaseType structure type contains information related to the chase, including the following: (a) one runner (as a pointer) that represents Timmy Tortoise, and another one for Harold the Hare (b) an array of all the runners in the chase (also pointers), including both heroes (Timmy and Harold) and all the villains (dorcs and Ninja warriors) that are created during the program’s execution (c) the current number of runners in the runners array (d) a POSIX thread structure for the output manager, which is the function solely responsible for printing out the Vale of Doom to the screen, at predetermined time intervals (e) a mutex (binary semaphore) that’s used by the output manager thread to gain exclusive access to the chase information for the purpose of printing out the Vale of Doom to the screen 3.1.5. The randm(int max) function uses a pseudo-random number generator (PRNG) to generate a pseudo-random number between zero and max-1, inclusively. You must use this function every time that randomized behaviour is required. To ensure that every execution of the program produces a different outcome, the PRNG must gener- ate a unique sequence of pseudo-random numbers every time the program runs. For this to happen, you must initialize the PRNG by seeding it with the current time. This is done by executing the following statement once, at the beginning of your program: srand( (unsigned)time( NULL ) ); 3.1.6. You have been provided with some basic graphics functions to assist in printing the Vale of Doom to the screen, using the ncurses character-based graphics library: (a) the initNcurses() function must be called once at the beginning of the program to initialize the ncurses library (b) the cleanupNcurses() function must be called once at the end of the program to clean up the resources used by ncurses (c) the scrPrt() function outputs a string to the screen at a specific row and column 3.2. Design your program 3.2.1. You will be coming up with your own design for this program. It must be separated into short, single-purpose, modular, reusable functions that communicate with each other exclusively through parameters, as you have learned to do by implementing the previous assignments in this course. 3.2.2. Your program must contain at least different 20 functions, in addition to the ones provided in the base code. Most of your functions will be between 5 and 15 lines long (excluding whitespace and braces). No function should be more than 20-25 lines long, including the main() function. 3.2.3. All the data in this program, including the chase, all the runners, and all the behaviours, must be dynamically allocated. All dynamically allocated memory must be explicitly deallocated at the end of the program. 3.3. Organize the code Your submission must separate the program’s functions into multiple source files, as follows: 3.3.1. The main.c source file must contain only the main() and randm() functions. 3.3.2. The graphics.c source file must contain only the provided functions. 3.3.3. All the functions that you implement must be separated by functionality into at least three (3) addi- tional source files, not including the two files provided. 3.3.4. You must provide a correctly formatted Makefile that compiles every source file separately into a corresponding object file, and then links all the object files into an executable. 3.3.5. Because we are using two external libraries, your Makefile will need to link in the ncurses and pthread libraries during the linking stage, as we saw in section 4 of the course material. 3.4. Implement the overall rules of the chase 3.4.1. Overall chase: (a) The chase simulates the behaviour of multiple runners: our heroes are trying to make their way from the left-hand side of the Vale of Doom to the right-hand side, in order to escape the Vale with the Emerald in hand; Lady Cordelia’s minions (the villains) are trying to catch our heroes so that they can retrieve the treasure. The villains are clever enough to choose the direction of their movements so that they always move towards the hero that’s closest to them. ©2022 Christine Laurendeau COMP 2401 A :: Fall 2022 :: Assignment #5 2/6 https://en.wikipedia.org/wiki/Pseudorandom_number_generator (b) Your main() function must declare and dynamically allocate a single instance of a ChaseType structure. This chase structure is continuously updated with runners and their changing positions in the Vale of Doom throughout the execution of the program. (c) Your program must have an output manager function that executes as a thread separate from the main control flow for the entire duration of the program. The output manager is spawned at the beginning of the program, and it ends when the program terminates. This function and its helpers continuously rebuild and print to the screen a temporary 2D grid of all the runners in the chase, by showing their avatars in their current positions in the Vale of Doom. (d) The chase is implemented as a continuous game loop that executes until one of our heroes escapes the Vale by reaching its right-hand side, or both heroes die in the attempt. (e) At every iteration of the game loop, there is a 30% probability that a new dorc is created and launched into the chase, and a 5% chance that a new Ninja warrior joins the chase. New villains must be added to the chase’s runners array so that they are moved at every iteration. (f) At every iteration of the game loop, each runner in the chase is processed as follows: (i) if the runner is a dead hero, it remains in its current position, and the loop moves on to the next runner (ii) a new behaviour is randomly selected from among the runner’s behaviours array, in accor- dance with the probabilistic behaviours listed in Table 1 (iii) the runner is moved to a new position in the Vale in accordance with the new behaviour, by using a function pointer to call the corresponding behaviour function (iv) if the move results in a collision, because either a villain moves into a position occupied by a hero, or a hero moves into a position occupied by a villain, then the hero involved in the collision dies instantly; collisions between two villains or between the two heroes have no effect (v) if a hero dies, their avatar is changed to a cross ’+’ that represents their grave, and they stop moving across the Vale (g) once the game loop has concluded: (i) the output manager thread must be terminated with a call to pthread_cancel() (ii) the Vale of Doom must be printed to the screen one final time (iii) the outcome of the chase must be printed out, stating either which hero escaped the Vale with the Emerald, or that both heroes are dead (iv) the program must explicitly clean up all the dynamically allocated memory used, as well as the graphics library (unfortunately, it’s possible that ncurses may leave memory leaks) 3.4.2. Selection of runner behaviour: (a) The runners of the chase include our heroes, Timmy Tortoise and Harold the Hare, as well as an ever-growing group of randomly generated villains. (b) Each runner has a set of possible behaviours that represent how they move in the Vale. Each behaviour is associated with the probability that the behaviour is selected for that type of runner. (c) At every iteration of the game loop, a new behaviour is randomly chosen for each runner from among that runner’s behaviours array, with a specific probability, as shown in Table 1. Table 1: Runner behaviour probabilities Runner Behaviour Percentage Timmy Walk 70% Jump 25% Slide 5% Harold Walk 30% Jump 30% Slide 10% Sleep 30% Dorcs Walk 95% Jump 5% Ninjas Jump 60% Teleport 40% ©2022 Christine Laurendeau COMP 2401 A :: Fall 2022 :: Assignment #5 3/6 https://man7.org/linux/man-pages/man3/pthread_cancel.3.html 3.4.3. Characteristics of runner movements: (a) When walking or jumping, villains (dorcs and Ninjas warriors) have the ability to orient the direc- tion of their behaviour towards the hero (Tortoise or Hare) that is currently located closest to the villain. If the closest hero is dead, then the villain moves in the direction of the remaining hero. (b) Heroes are only interested in escaping the Vale, so they move in a straight line, in the same row. (c) All runner movements must be to valid positions in the Vale. If a newly generated row or column is invalid, it must be reset to the closest valid row or closest valid column. 3.4.4. Description of runner behaviours: (a) Walk: A hero walks by staying in the same row and moving one column to the right. A villain walks by moving one row and one column in the direction of the hero that is closest to them. (b) Jump: A hero jumps by staying in the same row and moving a random number of columns (be- tween 0 and 7 inclusively) to the right. A villain jumps by moving a random number of rows (between 0 and 7 inclusively) and a separately generated random number of columns (also be- tween 0 and 7) in the direction of the hero that is closest to them. (c) Slide: A runner slides backwards by staying in the same row and moving a random number of columns (between 0 and 4 inclusively) to the left. This represents the runner slipping backwards on the wet terrain of the Vale. (d) Sleep: When a runner sleeps, they stay in the same position. (e) Teleport: A runner teleports by moving to a random position in the vale. The random position is computed as a randomly generated valid row and a separate randomly generated valid column. 3.5. Implement the initialization functions 3.5.1. Your main() function must declare and dynamically allocate a single instance of a ChaseType struc- ture. The chase initialization code must initialize every field of this chase structure, and it must also do the following: (a) seed the PRNG, as indicated in instruction 3.1.5 (b) initialize the ncurses graphics library (c) allocate, initialize, and add to the runners array a runner that corresponds to Timmy Tortoise (d) allocate, initialize, and add to the runners array a runner that corresponds to Harold the Hare (e) initialize the mutex (f) spawn the output manager thread that is responsible for printing the Vale to the screen 3.5.2. The code that initializes each type of runner must initialize their behaviour arrays in accordance with the rules in Table 1. 3.5.3.