CS247—Assignment 3 (Spring 2024)

Note: On this and subsequent assignments, you will be required to take responsibility for your own testing. As part of that requirement, this assignment is designed to get you into the habit of thinking about testing before you start writing your program.  If you look at the deliverables and their due dates, you will notice that there is no C++ code due on Due Date 1. Instead, you will be asked to submit test suites for C++ programs that you will later submit by Due Date 2.

There will be a handmarking component in this assignment, whose purpose is to ensure that you are following an appropriate standard of documentation and style, and to verify any assignment requirements not directly checked by Marmoset.  You are not expected to follow a specific style guide, however your code should be readable and you should code with good style.  That is, abstract out functions instead of having repetitive code segments, follow good OOP style, as well as not writing overly complex code when unnecessary.  Please be aware that if handmarking shows you have not followed the requirements of the question, correctness marks from test cases can partially or totally be taken away.

Some or all of these programs will ask you to develop C++ modules in order to make a provided test harness file which includes those modules work.   Since you must use the main provided in the test harness to test your program, it is suggested that you first begin by providing empty implementations of all of the necessary functions.  Then you will at least be able to compile, and as you implement each function you can recompile and test them immediately.

Note: All of your program must not leak resources.  If your program produces the correct result but in doing so leaks resources then test case will not be considered as having been passed.  We will use the tool valgrind to test your programs (which is available on the student servers) so you can too. You code must compile and run correctly on the student server.

Allowed headers for this assignment: For this  assigment you may use any of the standard library headers you would like.

1.  Finding a way out of a maze is a classic sample problem used with learning algorithms. It’s especially common to see mazes used as simple examples of how Reinforcment Learning algorithms work. In these types of puzzles an “agent” exists in a maze, and can take actions to move through it to find its way out.  In this question you’ll be using your knowledge of virtual functions to develop a class hierarchy for different types of mazes to be solved.

You will have to develop at least four classes, an abstract base class Maze, and concrete classes BasicMaze, TeleporterMaze, and IcyMaze. Your mazes represent a two-dimensional grid of tiles, and the types of tiles that are acceptable can vary between the maze types.

•  Start Tile - Denoted by the character ’S’ , this denotes where the agent will begin in the maze when it is first created, or when it is reset.  You may assume every maze has exactly one start tile.

•  Goal Tile - Denoted by the character ’G’ , this denotes the “goal” or exit of the maze. When the agent reaches this location its task is done.  There may be multiple goal states in a maze.

•  Open Tile - Denoted by the character ’O’, this denotes a normal tile of the maze that the agent is allowed to walk through.

• Wall Tile - Denoted by the character ’X’ , this denotes a solid wall tile of the maze that the agent is not able to walk through.

• Agent Tile - Denoted by the character ’P’ . This is not actually a tile in your maze, but when outputting your maze whichever tile the agent is currently located on should be printed as a ’P’ instead of its tile character.

•  Teleporter Tiles - Denoted by any digit character  ( ’0’ through ’9’), this denotes a teleporter tile. Only  available  in the TeleporterMaze variant. When the agent walks on a teleporter tile their location becomes that of the next matching teleporter tile “in order” .   That  is,  if the agent walks on a teleporter tile denoted by ’2’  (we will call this the source), then after that move the agent is actually located at the next teleporter tile denoted by  ’2’ (we will call this the destination). The definition of how to find the ”next” here is interpreted the same way English is read, from left-to-right, top-to-bottom starting at the location immediately after the source.  If you reach the bottom right corner of your maze and have not found a matching teleporter, than you should begin again looking at the top-left corner of your maze. If you are unsure about the behaviour, as always, test with the sample executable.

Here is an example of a basic maze, with the agent directly adjacent to the goal state, with the start state in the top left and the goal state in the bottom right:

SOOXO

OXOOO

OXXXP

OOXXG

Your program will be tested with the provided test harness a3q1 .cc.  As always for clarifica- tions on these functions you should see the sample executable, in the case of a discrepancy between the assignment specification and the sample executable you should match the sample executable. The required functions (those used in a3q1.cc) are:

• Default Constructors - Each of the three classes must provide a default constructor.

•  Overloaded Input Operator - The input operator should be overloaded to work with Maze reference parameters. This function should read characters from the stream using them to create your maze, until it reads the character ’Q’ which is the signal to stop. Every time a new line character is read that means the user is inputting the next row of your maze.  When a character that is not a valid tile of your maze is read it should be ignored.  See the provided input file for an example of the formatting.  Empty rows (when a newline is read when no valid characters have been read before it) should be excluded from your maze. In order to read in the newline characters you will need to use the noskipws flag with the provided stream, however you should make sure that after you are done the stream is returned to itsintial state.  See cplusplus.comfor information on this flag.

•  Overloaded Output Operator - The output operator should be overloaded to work with const  Maze reference parameters.  This function should print out the maze, with the location of the agent being represented by the character ’P’ . There should be a newline after every row, including the last one.

•  The member function vector makeMove(char) - This function is used to allow the agent to move through your maze.  The input to this function is one of the characters ’N’,  ’E’,  ’S’, or  ’W’ , denoting the agent attempting to move North, East, South, or West respectively. The rules of movement vary for the types of mazes.

– In any maze if the movement is off the bounds of the maze, or into a wall tile, then the agent remains in its current position.

– In the BasicMaze if the tile is not a wall and in the bounds of the maze then the agent moves into that tile.

– In the TeleporterMaze the rules of the BasicMaze are followed, but additionally if the tile is a teleporter tile then the agent is teleported to corresponding destination tile, as per the rules described above when defining teleporter tiles.

– In the IcyMaze the agent will repeatedly move in the direction provided until it reaches the goal, or until it can no longer move in that direction (it reaches a wall or the bounds of the maze).

The return type of this function is a vector of ints which should have exactly two elements within.  The first element should represent the agent’s new position in the x-axis, and the second element should represent the agent’s new position in the y-axis. Unless the agent moved into a goal state with this move, then both values in the vector should be -1.

•  The member function void  reset() - This function “resets” the maze, by placing the agent back at the starting tile.

Deliverables:

a) Due on Due Date 1: Design  a  test  suite  for  this  program.    Call  your  suite file suiteq1 .txt.  Zip your suite file, together with the associated  .in files, into the file a3q1 .zip.

b) Due on Due Date 2: Write the program in C++. You must include in your submission (a3q1.zip) your header and implementation files as well as a Makefile that builds your program with the executable named a3q1.

2. In this question you will be building a fun ASCII art drawing and animation program! You’ll start with a blank canvas, and will draw rectangles consisting of characters of your choosing on that canvas (remember that any point is a 1x1 rectangle, so you can draw anything!), and choose how your drawing will evolve with time.

The key to the functioning of this program is the Decorator pattern.  A blank canvas will respond with a blank space to any query about the contents of a cell at a particular row or column. However, it can be decorated by rectangles, which will respond in their own way to the same query, or will pass it along to the ASCII art element behind them.  Moreover, the key to the animation aspect of this program is that the response to a query for a cell can be time-varying.  So a query to a cell actually involves three parameters:  the row, the column, and the tick count (where the latter is the number of rendering events that have occurred since the last time the animation was reset).

You are to support the following kinds of ASCII art elements:

• filled box:  A simple solid rectangle, specified by top and bottom row (inclusive) and left and right column (inclusive). Does not move.

•  blinking  box:   A box that is displayed when the tick count is even,  and is transparent otherwise.

•  moving  box:  A box that moves one position  (either up, down, left, or right) with each tick.

•  mask box:  A box that is invisible unless there is a visible art element beneath it.  In that case, the part of the mask that lies above the art below becomes visible and covers that art. Does not move.

The provided starter code comes with a test harness that supports the following commands:

• render — causes the current artwork to be displayed, with a frame around it, so that the boundaries are clear (see the provided executable for details). Counts as a tick.

• animate  n — renders the artwork n times.

• reset — resets the tick count to 0.

•  filledbox  t  b  l  r  c — adds a filled box with given top, bottom, left, right boundaries, filled with the character c (assumed to be non-whitespace and printable ASCII in the range 0–127). Invalid if top exceeds bottom or left exceeds right.

• blinkingbox  t  b  l  r  c — adds a blinking box, with parameters understood as above.

• movingbox  t  b  l  r  c  dir — adds a moving box, with first five parameters understood as above and a direction dir, which can be one of u  d  l  r. Clarification: These parameters are understood to be the position of the box when the tick count is 0.  If the tick count is not 0 when the moving box is placed, it will show up shifted by a number of positions equal to the current tick count.

• maskbox  t  b  l  r  c — adds a mask, with parameters understood as above.

Important: As the point of this problem is to use the Decorator pattern, if your solution is found in handmarking to not employ the Decorator pattern, your correctness marks from Marmoset will be revoked.

Due on Due Date 1: Submit your test suite (suiteq2 .txt and all necessary files) in the file a3q2a.zip.

Due on Due Date 2: Submit your solution in the file  a3q2b.zip.  You must include a Makefile, such that issuing the command make will build your program.  The executable should be called a3q2.

3. Note: This problem asks you to work with XWindows graphics.  Well before starting this question, make sure you are able to use graphical applications from your student.cs session. If you are using Linux you should be fine (if making an ssh connection to a campus machine, be sure to pass the -Y option).  If you are using Windows and putty, you should download and run an X server such as XMing, and be sure that putty is configured to forward X connections. If you are using a Mac, download and run XQuartz, and pass the -Y option when making ssh connections. Alert course staff immediately if you are unable to set up your X connection (e.g. if you can’t run xeyes).

Also (if working on your own machine) make sure you have the necessary libraries to compile graphics. Try executing the following for our supplied graphics demo:

g++14  window .cc  graphicsdemo .cc  -o  graphicsdemo  -lX11

Be sure to add the -lX11 option to the linking line of your Makefile (that’s lowercase-L, X, eleven, and it goes at the end of the linking line in your Makefile).

This question extends the previous question, in which you wrote an ASCII art animator program.  In that problem, you had a studio object that managed the tick count,  and was responsible for rendering your artwork to an output stream (std::cout).  In this problem, we’ll take that second responsibility away from the Studio class by employing the Observer pattern. Your Studio class will become a concrete “subject” class in this new model.

If you wish to actually seeyour artwork, you will need to create an observer object and attach it to the subject. But why stop at one? You could, in fact, create several observers!  (And why should they all be necessarily text-based?  More on that in a bit.)  A bunch of observers all observing and rendering the same text is boring. But who says they all have to be watching the same part of your artwork?  And who says your artwork has to be limited to just a 10x10 grid?

No, in this problem, your art has rows and columns spanning the entire range of 32-bit integers! But each of your observers, of course, will only see a much smaller portion of it.

In this problem, you will restructure your solution so that, in addition to following the Decora- tor pattern, it also conforms to the Observer pattern.  As well, incorporate the other changes described above.

The test harness for this problem includes all of the commands from the previous problem. Those whose meanings have changed are described below, along with the new commands specific to this problem:

•  render — causes all observers to render their images.  Images should be displayed in the order the observers were registered with the subject.

•  addtext  t  b  l  r — adds a text-based observer watching a portion of the image with the given top,  bottom,  left,  right boundaries.   Invalid  if top  exceeds bottom or left exceeds right. This observer, when notified, will display its view to std::cout.

•  addgraphics  t  b  l  r — adds a graphical observer,  with parameters understood as above.

For the graphical observers, you will use the Xwindow class that has been provided to you.

Make  sure you  have  a  working  XWindows  server  running  on  your  computer, such that you can run graphical applications over an SSH connection.  Test this EARLY. Your windows will be of size  10r by  10c, where r is the number of rows being observed, and c is the number of columns being observed.  Represent the rendered objects by colour-coded 10x10 squares:

• A red square will represent any lower-case letter.

•  A green square will represent any upper-case letter.

• A blue square will represent any digit.

• A black square will represent any other printable character.

• A white square will represent no character.

If you have difficulty distinguishing colours, such that this portion of the assign- ment would be difficult for you to complete, then please contact an ISA to request an alternative means of completing the graphical display.

Important: As the point of this problem is to use the Decorator and Observer patterns, if your solution is found in handmarking to not employ these patterns, your correctness marks from Marmoset will be revoked.

Something to think  about: You will probably find that your graphical display, when running anywhere other than on campus, will be quite slow.  Think about how you might optimize the performance of your graphics observer, so that it renders more quickly.  This is not an assignment requirement, but something to think about for your own interest.

Due on Due Date 1: Get X11 forwarding working on your system.  When you have done so, submit a text file a3q3a .txt with the contents (on one line, with a newline at the end, period included) I  successfully  ran  xeyes .  You do not have to submit testing for this problem.

Due on Due Date 2: Submit your solution in the file  a3q3b.zip.  You must include a Makefile, such that issuing the command make will build your program.  The executable should be called a3q3.