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