pegs.c

   1 /*
   2  * pegs.c: the classic Peg Solitaire game.
   3  */
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8 #include <assert.h>
   9 #include <ctype.h>
  10 #include <math.h>
  11
  12 #include "puzzles.h"
  13 #include "tree234.h"
  14
  15 #define GRID_HOLE 0
  16 #define GRID_PEG  1
  17 #define GRID_OBST 2
  18
  19 enum {
  20     COL_BACKGROUND,
  21     COL_HIGHLIGHT,
  22     COL_LOWLIGHT,
  23     COL_PEG,
  24     NCOLOURS
  25 };
  26
  27 /*
  28  * Grid shapes. I do some macro ickery here to ensure that my enum
  29  * and the various forms of my name list always match up.
  30  */
  31 #define TYPELIST(A) \
  32     A(CROSS,Cross,cross) \
  33     A(OCTAGON,Octagon,octagon) \
  34     A(RANDOM,Random,random)
  35 #define ENUM(upper,title,lower) TYPE_ ## upper,
  36 #define TITLE(upper,title,lower) #title,
  37 #define LOWER(upper,title,lower) #lower,
  38 #define CONFIG(upper,title,lower) ":" #title
  39
  40 enum { TYPELIST(ENUM) TYPECOUNT };
  41 static char const *const pegs_titletypes[] = { TYPELIST(TITLE) };
  42 static char const *const pegs_lowertypes[] = { TYPELIST(LOWER) };
  43 #define TYPECONFIG TYPELIST(CONFIG)
  44
  45 #define FLASH_FRAME 0.13F
  46
  47 struct game_params {
  48     int w, h;
  49     int type;
  50 };
  51
  52 struct game_state {
  53     int w, h;
  54     int completed;
  55     unsigned char *grid;
  56 };
  57
  58 static game_params *default_params(void)
  59 {
  60     game_params *ret = snew(game_params);
  61
  62     ret->w = ret->h = 7;
  63     ret->type = TYPE_CROSS;
  64
  65     return ret;
  66 }
  67
  68 static const struct game_params pegs_presets[] = {
  69     {7, 7, TYPE_CROSS},
  70     {7, 7, TYPE_OCTAGON},
  71     {5, 5, TYPE_RANDOM},
  72     {7, 7, TYPE_RANDOM},
  73     {9, 9, TYPE_RANDOM},
  74 };
  75
  76 static int game_fetch_preset(int i, char **name, game_params **params)
  77 {
  78     game_params *ret;
  79     char str[80];
  80
  81     if (i < 0 || i >= lenof(pegs_presets))
  82         return FALSE;
  83
  84     ret = snew(game_params);
  85     *ret = pegs_presets[i];
  86
  87     strcpy(str, pegs_titletypes[ret->type]);
  88     if (ret->type == TYPE_RANDOM)
  89         sprintf(str + strlen(str), " %dx%d", ret->w, ret->h);
  90
  91     *name = dupstr(str);
  92     *params = ret;
  93     return TRUE;
  94 }
  95
  96 static void free_params(game_params *params)
  97 {
  98     sfree(params);
  99 }
 100
 101 static game_params *dup_params(game_params *params)
 102 {
 103     game_params *ret = snew(game_params);
 104     *ret = *params;                    /* structure copy */
 105     return ret;
 106 }
 107
 108 static void decode_params(game_params *params, char const *string)
 109 {
 110     char const *p = string;
 111     int i;
 112
 113     params->w = atoi(p);
 114     while (*p && isdigit((unsigned char)*p)) p++;
 115     if (*p == 'x') {
 116         p++;
 117         params->h = atoi(p);
 118         while (*p && isdigit((unsigned char)*p)) p++;
 119     } else {
 120         params->h = params->w;
 121     }
 122
 123     for (i = 0; i < lenof(pegs_lowertypes); i++)
 124         if (!strcmp(p, pegs_lowertypes[i]))
 125             params->type = i;
 126 }
 127
 128 static char *encode_params(game_params *params, int full)
 129 {
 130     char str[80];
 131
 132     sprintf(str, "%dx%d", params->w, params->h);
 133     if (full) {
 134         assert(params->type >= 0 && params->type < lenof(pegs_lowertypes));
 135         strcat(str, pegs_lowertypes[params->type]);
 136     }
 137     return dupstr(str);
 138 }
 139
 140 static config_item *game_configure(game_params *params)
 141 {
 142     config_item *ret = snewn(4, config_item);
 143     char buf[80];
 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 = "Board type";
 158     ret[2].type = C_CHOICES;
 159     ret[2].sval = TYPECONFIG;
 160     ret[2].ival = params->type;
 161
 162     ret[3].name = NULL;
 163     ret[3].type = C_END;
 164     ret[3].sval = NULL;
 165     ret[3].ival = 0;
 166
 167     return ret;
 168 }
 169
 170 static game_params *custom_params(config_item *cfg)
 171 {
 172     game_params *ret = snew(game_params);
 173
 174     ret->w = atoi(cfg[0].sval);
 175     ret->h = atoi(cfg[1].sval);
 176     ret->type = cfg[2].ival;
 177
 178     return ret;
 179 }
 180
 181 static char *validate_params(game_params *params, int full)
 182 {
 183     if (full && (params->w <= 3 || params->h <= 3))
 184         return "Width and height must both be greater than three";
 185
 186     /*
 187      * It might be possible to implement generalisations of Cross
 188      * and Octagon, but only if I can find a proof that they're all
 189      * soluble. For the moment, therefore, I'm going to disallow
 190      * them at any size other than the standard one.
 191      */
 192     if (full && (params->type == TYPE_CROSS || params->type == TYPE_OCTAGON)) {
 193         if (params->w != 7 || params->h != 7)
 194             return "This board type is only supported at 7x7";
 195     }
 196     return NULL;
 197 }
 198
 199 /* ----------------------------------------------------------------------
 200  * Beginning of code to generate random Peg Solitaire boards.
 201  *
 202  * This procedure is done with no aesthetic judgment, no effort at
 203  * symmetry, no difficulty grading and generally no finesse
 204  * whatsoever. We simply begin with an empty board containing a
 205  * single peg, and repeatedly make random reverse moves until it's
 206  * plausibly full. This typically yields a scrappy haphazard mess
 207  * with several holes, an uneven shape, and no redeeming features
 208  * except guaranteed solubility.
 209  *
 210  * My only concessions to sophistication are (a) to repeat the
 211  * generation process until I at least get a grid that touches
 212  * every edge of the specified board size, and (b) to try when
 213  * selecting moves to reuse existing space rather than expanding
 214  * into new space (so that non-rectangular board shape becomes a
 215  * factor during play).
 216  */
 217
 218 struct move {
 219     /*
 220      * x,y are the start point of the move during generation (hence
 221      * its endpoint during normal play).
 222      *
 223      * dx,dy are the direction of the move during generation.
 224      * Absolute value 1. Hence, for example, x=3,y=5,dx=1,dy=0
 225      * means that the move during generation starts at (3,5) and
 226      * ends at (5,5), and vice versa during normal play.
 227      */
 228     int x, y, dx, dy;
 229     /*
 230      * cost is 0, 1 or 2, depending on how many GRID_OBSTs we must
 231      * turn into GRID_HOLEs to play this move.
 232      */
 233     int cost;
 234 };
 235
 236 static int movecmp(void *av, void *bv)
 237 {
 238     struct move *a = (struct move *)av;
 239     struct move *b = (struct move *)bv;
 240
 241     if (a->y < b->y)
 242         return -1;
 243     else if (a->y > b->y)
 244         return +1;
 245
 246     if (a->x < b->x)
 247         return -1;
 248     else if (a->x > b->x)
 249         return +1;
 250
 251     if (a->dy < b->dy)
 252         return -1;
 253     else if (a->dy > b->dy)
 254         return +1;
 255
 256     if (a->dx < b->dx)
 257         return -1;
 258     else if (a->dx > b->dx)
 259         return +1;
 260
 261     return 0;
 262 }
 263
 264 static int movecmpcost(void *av, void *bv)
 265 {
 266     struct move *a = (struct move *)av;
 267     struct move *b = (struct move *)bv;
 268
 269     if (a->cost < b->cost)
 270         return -1;
 271     else if (a->cost > b->cost)
 272         return +1;
 273
 274     return movecmp(av, bv);
 275 }
 276
 277 struct movetrees {
 278     tree234 *bymove, *bycost;
 279 };
 280
 281 static void update_moves(unsigned char *grid, int w, int h, int x, int y,
 282                          struct movetrees *trees)
 283 {
 284     struct move move;
 285     int dir, pos;
 286
 287     /*
 288      * There are twelve moves that can include (x,y): three in each
 289      * of four directions. Check each one to see if it's possible.
 290      */
 291     for (dir = 0; dir < 4; dir++) {
 292         int dx, dy;
 293
 294         if (dir & 1)
 295             dx = 0, dy = dir - 2;
 296         else
 297             dy = 0, dx = dir - 1;
 298
 299         assert(abs(dx) + abs(dy) == 1);
 300
 301         for (pos = 0; pos < 3; pos++) {
 302             int v1, v2, v3;
 303
 304             move.dx = dx;
 305             move.dy = dy;
 306             move.x = x - pos*dx;
 307             move.y = y - pos*dy;
 308
 309             if (move.x < 0 || move.x >= w || move.y < 0 || move.y >= h)
 310                 continue;              /* completely invalid move */
 311             if (move.x+2*move.dx < 0 || move.x+2*move.dx >= w ||
 312                 move.y+2*move.dy < 0 || move.y+2*move.dy >= h)
 313                 continue;              /* completely invalid move */
 314
 315             v1 = grid[move.y * w + move.x];
 316             v2 = grid[(move.y+move.dy) * w + (move.x+move.dx)];
 317             v3 = grid[(move.y+2*move.dy)*w + (move.x+2*move.dx)];
 318             if (v1 == GRID_PEG && v2 != GRID_PEG && v3 != GRID_PEG) {
 319                 struct move *m;
 320
 321                 move.cost = (v2 == GRID_OBST) + (v3 == GRID_OBST);
 322
 323                 /*
 324                  * This move is possible. See if it's already in
 325                  * the tree.
 326                  */
 327                 m = find234(trees->bymove, &move, NULL);
 328                 if (m && m->cost != move.cost) {
 329                     /*
 330                      * It's in the tree but listed with the wrong
 331                      * cost. Remove the old version.
 332                      */
 333 #ifdef GENERATION_DIAGNOSTICS
 334                     printf("correcting %d%+d,%d%+d at cost %d\n",
 335                            m->x, m->dx, m->y, m->dy, m->cost);
 336 #endif
 337                     del234(trees->bymove, m);
 338                     del234(trees->bycost, m);
 339                     sfree(m);
 340                     m = NULL;
 341                 }
 342                 if (!m) {
 343                     struct move *m, *m2;
 344                     m = snew(struct move);
 345                     *m = move;
 346                     m2 = add234(trees->bymove, m);
 347                     m2 = add234(trees->bycost, m);
 348                     assert(m2 == m);
 349 #ifdef GENERATION_DIAGNOSTICS
 350                     printf("adding %d%+d,%d%+d at cost %d\n",
 351                            move.x, move.dx, move.y, move.dy, move.cost);
 352 #endif
 353                 } else {
 354 #ifdef GENERATION_DIAGNOSTICS
 355                     printf("not adding %d%+d,%d%+d at cost %d\n",
 356                            move.x, move.dx, move.y, move.dy, move.cost);
 357 #endif
 358                 }
 359             } else {
 360                 /*
 361                  * This move is impossible. If it is already in the
 362                  * tree, delete it.
 363                  *
 364                  * (We make use here of the fact that del234
 365                  * doesn't have to be passed a pointer to the
 366                  * _actual_ element it's deleting: it merely needs
 367                  * one that compares equal to it, and it will
 368                  * return the one it deletes.)
 369                  */
 370                 struct move *m = del234(trees->bymove, &move);
 371 #ifdef GENERATION_DIAGNOSTICS
 372                 printf("%sdeleting %d%+d,%d%+d\n", m ? "" : "not ",
 373                        move.x, move.dx, move.y, move.dy);
 374 #endif
 375                 if (m) {
 376                     del234(trees->bycost, m);
 377                     sfree(m);
 378                 }
 379             }
 380         }
 381     }
 382 }
 383
 384 static void pegs_genmoves(unsigned char *grid, int w, int h, random_state *rs)
 385 {
 386     struct movetrees atrees, *trees = &atrees;
 387     struct move *m;
 388     int x, y, i, nmoves;
 389
 390     trees->bymove = newtree234(movecmp);
 391     trees->bycost = newtree234(movecmpcost);
 392
 393     for (y = 0; y < h; y++)
 394         for (x = 0; x < w; x++)
 395             if (grid[y*w+x] == GRID_PEG)
 396                 update_moves(grid, w, h, x, y, trees);
 397
 398     nmoves = 0;
 399
 400     while (1) {
 401         int limit, maxcost, index;
 402         struct move mtmp, move, *m;
 403
 404         /*
 405          * See how many moves we can make at zero cost. Make one,
 406          * if possible. Failing that, make a one-cost move, and
 407          * then a two-cost one.
 408          *
 409          * After filling at least half the input grid, we no longer
 410          * accept cost-2 moves: if that's our only option, we give
 411          * up and finish.
 412          */
 413         mtmp.y = h+1;
 414         maxcost = (nmoves < w*h/2 ? 2 : 1);
 415         m = NULL;                      /* placate optimiser */
 416         for (mtmp.cost = 0; mtmp.cost <= maxcost; mtmp.cost++) {
 417             limit = -1;
 418             m = findrelpos234(trees->bycost, &mtmp, NULL, REL234_LT, &limit);
 419 #ifdef GENERATION_DIAGNOSTICS
 420             printf("%d moves available with cost %d\n", limit+1, mtmp.cost);
 421 #endif
 422             if (m)
 423                 break;
 424         }
 425         if (!m)
 426             break;
 427
 428         index = random_upto(rs, limit+1);
 429         move = *(struct move *)index234(trees->bycost, index);
 430
 431 #ifdef GENERATION_DIAGNOSTICS
 432         printf("selecting move %d%+d,%d%+d at cost %d\n",
 433                move.x, move.dx, move.y, move.dy, move.cost);
 434 #endif
 435
 436         grid[move.y * w + move.x] = GRID_HOLE;
 437         grid[(move.y+move.dy) * w + (move.x+move.dx)] = GRID_PEG;
 438         grid[(move.y+2*move.dy)*w + (move.x+2*move.dx)] = GRID_PEG;
 439
 440         for (i = 0; i <= 2; i++) {
 441             int tx = move.x + i*move.dx;
 442             int ty = move.y + i*move.dy;
 443             update_moves(grid, w, h, tx, ty, trees);
 444         }
 445
 446         nmoves++;
 447     }
 448
 449     while ((m = delpos234(trees->bymove, 0)) != NULL) {
 450         del234(trees->bycost, m);
 451         sfree(m);
 452     }
 453     freetree234(trees->bymove);
 454     freetree234(trees->bycost);
 455 }
 456
 457 static void pegs_generate(unsigned char *grid, int w, int h, random_state *rs)
 458 {
 459     while (1) {
 460         int x, y, extremes;
 461
 462         memset(grid, GRID_OBST, w*h);
 463         grid[(h/2) * w + (w/2)] = GRID_PEG;
 464 #ifdef GENERATION_DIAGNOSTICS
 465         printf("beginning move selection\n");
 466 #endif
 467         pegs_genmoves(grid, w, h, rs);
 468 #ifdef GENERATION_DIAGNOSTICS
 469         printf("finished move selection\n");
 470 #endif
 471
 472         extremes = 0;
 473         for (y = 0; y < h; y++) {
 474             if (grid[y*w+0] != GRID_OBST)
 475                 extremes |= 1;
 476             if (grid[y*w+w-1] != GRID_OBST)
 477                 extremes |= 2;
 478         }
 479         for (x = 0; x < w; x++) {
 480             if (grid[0*w+x] != GRID_OBST)
 481                 extremes |= 4;
 482             if (grid[(h-1)*w+x] != GRID_OBST)
 483                 extremes |= 8;
 484         }
 485
 486         if (extremes == 15)
 487             break;
 488 #ifdef GENERATION_DIAGNOSTICS
 489         printf("insufficient extent; trying again\n");
 490 #endif
 491     }
 492 #ifdef GENERATION_DIAGNOSTICS
 493     fflush(stdout);
 494 #endif
 495 }
 496
 497 /* ----------------------------------------------------------------------
 498  * End of board generation code. Now for the client code which uses
 499  * it as part of the puzzle.
 500  */
 501
 502 static char *new_game_desc(game_params *params, random_state *rs,
 503                            char **aux, int interactive)
 504 {
 505     int w = params->w, h = params->h;
 506     unsigned char *grid;
 507     char *ret;
 508     int i;
 509
 510     grid = snewn(w*h, unsigned char);
 511     if (params->type == TYPE_RANDOM) {
 512         pegs_generate(grid, w, h, rs);
 513     } else {
 514         int x, y, cx, cy, v;
 515
 516         for (y = 0; y < h; y++)
 517             for (x = 0; x < w; x++) {
 518                 v = GRID_OBST;         /* placate optimiser */
 519                 switch (params->type) {
 520                   case TYPE_CROSS:
 521                     cx = abs(x - w/2);
 522                     cy = abs(y - h/2);
 523                     if (cx == 0 && cy == 0)
 524                         v = GRID_HOLE;
 525                     else if (cx > 1 && cy > 1)
 526                         v = GRID_OBST;
 527                     else
 528                         v = GRID_PEG;
 529                     break;
 530                   case TYPE_OCTAGON:
 531                     cx = abs(x - w/2);
 532                     cy = abs(y - h/2);
 533                     if (cx + cy > 1 + max(w,h)/2)
 534                         v = GRID_OBST;
 535                     else
 536                         v = GRID_PEG;
 537                     break;
 538                 }
 539                 grid[y*w+x] = v;
 540             }
 541
 542         if (params->type == TYPE_OCTAGON) {
 543             /*
 544              * The octagonal (European) solitaire layout is
 545              * actually _insoluble_ with the starting hole at the
 546              * centre. Here's a proof:
 547              *
 548              * Colour the squares of the board diagonally in
 549              * stripes of three different colours, which I'll call
 550              * A, B and C. So the board looks like this:
 551              *
 552              *     A B C
 553              *   A B C A B
 554              * A B C A B C A
 555              * B C A B C A B
 556              * C A B C A B C
 557              *   B C A B C
 558              *     A B C
 559              *
 560              * Suppose we keep running track of the number of pegs
 561              * occuping each colour of square. This colouring has
 562              * the property that any valid move whatsoever changes
 563              * all three of those counts by one (two of them go
 564              * down and one goes up), which means that the _parity_
 565              * of every count flips on every move.
 566              *
 567              * If the centre square starts off unoccupied, then
 568              * there are twelve pegs on each colour and all three
 569              * counts start off even; therefore, after 35 moves all
 570              * three counts would have to be odd, which isn't
 571              * possible if there's only one peg left. []
 572              *
 573              * This proof works just as well if the starting hole
 574              * is _any_ of the thirteen positions labelled B. Also,
 575              * we can stripe the board in the opposite direction
 576              * and rule out any square labelled B in that colouring
 577              * as well. This leaves:
 578              *
 579              *     Y n Y
 580              *   n n Y n n
 581              * Y n n Y n n Y
 582              * n Y Y n Y Y n
 583              * Y n n Y n n Y
 584              *   n n Y n n
 585              *     Y n Y
 586              *
 587              * where the ns are squares we've proved insoluble, and
 588              * the Ys are the ones remaining.
 589              *
 590              * That doesn't prove all those starting positions to
 591              * be soluble, of course; they're merely the ones we
 592              * _haven't_ proved to be impossible. Nevertheless, it
 593              * turns out that they are all soluble, so when the
 594              * user requests an Octagon board the simplest thing is
 595              * to pick one of these at random.
 596              *
 597              * Rather than picking equiprobably from those twelve
 598              * positions, we'll pick equiprobably from the three
 599              * equivalence classes
 600              */
 601             switch (random_upto(rs, 3)) {
 602               case 0:
 603                 /* Remove a random corner piece. */
 604                 {
 605                     int dx, dy;
 606
 607                     dx = random_upto(rs, 2) * 2 - 1;   /* +1 or -1 */
 608                     dy = random_upto(rs, 2) * 2 - 1;   /* +1 or -1 */
 609                     if (random_upto(rs, 2))
 610                         dy *= 3;
 611                     else
 612                         dx *= 3;
 613                     grid[(3+dy)*w+(3+dx)] = GRID_HOLE;
 614                 }
 615                 break;
 616               case 1:
 617                 /* Remove a random piece two from the centre. */
 618                 {
 619                     int dx, dy;
 620                     dx = 2 * (random_upto(rs, 2) * 2 - 1);
 621                     if (random_upto(rs, 2))
 622                         dy = 0;
 623                     else
 624                         dy = dx, dx = 0;
 625                     grid[(3+dy)*w+(3+dx)] = GRID_HOLE;
 626                 }
 627                 break;
 628               default /* case 2 */:
 629                 /* Remove a random piece one from the centre. */
 630                 {
 631                     int dx, dy;
 632                     dx = random_upto(rs, 2) * 2 - 1;
 633                     if (random_upto(rs, 2))
 634                         dy = 0;
 635                     else
 636                         dy = dx, dx = 0;
 637                     grid[(3+dy)*w+(3+dx)] = GRID_HOLE;
 638                 }
 639                 break;
 640             }
 641         }
 642     }
 643
 644     /*
 645      * Encode a game description which is simply a long list of P
 646      * for peg, H for hole or O for obstacle.
 647      */
 648     ret = snewn(w*h+1, char);
 649     for (i = 0; i < w*h; i++)
 650         ret[i] = (grid[i] == GRID_PEG ? 'P' :
 651                   grid[i] == GRID_HOLE ? 'H' : 'O');
 652     ret[w*h] = '\0';
 653
 654     sfree(grid);
 655
 656     return ret;
 657 }
 658
 659 static char *validate_desc(game_params *params, char *desc)
 660 {
 661     int len = params->w * params->h;
 662
 663     if (len != strlen(desc))
 664         return "Game description is wrong length";
 665     if (len != strspn(desc, "PHO"))
 666         return "Invalid character in game description";
 667
 668     return NULL;
 669 }
 670
 671 static game_state *new_game(midend *me, game_params *params, char *desc)
 672 {
 673     int w = params->w, h = params->h;
 674     game_state *state = snew(game_state);
 675     int i;
 676
 677     state->w = w;
 678     state->h = h;
 679     state->completed = 0;
 680     state->grid = snewn(w*h, unsigned char);
 681     for (i = 0; i < w*h; i++)
 682         state->grid[i] = (desc[i] == 'P' ? GRID_PEG :
 683                           desc[i] == 'H' ? GRID_HOLE : GRID_OBST);
 684
 685     return state;
 686 }
 687
 688 static game_state *dup_game(game_state *state)
 689 {
 690     int w = state->w, h = state->h;
 691     game_state *ret = snew(game_state);
 692
 693     ret->w = state->w;
 694     ret->h = state->h;
 695     ret->completed = state->completed;
 696     ret->grid = snewn(w*h, unsigned char);
 697     memcpy(ret->grid, state->grid, w*h);
 698
 699     return ret;
 700 }
 701
 702 static void free_game(game_state *state)
 703 {
 704     sfree(state->grid);
 705     sfree(state);
 706 }
 707
 708 static char *solve_game(game_state *state, game_state *currstate,
 709                         char *aux, char **error)
 710 {
 711     return NULL;
 712 }
 713
 714 static int game_can_format_as_text_now(game_params *params)
 715 {
 716     return TRUE;
 717 }
 718
 719 static char *game_text_format(game_state *state)
 720 {
 721     int w = state->w, h = state->h;
 722     int x, y;
 723     char *ret;
 724
 725     ret = snewn((w+1)*h + 1, char);
 726
 727     for (y = 0; y < h; y++) {
 728         for (x = 0; x < w; x++)
 729             ret[y*(w+1)+x] = (state->grid[y*w+x] == GRID_HOLE ? '-' :
 730                               state->grid[y*w+x] == GRID_PEG ? '*' : ' ');
 731         ret[y*(w+1)+w] = '\n';
 732     }
 733     ret[h*(w+1)] = '\0';
 734
 735     return ret;
 736 }
 737
 738 struct game_ui {
 739     int dragging;                      /* boolean: is a drag in progress? */
 740     int sx, sy;                        /* grid coords of drag start cell */
 741     int dx, dy;                        /* pixel coords of current drag posn */
 742 };
 743
 744 static game_ui *new_ui(game_state *state)
 745 {
 746     game_ui *ui = snew(game_ui);
 747
 748     ui->sx = ui->sy = ui->dx = ui->dy = 0;
 749     ui->dragging = FALSE;
 750
 751     return ui;
 752 }
 753
 754 static void free_ui(game_ui *ui)
 755 {
 756     sfree(ui);
 757 }
 758
 759 static char *encode_ui(game_ui *ui)
 760 {
 761     return NULL;
 762 }
 763
 764 static void decode_ui(game_ui *ui, char *encoding)
 765 {
 766 }
 767
 768 static void game_changed_state(game_ui *ui, game_state *oldstate,
 769                                game_state *newstate)
 770 {
 771     /*
 772      * Cancel a drag, in case the source square has become
 773      * unoccupied.
 774      */
 775     ui->dragging = FALSE;
 776 }
 777
 778 #define PREFERRED_TILE_SIZE 33
 779 #define TILESIZE (ds->tilesize)
 780 #define BORDER (TILESIZE / 2)
 781
 782 #define HIGHLIGHT_WIDTH (TILESIZE / 16)
 783
 784 #define COORD(x)     ( BORDER + (x) * TILESIZE )
 785 #define FROMCOORD(x) ( ((x) + TILESIZE - BORDER) / TILESIZE - 1 )
 786
 787 struct game_drawstate {
 788     int tilesize;
 789     blitter *drag_background;
 790     int dragging, dragx, dragy;
 791     int w, h;
 792     unsigned char *grid;
 793     int started;
 794     int bgcolour;
 795 };
 796
 797 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
 798                             int x, int y, int button)
 799 {
 800     int w = state->w, h = state->h;
 801
 802     if (button == LEFT_BUTTON) {
 803         int tx, ty;
 804
 805         /*
 806          * Left button down: we attempt to start a drag.
 807          */
 808
 809         /*
 810          * There certainly shouldn't be a current drag in progress,
 811          * unless the midend failed to send us button events in
 812          * order; it has a responsibility to always get that right,
 813          * so we can legitimately punish it by failing an
 814          * assertion.
 815          */
 816         assert(!ui->dragging);
 817
 818         tx = FROMCOORD(x);
 819         ty = FROMCOORD(y);
 820         if (tx >= 0 && tx < w && ty >= 0 && ty < h &&
 821             state->grid[ty*w+tx] == GRID_PEG) {
 822             ui->dragging = TRUE;
 823             ui->sx = tx;
 824             ui->sy = ty;
 825             ui->dx = x;
 826             ui->dy = y;
 827             return "";                 /* ui modified */
 828         }
 829     } else if (button == LEFT_DRAG && ui->dragging) {
 830         /*
 831          * Mouse moved; just move the peg being dragged.
 832          */
 833         ui->dx = x;
 834         ui->dy = y;
 835         return "";                     /* ui modified */
 836     } else if (button == LEFT_RELEASE && ui->dragging) {
 837         char buf[80];
 838         int tx, ty, dx, dy;
 839
 840         /*
 841          * Button released. Identify the target square of the drag,
 842          * see if it represents a valid move, and if so make it.
 843          */
 844         ui->dragging = FALSE;          /* cancel the drag no matter what */
 845         tx = FROMCOORD(x);
 846         ty = FROMCOORD(y);
 847         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 848             return "";                 /* target out of range */
 849         dx = tx - ui->sx;
 850         dy = ty - ui->sy;
 851         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 852             return "";                 /* move length was wrong */
 853         dx /= 2;
 854         dy /= 2;
 855
 856         if (state->grid[ty*w+tx] != GRID_HOLE ||
 857             state->grid[(ty-dy)*w+(tx-dx)] != GRID_PEG ||
 858             state->grid[ui->sy*w+ui->sx] != GRID_PEG)
 859             return "";                 /* grid contents were invalid */
 860
 861         /*
 862          * We have a valid move. Encode it simply as source and
 863          * destination coordinate pairs.
 864          */
 865         sprintf(buf, "%d,%d-%d,%d", ui->sx, ui->sy, tx, ty);
 866         return dupstr(buf);
 867     }
 868     return NULL;
 869 }
 870
 871 static game_state *execute_move(game_state *state, char *move)
 872 {
 873     int w = state->w, h = state->h;
 874     int sx, sy, tx, ty;
 875     game_state *ret;
 876
 877     if (sscanf(move, "%d,%d-%d,%d", &sx, &sy, &tx, &ty) == 4) {
 878         int mx, my, dx, dy;
 879
 880         if (sx < 0 || sx >= w || sy < 0 || sy >= h)
 881             return NULL;               /* source out of range */
 882         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 883             return NULL;               /* target out of range */
 884
 885         dx = tx - sx;
 886         dy = ty - sy;
 887         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 888             return NULL;               /* move length was wrong */
 889         mx = sx + dx/2;
 890         my = sy + dy/2;
 891
 892         if (state->grid[sy*w+sx] != GRID_PEG ||
 893             state->grid[my*w+mx] != GRID_PEG ||
 894             state->grid[ty*w+tx] != GRID_HOLE)
 895             return NULL;               /* grid contents were invalid */
 896
 897         ret = dup_game(state);
 898         ret->grid[sy*w+sx] = GRID_HOLE;
 899         ret->grid[my*w+mx] = GRID_HOLE;
 900         ret->grid[ty*w+tx] = GRID_PEG;
 901
 902         /*
 903          * Opinion varies on whether getting to a single peg counts as
 904          * completing the game, or whether that peg has to be at a
 905          * specific location (central in the classic cross game, for
 906          * instance). For now we take the former, rather lax position.
 907          */
 908         if (!ret->completed) {
 909             int count = 0, i;
 910             for (i = 0; i < w*h; i++)
 911                 if (ret->grid[i] == GRID_PEG)
 912                     count++;
 913             if (count == 1)
 914                 ret->completed = 1;
 915         }
 916
 917         return ret;
 918     }
 919     return NULL;
 920 }
 921
 922 /* ----------------------------------------------------------------------
 923  * Drawing routines.
 924  */
 925
 926 static void game_compute_size(game_params *params, int tilesize,
 927                               int *x, int *y)
 928 {
 929     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
 930     struct { int tilesize; } ads, *ds = &ads;
 931     ads.tilesize = tilesize;
 932
 933     *x = TILESIZE * params->w + 2 * BORDER;
 934     *y = TILESIZE * params->h + 2 * BORDER;
 935 }
 936
 937 static void game_set_size(drawing *dr, game_drawstate *ds,
 938                           game_params *params, int tilesize)
 939 {
 940     ds->tilesize = tilesize;
 941
 942     assert(TILESIZE > 0);
 943
 944     assert(!ds->drag_background);      /* set_size is never called twice */
 945     ds->drag_background = blitter_new(dr, TILESIZE, TILESIZE);
 946 }
 947
 948 static float *game_colours(frontend *fe, int *ncolours)
 949 {
 950     float *ret = snewn(3 * NCOLOURS, float);
 951
 952     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
 953
 954     ret[COL_PEG * 3 + 0] = 0.0F;
 955     ret[COL_PEG * 3 + 1] = 0.0F;
 956     ret[COL_PEG * 3 + 2] = 1.0F;
 957
 958     *ncolours = NCOLOURS;
 959     return ret;
 960 }
 961
 962 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
 963 {
 964     int w = state->w, h = state->h;
 965     struct game_drawstate *ds = snew(struct game_drawstate);
 966
 967     ds->tilesize = 0;                  /* not decided yet */
 968
 969     /* We can't allocate the blitter rectangle for the drag background
 970      * until we know what size to make it. */
 971     ds->drag_background = NULL;
 972     ds->dragging = FALSE;
 973
 974     ds->w = w;
 975     ds->h = h;
 976     ds->grid = snewn(w*h, unsigned char);
 977     memset(ds->grid, 255, w*h);
 978
 979     ds->started = FALSE;
 980     ds->bgcolour = -1;
 981
 982     return ds;
 983 }
 984
 985 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
 986 {
 987     if (ds->drag_background)
 988         blitter_free(dr, ds->drag_background);
 989     sfree(ds->grid);
 990     sfree(ds);
 991 }
 992
 993 static void draw_tile(drawing *dr, game_drawstate *ds,
 994                       int x, int y, int v, int bgcolour)
 995 {
 996     if (bgcolour >= 0) {
 997         draw_rect(dr, x, y, TILESIZE, TILESIZE, bgcolour);
 998     }
 999
1000     if (v == GRID_HOLE) {
1001         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/4,
1002                     COL_LOWLIGHT, COL_LOWLIGHT);
1003     } else if (v == GRID_PEG) {
1004         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/3,
1005                     COL_PEG, COL_PEG);
1006     }
1007
1008     draw_update(dr, x, y, TILESIZE, TILESIZE);
1009 }
1010
1011 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1012                         game_state *state, int dir, game_ui *ui,
1013                         float animtime, float flashtime)
1014 {
1015     int w = state->w, h = state->h;
1016     int x, y;
1017     int bgcolour;
1018
1019     if (flashtime > 0) {
1020         int frame = (int)(flashtime / FLASH_FRAME);
1021         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1022     } else
1023         bgcolour = COL_BACKGROUND;
1024
1025     /*
1026      * Erase the sprite currently being dragged, if any.
1027      */
1028     if (ds->dragging) {
1029         assert(ds->drag_background);
1030         blitter_load(dr, ds->drag_background, ds->dragx, ds->dragy);
1031         draw_update(dr, ds->dragx, ds->dragy, TILESIZE, TILESIZE);
1032         ds->dragging = FALSE;
1033     }
1034
1035     if (!ds->started) {
1036         draw_rect(dr, 0, 0,
1037                   TILESIZE * state->w + 2 * BORDER,
1038                   TILESIZE * state->h + 2 * BORDER, COL_BACKGROUND);
1039
1040         /*
1041          * Draw relief marks around all the squares that aren't
1042          * GRID_OBST.
1043          */
1044         for (y = 0; y < h; y++)
1045             for (x = 0; x < w; x++)
1046                 if (state->grid[y*w+x] != GRID_OBST) {
1047                     /*
1048                      * First pass: draw the full relief square.
1049                      */
1050                     int coords[6];
1051                     coords[0] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1052                     coords[1] = COORD(y) - HIGHLIGHT_WIDTH;
1053                     coords[2] = COORD(x) - HIGHLIGHT_WIDTH;
1054                     coords[3] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1055                     coords[4] = COORD(x) - HIGHLIGHT_WIDTH;
1056                     coords[5] = COORD(y) - HIGHLIGHT_WIDTH;
1057                     draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1058                     coords[4] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1059                     coords[5] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1060                     draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1061                 }
1062         for (y = 0; y < h; y++)
1063             for (x = 0; x < w; x++)
1064                 if (state->grid[y*w+x] != GRID_OBST) {
1065                     /*
1066                      * Second pass: draw everything but the two
1067                      * diagonal corners.
1068                      */
1069                     draw_rect(dr, COORD(x) - HIGHLIGHT_WIDTH,
1070                               COORD(y) - HIGHLIGHT_WIDTH,
1071                               TILESIZE + HIGHLIGHT_WIDTH,
1072                               TILESIZE + HIGHLIGHT_WIDTH, COL_HIGHLIGHT);
1073                     draw_rect(dr, COORD(x),
1074                               COORD(y),
1075                               TILESIZE + HIGHLIGHT_WIDTH,
1076                               TILESIZE + HIGHLIGHT_WIDTH, COL_LOWLIGHT);
1077                 }
1078         for (y = 0; y < h; y++)
1079             for (x = 0; x < w; x++)
1080                 if (state->grid[y*w+x] != GRID_OBST) {
1081                     /*
1082                      * Third pass: draw a trapezium on each edge.
1083                      */
1084                     int coords[8];
1085                     int dx, dy, s, sn, c;
1086
1087                     for (dx = 0; dx < 2; dx++) {
1088                         dy = 1 - dx;
1089                         for (s = 0; s < 2; s++) {
1090                             sn = 2*s - 1;
1091                             c = s ? COL_LOWLIGHT : COL_HIGHLIGHT;
1092
1093                             coords[0] = COORD(x) + (s*dx)*(TILESIZE-1);
1094                             coords[1] = COORD(y) + (s*dy)*(TILESIZE-1);
1095                             coords[2] = COORD(x) + (s*dx+dy)*(TILESIZE-1);
1096                             coords[3] = COORD(y) + (s*dy+dx)*(TILESIZE-1);
1097                             coords[4] = coords[2] - HIGHLIGHT_WIDTH * (dy-sn*dx);
1098                             coords[5] = coords[3] - HIGHLIGHT_WIDTH * (dx-sn*dy);
1099                             coords[6] = coords[0] + HIGHLIGHT_WIDTH * (dy+sn*dx);
1100                             coords[7] = coords[1] + HIGHLIGHT_WIDTH * (dx+sn*dy);
1101                             draw_polygon(dr, coords, 4, c, c);
1102                         }
1103                     }
1104                 }
1105         for (y = 0; y < h; y++)
1106             for (x = 0; x < w; x++)
1107                 if (state->grid[y*w+x] != GRID_OBST) {
1108                     /*
1109                      * Second pass: draw everything but the two
1110                      * diagonal corners.
1111                      */
1112                     draw_rect(dr, COORD(x),
1113                               COORD(y),
1114                               TILESIZE,
1115                               TILESIZE, COL_BACKGROUND);
1116                 }
1117
1118         ds->started = TRUE;
1119
1120         draw_update(dr, 0, 0,
1121                     TILESIZE * state->w + 2 * BORDER,
1122                     TILESIZE * state->h + 2 * BORDER);
1123     }
1124
1125     /*
1126      * Loop over the grid redrawing anything that looks as if it
1127      * needs it.
1128      */
1129     for (y = 0; y < h; y++)
1130         for (x = 0; x < w; x++) {
1131             int v;
1132
1133             v = state->grid[y*w+x];
1134             /*
1135              * Blank the source of a drag so it looks as if the
1136              * user picked the peg up physically.
1137              */
1138             if (ui->dragging && ui->sx == x && ui->sy == y && v == GRID_PEG)
1139                 v = GRID_HOLE;
1140             if (v != GRID_OBST &&
1141                 (bgcolour != ds->bgcolour || /* always redraw when flashing */
1142                  v != ds->grid[y*w+x])) {
1143                 draw_tile(dr, ds, COORD(x), COORD(y), v, bgcolour);
1144             }
1145         }
1146
1147     /*
1148      * Draw the dragging sprite if any.
1149      */
1150     if (ui->dragging) {
1151         ds->dragging = TRUE;
1152         ds->dragx = ui->dx - TILESIZE/2;
1153         ds->dragy = ui->dy - TILESIZE/2;
1154         blitter_save(dr, ds->drag_background, ds->dragx, ds->dragy);
1155         draw_tile(dr, ds, ds->dragx, ds->dragy, GRID_PEG, -1);
1156     }
1157
1158     ds->bgcolour = bgcolour;
1159 }
1160
1161 static float game_anim_length(game_state *oldstate, game_state *newstate,
1162                               int dir, game_ui *ui)
1163 {
1164     return 0.0F;
1165 }
1166
1167 static float game_flash_length(game_state *oldstate, game_state *newstate,
1168                                int dir, game_ui *ui)
1169 {
1170     if (!oldstate->completed && newstate->completed)
1171         return 2 * FLASH_FRAME;
1172     else
1173         return 0.0F;
1174 }
1175
1176 static int game_timing_state(game_state *state, game_ui *ui)
1177 {
1178     return TRUE;
1179 }
1180
1181 static void game_print_size(game_params *params, float *x, float *y)
1182 {
1183 }
1184
1185 static void game_print(drawing *dr, game_state *state, int tilesize)
1186 {
1187 }
1188
1189 #ifdef COMBINED
1190 #define thegame pegs
1191 #endif
1192
1193 const struct game thegame = {
1194     "Pegs", "games.pegs", "pegs",
1195     default_params,
1196     game_fetch_preset,
1197     decode_params,
1198     encode_params,
1199     free_params,
1200     dup_params,
1201     TRUE, game_configure, custom_params,
1202     validate_params,
1203     new_game_desc,
1204     validate_desc,
1205     new_game,
1206     dup_game,
1207     free_game,
1208     FALSE, solve_game,
1209     TRUE, game_can_format_as_text_now, game_text_format,
1210     new_ui,
1211     free_ui,
1212     encode_ui,
1213     decode_ui,
1214     game_changed_state,
1215     interpret_move,
1216     execute_move,
1217     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1218     game_colours,
1219     game_new_drawstate,
1220     game_free_drawstate,
1221     game_redraw,
1222     game_anim_length,
1223     game_flash_length,
1224     FALSE, FALSE, game_print_size, game_print,
1225     FALSE,                             /* wants_statusbar */
1226     FALSE, game_timing_state,
1227     0,                                 /* flags */
1228 };