Instructions
Objective
Write a program to allocate dynamic memory and arrays in C++.
Requirements and Specifications
In this assignment, you will restructure your program to use dynamically allocated memory for the tiles. The Board and AvailableTiles classes will be put in canonical form and the constructors, destructors, and assignment operators will be written to allocate and deallocate the memory as needed. Internally, the game board will be a statically allocated 2D array of pointers (which will be set to point to dynamically allocated tiles) and the list of available tiles will be represented as a linked list. Each linked list element will store the tile cost and a pointer to a dynamically-allocated tile.
Note that the dynamically allocated tiles are always “owned” by the class that creates and deletes them. When a tile is needed elsewhere, it is passed by reference and, if necessary, the client creates a copy for its own use. No tile is ever created by one class and destroyed by another one. This reduces the chance of memory errors, such as memory leaks (caused by forgetting to call delete) and dangling pointers (caused by trying to use something after it was deleted).
The purpose of this assignment is to give you practice with dynamically allocated memory, including linked lists, and with how classes can be used to avoid memory leaks. For Part A, you will change your Board class to use dynamically allocated tiles. For Part B, you will create an encapsulated type to store a linked list element. For Part C, you will refactor your AvailableTiles class to store the tiles and costs in a linked list.
Source Code
AVAILABLE TILES
//
// AvailableTiles.cpp
//
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include "Tile.h"
#include "AvailableTiles.h"
using namespace std;
AvailableTiles :: AvailableTiles ()
{
for(unsigned int i = 0; i < AVAILABLE_TILE_COUNT; i++)
{
setRandomTile(i);
}
}
void AvailableTiles :: print () const
{
cout << "Available tiles:" << endl;
for(unsigned int i = 0; i < AVAILABLE_TILE_COUNT; i++)
{
cout << " " << i << ": ";
tiles[i].print();
cout << " $" << costs[i] << endl;
}
}
int AvailableTiles :: getCost (unsigned int index) const
{
assert(index < AVAILABLE_TILE_COUNT);
return costs[index];
}
const Tile& AvailableTiles :: getTile (unsigned int index) const
{
assert(index < AVAILABLE_TILE_COUNT);
return tiles[index];
}
void AvailableTiles :: replaceAt (unsigned int index)
{
assert(index < AVAILABLE_TILE_COUNT);
// shift tiles in array
for(unsigned int i = index + 1; i < AVAILABLE_TILE_COUNT; i++)
{
assert(i >= 1);
tiles[i - 1] = tiles[i];
costs[i - 1] = costs[i];
}
setRandomTile(AVAILABLE_TILE_COUNT - 1);
}
void AvailableTiles :: setRandomTile (unsigned int index)
{
assert(index < AVAILABLE_TILE_COUNT);
unsigned int chosen = rand() % 5;
if(chosen < 3)
{
unsigned int dice = 1 + rand() % 2;
tiles[index] = Tile(GENUS_DICE, dice);
costs[index] = 5 * dice;
}
else
{
unsigned int points = 1 + rand() % 3;
tiles[index] = Tile(GENUS_POINTS, points);
costs[index] = points * points;
}
}
BOARD
//
// Board.cpp
//
#include <cassert>
#include <cmath>
#include <iostream>
#include "BoardSize.h"
#include "CellId.h"
#include "Tile.h"
#include "Board.h"
using namespace std;
Board :: Board ()
{
for(int r = 0; r < BOARD_SIZE; r++)
{
for(int c = 0; c < BOARD_SIZE; c++)
{
int r2 = abs(r - BOARD_SIZE / 2);
int c2 = abs(c - BOARD_SIZE / 2);
int larger = r2;
if(c2 > r2)
larger = c2;
int money = 4 - larger;
board[r][c] = Tile(GENUS_MONEY, money);
}
}
}
void Board :: print () const
{
printColumnNameRow();
printBorderRow();
for(int r = 0; r < BOARD_SIZE; r++)
{
printEmptyRow();
printDataRow(r);
}
printEmptyRow();
printBorderRow();
printColumnNameRow();
}
const Tile& Board :: getAt (const CellId& cell_id) const
{
assert(isOnBoard(cell_id));
return board[cell_id.row][cell_id.column];
}
void Board :: setAt (const CellId& cell_id,
const Tile& value,
unsigned int owner)
{
assert(isOnBoard(cell_id));
assert(!value.isOwner());
board[cell_id.row][cell_id.column] = value;
board[cell_id.row][cell_id.column].setOwner(owner);
}
void Board :: printColumnNameRow () const
{
cout << " ";
for(int c = 0; c < BOARD_SIZE; c++)
{
char label = getColumnName(c);
cout << " " << label << " ";
}
cout << endl;
}
void Board :: printBorderRow () const
{
cout << " +";
for(int c = 0; c < BOARD_SIZE; c++)
{
cout << "-----";
}
cout << "--+" << endl;
}
void Board :: printEmptyRow () const
{
cout << " |";
for(int c = 0; c < BOARD_SIZE; c++)
{
cout << " ";
}
cout << " |" << endl;
}
void Board :: printDataRow (int row) const
{
assert(row >= 0);
assert(row < BOARD_SIZE);
char label = getRowName(row);
cout << " " << label << " |";
for(int c = 0; c < BOARD_SIZE; c++)
{
cout << " ";
board[row][c].print();
}
cout << " | " << label << endl;
}
CELL CHOOSER
//
// CellChooser.cpp
//
#include <cassert>
#include <iostream>
#include "BoardSize.h"
#include "CellId.h"
#include "Dice.h"
#include "CellChooser.h"
using namespace std;
const unsigned int NOT_IN_LIST = 999999;
const CellId NO_CELL_CHOSEN = toCellId(BOARD_SIZE, BOARD_SIZE);
CellChooser :: CellChooser (int row1_roll,
int row2_roll,
int column1_roll,
int column2_roll,
int extra_roll,
bool is_extra)
{
assert(row1_roll >= 0);
assert(row1_roll < DICE_SIDE_COUNT);
assert(row2_roll >= 0);
assert(row2_roll < DICE_SIDE_COUNT);
assert(column1_roll >= 0);
assert(column1_roll < DICE_SIDE_COUNT);
assert(column2_roll >= 0);
assert(column2_roll < DICE_SIDE_COUNT);
assert(extra_roll >= 0);
assert(extra_roll < DICE_SIDE_COUNT);
calculateAllAvailable(row1_roll, row2_roll,
column1_roll, column2_roll,
extra_roll, is_extra);
//insertionSort();
selectionSort();
assert(available_count >= 1);
if(available_count == 1)
chosen = available_cells[0];
else
chosen = NO_CELL_CHOSEN;
assert(isInvariantTrue());
}
bool CellChooser :: isChosen () const
{
assert(isInvariantTrue());
if(chosen == NO_CELL_CHOSEN)
return false;
else
return true;
}
CellId CellChooser :: getChosen () const
{
assert(isInvariantTrue());
assert(isChosen());
return chosen;
}
void CellChooser :: printAvailable () const
{
assert(isInvariantTrue());
cout << "Available cells:";
for(unsigned int a = 0; a < available_count; a++)
cout << " " << available_cells[a];
cout << endl;
}
bool CellChooser :: isAvailable (const CellId& cell_id) const
{
assert(isInvariantTrue());
//unsigned int index = linearSearch(cell_id);
unsigned int index = binarySearch(cell_id);
if(index != NOT_IN_LIST)
return true;
else
return false;
}
void CellChooser :: chooseAvailable (const CellId& cell_id)
{
assert(isInvariantTrue());
assert(isAvailable(cell_id));
chosen = cell_id;
assert(isInvariantTrue());
}
void CellChooser :: addCellIds (const CellId cells[BOARD_CELL_COUNT],
unsigned int cell_count)
{
assert(isInvariantTrue());
for(unsigned int i = 0; i < cell_count; i++)
addAvailableCell(cells[i]);
//insertionSort();
selectionSort();
assert(isInvariantTrue());
}
void CellChooser :: calculateAllAvailable (int row1_roll,
int row2_roll,
int column1_roll,
int column2_roll,
int extra_roll,
bool is_extra)
{
assert(row1_roll >= 0);
assert(row1_roll < DICE_SIDE_COUNT);
assert(row2_roll >= 0);
assert(row2_roll < DICE_SIDE_COUNT);
assert(column1_roll >= 0);
assert(column1_roll < DICE_SIDE_COUNT);
assert(column2_roll >= 0);
assert(column2_roll < DICE_SIDE_COUNT);
assert(extra_roll >= 0);
assert(extra_roll < DICE_SIDE_COUNT);
available_count = 0;
// always add the cell without the extra die
int row_sum = row1_roll + row2_roll;
int column_sum = column1_roll + column2_roll;
addAvailableCell(toCellId(row_sum, column_sum));
if(is_extra)
{
// if extra die, add up to 4 more cells
// -> substitute the extra die for each other die
int row_sum_r1 = extra_roll + row2_roll;
addAvailableCell(toCellId(row_sum_r1, column_sum));
int row_sum_r2 = row1_roll + extra_roll;
addAvailableCell(toCellId(row_sum_r2, column_sum));
int column_sum_r1 = extra_roll + column2_roll;
addAvailableCell(toCellId(row_sum, column_sum_r1));
int column_sum_r2 = column1_roll + extra_roll;
addAvailableCell(toCellId(row_sum, column_sum_r2));
}
assert(available_count >= 1);
assert(available_count <= BOARD_CELL_COUNT);
}
void CellChooser :: addAvailableCell (const CellId& cell_id)
{
assert(isOnBoard(cell_id));
if(linearSearch(cell_id) == NOT_IN_LIST)
{
available_cells[available_count] = cell_id;
available_count++;
}
}
unsigned int CellChooser :: linearSearch (const CellId& cell_id) const
{
for(unsigned int a = 0; a < available_count; a++)
{
if(cell_id == available_cells[a])
return a;
}
return NOT_IN_LIST;
}
unsigned int CellChooser :: binarySearch (const CellId& cell_id) const
{
unsigned int low = 0; // inclusive
unsigned int high = available_count; // exclusive
while(low < high)
{
unsigned int mid = (low + high) / 2;
if(cell_id == available_cells[mid])
return mid;
else if(cell_id < available_cells[mid])
high = mid;
else
low = mid + 1;
}
return NOT_IN_LIST;
}
void CellChooser :: selectionSort ()
{
assert(available_count <= BOARD_CELL_COUNT);
for(unsigned int a = 0; a < available_count - 1; a++)
{
// find cell next in list
unsigned int best_index = a;
for(unsigned int a2 = a + 1; a2 < available_count; a2++)
{
if(available_cells[a2] < available_cells[best_index])
best_index = a2;
}
// swap cells
CellId temp = available_cells[a];
available_cells[a] = available_cells[best_index];
available_cells[best_index] = temp;
}
}
void CellChooser :: insertionSort ()
{
assert(available_count <= BOARD_CELL_COUNT);
for(unsigned int a = 1; a < available_count; a++)
{
CellId temp = available_cells[a];
// find where to insert
int insert_index = a - 1;
while(insert_index >= 0 && available_cells[a] < available_cells[insert_index])
{
insert_index--;
}
// shift everything over
for(int a2 = a; a2 > insert_index; a2--)
{
assert(a2 >= 1);
available_cells[a2] = available_cells[a2 - 1];
}
// insert value
available_cells[insert_index] = temp;
}
}
bool CellChooser :: isInvariantTrue () const
{
if(available_count < 1)
return false;
if(available_count > BOARD_CELL_COUNT)
return false;
for(unsigned int a = 0; a < available_count; a++)
{
if(!isOnBoard(available_cells[a]))
return false;
}
for(unsigned int a = 0; a < available_count - 1; a++)
{
assert(a + 1 < available_count);
if(!(available_cells[a] < available_cells[a + 1]))
return false;
}
// all checks successful
return true;
}
GAME
//
// Game.cpp
//
#include <cassert>
#include <string>
#include <iostream>
#include "Player.h"
#include "BoardSize.h"
#include "CellId.h"
#include "Tile.h"
#include "Board.h"
#include "AvailableTiles.h"
#include "Dice.h"
#include "CellChooser.h"
#include "Game.h"
using namespace std;
Game :: Game ()
: board(),
available()
{
}
void Game :: printState (unsigned int whose_turn) const
{
assert(whose_turn < playerGetCount());
board.print();
cout << endl;
available.print();
cout << endl;
cout << playerGetName(whose_turn) << "'s turn:" << endl;
cout << endl;
}
void Game :: handleDiceRoll (unsigned int whose_turn)
{
assert(whose_turn < playerGetCount());
bool is_extra_die = false;
if(playerHasDice(whose_turn, 1))
{
is_extra_die = true;
playerDecreaseDice(whose_turn, 1);
}
int row1 = diceRoll();
int row2 = diceRoll();
int column1 = diceRoll();
int column2 = diceRoll();
int extra = diceRoll();
if(is_extra_die)
dicePrint2and2and1(row1, row2, column1, column2, extra);
else
dicePrint2and2(row1, row2, column1, column2);
cout << endl; // blank line
// ask player to choose a cell if needed
CellChooser cell_chooser(row1, row2, column1, column2, extra, is_extra_die);
if(!cell_chooser.isChosen())
{
cell_chooser.printAvailable();
while(!cell_chooser.isChosen())
{
cout << "Choose a cell to roll: ";
string input;
getline(cin, input);
if(isOnBoard(input))
{
CellId chosen = toCellId(input);
if(cell_chooser.isAvailable(chosen))
cell_chooser.chooseAvailable(chosen);
else
cout << " Cell " << chosen << " is not available" << endl;
}
else
cout << " Invalid cell" << endl;
}
}
else
cout << "Rolled cell: " << cell_chooser.getChosen() << endl;
CellId chosen_cell = cell_chooser.getChosen();
assert(isOnBoard(chosen_cell));
Tile tile = board.getAt(chosen_cell);
tile.activate(whose_turn);
}
bool Game :: puchaseTile (unsigned int whose_turn)
{
assert(whose_turn < playerGetCount());
playerPrint(whose_turn);
string input;
cout << "Choose a cell to place a tile: ";
getline(cin, input);
if(input == "q")
return true; // player wants to quit
bool is_discard_tile = true;
if(isOnBoard(input))
{
CellId chosen_cell = toCellId(input);
assert(isOnBoard(chosen_cell));
if(!board.getAt(chosen_cell).isOwner())
{
int tile_index;
cout << "Choose a tile to buy (by index): ";
cin >> tile_index;
cin.clear(); // clean up bad input
getline(cin, input); // read to end of line
if(tile_index >= 0 && tile_index < AVAILABLE_TILE_COUNT)
{
int cost = available.getCost(tile_index);
if(playerHasMoney(whose_turn, cost))
{
board.setAt(chosen_cell, available.getTile(tile_index), whose_turn);
playerDecreaseMoney(whose_turn, cost);
available.replaceAt(tile_index);
is_discard_tile = false;
cout << "Success: Tile added" << endl;
}
else
cout << "Failure: Not enough money" << endl;
}
else
cout << "Failure: Invalid tile" << endl;
}
else
cout << "Failure: Cell already has an owner" << endl;
}
else
cout << "Failure: Invalid cell" << endl;
if(is_discard_tile)
available.replaceAt(0);
return false; // player does not want to quit
}
MAIN
//
// Main.cpp
//
// The main program for Assignment 4.
// For Dr. Hamilton's CS 115 class, 202110 (Winter) term.
//
// Name: ___________________
// Student number: _________
//
#include <cassert>
#include <string>
#include <iostream>
#include "Dice.h"
#include "Player.h"
#include "Game.h"
using namespace std;
const int POINTS_TO_WIN = 5;
int main ()
{
// setup
diceInit();
string player_names[2] = { "Alice", "Bob" };
playerInit(2, player_names);
Game game;
cout << "Welcome to the game." << endl;
// run main loop
unsigned int current_player = 0;
bool is_quit = false;
do
{
cout << endl;
cout << endl;
assert(current_player < playerGetCount());
game.printState(current_player);
game.handleDiceRoll(current_player);
cout << endl;
is_quit = game.puchaseTile(current_player);
current_player++;
if(current_player >= playerGetCount())
current_player = 0;
}
while (!is_quit && !playerHasPointsAnyone(POINTS_TO_WIN));
// print end messages
cout << endl;
cout << endl;
for(unsigned int p = 0; p < playerGetCount(); p++)
{
playerPrint(p);
}
cout << endl;
cout << "Thank you for playing!" << endl;
return 0; // program exited without crashing
}