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_data *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 char *game_text_format(game_state *state)
 715 {
 716     int w = state->w, h = state->h;
 717     int x, y;
 718     char *ret;
 719
 720     ret = snewn((w+1)*h + 1, char);
 721
 722     for (y = 0; y < h; y++) {
 723         for (x = 0; x < w; x++)
 724             ret[y*(w+1)+x] = (state->grid[y*w+x] == GRID_HOLE ? '-' :
 725                               state->grid[y*w+x] == GRID_PEG ? '*' : ' ');
 726         ret[y*(w+1)+w] = '\n';
 727     }
 728     ret[h*(w+1)] = '\0';
 729
 730     return ret;
 731 }
 732
 733 struct game_ui {
 734     int dragging;                      /* boolean: is a drag in progress? */
 735     int sx, sy;                        /* grid coords of drag start cell */
 736     int dx, dy;                        /* pixel coords of current drag posn */
 737 };
 738
 739 static game_ui *new_ui(game_state *state)
 740 {
 741     game_ui *ui = snew(game_ui);
 742
 743     ui->sx = ui->sy = ui->dx = ui->dy = 0;
 744     ui->dragging = FALSE;
 745
 746     return ui;
 747 }
 748
 749 static void free_ui(game_ui *ui)
 750 {
 751     sfree(ui);
 752 }
 753
 754 static char *encode_ui(game_ui *ui)
 755 {
 756     return NULL;
 757 }
 758
 759 static void decode_ui(game_ui *ui, char *encoding)
 760 {
 761 }
 762
 763 static void game_changed_state(game_ui *ui, game_state *oldstate,
 764                                game_state *newstate)
 765 {
 766     /*
 767      * Cancel a drag, in case the source square has become
 768      * unoccupied.
 769      */
 770     ui->dragging = FALSE;
 771 }
 772
 773 #define PREFERRED_TILE_SIZE 33
 774 #define TILESIZE (ds->tilesize)
 775 #define BORDER (TILESIZE / 2)
 776
 777 #define HIGHLIGHT_WIDTH (TILESIZE / 16)
 778
 779 #define COORD(x)     ( BORDER + (x) * TILESIZE )
 780 #define FROMCOORD(x) ( ((x) + TILESIZE - BORDER) / TILESIZE - 1 )
 781
 782 struct game_drawstate {
 783     int tilesize;
 784     blitter *drag_background;
 785     int dragging, dragx, dragy;
 786     int w, h;
 787     unsigned char *grid;
 788     int started;
 789     int bgcolour;
 790 };
 791
 792 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
 793                             int x, int y, int button)
 794 {
 795     int w = state->w, h = state->h;
 796
 797     if (button == LEFT_BUTTON) {
 798         int tx, ty;
 799
 800         /*
 801          * Left button down: we attempt to start a drag.
 802          */
 803
 804         /*
 805          * There certainly shouldn't be a current drag in progress,
 806          * unless the midend failed to send us button events in
 807          * order; it has a responsibility to always get that right,
 808          * so we can legitimately punish it by failing an
 809          * assertion.
 810          */
 811         assert(!ui->dragging);
 812
 813         tx = FROMCOORD(x);
 814         ty = FROMCOORD(y);
 815         if (tx >= 0 && tx < w && ty >= 0 && ty < h &&
 816             state->grid[ty*w+tx] == GRID_PEG) {
 817             ui->dragging = TRUE;
 818             ui->sx = tx;
 819             ui->sy = ty;
 820             ui->dx = x;
 821             ui->dy = y;
 822             return "";                 /* ui modified */
 823         }
 824     } else if (button == LEFT_DRAG && ui->dragging) {
 825         /*
 826          * Mouse moved; just move the peg being dragged.
 827          */
 828         ui->dx = x;
 829         ui->dy = y;
 830         return "";                     /* ui modified */
 831     } else if (button == LEFT_RELEASE && ui->dragging) {
 832         char buf[80];
 833         int tx, ty, dx, dy;
 834
 835         /*
 836          * Button released. Identify the target square of the drag,
 837          * see if it represents a valid move, and if so make it.
 838          */
 839         ui->dragging = FALSE;          /* cancel the drag no matter what */
 840         tx = FROMCOORD(x);
 841         ty = FROMCOORD(y);
 842         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 843             return "";                 /* target out of range */
 844         dx = tx - ui->sx;
 845         dy = ty - ui->sy;
 846         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 847             return "";                 /* move length was wrong */
 848         dx /= 2;
 849         dy /= 2;
 850
 851         if (state->grid[ty*w+tx] != GRID_HOLE ||
 852             state->grid[(ty-dy)*w+(tx-dx)] != GRID_PEG ||
 853             state->grid[ui->sy*w+ui->sx] != GRID_PEG)
 854             return "";                 /* grid contents were invalid */
 855
 856         /*
 857          * We have a valid move. Encode it simply as source and
 858          * destination coordinate pairs.
 859          */
 860         sprintf(buf, "%d,%d-%d,%d", ui->sx, ui->sy, tx, ty);
 861         return dupstr(buf);
 862     }
 863     return NULL;
 864 }
 865
 866 static game_state *execute_move(game_state *state, char *move)
 867 {
 868     int w = state->w, h = state->h;
 869     int sx, sy, tx, ty;
 870     game_state *ret;
 871
 872     if (sscanf(move, "%d,%d-%d,%d", &sx, &sy, &tx, &ty)) {
 873         int mx, my, dx, dy;
 874
 875         if (sx < 0 || sx >= w || sy < 0 || sy >= h)
 876             return NULL;               /* source out of range */
 877         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 878             return NULL;               /* target out of range */
 879
 880         dx = tx - sx;
 881         dy = ty - sy;
 882         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 883             return NULL;               /* move length was wrong */
 884         mx = sx + dx/2;
 885         my = sy + dy/2;
 886
 887         if (state->grid[sy*w+sx] != GRID_PEG ||
 888             state->grid[my*w+mx] != GRID_PEG ||
 889             state->grid[ty*w+tx] != GRID_HOLE)
 890             return NULL;               /* grid contents were invalid */
 891
 892         ret = dup_game(state);
 893         ret->grid[sy*w+sx] = GRID_HOLE;
 894         ret->grid[my*w+mx] = GRID_HOLE;
 895         ret->grid[ty*w+tx] = GRID_PEG;
 896
 897         /*
 898          * Opinion varies on whether getting to a single peg counts as
 899          * completing the game, or whether that peg has to be at a
 900          * specific location (central in the classic cross game, for
 901          * instance). For now we take the former, rather lax position.
 902          */
 903         if (!ret->completed) {
 904             int count = 0, i;
 905             for (i = 0; i < w*h; i++)
 906                 if (ret->grid[i] == GRID_PEG)
 907                     count++;
 908             if (count == 1)
 909                 ret->completed = 1;
 910         }
 911
 912         return ret;
 913     }
 914     return NULL;
 915 }
 916
 917 /* ----------------------------------------------------------------------
 918  * Drawing routines.
 919  */
 920
 921 static void game_compute_size(game_params *params, int tilesize,
 922                               int *x, int *y)
 923 {
 924     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
 925     struct { int tilesize; } ads, *ds = &ads;
 926     ads.tilesize = tilesize;
 927
 928     *x = TILESIZE * params->w + 2 * BORDER;
 929     *y = TILESIZE * params->h + 2 * BORDER;
 930 }
 931
 932 static void game_set_size(game_drawstate *ds, game_params *params,
 933                           int tilesize)
 934 {
 935     ds->tilesize = tilesize;
 936
 937     assert(TILESIZE > 0);
 938
 939     if (ds->drag_background)
 940         blitter_free(ds->drag_background);
 941     ds->drag_background = blitter_new(TILESIZE, TILESIZE);
 942 }
 943
 944 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
 945 {
 946     float *ret = snewn(3 * NCOLOURS, float);
 947
 948     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
 949
 950     ret[COL_PEG * 3 + 0] = 0.0F;
 951     ret[COL_PEG * 3 + 1] = 0.0F;
 952     ret[COL_PEG * 3 + 2] = 1.0F;
 953
 954     *ncolours = NCOLOURS;
 955     return ret;
 956 }
 957
 958 static game_drawstate *game_new_drawstate(game_state *state)
 959 {
 960     int w = state->w, h = state->h;
 961     struct game_drawstate *ds = snew(struct game_drawstate);
 962
 963     ds->tilesize = 0;                  /* not decided yet */
 964
 965     /* We can't allocate the blitter rectangle for the drag background
 966      * until we know what size to make it. */
 967     ds->drag_background = NULL;
 968     ds->dragging = FALSE;
 969
 970     ds->w = w;
 971     ds->h = h;
 972     ds->grid = snewn(w*h, unsigned char);
 973     memset(ds->grid, 255, w*h);
 974
 975     ds->started = FALSE;
 976     ds->bgcolour = -1;
 977
 978     return ds;
 979 }
 980
 981 static void game_free_drawstate(game_drawstate *ds)
 982 {
 983     if (ds->drag_background)
 984         blitter_free(ds->drag_background);
 985     sfree(ds->grid);
 986     sfree(ds);
 987 }
 988
 989 static void draw_tile(frontend *fe, game_drawstate *ds,
 990                       int x, int y, int v, int bgcolour)
 991 {
 992     if (bgcolour >= 0) {
 993         draw_rect(fe, x, y, TILESIZE, TILESIZE, bgcolour);
 994     }
 995
 996     if (v == GRID_HOLE) {
 997         draw_circle(fe, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/4,
 998                     COL_LOWLIGHT, COL_LOWLIGHT);
 999     } else if (v == GRID_PEG) {
1000         draw_circle(fe, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/3,
1001                     COL_PEG, COL_PEG);
1002     }
1003
1004     draw_update(fe, x, y, TILESIZE, TILESIZE);
1005 }
1006
1007 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
1008                         game_state *state, int dir, game_ui *ui,
1009                         float animtime, float flashtime)
1010 {
1011     int w = state->w, h = state->h;
1012     int x, y;
1013     int bgcolour;
1014
1015     if (flashtime > 0) {
1016         int frame = (int)(flashtime / FLASH_FRAME);
1017         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1018     } else
1019         bgcolour = COL_BACKGROUND;
1020
1021     /*
1022      * Erase the sprite currently being dragged, if any.
1023      */
1024     if (ds->dragging) {
1025         assert(ds->drag_background);
1026         blitter_load(fe, ds->drag_background, ds->dragx, ds->dragy);
1027         draw_update(fe, ds->dragx, ds->dragy, TILESIZE, TILESIZE);
1028         ds->dragging = FALSE;
1029     }
1030
1031     if (!ds->started) {
1032         draw_rect(fe, 0, 0,
1033                   TILESIZE * state->w + 2 * BORDER,
1034                   TILESIZE * state->h + 2 * BORDER, COL_BACKGROUND);
1035
1036         /*
1037          * Draw relief marks around all the squares that aren't
1038          * GRID_OBST.
1039          */
1040         for (y = 0; y < h; y++)
1041             for (x = 0; x < w; x++)
1042                 if (state->grid[y*w+x] != GRID_OBST) {
1043                     /*
1044                      * First pass: draw the full relief square.
1045                      */
1046                     int coords[6];
1047                     coords[0] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1048                     coords[1] = COORD(y) - HIGHLIGHT_WIDTH;
1049                     coords[2] = COORD(x) - HIGHLIGHT_WIDTH;
1050                     coords[3] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1051                     coords[4] = COORD(x) - HIGHLIGHT_WIDTH;
1052                     coords[5] = COORD(y) - HIGHLIGHT_WIDTH;
1053                     draw_polygon(fe, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1054                     coords[4] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1055                     coords[5] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1056                     draw_polygon(fe, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1057                 }
1058         for (y = 0; y < h; y++)
1059             for (x = 0; x < w; x++)
1060                 if (state->grid[y*w+x] != GRID_OBST) {
1061                     /*
1062                      * Second pass: draw everything but the two
1063                      * diagonal corners.
1064                      */
1065                     draw_rect(fe, COORD(x) - HIGHLIGHT_WIDTH,
1066                               COORD(y) - HIGHLIGHT_WIDTH,
1067                               TILESIZE + HIGHLIGHT_WIDTH,
1068                               TILESIZE + HIGHLIGHT_WIDTH, COL_HIGHLIGHT);
1069                     draw_rect(fe, COORD(x),
1070                               COORD(y),
1071                               TILESIZE + HIGHLIGHT_WIDTH,
1072                               TILESIZE + HIGHLIGHT_WIDTH, COL_LOWLIGHT);
1073                 }
1074         for (y = 0; y < h; y++)
1075             for (x = 0; x < w; x++)
1076                 if (state->grid[y*w+x] != GRID_OBST) {
1077                     /*
1078                      * Third pass: draw a trapezium on each edge.
1079                      */
1080                     int coords[8];
1081                     int dx, dy, s, sn, c;
1082
1083                     for (dx = 0; dx < 2; dx++) {
1084                         dy = 1 - dx;
1085                         for (s = 0; s < 2; s++) {
1086                             sn = 2*s - 1;
1087                             c = s ? COL_LOWLIGHT : COL_HIGHLIGHT;
1088
1089                             coords[0] = COORD(x) + (s*dx)*(TILESIZE-1);
1090                             coords[1] = COORD(y) + (s*dy)*(TILESIZE-1);
1091                             coords[2] = COORD(x) + (s*dx+dy)*(TILESIZE-1);
1092                             coords[3] = COORD(y) + (s*dy+dx)*(TILESIZE-1);
1093                             coords[4] = coords[2] - HIGHLIGHT_WIDTH * (dy-sn*dx);
1094                             coords[5] = coords[3] - HIGHLIGHT_WIDTH * (dx-sn*dy);
1095                             coords[6] = coords[0] + HIGHLIGHT_WIDTH * (dy+sn*dx);
1096                             coords[7] = coords[1] + HIGHLIGHT_WIDTH * (dx+sn*dy);
1097                             draw_polygon(fe, coords, 4, c, c);
1098                         }
1099                     }
1100                 }
1101         for (y = 0; y < h; y++)
1102             for (x = 0; x < w; x++)
1103                 if (state->grid[y*w+x] != GRID_OBST) {
1104                     /*
1105                      * Second pass: draw everything but the two
1106                      * diagonal corners.
1107                      */
1108                     draw_rect(fe, COORD(x),
1109                               COORD(y),
1110                               TILESIZE,
1111                               TILESIZE, COL_BACKGROUND);
1112                 }
1113
1114         ds->started = TRUE;
1115
1116         draw_update(fe, 0, 0,
1117                     TILESIZE * state->w + 2 * BORDER,
1118                     TILESIZE * state->h + 2 * BORDER);
1119     }
1120
1121     /*
1122      * Loop over the grid redrawing anything that looks as if it
1123      * needs it.
1124      */
1125     for (y = 0; y < h; y++)
1126         for (x = 0; x < w; x++) {
1127             int v;
1128
1129             v = state->grid[y*w+x];
1130             /*
1131              * Blank the source of a drag so it looks as if the
1132              * user picked the peg up physically.
1133              */
1134             if (ui->dragging && ui->sx == x && ui->sy == y && v == GRID_PEG)
1135                 v = GRID_HOLE;
1136             if (v != GRID_OBST &&
1137                 (bgcolour != ds->bgcolour || /* always redraw when flashing */
1138                  v != ds->grid[y*w+x])) {
1139                 draw_tile(fe, ds, COORD(x), COORD(y), v, bgcolour);
1140             }
1141         }
1142
1143     /*
1144      * Draw the dragging sprite if any.
1145      */
1146     if (ui->dragging) {
1147         ds->dragging = TRUE;
1148         ds->dragx = ui->dx - TILESIZE/2;
1149         ds->dragy = ui->dy - TILESIZE/2;
1150         blitter_save(fe, ds->drag_background, ds->dragx, ds->dragy);
1151         draw_tile(fe, ds, ds->dragx, ds->dragy, GRID_PEG, -1);
1152     }
1153
1154     ds->bgcolour = bgcolour;
1155 }
1156
1157 static float game_anim_length(game_state *oldstate, game_state *newstate,
1158                               int dir, game_ui *ui)
1159 {
1160     return 0.0F;
1161 }
1162
1163 static float game_flash_length(game_state *oldstate, game_state *newstate,
1164                                int dir, game_ui *ui)
1165 {
1166     if (!oldstate->completed && newstate->completed)
1167         return 2 * FLASH_FRAME;
1168     else
1169         return 0.0F;
1170 }
1171
1172 static int game_wants_statusbar(void)
1173 {
1174     return FALSE;
1175 }
1176
1177 static int game_timing_state(game_state *state)
1178 {
1179     return TRUE;
1180 }
1181
1182 #ifdef COMBINED
1183 #define thegame pegs
1184 #endif
1185
1186 const struct game thegame = {
1187     "Pegs", "games.pegs",
1188     default_params,
1189     game_fetch_preset,
1190     decode_params,
1191     encode_params,
1192     free_params,
1193     dup_params,
1194     TRUE, game_configure, custom_params,
1195     validate_params,
1196     new_game_desc,
1197     validate_desc,
1198     new_game,
1199     dup_game,
1200     free_game,
1201     FALSE, solve_game,
1202     TRUE, game_text_format,
1203     new_ui,
1204     free_ui,
1205     encode_ui,
1206     decode_ui,
1207     game_changed_state,
1208     interpret_move,
1209     execute_move,
1210     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1211     game_colours,
1212     game_new_drawstate,
1213     game_free_drawstate,
1214     game_redraw,
1215     game_anim_length,
1216     game_flash_length,
1217     game_wants_statusbar,
1218     FALSE, game_timing_state,
1219     0,                                 /* mouse_priorities */
1220 };