COMP 2401 B/C – Final Project

COMP 2401 B/C – Final Project
The Tortoise Chronicles: Pirate Wars
Note: You don’t have to read the backstory to do the work. This part is just for fun.
King Aesop has a serious problem. His peaceful kingdom’s coastal villages are under constant threat of attack
and pillage from the Dread Pirate Neville and his band of marauders, and the population has had enough.
Thus the King has decided to send two of his best champions to fight the Dread Pirate Neville and his crew,
and to rid the peaceful kingdom of this merciless scourge. Luckily, our intrepid heroes Timmy Tortoise and
handsome Prince Harold the Hare have decided to volunteer for this perilous mission.
The King has decreed that this epic battle will take place at dawn, three days hence, on the Dread Pirate
Neville’s ship. To assist our heroes, King Aesop has offered to lend them the legendary magical sword
Grayswandir. Timmy and Harold have devised a strategy for fighting the pirate crew in hand-to-hand combat.
They will trap the pirate gang below deck and approach them, each from a different direction, forcing the
pirates to organize themselves in a double-ended queue (also known as a deque). With one hero at each end
of the deque, each of them only has to fight one enemy at a time. For example, Timmy can take on the pirate
currently at the front of the deque, while at the same time, Harold fights the one currently at the back. Once
an enemy is slain, the hero can engage with the next pirate in line. The battle continues until either all the
pirates have been defeated, or both heroes have perished in the attempt.
Each hero wears a bit of defensive armour, but they only have the one Grayswandir sword to share between
them. As part of devising the best combat strategy, our heroes need to know whether it would be more
advantageous for Timmy or Harold to wield Grayswandir. This is where they need your help.
Timmy Tortoise is an ace C programmer in his own right, but he needs your help in coding a simulation of this
epic battle. In computing their survival rates over multiple executions of this simulation, you can help our
heroes decide which of them should use the sword in the real-life battle, to ensure the best chance of success.
By making this implementation multi-threaded, you can ensure that Timmy and Harold get the simulation
results quickly, giving them lots of time to prepare for this epic battle.
1. Introduction
1.1. Goal
For this project, you will write a program in C, in the VM’s Linux environment, to simulate multiple randomized executions (or runs) of a battle between our two heroes and the pirate crew. Each run will
simulate multiple scenarios, based on which hero (or neither) wields the sword.
Your program will be multi-threaded, to enable the execution of parallel, simultaneous scenarios and
fights between heroes and pirates. At the end of the simulation, it will print the percentage distribution
of successful, partly successful, and failed runs for each scenario, over all the runs of the simulation.
1.2. Learning Outcomes
With this project, you will:
• write a program in C that is multi-threaded, and that is correctly designed for this purpose
• use dynamically allocated memory to store all data, and implement a deque as a singly linked list
1.3. Required background
To begin this project, you must understand the following concepts from the course material:
• section 2.3: command line arguments
• sections 3.2 and 3.3: dynamically allocated memory, linked lists, arrays of pointers
• section 5.4: multi-threaded programming, semaphores and mutexes
If you are not familiar with this material, you must review it before you can start this project.
©2021 Christine Laurendeau COMP 2401 B/C :: Fall 2021 :: Final Project 1/7
2. Data and Control Flow
This section describes the data structures that your program functions will use to communicate with each
other, as well as the overall threaded control flow of this program.
2.1. Definitions
This document uses the following terminology throughout the project requirements:
2.1.1. Simulation: A simulation is a virtual execution of a “real-life” event. In this document, the entire
program is the simulation.
2.1.2. Run: The goal of our simulation is to gather statistics on hero survival rates over a large number of
separate, randomized executions. Each execution is called a run, and it simulates a battle between
our heroes (the Tortoise and the Hare) and a group of pirates with randomly generated properties.
Each run is different, because of the randomized pirate properties, and each run simulates the battle
under three different scenarios, as described below. By default, our program executes 100 runs.
2.1.3. Scenario: Within one single run, our heroes fight against the same group of pirates under three separate fighting conditions, called scenarios. In scenario #1, the Tortoise wields a sword that provides
extra strength; in scenario #2, the Hare wields the sword; and in scenario #3, neither hero wields
the sword.
Each scenario in a single run results in one of three possible outcomes, as described below. The
program accumulates statistics on how many times each scenario results in a specific outcome.
2.1.4. Fight: Each scenario has our two heroes, the Tortoise and the Hare, fighting a group of pirates that
are stored in a double-ended queue (a deque). A fight has one hero fighting the pirates at one end
of the deque, one pirate at a time.
Each scenario has two fights taking place simultaneously, with the Tortoise fighting the pirate at the
front of the deque, and the Hare doing the same at the back of the deque. A fight continues until
either all the pirates in the deque are defeated, or the hero dies.
2.1.5. Scenario outcome: Each battle scenario between our two heroes and one group of pirates ends in
one of three ways: success is achieved if all the pirates die and both heroes survive; partial success
is achieved if all the pirates die but only one hero survives; and failure is achieved if both heroes die
before all the pirates can be defeated.
2.2. Data flow
The provided defs.h file contains all the structure data types that your simulation must use:
2.2.1. The StatsType structure type contains the statistics for one scenario, accumulated over all the runs
of the simulation. Its fields store the number of times that the scenario ends with a specific outcome:
success, failure, or partial success, as described in instruction 2.1.5.
2.2.2. The FighterType structure type stores the information for one fighter. This could be a Tortoise, or a
Hare, or one of the pirates. Each fighter has numeric indicators for strength, armour, and health.
2.2.3. The DequeType and NodeType structure types together define a double-ended queue (also known
as a deque) that contains the group of pirates that our heroes are fighting during one scenario, in
one run of the simulation. The deque is a singly linked list that contains both a head and a tail, since
the Tortoise and the Hare each need to fight the pirates at one end of the deque.
2.2.4. The RunSpecsType structure type stores the information required for one scenario, during one run of
the simulation. This information needs to be communicated with each control flow thread associated
with a scenario, as described in a later step.
This structure contains the following fields:
(a) a copy of the deque of pirates that our heroes are fighting, in this scenario
(b) the Tortoise that fights at one end of the pirate deque, in this scenario
(c) the Hare that fights at the other end of the pirate deque, in this scenario
(d) the StatsType structure for this scenario, for all runs of the simulation; this structure is updated
once the two heroes are done fighting the pirates in the deque, and the scenario outcome is
determined
©2021 Christine Laurendeau COMP 2401 B/C :: Fall 2021 :: Final Project 2/7
2.2.5. The FightSpecsType structure type stores the information required by one fight, as part of one
scenario, during one run of the simulation. This information needs to be communicated with each
control flow thread associated with a fight, as described in a later step.
This structure contains the following fields:
(a) the hero who is fighting at one end of the pirates deque
(b) the deque that contains the pirates; a pirate is removed from the deque when it fights a hero
(c) the direction in which the hero is fighting the pirates; the FRONT value indicates that the hero
fights the pirate at the front of the deque, and the BACK value indicates that the hero fights the
pirate at the back
(d) a mutex semaphore that ensures that the deque is only accessed and modified by one fight
thread at a time; since both heroes are fighting the pirates in the same deque concurrently (at
the exact same time), it’s important that each pirate is removed from the deque only once
Figure 1: Control flow for a single run
2.3. Control flow
This section describes the program control flow in general terms only. The detailed control flow requirements are described in section 4 of this document.
2.3.1. The overall control flow for the simulation executes a number of runs. Every run goes through the
same steps, but the outcome is always different because every pirate is created with randomly
generated properties.
Each run spawns (i.e. creates) a total of nine separate threads, not including the main control flow,
as shown in Figure 1:
(a) three scenario threads, with one scenario thread created for each of the three scenarios described
in instruction 2.1.3
(b) two fight threads for each scenario thread, for a total of six fight threads; each scenario thread
creates one fight thread for each of our two heroes (the Tortoise and the Hare), where they both
fight the same deque of pirates
©2021 Christine Laurendeau COMP 2401 B/C :: Fall 2021 :: Final Project 3/7
2.3.2. The control flow for each run must be threaded, and its general steps are the following:
(a) Initialize the run and the run specifications for all three scenarios.
(b) Spawn three scenario threads, one for each scenario, and wait for all three threads to terminate.
(c) Clean up the data after the run.
2.3.3. The control flow for each scenario is also threaded, and it involves one Tortoise and one Hare fighting
the same deque of pirates, with each fight taking place in its own fight thread. Each scenario thread
must include the following steps:
(a) Initialize the fight specifications for each hero.
(b) Spawn two separate fight threads, one for each hero, and wait for both threads to terminate.
(c) Compute the scenario outcome: success, failure, or partial success, as described in 2.1.5.
(d) Update the statistics for the current scenario and its outcome, and clean up after the scenario.
3. Design Requirements
Your design must meet all of the following requirements:
3.1. Function design
3.1.1. Your program must be separated into 15-25 modular, reusable functions that could be used in an
extended version of this program, or potentially in other programs.
3.1.2. Your functions must be single-purpose and reusable, and they must have a clear interface, with
parameters that are identified as either input, output, or input-output parameters.
3.1.3. Your functions must include, at minimum, the following:
(a) individual functions for initializing each type of dynamically allocated data (fighters, run specifications, and fight specifications)
(b) functions for cleaning up dynamically allocated data once it’s no longer required
(c) functions for manipulating the deque, including initialization, adding an element to the deque,
removing an element from the front the deque, removing an element from the back, performing
a deep copy of a deque, checking if a deque is empty, and cleaning up a deque once it is no
longer required
(d) one function that executes a scenario thread, and one function that executes a fight thread
(e) one function that computes the scenario outcome
(f) functions for initializing, updating, and printing statistics
3.1.4. Every function must be documented, along with each of its parameters and the return value, as
covered in the course material.
3.2. Data design
3.2.1. Your program must allocate, populate, and extensively use all the structure data types that are
provided in the base code. No additional structure data types are permitted, and no modifications
to the provided data types are allowed. You must use predefined constants everywhere possible.
3.2.2. All fighter and specification data in this program must be dynamically allocated. All dynamically
allocated memory must be explicitly deallocated when no longer in use.
3.2.3. Arrays may be used for collections of data, except for pirates, which must be stored in the provided
deque collection. The collections may be statically allocated, but they must store pointers to data.
3.2.4. All fighter data must be allocated and initialized at the beginning of each separate run, and deallocated at the end of the run. Pirate data and hero data must not be reused between different runs or
different scenarios. Data and collections must not be copied, unless permitted in the instructions.
3.2.5. Statistics data may be statically allocated, but must not be copied in any part of the program. There
must be one statistics structure for each type of scenario, for the lifetime of the program, and the
corresponding structure must be updated at the end of every scenario, in every run. Your program
must use pointers to statistics data in each function that needs to update it.
3.2.6. Do not use any global or static storage class variables anywhere in this program. Functions must
communicate with each other exclusively through parameters.
©2021 Christine Laurendeau COMP 2401 B/C :: Fall 2021 :: Final Project 4/7
3.3. Control design
3.3.1. Your program must be generalized for any number of scenarios, as declared in a constant in the
given header file. Everywhere that scenario data is required, you must declare a collection of this
data and process it in a loop. DO NOT use three fixed variables where scenario data is required.
3.3.2. The program must be multi-threaded, and not multi-process. This means that you must use the
pthread library to spawn all the different threads, as we did in the course material, section 5.4.
4. Program Requirements
Your program must not use any library functions or techniques not covered in this course, unless permitted in
the instructions. In addition, your implementation must meet all of the following requirements:
4.1. Implementation of the overall control flow
The overall control flow for the simulation does the following:
4.1.1. Determine the number of runs that the end user wants to execute. This is specified using a command
line argument, as we saw in the course material, section 2.3.7. If the user indicates no command
line argument, then a default number of runs are executed, with the default number defined as a
constant in the given header file.
4.1.2. Initialize the simulation, as follows:
(a) you must seed the pseudo-random number generator with the current time, so that every execution is different; this is done with the statement: srand( (unsigned)time( NULL ) );
(b) initialize the statistics for all scenarios
4.1.3. Execute the required number of runs, and accumulate the statistics for each scenario and outcome
throughout all the runs.
4.1.4. Print to the screen the scenario and outcome statistics, as the percentage distribution of successful,
partly successful, and failed runs for each scenario, over all the runs of the simulation (see the
sample execution in the introduction video to see what’s expected here).
4.2. Implementation of the control flow for one run
Each run executes the same steps, but the outcomes are always different due to the randomized nature
of some of the pirate properties. Every run does the following:
4.2.1. Initialize the run. This must include the following steps:
(a) initialize one deque for each scenario
(b) create and initialize 10 pirates, and place them in the first deque only
(i) each pirate has a randomly generated number of strength points, between 5 and 9 inclusively
(ii) each pirate has a randomly generated number of armour points, between 1 and 4 inclusively
(iii) each pirate begins with 10 health points
(c) make a deep copy of this first deque into every other deque that you initialized; this populates
one deque for each scenario of this run, with each deque containing copies of all the same pirates
(d) initialize one Tortoise fighter and one Hare fighter for each scenario:
(i) each Tortoise has a strength of 5 points and armour of 8 points
(ii) each Hare has a strength of 8 points and armour of 5 points
(iii) each hero begins with 20 health points
(iv) the sword’s strength indicator of 2 points is added to the strength of the hero wielding it
4.2.2. Initialize the run specifications for each scenario. This involves initializing a collection of
RunSpecsType structures, using data that was already generated in instruction 4.2.1.
NOTE: The pirates deque, the Tortoise, and the Hare are all separate for each scenario. The statistics
structure is also different for each scenario, but this data is stored at the simulation level, since it
must be updated throughout all the runs of the simulation.
4.2.3. Spawn one scenario thread for each scenario, with the correct RunSpecsType structure as parameter.
Wait for all three scenario threads to terminate.
4.2.4. Clean up the memory for the run.
©2021 Christine Laurendeau COMP 2401 B/C :: Fall 2021 :: Final Project 5/7
4.3. Implementation of the control flow for one scenario
Each scenario thread that is spawned during a run involves one Tortoise and one Hare fighting the same
deque of pirates, each in its own fight thread.
The Tortoise and Hare are positioned at each end of the deque (the Tortoise at the front, and the Hare at
the back). As long as the deque is not empty of pirates, a pirate is removed from the end of the deque
where the hero is fighting, and the hero fights that pirate until one of them wins. Because the same
deque is shared between two fight threads, the deque must be protected by a mutex during the removal
of each pirate.
Each scenario thread must perform the following steps:
4.3.1. Initialize the fight specifications for each hero. This involves initializing the fields of two separate
FightSpecsType structures.
One fight specification structure contains the Tortoise hero, the deque found in the RunSpecsType
structure passed in as parameter, the FRONT direction, and an initialized deque mutex. The other
fight specification structure contains the Hare hero, the same deque of pirates, the BACK direction,
and the same deque mutex.
NOTE: It is important that both fight specifications for a scenario share the same deque of pirates
and the same deque mutex. This is necessary to make sure that the heroes are not fighting the same
pirate as each other. (Hint: pointers are your friends here)
4.3.2. Spawn two separate fight threads, one for each hero, with the correct FightSpecsType structure as
parameter. The fight rules are described in a later step. Wait for both fight threads to terminate.
4.3.3. Compute the scenario outcome: success, failure, or partial success, as described in instruction 2.1.5.
4.3.4. Update the statistics for the current scenario and the computed scenario outcome.
4.3.5. Clean up the memory for the scenario.
4.4. Implementation of the fight rules
Each fight thread continues as long as the hero is still alive and there is at least one pirate remaining in
the deque. As long as this is the case, the program does the following:
4.4.1. remove the next pirate from the pirates deque, at the end where the hero is positioned
4.4.2. simulate a fight between the hero and the removed pirate, in accordance with the fight rules described below, until one of the two participants dies
NOTE: Sometimes, in threaded programs, it is necessary to slow down the processing to make sure
that each thread gets a fair share of the processing time. If your simulation results are greatly different
between executing inside of valgrind and outside of it, try adding a short sleep cycle after each heropirate fight, for example with a call to usleep(1000), which pauses processing for 1000 micro-seconds.
The fight rules are as follows, and they continue until one of the participants dies:
4.4.3. the hero hits the pirate
(a) the amount of damage caused by the hero is computed as the hero’s strength, minus the pirate’s
armour; damage must never be less than zero
(b) the pirate’s health indicator is decreased by the amount of damage caused; health indicators
must never be less than zero
(c) if the pirate’s health indicator reaches zero, he dies
(d) if the pirate dies, the hero’s health indicator gets a boost of 3 points (hero health must never
exceed 20 points), and the fight is over; if the pirate is still alive, the fight continues
4.4.4. the pirate hits the hero
(a) pirates love to fight, and it gives them great energy; the pirate’s strength is temporarily increased
by a randomly generated amount between 0 and their regular strength minus 2, inclusively
(b) the amount of damage caused by the pirate is computed as the pirate’s temporary strength,
minus the hero’s armour; damage must never be less than zero
(c) the hero’s health indicator is decreased by the amount of damage caused; health indicators must
never be less than zero
(d) if the hero’s health indicator reaches zero, he dies
(e) if the hero dies, the fight is over; if the hero is still alive, the fight continues
©2021 Christine Laurendeau COMP 2401 B/C :: Fall 2021 :: Final Project 6/7
4.5. Packaging
4.5.1. Your program must be separated into at least four (4) source files, including the main.c file. Each
source file must contain functions that are functionally related to each other.
4.5.2. You must provide a Makefile that separates the compiling and linking of the code, and produces the
program executable. Your Makefile must also include the clean target that removes all the object
files and the program executable.
4.5.3. You must provide a README file that includes:
(a) a preamble (program author, purpose, list of source, header, and data files, if applicable)
(b) compilation and launching instructions, including any command line arguments
4.5.4. All your files, including your executable, must be given names that make sense for this project.
4.5.5. Do not include any additional files or directories in your submission.
5. Submission Requirements
5.1. You will submit in Brightspace, before the due date and time, one tar or zip file that includes all your
program files, as described in instruction 4.5.
5.2. Late submissions will be subject to the late penalty described in the course outline. No exceptions will
be made, including for technical and/or connectivity issues. Do not wait until the last day to submit.
5.3. Only files uploaded into Brightspace will be graded. Submissions that contain incorrect, corrupt, or missing files will receive a grade of zero. Corrections to submissions will not be accepted after the due date
and time, for any reason.
6. Grading Criteria
• 10 marks: correct design and implementation of the overall simulation
• 25 marks: correct design and implementation of runs
• 26 marks: correct design and implementation of scenarios
• 21 marks: correct design and implementation of fights
• 4 marks: correct packaging
• 4 marks: correct documentation
• 10 marks: correct program execution
©2021 Christine Laurendeau COMP 2401 B/C :: Fall 2021 :: Final Project 7/7

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply