undead.c

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