Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS3413 Fall 2022 Assignment 2

Due: Friday, Nov 04th, 11:59PM

Notes and Style

•    must be written in C. No C++

•   The prof has provided a working demo in D2l (a2demo executable <- change permissions when copied to your FCS machine with chmod u+x <file>)

•    your assignment code must be handed in electronically using the D2L drop box. Try early and re-submit later.

•    Include a Makefile. If “make” doesn’t compile and produce an executable, your assignment will not be marked

•   You make file should also include a make run” and make clean” command that runs your executable and removes all files resulting from compilation

•   Your program must run. Programs that do not run, or segfault before working at all, will lost 50%. Save early and often, and use version control. Submit often,    only submit working versions.

•   Your program must compile with Wall, with no warnings showing. You will lose marks for warnings and lose marks for not compiling with -Wall in your makefile

•    Include a “listing” file, a single .txt file with all your source files concatenated into it. Good header text in EACH file is imperative here. E.g. cat *.h *.c | listing.txt

•    Use  common-sense  commenting  and  good  style,  practices.  Provide  function headers, comment regions, etc. No particular format or style is required but bad programming  practices  will  result  in  marks  docked  (e.g.,  huge  complicated functions, unreadable code, magic numbers, bad variable names, etc).

•    Error checking is extremely important in real world OS work, and you must do it    rigorously. Error handing, however, is hard in C. Try to handle gracefully when you can, but for hard errors (out of memory, etc.), hard fail (exit) is OK.

•   Test on FCS computers with their version of gcc, make sure your Makefile uses the one you tested.

•   Your assignment will be tested on FCS computers.

Attack of the Poisonous Fredericton Caterpillars

You will make a text version of the classic video game centipede.” However, when researching Fredericton. I found a funny story about venomous caterpillars in the city, so  we’ll  do  caterpillars  instead.  The  rules  for  the  game  are  simple:  kill  all  the caterpillars before they kill you. The problem is, these are space caterpillars (and you are in a space ship) when you shoot them, they split at the point they were hit, and now you have two smaller caterpillars!

To save explanation, try running a sample of the program (how yours will act) on AN FCS computer using the precompiled executable on D2L. (a3demo). When you copy it

over you will probably need to give it executable permissions (chmod u+x a3demo) wasd controls for up/left/down/right), space to fire, and q quits.

This assignment seems large, but can be broken down into many small components that are, on their own, easy to create. The tough part will be making them all run together with threads and managing resources with mutexes! Take your time reading through  this,  tackle  one  small  problem  at  a  time,  and  review  this  document throughout your work!

Synopsis:

-   Have a player spaceship that the player can control using w, a, s, d, around a restricted space at the bottom of the screen. The player spaceship must animate.

-   Generate caterpillars starting at the top of the screen, at some random interval. They go left to right (or opposite), and when they hit an end, they go to the next row and change direction. Note in the sample how they wrap around (tricky logic). Caterpillars must animate graphics in addition to move.

-   If the player presses space, a bullet fires from the player toward the top of the screen. If it goes off the screen, it is destroyed. If it hits a caterpillar, the caterpillar splits into two at that spot, and you now have two caterpillars, with the new one going faster than the old one by some multiple. If one of the two caterpillars is below a minimum size (e.g., 5), it dies. The player has a reasonable maximum fire rate (e.g., once per n ticks).

-   The caterpillars randomly shoot from their head at the player.

-   When the player is hit, pause the game briefly and kill all the bullets (but leave the caterpillars) to avoid unfair re-spawn deaths. If the player is hit, they lose a life. When no lives are left, the game is over.

-   The player wins if there are no caterpillars left on screen.

-   The program must quit properly by joining all threads, until only the main one is left, and freeing memory, and quickly. The final Done” text must appear on the  console  as  in the  provided  main and sample. This  is to highlight that you did not just use an exit() call. Every time you create a thread, you MUST think: who will join it and when? This is to make scalable, reusable  programs.  For  the  same  reasons,  you  must  free  all  memory properly.

-   There must be no evident race conditions or deadlock conditions.

-   Game mechanics will not be a major concern, e.g., left-over dead aliens, exact speeds, etc.  Collision detection  (e.g.,  bullets  hitting the  player or caterpillars) must be perfect to help test for race conditions.

REQUIRED  programming  components: As this is a threading assignment, you need the following (to make it hard enough!)

    You will create (at least) the following threads. You may find it useful to make

additional ones to help you. Threads must be joinable (default), and cannot be detached (man pthread_create).

➢  a thread for the player. This handles the player animation and other things, e.g., what happens when the player is shot.

➢  a thread for the keyboard. This requires its own thread so it can block while the rest of the program runs. This is quite tricky because you will have to use the select” command (man select) : it blocks until there is data on a stream, or on a timeout. Here is the problem: if you use getchar, it blocks. While it is blocking, the game may end (you get shot). However, until getchar unblocks that thread cannot end. Using select, you can time out regularly to check if the game is over before blocking again. I have provided a working example using the command, but you should try to understand it by reading the man page for pselect.

➢  a thread to re-draw the screen / perform a refresh using the command in the provided console code. Do not do refreshes each time you draw, only here.

➢  An upkeep thread, that puts updated score and player lives to screen, checks if there are no enemies left, and does regular cleanup (such as delete memory left behind for dead bullets and caterpillars, maybe).

➢  A thread that spawns new caterpillars at a regular (but somewhat random) interval.

➢  a new thread for EACH caterpillar. The thread lives until the caterpillar is shot and killed. Using a single thread for all the caterpillars is not acceptable. When a caterpillar splits, a new thread is started for the new caterpillar.

➢  a new thread for each bullet (yours and caterpillars’!), which lives until the bullet gets consumed into an enemy or you, or until it leaves the screen.

➢  a main program (not in main.c!) that starts everything and then sleeps using a condition variable (pthread_cond_wait). When the game ends this thread is  woken  up  (pthread_cond_signal)  and  cleans  up.  You  must  use  a condition variable and signal here for the assignment.

.   Dynamically managed (malloc/free) linked lists: these are very thread un-friendly. At least one list for the bullets, and one list for the caterpillars. No storing in arrays, etc.

In a real game engine, you would likely have fewer threads, e.g., one thread for enemy AI, one thread for input, etc. However, games are highly multithreaded and have a lot of concurrency issues. Making a game engine is a lot like making a simple OS as well: there is a core set of functions that control access to game resources and keeps track of states of other parts. Then, the actual game components (player, enemies, etc) will access those through the engine. This assignment should require more thinking about the engineering and planning of your solution than normal, but it is  perhaps  algorithmically  more  straight  forward  than  A2,  as  each  individual component (e.g., make a player move) is relatively simple.

Have fun! There’s a lot up to you (redesign the spaceship or enemy look, manage difficulty, etc). Your caterpillars may just be simple chains of ascii characters that animate a bit, or they may be more like as seen in the example, larger and stranger looking. Want to add other enemy types? Go for it! There are no game aesthetic or marks for fun” factor, but it can feel good to make something you’re proud of.

Handout:

You have been provided with a console.h/console.c library that provides text- mode functions for you and a sample program. Be sure to compile with the –lcurses flag to link to the curses (text graphics) library, and the –pthread flag to link to the posix-threads library. Console.h has a lot of comments to explain how to use each function. Definitely use these in your solution . They are provided so you don’t have to worry about graphics” and drawing to screen here. An example and main.c (in distribute” with console.h/c) will help you see how this is used.

.  This library is simple to use (see the examples included in my distribute sample code). There  is a screen  buffer off screen. You draw to the  buffer  using the commands detailed in the library. To have the changes reflected to screen, use the refresh command. To move, e.g., the player, you first draw a blank square where the player WAS and then draw the player at its new location.

    This library contains a sleep function that sleeps for the given number of ticks,

where a tick is 10ms. Use this in your thread loops, e.g., to set the speed of screen redraw (1 tick?), alien animation, movements, etc. Most of your threads will be loops that sleep before checking for more work.

    note that you can alter speeds simply by making each sleep longer or shorter.          this library is not thread safe! (e.g., it is non-re-entrant) Create a mutex

and make sure to lock it before using ANY screen calls. Not ensuring mutual exclusion will yield funny results.

    You shouldn’t  really  need to  look at the Console.c file, and there are  limited

comments in it. Most information you need is documented in the .h file.

Distribute

I have included a distribute” package which includes multiple files. There is a rough make and sample set up to get you started feel free to use and edit these as necessary (though, as mentioned, you shouldn’t need to read or edit Console.c you will  need to compile  it  into your  program, so I am  including  it  here). The  main example  file  contains  a  sample  enemy,  gameboard,  and  3  examples  of  how  to perform  basic  tasks  in  this  environment.  They  are  NOT  thread  safe  examples necessarily, so they are commented out. Uncomment the example you want to see run, make, and try it out! Some will break, to showcase why mutexing, especially the screen resource (a shared, critical resource) is important, and how it could make nonsensical output when race conditions occur.

These examples should be either useful or fixable (and then useful) for you. You can use them, delete them, or reference them in your final code. In other words, they should help act as building blocks or simple examples for your final assignment. They are designed after looking at common problem points getting started for students in my prior sections of this course. If you need help understanding them, send me an email or come talk in office hours.

Hints:

-   KEEP FINE-GRAINED MUTEXING, e.g., only lock each caterpillar, the player, the screen, a list, etc., as you need it. A single, global lock is missing the point (and extremely  inefficient)  and  will  yield  very few  marks,  potentially  even  negative marks.

-   What happens to memory when a joinable thread dies (man pthread_create)? What happens if you are making a lot of threads (bullets) and killing them and do not clean up the memory as you go?

-   Suggested  order: Get the  player’s ship on-screen and animating, to  practice threads (create the screen refresh and player threads first). Then get the keyboard thread working to move the player around (see the sample input example). Get a single caterpillar working, and then the thread for spawning new ones. Add bullets last, as they are the hardest part. AT EACH STEP make sure you can quit cleanly and join all threads that you created. Take each step slowly, and think What is the next smallest piece of work I can do to get closer to a finished solution?” E.g., draw a caterpillar first, then think about spawning them, then think about moving them, then worry about wrapping around, etc.

-   HHIINNTT:: USE GDB. seriously. I’m not joking. I say this all the time because I mean it. Spending an hour or two reading about gdb and playing around/learning it will save you dozens of hours over this course, and good debugging skills will save you so much time throughout your career. Your program segfaults? run it through gdb and do a backtrace and it tells you where. Your program deadlocks? GDB can let  you  look  at  where  each  thread  is  stopped  so  you  can  figure  out  who  is contending. Printfs? Sure, if you don’t mind taking a lot of time to sift through threaded output … seriously. gdb can turn an hours-long debug session into 5 minutes as you see which threads are blocking on which mutexes. Of course, if you prefer other debugging tools that’s fine. The point is, they’re extremely useful tools. Printfs help find simple bugs, but if you’re stuck, use gdb.

-   Of course, debugging threads is difficult as you can only gdb one thread at a time! All fully featured debuggers (DDD, GDB, visual studio’s etc), should be able to switch  through  threads  through  various  commands.  Different  threads  can  still trigger breakpoints so make sure to keep track of what your debugger is showing you. Read up on gdb (or your debugger of choice) and threads … it’ll help you!

➢  I talk a  lot about debugging  because debugging threads  is  perhaps going to be the hardest thing you have debugged yet the behavior can change each run, thanks to interleaving being different each run, so finding consistent behavior to help you debug is very difficult.

-   This is a big assignment, and some students get overwhelmed in the organization. I made a lot of files and classes to help with this, including some that just held utility functions (e.g., wrapping classes to help with thread creation and deletion).

BONUS: make a submission note to the marker in D2L about the bonus, if you do it.

Bonus  (10%): Your program creates / destroys threads constantly as things are created and destroyed this is a huge overhead. Implement a thread pool to re-use threads once they are abandoned. NOTE: this does not mean making bullets simply move to a new location, this means making a generic library that does jobs, so that when a thread dies the library holds onto the thread instead of killing it, and a new job takes a held one instead of creating a new one. E.g., a caterpillar thread may be recycled as a bullet next time! This isn’t hard once you see it. You can rely on function pointers (as the work to do). Note that you can have multiple listeners on a condition variable (e.g., waiting for work!).

Marking

Assignments that do not have a Makefile, do not compile, or do not run (e.g., no       action, or segfault before running) will not be marked, and will receive a 0. Makefiles will not be marked, just get it working. If segfaults happen part way, we will mark up to the segfault. Partial marks may be given for code that segfaults part way through.

Marks in brackets, with resolution to half mark. To get full marks in a category your  solution must be amazing” (e.g., coded well, general, with good algorithmic             solutions). Good solutions that have small quirks or could be improved can lose 0.5-2 marks, and on the opposite ends, solutions that have something kind of working may gain 1 mark. Handing in partially working (not segfaulting) solutions that get the gist of things working is a good way to get a reasonable score on the assignment. Remember to develop incrementally!

[4] C quality defensive programming, error checking, no magic numbers. Your listing file is used for this. No listing file, you get 0.

[2] Basic player – animates, moves, can shoot bullets

[3] Advanced player dies when hit (respawns, all bullets disappear). Game over when no lives left.

[4] basic caterpillars animates, move, wraps properly. Shoots bullets

[3] Advanced caterpillars breaks when hit, spawning new thread. Dies when too small.

[3] bullets – move appropriately, die appropriately

[3] end conditions: quit, win, and lose

[3] joins all threads and quits cleanly