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                 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                 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                 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                 if (!ui->hcursor) ui->hshow = 0;
1732                 sprintf(buf,"E%d",xi);
1733                 ui->hpencil = ui->hshow = 0;
1734                 return dupstr(buf);
1735             }
1736         }
1737     }
1738
1739     if (gx > 0 && gx < ds->w+1 && gy > 0 && gy < ds->h+1) {
1740         xi = state->common->xinfo[gx+gy*(state->common->params.w+2)];
1741         if (xi >= 0 && !state->common->fixed[xi]) {
1742             g = state->guess[xi];
1743             if (ui->hshow == 0) {
1744                 if (button == LEFT_BUTTON) {
1745                     ui->hshow = 1; ui->hpencil = 0; ui->hcursor = 0;
1746                     ui->hx = gx; ui->hy = gy;
1747                     return "";
1748                 }
1749                 else if (button == RIGHT_BUTTON && g == 7) {
1750                     ui->hshow = 1; ui->hpencil = 1; ui->hcursor = 0;
1751                     ui->hx = gx; ui->hy = gy;
1752                     return "";
1753                 }
1754             }
1755             else if (ui->hshow == 1) {
1756                 if (button == LEFT_BUTTON) {
1757                     if (ui->hpencil == 0) {
1758                         if (gx == ui->hx && gy == ui->hy) {
1759                             ui->hshow = 0; ui->hpencil = 0; ui->hcursor = 0;
1760                             ui->hx = 0; ui->hy = 0;
1761                             return "";
1762                         }
1763                         else {
1764                             ui->hshow = 1; ui->hpencil = 0; ui->hcursor = 0;
1765                             ui->hx = gx; ui->hy = gy;
1766                             return "";
1767                         }
1768                     }
1769                     else {
1770                         ui->hshow = 1; ui->hpencil = 0; ui->hcursor = 0;
1771                         ui->hx = gx; ui->hy = gy;
1772                         return "";
1773                     }
1774                 }
1775                 else if (button == RIGHT_BUTTON) {
1776                     if (ui->hpencil == 0 && g == 7) {
1777                         ui->hshow = 1; ui->hpencil = 1; ui->hcursor = 0;
1778                         ui->hx = gx; ui->hy = gy;
1779                         return "";
1780                     }
1781                     else {
1782                         if (gx == ui->hx && gy == ui->hy) {
1783                             ui->hshow = 0; ui->hpencil = 0; ui->hcursor = 0;
1784                             ui->hx = 0; ui->hy = 0;
1785                             return "";
1786                         }
1787                         else if (g == 7) {
1788                             ui->hshow = 1; ui->hpencil = 1; ui->hcursor = 0;
1789                             ui->hx = gx; ui->hy = gy;
1790                             return "";
1791                         }
1792                     }
1793                 }
1794             }
1795         }
1796     }
1797
1798     return NULL;
1799 }
1800
1801 int check_numbers_draw(game_state *state, int *guess) {
1802     int valid, filled;
1803     int i,x,y,xy;
1804     int count_ghosts, count_vampires, count_zombies;
1805
1806     count_ghosts = count_vampires = count_zombies = 0;
1807     for (i=0;i<state->common->num_total;i++) {
1808         if (guess[i] == 1) count_ghosts++;
1809         if (guess[i] == 2) count_vampires++;
1810         if (guess[i] == 4) count_zombies++;
1811     }
1812
1813     valid = TRUE;
1814     filled = (count_ghosts + count_vampires + count_zombies >=
1815               state->common->num_total);
1816
1817     if (count_ghosts > state->common->num_ghosts ||
1818         (filled && count_ghosts != state->common->num_ghosts) ) {
1819         valid = FALSE;
1820         state->count_errors[0] = TRUE;
1821         for (x=1;x<state->common->params.w+1;x++)
1822             for (y=1;y<state->common->params.h+1;y++) {
1823                 xy = x+y*(state->common->params.w+2);
1824                 if (state->common->xinfo[xy] >= 0 &&
1825                     guess[state->common->xinfo[xy]] == 1)
1826                     state->cell_errors[xy] = TRUE;
1827             }
1828     }
1829     if (count_vampires > state->common->num_vampires ||
1830         (filled && count_vampires != state->common->num_vampires) ) {
1831         valid = FALSE;
1832         state->count_errors[1] = TRUE;
1833         for (x=1;x<state->common->params.w+1;x++)
1834             for (y=1;y<state->common->params.h+1;y++) {
1835                 xy = x+y*(state->common->params.w+2);
1836                 if (state->common->xinfo[xy] >= 0 &&
1837                     guess[state->common->xinfo[xy]] == 2)
1838                     state->cell_errors[xy] = TRUE;
1839             }
1840     }
1841     if (count_zombies > state->common->num_zombies ||
1842         (filled && count_zombies != state->common->num_zombies) )  {
1843         valid = FALSE;
1844         state->count_errors[2] = TRUE;
1845         for (x=1;x<state->common->params.w+1;x++)
1846             for (y=1;y<state->common->params.h+1;y++) {
1847                 xy = x+y*(state->common->params.w+2);
1848                 if (state->common->xinfo[xy] >= 0 &&
1849                     guess[state->common->xinfo[xy]] == 4)
1850                     state->cell_errors[xy] = TRUE;
1851             }
1852     }
1853
1854     return valid;
1855 }
1856
1857 int check_path_solution(game_state *state, int p) {
1858     int i;
1859     int mirror;
1860     int count;
1861     int correct;
1862     int unfilled;
1863
1864     count = 0;
1865     mirror = FALSE;
1866     correct = TRUE;
1867
1868     unfilled = 0;
1869     for (i=0;i<state->common->paths[p].length;i++) {
1870         if (state->common->paths[p].p[i] == -1) mirror = TRUE;
1871         else {
1872             if (state->guess[state->common->paths[p].p[i]] == 1 && mirror)
1873                 count++;
1874             else if (state->guess[state->common->paths[p].p[i]] == 2 && !mirror)
1875                 count++;
1876             else if (state->guess[state->common->paths[p].p[i]] == 4)
1877                 count++;
1878             else if (state->guess[state->common->paths[p].p[i]] == 7)
1879                 unfilled++;
1880         }
1881     }
1882
1883     if (unfilled == 0 && count != state->common->paths[p].sightings_start) {
1884         correct = FALSE;
1885         state->hint_errors[state->common->paths[p].grid_start] = TRUE;
1886     }
1887
1888     count = 0;
1889     mirror = FALSE;
1890     unfilled = 0;
1891     for (i=state->common->paths[p].length-1;i>=0;i--) {
1892         if (state->common->paths[p].p[i] == -1) mirror = TRUE;
1893         else {
1894             if (state->guess[state->common->paths[p].p[i]] == 1 && mirror)
1895                 count++;
1896             else if (state->guess[state->common->paths[p].p[i]] == 2 && !mirror)
1897                 count++;
1898             else if (state->guess[state->common->paths[p].p[i]] == 4)
1899                 count++;
1900             else if (state->guess[state->common->paths[p].p[i]] == 7)
1901                 unfilled++;
1902         }
1903     }
1904
1905     if (unfilled == 0 && count != state->common->paths[p].sightings_end) {
1906         correct = FALSE;
1907         state->hint_errors[state->common->paths[p].grid_end] = TRUE;
1908     }
1909
1910     if (!correct) {
1911         for (i=0;i<state->common->paths[p].length;i++)
1912             state->cell_errors[state->common->paths[p].xy[i]] = TRUE;
1913     }
1914
1915     return correct;
1916 }
1917
1918 static game_state *execute_move(game_state *state, char *move) {
1919     int x,n,p,i;
1920     char c;
1921     int correct;
1922     int solver;
1923
1924     game_state *ret = dup_game(state);
1925     solver = FALSE;
1926
1927     while (*move) {
1928         c = *move;
1929         if (c == 'S') {
1930             move++;
1931             solver = TRUE;
1932         }
1933         if (c == 'G' || c == 'V' || c == 'Z' || c == 'E' ||
1934             c == 'g' || c == 'v' || c == 'z') {
1935             move++;
1936             sscanf(move, "%d%n", &x, &n);
1937             if (c == 'G') ret->guess[x] = 1;
1938             if (c == 'V') ret->guess[x] = 2;
1939             if (c == 'Z') ret->guess[x] = 4;
1940             if (c == 'E') { ret->guess[x] = 7; ret->pencils[x] = 0; }
1941             if (c == 'g') ret->pencils[x] ^= 1;
1942             if (c == 'v') ret->pencils[x] ^= 2;
1943             if (c == 'z') ret->pencils[x] ^= 4;
1944             move += n;
1945         }
1946         if (*move == ';') move++;
1947     }
1948
1949     correct = TRUE;
1950
1951     for (i=0;i<ret->common->wh;i++) ret->cell_errors[i] = FALSE;
1952     for (i=0;i<2*ret->common->num_paths;i++) ret->hint_errors[i] = FALSE;
1953     for (i=0;i<3;i++) ret->count_errors[i] = FALSE;
1954
1955     if (!check_numbers_draw(ret,ret->guess)) correct = FALSE;
1956
1957     for (p=0;p<state->common->num_paths;p++)
1958         if (!check_path_solution(ret,p)) correct = FALSE;
1959
1960     for (i=0;i<state->common->num_total;i++)
1961         if (!(ret->guess[i] == 1 || ret->guess[i] == 2 ||
1962               ret->guess[i] == 4)) correct = FALSE;
1963
1964     if (correct && !solver) ret->solved = TRUE;
1965     if (solver) ret->cheated = TRUE;
1966
1967     return ret;
1968 }
1969
1970 /* ----------------------------------------------------------------------
1971  * Drawing routines.
1972  */
1973
1974 #define PREFERRED_TILE_SIZE 64
1975
1976 static void game_compute_size(game_params *params, int tilesize,
1977                               int *x, int *y) {
1978     *x = tilesize + (2 + params->w) * tilesize;
1979     *y = tilesize + (3 + params->h) * tilesize;
1980     return;
1981 }
1982
1983 static void game_set_size(drawing *dr, game_drawstate *ds,
1984                           game_params *params, int tilesize) {
1985     ds->tilesize = tilesize;
1986     return;
1987 }
1988
1989 #define COLOUR(ret, i, r, g, b)     ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1990
1991 static float *game_colours(frontend *fe, int *ncolours) {
1992     float *ret = snewn(3 * NCOLOURS, float);
1993
1994     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1995
1996     ret[COL_GRID * 3 + 0] = 0.0F;
1997     ret[COL_GRID * 3 + 1] = 0.0F;
1998     ret[COL_GRID * 3 + 2] = 0.0F;
1999
2000     ret[COL_TEXT * 3 + 0] = 0.0F;
2001     ret[COL_TEXT * 3 + 1] = 0.0F;
2002     ret[COL_TEXT * 3 + 2] = 0.0F;
2003
2004     ret[COL_ERROR * 3 + 0] = 1.0F;
2005     ret[COL_ERROR * 3 + 1] = 0.0F;
2006     ret[COL_ERROR * 3 + 2] = 0.0F;
2007
2008     ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
2009     ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
2010     ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
2011
2012     ret[COL_FLASH * 3 + 0] = 1.0F;
2013     ret[COL_FLASH * 3 + 1] = 1.0F;
2014     ret[COL_FLASH * 3 + 2] = 1.0F;
2015
2016     ret[COL_GHOST * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2017     ret[COL_GHOST * 3 + 1] = ret[COL_BACKGROUND * 3 + 0];
2018     ret[COL_GHOST * 3 + 2] = ret[COL_BACKGROUND * 3 + 0];
2019
2020     ret[COL_ZOMBIE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2021     ret[COL_ZOMBIE * 3 + 1] = ret[COL_BACKGROUND * 3 + 0];
2022     ret[COL_ZOMBIE * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
2023
2024     ret[COL_VAMPIRE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
2025     ret[COL_VAMPIRE * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
2026     ret[COL_VAMPIRE * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
2027
2028     *ncolours = NCOLOURS;
2029     return ret;
2030 }
2031
2032 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) {
2033     int i;
2034     struct game_drawstate *ds = snew(struct game_drawstate);
2035
2036     ds->tilesize = 0;
2037     ds->started = ds->solved = FALSE;
2038     ds->w = state->common->params.w;
2039     ds->h = state->common->params.h;
2040     ds->ascii = FALSE;
2041
2042     ds->count_errors[0] = FALSE;
2043     ds->count_errors[1] = FALSE;
2044     ds->count_errors[2] = FALSE;
2045
2046     ds->monsters = snewn(state->common->num_total,int);
2047     for (i=0;i<(state->common->num_total);i++)
2048         ds->monsters[i] = 7;
2049     ds->pencils = snewn(state->common->num_total,unsigned char);
2050     for (i=0;i<state->common->num_total;i++)
2051         ds->pencils[i] = 0;
2052
2053     ds->cell_errors = snewn(state->common->wh,unsigned char);
2054     for (i=0;i<state->common->wh;i++)
2055         ds->cell_errors[i] = FALSE;
2056     ds->hint_errors = snewn(2*state->common->num_paths,unsigned char);
2057     for (i=0;i<2*state->common->num_paths;i++)
2058         ds->hint_errors[i] = FALSE;
2059
2060     ds->hshow = ds->hpencil = ds->hflash = 0;
2061     ds->hx = ds->hy = 0;
2062     return ds;
2063 }
2064
2065 static void game_free_drawstate(drawing *dr, game_drawstate *ds) {
2066     sfree(ds->hint_errors);
2067     sfree(ds->cell_errors);
2068     sfree(ds->pencils);
2069     sfree(ds->monsters);
2070     sfree(ds);
2071     return;
2072 }
2073
2074 static void draw_cell_background(drawing *dr, game_drawstate *ds,
2075                                  game_state *state, game_ui *ui, int x, int y) {
2076
2077     int hon;
2078     int dx,dy;
2079     dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2080     dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2081
2082     hon = (ui->hshow && x == ui->hx && y == ui->hy);
2083     draw_rect(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1,(hon && !ui->hpencil) ? COL_HIGHLIGHT : COL_BACKGROUND);
2084
2085     if (hon && ui->hpencil) {
2086         int coords[6];
2087         coords[0] = dx-(TILESIZE/2)+1;
2088         coords[1] = dy-(TILESIZE/2)+1;
2089         coords[2] = coords[0] + TILESIZE/2;
2090         coords[3] = coords[1];
2091         coords[4] = coords[0];
2092         coords[5] = coords[1] + TILESIZE/2;
2093         draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
2094     }
2095
2096     draw_update(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1);
2097
2098     return;
2099 }
2100
2101 static void draw_circle_or_point(drawing *dr, int cx, int cy, int radius,
2102                                  int colour)
2103 {
2104     if (radius > 0)
2105         draw_circle(dr, cx, cy, radius, colour, colour);
2106     else
2107         draw_rect(dr, cx, cy, 1, 1, colour);
2108 }
2109
2110 static void draw_monster(drawing *dr, game_drawstate *ds, int x, int y,
2111                          int tilesize, int hflash, int monster)
2112 {
2113     int black = (hflash ? COL_FLASH : COL_TEXT);
2114
2115     if (monster == 1) {                /* ghost */
2116         int poly[80], i, j;
2117
2118         clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize/2+1);
2119         draw_circle(dr,x,y,2*tilesize/5, COL_GHOST,black);
2120         unclip(dr);
2121
2122         i = 0;
2123         poly[i++] = x - 2*tilesize/5;
2124         poly[i++] = y-2;
2125         poly[i++] = x - 2*tilesize/5;
2126         poly[i++] = y + 2*tilesize/5;
2127
2128         for (j = 0; j < 3; j++) {
2129             int total = (2*tilesize/5) * 2;
2130             int before = total * j / 3;
2131             int after = total * (j+1) / 3;
2132             int mid = (before + after) / 2;
2133             poly[i++] = x - 2*tilesize/5 + mid;
2134             poly[i++] = y + 2*tilesize/5 - (total / 6);
2135             poly[i++] = x - 2*tilesize/5 + after;
2136             poly[i++] = y + 2*tilesize/5;
2137         }
2138
2139         poly[i++] = x + 2*tilesize/5;
2140         poly[i++] = y-2;
2141
2142         clip(dr,x-(tilesize/2)+2,y,tilesize-3,tilesize-(tilesize/2)-1);
2143         draw_polygon(dr, poly, i/2, COL_GHOST, black);
2144         unclip(dr);
2145
2146         draw_circle(dr,x-tilesize/6,y-tilesize/12,tilesize/10,
2147                     COL_BACKGROUND,black);
2148         draw_circle(dr,x+tilesize/6,y-tilesize/12,tilesize/10,
2149                     COL_BACKGROUND,black);
2150
2151         draw_circle_or_point(dr,x-tilesize/6+1+tilesize/48,y-tilesize/12,
2152                              tilesize/48,black);
2153         draw_circle_or_point(dr,x+tilesize/6+1+tilesize/48,y-tilesize/12,
2154                              tilesize/48,black);
2155
2156     } else if (monster == 2) {         /* vampire */
2157         int poly[80], i;
2158
2159         clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize/2);
2160         draw_circle(dr,x,y,2*tilesize/5,black,black);
2161         unclip(dr);
2162
2163         clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize/2+1,tilesize/2);
2164         draw_circle(dr,x-tilesize/7,y,2*tilesize/5-tilesize/7,
2165                     COL_VAMPIRE,black);
2166         unclip(dr);
2167         clip(dr,x,y-(tilesize/2)+2,tilesize/2+1,tilesize/2);
2168         draw_circle(dr,x+tilesize/7,y,2*tilesize/5-tilesize/7,
2169                     COL_VAMPIRE,black);
2170         unclip(dr);
2171
2172         clip(dr,x-(tilesize/2)+2,y,tilesize-3,tilesize/2);
2173         draw_circle(dr,x,y,2*tilesize/5, COL_VAMPIRE,black);
2174         unclip(dr);
2175
2176         draw_circle(dr, x-tilesize/7, y-tilesize/16, tilesize/16,
2177                     COL_BACKGROUND, black);
2178         draw_circle(dr, x+tilesize/7, y-tilesize/16, tilesize/16,
2179                     COL_BACKGROUND, black);
2180         draw_circle_or_point(dr, x-tilesize/7, y-tilesize/16, tilesize/48,
2181                              black);
2182         draw_circle_or_point(dr, x+tilesize/7, y-tilesize/16, tilesize/48,
2183                              black);
2184
2185         clip(dr, x-(tilesize/2)+2, y+tilesize/8, tilesize-3, tilesize/4);
2186
2187         i = 0;
2188         poly[i++] = x-3*tilesize/16;
2189         poly[i++] = y+1*tilesize/8;
2190         poly[i++] = x-2*tilesize/16;
2191         poly[i++] = y+7*tilesize/24;
2192         poly[i++] = x-1*tilesize/16;
2193         poly[i++] = y+1*tilesize/8;
2194         draw_polygon(dr, poly, i/2, COL_BACKGROUND, black);
2195         i = 0;
2196         poly[i++] = x+3*tilesize/16;
2197         poly[i++] = y+1*tilesize/8;
2198         poly[i++] = x+2*tilesize/16;
2199         poly[i++] = y+7*tilesize/24;
2200         poly[i++] = x+1*tilesize/16;
2201         poly[i++] = y+1*tilesize/8;
2202         draw_polygon(dr, poly, i/2, COL_BACKGROUND, black);
2203
2204         draw_circle(dr, x, y-tilesize/5, 2*tilesize/5, COL_VAMPIRE, black);
2205         unclip(dr);
2206
2207     } else if (monster == 4) {         /* zombie */
2208         draw_circle(dr,x,y,2*tilesize/5, COL_ZOMBIE,black);
2209
2210         draw_line(dr,
2211                   x-tilesize/7-tilesize/16, y-tilesize/12-tilesize/16,
2212                   x-tilesize/7+tilesize/16, y-tilesize/12+tilesize/16,
2213                   black);
2214         draw_line(dr,
2215                   x-tilesize/7+tilesize/16, y-tilesize/12-tilesize/16,
2216                   x-tilesize/7-tilesize/16, y-tilesize/12+tilesize/16,
2217                   black);
2218         draw_line(dr,
2219                   x+tilesize/7-tilesize/16, y-tilesize/12-tilesize/16,
2220                   x+tilesize/7+tilesize/16, y-tilesize/12+tilesize/16,
2221                   black);
2222         draw_line(dr,
2223                   x+tilesize/7+tilesize/16, y-tilesize/12-tilesize/16,
2224                   x+tilesize/7-tilesize/16, y-tilesize/12+tilesize/16,
2225                   black);
2226
2227         clip(dr, x-tilesize/5, y+tilesize/6, 2*tilesize/5+1, tilesize/2);
2228         draw_circle(dr, x-tilesize/15, y+tilesize/6, tilesize/12,
2229                     COL_BACKGROUND, black);
2230         unclip(dr);
2231
2232         draw_line(dr, x-tilesize/5, y+tilesize/6, x+tilesize/5, y+tilesize/6,
2233                   black);
2234     }
2235
2236     draw_update(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize-3);
2237 }
2238
2239 static void draw_monster_count(drawing *dr, game_drawstate *ds,
2240                                game_state *state, int c, int hflash) {
2241     int dx,dy,dh;
2242     char buf[8];
2243     char bufm[8];
2244
2245     dy = TILESIZE/2;
2246     dh = TILESIZE;
2247     dx = BORDER+(ds->w+2)*TILESIZE/2+TILESIZE/4;
2248     switch (c) {
2249       case 0:
2250         sprintf(buf,"%d",state->common->num_ghosts);
2251         sprintf(bufm,"G");
2252         dx -= 3*TILESIZE/2;
2253         break;
2254       case 1:
2255         sprintf(buf,"%d",state->common->num_vampires);
2256         sprintf(bufm,"V");
2257         break;
2258       case 2:
2259         sprintf(buf,"%d",state->common->num_zombies);
2260         sprintf(bufm,"Z");
2261         dx += 3*TILESIZE/2;
2262         break;
2263     }
2264
2265     if (!ds->ascii) {
2266         draw_rect(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh,COL_BACKGROUND);
2267         draw_monster(dr,ds,dx-TILESIZE/3,dh,2*TILESIZE/3,hflash,1<<c);
2268         draw_text(dr,dx,dh,FONT_VARIABLE,dy-1,ALIGN_HLEFT|ALIGN_VCENTRE,
2269                   (state->count_errors[c] ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT), buf);
2270         draw_update(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh);
2271     }
2272     else {
2273         draw_rect(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh,COL_BACKGROUND);
2274         draw_text(dr,dx-TILESIZE/3,dh,FONT_VARIABLE,dy-1,
2275                   ALIGN_HCENTRE|ALIGN_VCENTRE,
2276                   hflash ? COL_FLASH : COL_TEXT, bufm);
2277         draw_text(dr,dx,dh,FONT_VARIABLE,dy-1,ALIGN_HLEFT|ALIGN_VCENTRE,
2278                   (state->count_errors[c] ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT), buf);
2279         draw_update(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh);
2280     }
2281
2282     return;
2283 }
2284
2285 static void draw_path_hint(drawing *dr, game_drawstate *ds, game_state *state,
2286                            int i, int hflash, int start) {
2287     int dx,dy,x,y;
2288     int p,error;
2289     char buf[80];
2290
2291     p = start ? state->common->paths[i].grid_start : state->common->paths[i].grid_end;
2292     range2grid(p,state->common->params.w,state->common->params.h,&x,&y);
2293     error = ds->hint_errors[p];
2294
2295     dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2296     dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2297     sprintf(buf,"%d", start ? state->common->paths[i].sightings_start : state->common->paths[i].sightings_end);
2298     draw_rect(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,TILESIZE-3,COL_BACKGROUND);
2299     draw_text(dr,dx,dy,FONT_FIXED,TILESIZE/2,ALIGN_HCENTRE|ALIGN_VCENTRE, error ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT,buf);
2300     draw_update(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,TILESIZE-3);
2301
2302     return;
2303 }
2304
2305 static void draw_mirror(drawing *dr, game_drawstate *ds, game_state *state,
2306                         int x, int y, int hflash, int mirror) {
2307     int dx,dy,mx1,my1,mx2,my2;
2308     dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2309     dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2310
2311     if (mirror == CELL_MIRROR_L) {
2312         mx1 = dx-(TILESIZE/4);
2313         my1 = dy-(TILESIZE/4);
2314         mx2 = dx+(TILESIZE/4);
2315         my2 = dy+(TILESIZE/4);
2316     }
2317     else {
2318         mx1 = dx-(TILESIZE/4);
2319         my1 = dy+(TILESIZE/4);
2320         mx2 = dx+(TILESIZE/4);
2321         my2 = dy-(TILESIZE/4);
2322     }
2323     draw_thick_line(dr,(float)(TILESIZE/16),mx1,my1,mx2,my2,
2324                     hflash ? COL_FLASH : COL_TEXT);
2325     draw_update(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1);
2326
2327     return;
2328 }
2329
2330 static void draw_big_monster(drawing *dr, game_drawstate *ds, game_state *state,
2331                              int x, int y, int hflash, int monster)
2332 {
2333     int dx,dy;
2334     char buf[10];
2335     dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
2336     dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
2337     if (ds->ascii) {
2338         if (monster == 1) sprintf(buf,"G");
2339         else if (monster == 2) sprintf(buf,"V");
2340         else if (monster == 4) sprintf(buf,"Z");
2341         else sprintf(buf," ");
2342         draw_text(dr,dx,dy,FONT_FIXED,TILESIZE/2,ALIGN_HCENTRE|ALIGN_VCENTRE,
2343                   hflash ? COL_FLASH : COL_TEXT,buf);
2344         draw_update(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,
2345                     TILESIZE-3);
2346     }
2347     else {
2348         draw_monster(dr, ds, dx, dy, 3*TILESIZE/4, hflash, monster);
2349     }
2350     return;
2351 }
2352
2353 static void draw_pencils(drawing *dr, game_drawstate *ds, game_state *state,
2354                          int x, int y, int pencil) {
2355     int dx, dy;
2356     int monsters[4];
2357     int i, j, px, py;
2358     char buf[10];
2359     dx = BORDER+(x* ds->tilesize)+(TILESIZE/4);
2360     dy = BORDER+(y* ds->tilesize)+(TILESIZE/4)+TILESIZE;
2361
2362     for (i = 0, j = 1; j < 8; j *= 2)
2363         if (pencil & j)
2364             monsters[i++] = j;
2365     while (i < 4)
2366         monsters[i++] = 0;
2367
2368     for (py = 0; py < 2; py++)
2369         for (px = 0; px < 2; px++)
2370             if (monsters[py*2+px]) {
2371                 if (!ds->ascii) {
2372                     draw_monster(dr, ds,
2373                                  dx + TILESIZE/2 * px, dy + TILESIZE/2 * py,
2374                                  TILESIZE/2, 0, monsters[py*2+px]);
2375                 }
2376                 else {
2377                     switch (monsters[py*2+px]) {
2378                       case 1: sprintf(buf,"G"); break;
2379                       case 2: sprintf(buf,"V"); break;
2380                       case 4: sprintf(buf,"Z"); break;
2381                     }
2382                     draw_text(dr,dx + TILESIZE/2 * px,dy + TILESIZE/2 * py,
2383                               FONT_FIXED,TILESIZE/4,ALIGN_HCENTRE|ALIGN_VCENTRE,
2384                               COL_TEXT,buf);
2385                 }
2386             }
2387     draw_update(dr,dx-(TILESIZE/4)+2,dy-(TILESIZE/4)+2,
2388                 (TILESIZE/2)-3,(TILESIZE/2)-3);
2389
2390     return;
2391 }
2392
2393 #define FLASH_TIME 0.7F
2394
2395 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
2396                         game_state *state, int dir, game_ui *ui,
2397                         float animtime, float flashtime) {
2398     int i,j,x,y,xy;
2399     int stale, xi, c, hflash, hchanged, changed_ascii;
2400
2401     hflash = (int)(flashtime * 5 / FLASH_TIME) % 2;
2402
2403     /* Draw static grid components at startup */
2404     if (!ds->started) {
2405         draw_rect(dr, 0, 0, 2*BORDER+(ds->w+2)*TILESIZE,
2406                   2*BORDER+(ds->h+3)*TILESIZE, COL_BACKGROUND);
2407         draw_rect(dr, BORDER+TILESIZE-1, BORDER+2*TILESIZE-1,
2408                   (ds->w)*TILESIZE +3, (ds->h)*TILESIZE +3, COL_GRID);
2409         for (i=0;i<ds->w;i++)
2410             for (j=0;j<ds->h;j++)
2411                 draw_rect(dr, BORDER+(ds->tilesize*(i+1))+1,
2412                           BORDER+(ds->tilesize*(j+2))+1, ds->tilesize-1,
2413                           ds->tilesize-1, COL_BACKGROUND);
2414         draw_update(dr,BORDER+TILESIZE-1,BORDER+2*TILESIZE-1,
2415                     (ds->w)*TILESIZE+3, (ds->h)*TILESIZE+3);
2416     }
2417
2418     hchanged = FALSE;
2419     if (ds->hx != ui->hx || ds->hy != ui->hy ||
2420         ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
2421         hchanged = TRUE;
2422
2423     if (ds->ascii != ui->ascii) {
2424         ds->ascii = ui->ascii;
2425         changed_ascii = TRUE;
2426     } else
2427         changed_ascii = FALSE;
2428
2429     /* Draw monster count hints */
2430
2431     for (i=0;i<3;i++) {
2432         stale = FALSE;
2433         if (!ds->started) stale = TRUE;
2434         if (ds->hflash != hflash) stale = TRUE;
2435         if (changed_ascii) stale = TRUE;
2436         if (ds->count_errors[i] != state->count_errors[i]) {
2437             stale = TRUE;
2438             ds->count_errors[i] = state->count_errors[i];
2439         }
2440
2441         if (stale) {
2442             draw_monster_count(dr, ds, state, i, hflash);
2443         }
2444     }
2445
2446     /* Draw path count hints */
2447     for (i=0;i<state->common->num_paths;i++) {
2448         int p;
2449         stale = FALSE;
2450
2451         if (!ds->started) stale = TRUE;
2452         if (ds->hflash != hflash) stale = TRUE;
2453
2454         p = state->common->paths[i].grid_start;
2455         if (ds->hint_errors[p] != state->hint_errors[p]) {
2456             stale = TRUE;
2457             ds->hint_errors[p] = state->hint_errors[p];
2458         }
2459
2460         if (stale) {
2461             draw_path_hint(dr, ds, state, i, hflash, TRUE);
2462         }
2463
2464         stale = FALSE;
2465
2466         if (!ds->started) stale = TRUE;
2467         if (ds->hflash != hflash) stale = TRUE;
2468
2469         p = state->common->paths[i].grid_end;
2470         if (ds->hint_errors[p] != state->hint_errors[p]) {
2471             stale = TRUE;
2472             ds->hint_errors[p] = state->hint_errors[p];
2473         }
2474
2475         if (stale) {
2476             draw_path_hint(dr, ds, state, i, hflash, FALSE);
2477         }
2478
2479     }
2480
2481     /* Draw puzzle grid contents */
2482     for (x = 1; x < ds->w+1; x++)
2483         for (y = 1; y < ds->h+1; y++) {
2484             stale = FALSE;
2485             xy = x+y*(state->common->params.w+2);
2486             xi = state->common->xinfo[xy];
2487             c = state->common->grid[xy];
2488
2489             if (!ds->started) stale = TRUE;
2490             if (ds->hflash != hflash) stale = TRUE;
2491             if (changed_ascii) stale = TRUE;
2492
2493             if (hchanged) {
2494                 if ((x == ui->hx && y == ui->hy) ||
2495                     (x == ds->hx && y == ds->hy))
2496                     stale = TRUE;
2497             }
2498
2499             if (xi >= 0 && (state->guess[xi] != ds->monsters[xi]) ) {
2500                 stale = TRUE;
2501                 ds->monsters[xi] = state->guess[xi];
2502             }
2503
2504             if (xi >= 0 && (state->pencils[xi] != ds->pencils[xi]) ) {
2505                 stale = TRUE;
2506                 ds->pencils[xi] = state->pencils[xi];
2507             }
2508
2509             if (state->cell_errors[xy] != ds->cell_errors[xy]) {
2510                 stale = TRUE;
2511                 ds->cell_errors[xy] = state->cell_errors[xy];
2512             }
2513
2514             if (stale) {
2515                 draw_cell_background(dr, ds, state, ui, x, y);
2516                 if (xi < 0)
2517                     draw_mirror(dr, ds, state, x, y, hflash, c);
2518                 else if (state->guess[xi] == 1 || state->guess[xi] == 2 ||
2519                          state->guess[xi] == 4)
2520                     draw_big_monster(dr, ds, state, x, y, hflash, state->guess[xi]);
2521                 else
2522                     draw_pencils(dr, ds, state, x, y, state->pencils[xi]);
2523             }
2524         }
2525
2526     ds->hx = ui->hx; ds->hy = ui->hy;
2527     ds->hshow = ui->hshow;
2528     ds->hpencil = ui->hpencil;
2529     ds->hflash = hflash;
2530     ds->started = TRUE;
2531     return;
2532 }
2533
2534 static float game_anim_length(game_state *oldstate, game_state *newstate,
2535                               int dir, game_ui *ui) {
2536     return 0.0F;
2537 }
2538
2539 static float game_flash_length(game_state *oldstate, game_state *newstate,
2540                                int dir, game_ui *ui) {
2541     return (!oldstate->solved && newstate->solved && !oldstate->cheated &&
2542             !newstate->cheated) ? FLASH_TIME : 0.0F;
2543 }
2544
2545 static int game_status(game_state *state) {
2546     return state->solved;
2547 }
2548
2549 static int game_timing_state(game_state *state, game_ui *ui) {
2550     return TRUE;
2551 }
2552
2553 static void game_print_size(game_params *params, float *x, float *y) {
2554 }
2555
2556 static void game_print(drawing *dr, game_state *state, int tilesize) {
2557 }
2558
2559 #ifdef COMBINED
2560 #define thegame undead
2561 #endif
2562
2563 const struct game thegame = {
2564     "Undead", "games.undead", "undead",
2565     default_params,
2566     game_fetch_preset,
2567     decode_params,
2568     encode_params,
2569     free_params,
2570     dup_params,
2571     TRUE, game_configure, custom_params,
2572     validate_params,
2573     new_game_desc,
2574     validate_desc,
2575     new_game,
2576     dup_game,
2577     free_game,
2578     TRUE, solve_game,
2579     TRUE, game_can_format_as_text_now, game_text_format,
2580     new_ui,
2581     free_ui,
2582     encode_ui,
2583     decode_ui,
2584     game_changed_state,
2585     interpret_move,
2586     execute_move,
2587     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2588     game_colours,
2589     game_new_drawstate,
2590     game_free_drawstate,
2591     game_redraw,
2592     game_anim_length,
2593     game_flash_length,
2594     game_status,
2595     FALSE, FALSE, game_print_size, game_print,
2596     FALSE,                 /* wants_statusbar */
2597     FALSE, game_timing_state,
2598     0,                     /* flags */
2599 };
2600