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