1
\$\begingroup\$

I have implemented minesweeper in C++. You can get a box by entering the coordinates -row number, then column; starting from 0- of said box (eg: "0 0"); you can mark a box as a bomb by adding the prefix "mark" (eg: "mark 0 0"); you can unflag a box by adding the prefix "unmark" (eg: "unmark 0 0"). The game ends when all non-bomb boxes have been checked & all bombs have been marked. Any feedback/ideas on how to improve my code would be very much appreciated.

main.cpp

#include "Game.h"

int main()
{
    Game* g = new Game(16, 40);
    g->playGame();
    return 0;
}

Game.h

#ifndef GAME_H
#define GAME_H

#include "Grid.h"

#include <string>

class Game
{
    private:
        Grid* grid;
        int** closedSet;
        int len;
        int foundNum, closedSetSize;

    public:
        Game(int n, int b);
        ~Game();
        void printClosedSet();
        void playGame();

    private:
        void clearSpace(int n, int m);
};

#endif // GAME_H

Game.cpp

#include "Game.h"

#include <queue>
#include <cstddef>
#include <iomanip>
#include <cstring>
#include <iostream>

Game::Game(int n, int b) : foundNum(0), closedSetSize(0) {
    grid = new Grid(n, b);

    len = grid->getSize();
    closedSet = new int*[len];
    for(int i = 0; i < len; i++) {
        closedSet[i] = new int[len];
        std::memset(closedSet[i], 0, len * sizeof(int));
    }
}

Game::~Game() {
    delete grid;
    for(int i = 0; i < len; i++)
        delete[] closedSet[i];
    delete[] closedSet;
}

void Game::printClosedSet() {
    std::cout << "    ";
    for(int i = 0; i < len; i++) {
        std::cout << std::setw(3) << i;
    }
    std::cout << std::endl;
    std::cout << "    ";
    for(int i = 0; i < len; i++) {
        std::cout << "---";
    }
    std::cout << std::endl;
    for(int i = 0; i < len; i++) {
        std::cout << std::setw(3) << i << "|";
        for(int j = 0; j < len; j++) {
            if(closedSet[i][j] == 1) {
                std::cout << std::setw(3) << grid->getNum(i, j);
            } else if(closedSet[i][j] == 0) {
                std::cout << std::setw(3) << "-";
            } else std::cout << std::setw(3) << "*";
        }
        std::cout << std::endl;
    }
}

void Game::playGame() {
    std::string s;
    int n, m;
    while(true) {
        printClosedSet();
        std::cin >> s;
        if((s.find_first_not_of("0123456789") == std::string::npos) && ((std::stoi(s) <= len-1) && (std::stoi(s) >= 0)))  {
            n = std::stoi(s);
            s = "placeholder";
            while(s.find_first_not_of("0123456789") != std::string::npos) {
                std::cin >> s;
                if((s.find_first_not_of("0123456789") == std::string::npos) &&
                   ((std::stoi(s) > len-1) || (std::stoi(s) < 0))) s = "placeholder";
            }
            m = std::stoi(s);
            if(closedSet[n][m] == 0) {
                if(grid->getNum(n, m) < 0) {
                    grid->printBombs(closedSet);
                    std::cout << "YOU HAVE LOST" << std::endl;
                    break;
                }
                clearSpace(n, m);
            }
        } else if (s == "mark" || s == "unmark"){
            std::string temp = "placeholder";
            while(temp.find_first_not_of("0123456789") != std::string::npos) {
                std::cin >> temp;
                if((temp.find_first_not_of("0123456789") == std::string::npos) &&
                   (std::stoi(temp) > len-1)) temp = "placeholder";
            }
            n = std::stoi(temp);
            temp = "placeholder";
            while(temp.find_first_not_of("0123456789") != std::string::npos) {
                std::cin >> temp;
                if((temp.find_first_not_of("0123456789") == std::string::npos) &&
                   (std::stoi(temp) > len-1)) temp = "placeholder";
            }
            m = std::stoi(temp);
            if((s == "mark") && (closedSet[n][m] == 0)) {
                closedSet[n][m] = 3;
                if(grid->getNum(n, m) < 0) ++foundNum;
            } else if((s == "unmark") && (closedSet[n][m] == 3)) {
                closedSet[n][m] = 0;
                if(grid->getNum(n, m) < 0) --foundNum;
            }
        } else continue;
        if((grid->getBombNum() == foundNum) && (closedSetSize == len*len - grid->getBombNum())) {
            printClosedSet();
            std::cout << "YOU HAVE WON" << std::endl;
            break;
        }
    }
    grid->clearGrid();
    grid->generateGrid();
    for(int i = 0; i < len; i++)
        std::memset(closedSet[i], 0, len * sizeof(int));
    foundNum = 0;
    closedSetSize = 0;
}

void Game::clearSpace(int n, int m) {
    std::queue<std::pair<int, int>> q;
    if(closedSet[n][m] == 0) ++closedSetSize;
    closedSet[n][m] = 1;
    if(grid->getNum(n, m) == 0) q.push(std::make_pair(n, m));
    while(!q.empty()) {
        n = q.front().first;
        m = q.front().second;
        closedSet[n][m] = 1;
        if((n < len-1) && (closedSet[n+1][m] == 0)) {
            if(grid->getNum(n+1, m) == 0)
                q.push(std::make_pair(n+1, m));
            closedSet[n+1][m] = 1;
            ++closedSetSize;
        }

        if((n < len-1) && (m < len-1) && (closedSet[n+1][m+1] == 0)) {
            if(grid->getNum(n+1, m+1) == 0)
                q.push(std::make_pair(n+1, m+1));
            closedSet[n+1][m+1] = 1;
            ++closedSetSize;
        }

        if((n < len-1) && (m > 0)  && (closedSet[n+1][m-1] == 0)) {
            if(grid->getNum(n+1, m-1) == 0)
                q.push(std::make_pair(n+1, m-1));
            closedSet[n+1][m-1] = 1;
            ++closedSetSize;
        }

        if((m < len-1) && (closedSet[n][m+1] == 0)) {
            if(grid->getNum(n, m+1) == 0)
                q.push(std::make_pair(n, m+1));
            closedSet[n][m+1] = 1;
            ++closedSetSize;
        }

        if((n > 0) && (closedSet[n-1][m] == 0)) {
            if(grid->getNum(n-1, m) == 0)
                q.push(std::make_pair(n-1, m));
            closedSet[n-1][m] = 1;
            ++closedSetSize;
        }

        if((n > 0) && (m < len-1) && (closedSet[n-1][m+1] == 0)) {
            if(grid->getNum(n-1, m+1) == 0)
                q.push(std::make_pair(n-1, m+1));
            closedSet[n-1][m+1] = 1;
            ++closedSetSize;
        }

        if((n > 0) && (m > 0)  && (closedSet[n-1][m-1] == 0)) {
            if(grid->getNum(n-1, m-1) == 0)
                q.push(std::make_pair(n-1, m-1));
            closedSet[n-1][m-1] = 1;
            ++closedSetSize;
        }

        if((m > 0)  && (closedSet[n][m-1] == 0)) {
            if(grid->getNum(n, m-1) == 0)
                q.push(std::make_pair(n, m-1));
            closedSet[n][m-1] = 1;
            ++closedSetSize;
        }
        q.pop();
    }
}

Grid.h

#ifndef GRID_H
#define GRID_H

#include <vector>

class Grid
{
    private:
        int** grid;
        int len;
        int bombNum;
        std::vector<std::pair<int, int>> s;

    public:
        Grid(int n, int b);
        ~Grid();
        void printBombs(int** closedSet);
        void generateGrid();
        void clearGrid();
        int getNum(int n, int m) {return grid[n][m];}
        int getSize() {return len;}
        int getBombNum() {return bombNum;}
};

#endif // GRID_H

Grid.cpp

#include "Grid.h"

#include <iostream>
#include <cstring>
#include <algorithm>
#include <chrono>
#include <random>
#include <iomanip>

Grid::Grid(int n, int b) : len(n), bombNum(b) {
    grid = new int*[len];

    s.reserve(len);

    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len; j++)
            s.push_back(std::make_pair(i, j));
        grid[i] = new int[len];
        std::memset(grid[i], 0, len * sizeof(int));
    }
    generateGrid();
}

Grid::~Grid() {
    for(int i = 0; i < len; i++)
        delete[] grid[i];
    delete[] grid;
}

void Grid::printBombs(int** closedSet) {
    std::cout << "    ";
    for(int i = 0; i < len; i++) {
        std::cout << std::setw(3) << i;
    }
    std::cout << std::endl;
    std::cout << "    ";
    for(int i = 0; i < len; i++) {
        std::cout << "---";
    }
    std::cout << std::endl;
    for(int i = 0; i < len; i++) {
        std::cout << std::setw(3) << i << "|";
        for(int j = 0; j < len; j++) {
            if(grid[i][j] < 0) {
                std::cout << std::setw(3) << "X";
            } else if(closedSet[i][j] == 1) {
                std::cout << std::setw(3) << grid[i][j];
            } else std::cout << std::setw(3) << "-";
        }
        std::cout << std::endl;
    }
}

void Grid::generateGrid() {
    shuffle(s.begin(),
        s.end(),
        std::default_random_engine(std::chrono::system_clock::now().time_since_epoch().count()));

    for(int i = 0; i < bombNum; i++) {
        int randRow = s[i].first;
        int randCol = s[i].second;
        grid[randRow][randCol] = -1;
        if(randRow > 0) {
            if(grid[randRow-1][randCol] >= 0)
                ++grid[randRow-1][randCol];

            if((randCol > 0) && (grid[randRow-1][randCol-1] >= 0))
                ++grid[randRow-1][randCol-1];

            if((randCol < len-1) && (grid[randRow-1][randCol+1] >= 0))
                ++grid[randRow-1][randCol+1];
        }
        if(randRow < len-1) {
            if(grid[randRow+1][randCol] >= 0)
                ++grid[randRow+1][randCol];

            if((randCol > 0) && (grid[randRow+1][randCol-1] >= 0))
                ++grid[randRow+1][randCol-1];

            if((randCol < len-1) && (grid[randRow+1][randCol+1] >= 0))
                ++grid[randRow+1][randCol+1];
        }
        if((randCol > 0) && (grid[randRow][randCol-1] >= 0))
            ++grid[randRow][randCol-1];

        if((randCol < len-1) && (grid[randRow][randCol+1] >= 0))
            ++grid[randRow][randCol+1];
    }
}

void Grid::clearGrid() {
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len; j++)
            grid[i][j] = 0;
    }
}
\$\endgroup\$
0

2 Answers 2

3
\$\begingroup\$

Unnecessary memory allocations

You are using new and delete in many places where it is not necessary to do any memory allocations. Starting in main(), you can just write:

Game g(16, 40);
g.playGame();

Apart from slightly less typing, this also prevents the inevitable memory leak when you forget to delete what you just allocated.

The same goes for Game::grid, this doesn't have to be a pointer, it can be a regular member variable of Game.

Let STL containers manage memory for you

In those cases where you do need to allocate memory, try to avoid using manual new and delete. In particular, for arrays of which you don't know the size up front, you can use std::vector. It will automatically allocate and deallocate memory for you. If you have a two-dimensional array, you could make a vector of vectors, like so:

class Grid
{
    std::vector<std::vector<int>> grid;
    ...
};

Grid::Grid(int n, int b): grid(n, std::vector<int>(n)), ... {
    ...
}

However, that brings me to the following:

Allocate a single array/vector for all elements of a 2D grid

Vectors of vectors, or dynamically allocated arrays of dynamically allocated arrays as you did in your code, are not efficient. To get to a certain element, the CPU would have to follow two pointers, which is inefficient. However, CPUs nowadays are great at multiplications and additions, so it is actually faster to allocate a 1D vector, and calculate yourself how to position 2D elements in it. For example:

class Grid
{
    std::vector<int> grid;
};
...
Grid::Grid(int n, int b): grid(n * n), ... {
    ...
}
...
void Grid::printBombs(...) {
    ...
    if (grid[i * len + j] < 0)
       ...
}

To avoid having to write that formula all the time, consider making a member function that takes the row and column position, and returns a reference to the desired grid element:

int& Grid::gridAt(int row, int col) {
    return grid[row * len + col];
}

Then you can just write:

if (gridAt(i, j) < 0)
    ...

Once you have a one-dimensional vector, some other things become easier as well. For example,

Make use of STL algorithms

If you use STL containers, STL algorithms can now be used as well. For example, to clear the grid you can use [std::fill()][3]:

void Grid::clearGrid() {
    std::fill(grid.begin(), grid.end(), 0);
}

Think of std::fill() and std::fill_n() as C++'s version of C's memset(), and there's std::copy() and std::copy_n to replace memcpy(), but the algorithms can do much more than that, saving you the trouble of having to implement them yourself. To get more familiar with them, I recommend you read or watch The World Map of C++ STL Algorithms.

Simplify parsing the input

Parsing the input is a bit complicated in your code, mainly because you either allow coordinates without any prefix, or coordinates with a prefix to be entered. Because you can't be sure if the first thing you read is going to be a number or a prefix, you have to read it as a std::string, check what it is, then use std::stoi() to convert it to a number if necessary. If you would change the way you read the input such that you always have to prefix the coordinates, and use the prefix "reveal" or "get" to reveal what is on a given grid position, you can greatly simplify parsing the input:

while (true) {
    printClosedSet();

    std::string command;
    int row;
    int col;

    std::cin >> command >> row >> col;

    if (command == "reveal") {
        ...
    }
    ...
}

Consider using emplace() instead of push() where possible

Many containers have both push() and emplace() functions. The latter is sometimes more efficient and convenient. In particular, it reserves room for the new element and constructs it in place, and the arguments to emplace() are passed to the constructor of the value type of the container. This allows you to write:

std::queue<std::pair<int, int>> q;
...
q.emplace(n, m);

Note how you no longer need to use std::make_pair().

Create a struct Cell

You are actually keeping track of the state of each location on the board using two grids; one is grid and the other closedSet. It's also not so nice to overload ints to mean different things. Consider creating a struct Cell that holds all information of a grid cell:

struct Cell {
    int adjacentBombs;
    bool bomb;
    bool revealed;
    bool marked;
};

The you just need one datastructure to hold all information about the board:

std::vector<Cell> grid;

Prefer '\n' instead of std::endl

Prefer using '\n' instead of std::endl; the latter is equivalent to the former, but also forces the output to be flushed, which is usually not necessary and has performance implications.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ sizeof(Cell) could be reduced easily, typically by half: Though char is overkill to count to 8. Bitfields would reduce to a single byte, but the more costly access probably makes it a net-negative. \$\endgroup\$ May 22 at 15:32
3
\$\begingroup\$
  • Separate IO from business logic. From the game point of view it doesn't matter how the user asks to perform the action. With CLI it is "X Y", or "mark X Y", or wharever; with GUI it could be Click, Shift-Click, etc. The game doesn't care. What matters is the action to be performed.

  • generateGrid seems buggy. Once the bomb is planted (that is, assigned -1) all the neighboring cells are incremented. If a bomb was already planted there, the cell's value is not -1 anymore. Its bomb just disappears.

  • playGame regenerates the grid after the game is finished. It doesn't feel right.

  • The wall of ifs in clearSpace shall be a loop over the neighboring cells.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.