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/2)
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     *x = tilesize + (2 + params->w) * tilesize;
1978     *y = tilesize + (3 + params->h) * tilesize;
1979     return;
1980 }
1981
1982 static void game_set_size(drawing *dr, game_drawstate *ds,
1983                           game_params *params, int tilesize) {
1984     ds->tilesize = tilesize;
1985     return;
1986 }
1987
1988 #define COLOUR(ret, i, r, g, b)     ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1989
1990 static float *game_colours(frontend *fe, int *ncolours) {
1991     float *ret = snewn(3 * NCOLOURS, float);
1992
1993     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1994
1995     ret[COL_GRID * 3 + 0] = 0.0F;
1996     ret[COL_GRID * 3 + 1] = 0.0F;
1997     ret[COL_GRID * 3 + 2] = 0.0F;
1998
1999     ret[COL_TEXT * 3 + 0] = 0.0F;
2000     ret[COL_TEXT * 3 + 1] = 0.0F;
2001     ret[COL_TEXT * 3 + 2] = 0.0F;
2002
2003     ret[COL_ERROR * 3 + 0] = 1.0F;
2004     ret[COL_ERROR * 3 + 1] = 0.0F;
2005     ret[COL_ERROR * 3 + 2] = 0.0F;
2006
2007     ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
2008     ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
2009     ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
2010
2011     ret[COL_FLASH * 3 + 0] = 1.0F;
2012     ret[COL_FLASH * 3 + 1] = 1.0F;
2013     ret[COL_FLASH * 3 + 2] = 1.0F;
2014
2015     ret[COL_GHOST * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2016     ret[COL_GHOST * 3 + 1] = ret[COL_BACKGROUND * 3 + 0];
2017     ret[COL_GHOST * 3 + 2] = ret[COL_BACKGROUND * 3 + 0];
2018
2019     ret[COL_ZOMBIE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2020     ret[COL_ZOMBIE * 3 + 1] = ret[COL_BACKGROUND * 3 + 0];
2021     ret[COL_ZOMBIE * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2022
2023     ret[COL_VAMPIRE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
2024     ret[COL_VAMPIRE * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
2025     ret[COL_VAMPIRE * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
2026
2027     *ncolours = NCOLOURS;
2028     return ret;
2029 }
2030
2031 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) {
2032     int i;
2033     struct game_drawstate *ds = snew(struct game_drawstate);
2034
2035     ds->tilesize = 0;
2036     ds->started = ds->solved = FALSE;
2037     ds->w = state->common->params.w;
2038     ds->h = state->common->params.h;
2039     ds->ascii = FALSE;
2040
2041     ds->count_errors[0] = FALSE;
2042     ds->count_errors[1] = FALSE;
2043     ds->count_errors[2] = FALSE;
2044
2045     ds->monsters = snewn(state->common->num_total,int);
2046     for (i=0;i<(state->common->num_total);i++)
2047         ds->monsters[i] = 7;
2048     ds->pencils = snewn(state->common->num_total,unsigned char);
2049     for (i=0;i<state->common->num_total;i++)
2050         ds->pencils[i] = 0;
2051
2052     ds->cell_errors = snewn(state->common->wh,unsigned char);
2053     for (i=0;i<state->common->wh;i++)
2054         ds->cell_errors[i] = FALSE;
2055     ds->hint_errors = snewn(2*state->common->num_paths,unsigned char);
2056     for (i=0;i<2*state->common->num_paths;i++)
2057         ds->hint_errors[i] = FALSE;
2058
2059     ds->hshow = ds->hpencil = ds->hflash = 0;
2060     ds->hx = ds->hy = 0;
2061     return ds;
2062 }
2063
2064 static void game_free_drawstate(drawing *dr, game_drawstate *ds) {
2065     sfree(ds->hint_errors);
2066     sfree(ds->cell_errors);
2067     sfree(ds->pencils);
2068     sfree(ds->monsters);
2069     sfree(ds);
2070     return;
2071 }
2072
2073 static void draw_cell_background(drawing *dr, game_drawstate *ds,
2074                                  game_state *state, game_ui *ui, int x, int y) {
2075
2076     int hon;
2077     int dx,dy;
2078     dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2079     dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2080
2081     hon = (ui->hshow && x == ui->hx && y == ui->hy);
2082     draw_rect(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1,(hon && !ui->hpencil) ? COL_HIGHLIGHT : COL_BACKGROUND);
2083
2084     if (hon && ui->hpencil) {
2085         int coords[6];
2086         coords[0] = dx-(TILESIZE/2)+1;
2087         coords[1] = dy-(TILESIZE/2)+1;
2088         coords[2] = coords[0] + TILESIZE/2;
2089         coords[3] = coords[1];
2090         coords[4] = coords[0];
2091         coords[5] = coords[1] + TILESIZE/2;
2092         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
2093     }
2094
2095     draw_update(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1);
2096
2097     return;
2098 }
2099
2100 static void draw_circle_or_point(drawing *dr, int cx, int cy, int radius,
2101                                  int colour)
2102 {
2103     if (radius > 0)
2104         draw_circle(dr, cx, cy, radius, colour, colour);
2105     else
2106         draw_rect(dr, cx, cy, 1, 1, colour);
2107 }
2108
2109 static void draw_monster(drawing *dr, game_drawstate *ds, int x, int y,
2110                          int tilesize, int hflash, int monster)
2111 {
2112     int black = (hflash ? COL_FLASH : COL_TEXT);
2113
2114     if (monster == 1) {                /* ghost */
2115         int poly[80], i, j;
2116
2117         clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize/2+1);
2118         draw_circle(dr,x,y,2*tilesize/5, COL_GHOST,black);
2119         unclip(dr);
2120
2121         i = 0;
2122         poly[i++] = x - 2*tilesize/5;
2123         poly[i++] = y-2;
2124         poly[i++] = x - 2*tilesize/5;
2125         poly[i++] = y + 2*tilesize/5;
2126
2127         for (j = 0; j < 3; j++) {
2128             int total = (2*tilesize/5) * 2;
2129             int before = total * j / 3;
2130             int after = total * (j+1) / 3;
2131             int mid = (before + after) / 2;
2132             poly[i++] = x - 2*tilesize/5 + mid;
2133             poly[i++] = y + 2*tilesize/5 - (total / 6);
2134             poly[i++] = x - 2*tilesize/5 + after;
2135             poly[i++] = y + 2*tilesize/5;
2136         }
2137
2138         poly[i++] = x + 2*tilesize/5;
2139         poly[i++] = y-2;
2140
2141         clip(dr,x-(tilesize/2)+2,y,tilesize-3,tilesize-(tilesize/2)-1);
2142         draw_polygon(dr, poly, i/2, COL_GHOST, black);
2143         unclip(dr);
2144
2145         draw_circle(dr,x-tilesize/6,y-tilesize/12,tilesize/10,
2146                     COL_BACKGROUND,black);
2147         draw_circle(dr,x+tilesize/6,y-tilesize/12,tilesize/10,
2148                     COL_BACKGROUND,black);
2149
2150         draw_circle_or_point(dr,x-tilesize/6+1+tilesize/48,y-tilesize/12,
2151                              tilesize/48,black);
2152         draw_circle_or_point(dr,x+tilesize/6+1+tilesize/48,y-tilesize/12,
2153                              tilesize/48,black);
2154
2155     } else if (monster == 2) {         /* vampire */
2156         int poly[80], i;
2157
2158         clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize/2);
2159         draw_circle(dr,x,y,2*tilesize/5,black,black);
2160         unclip(dr);
2161
2162         clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize/2+1,tilesize/2);
2163         draw_circle(dr,x-tilesize/7,y,2*tilesize/5-tilesize/7,
2164                     COL_VAMPIRE,black);
2165         unclip(dr);
2166         clip(dr,x,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
2171         clip(dr,x-(tilesize/2)+2,y,tilesize-3,tilesize/2);
2172         draw_circle(dr,x,y,2*tilesize/5, COL_VAMPIRE,black);
2173         unclip(dr);
2174
2175         draw_circle(dr, x-tilesize/7, y-tilesize/16, tilesize/16,
2176                     COL_BACKGROUND, black);
2177         draw_circle(dr, x+tilesize/7, y-tilesize/16, tilesize/16,
2178                     COL_BACKGROUND, black);
2179         draw_circle_or_point(dr, x-tilesize/7, y-tilesize/16, tilesize/48,
2180                              black);
2181         draw_circle_or_point(dr, x+tilesize/7, y-tilesize/16, tilesize/48,
2182                              black);
2183
2184         clip(dr, x-(tilesize/2)+2, y+tilesize/8, tilesize-3, tilesize/4);
2185
2186         i = 0;
2187         poly[i++] = x-3*tilesize/16;
2188         poly[i++] = y+1*tilesize/8;
2189         poly[i++] = x-2*tilesize/16;
2190         poly[i++] = y+7*tilesize/24;
2191         poly[i++] = x-1*tilesize/16;
2192         poly[i++] = y+1*tilesize/8;
2193         draw_polygon(dr, poly, i/2, COL_BACKGROUND, black);
2194         i = 0;
2195         poly[i++] = x+3*tilesize/16;
2196         poly[i++] = y+1*tilesize/8;
2197         poly[i++] = x+2*tilesize/16;
2198         poly[i++] = y+7*tilesize/24;
2199         poly[i++] = x+1*tilesize/16;
2200         poly[i++] = y+1*tilesize/8;
2201         draw_polygon(dr, poly, i/2, COL_BACKGROUND, black);
2202
2203         draw_circle(dr, x, y-tilesize/5, 2*tilesize/5, COL_VAMPIRE, black);
2204         unclip(dr);
2205
2206     } else if (monster == 4) {         /* zombie */
2207         draw_circle(dr,x,y,2*tilesize/5, COL_ZOMBIE,black);
2208
2209         draw_line(dr,
2210                   x-tilesize/7-tilesize/16, y-tilesize/12-tilesize/16,
2211                   x-tilesize/7+tilesize/16, y-tilesize/12+tilesize/16,
2212                   black);
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
2226         clip(dr, x-tilesize/5, y+tilesize/6, 2*tilesize/5+1, tilesize/2);
2227         draw_circle(dr, x-tilesize/15, y+tilesize/6, tilesize/12,
2228                     COL_BACKGROUND, black);
2229         unclip(dr);
2230
2231         draw_line(dr, x-tilesize/5, y+tilesize/6, x+tilesize/5, y+tilesize/6,
2232                   black);
2233     }
2234
2235     draw_update(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize-3);
2236 }
2237
2238 static void draw_monster_count(drawing *dr, game_drawstate *ds,
2239                                game_state *state, int c, int hflash) {
2240     int dx,dy,dh;
2241     char buf[8];
2242     char bufm[8];
2243
2244     dy = TILESIZE/2;
2245     dh = TILESIZE;
2246     dx = BORDER+(ds->w+2)*TILESIZE/2+TILESIZE/4;
2247     switch (c) {
2248       case 0:
2249         sprintf(buf,"%d",state->common->num_ghosts);
2250         sprintf(bufm,"G");
2251         dx -= 3*TILESIZE/2;
2252         break;
2253       case 1:
2254         sprintf(buf,"%d",state->common->num_vampires);
2255         sprintf(bufm,"V");
2256         break;
2257       case 2:
2258         sprintf(buf,"%d",state->common->num_zombies);
2259         sprintf(bufm,"Z");
2260         dx += 3*TILESIZE/2;
2261         break;
2262     }
2263
2264     if (!ds->ascii) {
2265         draw_rect(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh,COL_BACKGROUND);
2266         draw_monster(dr,ds,dx-TILESIZE/3,dh,2*TILESIZE/3,hflash,1<<c);
2267         draw_text(dr,dx,dh,FONT_VARIABLE,dy-1,ALIGN_HLEFT|ALIGN_VCENTRE,
2268                   (state->count_errors[c] ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT), buf);
2269         draw_update(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh);
2270     }
2271     else {
2272         draw_rect(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh,COL_BACKGROUND);
2273         draw_text(dr,dx-TILESIZE/3,dh,FONT_VARIABLE,dy-1,
2274                   ALIGN_HCENTRE|ALIGN_VCENTRE,
2275                   hflash ? COL_FLASH : COL_TEXT, bufm);
2276         draw_text(dr,dx,dh,FONT_VARIABLE,dy-1,ALIGN_HLEFT|ALIGN_VCENTRE,
2277                   (state->count_errors[c] ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT), buf);
2278         draw_update(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh);
2279     }
2280
2281     return;
2282 }
2283
2284 static void draw_path_hint(drawing *dr, game_drawstate *ds, game_state *state,
2285                            int i, int hflash, int start) {
2286     int dx,dy,x,y;
2287     int p,error;
2288     char buf[80];
2289
2290     p = start ? state->common->paths[i].grid_start : state->common->paths[i].grid_end;
2291     range2grid(p,state->common->params.w,state->common->params.h,&x,&y);
2292     error = ds->hint_errors[p];
2293
2294     dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2295     dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2296     sprintf(buf,"%d", start ? state->common->paths[i].sightings_start : state->common->paths[i].sightings_end);
2297     draw_rect(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,TILESIZE-3,COL_BACKGROUND);
2298     draw_text(dr,dx,dy,FONT_FIXED,TILESIZE/2,ALIGN_HCENTRE|ALIGN_VCENTRE, error ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT,buf);
2299     draw_update(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,TILESIZE-3);
2300
2301     return;
2302 }
2303
2304 static void draw_mirror(drawing *dr, game_drawstate *ds, game_state *state,
2305                         int x, int y, int hflash, int mirror) {
2306     int dx,dy,mx1,my1,mx2,my2;
2307     dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2308     dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2309
2310     if (mirror == CELL_MIRROR_L) {
2311         mx1 = dx-(TILESIZE/4);
2312         my1 = dy-(TILESIZE/4);
2313         mx2 = dx+(TILESIZE/4);
2314         my2 = dy+(TILESIZE/4);
2315     }
2316     else {
2317         mx1 = dx-(TILESIZE/4);
2318         my1 = dy+(TILESIZE/4);
2319         mx2 = dx+(TILESIZE/4);
2320         my2 = dy-(TILESIZE/4);
2321     }
2322     draw_thick_line(dr,(float)(TILESIZE/16),mx1,my1,mx2,my2,
2323                     hflash ? COL_FLASH : COL_TEXT);
2324     draw_update(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1);
2325
2326     return;
2327 }
2328
2329 static void draw_big_monster(drawing *dr, game_drawstate *ds, game_state *state,
2330                              int x, int y, int hflash, int monster)
2331 {
2332     int dx,dy;
2333     char buf[10];
2334     dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2335     dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2336     if (ds->ascii) {
2337         if (monster == 1) sprintf(buf,"G");
2338         else if (monster == 2) sprintf(buf,"V");
2339         else if (monster == 4) sprintf(buf,"Z");
2340         else sprintf(buf," ");
2341         draw_text(dr,dx,dy,FONT_FIXED,TILESIZE/2,ALIGN_HCENTRE|ALIGN_VCENTRE,
2342                   hflash ? COL_FLASH : COL_TEXT,buf);
2343         draw_update(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,
2344                     TILESIZE-3);
2345     }
2346     else {
2347         draw_monster(dr, ds, dx, dy, 3*TILESIZE/4, hflash, monster);
2348     }
2349     return;
2350 }
2351
2352 static void draw_pencils(drawing *dr, game_drawstate *ds, game_state *state,
2353                          int x, int y, int pencil) {
2354     int dx, dy;
2355     int monsters[4];
2356     int i, j, px, py;
2357     char buf[10];
2358     dx = BORDER+(x* ds->tilesize)+(TILESIZE/4);
2359     dy = BORDER+(y* ds->tilesize)+(TILESIZE/4)+TILESIZE;
2360
2361     for (i = 0, j = 1; j < 8; j *= 2)
2362         if (pencil & j)
2363             monsters[i++] = j;
2364     while (i < 4)
2365         monsters[i++] = 0;
2366
2367     for (py = 0; py < 2; py++)
2368         for (px = 0; px < 2; px++)
2369             if (monsters[py*2+px]) {
2370                 if (!ds->ascii) {
2371                     draw_monster(dr, ds,
2372                                  dx + TILESIZE/2 * px, dy + TILESIZE/2 * py,
2373                                  TILESIZE/2, 0, monsters[py*2+px]);
2374                 }
2375                 else {
2376                     switch (monsters[py*2+px]) {
2377                       case 1: sprintf(buf,"G"); break;
2378                       case 2: sprintf(buf,"V"); break;
2379                       case 4: sprintf(buf,"Z"); break;
2380                     }
2381                     draw_text(dr,dx + TILESIZE/2 * px,dy + TILESIZE/2 * py,
2382                               FONT_FIXED,TILESIZE/4,ALIGN_HCENTRE|ALIGN_VCENTRE,
2383                               COL_TEXT,buf);
2384                 }
2385             }
2386     draw_update(dr,dx-(TILESIZE/4)+2,dy-(TILESIZE/4)+2,
2387                 (TILESIZE/2)-3,(TILESIZE/2)-3);
2388
2389     return;
2390 }
2391
2392 #define FLASH_TIME 0.7F
2393
2394 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2395                         game_state *state, int dir, game_ui *ui,
2396                         float animtime, float flashtime) {
2397     int i,j,x,y,xy;
2398     int stale, xi, c, hflash, hchanged, changed_ascii;
2399
2400     hflash = (int)(flashtime * 5 / FLASH_TIME) % 2;
2401
2402     /* Draw static grid components at startup */
2403     if (!ds->started) {
2404         draw_rect(dr, 0, 0, 2*BORDER+(ds->w+2)*TILESIZE,
2405                   2*BORDER+(ds->h+3)*TILESIZE, COL_BACKGROUND);
2406         draw_rect(dr, BORDER+TILESIZE-1, BORDER+2*TILESIZE-1,
2407                   (ds->w)*TILESIZE +3, (ds->h)*TILESIZE +3, COL_GRID);
2408         for (i=0;i<ds->w;i++)
2409             for (j=0;j<ds->h;j++)
2410                 draw_rect(dr, BORDER+(ds->tilesize*(i+1))+1,
2411                           BORDER+(ds->tilesize*(j+2))+1, ds->tilesize-1,
2412                           ds->tilesize-1, COL_BACKGROUND);
2413         draw_update(dr,BORDER+TILESIZE-1,BORDER+2*TILESIZE-1,
2414                     (ds->w)*TILESIZE+3, (ds->h)*TILESIZE+3);
2415     }
2416
2417     hchanged = FALSE;
2418     if (ds->hx != ui->hx || ds->hy != ui->hy ||
2419         ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
2420         hchanged = TRUE;
2421
2422     if (ds->ascii != ui->ascii) {
2423         ds->ascii = ui->ascii;
2424         changed_ascii = TRUE;
2425     } else
2426         changed_ascii = FALSE;
2427
2428     /* Draw monster count hints */
2429
2430     for (i=0;i<3;i++) {
2431         stale = FALSE;
2432         if (!ds->started) stale = TRUE;
2433         if (ds->hflash != hflash) stale = TRUE;
2434         if (changed_ascii) stale = TRUE;
2435         if (ds->count_errors[i] != state->count_errors[i]) {
2436             stale = TRUE;
2437             ds->count_errors[i] = state->count_errors[i];
2438         }
2439
2440         if (stale) {
2441             draw_monster_count(dr, ds, state, i, hflash);
2442         }
2443     }
2444
2445     /* Draw path count hints */
2446     for (i=0;i<state->common->num_paths;i++) {
2447         int p;
2448         stale = FALSE;
2449
2450         if (!ds->started) stale = TRUE;
2451         if (ds->hflash != hflash) stale = TRUE;
2452
2453         p = state->common->paths[i].grid_start;
2454         if (ds->hint_errors[p] != state->hint_errors[p]) {
2455             stale = TRUE;
2456             ds->hint_errors[p] = state->hint_errors[p];
2457         }
2458
2459         if (stale) {
2460             draw_path_hint(dr, ds, state, i, hflash, TRUE);
2461         }
2462
2463         stale = FALSE;
2464
2465         if (!ds->started) stale = TRUE;
2466         if (ds->hflash != hflash) stale = TRUE;
2467
2468         p = state->common->paths[i].grid_end;
2469         if (ds->hint_errors[p] != state->hint_errors[p]) {
2470             stale = TRUE;
2471             ds->hint_errors[p] = state->hint_errors[p];
2472         }
2473
2474         if (stale) {
2475             draw_path_hint(dr, ds, state, i, hflash, FALSE);
2476         }
2477
2478     }
2479
2480     /* Draw puzzle grid contents */
2481     for (x = 1; x < ds->w+1; x++)
2482         for (y = 1; y < ds->h+1; y++) {
2483             stale = FALSE;
2484             xy = x+y*(state->common->params.w+2);
2485             xi = state->common->xinfo[xy];
2486             c = state->common->grid[xy];
2487
2488             if (!ds->started) stale = TRUE;
2489             if (ds->hflash != hflash) stale = TRUE;
2490             if (changed_ascii) stale = TRUE;
2491
2492             if (hchanged) {
2493                 if ((x == ui->hx && y == ui->hy) ||
2494                     (x == ds->hx && y == ds->hy))
2495                     stale = TRUE;
2496             }
2497
2498             if (xi >= 0 && (state->guess[xi] != ds->monsters[xi]) ) {
2499                 stale = TRUE;
2500                 ds->monsters[xi] = state->guess[xi];
2501             }
2502
2503             if (xi >= 0 && (state->pencils[xi] != ds->pencils[xi]) ) {
2504                 stale = TRUE;
2505                 ds->pencils[xi] = state->pencils[xi];
2506             }
2507
2508             if (state->cell_errors[xy] != ds->cell_errors[xy]) {
2509                 stale = TRUE;
2510                 ds->cell_errors[xy] = state->cell_errors[xy];
2511             }
2512
2513             if (stale) {
2514                 draw_cell_background(dr, ds, state, ui, x, y);
2515                 if (xi < 0)
2516                     draw_mirror(dr, ds, state, x, y, hflash, c);
2517                 else if (state->guess[xi] == 1 || state->guess[xi] == 2 ||
2518                          state->guess[xi] == 4)
2519                     draw_big_monster(dr, ds, state, x, y, hflash, state->guess[xi]);
2520                 else
2521                     draw_pencils(dr, ds, state, x, y, state->pencils[xi]);
2522             }
2523         }
2524
2525     ds->hx = ui->hx; ds->hy = ui->hy;
2526     ds->hshow = ui->hshow;
2527     ds->hpencil = ui->hpencil;
2528     ds->hflash = hflash;
2529     ds->started = TRUE;
2530     return;
2531 }
2532
2533 static float game_anim_length(game_state *oldstate, game_state *newstate,
2534                               int dir, game_ui *ui) {
2535     return 0.0F;
2536 }
2537
2538 static float game_flash_length(game_state *oldstate, game_state *newstate,
2539                                int dir, game_ui *ui) {
2540     return (!oldstate->solved && newstate->solved && !oldstate->cheated &&
2541             !newstate->cheated) ? FLASH_TIME : 0.0F;
2542 }
2543
2544 static int game_status(game_state *state) {
2545     return state->solved;
2546 }
2547
2548 static int game_timing_state(game_state *state, game_ui *ui) {
2549     return TRUE;
2550 }
2551
2552 static void game_print_size(game_params *params, float *x, float *y) {
2553 }
2554
2555 static void game_print(drawing *dr, game_state *state, int tilesize) {
2556 }
2557
2558 #ifdef COMBINED
2559 #define thegame undead
2560 #endif
2561
2562 const struct game thegame = {
2563     "Undead", "games.undead", "undead",
2564     default_params,
2565     game_fetch_preset,
2566     decode_params,
2567     encode_params,
2568     free_params,
2569     dup_params,
2570     TRUE, game_configure, custom_params,
2571     validate_params,
2572     new_game_desc,
2573     validate_desc,
2574     new_game,
2575     dup_game,
2576     free_game,
2577     TRUE, solve_game,
2578     TRUE, game_can_format_as_text_now, game_text_format,
2579     new_ui,
2580     free_ui,
2581     encode_ui,
2582     decode_ui,
2583     game_changed_state,
2584     interpret_move,
2585     execute_move,
2586     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2587     game_colours,
2588     game_new_drawstate,
2589     game_free_drawstate,
2590     game_redraw,
2591     game_anim_length,
2592     game_flash_length,
2593     game_status,
2594     FALSE, FALSE, game_print_size, game_print,
2595     FALSE,                 /* wants_statusbar */
2596     FALSE, game_timing_state,
2597     0,                     /* flags */
2598 };