1 /**********************************************************************
2 * This source code is copyright 1999 by Gus Hartmann & Peter Keller *
3 * It may be distributed under the terms of the GNU General Purpose *
4 * License, version 2 or above; see the file COPYING for more *
5 * information. *
6 * *
7 * $Id: clear.c,v 1.11 2002-07-12 07:06:44 hartmann Exp $
8 * *
9 **********************************************************************/
10
11 #include <stdio.h>
12 #include <stdlib.h>
13 #include "sweep.h"
14
15
16 static void InsertChildren(struct Mark **ht, GameStats *Game, int x, int y);
17 static int CalcSquareNumber(GameStats *Game, int xx, int yy);
18 static int ExposeSquare(GameStats *Game, int xx, int yy, int total);
19 static unsigned char* InitLookupTable(void);
20 static struct Mark* NewMark(int x, int y);
21 static int SuperCount(GameStats* Game);
22
23 /* I should clean these up */
24 int g_num = 0;
25 unsigned char *g_table = NULL;
26 int g_table_w;
27 int g_table_h = 0;
28 struct Mark *g_mlist = NULL;
29
Clear(GameStats * Game)30 void Clear(GameStats *Game)
31 {
32 struct Mark **ht = NULL;
33 int total;
34 int x, y;
35
36 g_num = 0;
37 g_table = InitLookupTable();
38
39 /* give it the first candidate */
40 InsertMark(ht, Game->CursorX, Game->CursorY);
41
42 /* This is data recursion */
43 while(DeleteRandomMark(ht, &x, &y) == TRUE)
44 {
45 total = CalcSquareNumber(Game, x, y);
46 if (ExposeSquare(Game, x, y, total) == EMPTY)
47 {
48 InsertChildren(ht, Game, x, y);
49 }
50 }
51
52 free (g_table);
53 }
54
55 /* grab the eight or so children around the mark and insert them into the
56 * hash table */
InsertChildren(struct Mark ** ht,GameStats * Game,int x,int y)57 void InsertChildren(struct Mark **ht, GameStats *Game, int x, int y)
58 {
59 unsigned char retval;
60
61 /* Check the above squares */
62 if (y-1 >= 0)
63 {
64 /* Check upper-left */
65 if (x-1 >= 0)
66 {
67 GetMine(x-1, y-1, retval);
68 if (retval == UNKNOWN)
69 {
70 InsertMark(ht, x-1, y-1);
71 }
72 }
73
74 /* Check directly above */
75 GetMine(x, y-1, retval);
76 if (retval == UNKNOWN)
77 {
78 InsertMark(ht, x, y-1);
79 }
80
81 /* Check upper-right */
82 if (x+1 < Game->Width)
83 {
84 GetMine(x+1, y-1, retval);
85 if (retval == UNKNOWN)
86 {
87 InsertMark(ht, x+1, y-1);
88 }
89 }
90 }
91
92 if (x-1 >= 0)
93 {
94 GetMine(x-1, y, retval);
95 if (retval == UNKNOWN)
96 {
97 InsertMark(ht, x-1, y);
98 }
99 }
100
101 if (x+1 < Game->Width)
102 {
103 GetMine(x+1, y, retval);
104 if (retval == UNKNOWN)
105 {
106 InsertMark(ht, x+1, y);
107 }
108 }
109
110 /* Check the below squares */
111 if (y+1 < Game->Height)
112 {
113 /* Check lower-left */
114 if (x-1 >= 0)
115 {
116 GetMine(x-1, y+1, retval);
117 if (retval == UNKNOWN)
118 {
119 InsertMark(ht, x-1, y+1);
120 }
121 }
122
123 /* Check directly below */
124 GetMine(x, y+1, retval);
125 if (retval == UNKNOWN)
126 {
127 InsertMark(ht, x, y+1);
128 }
129
130 /* Check lower-right */
131 if (x+1 < Game->Width)
132 {
133 GetMine(x+1, y+1, retval);
134 if (retval == UNKNOWN)
135 {
136 InsertMark(ht, x+1, y+1);
137 }
138 }
139 }
140 }
141
142 /* determine the number of a particular square */
CalcSquareNumber(GameStats * Game,int x,int y)143 int CalcSquareNumber(GameStats *Game, int x, int y)
144 {
145 unsigned char SquareVal;
146 int Total=0;
147
148 GetMine(x,y,SquareVal);
149 if (SquareVal != UNKNOWN)
150 {
151 return SquareVal;
152 }
153
154 /* Check the above squares */
155 if (y-1 >= 0)
156 {
157 /* Check upper-left */
158 if (x-1 >= 0)
159 {
160 GetMine(x-1,y-1,SquareVal);
161 if ((SquareVal == MINE)||(SquareVal == MARKED)||(SquareVal == DETONATED))
162 {
163 Total++;
164 }
165 }
166
167 /* Check directly above */
168 GetMine(x,y-1,SquareVal);
169 if ((SquareVal == MINE)||(SquareVal == MARKED)||(SquareVal == DETONATED))
170 {
171 Total++;
172 }
173
174 /* Check upper-right */
175 if (x+1 < Game->Width)
176 {
177 GetMine(x+1,y-1,SquareVal);
178 if ((SquareVal == MINE)||(SquareVal == MARKED)||(SquareVal == DETONATED))
179 {
180 Total++;
181 }
182 }
183 }
184
185 if (x-1 >= 0)
186 {
187 GetMine(x-1,y,SquareVal);
188 if ((SquareVal == MINE)||(SquareVal == MARKED)||(SquareVal == DETONATED))
189 {
190 Total++;
191 }
192 }
193
194 if (x+1 < Game->Width)
195 {
196 GetMine(x+1,y,SquareVal);
197 if ((SquareVal == MINE)||(SquareVal == MARKED)||(SquareVal == DETONATED))
198 {
199 Total++;
200 }
201 }
202
203 /* Check the below squares */
204 if (y+1 < Game->Height)
205 {
206 /* Check lower-left */
207 if (x-1 >= 0)
208 {
209 GetMine(x-1,y+1,SquareVal);
210 if ((SquareVal == MINE)||(SquareVal == MARKED)||(SquareVal == DETONATED))
211 {
212 Total++;
213 }
214 }
215
216 /* Check directly below */
217 GetMine(x,y+1,SquareVal);
218 if ((SquareVal == MINE)||(SquareVal == MARKED)||(SquareVal == DETONATED))
219 {
220 Total++;
221 }
222
223 /* Check lower-right */
224 if (x+1 < Game->Width)
225 {
226 GetMine(x+1,y+1,SquareVal);
227 if ((SquareVal == MINE)||(SquareVal == MARKED)||(SquareVal == DETONATED))
228 {
229 Total++;
230 }
231 }
232 }
233
234 return Total;
235 }
236
237 /* fill in what a square is number wise */
ExposeSquare(GameStats * Game,int x,int y,int total)238 int ExposeSquare(GameStats *Game, int x, int y, int total)
239 {
240 SetMine(x, y, total==0?EMPTY:total);
241
242 return (total==0?EMPTY:total);
243 }
244
InitLookupTable(void)245 unsigned char* InitLookupTable(void)
246 {
247 int width, height;
248 unsigned char *m = NULL;
249
250 width = MAX_W / 8;
251 if (MAX_W%8)
252 {
253 width++;
254 }
255
256 height = MAX_H;
257 if (MAX_W%8)
258 {
259 height++;
260 }
261
262 m = (unsigned char*)malloc(sizeof(unsigned char) * width * height);
263
264 if (m == NULL)
265 {
266 SweepError("Out of memory. Aborting...");
267 exit(EXIT_FAILURE);
268 }
269
270 g_table_w = width;
271 g_table_h = height;
272
273 memset(m, 0, width*height);
274
275 return (m);
276 }
277
278 /* if x,y exists, do nothing, otherwise, make a mark and insert it */
InsertMark(struct Mark ** ht,int x,int y)279 void InsertMark(struct Mark **ht, int x, int y)
280 {
281 struct Mark *m = NULL;
282
283 if (LOOKUP(g_table, x, y))
284 {
285 return;
286 }
287 SET(g_table, x, y);
288 g_num++;
289
290 m = NewMark(x, y);
291
292 m->next = g_mlist;
293 g_mlist = m;
294 }
295
296 /* find one in the table and deal with it */
DeleteRandomMark(struct Mark ** ht,int * xx,int * yy)297 char DeleteRandomMark(struct Mark **ht, int *xx, int *yy)
298 {
299 struct Mark *m = NULL;
300
301 m = g_mlist;
302 if (m == NULL)
303 {
304 return FALSE;
305 }
306
307 g_mlist = g_mlist->next;
308
309 *xx = m->x;
310 *yy = m->y;
311 UNSET(g_table, *xx, *yy);
312
313 free(m);
314
315 return TRUE;
316 }
317
318 /* make a new mark initialized nicely */
NewMark(int x,int y)319 struct Mark* NewMark(int x, int y)
320 {
321 struct Mark *m = NULL;
322
323 m = (struct Mark*)malloc(sizeof(struct Mark) * 1);
324
325 if (m == NULL)
326 {
327 SweepError("Out of memory! Sorry.");
328 exit(EXIT_FAILURE);
329 }
330
331 m->x = x;
332 m->y = y;
333 m->next = NULL;
334
335 return (m);
336 }
337
SuperClear(GameStats * Game)338 void SuperClear(GameStats *Game)
339 {
340 int val;
341 struct Mark **ht = NULL;
342 int total;
343 int x, y;
344
345 x = Game->CursorX;
346 y = Game->CursorY;
347 val = SuperCount(Game);
348
349 switch(val)
350 {
351 /* they marked incorrectly, and must now pay the price */
352 case DIE:
353 /* Boom();*/
354 Game->Status = LOSE;
355 SetMine(x,y,DETONATED);
356 CharSet.FalseMark='x';
357 CharSet.Mine='o';
358 break;
359 /* they marked correctly, and I can expand stuff */
360 case SUPERCLICK:
361 g_num = 0;
362 g_table = InitLookupTable();
363
364 /* insert all the ones around me */
365 InsertChildren(ht, Game, x, y);
366
367 /* This is data recursion */
368 while(DeleteRandomMark(ht, &x, &y) == TRUE)
369 {
370 total = CalcSquareNumber(Game, x, y);
371 if (ExposeSquare(Game, x, y, total) == EMPTY)
372 {
373 InsertChildren(ht, Game, x, y);
374 }
375 }
376
377 free (g_table);
378 break;
379 case DONOTHING:
380 /* yup, just that */
381 break;
382 default:
383 break;
384 }
385 }
386
387 /* calculate if I should superclick, die, or do nothing. */
SuperCount(GameStats * Game)388 int SuperCount(GameStats* Game)
389 {
390 unsigned char retval;
391 int MinesFound=0,BadFound=0;
392 int x, y;
393
394 x = Game->CursorX;
395 y = Game->CursorY;
396
397 /* Check the above squares */
398 if (y-1 >= 0)
399 {
400 /* Check upper-left */
401 if (x-1 >= 0)
402 {
403 GetMine(x-1, y-1, retval);
404 switch (retval)
405 {
406 case MINE:
407 MinesFound++;
408 break;
409 case BAD_MARK:
410 BadFound++;
411 break;
412 default:
413 break;
414 }
415 }
416
417 /* Check directly above */
418 GetMine(x, y-1, retval);
419 switch (retval)
420 {
421 case MINE:
422 MinesFound++;
423 break;
424 case BAD_MARK:
425 BadFound++;
426 break;
427 default:
428 break;
429 }
430
431 /* Check upper-right */
432 if (x+1 < Game->Width)
433 {
434 GetMine(x+1, y-1, retval);
435 switch (retval)
436 {
437 case MINE:
438 MinesFound++;
439 break;
440 case BAD_MARK:
441 BadFound++;
442 break;
443 default:
444 break;
445 }
446 }
447 }
448
449 if (x-1 >= 0)
450 {
451 GetMine(x-1, y, retval);
452 switch (retval)
453 {
454 case MINE:
455 MinesFound++;
456 break;
457 case BAD_MARK:
458 BadFound++;
459 break;
460 default:
461 break;
462 }
463 }
464
465 if (x+1 < Game->Width)
466 {
467 GetMine(x+1, y, retval);
468 switch (retval)
469 {
470 case MINE:
471 MinesFound++;
472 break;
473 case BAD_MARK:
474 BadFound++;
475 break;
476 default:
477 break;
478 }
479 }
480
481 /* Check the below squares */
482 if (y+1 < Game->Height)
483 {
484 /* Check lower-left */
485 if (x-1 >= 0)
486 {
487 GetMine(x-1, y+1, retval);
488 switch (retval)
489 {
490 case MINE:
491 MinesFound++;
492 break;
493 case BAD_MARK:
494 BadFound++;
495 break;
496 default:
497 break;
498 }
499 }
500
501 /* Check directly below */
502 GetMine(x, y+1, retval);
503 switch (retval)
504 {
505 case MINE:
506 MinesFound++;
507 break;
508 case BAD_MARK:
509 BadFound++;
510 break;
511 default:
512 break;
513 }
514
515 /* Check lower-right */
516 if (x+1 < Game->Width)
517 {
518 GetMine(x+1, y+1, retval);
519 switch (retval)
520 {
521 case MINE:
522 MinesFound++;
523 break;
524 case BAD_MARK:
525 BadFound++;
526 break;
527 default:
528 break;
529 }
530 }
531 }
532
533 /* some incorrectly marked mines */
534 if (BadFound != 0)
535 {
536 return DIE;
537 }
538 /* some correctly marked, some not marked mines */
539 else if (MinesFound != 0 && BadFound == 0)
540 {
541 return DONOTHING;
542 }
543 /* all mines correctly marked */
544 else
545 {
546 return SUPERCLICK;
547 }
548 }
549
550 #define TEST(a,b) if(a>=0 && a< Game->Height && b>=0 && b<Game->Width ) { GetMine(x, y, square) ; if (( square == MINE ) || ( square == UNKNOWN )) { Game->CursorX=a ; Game->CursorY=b ; return 0 ; } }
551
FindNearest(GameStats * Game)552 int FindNearest(GameStats *Game)
553 {
554 int x, y;
555 int minx, miny, minscore, score;
556 unsigned char square;
557
558 x = Game->CursorX;
559 y = Game->CursorY;
560
561 GetMine(x, y, square);
562 if (( square == MINE ) || ( square == UNKNOWN ))
563 {
564 /* We're *on* an unmarked square already! */
565 return 0;
566 }
567
568 /* This should be really, really big. */
569 /* minscore = ( Game->Width ) * ( Game->Width ) * ( Game->Height ) * ( Game->Height ));*/
570 /* minscore = MAX_INT;*/
571 minscore = 0x7ffffff;
572 minx = Game->CursorX;
573 miny = Game->CursorY;
574
575 for ( x = 0 ; x < Game->Width ; x++ ) {
576 for ( y = 0 ; y < Game->Height ; y++ ) {
577 GetMine(x, y, square);
578 if (( square == MINE ) || ( square == UNKNOWN ))
579 {
580 score = (( Game->CursorX - x ) * ( Game->CursorX - x )) + (( Game->CursorY - y ) * ( Game->CursorY - y ));
581 if ( score < minscore )
582 {
583 minscore = score;
584 minx = x;
585 miny = y;
586 }
587 }
588 }
589 }
590
591 Game->CursorX = minx;
592 Game->CursorY = miny;
593
594 #ifdef DEBUG_LOG
595 fprintf(DebugLog, "Minimum score of %d found at %d,%d\n", minscore, minx, miny);
596 fflush(DebugLog);
597 #endif /* DEBUG_LOG */
598
599 return 0;
600 }
601
FindNearestBad(GameStats * Game)602 int FindNearestBad(GameStats *Game)
603 {
604 int x, y;
605 int minx, miny, minscore, score;
606 unsigned char square;
607
608 x = Game->CursorX;
609 y = Game->CursorY;
610
611 GetMine(x, y, square);
612 if (( square == BAD_MARK ) || ( Game->BadMarkedMines == 0 ))
613 {
614 /* We're done here. */
615 return 0;
616 }
617
618 /* This should be really, really big. */
619 /* minscore = ( Game->Width ) * ( Game->Width ) * ( Game->Height ) * ( Game->Height ));*/
620 /* minscore = MAX_INT;*/
621 minscore = 0x7ffffff;
622 minx = Game->CursorX;
623 miny = Game->CursorY;
624
625 for ( x = 0 ; x < Game->Width ; x++ ) {
626 for ( y = 0 ; y < Game->Height ; y++ ) {
627 GetMine(x, y, square);
628 if ( square == BAD_MARK )
629 {
630 score = (( Game->CursorX - x ) * ( Game->CursorX - x )) + (( Game->CursorY - y ) * ( Game->CursorY - y ));
631 if ( score < minscore )
632 {
633 minscore = score;
634 minx = x;
635 miny = y;
636 }
637 }
638 }
639 }
640
641 Game->CursorX = minx;
642 Game->CursorY = miny;
643
644 #ifdef DEBUG_LOG
645 fprintf(DebugLog, "Bad mark: minimum score of %d found at %d,%d\n", minscore, minx, miny);
646 fflush(DebugLog);
647 #endif /* DEBUG_LOG */
648
649 return 0;
650 }
651