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