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