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 pursued 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.
- Learning Outcomes
With this assignment, you will:
- write a program that defifines 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.1. Understand the provided base code
The base code provided in the a5-posted.tar fifile 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 displayed 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
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 difffferent outcome, the PRNG must generate 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 specifific 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 difffferent 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 fifiles, as follows:
3.3.1. The main.c source fifile must contain only the main() and randm() functions.
3.3.2. The graphics.c source fifile 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) additional source fifiles, not including the two fifiles provided.
3.3.4. You must provide a correctly formatted Makefile that compiles every source fifile separately into a corresponding object fifile, and then links all the object fifiles 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.
(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 flflow 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 accordance 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 effffect
(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 fifinal 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 specifific probability, as shown in Table 1.