tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * undead: Implementation of Haunted Mirror Mazes
3 *
4 * http://www.janko.at/Raetsel/Spukschloss/index.htm
5 *
6 * Puzzle definition is the total number of each monster type, the
7 * grid definition, and the list of sightings (clockwise, starting
8 * from top left corner)
9 *
10 * Example: (Janko puzzle No. 1,
11 * http://www.janko.at/Raetsel/Spukschloss/001.a.htm )
12 *
13 * Ghosts: 0 Vampires: 2 Zombies: 6
14 *
15 * 2 1 1 1
16 * 1 \ \ . / 2
17 * 0 \ . / . 2
18 * 0 / . / . 2
19 * 3 . . . \ 2
20 * 3 3 2 2
21 *
22 * would be encoded into:
23 * 4x4:0,2,6,LLaRLaRaRaRdL,2,1,1,1,2,2,2,2,2,2,3,3,3,0,0,1
24 *
25 * Additionally, the game description can contain monsters fixed at a
26 * certain grid position. The internal generator does not (yet) use
27 * this feature, but this is needed to enter puzzles like Janko No.
28 * 14, which is encoded as:
29 * 8x5:12,12,0,LaRbLaRaLaRLbRaVaVaGRaRaRaLbLaRbRLb,0,2,0,2,2,1,2,1,3,1,0,1,8,4,3,0,0,2,3,2,7,2,1,6,2,1
30 *
31 */
32
33#include <stdio.h>
34#include <stdlib.h>
35#include <string.h>
36#include <assert.h>
37#include <ctype.h>
38#ifdef NO_TGMATH_H
39# include <math.h>
40#else
41# include <tgmath.h>
42#endif
43
44#include "puzzles.h"
45
46enum {
47 COL_BACKGROUND,
48 COL_GRID,
49 COL_TEXT,
50 COL_ERROR,
51 COL_HIGHLIGHT,
52 COL_FLASH,
53 COL_GHOST,
54 COL_ZOMBIE,
55 COL_VAMPIRE,
56 COL_DONE,
57 NCOLOURS
58};
59
60enum {
61 PREF_PENCIL_KEEP_HIGHLIGHT,
62 PREF_MONSTERS,
63 N_PREF_ITEMS
64};
65
66#define DIFFLIST(A) \
67 A(EASY,Easy,e) \
68 A(NORMAL,Normal,n) \
69 A(TRICKY,Tricky,t)
70#define ENUM(upper,title,lower) DIFF_ ## upper,
71#define TITLE(upper,title,lower) #title,
72#define ENCODE(upper,title,lower) #lower
73#define CONFIG(upper,title,lower) ":" #title
74enum { DIFFLIST(ENUM) DIFFCOUNT };
75static char const *const undead_diffnames[] = { DIFFLIST(TITLE) "(count)" };
76static char const undead_diffchars[] = DIFFLIST(ENCODE);
77#define DIFFCONFIG DIFFLIST(CONFIG)
78
79struct game_params {
80 int w; /* Grid width */
81 int h; /* Grid height */
82 int diff; /* Puzzle difficulty */
83};
84
85static const struct game_params undead_presets[] = {
86 { 4, 4, DIFF_EASY },
87 { 4, 4, DIFF_NORMAL },
88 { 4, 4, DIFF_TRICKY },
89 { 5, 5, DIFF_EASY },
90 { 5, 5, DIFF_NORMAL },
91 { 5, 5, DIFF_TRICKY },
92 { 7, 7, DIFF_EASY },
93 { 7, 7, DIFF_NORMAL }
94};
95
96#define DEFAULT_PRESET 1
97
98static game_params *default_params(void) {
99 game_params *ret = snew(game_params);
100
101 *ret = undead_presets[DEFAULT_PRESET];
102 return ret;
103}
104
105static bool game_fetch_preset(int i, char **name, game_params **params) {
106 game_params *ret;
107 char buf[64];
108
109 if (i < 0 || i >= lenof(undead_presets)) return false;
110
111 ret = default_params();
112 *ret = undead_presets[i]; /* struct copy */
113 *params = ret;
114
115 sprintf(buf, "%dx%d %s",
116 undead_presets[i].w, undead_presets[i].h,
117 undead_diffnames[undead_presets[i].diff]);
118 *name = dupstr(buf);
119
120 return true;
121}
122
123static void free_params(game_params *params) {
124 sfree(params);
125}
126
127static game_params *dup_params(const game_params *params)
128{
129 game_params *ret = snew(game_params);
130 *ret = *params; /* structure copy */
131 return ret;
132}
133
134static void decode_params(game_params *params, char const *string) {
135 params->w = params->h = atoi(string);
136
137 while (*string && isdigit((unsigned char) *string)) ++string;
138 if (*string == 'x') {
139 string++;
140 params->h = atoi(string);
141 while (*string && isdigit((unsigned char)*string)) string++;
142 }
143
144 params->diff = DIFF_NORMAL;
145 if (*string == 'd') {
146 int i;
147 string++;
148 for (i = 0; i < DIFFCOUNT; i++)
149 if (*string == undead_diffchars[i])
150 params->diff = i;
151 if (*string) string++;
152 }
153
154 return;
155}
156
157static char *encode_params(const game_params *params, bool full)
158{
159 char buf[256];
160 sprintf(buf, "%dx%d", params->w, params->h);
161 if (full)
162 sprintf(buf + strlen(buf), "d%c", undead_diffchars[params->diff]);
163 return dupstr(buf);
164}
165
166static config_item *game_configure(const game_params *params)
167{
168 config_item *ret;
169 char buf[64];
170
171 ret = snewn(4, config_item);
172
173 ret[0].name = "Width";
174 ret[0].type = C_STRING;
175 sprintf(buf, "%d", params->w);
176 ret[0].u.string.sval = dupstr(buf);
177
178 ret[1].name = "Height";
179 ret[1].type = C_STRING;
180 sprintf(buf, "%d", params->h);
181 ret[1].u.string.sval = dupstr(buf);
182
183 ret[2].name = "Difficulty";
184 ret[2].type = C_CHOICES;
185 ret[2].u.choices.choicenames = DIFFCONFIG;
186 ret[2].u.choices.selected = params->diff;
187
188 ret[3].name = NULL;
189 ret[3].type = C_END;
190
191 return ret;
192}
193
194static game_params *custom_params(const config_item *cfg)
195{
196 game_params *ret = snew(game_params);
197
198 ret->w = atoi(cfg[0].u.string.sval);
199 ret->h = atoi(cfg[1].u.string.sval);
200 ret->diff = cfg[2].u.choices.selected;
201 return ret;
202}
203
204static const char *validate_params(const game_params *params, bool full)
205{
206 if (params->w < 3) return "Width must be at least 3";
207 if (params->h < 3) return "Height must be at least 3";
208 if (params->w > 54 / params->h) return "Grid is too big";
209 if (params->diff >= DIFFCOUNT) return "Unknown difficulty rating";
210 return NULL;
211}
212
213/* --------------------------------------------------------------- */
214/* Game state allocation, deallocation. */
215
216struct path {
217 int length;
218 int *p;
219 int grid_start;
220 int grid_end;
221 int num_monsters;
222 int *mapping;
223 int sightings_start;
224 int sightings_end;
225 int *xy;
226};
227
228struct game_common {
229 int refcount;
230 struct game_params params;
231 int wh;
232 int num_ghosts,num_vampires,num_zombies,num_total;
233 int num_paths;
234 struct path *paths;
235 int *grid;
236 int *xinfo;
237 bool *fixed;
238};
239
240struct game_state {
241 struct game_common *common;
242 int *guess;
243 unsigned char *pencils;
244 bool *cell_errors;
245 bool *hint_errors;
246 bool *hints_done;
247 bool count_errors[3];
248 bool solved;
249 bool cheated;
250};
251
252static game_state *new_state(const game_params *params) {
253 int i;
254 game_state *state = snew(game_state);
255 state->common = snew(struct game_common);
256
257 state->common->refcount = 1;
258 state->common->params.w = params->w;
259 state->common->params.h = params->h;
260 state->common->params.diff = params->diff;
261
262 state->common->wh = (state->common->params.w +2) * (state->common->params.h +2);
263
264 state->common->num_ghosts = 0;
265 state->common->num_vampires = 0;
266 state->common->num_zombies = 0;
267 state->common->num_total = 0;
268
269 state->common->grid = snewn(state->common->wh, int);
270 state->common->xinfo = snewn(state->common->wh, int);
271 state->common->fixed = NULL;
272
273 state->common->num_paths =
274 state->common->params.w + state->common->params.h;
275 state->common->paths = snewn(state->common->num_paths, struct path);
276
277 for (i=0;i<state->common->num_paths;i++) {
278 state->common->paths[i].length = 0;
279 state->common->paths[i].grid_start = -1;
280 state->common->paths[i].grid_end = -1;
281 state->common->paths[i].num_monsters = 0;
282 state->common->paths[i].sightings_start = 0;
283 state->common->paths[i].sightings_end = 0;
284 state->common->paths[i].p = snewn(state->common->wh,int);
285 state->common->paths[i].xy = snewn(state->common->wh,int);
286 state->common->paths[i].mapping = snewn(state->common->wh,int);
287 }
288
289 state->guess = NULL;
290 state->pencils = NULL;
291
292 state->cell_errors = snewn(state->common->wh, bool);
293 for (i=0;i<state->common->wh;i++)
294 state->cell_errors[i] = false;
295 state->hint_errors = snewn(2*state->common->num_paths, bool);
296 for (i=0;i<2*state->common->num_paths;i++)
297 state->hint_errors[i] = false;
298 state->hints_done = snewn(2 * state->common->num_paths, bool);
299 memset(state->hints_done, 0,
300 2 * state->common->num_paths * sizeof(bool));
301 for (i=0;i<3;i++)
302 state->count_errors[i] = false;
303
304 state->solved = false;
305 state->cheated = false;
306
307 return state;
308}
309
310static game_state *dup_game(const game_state *state)
311{
312 game_state *ret = snew(game_state);
313
314 ret->common = state->common;
315 ret->common->refcount++;
316
317 if (state->guess != NULL) {
318 ret->guess = snewn(ret->common->num_total,int);
319 memcpy(ret->guess, state->guess, ret->common->num_total*sizeof(int));
320 }
321 else ret->guess = NULL;
322
323 if (state->pencils != NULL) {
324 ret->pencils = snewn(ret->common->num_total,unsigned char);
325 memcpy(ret->pencils, state->pencils,
326 ret->common->num_total*sizeof(unsigned char));
327 }
328 else ret->pencils = NULL;
329
330 if (state->cell_errors != NULL) {
331 ret->cell_errors = snewn(ret->common->wh,bool);
332 memcpy(ret->cell_errors, state->cell_errors,
333 ret->common->wh*sizeof(bool));
334 }
335 else ret->cell_errors = NULL;
336
337 if (state->hint_errors != NULL) {
338 ret->hint_errors = snewn(2*ret->common->num_paths,bool);
339 memcpy(ret->hint_errors, state->hint_errors,
340 2*ret->common->num_paths*sizeof(bool));
341 }
342 else ret->hint_errors = NULL;
343
344 if (state->hints_done != NULL) {
345 ret->hints_done = snewn(2 * state->common->num_paths, bool);
346 memcpy(ret->hints_done, state->hints_done,
347 2 * state->common->num_paths * sizeof(bool));
348 }
349 else ret->hints_done = NULL;
350
351 ret->count_errors[0] = state->count_errors[0];
352 ret->count_errors[1] = state->count_errors[1];
353 ret->count_errors[2] = state->count_errors[2];
354
355 ret->solved = state->solved;
356 ret->cheated = state->cheated;
357
358 return ret;
359}
360
361static void free_game(game_state *state) {
362 int i;
363
364 state->common->refcount--;
365 if (state->common->refcount == 0) {
366 for (i=0;i<state->common->num_paths;i++) {
367 sfree(state->common->paths[i].mapping);
368 sfree(state->common->paths[i].xy);
369 sfree(state->common->paths[i].p);
370 }
371 sfree(state->common->paths);
372 sfree(state->common->xinfo);
373 sfree(state->common->grid);
374 if (state->common->fixed != NULL) sfree(state->common->fixed);
375 sfree(state->common);
376 }
377 if (state->hints_done != NULL) sfree(state->hints_done);
378 if (state->hint_errors != NULL) sfree(state->hint_errors);
379 if (state->cell_errors != NULL) sfree(state->cell_errors);
380 if (state->pencils != NULL) sfree(state->pencils);
381 if (state->guess != NULL) sfree(state->guess);
382 sfree(state);
383
384 return;
385}
386
387/* --------------------------------------------------------------- */
388/* Puzzle generator */
389
390/* cell states */
391enum {
392 CELL_EMPTY,
393 CELL_MIRROR_L,
394 CELL_MIRROR_R,
395 CELL_GHOST,
396 CELL_VAMPIRE,
397 CELL_ZOMBIE,
398 CELL_UNDEF
399};
400
401/* grid walk directions */
402enum {
403 DIRECTION_NONE,
404 DIRECTION_UP,
405 DIRECTION_RIGHT,
406 DIRECTION_LEFT,
407 DIRECTION_DOWN
408};
409
410static int range2grid(int rangeno, int width, int height, int *x, int *y) {
411
412 if (rangeno < 0) {
413 *x = 0; *y = 0; return DIRECTION_NONE;
414 }
415 if (rangeno < width) {
416 *x = rangeno+1; *y = 0; return DIRECTION_DOWN;
417 }
418 rangeno = rangeno - width;
419 if (rangeno < height) {
420 *x = width+1; *y = rangeno+1; return DIRECTION_LEFT;
421 }
422 rangeno = rangeno - height;
423 if (rangeno < width) {
424 *x = width-rangeno; *y = height+1; return DIRECTION_UP;
425 }
426 rangeno = rangeno - width;
427 if (rangeno < height) {
428 *x = 0; *y = height-rangeno; return DIRECTION_RIGHT;
429 }
430 *x = 0; *y = 0;
431 return DIRECTION_NONE;
432}
433
434static int grid2range(int x, int y, int w, int h) {
435 if (x>0 && x<w+1 && y>0 && y<h+1) return -1;
436 if (x<0 || x>w+1 || y<0 || y>h+1) return -1;
437 if ((x == 0 || x==w+1) && (y==0 || y==h+1)) return -1;
438 if (y==0) return x-1;
439 if (x==(w+1)) return y-1+w;
440 if (y==(h+1)) return 2*w + h - x;
441 return 2*(w+h) - y;
442}
443
444static void make_paths(game_state *state) {
445 int i;
446 int count = 0;
447
448 for (i=0;i<2*(state->common->params.w + state->common->params.h);i++) {
449 int x,y,dir;
450 int j,k,num_monsters;
451 bool found;
452 int c,p;
453 found = false;
454 /* Check whether inverse path is already in list */
455 for (j=0;j<count;j++) {
456 if (i == state->common->paths[j].grid_end) {
457 found = true;
458 break;
459 }
460 }
461 if (found) continue;
462
463 /* We found a new path through the mirror maze */
464 state->common->paths[count].grid_start = i;
465 dir = range2grid(i, state->common->params.w,
466 state->common->params.h,&x,&y);
467 state->common->paths[count].sightings_start =
468 state->common->grid[x+y*(state->common->params.w +2)];
469 while (true) {
470 int c,r;
471
472 if (dir == DIRECTION_DOWN) y++;
473 else if (dir == DIRECTION_LEFT) x--;
474 else if (dir == DIRECTION_UP) y--;
475 else if (dir == DIRECTION_RIGHT) x++;
476
477 r = grid2range(x, y, state->common->params.w,
478 state->common->params.h);
479 if (r != -1) {
480 state->common->paths[count].grid_end = r;
481 state->common->paths[count].sightings_end =
482 state->common->grid[x+y*(state->common->params.w +2)];
483 break;
484 }
485
486 c = state->common->grid[x+y*(state->common->params.w+2)];
487 state->common->paths[count].xy[state->common->paths[count].length] =
488 x+y*(state->common->params.w+2);
489 if (c == CELL_MIRROR_L) {
490 state->common->paths[count].p[state->common->paths[count].length] = -1;
491 if (dir == DIRECTION_DOWN) dir = DIRECTION_RIGHT;
492 else if (dir == DIRECTION_LEFT) dir = DIRECTION_UP;
493 else if (dir == DIRECTION_UP) dir = DIRECTION_LEFT;
494 else if (dir == DIRECTION_RIGHT) dir = DIRECTION_DOWN;
495 }
496 else if (c == CELL_MIRROR_R) {
497 state->common->paths[count].p[state->common->paths[count].length] = -1;
498 if (dir == DIRECTION_DOWN) dir = DIRECTION_LEFT;
499 else if (dir == DIRECTION_LEFT) dir = DIRECTION_DOWN;
500 else if (dir == DIRECTION_UP) dir = DIRECTION_RIGHT;
501 else if (dir == DIRECTION_RIGHT) dir = DIRECTION_UP;
502 }
503 else {
504 state->common->paths[count].p[state->common->paths[count].length] =
505 state->common->xinfo[x+y*(state->common->params.w+2)];
506 }
507 state->common->paths[count].length++;
508 }
509 /* Count unique monster entries in each path */
510 state->common->paths[count].num_monsters = 0;
511 for (j=0;j<state->common->num_total;j++) {
512 num_monsters = 0;
513 for (k=0;k<state->common->paths[count].length;k++)
514 if (state->common->paths[count].p[k] == j)
515 num_monsters++;
516 if (num_monsters > 0)
517 state->common->paths[count].num_monsters++;
518 }
519
520 /* Generate mapping vector */
521 c = 0;
522 for (p=0;p<state->common->paths[count].length;p++) {
523 int m;
524 m = state->common->paths[count].p[p];
525 if (m == -1) continue;
526 found = false;
527 for (j=0; j<c; j++)
528 if (state->common->paths[count].mapping[j] == m) found = true;
529 if (!found) state->common->paths[count].mapping[c++] = m;
530 }
531 count++;
532 }
533 return;
534}
535
536struct guess {
537 int length;
538 int *guess;
539 int *possible;
540};
541
542static bool next_list(struct guess *g, int pos) {
543
544 if (pos == 0) {
545 if ((g->guess[pos] == 1 && g->possible[pos] == 1) ||
546 (g->guess[pos] == 2 && (g->possible[pos] == 3 ||
547 g->possible[pos] == 2)) ||
548 g->guess[pos] == 4)
549 return false;
550 if (g->guess[pos] == 1 && (g->possible[pos] == 3 ||
551 g->possible[pos] == 7)) {
552 g->guess[pos] = 2; return true;
553 }
554 if (g->guess[pos] == 1 && g->possible[pos] == 5) {
555 g->guess[pos] = 4; return true;
556 }
557 if (g->guess[pos] == 2 && (g->possible[pos] == 6 || g->possible[pos] == 7)) {
558 g->guess[pos] = 4; return true;
559 }
560 }
561
562 if (g->guess[pos] == 1) {
563 if (g->possible[pos] == 1) {
564 return next_list(g,pos-1);
565 }
566 if (g->possible[pos] == 3 || g->possible[pos] == 7) {
567 g->guess[pos] = 2; return true;
568 }
569 if (g->possible[pos] == 5) {
570 g->guess[pos] = 4; return true;
571 }
572 }
573
574 if (g->guess[pos] == 2) {
575 if (g->possible[pos] == 2) {
576 return next_list(g,pos-1);
577 }
578 if (g->possible[pos] == 3) {
579 g->guess[pos] = 1; return next_list(g,pos-1);
580 }
581 if (g->possible[pos] == 6 || g->possible[pos] == 7) {
582 g->guess[pos] = 4; return true;
583 }
584 }
585
586 if (g->guess[pos] == 4) {
587 if (g->possible[pos] == 5 || g->possible[pos] == 7) {
588 g->guess[pos] = 1; return next_list(g,pos-1);
589 }
590 if (g->possible[pos] == 6) {
591 g->guess[pos] = 2; return next_list(g,pos-1);
592 }
593 if (g->possible[pos] == 4) {
594 return next_list(g,pos-1);
595 }
596 }
597 return false;
598}
599
600static void get_unique(game_state *state, int counter, random_state *rs) {
601
602 int p,i,c,pathlimit,count_uniques;
603 struct guess path_guess;
604 int *view_count;
605
606 struct entry {
607 struct entry *link;
608 int *guess;
609 int start_view;
610 int end_view;
611 };
612
613 struct {
614 struct entry *head;
615 struct entry *node;
616 } views, single_views, test_views;
617
618 struct entry test_entry;
619
620 path_guess.length = state->common->paths[counter].num_monsters;
621 path_guess.guess = snewn(path_guess.length,int);
622 path_guess.possible = snewn(path_guess.length,int);
623 for (i=0;i<path_guess.length;i++)
624 path_guess.guess[i] = path_guess.possible[i] = 0;
625
626 for (p=0;p<path_guess.length;p++) {
627 path_guess.possible[p] =
628 state->guess[state->common->paths[counter].mapping[p]];
629 switch (path_guess.possible[p]) {
630 case 1: path_guess.guess[p] = 1; break;
631 case 2: path_guess.guess[p] = 2; break;
632 case 3: path_guess.guess[p] = 1; break;
633 case 4: path_guess.guess[p] = 4; break;
634 case 5: path_guess.guess[p] = 1; break;
635 case 6: path_guess.guess[p] = 2; break;
636 case 7: path_guess.guess[p] = 1; break;
637 }
638 }
639
640 views.head = NULL;
641 views.node = NULL;
642
643 pathlimit = state->common->paths[counter].length + 1;
644 view_count = snewn(pathlimit*pathlimit, int);
645 for (i = 0; i < pathlimit*pathlimit; i++)
646 view_count[i] = 0;
647
648 do {
649 bool mirror;
650 int start_view, end_view;
651
652 mirror = false;
653 start_view = 0;
654 for (p=0;p<state->common->paths[counter].length;p++) {
655 if (state->common->paths[counter].p[p] == -1) mirror = true;
656 else {
657 for (i=0;i<path_guess.length;i++) {
658 if (state->common->paths[counter].p[p] ==
659 state->common->paths[counter].mapping[i]) {
660 if (path_guess.guess[i] == 1 && mirror)
661 start_view++;
662 if (path_guess.guess[i] == 2 && !mirror)
663 start_view++;
664 if (path_guess.guess[i] == 4)
665 start_view++;
666 break;
667 }
668 }
669 }
670 }
671 mirror = false;
672 end_view = 0;
673 for (p=state->common->paths[counter].length-1;p>=0;p--) {
674 if (state->common->paths[counter].p[p] == -1) mirror = true;
675 else {
676 for (i=0;i<path_guess.length;i++) {
677 if (state->common->paths[counter].p[p] ==
678 state->common->paths[counter].mapping[i]) {
679 if (path_guess.guess[i] == 1 && mirror)
680 end_view++;
681 if (path_guess.guess[i] == 2 && !mirror)
682 end_view++;
683 if (path_guess.guess[i] == 4)
684 end_view++;
685 break;
686 }
687 }
688 }
689 }
690
691 assert(start_view >= 0 && start_view < pathlimit);
692 assert(end_view >= 0 && end_view < pathlimit);
693 i = start_view * pathlimit + end_view;
694 view_count[i]++;
695 if (view_count[i] == 1) {
696 views.node = snewn(1,struct entry);
697 views.node->link = views.head;
698 views.node->guess = snewn(path_guess.length,int);
699 views.head = views.node;
700 views.node->start_view = start_view;
701 views.node->end_view = end_view;
702 memcpy(views.node->guess, path_guess.guess,
703 path_guess.length*sizeof(int));
704 }
705 } while (next_list(&path_guess, path_guess.length-1));
706
707 /* extract single entries from view list */
708
709 test_views.head = views.head;
710 test_views.node = views.node;
711
712 test_entry.guess = snewn(path_guess.length,int);
713
714 single_views.head = NULL;
715 single_views.node = NULL;
716
717 count_uniques = 0;
718 while (test_views.head != NULL) {
719 test_views.node = test_views.head;
720 test_views.head = test_views.head->link;
721 i = test_views.node->start_view * pathlimit + test_views.node->end_view;
722 if (view_count[i] == 1) {
723 single_views.node = snewn(1,struct entry);
724 single_views.node->link = single_views.head;
725 single_views.node->guess = snewn(path_guess.length,int);
726 single_views.head = single_views.node;
727 single_views.node->start_view = test_views.node->start_view;
728 single_views.node->end_view = test_views.node->end_view;
729 memcpy(single_views.node->guess, test_views.node->guess,
730 path_guess.length*sizeof(int));
731 count_uniques++;
732 }
733 }
734
735 sfree(view_count);
736
737 if (count_uniques > 0) {
738 test_entry.start_view = 0;
739 test_entry.end_view = 0;
740 /* Choose one unique guess per random */
741 /* While we are busy with looping through single_views, we
742 * conveniently free the linked list single_view */
743 c = random_upto(rs,count_uniques);
744 while(single_views.head != NULL) {
745 single_views.node = single_views.head;
746 single_views.head = single_views.head->link;
747 if (c-- == 0) {
748 memcpy(test_entry.guess, single_views.node->guess,
749 path_guess.length*sizeof(int));
750 test_entry.start_view = single_views.node->start_view;
751 test_entry.end_view = single_views.node->end_view;
752 }
753 sfree(single_views.node->guess);
754 sfree(single_views.node);
755 }
756
757 /* Modify state_guess according to path_guess.mapping */
758 for (i=0;i<path_guess.length;i++)
759 state->guess[state->common->paths[counter].mapping[i]] =
760 test_entry.guess[i];
761 }
762
763 sfree(test_entry.guess);
764
765 while (views.head != NULL) {
766 views.node = views.head;
767 views.head = views.head->link;
768 sfree(views.node->guess);
769 sfree(views.node);
770 }
771
772 sfree(path_guess.possible);
773 sfree(path_guess.guess);
774
775 return;
776}
777
778static int count_monsters(game_state *state,
779 int *cGhost, int *cVampire, int *cZombie) {
780 int cNone;
781 int i;
782
783 *cGhost = *cVampire = *cZombie = cNone = 0;
784
785 for (i=0;i<state->common->num_total;i++) {
786 if (state->guess[i] == 1) (*cGhost)++;
787 else if (state->guess[i] == 2) (*cVampire)++;
788 else if (state->guess[i] == 4) (*cZombie)++;
789 else cNone++;
790 }
791
792 return cNone;
793}
794
795static bool check_numbers(game_state *state, int *guess) {
796 bool valid;
797 int i;
798 int count_ghosts, count_vampires, count_zombies;
799
800 count_ghosts = count_vampires = count_zombies = 0;
801 for (i=0;i<state->common->num_total;i++) {
802 if (guess[i] == 1) count_ghosts++;
803 if (guess[i] == 2) count_vampires++;
804 if (guess[i] == 4) count_zombies++;
805 }
806
807 valid = true;
808
809 if (count_ghosts > state->common->num_ghosts) valid = false;
810 if (count_vampires > state->common->num_vampires) valid = false;
811 if (count_zombies > state->common->num_zombies) valid = false;
812
813 return valid;
814}
815
816static bool check_solution(int *g, struct path path) {
817 int i;
818 bool mirror;
819 int count;
820
821 count = 0;
822 mirror = false;
823 for (i=0;i<path.length;i++) {
824 if (path.p[i] == -1) mirror = true;
825 else {
826 if (g[path.p[i]] == 1 && mirror) count++;
827 else if (g[path.p[i]] == 2 && !mirror) count++;
828 else if (g[path.p[i]] == 4) count++;
829 }
830 }
831 if (count != path.sightings_start) return false;
832
833 count = 0;
834 mirror = false;
835 for (i=path.length-1;i>=0;i--) {
836 if (path.p[i] == -1) mirror = true;
837 else {
838 if (g[path.p[i]] == 1 && mirror) count++;
839 else if (g[path.p[i]] == 2 && !mirror) count++;
840 else if (g[path.p[i]] == 4) count++;
841 }
842 }
843 if (count != path.sightings_end) return false;
844
845 return true;
846}
847
848static bool solve_iterative(game_state *state, struct path *paths) {
849 bool solved;
850 int p,i,j,count;
851
852 int *guess;
853 int *possible;
854
855 struct guess loop;
856
857 solved = true;
858 loop.length = state->common->num_total;
859 guess = snewn(state->common->num_total,int);
860 possible = snewn(state->common->num_total,int);
861
862 for (i=0;i<state->common->num_total;i++) {
863 guess[i] = state->guess[i];
864 possible[i] = 0;
865 }
866
867 for (p=0;p<state->common->num_paths;p++) {
868 if (paths[p].num_monsters > 0) {
869 loop.length = paths[p].num_monsters;
870 loop.guess = snewn(paths[p].num_monsters,int);
871 loop.possible = snewn(paths[p].num_monsters,int);
872
873 for (i=0;i<paths[p].num_monsters;i++) {
874 switch (state->guess[paths[p].mapping[i]]) {
875 case 1: loop.guess[i] = 1; break;
876 case 2: loop.guess[i] = 2; break;
877 case 3: loop.guess[i] = 1; break;
878 case 4: loop.guess[i] = 4; break;
879 case 5: loop.guess[i] = 1; break;
880 case 6: loop.guess[i] = 2; break;
881 case 7: loop.guess[i] = 1; break;
882 }
883 loop.possible[i] = state->guess[paths[p].mapping[i]];
884 possible[paths[p].mapping[i]] = 0;
885 }
886
887 while(true) {
888 for (i=0;i<state->common->num_total;i++) {
889 guess[i] = state->guess[i];
890 }
891 count = 0;
892 for (i=0;i<paths[p].num_monsters;i++)
893 guess[paths[p].mapping[i]] = loop.guess[count++];
894 if (check_numbers(state,guess) &&
895 check_solution(guess,paths[p]))
896 for (j=0;j<paths[p].num_monsters;j++)
897 possible[paths[p].mapping[j]] |= loop.guess[j];
898 if (!next_list(&loop,loop.length-1)) break;
899 }
900 for (i=0;i<paths[p].num_monsters;i++)
901 state->guess[paths[p].mapping[i]] &=
902 possible[paths[p].mapping[i]];
903 sfree(loop.possible);
904 sfree(loop.guess);
905 }
906 }
907
908 for (i=0;i<state->common->num_total;i++) {
909 if (state->guess[i] == 3 || state->guess[i] == 5 ||
910 state->guess[i] == 6 || state->guess[i] == 7) {
911 solved = false; break;
912 }
913 }
914
915 sfree(possible);
916 sfree(guess);
917
918 return solved;
919}
920
921static bool solve_bruteforce(game_state *state, struct path *paths) {
922 bool solved, correct;
923 int number_solutions;
924 int p,i;
925
926 struct guess loop;
927
928 loop.guess = snewn(state->common->num_total,int);
929 loop.possible = snewn(state->common->num_total,int);
930
931 for (i=0;i<state->common->num_total;i++) {
932 loop.possible[i] = state->guess[i];
933 switch (state->guess[i]) {
934 case 1: loop.guess[i] = 1; break;
935 case 2: loop.guess[i] = 2; break;
936 case 3: loop.guess[i] = 1; break;
937 case 4: loop.guess[i] = 4; break;
938 case 5: loop.guess[i] = 1; break;
939 case 6: loop.guess[i] = 2; break;
940 case 7: loop.guess[i] = 1; break;
941 }
942 }
943
944 solved = false;
945 number_solutions = 0;
946
947 while (true) {
948
949 correct = true;
950 if (!check_numbers(state,loop.guess)) correct = false;
951 else
952 for (p=0;p<state->common->num_paths;p++)
953 if (!check_solution(loop.guess,paths[p])) {
954 correct = false; break;
955 }
956 if (correct) {
957 number_solutions++;
958 solved = true;
959 if(number_solutions > 1) {
960 solved = false;
961 break;
962 }
963 for (i=0;i<state->common->num_total;i++)
964 state->guess[i] = loop.guess[i];
965 }
966 if (!next_list(&loop,state->common->num_total -1)) {
967 break;
968 }
969 }
970
971 sfree(loop.possible);
972 sfree(loop.guess);
973
974 return solved;
975}
976
977static int path_cmp(const void *a, const void *b) {
978 const struct path *pa = (const struct path *)a;
979 const struct path *pb = (const struct path *)b;
980 return pa->num_monsters - pb->num_monsters;
981}
982
983static char *new_game_desc(const game_params *params, random_state *rs,
984 char **aux, bool interactive) {
985 int count,c,w,h,r,p,g;
986 game_state *new;
987
988 /* Variables for puzzle generation algorithm */
989 int filling;
990 int max_length;
991 int count_ghosts, count_vampires, count_zombies;
992 bool abort;
993 float ratio;
994
995 /* Variables for solver algorithm */
996 bool solved_iterative, solved_bruteforce, contains_inconsistency;
997 int count_ambiguous;
998 int iterative_depth;
999 int *old_guess;
1000
1001 /* Variables for game description generation */
1002 int x,y;
1003 char *e;
1004 char *desc;
1005
1006 while (true) {
1007 new = new_state(params);
1008 abort = false;
1009
1010 /* Fill grid with random mirrors and (later to be populated)
1011 * empty monster cells */
1012 count = 0;
1013 for (h=1;h<new->common->params.h+1;h++)
1014 for (w=1;w<new->common->params.w+1;w++) {
1015 c = random_upto(rs,5);
1016 if (c >= 2) {
1017 new->common->grid[w+h*(new->common->params.w+2)] = CELL_EMPTY;
1018 new->common->xinfo[w+h*(new->common->params.w+2)] = count++;
1019 }
1020 else if (c == 0) {
1021 new->common->grid[w+h*(new->common->params.w+2)] =
1022 CELL_MIRROR_L;
1023 new->common->xinfo[w+h*(new->common->params.w+2)] = -1;
1024 }
1025 else {
1026 new->common->grid[w+h*(new->common->params.w+2)] =
1027 CELL_MIRROR_R;
1028 new->common->xinfo[w+h*(new->common->params.w+2)] = -1;
1029 }
1030 }
1031 new->common->num_total = count; /* Total number of monsters in maze */
1032
1033 /* Puzzle is boring if it has too few monster cells. Discard
1034 * grid, make new grid */
1035 if (new->common->num_total <= 4) {
1036 free_game(new);
1037 continue;
1038 }
1039
1040 /* Monsters / Mirrors ratio should be balanced */
1041 ratio = (float)new->common->num_total /
1042 (float)(new->common->params.w * new->common->params.h);
1043 if (ratio < 0.48F || ratio > 0.78F) {
1044 free_game(new);
1045 continue;
1046 }
1047
1048 /* Assign clue identifiers */
1049 for (r=0;r<2*(new->common->params.w+new->common->params.h);r++) {
1050 int x,y,gridno;
1051 gridno = range2grid(r,new->common->params.w,new->common->params.h,
1052 &x,&y);
1053 new->common->grid[x+y*(new->common->params.w +2)] = gridno;
1054 new->common->xinfo[x+y*(new->common->params.w +2)] = 0;
1055 }
1056 /* The four corners don't matter at all for the game. Set them
1057 * all to zero, just to have a nice data structure */
1058 new->common->grid[0] = 0;
1059 new->common->xinfo[0] = 0;
1060 new->common->grid[new->common->params.w+1] = 0;
1061 new->common->xinfo[new->common->params.w+1] = 0;
1062 new->common->grid[new->common->params.w+1 + (new->common->params.h+1)*(new->common->params.w+2)] = 0;
1063 new->common->xinfo[new->common->params.w+1 + (new->common->params.h+1)*(new->common->params.w+2)] = 0;
1064 new->common->grid[(new->common->params.h+1)*(new->common->params.w+2)] = 0;
1065 new->common->xinfo[(new->common->params.h+1)*(new->common->params.w+2)] = 0;
1066
1067 /* Initialize solution vector */
1068 new->guess = snewn(new->common->num_total,int);
1069 for (g=0;g<new->common->num_total;g++) new->guess[g] = 7;
1070
1071 /* Initialize fixed flag from common. Not needed for the
1072 * puzzle generator; initialize it for having clean code */
1073 new->common->fixed = snewn(new->common->num_total, bool);
1074 for (g=0;g<new->common->num_total;g++)
1075 new->common->fixed[g] = false;
1076
1077 /* paths generation */
1078 make_paths(new);
1079
1080 /* Grid is invalid if max. path length > threshold. Discard
1081 * grid, make new one */
1082 switch (new->common->params.diff) {
1083 case DIFF_EASY: max_length = min(new->common->params.w,new->common->params.h) + 1; break;
1084 case DIFF_NORMAL: max_length = (max(new->common->params.w,new->common->params.h) * 3) / 2; break;
1085 case DIFF_TRICKY: max_length = 9; break;
1086 default: max_length = 9; break;
1087 }
1088
1089 for (p=0;p<new->common->num_paths;p++) {
1090 if (new->common->paths[p].num_monsters > max_length) {
1091 abort = true;
1092 }
1093 }
1094 if (abort) {
1095 free_game(new);
1096 continue;
1097 }
1098
1099 qsort(new->common->paths, new->common->num_paths,
1100 sizeof(struct path), path_cmp);
1101
1102 /* Grid monster initialization */
1103 /* For easy puzzles, we try to fill nearly the whole grid
1104 with unique solution paths (up to 2) For more difficult
1105 puzzles, we fill only roughly half the grid, and choose
1106 random monsters for the rest For hard puzzles, we fill
1107 even less paths with unique solutions */
1108
1109 switch (new->common->params.diff) {
1110 case DIFF_EASY: filling = 2; break;
1111 case DIFF_NORMAL: filling = min( (new->common->params.w+new->common->params.h) , (new->common->num_total)/2 ); break;
1112 case DIFF_TRICKY: filling = max( (new->common->params.w+new->common->params.h) , (new->common->num_total)/2 ); break;
1113 default: filling = 0; break;
1114 }
1115
1116 count = 0;
1117 while ( (count_monsters(new, &count_ghosts, &count_vampires,
1118 &count_zombies)) > filling) {
1119 if ((count) >= new->common->num_paths) break;
1120 if (new->common->paths[count].num_monsters == 0) {
1121 count++;
1122 continue;
1123 }
1124 get_unique(new,count,rs);
1125 count++;
1126 }
1127
1128 /* Fill any remaining ambiguous entries with random monsters */
1129 for(g=0;g<new->common->num_total;g++) {
1130 if (new->guess[g] == 7) {
1131 r = random_upto(rs,3);
1132 new->guess[g] = (r == 0) ? 1 : ( (r == 1) ? 2 : 4 );
1133 }
1134 }
1135
1136 /* Determine all hints */
1137 count_monsters(new, &new->common->num_ghosts,
1138 &new->common->num_vampires, &new->common->num_zombies);
1139
1140 /* Puzzle is trivial if it has only one type of monster. Discard. */
1141 if ((new->common->num_ghosts == 0 && new->common->num_vampires == 0) ||
1142 (new->common->num_ghosts == 0 && new->common->num_zombies == 0) ||
1143 (new->common->num_vampires == 0 && new->common->num_zombies == 0)) {
1144 free_game(new);
1145 continue;
1146 }
1147
1148 /* Discard puzzle if difficulty Tricky, and it has only 1
1149 * member of any monster type */
1150 if (new->common->params.diff == DIFF_TRICKY &&
1151 (new->common->num_ghosts <= 1 ||
1152 new->common->num_vampires <= 1 || new->common->num_zombies <= 1)) {
1153 free_game(new);
1154 continue;
1155 }
1156
1157 for (w=1;w<new->common->params.w+1;w++)
1158 for (h=1;h<new->common->params.h+1;h++) {
1159 c = new->common->xinfo[w+h*(new->common->params.w+2)];
1160 if (c >= 0) {
1161 if (new->guess[c] == 1) new->common->grid[w+h*(new->common->params.w+2)] = CELL_GHOST;
1162 if (new->guess[c] == 2) new->common->grid[w+h*(new->common->params.w+2)] = CELL_VAMPIRE;
1163 if (new->guess[c] == 4) new->common->grid[w+h*(new->common->params.w+2)] = CELL_ZOMBIE;
1164 }
1165 }
1166
1167 /* Prepare path information needed by the solver (containing all hints) */
1168 for (p=0;p<new->common->num_paths;p++) {
1169 bool mirror;
1170 int x,y;
1171
1172 new->common->paths[p].sightings_start = 0;
1173 new->common->paths[p].sightings_end = 0;
1174
1175 mirror = false;
1176 for (g=0;g<new->common->paths[p].length;g++) {
1177
1178 if (new->common->paths[p].p[g] == -1) mirror = true;
1179 else {
1180 if (new->guess[new->common->paths[p].p[g]] == 1 && mirror) (new->common->paths[p].sightings_start)++;
1181 else if (new->guess[new->common->paths[p].p[g]] == 2 && !mirror) (new->common->paths[p].sightings_start)++;
1182 else if (new->guess[new->common->paths[p].p[g]] == 4) (new->common->paths[p].sightings_start)++;
1183 }
1184 }
1185
1186 mirror = false;
1187 for (g=new->common->paths[p].length-1;g>=0;g--) {
1188 if (new->common->paths[p].p[g] == -1) mirror = true;
1189 else {
1190 if (new->guess[new->common->paths[p].p[g]] == 1 && mirror) (new->common->paths[p].sightings_end)++;
1191 else if (new->guess[new->common->paths[p].p[g]] == 2 && !mirror) (new->common->paths[p].sightings_end)++;
1192 else if (new->guess[new->common->paths[p].p[g]] == 4) (new->common->paths[p].sightings_end)++;
1193 }
1194 }
1195
1196 range2grid(new->common->paths[p].grid_start,
1197 new->common->params.w,new->common->params.h,&x,&y);
1198 new->common->grid[x+y*(new->common->params.w +2)] =
1199 new->common->paths[p].sightings_start;
1200 range2grid(new->common->paths[p].grid_end,
1201 new->common->params.w,new->common->params.h,&x,&y);
1202 new->common->grid[x+y*(new->common->params.w +2)] =
1203 new->common->paths[p].sightings_end;
1204 }
1205
1206 /* Try to solve the puzzle with the iterative solver */
1207 old_guess = snewn(new->common->num_total,int);
1208 for (p=0;p<new->common->num_total;p++) {
1209 new->guess[p] = 7;
1210 old_guess[p] = 7;
1211 }
1212 iterative_depth = 0;
1213 solved_iterative = false;
1214 contains_inconsistency = false;
1215 count_ambiguous = 0;
1216
1217 while (true) {
1218 bool no_change = true;
1219 solved_iterative = solve_iterative(new,new->common->paths);
1220 iterative_depth++;
1221 for (p=0;p<new->common->num_total;p++) {
1222 if (new->guess[p] != old_guess[p]) no_change = false;
1223 old_guess[p] = new->guess[p];
1224 if (new->guess[p] == 0) contains_inconsistency = true;
1225 }
1226 if (solved_iterative || no_change) break;
1227 }
1228
1229 /* If necessary, try to solve the puzzle with the brute-force solver */
1230 solved_bruteforce = false;
1231 if (new->common->params.diff != DIFF_EASY &&
1232 !solved_iterative && !contains_inconsistency) {
1233 for (p=0;p<new->common->num_total;p++)
1234 if (new->guess[p] != 1 && new->guess[p] != 2 &&
1235 new->guess[p] != 4) count_ambiguous++;
1236
1237 solved_bruteforce = solve_bruteforce(new, new->common->paths);
1238 }
1239
1240 /* Determine puzzle difficulty level */
1241 if (new->common->params.diff == DIFF_EASY && solved_iterative &&
1242 iterative_depth <= 3 && !contains_inconsistency) {
1243/* printf("Puzzle level: EASY Level %d Ratio %f Ambiguous %d (Found after %i tries)\n",iterative_depth, ratio, count_ambiguous, i); */
1244 break;
1245 }
1246
1247 if (new->common->params.diff == DIFF_NORMAL &&
1248 ((solved_iterative && iterative_depth > 3) ||
1249 (solved_bruteforce && count_ambiguous < 4)) &&
1250 !contains_inconsistency) {
1251/* printf("Puzzle level: NORMAL Level %d Ratio %f Ambiguous %d (Found after %d tries)\n", iterative_depth, ratio, count_ambiguous, i); */
1252 break;
1253 }
1254 if (new->common->params.diff == DIFF_TRICKY &&
1255 solved_bruteforce && iterative_depth > 0 &&
1256 count_ambiguous >= 4 && !contains_inconsistency) {
1257/* printf("Puzzle level: TRICKY Level %d Ratio %f Ambiguous %d (Found after %d tries)\n", iterative_depth, ratio, count_ambiguous, i); */
1258 break;
1259 }
1260
1261 /* If puzzle is not solvable or does not satisfy the desired
1262 * difficulty level, free memory and start from scratch */
1263 sfree(old_guess);
1264 free_game(new);
1265 }
1266
1267 /* We have a valid puzzle! */
1268
1269 desc = snewn(10 + new->common->wh +
1270 6*(new->common->params.w + new->common->params.h), char);
1271 e = desc;
1272
1273 /* Encode monster counts */
1274 e += sprintf(e, "%d,", new->common->num_ghosts);
1275 e += sprintf(e, "%d,", new->common->num_vampires);
1276 e += sprintf(e, "%d,", new->common->num_zombies);
1277
1278 /* Encode grid */
1279 count = 0;
1280 for (y=1;y<new->common->params.h+1;y++)
1281 for (x=1;x<new->common->params.w+1;x++) {
1282 c = new->common->grid[x+y*(new->common->params.w+2)];
1283 if (count > 25) {
1284 *e++ = 'z';
1285 count -= 26;
1286 }
1287 if (c != CELL_MIRROR_L && c != CELL_MIRROR_R) {
1288 count++;
1289 }
1290 else if (c == CELL_MIRROR_L) {
1291 if (count > 0) *e++ = (count-1 + 'a');
1292 *e++ = 'L';
1293 count = 0;
1294 }
1295 else {
1296 if (count > 0) *e++ = (count-1 + 'a');
1297 *e++ = 'R';
1298 count = 0;
1299 }
1300 }
1301 if (count > 0) *e++ = (count-1 + 'a');
1302
1303 /* Encode hints */
1304 for (p=0;p<2*(new->common->params.w + new->common->params.h);p++) {
1305 range2grid(p,new->common->params.w,new->common->params.h,&x,&y);
1306 e += sprintf(e, ",%d", new->common->grid[x+y*(new->common->params.w+2)]);
1307 }
1308
1309 *e++ = '\0';
1310 desc = sresize(desc, e - desc, char);
1311
1312 sfree(old_guess);
1313 free_game(new);
1314
1315 return desc;
1316}
1317
1318static void num2grid(int num, int width, int height, int *x, int *y) {
1319 *x = 1+(num%width);
1320 *y = 1+(num/width);
1321 return;
1322}
1323
1324static key_label *game_request_keys(const game_params *params, int *nkeys)
1325{
1326 key_label *keys = snewn(4, key_label);
1327 *nkeys = 4;
1328
1329 keys[0].button = 'G';
1330 keys[0].label = dupstr("Ghost");
1331
1332 keys[1].button = 'V';
1333 keys[1].label = dupstr("Vampire");
1334
1335 keys[2].button = 'Z';
1336 keys[2].label = dupstr("Zombie");
1337
1338 keys[3].button = '\b';
1339 keys[3].label = NULL;
1340
1341 return keys;
1342}
1343
1344static game_state *new_game(midend *me, const game_params *params,
1345 const char *desc)
1346{
1347 int i;
1348 int n;
1349 int count;
1350
1351 game_state *state = new_state(params);
1352
1353 state->common->num_ghosts = atoi(desc);
1354 while (*desc && isdigit((unsigned char)*desc)) desc++;
1355 desc++;
1356 state->common->num_vampires = atoi(desc);
1357 while (*desc && isdigit((unsigned char)*desc)) desc++;
1358 desc++;
1359 state->common->num_zombies = atoi(desc);
1360 while (*desc && isdigit((unsigned char)*desc)) desc++;
1361 desc++;
1362
1363 state->common->num_total = state->common->num_ghosts + state->common->num_vampires + state->common->num_zombies;
1364
1365 state->guess = snewn(state->common->num_total,int);
1366 state->pencils = snewn(state->common->num_total,unsigned char);
1367 state->common->fixed = snewn(state->common->num_total, bool);
1368 for (i=0;i<state->common->num_total;i++) {
1369 state->guess[i] = 7;
1370 state->pencils[i] = 0;
1371 state->common->fixed[i] = false;
1372 }
1373 for (i=0;i<state->common->wh;i++)
1374 state->cell_errors[i] = false;
1375 for (i=0;i<2*state->common->num_paths;i++)
1376 state->hint_errors[i] = false;
1377 for (i=0;i<3;i++)
1378 state->count_errors[i] = false;
1379
1380 count = 0;
1381 n = 0;
1382 while (*desc != ',') {
1383 int c;
1384 int x,y;
1385
1386 if (*desc == 'L') {
1387 num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
1388 state->common->grid[x+y*(state->common->params.w +2)] = CELL_MIRROR_L;
1389 state->common->xinfo[x+y*(state->common->params.w+2)] = -1;
1390 n++;
1391 }
1392 else if (*desc == 'R') {
1393 num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
1394 state->common->grid[x+y*(state->common->params.w +2)] = CELL_MIRROR_R;
1395 state->common->xinfo[x+y*(state->common->params.w+2)] = -1;
1396 n++;
1397 }
1398 else if (*desc == 'G') {
1399 num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
1400 state->common->grid[x+y*(state->common->params.w +2)] = CELL_GHOST;
1401 state->common->xinfo[x+y*(state->common->params.w+2)] = count;
1402 state->guess[count] = 1;
1403 state->common->fixed[count++] = true;
1404 n++;
1405 }
1406 else if (*desc == 'V') {
1407 num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
1408 state->common->grid[x+y*(state->common->params.w +2)] = CELL_VAMPIRE;
1409 state->common->xinfo[x+y*(state->common->params.w+2)] = count;
1410 state->guess[count] = 2;
1411 state->common->fixed[count++] = true;
1412 n++;
1413 }
1414 else if (*desc == 'Z') {
1415 num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
1416 state->common->grid[x+y*(state->common->params.w +2)] = CELL_ZOMBIE;
1417 state->common->xinfo[x+y*(state->common->params.w+2)] = count;
1418 state->guess[count] = 4;
1419 state->common->fixed[count++] = true;
1420 n++;
1421 }
1422 else {
1423 c = *desc - ('a' -1);
1424 while (c-- > 0) {
1425 num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
1426 state->common->grid[x+y*(state->common->params.w +2)] = CELL_EMPTY;
1427 state->common->xinfo[x+y*(state->common->params.w+2)] = count;
1428 state->guess[count] = 7;
1429 state->common->fixed[count++] = false;
1430 n++;
1431 }
1432 }
1433 desc++;
1434 }
1435 desc++;
1436
1437 for (i=0;i<2*(state->common->params.w + state->common->params.h);i++) {
1438 int x,y;
1439 int sights;
1440
1441 sights = atoi(desc);
1442 while (*desc && isdigit((unsigned char)*desc)) desc++;
1443 desc++;
1444
1445
1446 range2grid(i,state->common->params.w,state->common->params.h,&x,&y);
1447 state->common->grid[x+y*(state->common->params.w +2)] = sights;
1448 state->common->xinfo[x+y*(state->common->params.w +2)] = -2;
1449 }
1450
1451 state->common->grid[0] = 0;
1452 state->common->xinfo[0] = -2;
1453 state->common->grid[state->common->params.w+1] = 0;
1454 state->common->xinfo[state->common->params.w+1] = -2;
1455 state->common->grid[state->common->params.w+1 + (state->common->params.h+1)*(state->common->params.w+2)] = 0;
1456 state->common->xinfo[state->common->params.w+1 + (state->common->params.h+1)*(state->common->params.w+2)] = -2;
1457 state->common->grid[(state->common->params.h+1)*(state->common->params.w+2)] = 0;
1458 state->common->xinfo[(state->common->params.h+1)*(state->common->params.w+2)] = -2;
1459
1460 make_paths(state);
1461 qsort(state->common->paths, state->common->num_paths, sizeof(struct path), path_cmp);
1462
1463 return state;
1464}
1465
1466static const char *validate_desc(const game_params *params, const char *desc)
1467{
1468 int i;
1469 int w = params->w, h = params->h;
1470 int wh = w*h;
1471 int area;
1472 int monsters;
1473 int monster_count;
1474 const char *desc_s = desc;
1475
1476 for (i=0;i<3;i++) {
1477 if (!*desc) return "Faulty game description";
1478 while (*desc && isdigit((unsigned char)*desc)) { desc++; }
1479 if (*desc != ',') return "Invalid character in number list";
1480 desc++;
1481 }
1482 desc = desc_s;
1483
1484 area = monsters = monster_count = 0;
1485 for (i=0;i<3;i++) {
1486 monster_count += atoi(desc);
1487 while (*desc && isdigit((unsigned char)*desc)) desc++;
1488 desc++;
1489 }
1490 while (*desc && *desc != ',') {
1491 if (*desc >= 'a' && *desc <= 'z') {
1492 area += *desc - 'a' +1; monsters += *desc - 'a' +1;
1493 } else if (*desc == 'G' || *desc == 'V' || *desc == 'Z') {
1494 area++; monsters++;
1495 } else if (*desc == 'L' || *desc == 'R') {
1496 area++;
1497 } else
1498 return "Invalid character in grid specification";
1499 desc++;
1500 }
1501 if (area < wh) return "Not enough data to fill grid";
1502 else if (area > wh) return "Too much data to fill grid";
1503 if (monsters != monster_count)
1504 return "Monster numbers do not match grid spaces";
1505
1506 for (i = 0; i < 2*(w+h); i++) {
1507 if (!*desc) return "Not enough numbers given after grid specification";
1508 else if (*desc != ',') return "Invalid character in number list";
1509 desc++;
1510 while (*desc && isdigit((unsigned char)*desc)) { desc++; }
1511 }
1512
1513 if (*desc) return "Unexpected additional data at end of game description";
1514
1515 return NULL;
1516}
1517
1518static char *solve_game(const game_state *state_start, const game_state *currstate,
1519 const char *aux, const char **error)
1520{
1521 int p;
1522 int *old_guess;
1523 int iterative_depth;
1524 bool solved_iterative, solved_bruteforce, contains_inconsistency;
1525 int count_ambiguous;
1526
1527 int i;
1528 char *move, *c;
1529
1530 game_state *solve_state = dup_game(currstate);
1531
1532 old_guess = snewn(solve_state->common->num_total,int);
1533 for (p=0;p<solve_state->common->num_total;p++) {
1534 if (solve_state->common->fixed[p]) {
1535 old_guess[p] = solve_state->guess[p] = state_start->guess[p];
1536 }
1537 else {
1538 old_guess[p] = solve_state->guess[p] = 7;
1539 }
1540 }
1541 iterative_depth = 0;
1542 solved_iterative = false;
1543 contains_inconsistency = false;
1544 count_ambiguous = 0;
1545
1546 /* Try to solve the puzzle with the iterative solver */
1547 while (true) {
1548 bool no_change = true;
1549 solved_iterative =
1550 solve_iterative(solve_state,solve_state->common->paths);
1551 iterative_depth++;
1552 for (p=0;p<solve_state->common->num_total;p++) {
1553 if (solve_state->guess[p] != old_guess[p]) no_change = false;
1554 old_guess[p] = solve_state->guess[p];
1555 if (solve_state->guess[p] == 0) contains_inconsistency = true;
1556 }
1557 if (solved_iterative || no_change || contains_inconsistency) break;
1558 }
1559
1560 if (contains_inconsistency) {
1561 *error = "Puzzle is inconsistent";
1562 sfree(old_guess);
1563 free_game(solve_state);
1564 return NULL;
1565 }
1566
1567 /* If necessary, try to solve the puzzle with the brute-force solver */
1568 solved_bruteforce = false;
1569 if (!solved_iterative) {
1570 for (p=0;p<solve_state->common->num_total;p++)
1571 if (solve_state->guess[p] != 1 && solve_state->guess[p] != 2 &&
1572 solve_state->guess[p] != 4) count_ambiguous++;
1573 solved_bruteforce =
1574 solve_bruteforce(solve_state, solve_state->common->paths);
1575 }
1576
1577 if (!solved_iterative && !solved_bruteforce) {
1578 *error = "Puzzle is unsolvable";
1579 sfree(old_guess);
1580 free_game(solve_state);
1581 return NULL;
1582 }
1583
1584/* printf("Puzzle solved at level %s, iterations %d, ambiguous %d\n", (solved_bruteforce ? "TRICKY" : "NORMAL"), iterative_depth, count_ambiguous); */
1585 (void)iterative_depth;
1586 (void)count_ambiguous;
1587
1588 move = snewn(solve_state->common->num_total * 4 +2, char);
1589 c = move;
1590 *c++='S';
1591 for (i = 0; i < solve_state->common->num_total; i++) {
1592 if (solve_state->guess[i] == 1) c += sprintf(c, ";G%d", i);
1593 if (solve_state->guess[i] == 2) c += sprintf(c, ";V%d", i);
1594 if (solve_state->guess[i] == 4) c += sprintf(c, ";Z%d", i);
1595 }
1596 *c++ = '\0';
1597 move = sresize(move, c - move, char);
1598
1599 sfree(old_guess);
1600 free_game(solve_state);
1601 return move;
1602}
1603
1604static bool game_can_format_as_text_now(const game_params *params)
1605{
1606 return true;
1607}
1608
1609static char *game_text_format(const game_state *state)
1610{
1611 int w,h,c,r,xi,g;
1612 char *ret;
1613 char buf[120];
1614
1615 ret = snewn(50 + 6*(state->common->params.w +2) +
1616 6*(state->common->params.h+2) +
1617 3*(state->common->params.w * state->common->params.h), char);
1618
1619 sprintf(ret,"G: %d V: %d Z: %d\n\n",state->common->num_ghosts,
1620 state->common->num_vampires, state->common->num_zombies);
1621
1622 for (h=0;h<state->common->params.h+2;h++) {
1623 for (w=0;w<state->common->params.w+2;w++) {
1624 c = state->common->grid[w+h*(state->common->params.w+2)];
1625 xi = state->common->xinfo[w+h*(state->common->params.w+2)];
1626 r = grid2range(w,h,state->common->params.w,state->common->params.h);
1627 if (r != -1) {
1628 sprintf(buf,"%2d", c); strcat(ret,buf);
1629 } else if (c == CELL_MIRROR_L) {
1630 sprintf(buf," \\"); strcat(ret,buf);
1631 } else if (c == CELL_MIRROR_R) {
1632 sprintf(buf," /"); strcat(ret,buf);
1633 } else if (xi >= 0) {
1634 g = state->guess[xi];
1635 if (g == 1) { sprintf(buf," G"); strcat(ret,buf); }
1636 else if (g == 2) { sprintf(buf," V"); strcat(ret,buf); }
1637 else if (g == 4) { sprintf(buf," Z"); strcat(ret,buf); }
1638 else { sprintf(buf," ."); strcat(ret,buf); }
1639 } else {
1640 sprintf(buf," "); strcat(ret,buf);
1641 }
1642 }
1643 sprintf(buf,"\n"); strcat(ret,buf);
1644 }
1645
1646 return ret;
1647}
1648
1649struct game_ui {
1650 int hx, hy; /* as for solo.c, highlight pos */
1651 bool hshow, hpencil, hcursor; /* show state, type, and ?cursor. */
1652 bool ascii;
1653
1654 /*
1655 * User preference option: if the user right-clicks in a square
1656 * and presses a monster key to add/remove a pencil mark, do we
1657 * hide the mouse highlight again afterwards?
1658 *
1659 * Historically our answer was yes. The Android port prefers no.
1660 * There are advantages both ways, depending how much you dislike
1661 * the highlight cluttering your view. So it's a preference.
1662 */
1663 bool pencil_keep_highlight;
1664};
1665
1666static game_ui *new_ui(const game_state *state)
1667{
1668 game_ui *ui = snew(game_ui);
1669 ui->hpencil = false;
1670 ui->hx = ui->hy = ui->hshow = ui->hcursor =
1671 getenv_bool("PUZZLES_SHOW_CURSOR", false);
1672 ui->ascii = false;
1673
1674 ui->pencil_keep_highlight = false;
1675
1676 return ui;
1677}
1678
1679static config_item *get_prefs(game_ui *ui)
1680{
1681 config_item *ret;
1682
1683 ret = snewn(N_PREF_ITEMS+1, config_item);
1684
1685 ret[PREF_PENCIL_KEEP_HIGHLIGHT].name =
1686 "Keep mouse highlight after changing a pencil mark";
1687 ret[PREF_PENCIL_KEEP_HIGHLIGHT].kw = "pencil-keep-highlight";
1688 ret[PREF_PENCIL_KEEP_HIGHLIGHT].type = C_BOOLEAN;
1689 ret[PREF_PENCIL_KEEP_HIGHLIGHT].u.boolean.bval = ui->pencil_keep_highlight;
1690
1691 ret[PREF_MONSTERS].name = "Monster representation";
1692 ret[PREF_MONSTERS].kw = "monsters";
1693 ret[PREF_MONSTERS].type = C_CHOICES;
1694 ret[PREF_MONSTERS].u.choices.choicenames = ":Pictures:Letters";
1695 ret[PREF_MONSTERS].u.choices.choicekws = ":pictures:letters";
1696 ret[PREF_MONSTERS].u.choices.selected = ui->ascii;
1697
1698 ret[N_PREF_ITEMS].name = NULL;
1699 ret[N_PREF_ITEMS].type = C_END;
1700
1701 return ret;
1702}
1703
1704static void set_prefs(game_ui *ui, const config_item *cfg)
1705{
1706 ui->pencil_keep_highlight = cfg[PREF_PENCIL_KEEP_HIGHLIGHT].u.boolean.bval;
1707 ui->ascii = cfg[PREF_MONSTERS].u.choices.selected;
1708}
1709
1710static void free_ui(game_ui *ui) {
1711 sfree(ui);
1712 return;
1713}
1714
1715static void game_changed_state(game_ui *ui, const game_state *oldstate,
1716 const game_state *newstate)
1717{
1718 /* See solo.c; if we were pencil-mode highlighting and
1719 * somehow a square has just been properly filled, cancel
1720 * pencil mode. */
1721 if (ui->hshow && ui->hpencil && !ui->hcursor) {
1722 int g = newstate->guess[newstate->common->xinfo[ui->hx + ui->hy*(newstate->common->params.w+2)]];
1723 if (g == 1 || g == 2 || g == 4)
1724 ui->hshow = false;
1725 }
1726}
1727
1728static const char *current_key_label(const game_ui *ui,
1729 const game_state *state, int button)
1730{
1731 int xi;
1732
1733 if (ui->hshow && button == CURSOR_SELECT)
1734 return ui->hpencil ? "Ink" : "Pencil";
1735 if (button == CURSOR_SELECT2) {
1736 xi = state->common->xinfo[ui->hx + ui->hy*(state->common->params.w+2)];
1737 if (xi >= 0 && !state->common->fixed[xi]) return "Clear";
1738 }
1739 return "";
1740}
1741
1742struct game_drawstate {
1743 int tilesize;
1744 bool started, solved;
1745 int w, h;
1746
1747 int *monsters;
1748 unsigned char *pencils;
1749
1750 bool count_errors[3];
1751 bool *cell_errors;
1752 bool *hint_errors;
1753 bool *hints_done;
1754
1755 int hx, hy;
1756 bool hshow, hpencil; /* as for game_ui. */
1757 bool hflash;
1758 bool ascii;
1759};
1760
1761static bool is_clue(const game_state *state, int x, int y)
1762{
1763 int h = state->common->params.h, w = state->common->params.w;
1764
1765 if (((x == 0 || x == w + 1) && y > 0 && y <= h) ||
1766 ((y == 0 || y == h + 1) && x > 0 && x <= w))
1767 return true;
1768
1769 return false;
1770}
1771
1772static int clue_index(const game_state *state, int x, int y)
1773{
1774 int h = state->common->params.h, w = state->common->params.w;
1775
1776 if (y == 0)
1777 return x - 1;
1778 else if (x == w + 1)
1779 return w + y - 1;
1780 else if (y == h + 1)
1781 return 2 * w + h - x;
1782 else if (x == 0)
1783 return 2 * (w + h) - y;
1784
1785 return -1;
1786}
1787
1788#define TILESIZE (ds->tilesize)
1789#define BORDER (TILESIZE/4)
1790
1791static char *interpret_move(const game_state *state, game_ui *ui,
1792 const game_drawstate *ds,
1793 int x, int y, int button)
1794{
1795 int gx,gy;
1796 int g,xi;
1797 char buf[80];
1798
1799 gx = ((x-BORDER-1) / TILESIZE );
1800 gy = ((y-BORDER-2) / TILESIZE ) - 1;
1801
1802 if (button == 'a' || button == 'A') {
1803 ui->ascii = !ui->ascii;
1804 return MOVE_UI_UPDATE;
1805 }
1806
1807 if (button == 'm' || button == 'M') {
1808 return dupstr("M");
1809 }
1810
1811 if (ui->hshow && !ui->hpencil) {
1812 xi = state->common->xinfo[ui->hx + ui->hy*(state->common->params.w+2)];
1813 if (xi >= 0 && !state->common->fixed[xi]) {
1814 if (button == 'g' || button == 'G' || button == '1') {
1815 if (!ui->hcursor) ui->hshow = false;
1816 if (state->guess[xi] == 1)
1817 return ui->hcursor ? NULL : MOVE_UI_UPDATE;
1818 sprintf(buf,"G%d",xi);
1819 return dupstr(buf);
1820 }
1821 if (button == 'v' || button == 'V' || button == '2') {
1822 if (!ui->hcursor) ui->hshow = false;
1823 if (state->guess[xi] == 2)
1824 return ui->hcursor ? NULL : MOVE_UI_UPDATE;
1825 sprintf(buf,"V%d",xi);
1826 return dupstr(buf);
1827 }
1828 if (button == 'z' || button == 'Z' || button == '3') {
1829 if (!ui->hcursor) ui->hshow = false;
1830 if (state->guess[xi] == 4)
1831 return ui->hcursor ? NULL : MOVE_UI_UPDATE;
1832 sprintf(buf,"Z%d",xi);
1833 return dupstr(buf);
1834 }
1835 if (button == 'e' || button == 'E' || button == CURSOR_SELECT2 ||
1836 button == '0' || button == '\b' ) {
1837 if (!ui->hcursor) ui->hshow = false;
1838 if (state->guess[xi] == 7 && state->pencils[xi] == 0)
1839 return ui->hcursor ? NULL : MOVE_UI_UPDATE;
1840 sprintf(buf,"E%d",xi);
1841 return dupstr(buf);
1842 }
1843 }
1844 }
1845
1846 if (IS_CURSOR_MOVE(button)) {
1847 if (ui->hx == 0 && ui->hy == 0) {
1848 ui->hx = 1;
1849 ui->hy = 1;
1850 }
1851 else switch (button) {
1852 case CURSOR_UP: ui->hy -= (ui->hy > 1) ? 1 : 0; break;
1853 case CURSOR_DOWN: ui->hy += (ui->hy < ds->h) ? 1 : 0; break;
1854 case CURSOR_RIGHT: ui->hx += (ui->hx < ds->w) ? 1 : 0; break;
1855 case CURSOR_LEFT: ui->hx -= (ui->hx > 1) ? 1 : 0; break;
1856 }
1857 ui->hshow = true;
1858 ui->hcursor = true;
1859 return MOVE_UI_UPDATE;
1860 }
1861 if (ui->hshow && button == CURSOR_SELECT) {
1862 ui->hpencil = !ui->hpencil;
1863 ui->hcursor = true;
1864 return MOVE_UI_UPDATE;
1865 }
1866
1867 if (ui->hshow && ui->hpencil) {
1868 xi = state->common->xinfo[ui->hx + ui->hy*(state->common->params.w+2)];
1869 if (xi >= 0 && !state->common->fixed[xi]) {
1870 buf[0] = '\0';
1871
1872 if (button == 'g' || button == 'G' || button == '1') {
1873 sprintf(buf,"g%d",xi);
1874 } else if (button == 'v' || button == 'V' || button == '2') {
1875 sprintf(buf,"v%d",xi);
1876 } else if (button == 'z' || button == 'Z' || button == '3') {
1877 sprintf(buf,"z%d",xi);
1878 } else if (button == 'e' || button == 'E' ||
1879 button == CURSOR_SELECT2 || button == '0' ||
1880 button == '\b') {
1881 if (state->pencils[xi] == 0)
1882 return ui->hcursor ? NULL : MOVE_UI_UPDATE;
1883 sprintf(buf,"E%d",xi);
1884 }
1885
1886 if (buf[0]) {
1887 /*
1888 * Hide the highlight after a keypress, if it was mouse-
1889 * generated. Also, don't hide it if this move has changed
1890 * pencil marks and the user preference says not to hide the
1891 * highlight in that situation.
1892 */
1893 if (!ui->hcursor &&
1894 !(ui->hpencil && ui->pencil_keep_highlight)) {
1895 ui->hpencil = false;
1896 ui->hshow = false;
1897 }
1898 return dupstr(buf);
1899 }
1900 }
1901 }
1902
1903 if (gx > 0 && gx < ds->w+1 && gy > 0 && gy < ds->h+1) {
1904 xi = state->common->xinfo[gx+gy*(state->common->params.w+2)];
1905 if (xi >= 0 && !state->common->fixed[xi]) {
1906 g = state->guess[xi];
1907 if (!ui->hshow) {
1908 if (button == LEFT_BUTTON) {
1909 ui->hshow = true;
1910 ui->hpencil = false;
1911 ui->hcursor = false;
1912 ui->hx = gx; ui->hy = gy;
1913 return MOVE_UI_UPDATE;
1914 }
1915 else if (button == RIGHT_BUTTON && g == 7) {
1916 ui->hshow = true;
1917 ui->hpencil = true;
1918 ui->hcursor = false;
1919 ui->hx = gx; ui->hy = gy;
1920 return MOVE_UI_UPDATE;
1921 }
1922 }
1923 else if (ui->hshow) {
1924 if (button == LEFT_BUTTON) {
1925 if (!ui->hpencil) {
1926 if (gx == ui->hx && gy == ui->hy) {
1927 ui->hshow = false;
1928 ui->hpencil = false;
1929 ui->hcursor = false;
1930 ui->hx = 0; ui->hy = 0;
1931 return MOVE_UI_UPDATE;
1932 }
1933 else {
1934 ui->hshow = true;
1935 ui->hpencil = false;
1936 ui->hcursor = false;
1937 ui->hx = gx; ui->hy = gy;
1938 return MOVE_UI_UPDATE;
1939 }
1940 }
1941 else {
1942 ui->hshow = true;
1943 ui->hpencil = false;
1944 ui->hcursor = false;
1945 ui->hx = gx; ui->hy = gy;
1946 return MOVE_UI_UPDATE;
1947 }
1948 }
1949 else if (button == RIGHT_BUTTON) {
1950 if (!ui->hpencil && g == 7) {
1951 ui->hshow = true;
1952 ui->hpencil = true;
1953 ui->hcursor = false;
1954 ui->hx = gx; ui->hy = gy;
1955 return MOVE_UI_UPDATE;
1956 }
1957 else {
1958 if (gx == ui->hx && gy == ui->hy) {
1959 ui->hshow = false;
1960 ui->hpencil = false;
1961 ui->hcursor = false;
1962 ui->hx = 0; ui->hy = 0;
1963 return MOVE_UI_UPDATE;
1964 }
1965 else if (g == 7) {
1966 ui->hshow = true;
1967 ui->hpencil = true;
1968 ui->hcursor = false;
1969 ui->hx = gx; ui->hy = gy;
1970 return MOVE_UI_UPDATE;
1971 }
1972 }
1973 }
1974 }
1975 }
1976 } else if (button == LEFT_BUTTON) {
1977 if (is_clue(state, gx, gy)) {
1978 sprintf(buf, "D%d,%d", gx, gy);
1979 return dupstr(buf);
1980 }
1981 }
1982
1983 return NULL;
1984}
1985
1986static bool check_numbers_draw(game_state *state, int *guess) {
1987 bool valid, filled;
1988 int i,x,y,xy;
1989 int count_ghosts, count_vampires, count_zombies;
1990
1991 count_ghosts = count_vampires = count_zombies = 0;
1992 for (i=0;i<state->common->num_total;i++) {
1993 if (guess[i] == 1) count_ghosts++;
1994 if (guess[i] == 2) count_vampires++;
1995 if (guess[i] == 4) count_zombies++;
1996 }
1997
1998 valid = true;
1999 filled = (count_ghosts + count_vampires + count_zombies >=
2000 state->common->num_total);
2001
2002 if (count_ghosts > state->common->num_ghosts ||
2003 (filled && count_ghosts != state->common->num_ghosts) ) {
2004 valid = false;
2005 state->count_errors[0] = true;
2006 for (x=1;x<state->common->params.w+1;x++)
2007 for (y=1;y<state->common->params.h+1;y++) {
2008 xy = x+y*(state->common->params.w+2);
2009 if (state->common->xinfo[xy] >= 0 &&
2010 guess[state->common->xinfo[xy]] == 1)
2011 state->cell_errors[xy] = true;
2012 }
2013 }
2014 if (count_vampires > state->common->num_vampires ||
2015 (filled && count_vampires != state->common->num_vampires) ) {
2016 valid = false;
2017 state->count_errors[1] = true;
2018 for (x=1;x<state->common->params.w+1;x++)
2019 for (y=1;y<state->common->params.h+1;y++) {
2020 xy = x+y*(state->common->params.w+2);
2021 if (state->common->xinfo[xy] >= 0 &&
2022 guess[state->common->xinfo[xy]] == 2)
2023 state->cell_errors[xy] = true;
2024 }
2025 }
2026 if (count_zombies > state->common->num_zombies ||
2027 (filled && count_zombies != state->common->num_zombies) ) {
2028 valid = false;
2029 state->count_errors[2] = true;
2030 for (x=1;x<state->common->params.w+1;x++)
2031 for (y=1;y<state->common->params.h+1;y++) {
2032 xy = x+y*(state->common->params.w+2);
2033 if (state->common->xinfo[xy] >= 0 &&
2034 guess[state->common->xinfo[xy]] == 4)
2035 state->cell_errors[xy] = true;
2036 }
2037 }
2038
2039 return valid;
2040}
2041
2042static bool check_path_solution(game_state *state, int p) {
2043 int i;
2044 bool mirror;
2045 int count;
2046 bool correct;
2047 int unfilled;
2048
2049 count = 0;
2050 mirror = false;
2051 correct = true;
2052
2053 unfilled = 0;
2054 for (i=0;i<state->common->paths[p].length;i++) {
2055 if (state->common->paths[p].p[i] == -1) mirror = true;
2056 else {
2057 if (state->guess[state->common->paths[p].p[i]] == 1 && mirror)
2058 count++;
2059 else if (state->guess[state->common->paths[p].p[i]] == 2 && !mirror)
2060 count++;
2061 else if (state->guess[state->common->paths[p].p[i]] == 4)
2062 count++;
2063 else if (state->guess[state->common->paths[p].p[i]] == 7)
2064 unfilled++;
2065 }
2066 }
2067
2068 if (count > state->common->paths[p].sightings_start ||
2069 count + unfilled < state->common->paths[p].sightings_start)
2070 {
2071 correct = false;
2072 state->hint_errors[state->common->paths[p].grid_start] = true;
2073 }
2074
2075 count = 0;
2076 mirror = false;
2077 unfilled = 0;
2078 for (i=state->common->paths[p].length-1;i>=0;i--) {
2079 if (state->common->paths[p].p[i] == -1) mirror = true;
2080 else {
2081 if (state->guess[state->common->paths[p].p[i]] == 1 && mirror)
2082 count++;
2083 else if (state->guess[state->common->paths[p].p[i]] == 2 && !mirror)
2084 count++;
2085 else if (state->guess[state->common->paths[p].p[i]] == 4)
2086 count++;
2087 else if (state->guess[state->common->paths[p].p[i]] == 7)
2088 unfilled++;
2089 }
2090 }
2091
2092 if (count > state->common->paths[p].sightings_end ||
2093 count + unfilled < state->common->paths[p].sightings_end)
2094 {
2095 correct = false;
2096 state->hint_errors[state->common->paths[p].grid_end] = true;
2097 }
2098
2099 if (!correct) {
2100 for (i=0;i<state->common->paths[p].length;i++)
2101 state->cell_errors[state->common->paths[p].xy[i]] = true;
2102 }
2103
2104 return correct;
2105}
2106
2107static game_state *execute_move(const game_state *state, const char *move)
2108{
2109 int x,y,n,p,i;
2110 char c;
2111 bool correct;
2112 bool solver;
2113
2114 game_state *ret = dup_game(state);
2115 solver = false;
2116
2117 while (*move) {
2118 c = *move;
2119 if (c == 'S') {
2120 move++;
2121 solver = true;
2122 } else if (c == 'G' || c == 'V' || c == 'Z' || c == 'E' ||
2123 c == 'g' || c == 'v' || c == 'z') {
2124 move++;
2125 if (sscanf(move, "%d%n", &x, &n) != 1) goto badmove;
2126 if (x < 0 || x >= ret->common->num_total) goto badmove;
2127 if (c == 'G') ret->guess[x] = 1;
2128 if (c == 'V') ret->guess[x] = 2;
2129 if (c == 'Z') ret->guess[x] = 4;
2130 if (c == 'E') { ret->guess[x] = 7; ret->pencils[x] = 0; }
2131 if (c == 'g') ret->pencils[x] ^= 1;
2132 if (c == 'v') ret->pencils[x] ^= 2;
2133 if (c == 'z') ret->pencils[x] ^= 4;
2134 move += n;
2135 } else if (c == 'D' && sscanf(move + 1, "%d,%d%n", &x, &y, &n) == 2 &&
2136 is_clue(ret, x, y)) {
2137 ret->hints_done[clue_index(ret, x, y)] ^= 1;
2138 move += n + 1;
2139 } else if (c == 'M') {
2140 /*
2141 * Fill in absolutely all pencil marks in unfilled
2142 * squares, for those who like to play by the rigorous
2143 * approach of starting off in that state and eliminating
2144 * things.
2145 */
2146 for (i = 0; i < ret->common->num_total; i++)
2147 if (ret->guess[i] == 7)
2148 ret->pencils[i] = 7;
2149 move++;
2150 } else {
2151 /* Unknown move type. */
2152 badmove:
2153 free_game(ret);
2154 return NULL;
2155 }
2156 if (*move == ';') move++;
2157 }
2158
2159 correct = true;
2160
2161 for (i=0;i<ret->common->wh;i++) ret->cell_errors[i] = false;
2162 for (i=0;i<2*ret->common->num_paths;i++) ret->hint_errors[i] = false;
2163 for (i=0;i<3;i++) ret->count_errors[i] = false;
2164
2165 if (!check_numbers_draw(ret,ret->guess)) correct = false;
2166
2167 for (p=0;p<state->common->num_paths;p++)
2168 if (!check_path_solution(ret,p)) correct = false;
2169
2170 for (i=0;i<state->common->num_total;i++)
2171 if (!(ret->guess[i] == 1 || ret->guess[i] == 2 ||
2172 ret->guess[i] == 4)) correct = false;
2173
2174 if (correct && !solver) ret->solved = true;
2175 if (solver) ret->cheated = true;
2176
2177 return ret;
2178}
2179
2180/* ----------------------------------------------------------------------
2181 * Drawing routines.
2182 */
2183
2184#define PREFERRED_TILE_SIZE 64
2185
2186static void game_compute_size(const game_params *params, int tilesize,
2187 const game_ui *ui, int *x, int *y)
2188{
2189 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2190 struct { int tilesize; } ads, *ds = &ads;
2191 ads.tilesize = tilesize;
2192
2193 *x = 2*BORDER+(params->w+2)*TILESIZE;
2194 *y = 2*BORDER+(params->h+3)*TILESIZE;
2195 return;
2196}
2197
2198static void game_set_size(drawing *dr, game_drawstate *ds,
2199 const game_params *params, int tilesize)
2200{
2201 ds->tilesize = tilesize;
2202 return;
2203}
2204
2205#define COLOUR(ret, i, r, g, b) ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
2206
2207static float *game_colours(frontend *fe, int *ncolours)
2208{
2209 float *ret = snewn(3 * NCOLOURS, float);
2210
2211 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
2212
2213 ret[COL_GRID * 3 + 0] = 0.0F;
2214 ret[COL_GRID * 3 + 1] = 0.0F;
2215 ret[COL_GRID * 3 + 2] = 0.0F;
2216
2217 ret[COL_TEXT * 3 + 0] = 0.0F;
2218 ret[COL_TEXT * 3 + 1] = 0.0F;
2219 ret[COL_TEXT * 3 + 2] = 0.0F;
2220
2221 ret[COL_ERROR * 3 + 0] = 1.0F;
2222 ret[COL_ERROR * 3 + 1] = 0.0F;
2223 ret[COL_ERROR * 3 + 2] = 0.0F;
2224
2225 ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
2226 ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
2227 ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
2228
2229 ret[COL_FLASH * 3 + 0] = 1.0F;
2230 ret[COL_FLASH * 3 + 1] = 1.0F;
2231 ret[COL_FLASH * 3 + 2] = 1.0F;
2232
2233 ret[COL_GHOST * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2234 ret[COL_GHOST * 3 + 1] = ret[COL_BACKGROUND * 3 + 0];
2235 ret[COL_GHOST * 3 + 2] = ret[COL_BACKGROUND * 3 + 0];
2236
2237 ret[COL_ZOMBIE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2238 ret[COL_ZOMBIE * 3 + 1] = ret[COL_BACKGROUND * 3 + 0];
2239 ret[COL_ZOMBIE * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2240
2241 ret[COL_VAMPIRE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
2242 ret[COL_VAMPIRE * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
2243 ret[COL_VAMPIRE * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
2244
2245 ret[COL_DONE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F;
2246 ret[COL_DONE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F;
2247 ret[COL_DONE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F;
2248
2249 *ncolours = NCOLOURS;
2250 return ret;
2251}
2252
2253static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
2254{
2255 int i;
2256 struct game_drawstate *ds = snew(struct game_drawstate);
2257
2258 ds->tilesize = 0;
2259 ds->started = ds->solved = false;
2260 ds->w = state->common->params.w;
2261 ds->h = state->common->params.h;
2262 ds->ascii = false;
2263
2264 ds->count_errors[0] = false;
2265 ds->count_errors[1] = false;
2266 ds->count_errors[2] = false;
2267
2268 ds->monsters = snewn(state->common->num_total,int);
2269 for (i=0;i<(state->common->num_total);i++)
2270 ds->monsters[i] = 7;
2271 ds->pencils = snewn(state->common->num_total,unsigned char);
2272 for (i=0;i<state->common->num_total;i++)
2273 ds->pencils[i] = 0;
2274
2275 ds->cell_errors = snewn(state->common->wh,bool);
2276 for (i=0;i<state->common->wh;i++)
2277 ds->cell_errors[i] = false;
2278 ds->hint_errors = snewn(2*state->common->num_paths,bool);
2279 for (i=0;i<2*state->common->num_paths;i++)
2280 ds->hint_errors[i] = false;
2281 ds->hints_done = snewn(2 * state->common->num_paths, bool);
2282 memset(ds->hints_done, 0,
2283 2 * state->common->num_paths * sizeof(bool));
2284
2285 ds->hshow = false;
2286 ds->hpencil = false;
2287 ds->hflash = false;
2288 ds->hx = ds->hy = 0;
2289 return ds;
2290}
2291
2292static void game_free_drawstate(drawing *dr, game_drawstate *ds) {
2293 sfree(ds->hints_done);
2294 sfree(ds->hint_errors);
2295 sfree(ds->cell_errors);
2296 sfree(ds->pencils);
2297 sfree(ds->monsters);
2298 sfree(ds);
2299 return;
2300}
2301
2302static void draw_cell_background(drawing *dr, game_drawstate *ds,
2303 const game_state *state, const game_ui *ui,
2304 int x, int y) {
2305
2306 bool hon;
2307 int dx,dy;
2308 dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2309 dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2310
2311 hon = (ui->hshow && x == ui->hx && y == ui->hy);
2312 draw_rect(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1,(hon && !ui->hpencil) ? COL_HIGHLIGHT : COL_BACKGROUND);
2313
2314 if (hon && ui->hpencil) {
2315 int coords[6];
2316 coords[0] = dx-(TILESIZE/2)+1;
2317 coords[1] = dy-(TILESIZE/2)+1;
2318 coords[2] = coords[0] + TILESIZE/2;
2319 coords[3] = coords[1];
2320 coords[4] = coords[0];
2321 coords[5] = coords[1] + TILESIZE/2;
2322 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
2323 }
2324
2325 draw_update(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1);
2326
2327 return;
2328}
2329
2330static void draw_circle_or_point(drawing *dr, int cx, int cy, int radius,
2331 int colour)
2332{
2333 if (radius > 0)
2334 draw_circle(dr, cx, cy, radius, colour, colour);
2335 else
2336 draw_rect(dr, cx, cy, 1, 1, colour);
2337}
2338
2339static void draw_monster(drawing *dr, game_drawstate *ds, int x, int y,
2340 int tilesize, bool hflash, int monster)
2341{
2342 int black = (hflash ? COL_FLASH : COL_TEXT);
2343
2344 if (monster == 1) { /* ghost */
2345 int poly[80], i, j;
2346
2347 clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize/2+1);
2348 draw_circle(dr,x,y,2*tilesize/5, COL_GHOST,black);
2349 unclip(dr);
2350
2351 i = 0;
2352 poly[i++] = x - 2*tilesize/5;
2353 poly[i++] = y-2;
2354 poly[i++] = x - 2*tilesize/5;
2355 poly[i++] = y + 2*tilesize/5;
2356
2357 for (j = 0; j < 3; j++) {
2358 int total = (2*tilesize/5) * 2;
2359 int before = total * j / 3;
2360 int after = total * (j+1) / 3;
2361 int mid = (before + after) / 2;
2362 poly[i++] = x - 2*tilesize/5 + mid;
2363 poly[i++] = y + 2*tilesize/5 - (total / 6);
2364 poly[i++] = x - 2*tilesize/5 + after;
2365 poly[i++] = y + 2*tilesize/5;
2366 }
2367
2368 poly[i++] = x + 2*tilesize/5;
2369 poly[i++] = y-2;
2370
2371 clip(dr,x-(tilesize/2)+2,y,tilesize-3,tilesize-(tilesize/2)-1);
2372 draw_polygon(dr, poly, i/2, COL_GHOST, black);
2373 unclip(dr);
2374
2375 draw_circle(dr,x-tilesize/6,y-tilesize/12,tilesize/10,
2376 COL_BACKGROUND,black);
2377 draw_circle(dr,x+tilesize/6,y-tilesize/12,tilesize/10,
2378 COL_BACKGROUND,black);
2379
2380 draw_circle_or_point(dr,x-tilesize/6+1+tilesize/48,y-tilesize/12,
2381 tilesize/48,black);
2382 draw_circle_or_point(dr,x+tilesize/6+1+tilesize/48,y-tilesize/12,
2383 tilesize/48,black);
2384
2385 } else if (monster == 2) { /* vampire */
2386 int poly[80], i;
2387
2388 clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize/2);
2389 draw_circle(dr,x,y,2*tilesize/5,black,black);
2390 unclip(dr);
2391
2392 clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize/2+1,tilesize/2);
2393 draw_circle(dr,x-tilesize/7,y,2*tilesize/5-tilesize/7,
2394 COL_VAMPIRE,black);
2395 unclip(dr);
2396 clip(dr,x,y-(tilesize/2)+2,tilesize/2+1,tilesize/2);
2397 draw_circle(dr,x+tilesize/7,y,2*tilesize/5-tilesize/7,
2398 COL_VAMPIRE,black);
2399 unclip(dr);
2400
2401 clip(dr,x-(tilesize/2)+2,y,tilesize-3,tilesize/2);
2402 draw_circle(dr,x,y,2*tilesize/5, COL_VAMPIRE,black);
2403 unclip(dr);
2404
2405 draw_circle(dr, x-tilesize/7, y-tilesize/16, tilesize/16,
2406 COL_BACKGROUND, black);
2407 draw_circle(dr, x+tilesize/7, y-tilesize/16, tilesize/16,
2408 COL_BACKGROUND, black);
2409 draw_circle_or_point(dr, x-tilesize/7, y-tilesize/16, tilesize/48,
2410 black);
2411 draw_circle_or_point(dr, x+tilesize/7, y-tilesize/16, tilesize/48,
2412 black);
2413
2414 clip(dr, x-(tilesize/2)+2, y+tilesize/8, tilesize-3, tilesize/4);
2415
2416 i = 0;
2417 poly[i++] = x-3*tilesize/16;
2418 poly[i++] = y+1*tilesize/8;
2419 poly[i++] = x-2*tilesize/16;
2420 poly[i++] = y+7*tilesize/24;
2421 poly[i++] = x-1*tilesize/16;
2422 poly[i++] = y+1*tilesize/8;
2423 draw_polygon(dr, poly, i/2, COL_BACKGROUND, black);
2424 i = 0;
2425 poly[i++] = x+3*tilesize/16;
2426 poly[i++] = y+1*tilesize/8;
2427 poly[i++] = x+2*tilesize/16;
2428 poly[i++] = y+7*tilesize/24;
2429 poly[i++] = x+1*tilesize/16;
2430 poly[i++] = y+1*tilesize/8;
2431 draw_polygon(dr, poly, i/2, COL_BACKGROUND, black);
2432
2433 draw_circle(dr, x, y-tilesize/5, 2*tilesize/5, COL_VAMPIRE, black);
2434 unclip(dr);
2435
2436 } else if (monster == 4) { /* zombie */
2437 draw_circle(dr,x,y,2*tilesize/5, COL_ZOMBIE,black);
2438
2439 draw_line(dr,
2440 x-tilesize/7-tilesize/16, y-tilesize/12-tilesize/16,
2441 x-tilesize/7+tilesize/16, y-tilesize/12+tilesize/16,
2442 black);
2443 draw_line(dr,
2444 x-tilesize/7+tilesize/16, y-tilesize/12-tilesize/16,
2445 x-tilesize/7-tilesize/16, y-tilesize/12+tilesize/16,
2446 black);
2447 draw_line(dr,
2448 x+tilesize/7-tilesize/16, y-tilesize/12-tilesize/16,
2449 x+tilesize/7+tilesize/16, y-tilesize/12+tilesize/16,
2450 black);
2451 draw_line(dr,
2452 x+tilesize/7+tilesize/16, y-tilesize/12-tilesize/16,
2453 x+tilesize/7-tilesize/16, y-tilesize/12+tilesize/16,
2454 black);
2455
2456 clip(dr, x-tilesize/5, y+tilesize/6, 2*tilesize/5+1, tilesize/2);
2457 draw_circle(dr, x-tilesize/15, y+tilesize/6, tilesize/12,
2458 COL_BACKGROUND, black);
2459 unclip(dr);
2460
2461 draw_line(dr, x-tilesize/5, y+tilesize/6, x+tilesize/5, y+tilesize/6,
2462 black);
2463 }
2464
2465 draw_update(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize-3);
2466}
2467
2468static void draw_monster_count(drawing *dr, game_drawstate *ds,
2469 const game_state *state, int c, bool hflash) {
2470 int dx,dy;
2471 char buf[MAX_DIGITS(int) + 1];
2472 char bufm[8];
2473
2474 dy = TILESIZE/4;
2475 dx = BORDER+(ds->w+2)*TILESIZE/2+TILESIZE/4;
2476 switch (c) {
2477 case 0:
2478 sprintf(buf,"%d",state->common->num_ghosts);
2479 sprintf(bufm,"G");
2480 dx -= 3*TILESIZE/2;
2481 break;
2482 case 1:
2483 sprintf(buf,"%d",state->common->num_vampires);
2484 sprintf(bufm,"V");
2485 break;
2486 case 2:
2487 sprintf(buf,"%d",state->common->num_zombies);
2488 sprintf(bufm,"Z");
2489 dx += 3*TILESIZE/2;
2490 break;
2491 }
2492
2493 draw_rect(dr, dx-2*TILESIZE/3, dy, 3*TILESIZE/2, TILESIZE,
2494 COL_BACKGROUND);
2495 if (!ds->ascii) {
2496 draw_monster(dr, ds, dx-TILESIZE/3, dy+TILESIZE/2,
2497 2*TILESIZE/3, hflash, 1<<c);
2498 } else {
2499 draw_text(dr, dx-TILESIZE/3,dy+TILESIZE/2,FONT_VARIABLE,TILESIZE/2,
2500 ALIGN_HCENTRE|ALIGN_VCENTRE,
2501 hflash ? COL_FLASH : COL_TEXT, bufm);
2502 }
2503 draw_text(dr, dx, dy+TILESIZE/2, FONT_VARIABLE, TILESIZE/2,
2504 ALIGN_HLEFT|ALIGN_VCENTRE,
2505 (state->count_errors[c] ? COL_ERROR :
2506 hflash ? COL_FLASH : COL_TEXT), buf);
2507 draw_update(dr, dx-2*TILESIZE/3, dy, 3*TILESIZE/2, TILESIZE);
2508
2509 return;
2510}
2511
2512static void draw_path_hint(drawing *dr, game_drawstate *ds,
2513 const struct game_params *params,
2514 int hint_index, bool hflash, int hint) {
2515 int x, y, color, dx, dy, text_dx, text_dy, text_size;
2516 char buf[MAX_DIGITS(int) + 1];
2517
2518 if (ds->hint_errors[hint_index])
2519 color = COL_ERROR;
2520 else if (hflash)
2521 color = COL_FLASH;
2522 else if (ds->hints_done[hint_index])
2523 color = COL_DONE;
2524 else
2525 color = COL_TEXT;
2526
2527 range2grid(hint_index, params->w, params->h, &x, &y);
2528 /* Upper-left corner of the "tile" */
2529 dx = BORDER + x * TILESIZE;
2530 dy = BORDER + y * TILESIZE + TILESIZE;
2531 /* Center of the "tile" */
2532 text_dx = dx + TILESIZE / 2;
2533 text_dy = dy + TILESIZE / 2;
2534 /* Avoid wiping out the borders of the puzzle */
2535 dx += 2;
2536 dy += 2;
2537 text_size = TILESIZE - 3;
2538
2539 sprintf(buf,"%d", hint);
2540 draw_rect(dr, dx, dy, text_size, text_size, COL_BACKGROUND);
2541 draw_text(dr, text_dx, text_dy, FONT_VARIABLE, TILESIZE / 2,
2542 ALIGN_HCENTRE | ALIGN_VCENTRE, color, buf);
2543 draw_update(dr, dx, dy, text_size, text_size);
2544
2545 return;
2546}
2547
2548static void draw_mirror(drawing *dr, game_drawstate *ds,
2549 const game_state *state, int x, int y,
2550 bool hflash, int mirror) {
2551 int dx,dy,mx1,my1,mx2,my2;
2552 dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2553 dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2554
2555 if (mirror == CELL_MIRROR_L) {
2556 mx1 = dx-(TILESIZE/4);
2557 my1 = dy-(TILESIZE/4);
2558 mx2 = dx+(TILESIZE/4);
2559 my2 = dy+(TILESIZE/4);
2560 }
2561 else {
2562 mx1 = dx-(TILESIZE/4);
2563 my1 = dy+(TILESIZE/4);
2564 mx2 = dx+(TILESIZE/4);
2565 my2 = dy-(TILESIZE/4);
2566 }
2567 draw_thick_line(dr,(float)(TILESIZE/16),mx1,my1,mx2,my2,
2568 hflash ? COL_FLASH : COL_TEXT);
2569 draw_update(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1);
2570
2571 return;
2572}
2573
2574static void draw_big_monster(drawing *dr, game_drawstate *ds,
2575 const game_state *state, int x, int y,
2576 bool hflash, int monster)
2577{
2578 int dx,dy;
2579 char buf[10];
2580 dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2581 dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2582 if (ds->ascii) {
2583 if (monster == 1) sprintf(buf,"G");
2584 else if (monster == 2) sprintf(buf,"V");
2585 else if (monster == 4) sprintf(buf,"Z");
2586 else sprintf(buf," ");
2587 draw_text(dr,dx,dy,FONT_VARIABLE,TILESIZE/2,ALIGN_HCENTRE|ALIGN_VCENTRE,
2588 hflash ? COL_FLASH : COL_TEXT,buf);
2589 draw_update(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,
2590 TILESIZE-3);
2591 }
2592 else {
2593 draw_monster(dr, ds, dx, dy, 3*TILESIZE/4, hflash, monster);
2594 }
2595 return;
2596}
2597
2598static void draw_pencils(drawing *dr, game_drawstate *ds,
2599 const game_state *state, int x, int y, int pencil)
2600{
2601 int dx, dy;
2602 int monsters[4];
2603 int i, j, px, py;
2604 char buf[10];
2605 dx = BORDER+(x* ds->tilesize)+(TILESIZE/4);
2606 dy = BORDER+(y* ds->tilesize)+(TILESIZE/4)+TILESIZE;
2607
2608 for (i = 0, j = 1; j < 8; j *= 2)
2609 if (pencil & j)
2610 monsters[i++] = j;
2611 while (i < 4)
2612 monsters[i++] = 0;
2613
2614 for (py = 0; py < 2; py++)
2615 for (px = 0; px < 2; px++)
2616 if (monsters[py*2+px]) {
2617 if (!ds->ascii) {
2618 draw_monster(dr, ds,
2619 dx + TILESIZE/2 * px, dy + TILESIZE/2 * py,
2620 TILESIZE/2, false, monsters[py*2+px]);
2621 }
2622 else {
2623 switch (monsters[py*2+px]) {
2624 case 1: sprintf(buf,"G"); break;
2625 case 2: sprintf(buf,"V"); break;
2626 case 4: sprintf(buf,"Z"); break;
2627 }
2628 draw_text(dr,dx + TILESIZE/2 * px,dy + TILESIZE/2 * py,
2629 FONT_VARIABLE,TILESIZE/4,ALIGN_HCENTRE|ALIGN_VCENTRE,
2630 COL_TEXT,buf);
2631 }
2632 }
2633 draw_update(dr,dx-(TILESIZE/4)+2,dy-(TILESIZE/4)+2,
2634 (TILESIZE/2)-3,(TILESIZE/2)-3);
2635
2636 return;
2637}
2638
2639#define FLASH_TIME 0.7F
2640
2641static bool is_hint_stale(const game_drawstate *ds, bool hflash,
2642 const game_state *state, int index)
2643{
2644 bool ret = false;
2645 if (!ds->started) ret = true;
2646 if (ds->hflash != hflash) ret = true;
2647
2648 if (ds->hint_errors[index] != state->hint_errors[index]) {
2649 ds->hint_errors[index] = state->hint_errors[index];
2650 ret = true;
2651 }
2652
2653 if (ds->hints_done[index] != state->hints_done[index]) {
2654 ds->hints_done[index] = state->hints_done[index];
2655 ret = true;
2656 }
2657
2658 return ret;
2659}
2660
2661static void game_redraw(drawing *dr, game_drawstate *ds,
2662 const game_state *oldstate, const game_state *state,
2663 int dir, const game_ui *ui,
2664 float animtime, float flashtime)
2665{
2666 int i,j,x,y,xy;
2667 int xi, c;
2668 bool stale, hflash, hchanged, changed_ascii;
2669
2670 hflash = (int)(flashtime * 5 / FLASH_TIME) % 2;
2671
2672 /* Draw static grid components at startup */
2673 if (!ds->started) {
2674 draw_rect(dr, BORDER+TILESIZE-1, BORDER+2*TILESIZE-1,
2675 (ds->w)*TILESIZE +3, (ds->h)*TILESIZE +3, COL_GRID);
2676 for (i=0;i<ds->w;i++)
2677 for (j=0;j<ds->h;j++)
2678 draw_rect(dr, BORDER+(ds->tilesize*(i+1))+1,
2679 BORDER+(ds->tilesize*(j+2))+1, ds->tilesize-1,
2680 ds->tilesize-1, COL_BACKGROUND);
2681 draw_update(dr, 0, 0, 2*BORDER+(ds->w+2)*TILESIZE,
2682 2*BORDER+(ds->h+3)*TILESIZE);
2683 }
2684
2685 hchanged = false;
2686 if (ds->hx != ui->hx || ds->hy != ui->hy ||
2687 ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
2688 hchanged = true;
2689
2690 if (ds->ascii != ui->ascii) {
2691 ds->ascii = ui->ascii;
2692 changed_ascii = true;
2693 } else
2694 changed_ascii = false;
2695
2696 /* Draw monster count hints */
2697
2698 for (i=0;i<3;i++) {
2699 stale = false;
2700 if (!ds->started) stale = true;
2701 if (ds->hflash != hflash) stale = true;
2702 if (changed_ascii) stale = true;
2703 if (ds->count_errors[i] != state->count_errors[i]) {
2704 stale = true;
2705 ds->count_errors[i] = state->count_errors[i];
2706 }
2707
2708 if (stale) {
2709 draw_monster_count(dr, ds, state, i, hflash);
2710 }
2711 }
2712
2713 /* Draw path count hints */
2714 for (i=0;i<state->common->num_paths;i++) {
2715 struct path *path = &state->common->paths[i];
2716
2717 if (is_hint_stale(ds, hflash, state, path->grid_start)) {
2718 draw_path_hint(dr, ds, &state->common->params, path->grid_start,
2719 hflash, path->sightings_start);
2720 }
2721
2722 if (is_hint_stale(ds, hflash, state, path->grid_end)) {
2723 draw_path_hint(dr, ds, &state->common->params, path->grid_end,
2724 hflash, path->sightings_end);
2725 }
2726 }
2727
2728 /* Draw puzzle grid contents */
2729 for (x = 1; x < ds->w+1; x++)
2730 for (y = 1; y < ds->h+1; y++) {
2731 stale = false;
2732 xy = x+y*(state->common->params.w+2);
2733 xi = state->common->xinfo[xy];
2734 c = state->common->grid[xy];
2735
2736 if (!ds->started) stale = true;
2737 if (ds->hflash != hflash) stale = true;
2738 if (changed_ascii) stale = true;
2739
2740 if (hchanged) {
2741 if ((x == ui->hx && y == ui->hy) ||
2742 (x == ds->hx && y == ds->hy))
2743 stale = true;
2744 }
2745
2746 if (xi >= 0 && (state->guess[xi] != ds->monsters[xi]) ) {
2747 stale = true;
2748 ds->monsters[xi] = state->guess[xi];
2749 }
2750
2751 if (xi >= 0 && (state->pencils[xi] != ds->pencils[xi]) ) {
2752 stale = true;
2753 ds->pencils[xi] = state->pencils[xi];
2754 }
2755
2756 if (state->cell_errors[xy] != ds->cell_errors[xy]) {
2757 stale = true;
2758 ds->cell_errors[xy] = state->cell_errors[xy];
2759 }
2760
2761 if (stale) {
2762 draw_cell_background(dr, ds, state, ui, x, y);
2763 if (xi < 0)
2764 draw_mirror(dr, ds, state, x, y, hflash, c);
2765 else if (state->guess[xi] == 1 || state->guess[xi] == 2 ||
2766 state->guess[xi] == 4)
2767 draw_big_monster(dr, ds, state, x, y, hflash, state->guess[xi]);
2768 else
2769 draw_pencils(dr, ds, state, x, y, state->pencils[xi]);
2770 }
2771 }
2772
2773 ds->hx = ui->hx; ds->hy = ui->hy;
2774 ds->hshow = ui->hshow;
2775 ds->hpencil = ui->hpencil;
2776 ds->hflash = hflash;
2777 ds->started = true;
2778 return;
2779}
2780
2781static float game_anim_length(const game_state *oldstate,
2782 const game_state *newstate, int dir, game_ui *ui)
2783{
2784 return 0.0F;
2785}
2786
2787static float game_flash_length(const game_state *oldstate,
2788 const game_state *newstate, int dir, game_ui *ui)
2789{
2790 return (!oldstate->solved && newstate->solved && !oldstate->cheated &&
2791 !newstate->cheated) ? FLASH_TIME : 0.0F;
2792}
2793
2794static void game_get_cursor_location(const game_ui *ui,
2795 const game_drawstate *ds,
2796 const game_state *state,
2797 const game_params *params,
2798 int *x, int *y, int *w, int *h)
2799{
2800 if(ui->hshow) {
2801 *x = BORDER + (ui->hx) * TILESIZE;
2802 *y = BORDER + (ui->hy + 1) * TILESIZE;
2803 *w = *h = TILESIZE;
2804 }
2805}
2806
2807static int game_status(const game_state *state)
2808{
2809 return state->solved;
2810}
2811
2812#ifdef COMBINED
2813#define thegame undead
2814#endif
2815
2816const struct game thegame = {
2817 "Undead", "games.undead", "undead",
2818 default_params,
2819 game_fetch_preset, NULL,
2820 decode_params,
2821 encode_params,
2822 free_params,
2823 dup_params,
2824 true, game_configure, custom_params,
2825 validate_params,
2826 new_game_desc,
2827 validate_desc,
2828 new_game,
2829 dup_game,
2830 free_game,
2831 true, solve_game,
2832 true, game_can_format_as_text_now, game_text_format,
2833 get_prefs, set_prefs,
2834 new_ui,
2835 free_ui,
2836 NULL, /* encode_ui */
2837 NULL, /* decode_ui */
2838 game_request_keys,
2839 game_changed_state,
2840 current_key_label,
2841 interpret_move,
2842 execute_move,
2843 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2844 game_colours,
2845 game_new_drawstate,
2846 game_free_drawstate,
2847 game_redraw,
2848 game_anim_length,
2849 game_flash_length,
2850 game_get_cursor_location,
2851 game_status,
2852 false, false, NULL, NULL, /* print_size, print */
2853 false, /* wants_statusbar */
2854 false, NULL, /* timing_state */
2855 0, /* flags */
2856};