PROGRAM #3
Fall 2009
Due: October 30, 2009, 5pm on eLearning
General Guidelines:
- All source code must be in C++. You can use Windows or Unix environments at your discretion.
- Each program project should be accompanied by a COVER SHEET (see details below). Assignments without cover page will NOT be graded.
- Team work is allowed (although not mandatory) for this project. Each team should comprise of at most two members. Although team work is recommended, grading will not differentiate between 1-member and 2-member teams. It is an option that is intended to encourage joint discussion and teamwork.
- The final material for submission should be entirely written by you. If you decide to consult with others or refer materials online, you MUST give due credits to these sources (people, books, webpages, etc.) by listing them on the cover sheet mentioned below. Note that no points will be deducted for referencing these sources. However, your discussion/consultation should be limited to the initial design level. Sharing or even showing your source code/assignment verbiage to anyone else in the class, or direct reproduction of source code/verbiage from online resources, will all be considered plagiarism, and therefore will be awarded ZERO points and subject to the WSU Academic Dishonesty policy. (Reproducing from the Weiss textbook is an exception to this rule, and such reproduction is encouraged wherever possible.)
- Grading will be based on correctness, coding style, implementation efficiency, exception handling, source code documentation, and the written report.
- Submission: All assignments with cover sheet should be zipped or tarred into one archive folder (named after your last names), and attached by email and sent to the instructor and one of the TAs through the eLearning website. For team submission, send only one mail per team with CC to other team member and the instructor. Regarding which TA to send to, should be based on the message I sent over email on eLearning.
Submissions are due by 5pm. A late penalty of 10% will be assessed for late submissions within the next 24-hour. Note: Submissions will be accepted only through the eLearning webmail. Any other submission outside the eLearning portal will be discarded and not graded. (In the unlikely event of an eLearning server outage on the day of submission, assisgnments can be emailed to the instructor's EECS email account.)
PROBLEM A board game
For this assignment, you will be implementing a simple board game using the best data structure of your choice. A "board" is defined as a m x m square matrix, with each cell identified using a unique (x,y) coordinate. An example 10 x 10 board is shown in the figure below. In a game, a board has n players. It should always be true that n ≤ m. The figure shown below is for m=10 and n=8.
Your task is to implement the following specifications and functionalities:
- Write a Board class
that implements a board of size m x
m with n players. At the
start of the game, all the m x m
empty cells of the board are empty (i.e., n=0). As the game progresses n is allowed to change. However, the dimension of the board (m x m) has to stay fixed.
- Write a Player class
that implements each player. Each player object will have a unique,
positive integer ID, and will occupy a unique (x,y) position on the board. Care must be taken that the value
of (x,y) position is always
within bounds of the board at all times. Also, no collisions are allowed -
i.e., no two players are allowed to share a cell.
- Implement an Insert
method in the Board class that will allow you to add a new player to the
board. The method should take as input the player ID to be inserted, along
with a desired (x,y) position
into which it is to be initially placed. For successful insertion, i)
another player with the same ID should not already exist and ii) the specified
insertion position on board should be currently unoccupied. A third
condition would be to ensure the total number of players with this
insertion (i.e., n) should not exceed m.
If successful, the method should increment n and return true. If insertion fails, the code
should display an appropriate/informative error message and return false without changing the data
structures.
- Implement a Remove method
in the Board class that will allow you to remove a player from the board.
The method should take as input the player ID to be removed, and should
return true upon successful
removal and false otherwise
(i.e., player not found). The value of n
should also be accordingly updated. Note that upon successful
removal, the corresponding cell on the board should be released to being
unoccupied.
- Implement a Find method
in the Board class that is given a player ID and returns true if the player is found and false otherwise.
- Implement a MoveTo method in the Board class that takes as input a player ID and a destination (x,y) cell position. The method should move the player from its current position, say (x1,y1), to the new position (x,y) only if the both following conditions are satisfied:
- (x,y) is also within bounds, and
- the movement from (x1,y1) to (x,y) is always along the same row or same column or same diagonal in any direction (i.e., top-left -- right-bottom or top-right -- left-bottom).
Additional action is necessary if the destination cell (x,y) already has some other player, say Y. Then this function should first remove Y from the board before placing this player (ID) in its new position. Upon a successful move, the method should return a Boolean true. If any player was removed in the process, the method should print a message to indicate which player was removed. If the move fails, the code should display an error message stating the reason of failure and return false.
- Implement a PrintByCoordinate
method in the Board class that prints all the player IDs along with their (x,y) positions, in the increasing
order of their x-coordinate
values. If there are many players with the same x-coordinate value then you may print them in any order. In
the example illustrated in the figure above, this method can print the
player IDs from the positions (in this order): (3,2) (4,3)
(4,6) (5,7) (6,3) (8,2) (9,3) (9,8). Another equally correct output (among
other possibilities) is: (3,2) (4,6) (4,3) (5,7) (6,3) (8,2) (9,8)
(9,3).
- Implement a PrintByID
method in the Board class that prints all the player IDs along with their (x,y) positions, in the increasing
order of their IDs.
- Write a main function in which you test all the above methods at least once. You can think of using the example in the figure above as an initial configuration to do testing. (We will have our own test code to test your source. Test sample here) There will be only correctness/functionality testing in this exercise. No need to devise any performance or scalability testing, although performance will be assessed at the design level.
You should make the best choice possible for the container data structure(s) based on what is expected to give you the best time and memory complexities in practice. In practice, you can expect n to be much smaller than m. You can also assume that the probability of O(n) players occupying cells with the same x-value is very low.
Design/coding complexity is another factor to consider although of secondary importance when compared to performance. You are permitted to maintain multiple data structures and/or copies of the same data in different containers as you deem necessary for design and efficiency. You are free to define new member functions not specified above to enhance code reuse and modularity.
Written Report:
In a separate document (Word or PDF), compile the following sections:
· A: Problem statement. In a couple of sentences state the goal(s) of this exercise.
- B: Experimental setup. In this section, specify the machine architectural details where the testing was conducted. Also mention whether you used Windows or Unix or Mac OSX for your testing.
· C:Algorithm design (limit to 2 pages): Provide a design document for your code. State what data structure(s) options you considered, what you ended up using, why, what are the run-time complexities for each of the functions, and what is the memory complexity for your implementation as a whole. Figures and illustrations will be preferred.
FINAL CHECKLIST FOR SUBMISSION:
___ Cover sheet
___ A separate folder containing all your sourcecode (including the main function you used for testing)
___ Report
___ Both the above zipped into another folder archivecalled Program3<YourLastNames>.zip