You are now allowed to redeclare OutputBoard() in
GridGame.h as not being "const"--but you will get extra credit
if you can make it work with the "const" left as-is.
Objectives
To gain experience:
Using polymorphism in C++.
Adapting a hierarchy of classes to a new design.
Using exceptions.
Project Policy
This project is considered an CLOSED project. Please review the
open project policy before beginning
your project.
Overview: the Polymorphic Grid Game Collection Program
In Project 4, you designed a collection (okay, "two" is stretching the
definition of "collection" a bit) of board games as a C++ class hierarchy,
to take advantage of the reusability that inheritance affords.
In this project, you are going to redesign and augment the work from
Project 4 to take advantage of the even more powerful mechanisms of
late binding and polymorphism. You will be restructuring Project 4's
code to make it simpler and clearer, as well as more flexible, and
you will also be adding an entirely new class to play an additional
"game". We put that word in quotes because the game we will be adding
is not a traditional board game in the usual sense... but we will make
it work.
Conway's Game of Life
The game we will be adding is called "Life", or more fully, "Conway's
Game of Life". Wikipedia has a good description
here.
It is a classic computational diversion that has been
the focus of much CS research. The rules are given below, but
basically, it is a "game" that is fully determinisitic (in other words,
completely predictable), and yet, hard to predict to any significant
degree. Computer scientists could stare at an evolving Life game for
hours without getting bored.
In the classic version of the game, the board is effectively infinite
in size. The user lays out an initial board
configuration, consisting of pieces (there's only one kind of piece)
placed at various positions on the board; the rest of the spaces are empty.
This layout is called "generation 0". The user then starts the automatic
board generation process, and the game proceeds to generate successive
generations of the board, where each new generation is calculated
deterministically from the current generation's
board according to the following rules:
For each grid position, or "cell", scan the 8 cells immediately adjacent in the
horizontal, vertical, and diagonial directions.
If the current cell contains a piece, do one of the following:
If less than 2 of the neighbors are occupied, the current
cell dies of loneliness (i.e., the piece is removed).
If 2 or 3 of the neighbors are occupied, the current
cell is happy and lives on (the piece is left in place).
If 4 or more of the neighbors are occupied, the current
cell dies of overcrowding (the piece is removed).
Or, if the current cell is empty:
If exactly 3 neighbours are occupied, a new piece is born in
the empty cell: this is reproduction.
For all other cases, leave the cell empty.
You should only be considering cells from the current generation's board
in generating cells for the next generation. In other words,
you should not be changing the cells in-place, because that would
mean you would be basing some of the cell updates from a mix of
old and new cells. (If this doesn't make sense, please ask your
TA or professor.)
Once the next generation is complete, replace your current generation
board with the new one.
You should study the patterns given
here. We've exerpted a couple of the simpler yet still interesting ones
for you:
(Courtesy of Wikipedia)
Make sure you understand how they work. For example, the one on the left
is called the "blinker" or "stoplight". In the vertical configuration,
most of the empty spaces immediately around the three vertically-aligned
pieces have 2 or fewer occupied neighbors, so they will remain empty.
Only the spaces immediately to
the left and right of the middle piece have exactly three living neighbors,
so they will be filled with a piece in the next generation. At the same time, considering
the three existing pieces, the ones at the top and bottom will die of loneliness,
while the one in the middle has exactly two neighboring pieces, so it
will remain in the next generation. Thus, the vertical line-of-3 becomes
a horizontal line-of-3, and then flip back in the next generation after
that.
Description
We will not be redescribing the GridGame class hierarchy here--refer
back to the project description for Project 4 to refresh your memory.
For this project, we will be providing the driver program, as before.
It will guide your design. The new driver program is much improved
from the version we provided for Project 4: it uses polymorphism
(or rather, assumes the class it will be using implement polymorphism)
to greatly reduce the size and complexity of its code, making it much
more understandable and maintainable in the process. For example, it no
longer depends on a type field in the game instance to decide
which of several member functions to call, but instead lets it be managed
automatically by the late binding mechanism. (Incidentally, that means
we've gotten rid of GameType.h completely.) You should study
the Proj5.cpp and Proj5Aux.cpp files that we provide to see what
is expected of your new GridGame hierarchy of classes. (You might
also want to compare it to the equivalent files from Project 4, to
see how much simpler they have gotten, thanks to polymorphism.)
Adaptation of the Reversi and TicTacToe classes
We are adapting the code for the Reversi and TicTacToe classes from Project 4.
However, to level the playing field among people with varying degrees of
success in finishing Project 4, we are providing the canonical implementations
of the TicTacToe and Reversi classes that the instructor wrote as his own
solution for Project 4. You are equally welcome to use your own code
from Project 4 instead; the tradeoffs are that you are more familiar with your own
code, but that you might be worried about its reliability. We're not
claiming our code is bug-free -- just that we probably won't blame you if
a bug in our code causes problems :-) If you are planning to reuse
your own code from Project 4, note that you must add one new member
function to the GridGame class:
int GridGame::NumPlayers(); // Simply returns the constant 2
This will be inherited by TicTacToe and Revrsi, but will be overridden
in the Life class.
Whether talking about your code or ours, the Project 4 classes were designed to use simple
inheritance and member function
redefinition to implement a subclass having a more specific implementations
of member functions that would have been inherited from the base class. In this project, you must
now modify the class hierarchy structure to use virtual functions and real overriding
to implement polymorphism. This should be relatively straightforward if you
understand the mechanics of how to write virtual functions.
You must modify the GridGame, Reversi and TicTacToe classes
to be polymorphic. You must make the functions in the parent
GridGame class be virtual, possibly pure virtual (thereby making
GridGame an abstract class), and use
member function overriding in the child classes, when necessary,
to implement more type-specific versions. You must pay attention
to the usual rules of good class design: move the function
definitions up to parent classes when it might be usefully
shared by the child classes, but move it down the hierarchy,
or override, when the child class needs a specific implementation.
This redesign process applies to all of the following functions in
the GridGame class hierarchy's interface:
OutputGreeting()
NumPlayers() // THIS IS NEW
IsDone()
OutputBoard()
OutputResults()
GetPlayerSymbol()
IsLegalMove()
DoMove()
The above is just a list; you must look at the code to review
what the declaration and purpose is for each.
Once you have finished this adaptation, you should be able to
compile the full program to see if the new polymorphic logic
works properly. We have provided stub Life.h and Life.cpp
files to allow you to build a working program, as long as
you don't try to actually play a Life game.
One last note: unless you change the logic of these functions
significantly from what we are providing, you do not have to
add documentation for the functions in these provided
classes. However, you do have to fully document any functions
you add or significantly modify. You also must document any
new classes you create, in particular, the Life class,
described next.
Implementation of the Life class
After you have adapted the GridGame parent class and
Reversi and TicTacToe child classes
and gotten them to work polymorphically, the next task will
be to write the Life class, again as a subclass of GridGame.
Adapting Life to work as a board game requires a bit
of creativity. It's not really an interactive game as originally
described in the intro: it only involves one player, and it doesn't
have a traditional sense of an "end". However, we can make it work.
The first modification will be to allow single-player games.
This has actually already been built into the Proj5Aux driver
functions: it now calls NumPlayers() (described above) to see how many
players the game allows. You must design the Life class
to override this function so that the driver will know Life
only has one player.
In your implementation of Life, you will make each "move" be a request
by the user to place a new piece, remove a piece, or cycle through one
or more generations of the board. This will be specified via the
same row/column entry system of all of the other games.
If the user enters row and column numbers that are within the bounds
of the board (using a 1-origin, as always), that means the user
wants to place or remove a piece from the board; it will place a
new piece if the position is empty, remove it if the position
is already filled. So, basically, it just flips the state of
that position. The driver
will then re-display the board and prompt for another "move".
If the user enters a "0" (zero) for the row, that is a special flag
indicating she wants the game to do some automatic board generations.
The column number then
specifies a number of generations to automatically iterate for
the current board layout. However, you must not output the board
from within the DoMove() member function; instead, you must output
the multiple boards from within OutputBoard().
If the user enters the special pair "0 0", that indicates the user
wants to quit. Again, however, to fit the design of the game,
you must not exit immediately from DoMove(). Instead, the next
call to [GameDone()] must return true, so that the driver can
properly finish the game.
All other moves (e.g., negative coordinates, or coordinates over
the board size) are still illegal, and must be handled as such.
The above special cases means that the definition of a legal move
(as implemented by ) is different from our other games.
Also, in our version of Life, We must also deal with edge cases,
literally: in the real Life, the grid is infinite.
On our finite board's borders, the cells will have fewer
than 8 neighbors (some will have as few as 3!); for these cells,
just apply the same rules as usual, just making sure
you do not scan non-existent positions beyond the board.
Since this is a new class that you are creating, all of the
class coding standards apply: you must put in a file header, a
function header for every function, and inline comments
to describe your variables and code.
Implementation
You will have to do the following four steps to build a working
Project 5:
Step 1: Study and understand Proj5.cpp and Proj5Aux.cpp
This is self-explanatory.
STEP 2: Adapt the GridGame, Reversi and TicTacToe classes
Now, you should work on adapting the GridGame parent class, and the
Reversi and TicTacToe child classes. As mentioned before, the
idea is to declare all of the functions in GridGame virtual,
then override the necessary functions in the child classes to
make polymorphism work.
You should not have to really write much new code for this part.
STEP 3: Create the new Life class
The skeletal versions of Life.h and Life.cpp that we provide
is actually mostly just documentation, plus just enough structure
to let you compile and test your Reversi and TicTacToe separately, as suggested
in Step 2.
You need to write a full implementation of the Game of Life.
You will use the same basic structure as the other games, but
adapt the behavior of the interface (i.e., member functions
and their purpose) to fit the Life game. This was covered in
an earlier section.
A couple of implementation details: this class should initialize
the player symbols string to the single-char string "O" (that's
the letter "OH", not the number "zero").
Also, the default board size created by the constructor should
be 20x20.
STEP 4: Compile, Test, Repeat
This step is obvious. Need we say more?
The Grid Game main()
The execution syntax for the program is almost exactly the same as for
Project 4: it takes one runtime argument, one of the strings "ttt",
"reversi", or "life", to indicate which game you want to play.
main() will then
construct an object of the proper game type, and go into a loop
requesting moves from the user (always a row and column, just like
in Project 1's Reversi). It firsts validates the move by asking the
game object, then if it is judged a good move, it will actually play
the move. Before each turn of the loop, it will ask the game object if
the game is over yet. When the game is done, main() asks the object
to print out end-of-game statistics, and then exits.
Requirements
1. You may not change any of the code in Proj5.cpp, Proj5Aux.h,
or Proj5Aux.cpp. You should not even submit these files.
You are free to change and of the rest of the files, and add any
additional files.
2. If you use any dynamic objects as members in your classes, you must have appropriate
destructors for the class that deletes these dynamic objects. You can use the one in GridGame as an example.
Hints
Hint #1:
Note that for the Life class, you still should not be outputting
any board displays from the call to DoMove()--that would violate
the purpose of that member function. This will cause problems with
a "0 #" move where you are asked to output a series of boards, one
for each generation calculated. In this case, you would need to store
away what the move request was, and execute it when OutputBoard() is
called.
Hint #2:
If you take the logic concerning cell birth and death, and draw it
out in a chart, you might see a very simple pattern that will ease
implementation.
Provided Code
Going along with the progression of the projects in this course,
we are providing even less overt design guidance on this project
than previously. Instead of documentation specifications that
you must write code to match, you must now actually analyze existing code
for hints on how your class must work.
First, there are the provided working driver source files; these files
must not be modified:
Next, there are the non-polymorphic implementations for the game classes.
You are free to use your own versions of these from Project 4 if you want.
Either way, you must significantly upgrade these to make them work
polymorphically:
(Note that the last two--Life.cpp and Life.h--are just stubs;
they only contain rudimentary hints about how you should design the
actual Life class yourself.)
Lastly, we are providing, for the first time, a Makefile.
Study it to see how it works. If you add any new files, you
must add them to the Makefile. Also, make sure you submit the
Makefile with your project, regardless of whether you modified it or not.
If you've ssh’ed into the GL servers, you can copy all of the
files over directly: issue
the following command at the command prompt while you’re inside
your project directory:
(Note the '.' at the end of the command--that is very important.)
Additionally, you are free to add any helper functions to make
your program more modular and cleaner in design, although we don't
see the need for any.
Example Session
The program takes one command line argument: one of "ttt", "reversi",
or "life", to select which game to launch.
It then goes into a contiuous loop, reading in a row and column to play the
next piece on, making sure it's a valid move, then executing the move.
It then prints out the resulting state of the game board.
It automatically detects when the game is done, and prints out
the final results.
The output for TicTacToe and Reversi are exactly as for Project 4,
so we do not repeat it here. The following is a sample run for the
Life game:
$ ./Proj5.out
Syntax: ./Proj5.out {ttt|reversi|life}
$ ./Proj5.out life
Welcome to Conway's Game of Life!
Player O's move: 3 4
--------
--------
---O----
--------
--------
--------
--------
--------
Player O's move: 4 4
--------
--------
---O----
---O----
--------
--------
--------
--------
Player O's move: 5 4
--------
--------
---O----
---O----
---O----
--------
--------
--------
Player O's move: 0 1
--------
--------
--------
--OOO---
--------
--------
--------
--------
Player O's move: 0 2
--------
--------
---O----
---O----
---O----
--------
--------
--------
--------
--------
--------
--OOO---
--------
--------
--------
--------
Player O's move: 0 0
--------
--------
--------
--OOO---
--------
--------
--------
--------
Completed 3 generations.
3 live cells at end.
$
Several things to note in the above example:
The board in the example is reduced to 8x8 for demonstration,
but your board should be a full 20x20 in the code that you submit.
Note that moves where you are adding or removing pieces to not count
as "generations"--only the moves starting with "0" actually go
through "generations" in Life.
Note that the user inputting "0 0" will cause one last board to
be output. This is not done by OutputResults()--it just happens
naturally because the driver sees that "0 0" is accepted by
IsLegalMove(), so the driver will call DoMove() and OutputBoard().
How to Test Your Project
At this point, you should know pretty well how to test your program.
Note that whether you use your versions of Reversi and TicTacToe
or ours, those classes should be pretty well debugged. You should
mainly be testing them to verify that the new polymorphic structure
works as expected.
You should then move on to testing Life. For that class, you should
check various cases to make sure both the structure and the algorithms
work. Go to the Wikipedia page linked at the top of the document
to check out some nice sample cell patterns that you can try out.
We will be automating much of the grading for this project.
It is absolutely essential that you do not modify any of the files that
we provided to you that we instruct you not to alter;
You should not even submit these files. If you do inadvertantly submit
your copies of these files, we will be replacing them with our own versions
before trying to compile and run your program.
Another requirement is that your executable, as produced by your Makefile,
is called Proj5.out; adjust your Makefile accordingly.
Project Submission
Before submitting your project, be sure to compile and test your code on the
GL system. See the Project Compilation section
of the course Projects page for details on how to compile and execute your
project on GL.
Assuming you’ve used the specified file names, submit your
project by typing the command
submit cs202 proj5 [all of your various .h and .cpp files] Makefile
See the Project Submission page for
detailed instructions. Note that we require you to submit the Makefile,
also. We will in fact be using your own Makefile to build your program,
so it must work properly.
You may resubmit your files as often as you like, but only the last
submittal will be graded and will be used to determine if your project is
late. Also note that if you rename or remove certain files, the old
versions that you submitted earlier will
stay in the submit directory unless you use "submitrm" to clean them out,
which you should. At the end, a "submitls" should show exactly those
files that are part of your project: no more, no less.
For more information, see the Projects page on the course web site.
Remember — if you make any change to your
program, no matter how insignificant it may seem, you should
recompile and retest your program before submitting it. Even the
smallest typo can cause errors and a reduction in your grade.
