undead.c

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