pattern.c

   1 /*
   2  * pattern.c: the pattern-reconstruction game known as `nonograms'.
   3  *
   4  * TODO before checkin:
   5  *
   6  *  - make some sort of stab at number-of-numbers judgment
   7  */
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <assert.h>
  13 #include <ctype.h>
  14 #include <math.h>
  15
  16 #include "puzzles.h"
  17
  18 #define max(x,y) ( (x)>(y) ? (x):(y) )
  19 #define min(x,y) ( (x)<(y) ? (x):(y) )
  20
  21 const char *const game_name = "Pattern";
  22 const char *const game_winhelp_topic = "games.pattern";
  23 const int game_can_configure = TRUE;
  24
  25 enum {
  26     COL_BACKGROUND,
  27     COL_EMPTY,
  28     COL_FULL,
  29     COL_UNKNOWN,
  30     COL_GRID,
  31     NCOLOURS
  32 };
  33
  34 #define BORDER 18
  35 #define TLBORDER(d) ( (d) / 5 + 2 )
  36 #define GUTTER 12
  37 #define TILE_SIZE 24
  38
  39 #define FROMCOORD(d, x) \
  40         ( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE )
  41
  42 #define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d)))
  43
  44 #define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x)))
  45
  46 struct game_params {
  47     int w, h;
  48 };
  49
  50 #define GRID_UNKNOWN 2
  51 #define GRID_FULL 1
  52 #define GRID_EMPTY 0
  53
  54 struct game_state {
  55     int w, h;
  56     unsigned char *grid;
  57     int rowsize;
  58     int *rowdata, *rowlen;
  59     int completed;
  60 };
  61
  62 #define FLASH_TIME 0.13F
  63
  64 game_params *default_params(void)
  65 {
  66     game_params *ret = snew(game_params);
  67
  68     ret->w = ret->h = 15;
  69
  70     return ret;
  71 }
  72
  73 int game_fetch_preset(int i, char **name, game_params **params)
  74 {
  75     game_params *ret;
  76     char str[80];
  77     static const struct { int x, y; } values[] = {
  78         {10, 10},
  79         {15, 15},
  80         {20, 20},
  81         {25, 25},
  82         {30, 30},
  83     };
  84
  85     if (i < 0 || i >= lenof(values))
  86         return FALSE;
  87
  88     ret = snew(game_params);
  89     ret->w = values[i].x;
  90     ret->h = values[i].y;
  91
  92     sprintf(str, "%dx%d", ret->w, ret->h);
  93
  94     *name = dupstr(str);
  95     *params = ret;
  96     return TRUE;
  97 }
  98
  99 void free_params(game_params *params)
 100 {
 101     sfree(params);
 102 }
 103
 104 game_params *dup_params(game_params *params)
 105 {
 106     game_params *ret = snew(game_params);
 107     *ret = *params;                    /* structure copy */
 108     return ret;
 109 }
 110
 111 game_params *decode_params(char const *string)
 112 {
 113     game_params *ret = default_params();
 114     char const *p = string;
 115
 116     ret->w = atoi(p);
 117     while (*p && isdigit(*p)) p++;
 118     if (*p == 'x') {
 119         p++;
 120         ret->h = atoi(p);
 121         while (*p && isdigit(*p)) p++;
 122     } else {
 123         ret->h = ret->w;
 124     }
 125
 126     return ret;
 127 }
 128
 129 char *encode_params(game_params *params)
 130 {
 131     char ret[400];
 132     int len;
 133
 134     len = sprintf(ret, "%dx%d", params->w, params->h);
 135     assert(len < lenof(ret));
 136     ret[len] = '\0';
 137
 138     return dupstr(ret);
 139 }
 140
 141 config_item *game_configure(game_params *params)
 142 {
 143     config_item *ret;
 144     char buf[80];
 145
 146     ret = snewn(3, config_item);
 147
 148     ret[0].name = "Width";
 149     ret[0].type = C_STRING;
 150     sprintf(buf, "%d", params->w);
 151     ret[0].sval = dupstr(buf);
 152     ret[0].ival = 0;
 153
 154     ret[1].name = "Height";
 155     ret[1].type = C_STRING;
 156     sprintf(buf, "%d", params->h);
 157     ret[1].sval = dupstr(buf);
 158     ret[1].ival = 0;
 159
 160     ret[2].name = NULL;
 161     ret[2].type = C_END;
 162     ret[2].sval = NULL;
 163     ret[2].ival = 0;
 164
 165     return ret;
 166 }
 167
 168 game_params *custom_params(config_item *cfg)
 169 {
 170     game_params *ret = snew(game_params);
 171
 172     ret->w = atoi(cfg[0].sval);
 173     ret->h = atoi(cfg[1].sval);
 174
 175     return ret;
 176 }
 177
 178 char *validate_params(game_params *params)
 179 {
 180     if (params->w <= 0 && params->h <= 0)
 181         return "Width and height must both be greater than zero";
 182     if (params->w <= 0)
 183         return "Width must be greater than zero";
 184     if (params->h <= 0)
 185         return "Height must be greater than zero";
 186     return NULL;
 187 }
 188
 189 /* ----------------------------------------------------------------------
 190  * Puzzle generation code.
 191  *
 192  * For this particular puzzle, it seemed important to me to ensure
 193  * a unique solution. I do this the brute-force way, by having a
 194  * solver algorithm alongside the generator, and repeatedly
 195  * generating a random grid until I find one whose solution is
 196  * unique. It turns out that this isn't too onerous on a modern PC
 197  * provided you keep grid size below around 30. Any offers of
 198  * better algorithms, however, will be very gratefully received.
 199  *
 200  * Another annoyance of this approach is that it limits the
 201  * available puzzles to those solvable by the algorithm I've used.
 202  * My algorithm only ever considers a single row or column at any
 203  * one time, which means it's incapable of solving the following
 204  * difficult example (found by Bella Image around 1995/6, when she
 205  * and I were both doing maths degrees):
 206  *
 207  *        2  1  2  1
 208  *
 209  *      +--+--+--+--+
 210  * 1 1  |  |  |  |  |
 211  *      +--+--+--+--+
 212  *   2  |  |  |  |  |
 213  *      +--+--+--+--+
 214  *   1  |  |  |  |  |
 215  *      +--+--+--+--+
 216  *   1  |  |  |  |  |
 217  *      +--+--+--+--+
 218  *
 219  * Obviously this cannot be solved by a one-row-or-column-at-a-time
 220  * algorithm (it would require at least one row or column reading
 221  * `2 1', `1 2', `3' or `4' to get started). However, it can be
 222  * proved to have a unique solution: if the top left square were
 223  * empty, then the only option for the top row would be to fill the
 224  * two squares in the 1 columns, which would imply the squares
 225  * below those were empty, leaving no place for the 2 in the second
 226  * row. Contradiction. Hence the top left square is full, and the
 227  * unique solution follows easily from that starting point.
 228  *
 229  * (The game ID for this puzzle is 4x4:2/1/2/1/1.1/2/1/1 , in case
 230  * it's useful to anyone.)
 231  */
 232
 233 static int float_compare(const void *av, const void *bv)
 234 {
 235     const float *a = (const float *)av;
 236     const float *b = (const float *)bv;
 237     if (*a < *b)
 238         return -1;
 239     else if (*a > *b)
 240         return +1;
 241     else
 242         return 0;
 243 }
 244
 245 static void generate(random_state *rs, int w, int h, unsigned char *retgrid)
 246 {
 247     float *fgrid;
 248     float *fgrid2;
 249     int step, i, j;
 250     float threshold;
 251
 252     fgrid = snewn(w*h, float);
 253
 254     for (i = 0; i < h; i++) {
 255         for (j = 0; j < w; j++) {
 256             fgrid[i*w+j] = random_upto(rs, 100000000UL) / 100000000.F;
 257         }
 258     }
 259
 260     /*
 261      * The above gives a completely random splattering of black and
 262      * white cells. We want to gently bias this in favour of _some_
 263      * reasonably thick areas of white and black, while retaining
 264      * some randomness and fine detail.
 265      *
 266      * So we evolve the starting grid using a cellular automaton.
 267      * Currently, I'm doing something very simple indeed, which is
 268      * to set each square to the average of the surrounding nine
 269      * cells (or the average of fewer, if we're on a corner).
 270      */
 271     for (step = 0; step < 1; step++) {
 272         fgrid2 = snewn(w*h, float);
 273
 274         for (i = 0; i < h; i++) {
 275             for (j = 0; j < w; j++) {
 276                 float sx, xbar;
 277                 int n, p, q;
 278
 279                 /*
 280                  * Compute the average of the surrounding cells.
 281                  */
 282                 n = 0;
 283                 sx = 0.F;
 284                 for (p = -1; p <= +1; p++) {
 285                     for (q = -1; q <= +1; q++) {
 286                         if (i+p < 0 || i+p >= h || j+q < 0 || j+q >= w)
 287                             continue;
 288                         n++;
 289                         sx += fgrid[(i+p)*w+(j+q)];
 290                     }
 291                 }
 292                 xbar = sx / n;
 293
 294                 fgrid2[i*w+j] = xbar;
 295             }
 296         }
 297
 298         sfree(fgrid);
 299         fgrid = fgrid2;
 300     }
 301
 302     fgrid2 = snewn(w*h, float);
 303     memcpy(fgrid2, fgrid, w*h*sizeof(float));
 304     qsort(fgrid2, w*h, sizeof(float), float_compare);
 305     threshold = fgrid2[w*h/2];
 306     sfree(fgrid2);
 307
 308     for (i = 0; i < h; i++) {
 309         for (j = 0; j < w; j++) {
 310             retgrid[i*w+j] = (fgrid[i*w+j] > threshold ? GRID_FULL :
 311                               GRID_EMPTY);
 312         }
 313     }
 314
 315     sfree(fgrid);
 316 }
 317
 318 int compute_rowdata(int *ret, unsigned char *start, int len, int step)
 319 {
 320     int i, n;
 321
 322     n = 0;
 323
 324     for (i = 0; i < len; i++) {
 325         if (start[i*step] == GRID_FULL) {
 326             int runlen = 1;
 327             while (i+runlen < len && start[(i+runlen)*step] == GRID_FULL)
 328                 runlen++;
 329             ret[n++] = runlen;
 330             i += runlen;
 331         }
 332
 333         if (i < len && start[i*step] == GRID_UNKNOWN)
 334             return -1;
 335     }
 336
 337     return n;
 338 }
 339
 340 #define UNKNOWN 0
 341 #define BLOCK 1
 342 #define DOT 2
 343 #define STILL_UNKNOWN 3
 344
 345 static void do_recurse(unsigned char *known, unsigned char *deduced,
 346                        unsigned char *row, int *data, int len,
 347                        int freespace, int ndone, int lowest)
 348 {
 349     int i, j, k;
 350
 351     if (data[ndone]) {
 352         for (i=0; i<=freespace; i++) {
 353             j = lowest;
 354             for (k=0; k<i; k++) row[j++] = DOT;
 355             for (k=0; k<data[ndone]; k++) row[j++] = BLOCK;
 356             if (j < len) row[j++] = DOT;
 357             do_recurse(known, deduced, row, data, len,
 358                        freespace-i, ndone+1, j);
 359         }
 360     } else {
 361         for (i=lowest; i<len; i++)
 362             row[i] = DOT;
 363         for (i=0; i<len; i++)
 364             if (known[i] && known[i] != row[i])
 365                 return;
 366         for (i=0; i<len; i++)
 367             deduced[i] |= row[i];
 368     }
 369 }
 370
 371 static int do_row(unsigned char *known, unsigned char *deduced,
 372                   unsigned char *row,
 373                   unsigned char *start, int len, int step, int *data)
 374 {
 375     int rowlen, i, freespace, done_any;
 376
 377     freespace = len+1;
 378     for (rowlen = 0; data[rowlen]; rowlen++)
 379         freespace -= data[rowlen]+1;
 380
 381     for (i = 0; i < len; i++) {
 382         known[i] = start[i*step];
 383         deduced[i] = 0;
 384     }
 385
 386     do_recurse(known, deduced, row, data, len, freespace, 0, 0);
 387     done_any = FALSE;
 388     for (i=0; i<len; i++)
 389         if (deduced[i] && deduced[i] != STILL_UNKNOWN && !known[i]) {
 390             start[i*step] = deduced[i];
 391             done_any = TRUE;
 392         }
 393     return done_any;
 394 }
 395
 396 static unsigned char *generate_soluble(random_state *rs, int w, int h)
 397 {
 398     int i, j, done_any, ok, ntries, max;
 399     unsigned char *grid, *matrix, *workspace;
 400     int *rowdata;
 401
 402     grid = snewn(w*h, unsigned char);
 403     matrix = snewn(w*h, unsigned char);
 404     max = max(w, h);
 405     workspace = snewn(max*3, unsigned char);
 406     rowdata = snewn(max+1, int);
 407
 408     ntries = 0;
 409
 410     do {
 411         ntries++;
 412
 413         generate(rs, w, h, grid);
 414
 415         memset(matrix, 0, w*h);
 416
 417         do {
 418             done_any = 0;
 419             for (i=0; i<h; i++) {
 420                 rowdata[compute_rowdata(rowdata, grid+i*w, w, 1)] = 0;
 421                 done_any |= do_row(workspace, workspace+max, workspace+2*max,
 422                                    matrix+i*w, w, 1, rowdata);
 423             }
 424             for (i=0; i<w; i++) {
 425                 rowdata[compute_rowdata(rowdata, grid+i, h, w)] = 0;
 426                 done_any |= do_row(workspace, workspace+max, workspace+2*max,
 427                                    matrix+i, h, w, rowdata);
 428             }
 429         } while (done_any);
 430
 431         ok = TRUE;
 432         for (i=0; i<h; i++) {
 433             for (j=0; j<w; j++) {
 434                 if (matrix[i*w+j] == UNKNOWN)
 435                     ok = FALSE;
 436             }
 437         }
 438     } while (!ok);
 439
 440     sfree(matrix);
 441     sfree(workspace);
 442     sfree(rowdata);
 443     return grid;
 444 }
 445
 446 char *new_game_seed(game_params *params, random_state *rs)
 447 {
 448     unsigned char *grid;
 449     int i, j, max, rowlen, *rowdata;
 450     char intbuf[80], *seed;
 451     int seedlen, seedpos;
 452
 453     grid = generate_soluble(rs, params->w, params->h);
 454     max = max(params->w, params->h);
 455     rowdata = snewn(max, int);
 456
 457     /*
 458      * Seed is a slash-separated list of row contents; each row
 459      * contents section is a dot-separated list of integers. Row
 460      * contents are listed in the order (columns left to right,
 461      * then rows top to bottom).
 462      *
 463      * Simplest way to handle memory allocation is to make two
 464      * passes, first computing the seed size and then writing it
 465      * out.
 466      */
 467     seedlen = 0;
 468     for (i = 0; i < params->w + params->h; i++) {
 469         if (i < params->w)
 470             rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
 471         else
 472             rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w,
 473                                      params->w, 1);
 474         if (rowlen > 0) {
 475             for (j = 0; j < rowlen; j++) {
 476                 seedlen += 1 + sprintf(intbuf, "%d", rowdata[j]);
 477             }
 478         } else {
 479             seedlen++;
 480         }
 481     }
 482     seed = snewn(seedlen, char);
 483     seedpos = 0;
 484     for (i = 0; i < params->w + params->h; i++) {
 485         if (i < params->w)
 486             rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
 487         else
 488             rowlen = compute_rowdata(rowdata, grid+(i-params->w)*params->w,
 489                                      params->w, 1);
 490         if (rowlen > 0) {
 491             for (j = 0; j < rowlen; j++) {
 492                 int len = sprintf(seed+seedpos, "%d", rowdata[j]);
 493                 if (j+1 < rowlen)
 494                     seed[seedpos + len] = '.';
 495                 else
 496                     seed[seedpos + len] = '/';
 497                 seedpos += len+1;
 498             }
 499         } else {
 500             seed[seedpos++] = '/';
 501         }
 502     }
 503     assert(seedpos == seedlen);
 504     assert(seed[seedlen-1] == '/');
 505     seed[seedlen-1] = '\0';
 506     sfree(rowdata);
 507     return seed;
 508 }
 509
 510 char *validate_seed(game_params *params, char *seed)
 511 {
 512     int i, n, rowspace;
 513     char *p;
 514
 515     for (i = 0; i < params->w + params->h; i++) {
 516         if (i < params->w)
 517             rowspace = params->h + 1;
 518         else
 519             rowspace = params->w + 1;
 520
 521         if (*seed && isdigit((unsigned char)*seed)) {
 522             do {
 523                 p = seed;
 524                 while (seed && isdigit((unsigned char)*seed)) seed++;
 525                 n = atoi(p);
 526                 rowspace -= n+1;
 527
 528                 if (rowspace < 0) {
 529                     if (i < params->w)
 530                         return "at least one column contains more numbers than will fit";
 531                     else
 532                         return "at least one row contains more numbers than will fit";
 533                 }
 534             } while (*seed++ == '.');
 535         } else {
 536             seed++;                    /* expect a slash immediately */
 537         }
 538
 539         if (seed[-1] == '/') {
 540             if (i+1 == params->w + params->h)
 541                 return "too many row/column specifications";
 542         } else if (seed[-1] == '\0') {
 543             if (i+1 < params->w + params->h)
 544                 return "too few row/column specifications";
 545         } else
 546             return "unrecognised character in game specification";
 547     }
 548
 549     return NULL;
 550 }
 551
 552 game_state *new_game(game_params *params, char *seed)
 553 {
 554     int i;
 555     char *p;
 556     game_state *state = snew(game_state);
 557
 558     state->w = params->w;
 559     state->h = params->h;
 560
 561     state->grid = snewn(state->w * state->h, unsigned char);
 562     memset(state->grid, GRID_UNKNOWN, state->w * state->h);
 563
 564     state->rowsize = max(state->w, state->h);
 565     state->rowdata = snewn(state->rowsize * (state->w + state->h), int);
 566     state->rowlen = snewn(state->w + state->h, int);
 567
 568     state->completed = FALSE;
 569
 570     for (i = 0; i < params->w + params->h; i++) {
 571         state->rowlen[i] = 0;
 572         if (*seed && isdigit((unsigned char)*seed)) {
 573             do {
 574                 p = seed;
 575                 while (seed && isdigit((unsigned char)*seed)) seed++;
 576                 state->rowdata[state->rowsize * i + state->rowlen[i]++] =
 577                     atoi(p);
 578             } while (*seed++ == '.');
 579         } else {
 580             seed++;                    /* expect a slash immediately */
 581         }
 582     }
 583
 584     return state;
 585 }
 586
 587 game_state *dup_game(game_state *state)
 588 {
 589     game_state *ret = snew(game_state);
 590
 591     ret->w = state->w;
 592     ret->h = state->h;
 593
 594     ret->grid = snewn(ret->w * ret->h, unsigned char);
 595     memcpy(ret->grid, state->grid, ret->w * ret->h);
 596
 597     ret->rowsize = state->rowsize;
 598     ret->rowdata = snewn(ret->rowsize * (ret->w + ret->h), int);
 599     ret->rowlen = snewn(ret->w + ret->h, int);
 600     memcpy(ret->rowdata, state->rowdata,
 601            ret->rowsize * (ret->w + ret->h) * sizeof(int));
 602     memcpy(ret->rowlen, state->rowlen,
 603            (ret->w + ret->h) * sizeof(int));
 604
 605     ret->completed = state->completed;
 606
 607     return ret;
 608 }
 609
 610 void free_game(game_state *state)
 611 {
 612     sfree(state->rowdata);
 613     sfree(state->rowlen);
 614     sfree(state->grid);
 615     sfree(state);
 616 }
 617
 618 struct game_ui {
 619     int dragging;
 620     int drag_start_x;
 621     int drag_start_y;
 622     int drag_end_x;
 623     int drag_end_y;
 624     int drag, release, state;
 625 };
 626
 627 game_ui *new_ui(game_state *state)
 628 {
 629     game_ui *ret;
 630
 631     ret = snew(game_ui);
 632     ret->dragging = FALSE;
 633
 634     return ret;
 635 }
 636
 637 void free_ui(game_ui *ui)
 638 {
 639     sfree(ui);
 640 }
 641
 642 game_state *make_move(game_state *from, game_ui *ui, int x, int y, int button)
 643 {
 644     game_state *ret;
 645
 646     x = FROMCOORD(from->w, x);
 647     y = FROMCOORD(from->h, y);
 648
 649     if (x >= 0 && x < from->w && y >= 0 && y < from->h &&
 650         (button == LEFT_BUTTON || button == RIGHT_BUTTON ||
 651          button == MIDDLE_BUTTON)) {
 652
 653         ui->dragging = TRUE;
 654
 655         if (button == LEFT_BUTTON) {
 656             ui->drag = LEFT_DRAG;
 657             ui->release = LEFT_RELEASE;
 658             ui->state = GRID_FULL;
 659         } else if (button == RIGHT_BUTTON) {
 660             ui->drag = RIGHT_DRAG;
 661             ui->release = RIGHT_RELEASE;
 662             ui->state = GRID_EMPTY;
 663         } else /* if (button == MIDDLE_BUTTON) */ {
 664             ui->drag = MIDDLE_DRAG;
 665             ui->release = MIDDLE_RELEASE;
 666             ui->state = GRID_UNKNOWN;
 667         }
 668
 669         ui->drag_start_x = ui->drag_end_x = x;
 670         ui->drag_start_y = ui->drag_end_y = y;
 671
 672         return from;                   /* UI activity occurred */
 673     }
 674
 675     if (ui->dragging && button == ui->drag) {
 676         /*
 677          * There doesn't seem much point in allowing a rectangle
 678          * drag; people will generally only want to drag a single
 679          * horizontal or vertical line, so we make that easy by
 680          * snapping to it.
 681          *
 682          * Exception: if we're _middle_-button dragging to tag
 683          * things as UNKNOWN, we may well want to trash an entire
 684          * area and start over!
 685          */
 686         if (ui->state != GRID_UNKNOWN) {
 687             if (abs(x - ui->drag_start_x) > abs(y - ui->drag_start_y))
 688                 y = ui->drag_start_y;
 689             else
 690                 x = ui->drag_start_x;
 691         }
 692
 693         if (x < 0) x = 0;
 694         if (y < 0) y = 0;
 695         if (x >= from->w) x = from->w - 1;
 696         if (y >= from->h) y = from->h - 1;
 697
 698         ui->drag_end_x = x;
 699         ui->drag_end_y = y;
 700
 701         return from;                   /* UI activity occurred */
 702     }
 703
 704     if (ui->dragging && button == ui->release) {
 705         int x1, x2, y1, y2, xx, yy;
 706         int move_needed = FALSE;
 707
 708         x1 = min(ui->drag_start_x, ui->drag_end_x);
 709         x2 = max(ui->drag_start_x, ui->drag_end_x);
 710         y1 = min(ui->drag_start_y, ui->drag_end_y);
 711         y2 = max(ui->drag_start_y, ui->drag_end_y);
 712
 713         for (yy = y1; yy <= y2; yy++)
 714             for (xx = x1; xx <= x2; xx++)
 715                 if (from->grid[yy * from->w + xx] != ui->state)
 716                     move_needed = TRUE;
 717
 718         ui->dragging = FALSE;
 719
 720         if (move_needed) {
 721             ret = dup_game(from);
 722             for (yy = y1; yy <= y2; yy++)
 723                 for (xx = x1; xx <= x2; xx++)
 724                     ret->grid[yy * ret->w + xx] = ui->state;
 725
 726             /*
 727              * An actual change, so check to see if we've completed
 728              * the game.
 729              */
 730             if (!ret->completed) {
 731                 int *rowdata = snewn(ret->rowsize, int);
 732                 int i, len;
 733
 734                 ret->completed = TRUE;
 735
 736                 for (i=0; i<ret->w; i++) {
 737                     len = compute_rowdata(rowdata,
 738                                           ret->grid+i, ret->h, ret->w);
 739                     if (len != ret->rowlen[i] ||
 740                         memcmp(ret->rowdata+i*ret->rowsize, rowdata,
 741                                len * sizeof(int))) {
 742                         ret->completed = FALSE;
 743                         break;
 744                     }
 745                 }
 746                 for (i=0; i<ret->h; i++) {
 747                     len = compute_rowdata(rowdata,
 748                                           ret->grid+i*ret->w, ret->w, 1);
 749                     if (len != ret->rowlen[i+ret->w] ||
 750                         memcmp(ret->rowdata+(i+ret->w)*ret->rowsize, rowdata,
 751                                len * sizeof(int))) {
 752                         ret->completed = FALSE;
 753                         break;
 754                     }
 755                 }
 756
 757                 sfree(rowdata);
 758             }
 759
 760             return ret;
 761         } else
 762             return from;               /* UI activity occurred */
 763     }
 764
 765     return NULL;
 766 }
 767
 768 /* ----------------------------------------------------------------------
 769  * Drawing routines.
 770  */
 771
 772 struct game_drawstate {
 773     int started;
 774     int w, h;
 775     unsigned char *visible;
 776 };
 777
 778 void game_size(game_params *params, int *x, int *y)
 779 {
 780     *x = SIZE(params->w);
 781     *y = SIZE(params->h);
 782 }
 783
 784 float *game_colours(frontend *fe, game_state *state, int *ncolours)
 785 {
 786     float *ret = snewn(3 * NCOLOURS, float);
 787
 788     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
 789
 790     ret[COL_GRID * 3 + 0] = 0.3F;
 791     ret[COL_GRID * 3 + 1] = 0.3F;
 792     ret[COL_GRID * 3 + 2] = 0.3F;
 793
 794     ret[COL_UNKNOWN * 3 + 0] = 0.5F;
 795     ret[COL_UNKNOWN * 3 + 1] = 0.5F;
 796     ret[COL_UNKNOWN * 3 + 2] = 0.5F;
 797
 798     ret[COL_FULL * 3 + 0] = 0.0F;
 799     ret[COL_FULL * 3 + 1] = 0.0F;
 800     ret[COL_FULL * 3 + 2] = 0.0F;
 801
 802     ret[COL_EMPTY * 3 + 0] = 1.0F;
 803     ret[COL_EMPTY * 3 + 1] = 1.0F;
 804     ret[COL_EMPTY * 3 + 2] = 1.0F;
 805
 806     *ncolours = NCOLOURS;
 807     return ret;
 808 }
 809
 810 game_drawstate *game_new_drawstate(game_state *state)
 811 {
 812     struct game_drawstate *ds = snew(struct game_drawstate);
 813
 814     ds->started = FALSE;
 815     ds->w = state->w;
 816     ds->h = state->h;
 817     ds->visible = snewn(ds->w * ds->h, unsigned char);
 818     memset(ds->visible, 255, ds->w * ds->h);
 819
 820     return ds;
 821 }
 822
 823 void game_free_drawstate(game_drawstate *ds)
 824 {
 825     sfree(ds->visible);
 826     sfree(ds);
 827 }
 828
 829 static void grid_square(frontend *fe, game_drawstate *ds,
 830                         int y, int x, int state)
 831 {
 832     int xl, xr, yt, yb;
 833
 834     draw_rect(fe, TOCOORD(ds->w, x), TOCOORD(ds->h, y),
 835               TILE_SIZE, TILE_SIZE, COL_GRID);
 836
 837     xl = (x % 5 == 0 ? 1 : 0);
 838     yt = (y % 5 == 0 ? 1 : 0);
 839     xr = (x % 5 == 4 || x == ds->w-1 ? 1 : 0);
 840     yb = (y % 5 == 4 || y == ds->h-1 ? 1 : 0);
 841
 842     draw_rect(fe, TOCOORD(ds->w, x) + 1 + xl, TOCOORD(ds->h, y) + 1 + yt,
 843               TILE_SIZE - xl - xr - 1, TILE_SIZE - yt - yb - 1,
 844               (state == GRID_FULL ? COL_FULL :
 845                state == GRID_EMPTY ? COL_EMPTY : COL_UNKNOWN));
 846
 847     draw_update(fe, TOCOORD(ds->w, x), TOCOORD(ds->h, y),
 848                 TILE_SIZE, TILE_SIZE);
 849 }
 850
 851 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 852                  game_state *state, int dir, game_ui *ui,
 853                  float animtime, float flashtime)
 854 {
 855     int i, j;
 856     int x1, x2, y1, y2;
 857
 858     if (!ds->started) {
 859         /*
 860          * The initial contents of the window are not guaranteed
 861          * and can vary with front ends. To be on the safe side,
 862          * all games should start by drawing a big background-
 863          * colour rectangle covering the whole window.
 864          */
 865         draw_rect(fe, 0, 0, SIZE(ds->w), SIZE(ds->h), COL_BACKGROUND);
 866
 867         /*
 868          * Draw the numbers.
 869          */
 870         for (i = 0; i < ds->w + ds->h; i++) {
 871             int rowlen = state->rowlen[i];
 872             int *rowdata = state->rowdata + state->rowsize * i;
 873             int nfit;
 874
 875             /*
 876              * Normally I space the numbers out by the same
 877              * distance as the tile size. However, if there are
 878              * more numbers than available spaces, I have to squash
 879              * them up a bit.
 880              */
 881             nfit = max(rowlen, TLBORDER(ds->h))-1;
 882             assert(nfit > 0);
 883
 884             for (j = 0; j < rowlen; j++) {
 885                 int x, y;
 886                 char str[80];
 887
 888                 if (i < ds->w) {
 889                     x = TOCOORD(ds->w, i);
 890                     y = BORDER + TILE_SIZE * (TLBORDER(ds->h)-1);
 891                     y -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(ds->h)-1) / nfit;
 892                 } else {
 893                     y = TOCOORD(ds->h, i - ds->w);
 894                     x = BORDER + TILE_SIZE * (TLBORDER(ds->w)-1);
 895                     x -= ((rowlen-j-1)*TILE_SIZE) * (TLBORDER(ds->h)-1) / nfit;
 896                 }
 897
 898                 sprintf(str, "%d", rowdata[j]);
 899                 draw_text(fe, x+TILE_SIZE/2, y+TILE_SIZE/2, FONT_VARIABLE,
 900                           TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE,
 901                           COL_FULL, str);   /* FIXME: COL_TEXT */
 902             }
 903         }
 904
 905         /*
 906          * Draw the grid outline.
 907          */
 908         draw_rect(fe, TOCOORD(ds->w, 0) - 1, TOCOORD(ds->h, 0) - 1,
 909                   ds->w * TILE_SIZE + 2, ds->h * TILE_SIZE + 2,
 910                   COL_GRID);
 911
 912         ds->started = TRUE;
 913
 914         draw_update(fe, 0, 0, SIZE(ds->w), SIZE(ds->h));
 915     }
 916
 917     if (ui->dragging) {
 918         x1 = min(ui->drag_start_x, ui->drag_end_x);
 919         x2 = max(ui->drag_start_x, ui->drag_end_x);
 920         y1 = min(ui->drag_start_y, ui->drag_end_y);
 921         y2 = max(ui->drag_start_y, ui->drag_end_y);
 922     } else {
 923         x1 = x2 = y1 = y2 = -1;        /* placate gcc warnings */
 924     }
 925
 926     /*
 927      * Now draw any grid squares which have changed since last
 928      * redraw.
 929      */
 930     for (i = 0; i < ds->h; i++) {
 931         for (j = 0; j < ds->w; j++) {
 932             int val;
 933
 934             /*
 935              * Work out what state this square should be drawn in,
 936              * taking any current drag operation into account.
 937              */
 938             if (ui->dragging && x1 <= j && j <= x2 && y1 <= i && i <= y2)
 939                 val = ui->state;
 940             else
 941                 val = state->grid[i * state->w + j];
 942
 943             /*
 944              * Briefly invert everything twice during a completion
 945              * flash.
 946              */
 947             if (flashtime > 0 &&
 948                 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3) &&
 949                 val != GRID_UNKNOWN)
 950                 val = (GRID_FULL ^ GRID_EMPTY) ^ val;
 951
 952             if (ds->visible[i * ds->w + j] != val) {
 953                 grid_square(fe, ds, i, j, val);
 954                 ds->visible[i * ds->w + j] = val;
 955             }
 956         }
 957     }
 958 }
 959
 960 float game_anim_length(game_state *oldstate, game_state *newstate, int dir)
 961 {
 962     return 0.0F;
 963 }
 964
 965 float game_flash_length(game_state *oldstate, game_state *newstate, int dir)
 966 {
 967     if (!oldstate->completed && newstate->completed)
 968         return FLASH_TIME;
 969     return 0.0F;
 970 }
 971
 972 int game_wants_statusbar(void)
 973 {
 974     return FALSE;
 975 }