Project 1: Snakes and Ladders - Fall 2024

Due: Tuesday Oct 1, before 9:00 pm

Objectives

  • Practice analyzing a project's requirements.
  • Implementing a linked list data structure.
  • Practice C++ dynamic memory management, i.e. avoiding memory leaks, avoiding double free, protection against wrong accesses in memory (segmentation fault), etc.
  • Practice writing test cases for a project.

Introduction

Snakes and Ladders is a dice board game that multiple players can compete with each other. The board can be of any size and it must be a square grid. Players make moves based on dice rolling and depending on what cell they land they might receive a reward or a punishment. If a player lands on a cell that has a ladder, the player can climb the ladder. If a player lands on a cell that has a snake, the player needs to fall down to the other cell containing the tail of the snake. You are assigned a task to design and implement a game engine for a Snakes and Ladders board. The grid in this engine is a linked list, and the players can traverse the list to advance. The following figure presents a sample board.

Figure from The Alzheimer Society of Brant, Haldimand Norfolk, Hamilton Halton, Ontario, Canada

Assignment

Your assignment is to implement the game engine which consists of a linked list.

For this project, you are provided with the skeleton .h and .cpp files and a sample driver:

Additionally, you are responsible for thoroughly testing your program. Your test program, mytest.cpp, must be submitted along with other files. For grading purposes, your implementation will be tested on input data of varying sizes, including very large data. Your submission will also be checked for memory leaks and memory errors.

The Rules

  • The size of smallest possible board is 9, that would be a board of 3x3.
  • No cell can have both a ladder and a snake.
  • The first cell and the last cell cannot have a snake/ladder.
  • At the start of game players are placed on the cell number 1.
  • The total number of snakes and ladders on a default board is 1/4 of the board size. For example, if the board size is 25, the total number of snakes and ladders would be (25/4 - 1) or (25/4 + 1).
  • On a default board the number of snakes and ladders are equal. We tolerate a difference of 1.
  • On a default board the snakes and ladders must be distributed evenly on the board. There should not be a concentration of snakes and ladders anywhere on the board.
  • The player 1 always starts the game.
  • A player's turn is specified with one of the values NOGAME, PLAYER1TURN, or PLAYER2TURN.
  • The min number of snakes and ladders on a random board is 2.
  • The max number of snakes and ladders on a random board is half the board size minus two (the first and last cells cannot have a snake/ladder).
  • On a random board the number of snakes and ladders are equal. We tolerate a difference of 1.

Specifications

The Snakes Class

The Snakes class has a pointer to an object of type Cell. The pointer is stored in the member variable m_start. This variable is the head to a singly linked list. The linked list represents the game board. The two players m_player1 and m_player2 start the game at cell number 1 in the list. They play in turn by rolling dice and perform the required moves. The game continues until one of the players reaches the last cell of the board.

Snakes::Snakes()
The default constructor creates an empty object.
Snakes::~Snakes()
The destructor deallocates all memory in the object and reinitializes all member variables.
void Snakes::clear()
This function deallocates all memory in the object and reinitializes all member variables.
Snakes::Snakes(int boardSize)
The alternative constructor creates a default game board. The parameter boardSize specifies the number of cells on the square board. If a user provides a size which does not have an integer square root, the constructor converts the size to the largest possible value less than boardSize which has an integer square root. For the requirements of a default board please refer to The Rules section on this page. If the requested size is not valid the constructor creates an empty object.
bool Snakes::makeDefaultBoard(int boardSize)
This function creates a default board. The parameter boardSize specifies the number of cells on the square board. If a user provides a size which does not have an integer square root, the constructor converts the size to the largest possible value less than boardSize which has an integer square root. For the requirements of a default board please refer to The Rules section on this page. If the requested size is not valid the function does not modify the object and returns false. If the object has already a board this function does not modify the object and returns false. If everything is in order and the new board is created the function returns true.
void Snakes::makeRandomBoard(int boardSize, int numSnakesLadders)
This function creates a board using random values. It clears the current board and creates a new board with the requested values. The user can specify two parameters. The parameter boardSize specifies the number of cells on the square board. If a user provides a size which does not have an integer square root, the function converts the size to the largest possible value less than boardSize which has an integer square root. Also, the user specifies the total number of snakes and ladders by passing the parameter numSnakesLadders. The function uses this parameter to create the snakes and ladders and it places them on the board in random locations. If the requested numSnakesLadders is an invalid value the function adjusts it to the min or max valid values. For the random board requirements please refer to The Rules section on this page. If the requested board size is invalid the function creates an empty object.
bool Snakes::play(int dice)
This function performs the requested move, the parameter dice indicates the number of cells a player can advance. Every time a move is complete the function changes the player turn. If a move is complete the function returns true. If a player lands on a cell with a snake or a ladder the corresponding action must be taken to complete the move. If a player lands on the last cell the game ends, in such a case the play function returns false. If a player is near the end the player must continue rolling dice until the player receives the required dice value to move to the last cell. Such a case is considered a valid play, then the function returns true.
int Snakes::rollDice()
This function returns a random number between 1 and 6.
void Snakes::reStart()
This function reinitializes the game without any changes to the board. The players can start the game again on the same board.
const Snakes & Snakes::operator=(const Snakes & rhs)
The assignment operator, creates a deep copy of rhs.
void Snakes::dumpBoard()
This function prints out the game board to the standard output. Note: The implementation for this function is provided to you. The purpose of this function is to facilitate debugging.

Additional Requirements

  • The class declarations (Snakes and Cell) and provided function implementations in snakes.cpp may not be modified in any way. You are not allowed to add a member variable. No additional libraries may be used.
  • You are not allowed to use STL template containers in the Snakes class.
  • You are allowed to use STL template containers in your test functions.
  • The class functions must be written in snakes.cpp; in particular, they must not be written “in-line.”
  • Private helper functions may be added, but must be declared in the private section of the Snakes class. There is a comment indicating where private helper function declarations should be written.

Testing

  • The test file name must be mytest.cpp; the file name must be in lower case, a file name like myTest.cpp is not acceptable.
  • The test file must contain the declaration and implementation of your Tester class and the main() function as well as all your test cases, i.e. calls to your test functions.
  • You are responsible for adequately testing your work before submission. The following section presents a non-exhaustive list of tests to perform on your implementation.
  • You must write a separate function for every test case.
  • Every test function must return true/false depending on passing or failing the test. Visual outputs are not accepted as test results.
  • The dump() function should not be called in the test functions. The dump() function is only provided to facilitate debugging.
  • Tests cannot be interactive. The test file mytest.cpp must compile and run to completion.
  • An example of declaring, implementing, and calling a test function, and outputting the test results was provided in the driver.cpp file of project 0.
  • The testing guidelines page provides information that helps you to write more effective test cases.

Note: Testing incrementally makes finding bugs easier. Once you finish a function and it is testable, make sure it is working correctly.

Testing Snakes Class

  • Test the alternative constructor for a normal case. It must create a default board.
  • Test the alternative constructor for an error case. That would be a board size which is not a square value.
  • Test the function reStart() and check whether it reinitializes the game.
  • Test the function play(...) for a valid move on a ladder.
  • Test the function play(...) for a valid move on a snake.
  • Test the function makeDefaultBoard(...) for a normal case.
  • Test the function makeRandomBoard(...) for a normal case.
  • Test the function makeRandomBoard(...) for an error case.
  • Test the overloaded assignment operator for a normal case.
  • Test the overloaded assignment operator for an edge case.

Testing For Memory Leaks / Memory Errors

  • Run your test program in valgrind; check that there are no memory leaks or errors.
    Note: If valgrind finds memory errors, compile your code with the -g option to enable debugging support and then re-run valgrind with the -s and --track-origins=yes options. valgrind will show you the line numbers where the errors are detected and can usually tell you which line is causing the error.
  • Never ignore warnings. They are a major source of errors in a program.

What to Submit

You must submit the following files to the proj1 submit directory:

  • snakes.h
  • snakes.cpp
  • mytest.cpp (Note: This file contains the declaration and implementation of your Tester class as well as all your test cases.)

If you followed the instructions in the Project Submission page to set up your directories, you can submit your code using the following command: 

   cp snakes.h snakes.cpp mytest.cpp ~/cs341proj/proj1/

Grading Rubric

The following presents a course rubric. It shows how a submitted project might lose points.

  • Conforming to coding standards make about 10% of the grade.
  • Your test program is worth 50%. If you submit the sample driver program as your test program or no test program is submitted there will be 50% deduction.
  • Correctness and completeness of your test cases (mytest.cpp) make about 15% of the grade.
  • We have written test cases to test your submission without knowing anything about your code. Therefore, it is extremely important that your submission conforms to the specified requirements. Passing tests make about 30% of the grade.
  • There is a 5% deduction for every modification that we need to perform to compile and run your work. For example, if we need to rename your file from myTest.cpp to mytest.cpp the deduction will be applied.

If the submitted project is in a state that receives the deduction for all above items, it will be graded for efforts. The grade will depend on the required efforts to complete such a work.