0

I'm a high school student and, as a homework, i have to develop a console (MS-DOS) version of Minesweeper. For the grid where the game is played, I used a two-dimensional array and I'm stuck on the function which puts the mines (which i represent with -2) in random boxes and determines how many mines are adjacent to every box. This last part is giving me some trouble, because it takes about 2 minutes from start to finish for the "hard" mode of the game (32x18 array with 99 mines). Here is the function I have written:

void InsMine(int mat[32][18]){
int i, r, c, j, k, contatore;
for(i=0;i<n_mine;i++){
    do{
        srand(time(NULL));
        r=minimo + rand() % massimo-1;
        c=minimo + rand() % massimo_c-1;
    }
    while(mat[r][c]==-2||mat[r][c]==-1);
    mat[r][c]=-2;
}

for(j=1;j<=massimo;j++){ //for che scorre la matrice (colonne)
    for(k=1;k<=massimo_c;k++){ //for che scorre la matrice (righe)
        contatore=0;
        if(mat[j][k]!=-2){
            if(mat[j-1][k]==-2){
                contatore++;
            }
            if(mat[j-1][k+1]==-2){
                contatore++;
            }
            if(mat[j][k+1]==-2){
                contatore++;
            }
            if(mat[j+1][k+1]==-2){
                contatore++;
            }
            if(mat[j+1][k]==-2){
                contatore++;
            }
            if(mat[j+1][k-1]==-2){
                contatore++;
            }
            if(mat[j+1][k-1]==-2){
                contatore++;
            }
            if(mat[j-1][k-1]==-2){
                contatore++;
            }
            mat[j][k]=contatore;
        }
    }
}

}

The first for places the mines in random squares, while the second for determines how many mines are adjacent to a given box and saves the value in that box. The code is written in Italian, so here's a little translation: "massimo" means maximum, "minimo" is minimum and "contatore" is counter and I use it to count how many mines are adjacent to a given square. If you could help me to understand how to optimize better this part I'd be very grateful, as I really can't wrap my head around it.

Here is every piece of code I've written so far:

#include <iostream>
#include <stdlib.h>
#include <conio.h>
#include <time.h>

using namespace std;
int righe_mat, colonne_mat, n_mine, minimo, massimo, massimo_c;

void InsMine(int mat[32][18]);
void RiempiMat(int mat[32][18]);
void StampaMat(int mat[32][18]);


int main()
{
    int scelta;
    int PosNum[32][18], Scoperte[32][18];
    do{ //scelta difficoltà da parte dell'utente
        cout << "Scegliere il livello di difficolta' (1=facile, 2=medio, 3=difficile): ";
        cin >> scelta;

        switch(scelta){ //modifica variabili globali in base alla difficoltà scelta
        case 1:
            righe_mat=11;
            colonne_mat=11;
            n_mine=10;
            minimo=1;
            massimo=9;
            massimo_c=9;
            break;
        case 2:
            righe_mat=18;
            colonne_mat=18;
            n_mine=40;
            minimo=1;
            massimo=16;
            massimo_c=16;
            break;
        case 3:
            righe_mat=32;
            colonne_mat=18;
            n_mine=99;
            minimo=1;
            massimo=30;
            massimo_c=16;
            break;
        default:
            cout << "Scelta non valida, ripetere selezione" << endl;
        }
    }
    while(scelta!=1&&scelta!=2&&scelta!=3);

    RiempiMat(PosNum);
    RiempiMat(Scoperte);
    InsMine(PosNum);
    cout << endl << endl;
    StampaMat(PosNum);
}

void RiempiMat(int mat[32][18]){
    int i, j, k, o, m, n;
    for(i=0;i<colonne_mat;i++){
        mat[0][i]=-1;
    }
    for(j=0;j<colonne_mat;j++){
        mat[righe_mat-1][j]=-1;
    }
    for(k=0;k<righe_mat;k++){
        mat[k][0]=-1;
    }
    for(o=0;o<righe_mat;o++){
        mat[o][colonne_mat-1]=-1;
    }

    for(m=1;m<colonne_mat-1;m++){
        for(n=1;n<righe_mat-1;n++){
            mat[n][m]=0;
        }
    }
}

void InsMine(int mat[32][18]){
    int i, r, c, j, k, contatore;
    for(i=0;i<n_mine;i++){
        do{
            srand(time(NULL));
            r=minimo + rand() % massimo-1;
            c=minimo + rand() % massimo_c-1;
        }
        while(mat[r][c]==-2||mat[r][c]==-1);
        mat[r][c]=-2;
    }

    for(j=1;j<=massimo;j++){ //for che scorre la matrice (colonne)
        for(k=1;k<=massimo_c;k++){ //for che scorre la matrice (righe)
            contatore=0;
            if(mat[j][k]!=-2){
                if(mat[j-1][k]==-2){
                    contatore++;
                }
                if(mat[j-1][k+1]==-2){
                    contatore++;
                }
                if(mat[j][k+1]==-2){
                    contatore++;
                }
                if(mat[j+1][k+1]==-2){
                    contatore++;
                }
                if(mat[j+1][k]==-2){
                    contatore++;
                }
                if(mat[j+1][k-1]==-2){
                    contatore++;
                }
                if(mat[j+1][k-1]==-2){
                    contatore++;
                }
                if(mat[j-1][k-1]==-2){
                    contatore++;
                }
                mat[j][k]=contatore;
            }
        }
    }
}

void StampaMat(int mat[32][18]){
    int i, j;
    for(i=0;i<colonne_mat;i++){
        for(j=0;j<righe_mat;j++){
            cout << mat[j][i] << " |";
        }
        cout << endl;
    }
    cout << endl << endl << endl;
}

The cout in main is basically asking to choose the difficulty of the game (1=easy, 9x9 array and 10 mines, 2=medium, 18x18 array and 40 mines, 3=hard, 32x18 array and 99 mines). I use the switch to set the value of some global variables: righe_mat and colonne_mat represent the size of the array (x;y), n_mine represents the number of mines and massimo and minimo are used to set the range in which the mines can be placed. The function RiempiMat() fills both the arrays (1 used to save where the mines are and how many of them are adjacent to each box and 1 used to save which square the user sees and which the user doesn't see yet) with 0s and -1s (the border) and StampaMat() just prints both the arrays.

I apologise for my English, as I'm Italian and English is not my first language. Thanks in advance for the kind help, Matteo

Boss
  • 1
  • 1
  • 2
    Unrelated: You only want to call `srand(time(NULL));` once, somewhere near the beginning of `main`. Every time you call, `srand`, it restarts the random number generator and if you call it quickly enough to get inside the resolution of `time`, usually one second, you'll get the same number sequence. Kinda ruins the whole random experience. If you find a case where you really do need to call `srand` more than once, you're probably in a problem space where `rand` just isn't good enough and you should consider using the `` library facilities. – user4581301 Apr 21 '21 at 19:21
  • Your development software may have a profiling tool tat can tell you what part of your code is soaking up all of the time. Learning to use and then using the tools that came with the compiler, particularly the debugging tools, often make the difference between those who have time to do well in the class and those who don't. And if you become a professional programmer, using all of the tools is pretty much a must if you want to be productive and well paid. – user4581301 Apr 21 '21 at 19:26
  • 1
    I made minesweeper once, and I realized that there are much more fields than bombs. So I decided to increase the counter of the surrounding fields for every bomb I generated, instead of looping over the entire field counting the bombs around every field. I doubt this is your main issue, but it may help. – Emanuel P Apr 21 '21 at 19:32
  • 4
    Directly addressing your problem, as the matrix fills up , it's harder and harder to find places to put mines, so the program will spin around a lot looking for an empty spot. The common solution for a problem like this is the [Fisher-Yates Shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). Basically you make the grid, you place the right number of mines right at the beginning (or end, it doesn't matter) and then shuffle the grid so the location of the mines is randomized. – user4581301 Apr 21 '21 at 19:32
  • Fisher-yates is implemented in C++ with the [`std::shuffle`](https://en.cppreference.com/w/cpp/algorithm/random_shuffle) function. Note that it only works on a 1D array, but what is a M by N 2D array other than a MxN 1D array with extra rules saying there's a new row every N spaces? – user4581301 Apr 21 '21 at 19:35
  • Thinking back to the comment about the profiling tool, you can do some poor-man's profiling with the debugger that comes with your tools. If you run the program in the debugger and wait for it to look like it's locked up , you can tell the debugger to pause and look at where the program stopped. Odds are really good it'll be inside the loop that's eating up all of the time. You can then step through the loop a few times and see why it is not proceeding as quickly as you like. – user4581301 Apr 21 '21 at 19:38
  • thanks a lot guys, will try out your solutions! – Boss Apr 21 '21 at 19:40
  • 1
    @user4581301 Re: `Unrelated: You only want to call srand(time(NULL));` - this is actually VERY MUCH related, as the first loop would spin untill `time(NULL)` changes, 99 times! – Vlad Feinstein Apr 21 '21 at 19:44
  • I refrained from answering because [here](https://stackoverflow.com/questions/7343833/srand-why-call-it-only-once) you could already find an explanation on why `srand` is misplaced there. In particular, note the point where they discuss calling the combo srand/rand multiple times in the same second. – Bob__ Apr 21 '21 at 19:45
  • hey guys, just wanted to let you know that the problem was the srand in the do while, as suggested by @user4581301. The execution time jumper down from 145 seconds to just 5! Thanks a lot for your suggestions, you really helped me out and I wouldn't have been able to finish my project in time without your help – Boss Apr 21 '21 at 19:52
  • OK, so there were two problems and I flagged, but dismissed, the first problem in favour of the second. Will close as a dupe. – user4581301 Apr 21 '21 at 20:04

0 Answers0