rect.c

   1 /*
   2  * rect.c: Puzzle from nikoli.co.jp. You have a square grid with
   3  * numbers in some squares; you must divide the square grid up into
   4  * variously sized rectangles, such that every rectangle contains
   5  * exactly one numbered square and the area of each rectangle is
   6  * equal to the number contained in it.
   7  */
   8
   9 /*
  10  * TODO:
  11  *
  12  *  - Improve on singleton removal by making an aesthetic choice
  13  *    about which of the options to take.
  14  *
  15  *  - When doing the 3x3 trick in singleton removal, limit the size
  16  *    of the generated rectangles in accordance with the max
  17  *    rectangle size.
  18  *
  19  *  - It might be interesting to deliberately try to place
  20  *    numbers so as to reduce alternative solution patterns. I
  21  *    doubt we can do a perfect job of this, but we can make a
  22  *    start by, for example, noticing pairs of 2-rects
  23  *    alongside one another and _not_ putting their numbers at
  24  *    opposite ends.
  25  *
  26  *  - If we start by sorting the rectlist in descending order
  27  *    of area, we might be able to bias our random number
  28  *    selection to produce a few large rectangles more often
  29  *    than oodles of small ones? Unsure, but might be worth a
  30  *    try.
  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 const char *const game_name = "Rectangles";
  43 const char *const game_winhelp_topic = "games.rectangles";
  44 const int game_can_configure = TRUE;
  45
  46 enum {
  47     COL_BACKGROUND,
  48     COL_CORRECT,
  49     COL_LINE,
  50     COL_TEXT,
  51     COL_GRID,
  52     COL_DRAG,
  53     NCOLOURS
  54 };
  55
  56 struct game_params {
  57     int w, h;
  58     float expandfactor;
  59 };
  60
  61 #define INDEX(state, x, y)    (((y) * (state)->w) + (x))
  62 #define index(state, a, x, y) ((a) [ INDEX(state,x,y) ])
  63 #define grid(state,x,y)       index(state, (state)->grid, x, y)
  64 #define vedge(state,x,y)      index(state, (state)->vedge, x, y)
  65 #define hedge(state,x,y)      index(state, (state)->hedge, x, y)
  66
  67 #define CRANGE(state,x,y,dx,dy) ( (x) >= dx && (x) < (state)->w && \
  68                                 (y) >= dy && (y) < (state)->h )
  69 #define RANGE(state,x,y)  CRANGE(state,x,y,0,0)
  70 #define HRANGE(state,x,y) CRANGE(state,x,y,0,1)
  71 #define VRANGE(state,x,y) CRANGE(state,x,y,1,0)
  72
  73 #define TILE_SIZE 24
  74 #define BORDER 18
  75
  76 #define CORNER_TOLERANCE 0.15F
  77 #define CENTRE_TOLERANCE 0.15F
  78
  79 #define FLASH_TIME 0.13F
  80
  81 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
  82 #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE )
  83
  84 struct game_state {
  85     int w, h;
  86     int *grid;                         /* contains the numbers */
  87     unsigned char *vedge;              /* (w+1) x h */
  88     unsigned char *hedge;              /* w x (h+1) */
  89     int completed;
  90 };
  91
  92 game_params *default_params(void)
  93 {
  94     game_params *ret = snew(game_params);
  95
  96     ret->w = ret->h = 7;
  97     ret->expandfactor = 0.0F;
  98
  99     return ret;
 100 }
 101
 102 int game_fetch_preset(int i, char **name, game_params **params)
 103 {
 104     game_params *ret;
 105     int w, h;
 106     char buf[80];
 107
 108     switch (i) {
 109       case 0: w = 7, h = 7; break;
 110       case 1: w = 11, h = 11; break;
 111       case 2: w = 15, h = 15; break;
 112       case 3: w = 19, h = 19; break;
 113       default: return FALSE;
 114     }
 115
 116     sprintf(buf, "%dx%d", w, h);
 117     *name = dupstr(buf);
 118     *params = ret = snew(game_params);
 119     ret->w = w;
 120     ret->h = h;
 121     ret->expandfactor = 0.0F;
 122     return TRUE;
 123 }
 124
 125 void free_params(game_params *params)
 126 {
 127     sfree(params);
 128 }
 129
 130 game_params *dup_params(game_params *params)
 131 {
 132     game_params *ret = snew(game_params);
 133     *ret = *params;                    /* structure copy */
 134     return ret;
 135 }
 136
 137 game_params *decode_params(char const *string)
 138 {
 139     game_params *ret = default_params();
 140
 141     ret->w = ret->h = atoi(string);
 142     ret->expandfactor = 0.0F;
 143     while (*string && isdigit((unsigned char)*string)) string++;
 144     if (*string == 'x') {
 145         string++;
 146         ret->h = atoi(string);
 147         while (*string && isdigit((unsigned char)*string)) string++;
 148     }
 149     if (*string == 'e') {
 150         string++;
 151         ret->expandfactor = atof(string);
 152     }
 153
 154     return ret;
 155 }
 156
 157 char *encode_params(game_params *params)
 158 {
 159     char data[256];
 160
 161     sprintf(data, "%dx%d", params->w, params->h);
 162
 163     return dupstr(data);
 164 }
 165
 166 config_item *game_configure(game_params *params)
 167 {
 168     config_item *ret;
 169     char buf[80];
 170
 171     ret = snewn(5, config_item);
 172
 173     ret[0].name = "Width";
 174     ret[0].type = C_STRING;
 175     sprintf(buf, "%d", params->w);
 176     ret[0].sval = dupstr(buf);
 177     ret[0].ival = 0;
 178
 179     ret[1].name = "Height";
 180     ret[1].type = C_STRING;
 181     sprintf(buf, "%d", params->h);
 182     ret[1].sval = dupstr(buf);
 183     ret[1].ival = 0;
 184
 185     ret[2].name = "Expansion factor";
 186     ret[2].type = C_STRING;
 187     sprintf(buf, "%g", params->expandfactor);
 188     ret[2].sval = dupstr(buf);
 189     ret[2].ival = 0;
 190
 191     ret[3].name = NULL;
 192     ret[3].type = C_END;
 193     ret[3].sval = NULL;
 194     ret[3].ival = 0;
 195
 196     return ret;
 197 }
 198
 199 game_params *custom_params(config_item *cfg)
 200 {
 201     game_params *ret = snew(game_params);
 202
 203     ret->w = atoi(cfg[0].sval);
 204     ret->h = atoi(cfg[1].sval);
 205     ret->expandfactor = atof(cfg[2].sval);
 206
 207     return ret;
 208 }
 209
 210 char *validate_params(game_params *params)
 211 {
 212     if (params->w <= 0 && params->h <= 0)
 213         return "Width and height must both be greater than zero";
 214     if (params->w < 2 && params->h < 2)
 215         return "Grid area must be greater than one";
 216     if (params->expandfactor < 0.0F)
 217         return "Expansion factor may not be negative";
 218     return NULL;
 219 }
 220
 221 struct rect {
 222     int x, y;
 223     int w, h;
 224 };
 225
 226 struct rectlist {
 227     struct rect *rects;
 228     int n;
 229 };
 230
 231 static struct rectlist *get_rectlist(game_params *params, int *grid)
 232 {
 233     int rw, rh;
 234     int x, y;
 235     int maxarea;
 236     struct rect *rects = NULL;
 237     int nrects = 0, rectsize = 0;
 238
 239     /*
 240      * Maximum rectangle area is 1/6 of total grid size, unless
 241      * this means we can't place any rectangles at all in which
 242      * case we set it to 2 at minimum.
 243      */
 244     maxarea = params->w * params->h / 6;
 245     if (maxarea < 2)
 246         maxarea = 2;
 247
 248     for (rw = 1; rw <= params->w; rw++)
 249         for (rh = 1; rh <= params->h; rh++) {
 250             if (rw * rh > maxarea)
 251                 continue;
 252             if (rw * rh == 1)
 253                 continue;
 254             for (x = 0; x <= params->w - rw; x++)
 255                 for (y = 0; y <= params->h - rh; y++) {
 256                     if (nrects >= rectsize) {
 257                         rectsize = nrects + 256;
 258                         rects = sresize(rects, rectsize, struct rect);
 259                     }
 260
 261                     rects[nrects].x = x;
 262                     rects[nrects].y = y;
 263                     rects[nrects].w = rw;
 264                     rects[nrects].h = rh;
 265                     nrects++;
 266                 }
 267         }
 268
 269     if (nrects > 0) {
 270         struct rectlist *ret;
 271         ret = snew(struct rectlist);
 272         ret->rects = rects;
 273         ret->n = nrects;
 274         return ret;
 275     } else {
 276         assert(rects == NULL);         /* hence no need to free */
 277         return NULL;
 278     }
 279 }
 280
 281 static void free_rectlist(struct rectlist *list)
 282 {
 283     sfree(list->rects);
 284     sfree(list);
 285 }
 286
 287 static void place_rect(game_params *params, int *grid, struct rect r)
 288 {
 289     int idx = INDEX(params, r.x, r.y);
 290     int x, y;
 291
 292     for (x = r.x; x < r.x+r.w; x++)
 293         for (y = r.y; y < r.y+r.h; y++) {
 294             index(params, grid, x, y) = idx;
 295         }
 296 #ifdef GENERATION_DIAGNOSTICS
 297     printf("    placing rectangle at (%d,%d) size %d x %d\n",
 298            r.x, r.y, r.w, r.h);
 299 #endif
 300 }
 301
 302 static struct rect find_rect(game_params *params, int *grid, int x, int y)
 303 {
 304     int idx, w, h;
 305     struct rect r;
 306
 307     /*
 308      * Find the top left of the rectangle.
 309      */
 310     idx = index(params, grid, x, y);
 311
 312     if (idx < 0) {
 313         r.x = x;
 314         r.y = y;
 315         r.w = r.h = 1;
 316         return r;                      /* 1x1 singleton here */
 317     }
 318
 319     y = idx / params->w;
 320     x = idx % params->w;
 321
 322     /*
 323      * Find the width and height of the rectangle.
 324      */
 325     for (w = 1;
 326          (x+w < params->w && index(params,grid,x+w,y)==idx);
 327          w++);
 328     for (h = 1;
 329          (y+h < params->h && index(params,grid,x,y+h)==idx);
 330          h++);
 331
 332     r.x = x;
 333     r.y = y;
 334     r.w = w;
 335     r.h = h;
 336
 337     return r;
 338 }
 339
 340 #ifdef GENERATION_DIAGNOSTICS
 341 static void display_grid(game_params *params, int *grid, int *numbers, int all)
 342 {
 343     unsigned char *egrid = snewn((params->w*2+3) * (params->h*2+3),
 344                                  unsigned char);
 345     int x, y;
 346     int r = (params->w*2+3);
 347
 348     memset(egrid, 0, (params->w*2+3) * (params->h*2+3));
 349
 350     for (x = 0; x < params->w; x++)
 351         for (y = 0; y < params->h; y++) {
 352             int i = index(params, grid, x, y);
 353             if (x == 0 || index(params, grid, x-1, y) != i)
 354                 egrid[(2*y+2) * r + (2*x+1)] = 1;
 355             if (x == params->w-1 || index(params, grid, x+1, y) != i)
 356                 egrid[(2*y+2) * r + (2*x+3)] = 1;
 357             if (y == 0 || index(params, grid, x, y-1) != i)
 358                 egrid[(2*y+1) * r + (2*x+2)] = 1;
 359             if (y == params->h-1 || index(params, grid, x, y+1) != i)
 360                 egrid[(2*y+3) * r + (2*x+2)] = 1;
 361         }
 362
 363     for (y = 1; y < 2*params->h+2; y++) {
 364         for (x = 1; x < 2*params->w+2; x++) {
 365             if (!((y|x)&1)) {
 366                 int k = numbers ? index(params, numbers, x/2-1, y/2-1) : 0;
 367                 if (k || (all && numbers)) printf("%2d", k); else printf("  ");
 368             } else if (!((y&x)&1)) {
 369                 int v = egrid[y*r+x];
 370                 if ((y&1) && v) v = '-';
 371                 if ((x&1) && v) v = '|';
 372                 if (!v) v = ' ';
 373                 putchar(v);
 374                 if (!(x&1)) putchar(v);
 375             } else {
 376                 int c, d = 0;
 377                 if (egrid[y*r+(x+1)]) d |= 1;
 378                 if (egrid[(y-1)*r+x]) d |= 2;
 379                 if (egrid[y*r+(x-1)]) d |= 4;
 380                 if (egrid[(y+1)*r+x]) d |= 8;
 381                 c = " ??+?-++?+|+++++"[d];
 382                 putchar(c);
 383                 if (!(x&1)) putchar(c);
 384             }
 385         }
 386         putchar('\n');
 387     }
 388
 389     sfree(egrid);
 390 }
 391 #endif
 392
 393 char *new_game_seed(game_params *params, random_state *rs)
 394 {
 395     int *grid, *numbers;
 396     struct rectlist *list;
 397     int x, y, y2, y2last, yx, run, i;
 398     char *seed, *p;
 399     game_params params2real, *params2 = &params2real;
 400
 401     /*
 402      * Set up the smaller width and height which we will use to
 403      * generate the base grid.
 404      */
 405     params2->w = params->w / (1.0F + params->expandfactor);
 406     if (params2->w < 2 && params->w >= 2) params2->w = 2;
 407     params2->h = params->h / (1.0F + params->expandfactor);
 408     if (params2->h < 2 && params->h >= 2) params2->h = 2;
 409
 410     grid = snewn(params2->w * params2->h, int);
 411
 412     for (y = 0; y < params2->h; y++)
 413         for (x = 0; x < params2->w; x++) {
 414             index(params2, grid, x, y) = -1;
 415         }
 416
 417     list = get_rectlist(params2, grid);
 418     assert(list != NULL);
 419
 420     /*
 421      * Place rectangles until we can't any more.
 422      */
 423     while (list->n > 0) {
 424         int i, m;
 425         struct rect r;
 426
 427         /*
 428          * Pick a random rectangle.
 429          */
 430         i = random_upto(rs, list->n);
 431         r = list->rects[i];
 432
 433         /*
 434          * Place it.
 435          */
 436         place_rect(params2, grid, r);
 437
 438         /*
 439          * Winnow the list by removing any rectangles which
 440          * overlap this one.
 441          */
 442         m = 0;
 443         for (i = 0; i < list->n; i++) {
 444             struct rect s = list->rects[i];
 445             if (s.x+s.w <= r.x || r.x+r.w <= s.x ||
 446                 s.y+s.h <= r.y || r.y+r.h <= s.y)
 447                 list->rects[m++] = s;
 448         }
 449         list->n = m;
 450     }
 451
 452     free_rectlist(list);
 453
 454     /*
 455      * Deal with singleton spaces remaining in the grid, one by
 456      * one.
 457      *
 458      * We do this by making a local change to the layout. There are
 459      * several possibilities:
 460      *
 461      *     +-----+-----+    Here, we can remove the singleton by
 462      *     |     |     |    extending the 1x2 rectangle below it
 463      *     +--+--+-----+    into a 1x3.
 464      *     |  |  |     |
 465      *     |  +--+     |
 466      *     |  |  |     |
 467      *     |  |  |     |
 468      *     |  |  |     |
 469      *     +--+--+-----+
 470      *
 471      *     +--+--+--+       Here, that trick doesn't work: there's no
 472      *     |     |  |       1 x n rectangle with the singleton at one
 473      *     |     |  |       end. Instead, we extend a 1 x n rectangle
 474      *     |     |  |       _out_ from the singleton, shaving a layer
 475      *     +--+--+  |       off the end of another rectangle. So if we
 476      *     |  |  |  |       extended up, we'd make our singleton part
 477      *     |  +--+--+       of a 1x3 and generate a 1x2 where the 2x2
 478      *     |  |     |       used to be; or we could extend right into
 479      *     +--+-----+       a 2x1, turning the 1x3 into a 1x2.
 480      *
 481      *     +-----+--+       Here, we can't even do _that_, since any
 482      *     |     |  |       direction we choose to extend the singleton
 483      *     +--+--+  |       will produce a new singleton as a result of
 484      *     |  |  |  |       truncating one of the size-2 rectangles.
 485      *     |  +--+--+       Fortunately, this case can _only_ occur when
 486      *     |  |     |       a singleton is surrounded by four size-2s
 487      *     +--+-----+       in this fashion; so instead we can simply
 488      *                      replace the whole section with a single 3x3.
 489      */
 490     for (x = 0; x < params2->w; x++) {
 491         for (y = 0; y < params2->h; y++) {
 492             if (index(params2, grid, x, y) < 0) {
 493                 int dirs[4], ndirs;
 494
 495 #ifdef GENERATION_DIAGNOSTICS
 496                 display_grid(params2, grid, NULL, FALSE);
 497                 printf("singleton at %d,%d\n", x, y);
 498 #endif
 499
 500                 /*
 501                  * Check in which directions we can feasibly extend
 502                  * the singleton. We can extend in a particular
 503                  * direction iff either:
 504                  *
 505                  *  - the rectangle on that side of the singleton
 506                  *    is not 2x1, and we are at one end of the edge
 507                  *    of it we are touching
 508                  *
 509                  *  - it is 2x1 but we are on its short side.
 510                  *
 511                  * FIXME: we could plausibly choose between these
 512                  * based on the sizes of the rectangles they would
 513                  * create?
 514                  */
 515                 ndirs = 0;
 516                 if (x < params2->w-1) {
 517                     struct rect r = find_rect(params2, grid, x+1, y);
 518                     if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
 519                         dirs[ndirs++] = 1;   /* right */
 520                 }
 521                 if (y > 0) {
 522                     struct rect r = find_rect(params2, grid, x, y-1);
 523                     if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
 524                         dirs[ndirs++] = 2;   /* up */
 525                 }
 526                 if (x > 0) {
 527                     struct rect r = find_rect(params2, grid, x-1, y);
 528                     if ((r.w * r.h > 2 && (r.y==y || r.y+r.h-1==y)) || r.h==1)
 529                         dirs[ndirs++] = 4;   /* left */
 530                 }
 531                 if (y < params2->h-1) {
 532                     struct rect r = find_rect(params2, grid, x, y+1);
 533                     if ((r.w * r.h > 2 && (r.x==x || r.x+r.w-1==x)) || r.w==1)
 534                         dirs[ndirs++] = 8;   /* down */
 535                 }
 536
 537                 if (ndirs > 0) {
 538                     int which, dir;
 539                     struct rect r1, r2;
 540
 541                     which = random_upto(rs, ndirs);
 542                     dir = dirs[which];
 543
 544                     switch (dir) {
 545                       case 1:          /* right */
 546                         assert(x < params2->w+1);
 547 #ifdef GENERATION_DIAGNOSTICS
 548                         printf("extending right\n");
 549 #endif
 550                         r1 = find_rect(params2, grid, x+1, y);
 551                         r2.x = x;
 552                         r2.y = y;
 553                         r2.w = 1 + r1.w;
 554                         r2.h = 1;
 555                         if (r1.y == y)
 556                             r1.y++;
 557                         r1.h--;
 558                         break;
 559                       case 2:          /* up */
 560                         assert(y > 0);
 561 #ifdef GENERATION_DIAGNOSTICS
 562                         printf("extending up\n");
 563 #endif
 564                         r1 = find_rect(params2, grid, x, y-1);
 565                         r2.x = x;
 566                         r2.y = r1.y;
 567                         r2.w = 1;
 568                         r2.h = 1 + r1.h;
 569                         if (r1.x == x)
 570                             r1.x++;
 571                         r1.w--;
 572                         break;
 573                       case 4:          /* left */
 574                         assert(x > 0);
 575 #ifdef GENERATION_DIAGNOSTICS
 576                         printf("extending left\n");
 577 #endif
 578                         r1 = find_rect(params2, grid, x-1, y);
 579                         r2.x = r1.x;
 580                         r2.y = y;
 581                         r2.w = 1 + r1.w;
 582                         r2.h = 1;
 583                         if (r1.y == y)
 584                             r1.y++;
 585                         r1.h--;
 586                         break;
 587                       case 8:          /* down */
 588                         assert(y < params2->h+1);
 589 #ifdef GENERATION_DIAGNOSTICS
 590                         printf("extending down\n");
 591 #endif
 592                         r1 = find_rect(params2, grid, x, y+1);
 593                         r2.x = x;
 594                         r2.y = y;
 595                         r2.w = 1;
 596                         r2.h = 1 + r1.h;
 597                         if (r1.x == x)
 598                             r1.x++;
 599                         r1.w--;
 600                         break;
 601                     }
 602                     if (r1.h > 0 && r1.w > 0)
 603                         place_rect(params2, grid, r1);
 604                     place_rect(params2, grid, r2);
 605                 } else {
 606 #ifndef NDEBUG
 607                     /*
 608                      * Sanity-check that there really is a 3x3
 609                      * rectangle surrounding this singleton and it
 610                      * contains absolutely everything we could
 611                      * possibly need.
 612                      */
 613                     {
 614                         int xx, yy;
 615                         assert(x > 0 && x < params2->w-1);
 616                         assert(y > 0 && y < params2->h-1);
 617
 618                         for (xx = x-1; xx <= x+1; xx++)
 619                             for (yy = y-1; yy <= y+1; yy++) {
 620                                 struct rect r = find_rect(params2,grid,xx,yy);
 621                                 assert(r.x >= x-1);
 622                                 assert(r.y >= y-1);
 623                                 assert(r.x+r.w-1 <= x+1);
 624                                 assert(r.y+r.h-1 <= y+1);
 625                             }
 626                     }
 627 #endif
 628
 629 #ifdef GENERATION_DIAGNOSTICS
 630                     printf("need the 3x3 trick\n");
 631 #endif
 632
 633                     /*
 634                      * FIXME: If the maximum rectangle area for
 635                      * this grid is less than 9, we ought to
 636                      * subdivide the 3x3 in some fashion. There are
 637                      * five other possibilities:
 638                      *
 639                      *  - a 6 and a 3
 640                      *  - a 4, a 3 and a 2
 641                      *  - three 3s
 642                      *  - a 3 and three 2s (two different arrangements).
 643                      */
 644
 645                     {
 646                         struct rect r;
 647                         r.x = x-1;
 648                         r.y = y-1;
 649                         r.w = r.h = 3;
 650                         place_rect(params2, grid, r);
 651                     }
 652                 }
 653             }
 654         }
 655     }
 656
 657     /*
 658      * We have now constructed a grid of the size specified in
 659      * params2. Now we extend it into a grid of the size specified
 660      * in params. We do this in two passes: we extend it vertically
 661      * until it's the right height, then we transpose it, then
 662      * extend it vertically again (getting it effectively the right
 663      * width), then finally transpose again.
 664      */
 665     for (i = 0; i < 2; i++) {
 666         int *grid2, *expand, *where;
 667         game_params params3real, *params3 = &params3real;
 668
 669 #ifdef GENERATION_DIAGNOSTICS
 670         printf("before expansion:\n");
 671         display_grid(params2, grid, NULL, TRUE);
 672 #endif
 673
 674         /*
 675          * Set up the new grid.
 676          */
 677         grid2 = snewn(params2->w * params->h, int);
 678         expand = snewn(params2->h-1, int);
 679         where = snewn(params2->w, int);
 680         params3->w = params2->w;
 681         params3->h = params->h;
 682
 683         /*
 684          * Decide which horizontal edges are going to get expanded,
 685          * and by how much.
 686          */
 687         for (y = 0; y < params2->h-1; y++)
 688             expand[y] = 0;
 689         for (y = params2->h; y < params->h; y++) {
 690             x = random_upto(rs, params2->h-1);
 691             expand[x]++;
 692         }
 693
 694 #ifdef GENERATION_DIAGNOSTICS
 695         printf("expand[] = {");
 696         for (y = 0; y < params2->h-1; y++)
 697             printf(" %d", expand[y]);
 698         printf(" }\n");
 699 #endif
 700
 701         /*
 702          * Perform the expansion. The way this works is that we
 703          * alternately:
 704          *
 705          *  - copy a row from grid into grid2
 706          *
 707          *  - invent some number of additional rows in grid2 where
 708          *    there was previously only a horizontal line between
 709          *    rows in grid, and make random decisions about where
 710          *    among these to place each rectangle edge that ran
 711          *    along this line.
 712          */
 713         for (y = y2 = y2last = 0; y < params2->h; y++) {
 714             /*
 715              * Copy a single line from row y of grid into row y2 of
 716              * grid2.
 717              */
 718             for (x = 0; x < params2->w; x++) {
 719                 int val = index(params2, grid, x, y);
 720                 if (val / params2->w == y &&   /* rect starts on this line */
 721                     (y2 == 0 ||        /* we're at the very top, or... */
 722                      index(params3, grid2, x, y2-1) / params3->w < y2last
 723                                        /* this rect isn't already started */))
 724                     index(params3, grid2, x, y2) =
 725                     INDEX(params3, val % params2->w, y2);
 726                 else
 727                     index(params3, grid2, x, y2) =
 728                     index(params3, grid2, x, y2-1);
 729             }
 730
 731             /*
 732              * If that was the last line, terminate the loop early.
 733              */
 734             if (++y2 == params3->h)
 735                 break;
 736
 737             y2last = y2;
 738
 739             /*
 740              * Invent some number of additional lines. First walk
 741              * along this line working out where to put all the
 742              * edges that coincide with it.
 743              */
 744             yx = -1;
 745             for (x = 0; x < params2->w; x++) {
 746                 if (index(params2, grid, x, y) !=
 747                     index(params2, grid, x, y+1)) {
 748                     /*
 749                      * This is a horizontal edge, so it needs
 750                      * placing.
 751                      */
 752                     if (x == 0 ||
 753                         (index(params2, grid, x-1, y) !=
 754                          index(params2, grid, x, y) &&
 755                          index(params2, grid, x-1, y+1) !=
 756                          index(params2, grid, x, y+1))) {
 757                         /*
 758                          * Here we have the chance to make a new
 759                          * decision.
 760                          */
 761                         yx = random_upto(rs, expand[y]+1);
 762                     } else {
 763                         /*
 764                          * Here we just reuse the previous value of
 765                          * yx.
 766                          */
 767                     }
 768                 } else
 769                     yx = -1;
 770                 where[x] = yx;
 771             }
 772
 773             for (yx = 0; yx < expand[y]; yx++) {
 774                 /*
 775                  * Invent a single row. For each square in the row,
 776                  * we copy the grid entry from the square above it,
 777                  * unless we're starting the new rectangle here.
 778                  */
 779                 for (x = 0; x < params2->w; x++) {
 780                     if (yx == where[x]) {
 781                         int val = index(params2, grid, x, y+1);
 782                         val %= params2->w;
 783                         val = INDEX(params3, val, y2);
 784                         index(params3, grid2, x, y2) = val;
 785                     } else
 786                         index(params3, grid2, x, y2) =
 787                         index(params3, grid2, x, y2-1);
 788                 }
 789
 790                 y2++;
 791             }
 792         }
 793
 794         sfree(expand);
 795         sfree(where);
 796
 797 #ifdef GENERATION_DIAGNOSTICS
 798         printf("after expansion:\n");
 799         display_grid(params3, grid2, NULL, TRUE);
 800 #endif
 801         /*
 802          * Transpose.
 803          */
 804         params2->w = params3->h;
 805         params2->h = params3->w;
 806         sfree(grid);
 807         grid = snewn(params2->w * params2->h, int);
 808         for (x = 0; x < params2->w; x++)
 809             for (y = 0; y < params2->h; y++) {
 810                 int idx1 = INDEX(params2, x, y);
 811                 int idx2 = INDEX(params3, y, x);
 812                 int tmp;
 813
 814                 tmp = grid2[idx2];
 815                 tmp = (tmp % params3->w) * params2->w + (tmp / params3->w);
 816                 grid[idx1] = tmp;
 817             }
 818
 819         sfree(grid2);
 820
 821         {
 822             int tmp;
 823             tmp = params->w;
 824             params->w = params->h;
 825             params->h = tmp;
 826         }
 827
 828 #ifdef GENERATION_DIAGNOSTICS
 829         printf("after transposition:\n");
 830         display_grid(params2, grid, NULL, TRUE);
 831 #endif
 832     }
 833
 834     /*
 835      * Place numbers.
 836      */
 837     numbers = snewn(params->w * params->h, int);
 838
 839     for (y = 0; y < params->h; y++)
 840         for (x = 0; x < params->w; x++) {
 841             index(params, numbers, x, y) = 0;
 842         }
 843
 844     for (x = 0; x < params->w; x++) {
 845         for (y = 0; y < params->h; y++) {
 846             int idx = INDEX(params, x, y);
 847             if (index(params, grid, x, y) == idx) {
 848                 struct rect r = find_rect(params, grid, x, y);
 849                 int n, xx, yy;
 850
 851                 /*
 852                  * Decide where to put the number.
 853                  */
 854                 n = random_upto(rs, r.w*r.h);
 855                 yy = n / r.w;
 856                 xx = n % r.w;
 857                 index(params,numbers,x+xx,y+yy) = r.w*r.h;
 858             }
 859         }
 860     }
 861
 862 #ifdef GENERATION_DIAGNOSTICS
 863     display_grid(params, grid, numbers, FALSE);
 864 #endif
 865
 866     seed = snewn(11 * params->w * params->h, char);
 867     p = seed;
 868     run = 0;
 869     for (i = 0; i <= params->w * params->h; i++) {
 870         int n = (i < params->w * params->h ? numbers[i] : -1);
 871
 872         if (!n)
 873             run++;
 874         else {
 875             if (run) {
 876                 while (run > 0) {
 877                     int c = 'a' - 1 + run;
 878                     if (run > 26)
 879                         c = 'z';
 880                     *p++ = c;
 881                     run -= c - ('a' - 1);
 882                 }
 883             } else {
 884                 *p++ = '_';
 885             }
 886             if (n > 0)
 887                 p += sprintf(p, "%d", n);
 888             run = 0;
 889         }
 890     }
 891     *p = '\0';
 892
 893     sfree(grid);
 894     sfree(numbers);
 895
 896     return seed;
 897 }
 898
 899 char *validate_seed(game_params *params, char *seed)
 900 {
 901     int area = params->w * params->h;
 902     int squares = 0;
 903
 904     while (*seed) {
 905         int n = *seed++;
 906         if (n >= 'a' && n <= 'z') {
 907             squares += n - 'a' + 1;
 908         } else if (n == '_') {
 909             /* do nothing */;
 910         } else if (n > '0' && n <= '9') {
 911             squares++;
 912             while (*seed >= '0' && *seed <= '9')
 913                 seed++;
 914         } else
 915             return "Invalid character in game specification";
 916     }
 917
 918     if (squares < area)
 919         return "Not enough data to fill grid";
 920
 921     if (squares > area)
 922         return "Too much data to fit in grid";
 923
 924     return NULL;
 925 }
 926
 927 game_state *new_game(game_params *params, char *seed)
 928 {
 929     game_state *state = snew(game_state);
 930     int x, y, i, area;
 931
 932     state->w = params->w;
 933     state->h = params->h;
 934
 935     area = state->w * state->h;
 936
 937     state->grid = snewn(area, int);
 938     state->vedge = snewn(area, unsigned char);
 939     state->hedge = snewn(area, unsigned char);
 940     state->completed = FALSE;
 941
 942     i = 0;
 943     while (*seed) {
 944         int n = *seed++;
 945         if (n >= 'a' && n <= 'z') {
 946             int run = n - 'a' + 1;
 947             assert(i + run <= area);
 948             while (run-- > 0)
 949                 state->grid[i++] = 0;
 950         } else if (n == '_') {
 951             /* do nothing */;
 952         } else if (n > '0' && n <= '9') {
 953             assert(i < area);
 954             state->grid[i++] = atoi(seed-1);
 955             while (*seed >= '0' && *seed <= '9')
 956                 seed++;
 957         } else {
 958             assert(!"We can't get here");
 959         }
 960     }
 961     assert(i == area);
 962
 963     for (y = 0; y < state->h; y++)
 964         for (x = 0; x < state->w; x++)
 965             vedge(state,x,y) = hedge(state,x,y) = 0;
 966
 967     return state;
 968 }
 969
 970 game_state *dup_game(game_state *state)
 971 {
 972     game_state *ret = snew(game_state);
 973
 974     ret->w = state->w;
 975     ret->h = state->h;
 976
 977     ret->vedge = snewn(state->w * state->h, unsigned char);
 978     ret->hedge = snewn(state->w * state->h, unsigned char);
 979     ret->grid = snewn(state->w * state->h, int);
 980
 981     ret->completed = state->completed;
 982
 983     memcpy(ret->grid, state->grid, state->w * state->h * sizeof(int));
 984     memcpy(ret->vedge, state->vedge, state->w*state->h*sizeof(unsigned char));
 985     memcpy(ret->hedge, state->hedge, state->w*state->h*sizeof(unsigned char));
 986
 987     return ret;
 988 }
 989
 990 void free_game(game_state *state)
 991 {
 992     sfree(state->grid);
 993     sfree(state->vedge);
 994     sfree(state->hedge);
 995     sfree(state);
 996 }
 997
 998 static unsigned char *get_correct(game_state *state)
 999 {
1000     unsigned char *ret;
1001     int x, y;
1002
1003     ret = snewn(state->w * state->h, unsigned char);
1004     memset(ret, 0xFF, state->w * state->h);
1005
1006     for (x = 0; x < state->w; x++)
1007         for (y = 0; y < state->h; y++)
1008             if (index(state,ret,x,y) == 0xFF) {
1009                 int rw, rh;
1010                 int xx, yy;
1011                 int num, area, valid;
1012
1013                 /*
1014                  * Find a rectangle starting at this point.
1015                  */
1016                 rw = 1;
1017                 while (x+rw < state->w && !vedge(state,x+rw,y))
1018                     rw++;
1019                 rh = 1;
1020                 while (y+rh < state->h && !hedge(state,x,y+rh))
1021                     rh++;
1022
1023                 /*
1024                  * We know what the dimensions of the rectangle
1025                  * should be if it's there at all. Find out if we
1026                  * really have a valid rectangle.
1027                  */
1028                 valid = TRUE;
1029                 /* Check the horizontal edges. */
1030                 for (xx = x; xx < x+rw; xx++) {
1031                     for (yy = y; yy <= y+rh; yy++) {
1032                         int e = !HRANGE(state,xx,yy) || hedge(state,xx,yy);
1033                         int ec = (yy == y || yy == y+rh);
1034                         if (e != ec)
1035                             valid = FALSE;
1036                     }
1037                 }
1038                 /* Check the vertical edges. */
1039                 for (yy = y; yy < y+rh; yy++) {
1040                     for (xx = x; xx <= x+rw; xx++) {
1041                         int e = !VRANGE(state,xx,yy) || vedge(state,xx,yy);
1042                         int ec = (xx == x || xx == x+rw);
1043                         if (e != ec)
1044                             valid = FALSE;
1045                     }
1046                 }
1047
1048                 /*
1049                  * If this is not a valid rectangle with no other
1050                  * edges inside it, we just mark this square as not
1051                  * complete and proceed to the next square.
1052                  */
1053                 if (!valid) {
1054                     index(state, ret, x, y) = 0;
1055                     continue;
1056                 }
1057
1058                 /*
1059                  * We have a rectangle. Now see what its area is,
1060                  * and how many numbers are in it.
1061                  */
1062                 num = 0;
1063                 area = 0;
1064                 for (xx = x; xx < x+rw; xx++) {
1065                     for (yy = y; yy < y+rh; yy++) {
1066                         area++;
1067                         if (grid(state,xx,yy)) {
1068                             if (num > 0)
1069                                 valid = FALSE;   /* two numbers */
1070                             num = grid(state,xx,yy);
1071                         }
1072                     }
1073                 }
1074                 if (num != area)
1075                     valid = FALSE;
1076
1077                 /*
1078                  * Now fill in the whole rectangle based on the
1079                  * value of `valid'.
1080                  */
1081                 for (xx = x; xx < x+rw; xx++) {
1082                     for (yy = y; yy < y+rh; yy++) {
1083                         index(state, ret, xx, yy) = valid;
1084                     }
1085                 }
1086             }
1087
1088     return ret;
1089 }
1090
1091 struct game_ui {
1092     /*
1093      * These coordinates are 2 times the obvious grid coordinates.
1094      * Hence, the top left of the grid is (0,0), the grid point to
1095      * the right of that is (2,0), the one _below that_ is (2,2)
1096      * and so on. This is so that we can specify a drag start point
1097      * on an edge (one odd coordinate) or in the middle of a square
1098      * (two odd coordinates) rather than always at a corner.
1099      *
1100      * -1,-1 means no drag is in progress.
1101      */
1102     int drag_start_x;
1103     int drag_start_y;
1104     int drag_end_x;
1105     int drag_end_y;
1106     /*
1107      * This flag is set as soon as a dragging action moves the
1108      * mouse pointer away from its starting point, so that even if
1109      * the pointer _returns_ to its starting point the action is
1110      * treated as a small drag rather than a click.
1111      */
1112     int dragged;
1113 };
1114
1115 game_ui *new_ui(game_state *state)
1116 {
1117     game_ui *ui = snew(game_ui);
1118     ui->drag_start_x = -1;
1119     ui->drag_start_y = -1;
1120     ui->drag_end_x = -1;
1121     ui->drag_end_y = -1;
1122     ui->dragged = FALSE;
1123     return ui;
1124 }
1125
1126 void free_ui(game_ui *ui)
1127 {
1128     sfree(ui);
1129 }
1130
1131 void coord_round(float x, float y, int *xr, int *yr)
1132 {
1133     float xs, ys, xv, yv, dx, dy, dist;
1134
1135     /*
1136      * Find the nearest square-centre.
1137      */
1138     xs = (float)floor(x) + 0.5F;
1139     ys = (float)floor(y) + 0.5F;
1140
1141     /*
1142      * And find the nearest grid vertex.
1143      */
1144     xv = (float)floor(x + 0.5F);
1145     yv = (float)floor(y + 0.5F);
1146
1147     /*
1148      * We allocate clicks in parts of the grid square to either
1149      * corners, edges or square centres, as follows:
1150      *
1151      *   +--+--------+--+
1152      *   |  |        |  |
1153      *   +--+        +--+
1154      *   |   `.    ,'   |
1155      *   |     +--+     |
1156      *   |     |  |     |
1157      *   |     +--+     |
1158      *   |   ,'    `.   |
1159      *   +--+        +--+
1160      *   |  |        |  |
1161      *   +--+--------+--+
1162      *
1163      * (Not to scale!)
1164      *
1165      * In other words: we measure the square distance (i.e.
1166      * max(dx,dy)) from the click to the nearest corner, and if
1167      * it's within CORNER_TOLERANCE then we return a corner click.
1168      * We measure the square distance from the click to the nearest
1169      * centre, and if that's within CENTRE_TOLERANCE we return a
1170      * centre click. Failing that, we find which of the two edge
1171      * centres is nearer to the click and return that edge.
1172      */
1173
1174     /*
1175      * Check for corner click.
1176      */
1177     dx = (float)fabs(x - xv);
1178     dy = (float)fabs(y - yv);
1179     dist = (dx > dy ? dx : dy);
1180     if (dist < CORNER_TOLERANCE) {
1181         *xr = 2 * (int)xv;
1182         *yr = 2 * (int)yv;
1183     } else {
1184         /*
1185          * Check for centre click.
1186          */
1187         dx = (float)fabs(x - xs);
1188         dy = (float)fabs(y - ys);
1189         dist = (dx > dy ? dx : dy);
1190         if (dist < CENTRE_TOLERANCE) {
1191             *xr = 1 + 2 * (int)xs;
1192             *yr = 1 + 2 * (int)ys;
1193         } else {
1194             /*
1195              * Failing both of those, see which edge we're closer to.
1196              * Conveniently, this is simply done by testing the relative
1197              * magnitude of dx and dy (which are currently distances from
1198              * the square centre).
1199              */
1200             if (dx > dy) {
1201                 /* Vertical edge: x-coord of corner,
1202                  * y-coord of square centre. */
1203                 *xr = 2 * (int)xv;
1204                 *yr = 1 + 2 * (int)ys;
1205             } else {
1206                 /* Horizontal edge: x-coord of square centre,
1207                  * y-coord of corner. */
1208                 *xr = 1 + 2 * (int)xs;
1209                 *yr = 2 * (int)yv;
1210             }
1211         }
1212     }
1213 }
1214
1215 static void ui_draw_rect(game_state *state, game_ui *ui,
1216                          unsigned char *hedge, unsigned char *vedge, int c)
1217 {
1218     int x1, x2, y1, y2, x, y, t;
1219
1220     x1 = ui->drag_start_x;
1221     x2 = ui->drag_end_x;
1222     if (x2 < x1) { t = x1; x1 = x2; x2 = t; }
1223
1224     y1 = ui->drag_start_y;
1225     y2 = ui->drag_end_y;
1226     if (y2 < y1) { t = y1; y1 = y2; y2 = t; }
1227
1228     x1 = x1 / 2;               /* rounds down */
1229     x2 = (x2+1) / 2;           /* rounds up */
1230     y1 = y1 / 2;               /* rounds down */
1231     y2 = (y2+1) / 2;           /* rounds up */
1232
1233     /*
1234      * Draw horizontal edges of rectangles.
1235      */
1236     for (x = x1; x < x2; x++)
1237         for (y = y1; y <= y2; y++)
1238             if (HRANGE(state,x,y)) {
1239                 int val = index(state,hedge,x,y);
1240                 if (y == y1 || y == y2)
1241                     val = c;
1242                 else if (c == 1)
1243                     val = 0;
1244                 index(state,hedge,x,y) = val;
1245             }
1246
1247     /*
1248      * Draw vertical edges of rectangles.
1249      */
1250     for (y = y1; y < y2; y++)
1251         for (x = x1; x <= x2; x++)
1252             if (VRANGE(state,x,y)) {
1253                 int val = index(state,vedge,x,y);
1254                 if (x == x1 || x == x2)
1255                     val = c;
1256                 else if (c == 1)
1257                     val = 0;
1258                 index(state,vedge,x,y) = val;
1259             }
1260 }
1261
1262 game_state *make_move(game_state *from, game_ui *ui, int x, int y, int button)
1263 {
1264     int xc, yc;
1265     int startdrag = FALSE, enddrag = FALSE, active = FALSE;
1266     game_state *ret;
1267
1268     if (button == LEFT_BUTTON) {
1269         startdrag = TRUE;
1270     } else if (button == LEFT_RELEASE) {
1271         enddrag = TRUE;
1272     } else if (button != LEFT_DRAG) {
1273         return NULL;
1274     }
1275
1276     coord_round(FROMCOORD((float)x), FROMCOORD((float)y), &xc, &yc);
1277
1278     if (startdrag) {
1279         ui->drag_start_x = xc;
1280         ui->drag_start_y = yc;
1281         ui->drag_end_x = xc;
1282         ui->drag_end_y = yc;
1283         ui->dragged = FALSE;
1284         active = TRUE;
1285     }
1286
1287     if (xc != ui->drag_end_x || yc != ui->drag_end_y) {
1288         ui->drag_end_x = xc;
1289         ui->drag_end_y = yc;
1290         ui->dragged = TRUE;
1291         active = TRUE;
1292     }
1293
1294     ret = NULL;
1295
1296     if (enddrag) {
1297         if (xc >= 0 && xc <= 2*from->w &&
1298             yc >= 0 && yc <= 2*from->h) {
1299             ret = dup_game(from);
1300
1301             if (ui->dragged) {
1302                 ui_draw_rect(ret, ui, ret->hedge, ret->vedge, 1);
1303             } else {
1304                 if ((xc & 1) && !(yc & 1) && HRANGE(from,xc/2,yc/2)) {
1305                     hedge(ret,xc/2,yc/2) = !hedge(ret,xc/2,yc/2);
1306                 }
1307                 if ((yc & 1) && !(xc & 1) && VRANGE(from,xc/2,yc/2)) {
1308                     vedge(ret,xc/2,yc/2) = !vedge(ret,xc/2,yc/2);
1309                 }
1310             }
1311
1312             if (!memcmp(ret->hedge, from->hedge, from->w*from->h) &&
1313                 !memcmp(ret->vedge, from->vedge, from->w*from->h)) {
1314                 free_game(ret);
1315                 ret = NULL;
1316             }
1317
1318             /*
1319              * We've made a real change to the grid. Check to see
1320              * if the game has been completed.
1321              */
1322             if (ret && !ret->completed) {
1323                 int x, y, ok;
1324                 unsigned char *correct = get_correct(ret);
1325
1326                 ok = TRUE;
1327                 for (x = 0; x < ret->w; x++)
1328                     for (y = 0; y < ret->h; y++)
1329                         if (!index(ret, correct, x, y))
1330                             ok = FALSE;
1331
1332                 sfree(correct);
1333
1334                 if (ok)
1335                     ret->completed = TRUE;
1336             }
1337         }
1338
1339         ui->drag_start_x = -1;
1340         ui->drag_start_y = -1;
1341         ui->drag_end_x = -1;
1342         ui->drag_end_y = -1;
1343         ui->dragged = FALSE;
1344         active = TRUE;
1345     }
1346
1347     if (ret)
1348         return ret;                    /* a move has been made */
1349     else if (active)
1350         return from;                   /* UI activity has occurred */
1351     else
1352         return NULL;
1353 }
1354
1355 /* ----------------------------------------------------------------------
1356  * Drawing routines.
1357  */
1358
1359 #define CORRECT 65536
1360
1361 #define COLOUR(k) ( (k)==1 ? COL_LINE : COL_DRAG )
1362 #define MAX(x,y) ( (x)>(y) ? (x) : (y) )
1363 #define MAX4(x,y,z,w) ( MAX(MAX(x,y),MAX(z,w)) )
1364
1365 struct game_drawstate {
1366     int started;
1367     int w, h;
1368     unsigned int *visible;
1369 };
1370
1371 void game_size(game_params *params, int *x, int *y)
1372 {
1373     *x = params->w * TILE_SIZE + 2*BORDER + 1;
1374     *y = params->h * TILE_SIZE + 2*BORDER + 1;
1375 }
1376
1377 float *game_colours(frontend *fe, game_state *state, int *ncolours)
1378 {
1379     float *ret = snewn(3 * NCOLOURS, float);
1380
1381     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1382
1383     ret[COL_GRID * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1384     ret[COL_GRID * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1385     ret[COL_GRID * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
1386
1387     ret[COL_DRAG * 3 + 0] = 1.0F;
1388     ret[COL_DRAG * 3 + 1] = 0.0F;
1389     ret[COL_DRAG * 3 + 2] = 0.0F;
1390
1391     ret[COL_CORRECT * 3 + 0] = 0.75F * ret[COL_BACKGROUND * 3 + 0];
1392     ret[COL_CORRECT * 3 + 1] = 0.75F * ret[COL_BACKGROUND * 3 + 1];
1393     ret[COL_CORRECT * 3 + 2] = 0.75F * ret[COL_BACKGROUND * 3 + 2];
1394
1395     ret[COL_LINE * 3 + 0] = 0.0F;
1396     ret[COL_LINE * 3 + 1] = 0.0F;
1397     ret[COL_LINE * 3 + 2] = 0.0F;
1398
1399     ret[COL_TEXT * 3 + 0] = 0.0F;
1400     ret[COL_TEXT * 3 + 1] = 0.0F;
1401     ret[COL_TEXT * 3 + 2] = 0.0F;
1402
1403     *ncolours = NCOLOURS;
1404     return ret;
1405 }
1406
1407 game_drawstate *game_new_drawstate(game_state *state)
1408 {
1409     struct game_drawstate *ds = snew(struct game_drawstate);
1410     int i;
1411
1412     ds->started = FALSE;
1413     ds->w = state->w;
1414     ds->h = state->h;
1415     ds->visible = snewn(ds->w * ds->h, unsigned int);
1416     for (i = 0; i < ds->w * ds->h; i++)
1417         ds->visible[i] = 0xFFFF;
1418
1419     return ds;
1420 }
1421
1422 void game_free_drawstate(game_drawstate *ds)
1423 {
1424     sfree(ds->visible);
1425     sfree(ds);
1426 }
1427
1428 void draw_tile(frontend *fe, game_state *state, int x, int y,
1429                unsigned char *hedge, unsigned char *vedge,
1430                unsigned char *corners, int correct)
1431 {
1432     int cx = COORD(x), cy = COORD(y);
1433     char str[80];
1434
1435     draw_rect(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1, COL_GRID);
1436     draw_rect(fe, cx+1, cy+1, TILE_SIZE-1, TILE_SIZE-1,
1437               correct ? COL_CORRECT : COL_BACKGROUND);
1438
1439     if (grid(state,x,y)) {
1440         sprintf(str, "%d", grid(state,x,y));
1441         draw_text(fe, cx+TILE_SIZE/2, cy+TILE_SIZE/2, FONT_VARIABLE,
1442                   TILE_SIZE/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_TEXT, str);
1443     }
1444
1445     /*
1446      * Draw edges.
1447      */
1448     if (!HRANGE(state,x,y) || index(state,hedge,x,y))
1449         draw_rect(fe, cx, cy, TILE_SIZE+1, 2,
1450                   HRANGE(state,x,y) ? COLOUR(index(state,hedge,x,y)) :
1451                   COL_LINE);
1452     if (!HRANGE(state,x,y+1) || index(state,hedge,x,y+1))
1453         draw_rect(fe, cx, cy+TILE_SIZE-1, TILE_SIZE+1, 2,
1454                   HRANGE(state,x,y+1) ? COLOUR(index(state,hedge,x,y+1)) :
1455                   COL_LINE);
1456     if (!VRANGE(state,x,y) || index(state,vedge,x,y))
1457         draw_rect(fe, cx, cy, 2, TILE_SIZE+1,
1458                   VRANGE(state,x,y) ? COLOUR(index(state,vedge,x,y)) :
1459                   COL_LINE);
1460     if (!VRANGE(state,x+1,y) || index(state,vedge,x+1,y))
1461         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, TILE_SIZE+1,
1462                   VRANGE(state,x+1,y) ? COLOUR(index(state,vedge,x+1,y)) :
1463                   COL_LINE);
1464
1465     /*
1466      * Draw corners.
1467      */
1468     if (index(state,corners,x,y))
1469         draw_rect(fe, cx, cy, 2, 2,
1470                   COLOUR(index(state,corners,x,y)));
1471     if (x+1 < state->w && index(state,corners,x+1,y))
1472         draw_rect(fe, cx+TILE_SIZE-1, cy, 2, 2,
1473                   COLOUR(index(state,corners,x+1,y)));
1474     if (y+1 < state->h && index(state,corners,x,y+1))
1475         draw_rect(fe, cx, cy+TILE_SIZE-1, 2, 2,
1476                   COLOUR(index(state,corners,x,y+1)));
1477     if (x+1 < state->w && y+1 < state->h && index(state,corners,x+1,y+1))
1478         draw_rect(fe, cx+TILE_SIZE-1, cy+TILE_SIZE-1, 2, 2,
1479                   COLOUR(index(state,corners,x+1,y+1)));
1480
1481     draw_update(fe, cx, cy, TILE_SIZE+1, TILE_SIZE+1);
1482 }
1483
1484 void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1485                  game_state *state, int dir, game_ui *ui,
1486                  float animtime, float flashtime)
1487 {
1488     int x, y;
1489     unsigned char *correct;
1490     unsigned char *hedge, *vedge, *corners;
1491
1492     correct = get_correct(state);
1493
1494     if (ui->dragged) {
1495         hedge = snewn(state->w*state->h, unsigned char);
1496         vedge = snewn(state->w*state->h, unsigned char);
1497         memcpy(hedge, state->hedge, state->w*state->h);
1498         memcpy(vedge, state->vedge, state->w*state->h);
1499         ui_draw_rect(state, ui, hedge, vedge, 2);
1500     } else {
1501         hedge = state->hedge;
1502         vedge = state->vedge;
1503     }
1504
1505     corners = snewn(state->w * state->h, unsigned char);
1506     memset(corners, 0, state->w * state->h);
1507     for (x = 0; x < state->w; x++)
1508         for (y = 0; y < state->h; y++) {
1509             if (x > 0) {
1510                 int e = index(state, vedge, x, y);
1511                 if (index(state,corners,x,y) < e)
1512                     index(state,corners,x,y) = e;
1513                 if (y+1 < state->h &&
1514                     index(state,corners,x,y+1) < e)
1515                     index(state,corners,x,y+1) = e;
1516             }
1517             if (y > 0) {
1518                 int e = index(state, hedge, x, y);
1519                 if (index(state,corners,x,y) < e)
1520                     index(state,corners,x,y) = e;
1521                 if (x+1 < state->w &&
1522                     index(state,corners,x+1,y) < e)
1523                     index(state,corners,x+1,y) = e;
1524             }
1525         }
1526
1527     if (!ds->started) {
1528         draw_rect(fe, 0, 0,
1529                   state->w * TILE_SIZE + 2*BORDER + 1,
1530                   state->h * TILE_SIZE + 2*BORDER + 1, COL_BACKGROUND);
1531         draw_rect(fe, COORD(0)-1, COORD(0)-1,
1532                   ds->w*TILE_SIZE+3, ds->h*TILE_SIZE+3, COL_LINE);
1533         ds->started = TRUE;
1534         draw_update(fe, 0, 0,
1535                     state->w * TILE_SIZE + 2*BORDER + 1,
1536                     state->h * TILE_SIZE + 2*BORDER + 1);
1537     }
1538
1539     for (x = 0; x < state->w; x++)
1540         for (y = 0; y < state->h; y++) {
1541             unsigned int c = 0;
1542
1543             if (HRANGE(state,x,y))
1544                 c |= index(state,hedge,x,y);
1545             if (HRANGE(state,x,y+1))
1546                 c |= index(state,hedge,x,y+1) << 2;
1547             if (VRANGE(state,x,y))
1548                 c |= index(state,vedge,x,y) << 4;
1549             if (VRANGE(state,x+1,y))
1550                 c |= index(state,vedge,x+1,y) << 6;
1551             c |= index(state,corners,x,y) << 8;
1552             if (x+1 < state->w)
1553                 c |= index(state,corners,x+1,y) << 10;
1554             if (y+1 < state->h)
1555                 c |= index(state,corners,x,y+1) << 12;
1556             if (x+1 < state->w && y+1 < state->h)
1557                 c |= index(state,corners,x+1,y+1) << 14;
1558             if (index(state, correct, x, y) && !flashtime)
1559                 c |= CORRECT;
1560
1561             if (index(ds,ds->visible,x,y) != c) {
1562                 draw_tile(fe, state, x, y, hedge, vedge, corners, c & CORRECT);
1563                 index(ds,ds->visible,x,y) = c;
1564             }
1565         }
1566
1567     if (hedge != state->hedge) {
1568         sfree(hedge);
1569         sfree(vedge);
1570    }
1571
1572     sfree(corners);
1573     sfree(correct);
1574 }
1575
1576 float game_anim_length(game_state *oldstate, game_state *newstate, int dir)
1577 {
1578     return 0.0F;
1579 }
1580
1581 float game_flash_length(game_state *oldstate, game_state *newstate, int dir)
1582 {
1583     if (!oldstate->completed && newstate->completed)
1584         return FLASH_TIME;
1585     return 0.0F;
1586 }
1587
1588 int game_wants_statusbar(void)
1589 {
1590     return FALSE;
1591 }