Calcolatori Elettronici - Prova di Laboratorio

15 febbraio 2022
Si vuole realizzare una variante interattiva del gioco campo minato. In questo gioco, il giocatore deve liberare
un campo di dimensione 10x10 celle da un certo numero di mine nascoste. Il campo viene inizializzato in
maniera casuale all’avvio del gioco: in particolare, vengono inserite nel campo un numero casuale di mine tra 3
e 10 (estremi inclusi).

Il gioco è organizzato in turni. In ciascun turno, il giocatore può compiere un’azione tra le seguenti:

1. Scopri cella: una cella viene scoperta per rivelarne il contenuto.

2. Pianta bandierina: una cella in cui il giocatore sospetta ci sia una mina viene marcata con una “bandiera”.
3. Rimuovi bandiera: viene rimossa, se presente, la bandiera da una cella.

Nel momento in cui viene scoperta una cella, si verificano due casi:

1. Se la cella scoperta contiene una mina, questa esplode ed il giocatore perde la partita.

2. Se la cella cliccata non contiene una mina, si verificano due sottocasi aggiuntivi:

1. Se non appare alcun numero, significa che tutti gli otto quadrati adiacenti non contengono una
mina
2. Se appare un numero compreso tra 1 e 8, questo indica la quantità di celle adiacenti (incluse quelle
in diagonale) che contengono mine.

Quando tutte le celle, escluse quelle contenenti mine, sono state scoperte, il giocatore vince la partita.

Lo studente è libero di rappresentare in memoria il campo di gioco utilizzando una qualsiasi struttura dati.
Similmente, lo studente è libero di scegliere come acquisire dall’utente i comandi per determinare le azioni di
gioco e come mostrare lo stato di gioco.

Soluzione
Di seguito si presenta una possibile soluzione. Altre scelte implementative sono possibili ed ugualmente valide.

Il problema può essere scomposto in tre parti separate: l'inizializzazione del campo di gioco ed il gioco vero e
proprio che si alterna in fasi di stampa dello stato di gioco e di input da tastiera. La funzione main() per gestire
quindi la vita del programma può essere implementata come segue. Avendo la necessità di generare un numero
di mine casuale in posizioni casuali, sarà necessario utilizzare un generatore di numeri pseudocasuali che deve
essere inizializzato. Si effettua l'inizializzazione con la classica chiamata a srand() . Si configura poi la partita e
si dà il controllo ad un main loop che implementerà le due fasi successive. Questa funzione di main loop
restituirà true o false a seconda che il giocatore abbia sminato correttamente il campo o sia esploso
calpestando una mina.

1 int main(void)
2 {
3 // Initialize the pseudo-random number generator
4 srand(time(NULL));
5
6 // Configure and start the game
7 init_field();
8 if(game_loop()) {
9 puts("YOU WON!");
10 } else {
11 puts("GAME OVER");
12 }
13
 14 return 0;
15 }
16

Il gioco è a turni, quindi è necessario prevedere delle azioni di gioco. In altri termini, è possibile definire
un'enumerazione che identifichi qual è l'insieme di azioni possibili, come segue:

1 // Definition of possible game actions

2 enum actions {
3 MARK_MINE, UNMARK_MINE, UNCOVER
4 };

Un altro aspetto importante è quello di rappresentare lo stato corrente della partita. Il campo da gioco è una
matrice 10x10 in cui ciascuna cella deve mantenere alcune informazioni di stato, in particolare le informazioni
minimali sono:

se è presente una mina;

se il giocatore ha scoperto la cella;
se il giocatore ha inserito una bandierina per marcare la cella come possibile mina.

Poiché quando si mostra la mappa di gioco è necessario mostrare anche il numero di celle vicine che hanno una
mina (con un massimo di 8), in questo caso le possibilità sono due: o si calcola questo numero ogni volta che si
stampa la mappa, oppure si precalcola questo valore e lo si memorizza nello stato di gioco di ciascuna cella. Per
motivi di efficienza e di semplicità di scrittura di codice, in questa soluzione si è optato per la seconda strategia.

Lo stato di gioco può anche contenere alcune informazioni aggiuntive, ovverosia: quante sono le mine totali
presenti nella partita corrente e quante celle sono state scoperte fino ad un certo punto (quest'ultima
informazione non è necessaria, ma consente di semplificare il codice per andare a verificare quando un
giocatore ha vinto o meno).

Poiché lo stato di gioco è uno solo per ciascuna esecuzione del programma (il programma deve implementare
una singola partita), è possibile rappresentarlo in una variabile globale inizializzata a zero a tempo di
compilazione, come segue.

1 // The state of the game: it's a matrix keeping the state of each cell, plus a couple of
2 // global variables that describe what happened so far in the program.
3 struct game_state_t {
4 struct cell_state_t {
5 unsigned char has_mine : 1;
6 unsigned char is_uncovered : 1;
7 unsigned char is_marked : 1;
8 unsigned char neighbours : 4; // The number of neighbours with mines (max is 8!)
9 } map[MAP_SIZE][MAP_SIZE];
10 unsigned char tot_num_mines;
11 unsigned char tot_uncovered_cells;
12 } game_state = {0};

Occorre poi capire come generare numeri pseudocasuali in un intervallo definito. L'esercizio chiede di avere un
numero di mine compreso in , mentre le mine vanno posizionate lungo gli assi ed nell'intervallo .
Si può utilizzare una sola funzione parametrica per generare tutti i numeri casuali necessari per il gioco, come
segue.

1 // This function returns a random value in [0, 10)

2 static int random_int(void)
3 {
4 int ret = (int) ((double) MAP_SIZE * rand() / RAND_MAX);
5 if(ret == MAP_SIZE)
6 ret--;
7 return ret;
8 }
Fatte queste scelte, si può realizzare la funzione che inizializza una partita. Questa funzione dovrà:

1. calcolare quante mine occorre inserire sul campo in questa partita, assicurandosi che ce ne siano almeno 3
( MAX_NUM_MINES nel codice);
2. determinare le posizioni casuali delle mine, assicurandosi che una stessa cella non riceva più di una mina;
3. precalcolare il numero di mine nelle celle adiacenti di ciascuna cella.

Per i punti 1 e 2 si può utilizzare la funzione random_int() definita precedentemente. Il punto 3 richiede
un'attenzione maggiore, per catturare correttamente le celle che si trovano sul bordo. Consideriamo infatti la
seguente porzione del campo di gioco:

se vogliamo analizzare i vicini della cella , questi sono effettivamente otto. Viceversa, se vogliamo
analizzare i vicini di , ci accorgiamo che non dobbiamo considerare quelli "a sinistra", poiché la cella si
trova sul bordo della mappa. Se poi consideriamo la cella , questa avrà soltanto tre vicini, poiché si trova
sullo spigolo.

Verificare tutte le possibilità è lungo e può essere soggetto ad errori. Possiamo però notare due aspetti che ci
aiutano a semplificare il problema. In tutti i casi, determinare i vicini di una cella significa andare ad
osservare lo stato delle celle che si trovano a , con e (questo approccio
"semplificato" considera anche i casi e che sono la stessa cella , ma non crea problemi di
correttezza).

Verificare se un "vicino calcolato" esiste o meno significa verificare se questo è fuori dalla mappa. Questa
situazione si verifica in quattro casi:

1. se MAP_SIZE ;
2. se MAP_SIZE ;
3. se ;
4. se .

In realtà i due ultimi casi possono essere accorpati ai primi due ricordandosi che, utilizzando un tipo di dato
unsigned , se si associa alla variabile un numero negativo, questo (a causa di overflow) verrà interpretato come
un numero positivo molto grande, sicuramente maggiore di MAP_SIZE .

Si può quindi implementare l'inizializzazione come segue. Si notino le linee che implementano la
precomputazione sui vicini utilizzando lo schema descritto qui sopra.

1 static void init_field(void)

2 {
3 // Get random number of mines
4 game_state.tot_num_mines = random_int(3, 10);
5
6 // Place the mines
7 for(unsigned short i = 0; i < game_state.tot_num_mines; i++) {
8 unsigned short x, y;
9
10 retry:
11 x = random_int(0, 9);
12 y = random_int(0, 9);
13
14 // If we picked a cell which has already a mine, we have to retry
15 if(game_state.map[x][y].has_mine)
16 goto retry;
17
18 game_state.map[x][y].has_mine = true;
 19 }
20
21 // Precompute the number of mines in adjacent cells to show hints
22 for(unsigned short x = 0; x < MAP_SIZE; x++) {
23 for(unsigned short y = 0; y < MAP_SIZE; y++) {
24 unsigned short mines = 0;
25 if(game_state.map[x][y].has_mine) // Don't consider cells with mines
26 continue;
27
28 // We should offset [-1,+1] from current coordinates both along x and y.
29 // BUT we must check if we get out of bounds of the map!
30 for(short i = -1; i <= 1; i++) {
31 for(short j = -1; j <= 1; j++) {
32 if((unsigned short)(x + i) < MAP_SIZE && (unsigned short)(y + j) < MAP_SIZE)
33 mines += game_state.map[x + i][y + j].has_mine == true;
34 }
35 }
36
37 assert(mines <= 8); // We cannot have more than 8 neighbours with mines!
38 game_state.map[x][y].neighbours = mines;
39 }
40 }
41 }

Un altro aspetto importante è la lettura dell'input. L'esercizio lasciava piena libertà su come acquisire l'input
associato alle varie azioni, pertanto è assolutamente lecito fare più di una domanda al giocatore (ad esempio,
per sapere cosa vuole fare e qual è la cella coinvolta). Nella soluzione qui proposta si utilizza una sorta di parser
che cerca di estrarre coordinate e comando in un unico input di tre caratteri. Viene comunque effettuata una
lettura di una riga completa da stdin un carattere alla volta e si effettuano poi alcuni controlli per determinare
se il comando è ben formato (ad esempio, se si inseriscono più di tre caratteri, il comando non viene
considerato corretto). Si noti che la funzione restituisce una delle azioni precedentemente definite in enum

actions che verranno successivamente "consumate" dal game loop.

1 enum actions get_input(unsigned short *x, unsigned short *y)

2 {
3 bool valid;
4 enum actions ret = UNCOVER;
5 int c;
6 unsigned char command[3];
7
8 puts("Accepted commands:");
9 puts(" - xyM: mark a cell as a mine.");
10 puts(" - xym: unmark a cell as a mine.");
11 puts(" - xy: uncover a cell as a mine.\n");
12
13 do {
14 unsigned short i = 0;
15 command[0] = command[1] = command[2] = '\0';
16 printf("What shall I do? ");
17 fflush(stdout);
18
19 do {
20 if((c = getchar()) == EOF) {
21 printf("\nQuitting...\n");
22 exit(EXIT_FAILURE);
23 }
24 if(i < 3)
25 command[i] = c;
26 i++;
27 } while(c != '\n');
28
29 // Ignore case for row letter
30 command[0] = tolower(command[0]);
31
32 // Check the input. Note that since we use UNSIGNED chars in checks, checking for greater
33 // values of characters implicitly checks for lower values, thanks to negative overflow
34 if(i > 4 // Too many characters
35 || (i == 4 && (tolower(command[2]) != 'm' && command[2] != '\n')) // last letter can
only be m/M
36 || (unsigned char)(command[0] - 'a') >= MAP_SIZE // row out of bounds
 37 || (unsigned char)(command[1] - '0') >= MAP_SIZE) { // col out of bounds
38 valid = false;
39 } else {
40 valid = true;
41 }
42 } while(!valid);
43
44 // Prepare return values
45 if(command[2] == 'm')
46 ret = UNMARK_MINE;
47 if(command[2] == 'M')
48 ret = MARK_MINE;
49 *x = command[0] - 'a';
50 *y = command[1] - '0';
51
52 return ret;
53 }

Di seguito viene riportata una possibile implementazione della funzione che consente di stampare la mappa a
schermo. Questa funzione si limita a "disegnare" con caratteri ASCII una tabella 10x10, andando a selezionare
come carattere da mostrare al centro di ciascuna cella della tabella un carattere diverso a seconda dello stato di
ciascuna cella nella variabile globale game_state .

1 static void print_map(void)

2 {
3 clrscr();
4 printf(" ** MINE SWEEPER **\n\n ");
5 for(unsigned short j = 0; j < MAP_SIZE; j++)
6 printf(" %d", j);
7 puts("");
8 for(unsigned short x = 0; x < MAP_SIZE; x++) {
9 printf("%c | ", 'A' + x);
10 for(unsigned short y = 0; y < MAP_SIZE; y++) {
11 char state = '.'; // An uncovered cell
12 if(game_state.map[x][y].has_mine && game_state.map[x][y].is_uncovered) {
13 state = '#'; // BOOM!
14 } else if(game_state.map[x][y].is_uncovered) {
15 // If a cell has been uncovered, show a hint if there are mines in the
neighbourhood
16 if(game_state.map[x][y].neighbours > 0)
17 state = (char)(game_state.map[x][y].neighbours + '0');
18 else
19 state = ' ';
20 } else if(game_state.map[x][y].is_marked) {
21 // If a cell is marked as a mine, show a
22 state = '!';
23 }
24 printf("%c | ", state);
25 }
26 puts("");
27 }
28 puts("");
29 }
30

Avendo implementato queste funzioni, il game_loop deve semplicemente alternare le fasi di stampa della mappa
e di input da tastiera. Come accennato in precedenza, la funzione get_input restituisce una enum action . Il
main loop dovrà quindi aggiornare lo stato della partita in funzione dell'azione, verificando anche se il
giocatore ha vinto o perso la partita.

Determinare se il giocatore ha perso la partita è semplice: basta che egli abbia scoperto una cella con una mina.
Viceversa, per determinare se il giocatore ha vinto la partita, è necessario accertarsi che tutte le celle senza
mina siano state scoperte una ed una sola volta. Nello stato della partita era stato introdotto il membro
tot_uncovered_cells proprio per semplificare questo controllo. Nel caso alla riga 16 si verifica se una data cella
sta venendo scoperta per la prima volta e, in quel caso, si incrementa anche questo contatore. Se il giocatore ha
scoperto una e una sola volta un numero di celle pari alle celle totali meno quelle occupate da mine (riga 32),
egli ha vinto la partita.

1
2
3 bool game_loop(void)
4 {
5 unsigned short x, y;
6 while(true) {
7 print_map();
8 enum actions action = get_input(&x, &y);
9 switch(action) {
10 case MARK_MINE:
11 game_state.map[x][y].is_marked = true;
12 break;
13 case UNMARK_MINE:
14 game_state.map[x][y].is_marked = false;
15 break;
16 case UNCOVER:
17 if(!game_state.map[x][y].is_uncovered) {
18 game_state.map[x][y].is_uncovered = true;
19 game_state.tot_uncovered_cells++;
20 }
21 if(game_state.map[x][y].has_mine) {
22 print_map();
23 return false;
24 }
25 break;
26 default:
27 fprintf(stderr, "Unexpected action! Aborting...\n");
28 exit(EXIT_FAILURE);
29 }
30
31 // Check if the player won
32 if(game_state.tot_uncovered_cells == MAP_SIZE * MAP_SIZE - game_state.tot_num_mines)
33 return true;
34 }
35 }

Codice completo
Per semplicità di fruizione della soluzione, si riporta di seguito il codice completo.

1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <stdbool.h>
4 #include <time.h>
5 #include <assert.h>
6 #include <string.h>
7 #include <ctype.h>
8
9 #define MIN_NUM_MINES 3
10 #define MAP_SIZE 10
11 #define clrscr() printf("\033[1;1H\033[2J")
12
13 // Definition of possible game actions
14 enum actions {
15 MARK_MINE, UNMARK_MINE, UNCOVER
16 };
17
18 // The state of the game: it's a matrix keeping the state of each cell, plus a couple of
19 // global variables that describe what happened so far in the program.
20 struct game_state_t {
21 struct cell_state_t {
22 unsigned char has_mine : 1;
23 unsigned char is_uncovered : 1;
24 unsigned char is_marked : 1;
25 unsigned char neighbours : 4; // The number of neighbours with mines (max is 8!)
26 } map[MAP_SIZE][MAP_SIZE];
27 unsigned char tot_num_mines;
28 unsigned char tot_uncovered_cells;
29 } game_state = {0};
30
31 // This function returns a random value in [min, max]
32 static int random_int(int min, int max)
33 {
34 int ret = (int) ((double)(max - min) * rand() / RAND_MAX) + min;
35 if(ret == MAP_SIZE)
36 ret--;
37 return ret;
38 }
39
40
41 static void init_field(void)
42 {
43 // Get random number of mines
44 game_state.tot_num_mines = random_int(3, 10);
45
46 // Place the mines
47 for(unsigned short i = 0; i < game_state.tot_num_mines; i++) {
48 unsigned short x, y;
49
50 retry:
51 x = random_int(0, 9);
52 y = random_int(0, 9);
53
54 // If we picked a cell which has already a mine, we have to retry
55 if(game_state.map[x][y].has_mine)
56 goto retry;
57
58 game_state.map[x][y].has_mine = true;
59 }
60
61 // Precompute the number of mines in adjacent cells to show hints
62 for(unsigned short x = 0; x < MAP_SIZE; x++) {
63 for(unsigned short y = 0; y < MAP_SIZE; y++) {
64 unsigned short mines = 0;
65 if(game_state.map[x][y].has_mine) // Don't consider cells with mines
66 continue;
67
68 // We should offset [-1,+1] from current coordinates both along x and y.
69 // BUT we must check if we get out of bounds of the map!
70 for(short i = -1; i <= 1; i++) {
71 for(short j = -1; j <= 1; j++) {
72 if((unsigned short)(x + i) < MAP_SIZE && (unsigned short)(y + j) < MAP_SIZE)
73 mines += game_state.map[x + i][y + j].has_mine == true;
74 }
75 }
76
77 assert(mines <= 8); // We cannot have more than 8 neighbours with mines!
78 game_state.map[x][y].neighbours = mines;
79 }
80 }
81 }
82
83
84 static void print_map(void)
85 {
86 clrscr();
87 printf(" ** MINE SWEEPER **\n\n ");
88 for(unsigned short j = 0; j < MAP_SIZE; j++)
89 printf(" %d", j);
90 puts("");
91 for(unsigned short x = 0; x < MAP_SIZE; x++) {
92 printf("%c | ", 'A' + x);
93 for(unsigned short y = 0; y < MAP_SIZE; y++) {
94 char state = '.'; // An uncovered cell
95 if(game_state.map[x][y].has_mine && game_state.map[x][y].is_uncovered) {
96 state = '#'; // BOOM!
97 } else if(game_state.map[x][y].is_uncovered) {
98 // If a cell has been uncovered, show a hint if there are mines in the
neighbourhood
99 if(game_state.map[x][y].neighbours > 0)
100 state = (char)(game_state.map[x][y].neighbours + '0');
101 else
102 state = ' ';
103 } else if(game_state.map[x][y].is_marked) {
104 // If a cell is marked as a mine, show a
105 state = '!';
106 }
107 printf("%c | ", state);
108 }
109 puts("");
110 }
111 puts("");
112 }
113
114
115 enum actions get_input(unsigned short *x, unsigned short *y)
116 {
117 bool valid;
118 enum actions ret = UNCOVER;
119 int c;
120 unsigned char command[3];
121
122 puts("Accepted commands:");
123 puts(" - xyM: mark a cell as a mine.");
124 puts(" - xym: unmark a cell as a mine.");
125 puts(" - xy: uncover a cell as a mine.\n");
126
127 do {
128 unsigned short i = 0;
129 command[0] = command[1] = command[2] = '\0';
130 printf("What shall I do? ");
131 fflush(stdout);
132
133 do {
134 if((c = getchar()) == EOF) {
135 printf("\nQuitting...\n");
136 exit(EXIT_FAILURE);
137 }
138 if(i < 3)
139 command[i] = c;
140 i++;
141 } while(c != '\n');
142
143 // Ignore case for row letter
144 command[0] = tolower(command[0]);
145
146 // Check the input. Note that since we use UNSIGNED chars in checks, checking for greater
147 // values of characters implicitly checks for lower values, thanks to negative overflow
148 if(i > 4 // Too many characters
149 || (i == 4 && (tolower(command[2]) != 'm' && command[2] != '\n')) // last letter can
only be m/M
150 || (unsigned char)(command[0] - 'a') >= MAP_SIZE // row out of bounds
151 || (unsigned char)(command[1] - '0') >= MAP_SIZE) { // col out of bounds
152 valid = false;
153 } else {
154 valid = true;
155 }
156 } while(!valid);
157
158 // Prepare return values
159 if(command[2] == 'm')
160 ret = UNMARK_MINE;
161 if(command[2] == 'M')
162 ret = MARK_MINE;
163 *x = command[0] - 'a';
164 *y = command[1] - '0';
165
166 return ret;
167 }
168
169
170 bool game_loop(void)
171 {
172 unsigned short x, y;
173 while(true) {
174 print_map();
175 enum actions action = get_input(&x, &y);
176 switch(action) {
177 case MARK_MINE:
178 game_state.map[x][y].is_marked = true;
179 break;
180 case UNMARK_MINE:
181 game_state.map[x][y].is_marked = false;
182 break;
183 case UNCOVER:
184 if(!game_state.map[x][y].is_uncovered) {
185 game_state.map[x][y].is_uncovered = true;
186 game_state.tot_uncovered_cells++;
187 }
188 if(game_state.map[x][y].has_mine) {
189 print_map();
190 return false;
191 }
192 break;
193 default:
194 fprintf(stderr, "Unexpected action! Aborting...\n");
195 exit(EXIT_FAILURE);
196 }
197
198 // Check if the player won
199 if(game_state.tot_uncovered_cells == MAP_SIZE * MAP_SIZE - game_state.tot_num_mines)
200 return true;
201 }
202 }
203
204 int main(void)
205 {
206 // Initialize the pseudo-random number generator
207 srand(time(NULL));
208
209 // Configure and start the game
210 init_field();
211 if(game_loop()) {
212 puts("YOU WON!");
213 } else {
214 puts("GAME OVER");
215 }
216
217 return 0;
218 }