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