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