In this assignment you will simulate a zombie invasion not dissimilar to the Plants vs. Zombies video game. In this turnbased simulation, zombies of various types will emerge from the right most side of the map and move across the map until all the goals on the leftmost side are captured. Plants attack the zombies but can be attacked themselves. The program needs to be developed in C and the code submitted with a report, details of which are outlined below. An executable should also be submitted.
Please read the entirety of the assignment before attempting any part of it, as thinking about the overall solution from the start will be beneficial for some of the later stages.
Show your code for all parts, even if you do not get the final result. If you cannot provide code at least explain your reasoning around the problem and how you would solve it. Marks will be given for both code and explanations more marks will be allocated for proper code that works. If you cannot provide the full functionality at any stage, provide part of it but state what part was provided.
Structure your report in a manner similar to this document. If a section asks for code and a comment, use the same subheading and provide the items requested in that same subheading. When asked to output results you can use an application such as the snipping tool in Windows to directly paste the results in your document this is very quick. Windows 10 has a new screen capture facility using ShiftMSkeyS.
Provide comments in the code the more readable it is the easier it is to understand and allocate marks. Please include Visual Studio solutions and all the source code. If you wish to use another compiler and IDE you are permitted but please contact module tutor before you do so such that arrangements for marking are made in a timely fashion.
Make sure you do not copy any code from the internet or online resources or from any other students.
You must write all the code yourself including data structures. Use of Standard Template Library is not permitted. However, you are allowed to use code we developed in class including the tutor provided solution. For example, the class location used in class can be used.
This PMA will help you reenforce the learning from the module. While it may seem like a game in nature, it is mostly a simulation solutions to programming and algorithmic issues are required to get it to work properly. In particular, it will help you think about solutions to problems that you will not have seen before were you can use solutions from literature or of your own devising. Furthermore, it helps you build a simulation in which you can test hypotheses. Such aspects are crucially important for working in scientific and engineering disciplines.
Overview
This section provides a broad overview of what the basic functionality of the system is meant to achieve. Further details will be given in forthcoming sections.
The simulation consists of an YxX grid in which the characters zombies and plants exist and some are allowed to roam. Figure 1 shows two consecutive steps of the simulation for a grid size of 12×6 Y refers to number of rows and is always presented first, X refers to number of columns. Henceforth we refer to the size as YxX, such that Figure 1 is considered a map of size 12×6.
There are different types of characters, three types of Zombies, Z, Y and R with different behaviours and a Plant P. There are four types of terrain, an empty terrain as a blank space , blocked terrain and a goal. Any of the zombie types will attempt to reach one of the goals termed G which is converted into an O once it is reached by any of the zombies. See Figure 1.
The simulation is turn based. At each step in the simulation some of the characters move around the grid in the cells north, south, east and west of the current location. The zombies roam around the environment using a random walk for Z any Y different probabilities for directions explained in the below. The runners are more directed and will be directed towards the closest plant or goal. If a zombie of any type Z, Y, R hits a P the P disappears. The zombies always start at the rightmost side of the map. The goals G and when captured O are present on the leftmost column of the map. If a zombie of any type hits a G this turns into an O. The simulation terminates once all the Gs have become Os. The zombies of any type are not allowed to step onto the . Zombies and plants spawn depending on probabilities outlined as part of the simulation. The plants shoot all zombies in all the squares around them including the diagonals and this happens once every K turns, where K is a parameter that will be set in the code. Various conditions for termination will be outlined below.
The simulation should also provide the facility to save and load a scenario.
A simulation run will be shown in the class to give you an idea of what to expect.
The simulation will be built in various stages. These are outlined below along with the marks for each stage successfully completed.
1.1 Marking Scheme
The following must be provided and is outlined in individual sections numbers correspond to sections, details of each one is explained in the individual section:
Basic functionality 12 marks
Adding the characters 13 marks
Simulation 18 marks
Advanced Simulation 17 marks
File IO 10 marks
Adding the runner 20 marks
A report outlining all of the above 10 marks
1.2 Uploads
Please submit the report in pdf or docx format. The sections need to follow the same format described in this document. That is:
1. Introduction
Basic functionality
Adding the characters
Simulation
Advanced Simulation
File IO
Adding the runner
Limitations
How you would approach the project differently if you had to restart now
Also please make sure that you provide a zip file containing the entire project ie the Visual Studio solution.
Figure 1: A 6×12 grid with two Ps, five Zs, one Y. One of the Goals G has already been captured. The stats at the bottom denote number of turns passed, number of zombies terminated and number of plants terminated.
Basic Functionality 12 marks
The initial functionality will involve the creation of the basic map as shown in Figure 1. This functionality should be encapsulated into a map class. The size of the map is variable and is given by a set of parameters on construction.
The map is used for display purposes only and should contain integer values for the objects on the map. For the , empty space , G and O these will be fixed values for example 0, 1, 2, 3 but for the characters these need to be unique identifiers per character using enums for this is recommended.
i Provide functionality for creating the map via the constructor. The constructor is only required to take as input the Y and X lengths other data may be passed but this depends on your design. At this stage the whole map should be empty. The minimum Y is 1 and the minimum X is set to 4 reasons for this will become apparent later. A destructor member function should also be provided.
ii Provide functionality for placing a value at a map cell using a member function map::place. The functionality for this member function should include bounds checking to ensure the place is on the map and also functionality for ensuring no two characters or terrain are placed on a single grid cell. Show code that shows that this functionality works. Also provide functionality for returning the value on the map map::getXY which also checks for boundaries and returns an error code if the request goes beyond the boundaries.
iii Provide functionality for displaying the map via map::display. Show the output from map::display in the report, for now for an empty grid. See Figure 2.
iv Place goals across the length of the first column, see Figure 3. Furthermore, show code for placing 15 blocks randomly this should be independent of the class on the map on a grid of size 6×12. See Figure 4. Make sure that a total of 15 separate blocks are generated. Blocks cannot be placed on either the first two columns or the last column this makes it so that Goals only belong on the first column, the last, rightmost, column is for zombies; it also makes the impassability test from Section 4 easier to solve. Show code for testing edge cases, for example for boundary errors and for trying to place two objects on the same place.
At this stage you can show the grid, the goals G, the blocks . See Figure 2 bottom.
v Finally, show maps for sizes of 1×4 smallest possible, 5×10 and 15×30. The number of blocks placed on these maps should be equal to the length of Y i.e. one for size 1×4, 5 s for 5×10 etc. Do not worry whether there is a path from right to left at this stage. Note: to capture wide maps make sure the terminal is resized before you display. You can do this easily by asking for player to input size and resizing the terminal using a mouse before you display the map.
Figure 2: map::display for 6×12 map before adding any characters
Figure 3: map::display after setting goals on first column
Figure 4: map::display after adding goals and 15 random blocks. When placing blocks care must be taken to not put them on a place occupied by another block and not in the first two or last column. This functionality should appear inside map::place
Adding the characters 13 marks
At this stage the student is at the liberty of constructing their own classes. However, it is recommended that classes are used for the character types, and a simulation class see next section. Furthermore, a class that is used as container to store all the characters would be useful.
The next part will involve adding the characters onto the map. It will require the inclusion and data management of the zombie Z and zombie 2 Y, plant P and eventually runner R characters. For this part of the assignment, the R can be ignored. Z and Y are required to move randomly using a random walk whereby at each turn Z and Y can move north, south, east or west on the grid. Z and Y cannot move beyond map boundaries, or onto . If they try to move into one of the other places and they are not successful they remain still for the turn. For now, P, G and O will be treated as but this behaviour will be changed in the next stage. The difference between Z and Y is in the probability of their movement. Z will move to the left twice as frequently as any other direction. Y will move to the left four times as frequently as any other direction.
The management of the characters is left at the developers discretion but as mentioned above it is suggested that they are maintained in a container class.
i For this part of the assignment, show how the classes that represent characters are developed. You should explain the reasoning behind your choices. Show functions for movement of the characters and any other functionality you deem fit. Clearly show the move function for both Z and Y. As described above: The difference between Z and Y is in the probability of their movement. Z will move to the left twice as frequently as any other direction. Y will move to the left four times as frequently as any other direction.
ii Show code that populates a map with three Zs and three Ys, for a map of size 6×12 with 12 blocks inserted and the Gs. The Z, Ys and s should be inserted randomly, such that different runs would result in different configurations. Note it is important that the Zs and Ys start at the rightmost column. If the rightmost column is occupied no Z is started at that given turn. Ensure the exact sizes requested are present. See Figure 5.
Figure 5: Adding Zs and Ys to a map of size 6×12.
iii Write code to move all characters three times. Show the results of four consecutive steps first step and three movements. If a zombie cannot move that turn for example it chose a direction occupied by another zombie or a it skips that turn. Be careful how characters are managed. Note significant functionality must be added for this to work including communicating and updating the map class. Please show all of this functionality. See Figure 6 for an example. Show a counter with every frame. Please see Figure 6 for an example of how the counter is used. In the case of Figure 6 the frames start at step 46 and go to 49 as shown by the counter. You can capture any consecutive sequence of steps from your work that you deem suitable.
iv Explain your overall choice of classes and how you would expect them to interact.
Figure 6: Output of three steps for Z and Y movement. Note: the step count in the bottom left starting at 46 on to 49. Students please provide and display your own counter also. Further note: the presented images are creating new Zs and Ys, the student is not required to do this yet. As long as 3 are moving that is fine.
Simulation 18 marks
This part runs the simulation. It is suggested that a simulation class is now added as it will make working with this section, and Section 5 easier. Z and Y behaviour will remain the same except that Zs and Ys can now interact with G and P. If a Z hits a G it becomes an O. Once all the Gs are converted into Os the simulation terminates.
Note: that this section is quite complex as compared to the previous so read it all in detail and every question carefully before answering.
i Provide code for managing when a Z or Y hits a G and converts it into an O. The Z or Y are terminated when this occurs.
ii Provide code that runs the simulation one step at a time, moving to the next step using any key press, until the user quits by pressing q. Use this to show an example of a Z capturing a G. Highlight this in red in your report highlighting should be done in the report not in the code. Figure 7 shows an example of this note you can clear the screen while it is running after every step using systemcls as shown in class I show it repeated here for visualisation purposes.
Figure 7: Consecutive steps until q is pressed. Two captures at consecutive steps in red showing the Z capture the G and convert it into an O. Z is terminated.
iii The plants P will now be added. Ps do not move. They are added randomly to the first half of the map first half of any row. For example, for a map of size 6×12, the Ps can be added to any column after 1 the first column is reserved for goals, and before 6 included, and at any row 1 to 6 Note: be careful with numbering remember CC arrays begin at 0 not 1 the above example was not starting from 0. When a Z or Y hits a plant the plant P is terminated. Every K steps the plant terminates any Zs and Ys around it including in the diagonal directions. Provide all the above functionality set K equal to 4 for now. Show diagrams of a Z or Y terminating a P see Figure 8 for an example and of a P terminating a Z or Y.
Figure 8: Shows how a Z terminates a P.
iv The simulation will now be run until all Gs become Os or 10,000 steps are reached there are situations when the terrain is impassable this will be fixed next andor the Ps dominate the simulation see Figure 9 for P domination. For this simulation create a new P with a probability PP of 2, a new Y with a probability PY of 5 and a new Z with a probability PZ of 10 each turn. When a P, Z or Y cannot be generated for that turn because for example the final row is full, the generation is ignored. Provide code for the random generation of P, Z and Ys at those probabilities and a method for testing when the simulation is meant to finish. Show an image of a map that has reached final state see Figure 10 for an example. For the example, set map size to 6×12, PP 2, PZ 10, PY 5 and K4. Also store and display the number of terminated zombies and plants as shown in Figure 8.
Figure 9: The Ps have established a strong defensive position and with the layout of the map it is likely they may be able to hold this for 10,000 steps.
Figure 10: Terminating condition for map.
v Provide code to test whether there is a path from the left to the right of the map. That is, it ensures that the zombies can make it across. As mentioned earlier, to make this easier, blocks cannot be placed in the first two columns and in the last column. An example of an impassable map can be seen in Figure 11 top and middle. Show code for attempting to create a passable map for a map size of 6×12 with 25 blocks. Show all the output maps until a passable one is achieved see Figure 11 for an example.
Note: if a solution for this cannot be provided in code try and explain a possible solution in text.
Figure 11: Two examples of generated maps which are impassable and one which is passable bottom. A potential path in bottom map shown in red.
Advanced Simulation 17 marks
This simulation will identify whether it is better for the plants to increase the frequency of their shooting K or their probability of spawning PP. In order to do so various simulations will be run with the following settings of K and PP:
K
PP
1
0.01
2
0.02
3
0.03
4
0.04
5
0.05
6
0.06
7
0.07
8
0.08
9
0.09
i Using the configurations above, run the simulation for a map size of 6×12 using 10 blocks. Identify how many times the Plants are successful for each one. Success is indicated when the Plants hold out for 10000 turns. In order to produce reasonably good results, make sure each simulation for every setting is run 500 times. The settings for zombie spawning should be set to PZ 10 and PY 5. Important Note: Please make sure you do not display the simulation when running in effect switch off any output to the screen as this will slow down things considerably. Also make sure you compile in release mode. On my PC i76700k using single threaded execution one setting takes a few seconds to run 500 simulations. Finally, be careful with memory management as this task can consume a lot of memory if you are not freeing it up correctly make sure your destructors are in place and functioning properly. Show simulation code and the number of successful attempts out of 500 for each of the pairs of settings.
ii This part tests what happens when the number of blocks changes. For the following settings:
K
PP
1
0.01
2
0.02
3
0.03
4
0.04
test how the results change as the number of blocks change from 0 to 20. Identify for each of the simulations with different blocks which pair produces the highest number of successes over the 500 runs. Map size remains fixed to 6×12, PY 5, PZ 1.
iii Finally, test whether map sizes have an effect by running ii for map sizes of 6×18 and 12×12 and produce the same results as in ii for these map sizes.
File IO 10 marks
This section will provide the capability of saving and outputting a single simulation run. The information will take the shape of the map and be stored in ASCII. This will provide the ability of creating custom scenarios by editing them inside a text editor and then load them into the simulation.
The format required is each of the first two lines containing the Y and X lengths of the map. Then the map itself with empty spaces represented as , blocks as , Goal G, captured goal O, zombies Z and Y and plants P. Runners are not required for now and will be introduced in the last section. Also store the statistics of turn number, and zombies and plants terminated. A format to be used is suggested in the following example:
6
12
OZ
OZ
OZZ
G
GP
GP
213
15
0
The first row contains the Y size of the map. The subsequent row the X size. The following the state of the map. After that the final three lines contain the turn, terminated zombies and plants respectively.
i For this task, show code for saving and loading. Show code for an example of saving and loading. Also add a check to see if the loaded map is impassable. If it is impassable give an error response and then exit the application Note: you do not need to check the first two and last column, if the user made a mistake there it can be discarded.
ii Load in a file containing the above sample file to produce the display and run it for a step or two as shown in Figure 12.
Figure 12: Displaying the next step in the loaded file.
iii The Ps contain information the counter K which stores when they are meant to shoot next. Capture this information in your file format and reload it.
Adding the Runner 20 marks
This section will now add runner zombie character R. Rs find the shortest distance to the closest of the Gs and Ps and at every step move into that direction. Initially the R will consider all the other zombies and objects as obstacles to be avoided Zs, Ys, Rs, Os and s. Note: there will be occasions when an R cannot move closer to a target in any way possible so does not need to move that turn. Also note that due to the dynamic nature of the simulation other Rs, Zs and Ys moving around the best route may change each turn and may indeed become blocked.
i Think about which algorithm to best use for this. Describe which algorithm it is and why it was chosen.
ii Describe how you modify the data from the simulation, and in particular the map, in order to use this algorithm.
iii Think about how often the algorithm needs to be run and explain why.
iv Show code for the modified R move function and any additional functionality you have produced.
v Import the following file and visualise distance to all the cells on the map as shown in Figure 13 1 symbolises unreachable:
6
12
ORZ
O
OPZZ
GR
G
G
213
15
0
Note: if you had not yet added the File IO due to issues with implementation feel free to construct the scenario directly in the code.
vi If you were to take into account the Ps such that the Rs would avoid Ps in order to get to the Gs alone, how would you go about it? Textual description required for this only no code or implementation is being asked for here
Report 10 marks
The report should contain all the details and code as requested in the rest of the document. As mentioned above, structure your report similarly to this document, whereby if a section asks for code and a comment, use the same subheading and provide the items requested in that same sub heading. When asked to output results you can use an application such as the snipping tool in Windows and paste the results in your document this is very quick.
Add a section on limitations if some of the things you tried did not work or there are bugs that you know about but could not fix.
Also add to the report a small section on how you would have approached this project differently if you had to start from scratch after this learning experience.
Do not add the code to the appendix but provide it separately and in a format where it can be compiled directly see Section 1. Important all samples of code shown in the text need to be in text format not a screen capture from your editor.
Figure 13: Visualising distance from any of the targets for the Runners in the above map. 1 denotes unreachable including Zs, Ys, Rs, s and Os. In this case the top R and some of the Zs may have already moved before the second the Rs run.
Complete your assignment from here heading styles have been set up to assist you in this work Delete the instructions before you save and submit your work:
MODULE TITLE
Table of Contents
1 Heading 1 Suggested that you use this for each Question answered 1
1.1 Heading 2 suggested that you use this for each subheading in each question answered 1
1.1.1 Heading 3 you may use this heading as appropriate 1
Enter a page break here and between each question
Heading 1 Suggested that you use this for each Question answered
Heading 2 suggested that you use this for each subheading in each question answered
Heading 3 you may use this heading as appropriate