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