1 /*
2 * Copyright � 1993-1999 Marc Baudoin <babafou@babafou.eu.org>
3 *
4 * Permission to use, copy, modify, and distribute this software and
5 * its documentation for any purpose and without fee is hereby
6 * granted, provided that the above copyright notice appear in all
7 * copies and that both that copyright notice and this permission
8 * notice appear in supporting documentation. The author makes no
9 * representations about the suitability of this software for any
10 * purpose. It is provided "as is" without express or implied
11 * warranty.
12 *
13 */
14
15 static char *const cvsid = "$Id: demineur.c,v 1.2.2.1 1999/07/29 21:25:30 babafou Exp $" ;
16
17 #include <sys/types.h>
18
19 #include <stdio.h>
20 #include <stdlib.h>
21 #include <sysexits.h>
22
23 #include <sys/time.h>
24
25 #include "demineur.h"
26 #include "util.h"
27 #include "xdemineur.h"
28
29 /* ------------------------------------------------------------------------- */
30
31 typedef struct row_column
32 {
33 int row ;
34 int column ;
35 struct row_column *next ;
36 }
37 row_column_t ;
38
39 /* ------------------------------------------------------------------------- */
40
41 int demineur_flag_count ( int row , int column ) ;
42
43 void demineur_won ( ) ;
44
45 /* ------------------------------------------------------------------------- */
46
47 board_t board ;
48 int mines ;
49 volatile time_t elapsed ;
50 state_t state ;
51
52 /* ------------------------------------------------------------------------- */
53
demineur_initialize(int option_mines)54 void demineur_initialize ( int option_mines )
55 {
56 int row , column , m , openings ;
57 row_column_t *rc = NULL , *ptr = NULL ;
58
59 /* There are two extra rows and two extra columns so that
60 * there's no need to handle side effects when counting the
61 * number of surrounding mines.
62 */
63
64 board.board = ( square_t ** ) xmalloc ( ( board.rows + 2 )
65 * sizeof ( square_t * ) ) ;
66 for ( row = 0 ; row < board.rows + 2 ; row ++ )
67 {
68 board.board[row] = ( square_t * ) xmalloc ( ( board.columns + 2 )
69 * sizeof ( square_t ) ) ;
70 }
71
72 if ( option_mines != 0 )
73 {
74 if ( option_mines >= board.rows * board.columns )
75 {
76 printf ( "Too many mines, using default number.\n" ) ;
77 mines = board.mines = board.rows * board.columns / 4.8 ;
78 }
79 else
80 {
81 mines = board.mines = option_mines ;
82 }
83 }
84 else
85 {
86 mines = board.mines = board.rows * board.columns / 4.8 ;
87 }
88
89 elapsed = 0 ;
90 state = PLAYING ;
91
92 /* initialize board */
93
94 for ( row = 0 ; row < board.rows + 2 ; row ++ )
95 {
96 for ( column = 0 ; column < board.columns + 2 ; column ++ )
97 {
98 board.board[row][column].mine = 0 ;
99 board.board[row][column].around = 0 ;
100 board.board[row][column].state = HIDDEN ;
101 }
102 }
103
104 /* special treatment for extra squares */
105
106 for ( row = 0 ; row < board.rows + 2 ; row ++ )
107 {
108 board.board[row][0].state = UNCOVERED ;
109 board.board[row][board.columns + 1].state = UNCOVERED ;
110 }
111
112 for ( column = 0 ; column < board.columns + 2 ; column ++ )
113 {
114 board.board[0][column].state = UNCOVERED ;
115 board.board[board.rows + 1][column].state = UNCOVERED ;
116 }
117
118 /* mines deposit */
119
120 for ( row = 1 ; row <= board.rows ; row ++ )
121 {
122 for ( column = 1 ; column <= board.columns ; column ++ )
123 {
124 if ( rc == NULL ) /* first square */
125 {
126 rc = ( row_column_t * ) xmalloc ( sizeof ( row_column_t ) ) ;
127 ptr = rc ;
128 }
129 else
130 {
131 ptr->next = ( row_column_t * )
132 xmalloc ( sizeof ( row_column_t ) ) ;
133 ptr = ptr->next ;
134 }
135
136 ptr->row = row ;
137 ptr->column = column ;
138 ptr->next = NULL ;
139 }
140 }
141
142 for ( m = 0 ; m < board.mines ; m ++ )
143 {
144 int alea = rand ( ) % ( board.rows * board.columns - m ) ;
145
146 if ( alea == 0 )
147 {
148 ptr = rc ;
149 rc = rc->next ;
150 }
151 else
152 {
153 row_column_t *tmp ;
154
155 for ( ptr = rc ; alea > 1 ; alea -- , ptr = ptr->next )
156 {
157 continue ;
158 }
159
160 tmp = ptr->next ;
161 ptr->next = ptr->next->next ;
162 ptr = tmp ;
163 }
164
165 board.board[ptr->row][ptr->column].mine = 1 ;
166 free ( ptr ) ;
167 }
168
169 /* free memory used by squares without mine */
170
171 for ( ptr = rc ; ptr != NULL ; )
172 {
173 row_column_t *tmp = ptr->next ;
174
175 free ( ptr ) ;
176 ptr = tmp ;
177 }
178 rc = NULL ;
179
180 /* mines counting */
181
182 for ( row = 1 ; row <= board.rows ; row ++ )
183 {
184 for ( column = 1 ; column <= board.columns ; column ++ )
185 {
186 board.board[row][column].around =
187 board.board[row - 1][column - 1].mine +
188 board.board[row - 1][column ].mine +
189 board.board[row - 1][column + 1].mine +
190 board.board[row ][column - 1].mine +
191 board.board[row ][column + 1].mine +
192 board.board[row + 1][column - 1].mine +
193 board.board[row + 1][column ].mine +
194 board.board[row + 1][column + 1].mine ;
195 }
196 }
197
198 /* automatic opening */
199
200 openings = 0 ;
201 for ( row = 1 ; row <= board.rows ; row ++ )
202 {
203 for ( column = 1 ; column <= board.columns ; column ++ )
204 {
205 if ( board.board[row][column].around == 0
206 && ! board.board[row][column].mine )
207 {
208 openings ++ ;
209
210 if ( rc == NULL ) /* first square */
211 {
212 rc = ( row_column_t * ) xmalloc ( sizeof ( row_column_t ) ) ;
213 ptr = rc ;
214 }
215 else
216 {
217 ptr->next = ( row_column_t * )
218 xmalloc ( sizeof ( row_column_t ) ) ;
219 ptr = ptr->next ;
220 }
221
222 ptr->row = row ;
223 ptr->column = column ;
224 ptr->next = NULL ;
225 }
226 }
227 }
228
229 if ( openings != 0 )
230 {
231 int alea = rand ( ) % openings , i ;
232
233 for ( i = 0 , ptr = rc ; i < alea ; i ++ , ptr = ptr->next )
234 {
235 continue ;
236 }
237
238 demineur_play ( ptr->row , ptr->column ) ;
239 }
240
241 for ( ptr = rc ; ptr != NULL ; )
242 {
243 row_column_t *tmp = ptr->next ;
244
245 free ( ptr ) ;
246 ptr = tmp ;
247 }
248 }
249
250 /* ------------------------------------------------------------------------- */
251
demineur_start_timer()252 void demineur_start_timer ( )
253 {
254 struct itimerval itimerval ;
255
256 itimerval.it_interval.tv_sec = 1 ;
257 itimerval.it_interval.tv_usec = 0 ;
258 itimerval.it_value.tv_sec = 1 ;
259 itimerval.it_value.tv_usec = 0 ;
260 if ( setitimer ( ITIMER_REAL , &itimerval , NULL ) == -1 )
261 {
262 perror ( "setitimer" ) ;
263 exit ( EX_OSERR ) ;
264 }
265 }
266
267 /* ------------------------------------------------------------------------- */
268
demineur_stop_timer()269 void demineur_stop_timer ( )
270 {
271 struct itimerval itimerval ;
272
273 timerclear ( &itimerval.it_interval ) ;
274 timerclear ( &itimerval.it_value ) ;
275
276 if ( setitimer ( ITIMER_REAL , &itimerval , NULL ) == -1 )
277 {
278 perror ( "setitimer" ) ;
279 exit ( EX_OSERR ) ;
280 }
281 }
282
283 /* ------------------------------------------------------------------------- */
284
demineur_play(int row,int column)285 void demineur_play ( int row , int column )
286 {
287 if ( row < 1 || row > board.rows || column < 1 || column > board.columns )
288 {
289 return ;
290 }
291
292 if ( board.board[row][column].state == HIDDEN )
293 {
294 board.board[row][column].state = UNCOVERED ;
295 xdemineur_square ( row , column ) ;
296 if ( board.board[row][column].mine )
297 {
298 state = LOST ;
299 demineur_stop_timer ( ) ;
300 xdemineur_display ( ) ;
301 }
302 else if ( board.board[row][column].around == 0 )
303 {
304 demineur_clear ( row , column ) ;
305 }
306 }
307
308 if ( mines == 0 )
309 {
310 demineur_won ( ) ;
311 }
312 }
313
314 /* ------------------------------------------------------------------------- */
315
demineur_hidden(int row,int column)316 int demineur_hidden ( int row , int column )
317 {
318 return demineur_hidden_count ( row - 1 , column - 1 ) +
319 demineur_hidden_count ( row - 1 , column ) +
320 demineur_hidden_count ( row - 1 , column + 1 ) +
321 demineur_hidden_count ( row , column - 1 ) +
322 demineur_hidden_count ( row , column + 1 ) +
323 demineur_hidden_count ( row + 1 , column - 1 ) +
324 demineur_hidden_count ( row + 1 , column ) +
325 demineur_hidden_count ( row + 1 , column + 1 ) ;
326 }
327
328 /* ------------------------------------------------------------------------- */
329
demineur_hidden_count(int row,int column)330 int demineur_hidden_count ( int row , int column )
331 {
332 return ( board.board[row][column].state == HIDDEN ) ? 1 : 0 ;
333 }
334
335 /* ------------------------------------------------------------------------- */
336
demineur_flags(int row,int column)337 int demineur_flags ( int row , int column )
338 {
339 return demineur_flag_count ( row - 1 , column - 1 ) +
340 demineur_flag_count ( row - 1 , column ) +
341 demineur_flag_count ( row - 1 , column + 1 ) +
342 demineur_flag_count ( row , column - 1 ) +
343 demineur_flag_count ( row , column + 1 ) +
344 demineur_flag_count ( row + 1 , column - 1 ) +
345 demineur_flag_count ( row + 1 , column ) +
346 demineur_flag_count ( row + 1 , column + 1 ) ;
347 }
348
349 /* ------------------------------------------------------------------------- */
350
demineur_flag_count(int row,int column)351 int demineur_flag_count ( int row , int column )
352 {
353 return ( board.board[row][column].state == FLAGGED ) ? 1 : 0 ;
354 }
355
356 /* ------------------------------------------------------------------------- */
357
demineur_clear(int row,int column)358 void demineur_clear ( int row , int column )
359 {
360 demineur_play ( row - 1 , column - 1 ) ;
361 demineur_play ( row - 1 , column ) ;
362 demineur_play ( row - 1 , column + 1 ) ;
363 demineur_play ( row , column - 1 ) ;
364 demineur_play ( row , column + 1 ) ;
365 demineur_play ( row + 1 , column - 1 ) ;
366 demineur_play ( row + 1 , column ) ;
367 demineur_play ( row + 1 , column + 1 ) ;
368 }
369
370 /* ------------------------------------------------------------------------- */
371
demineur_flag_question(int row,int column)372 void demineur_flag_question ( int row , int column )
373 {
374 switch ( board.board[row][column].state )
375 {
376 case HIDDEN :
377 if ( mines > 0 )
378 {
379 board.board[row][column].state = FLAGGED ;
380 mines -- ;
381 if ( mines == 0 )
382 {
383 demineur_won ( ) ;
384 }
385 }
386 break ;
387 case FLAGGED :
388 board.board[row][column].state = QUESTION ;
389 mines ++ ;
390 break ;
391 case QUESTION :
392 board.board[row][column].state = HIDDEN ;
393 break ;
394 case UNCOVERED :
395 break ;
396 }
397 }
398
399 /* ------------------------------------------------------------------------- */
400
demineur_won()401 void demineur_won ( )
402 {
403 int row , column ;
404
405 for ( row = 1 ; row <= board.rows ; row ++ )
406 {
407 for ( column = 1 ; column <= board.columns ; column ++ )
408 {
409 if ( board.board[row][column].state == HIDDEN ||
410 board.board[row][column].state == QUESTION )
411 {
412 return ;
413 }
414 }
415 }
416
417 /* if you get there, it's that you've won */
418
419 state = WON ;
420 demineur_stop_timer ( ) ;
421 xdemineur_face ( ) ;
422 }
423
424 /* ------------------------------------------------------------------------- */
425
demineur_end()426 void demineur_end ( )
427 {
428 int row ;
429
430 for ( row = 0 ; row < board.rows + 2 ; row ++ )
431 {
432 free ( board.board[row] ) ;
433 }
434 free ( board.board ) ;
435 }
436