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 #define GRID_CURSOR 10
  20 #define GRID_JUMPING 20
  21
  22 enum {
  23     COL_BACKGROUND,
  24     COL_HIGHLIGHT,
  25     COL_LOWLIGHT,
  26     COL_PEG,
  27     COL_CURSOR,
  28     NCOLOURS
  29 };
  30
  31 /*
  32  * Grid shapes. I do some macro ickery here to ensure that my enum
  33  * and the various forms of my name list always match up.
  34  */
  35 #define TYPELIST(A) \
  36     A(CROSS,Cross,cross) \
  37     A(OCTAGON,Octagon,octagon) \
  38     A(RANDOM,Random,random)
  39 #define ENUM(upper,title,lower) TYPE_ ## upper,
  40 #define TITLE(upper,title,lower) #title,
  41 #define LOWER(upper,title,lower) #lower,
  42 #define CONFIG(upper,title,lower) ":" #title
  43
  44 enum { TYPELIST(ENUM) TYPECOUNT };
  45 static char const *const pegs_titletypes[] = { TYPELIST(TITLE) };
  46 static char const *const pegs_lowertypes[] = { TYPELIST(LOWER) };
  47 #define TYPECONFIG TYPELIST(CONFIG)
  48
  49 #define FLASH_FRAME 0.13F
  50
  51 struct game_params {
  52     int w, h;
  53     int type;
  54 };
  55
  56 struct game_state {
  57     int w, h;
  58     int completed;
  59     unsigned char *grid;
  60 };
  61
  62 static game_params *default_params(void)
  63 {
  64     game_params *ret = snew(game_params);
  65
  66     ret->w = ret->h = 7;
  67     ret->type = TYPE_CROSS;
  68
  69     return ret;
  70 }
  71
  72 static const struct game_params pegs_presets[] = {
  73     {7, 7, TYPE_CROSS},
  74     {7, 7, TYPE_OCTAGON},
  75     {5, 5, TYPE_RANDOM},
  76     {7, 7, TYPE_RANDOM},
  77     {9, 9, TYPE_RANDOM},
  78 };
  79
  80 static int game_fetch_preset(int i, char **name, game_params **params)
  81 {
  82     game_params *ret;
  83     char str[80];
  84
  85     if (i < 0 || i >= lenof(pegs_presets))
  86         return FALSE;
  87
  88     ret = snew(game_params);
  89     *ret = pegs_presets[i];
  90
  91     strcpy(str, pegs_titletypes[ret->type]);
  92     if (ret->type == TYPE_RANDOM)
  93         sprintf(str + strlen(str), " %dx%d", ret->w, ret->h);
  94
  95     *name = dupstr(str);
  96     *params = ret;
  97     return TRUE;
  98 }
  99
 100 static void free_params(game_params *params)
 101 {
 102     sfree(params);
 103 }
 104
 105 static game_params *dup_params(const game_params *params)
 106 {
 107     game_params *ret = snew(game_params);
 108     *ret = *params;                    /* structure copy */
 109     return ret;
 110 }
 111
 112 static void decode_params(game_params *params, char const *string)
 113 {
 114     char const *p = string;
 115     int i;
 116
 117     params->w = atoi(p);
 118     while (*p && isdigit((unsigned char)*p)) p++;
 119     if (*p == 'x') {
 120         p++;
 121         params->h = atoi(p);
 122         while (*p && isdigit((unsigned char)*p)) p++;
 123     } else {
 124         params->h = params->w;
 125     }
 126
 127     for (i = 0; i < lenof(pegs_lowertypes); i++)
 128         if (!strcmp(p, pegs_lowertypes[i]))
 129             params->type = i;
 130 }
 131
 132 static char *encode_params(const game_params *params, int full)
 133 {
 134     char str[80];
 135
 136     sprintf(str, "%dx%d", params->w, params->h);
 137     if (full) {
 138         assert(params->type >= 0 && params->type < lenof(pegs_lowertypes));
 139         strcat(str, pegs_lowertypes[params->type]);
 140     }
 141     return dupstr(str);
 142 }
 143
 144 static config_item *game_configure(const game_params *params)
 145 {
 146     config_item *ret = snewn(4, config_item);
 147     char buf[80];
 148
 149     ret[0].name = "Width";
 150     ret[0].type = C_STRING;
 151     sprintf(buf, "%d", params->w);
 152     ret[0].u.string.sval = dupstr(buf);
 153
 154     ret[1].name = "Height";
 155     ret[1].type = C_STRING;
 156     sprintf(buf, "%d", params->h);
 157     ret[1].u.string.sval = dupstr(buf);
 158
 159     ret[2].name = "Board type";
 160     ret[2].type = C_CHOICES;
 161     ret[2].u.choices.choicenames = TYPECONFIG;
 162     ret[2].u.choices.selected = params->type;
 163
 164     ret[3].name = NULL;
 165     ret[3].type = C_END;
 166
 167     return ret;
 168 }
 169
 170 static game_params *custom_params(const config_item *cfg)
 171 {
 172     game_params *ret = snew(game_params);
 173
 174     ret->w = atoi(cfg[0].u.string.sval);
 175     ret->h = atoi(cfg[1].u.string.sval);
 176     ret->type = cfg[2].u.choices.selected;
 177
 178     return ret;
 179 }
 180
 181 static const char *validate_params(const 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(const 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 const char *validate_desc(const game_params *params, const 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, const game_params *params,
 672                             const char *desc)
 673 {
 674     int w = params->w, h = params->h;
 675     game_state *state = snew(game_state);
 676     int i;
 677
 678     state->w = w;
 679     state->h = h;
 680     state->completed = 0;
 681     state->grid = snewn(w*h, unsigned char);
 682     for (i = 0; i < w*h; i++)
 683         state->grid[i] = (desc[i] == 'P' ? GRID_PEG :
 684                           desc[i] == 'H' ? GRID_HOLE : GRID_OBST);
 685
 686     return state;
 687 }
 688
 689 static game_state *dup_game(const game_state *state)
 690 {
 691     int w = state->w, h = state->h;
 692     game_state *ret = snew(game_state);
 693
 694     ret->w = state->w;
 695     ret->h = state->h;
 696     ret->completed = state->completed;
 697     ret->grid = snewn(w*h, unsigned char);
 698     memcpy(ret->grid, state->grid, w*h);
 699
 700     return ret;
 701 }
 702
 703 static void free_game(game_state *state)
 704 {
 705     sfree(state->grid);
 706     sfree(state);
 707 }
 708
 709 static char *solve_game(const game_state *state, const game_state *currstate,
 710                         const char *aux, const char **error)
 711 {
 712     return NULL;
 713 }
 714
 715 static int game_can_format_as_text_now(const game_params *params)
 716 {
 717     return TRUE;
 718 }
 719
 720 static char *game_text_format(const game_state *state)
 721 {
 722     int w = state->w, h = state->h;
 723     int x, y;
 724     char *ret;
 725
 726     ret = snewn((w+1)*h + 1, char);
 727
 728     for (y = 0; y < h; y++) {
 729         for (x = 0; x < w; x++)
 730             ret[y*(w+1)+x] = (state->grid[y*w+x] == GRID_HOLE ? '-' :
 731                               state->grid[y*w+x] == GRID_PEG ? '*' : ' ');
 732         ret[y*(w+1)+w] = '\n';
 733     }
 734     ret[h*(w+1)] = '\0';
 735
 736     return ret;
 737 }
 738
 739 struct game_ui {
 740     int dragging;                      /* boolean: is a drag in progress? */
 741     int sx, sy;                        /* grid coords of drag start cell */
 742     int dx, dy;                        /* pixel coords of current drag posn */
 743     int cur_x, cur_y, cur_visible, cur_jumping;
 744 };
 745
 746 static game_ui *new_ui(const game_state *state)
 747 {
 748     game_ui *ui = snew(game_ui);
 749     int x, y, v;
 750
 751     ui->sx = ui->sy = ui->dx = ui->dy = 0;
 752     ui->dragging = FALSE;
 753     ui->cur_visible = ui->cur_jumping = 0;
 754
 755     /* make sure we start the cursor somewhere on the grid. */
 756     for (x = 0; x < state->w; x++) {
 757         for (y = 0; y < state->h; y++) {
 758             v = state->grid[y*state->w+x];
 759             if (v == GRID_PEG || v == GRID_HOLE) {
 760                 ui->cur_x = x; ui->cur_y = y;
 761                 goto found;
 762             }
 763         }
 764     }
 765     assert(!"new_ui found nowhere for cursor");
 766 found:
 767
 768     return ui;
 769 }
 770
 771 static void free_ui(game_ui *ui)
 772 {
 773     sfree(ui);
 774 }
 775
 776 static char *encode_ui(const game_ui *ui)
 777 {
 778     return NULL;
 779 }
 780
 781 static void decode_ui(game_ui *ui, const char *encoding)
 782 {
 783 }
 784
 785 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 786                                const game_state *newstate)
 787 {
 788     /*
 789      * Cancel a drag, in case the source square has become
 790      * unoccupied.
 791      */
 792     ui->dragging = FALSE;
 793 }
 794
 795 #define PREFERRED_TILE_SIZE 33
 796 #define TILESIZE (ds->tilesize)
 797 #define BORDER (TILESIZE / 2)
 798
 799 #define HIGHLIGHT_WIDTH (TILESIZE / 16)
 800
 801 #define COORD(x)     ( BORDER + (x) * TILESIZE )
 802 #define FROMCOORD(x) ( ((x) + TILESIZE - BORDER) / TILESIZE - 1 )
 803
 804 struct game_drawstate {
 805     int tilesize;
 806     blitter *drag_background;
 807     int dragging, dragx, dragy;
 808     int w, h;
 809     unsigned char *grid;
 810     int started;
 811     int bgcolour;
 812 };
 813
 814 static char *interpret_move(const game_state *state, game_ui *ui,
 815                             const game_drawstate *ds,
 816                             int x, int y, int button)
 817 {
 818     int w = state->w, h = state->h;
 819     char buf[80];
 820
 821     if (button == LEFT_BUTTON) {
 822         int tx, ty;
 823
 824         /*
 825          * Left button down: we attempt to start a drag.
 826          */
 827
 828         /*
 829          * There certainly shouldn't be a current drag in progress,
 830          * unless the midend failed to send us button events in
 831          * order; it has a responsibility to always get that right,
 832          * so we can legitimately punish it by failing an
 833          * assertion.
 834          */
 835         assert(!ui->dragging);
 836
 837         tx = FROMCOORD(x);
 838         ty = FROMCOORD(y);
 839         if (tx >= 0 && tx < w && ty >= 0 && ty < h &&
 840             state->grid[ty*w+tx] == GRID_PEG) {
 841             ui->dragging = TRUE;
 842             ui->sx = tx;
 843             ui->sy = ty;
 844             ui->dx = x;
 845             ui->dy = y;
 846             ui->cur_visible = ui->cur_jumping = 0;
 847             return UI_UPDATE;
 848         }
 849     } else if (button == LEFT_DRAG && ui->dragging) {
 850         /*
 851          * Mouse moved; just move the peg being dragged.
 852          */
 853         ui->dx = x;
 854         ui->dy = y;
 855         return UI_UPDATE;
 856     } else if (button == LEFT_RELEASE && ui->dragging) {
 857         int tx, ty, dx, dy;
 858
 859         /*
 860          * Button released. Identify the target square of the drag,
 861          * see if it represents a valid move, and if so make it.
 862          */
 863         ui->dragging = FALSE;          /* cancel the drag no matter what */
 864         tx = FROMCOORD(x);
 865         ty = FROMCOORD(y);
 866         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 867             return UI_UPDATE;          /* target out of range */
 868         dx = tx - ui->sx;
 869         dy = ty - ui->sy;
 870         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 871             return UI_UPDATE;          /* move length was wrong */
 872         dx /= 2;
 873         dy /= 2;
 874
 875         if (state->grid[ty*w+tx] != GRID_HOLE ||
 876             state->grid[(ty-dy)*w+(tx-dx)] != GRID_PEG ||
 877             state->grid[ui->sy*w+ui->sx] != GRID_PEG)
 878             return UI_UPDATE;          /* grid contents were invalid */
 879
 880         /*
 881          * We have a valid move. Encode it simply as source and
 882          * destination coordinate pairs.
 883          */
 884         sprintf(buf, "%d,%d-%d,%d", ui->sx, ui->sy, tx, ty);
 885         return dupstr(buf);
 886     } else if (IS_CURSOR_MOVE(button)) {
 887         if (!ui->cur_jumping) {
 888             /* Not jumping; move cursor as usual, making sure we don't
 889              * leave the gameboard (which may be an irregular shape) */
 890             int cx = ui->cur_x, cy = ui->cur_y;
 891             move_cursor(button, &cx, &cy, w, h, 0);
 892             ui->cur_visible = 1;
 893             if (state->grid[cy*w+cx] == GRID_HOLE ||
 894                 state->grid[cy*w+cx] == GRID_PEG) {
 895                 ui->cur_x = cx;
 896                 ui->cur_y = cy;
 897             }
 898             return UI_UPDATE;
 899         } else {
 900             int dx, dy, mx, my, jx, jy;
 901
 902             /* We're jumping; if the requested direction has a hole, and
 903              * there's a peg in the way, */
 904             assert(state->grid[ui->cur_y*w+ui->cur_x] == GRID_PEG);
 905             dx = (button == CURSOR_RIGHT) ? 1 : (button == CURSOR_LEFT) ? -1 : 0;
 906             dy = (button == CURSOR_DOWN) ? 1 : (button == CURSOR_UP) ? -1 : 0;
 907
 908             mx = ui->cur_x+dx; my = ui->cur_y+dy;
 909             jx = mx+dx; jy = my+dy;
 910
 911             ui->cur_jumping = 0; /* reset, whatever. */
 912             if (jx >= 0 && jy >= 0 && jx < w && jy < h &&
 913                 state->grid[my*w+mx] == GRID_PEG &&
 914                 state->grid[jy*w+jx] == GRID_HOLE) {
 915                 /* Move cursor to the jumped-to location (this felt more
 916                  * natural while playtesting) */
 917                 sprintf(buf, "%d,%d-%d,%d", ui->cur_x, ui->cur_y, jx, jy);
 918                 ui->cur_x = jx; ui->cur_y = jy;
 919                 return dupstr(buf);
 920             }
 921             return UI_UPDATE;
 922         }
 923     } else if (IS_CURSOR_SELECT(button)) {
 924         if (!ui->cur_visible) {
 925             ui->cur_visible = 1;
 926             return UI_UPDATE;
 927         }
 928         if (ui->cur_jumping) {
 929             ui->cur_jumping = 0;
 930             return UI_UPDATE;
 931         }
 932         if (state->grid[ui->cur_y*w+ui->cur_x] == GRID_PEG) {
 933             /* cursor is on peg: next arrow-move wil jump. */
 934             ui->cur_jumping = 1;
 935             return UI_UPDATE;
 936         }
 937         return NULL;
 938     }
 939
 940     return NULL;
 941 }
 942
 943 static game_state *execute_move(const game_state *state, const char *move)
 944 {
 945     int w = state->w, h = state->h;
 946     int sx, sy, tx, ty;
 947     game_state *ret;
 948
 949     if (sscanf(move, "%d,%d-%d,%d", &sx, &sy, &tx, &ty) == 4) {
 950         int mx, my, dx, dy;
 951
 952         if (sx < 0 || sx >= w || sy < 0 || sy >= h)
 953             return NULL;               /* source out of range */
 954         if (tx < 0 || tx >= w || ty < 0 || ty >= h)
 955             return NULL;               /* target out of range */
 956
 957         dx = tx - sx;
 958         dy = ty - sy;
 959         if (max(abs(dx),abs(dy)) != 2 || min(abs(dx),abs(dy)) != 0)
 960             return NULL;               /* move length was wrong */
 961         mx = sx + dx/2;
 962         my = sy + dy/2;
 963
 964         if (state->grid[sy*w+sx] != GRID_PEG ||
 965             state->grid[my*w+mx] != GRID_PEG ||
 966             state->grid[ty*w+tx] != GRID_HOLE)
 967             return NULL;               /* grid contents were invalid */
 968
 969         ret = dup_game(state);
 970         ret->grid[sy*w+sx] = GRID_HOLE;
 971         ret->grid[my*w+mx] = GRID_HOLE;
 972         ret->grid[ty*w+tx] = GRID_PEG;
 973
 974         /*
 975          * Opinion varies on whether getting to a single peg counts as
 976          * completing the game, or whether that peg has to be at a
 977          * specific location (central in the classic cross game, for
 978          * instance). For now we take the former, rather lax position.
 979          */
 980         if (!ret->completed) {
 981             int count = 0, i;
 982             for (i = 0; i < w*h; i++)
 983                 if (ret->grid[i] == GRID_PEG)
 984                     count++;
 985             if (count == 1)
 986                 ret->completed = 1;
 987         }
 988
 989         return ret;
 990     }
 991     return NULL;
 992 }
 993
 994 /* ----------------------------------------------------------------------
 995  * Drawing routines.
 996  */
 997
 998 static void game_compute_size(const game_params *params, int tilesize,
 999                               int *x, int *y)
1000 {
1001     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1002     struct { int tilesize; } ads, *ds = &ads;
1003     ads.tilesize = tilesize;
1004
1005     *x = TILESIZE * params->w + 2 * BORDER;
1006     *y = TILESIZE * params->h + 2 * BORDER;
1007 }
1008
1009 static void game_set_size(drawing *dr, game_drawstate *ds,
1010                           const game_params *params, int tilesize)
1011 {
1012     ds->tilesize = tilesize;
1013
1014     assert(TILESIZE > 0);
1015
1016     assert(!ds->drag_background);      /* set_size is never called twice */
1017     ds->drag_background = blitter_new(dr, TILESIZE, TILESIZE);
1018 }
1019
1020 static float *game_colours(frontend *fe, int *ncolours)
1021 {
1022     float *ret = snewn(3 * NCOLOURS, float);
1023
1024     game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1025
1026     ret[COL_PEG * 3 + 0] = 0.0F;
1027     ret[COL_PEG * 3 + 1] = 0.0F;
1028     ret[COL_PEG * 3 + 2] = 1.0F;
1029
1030     ret[COL_CURSOR * 3 + 0] = 0.5F;
1031     ret[COL_CURSOR * 3 + 1] = 0.5F;
1032     ret[COL_CURSOR * 3 + 2] = 1.0F;
1033
1034     *ncolours = NCOLOURS;
1035     return ret;
1036 }
1037
1038 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1039 {
1040     int w = state->w, h = state->h;
1041     struct game_drawstate *ds = snew(struct game_drawstate);
1042
1043     ds->tilesize = 0;                  /* not decided yet */
1044
1045     /* We can't allocate the blitter rectangle for the drag background
1046      * until we know what size to make it. */
1047     ds->drag_background = NULL;
1048     ds->dragging = FALSE;
1049
1050     ds->w = w;
1051     ds->h = h;
1052     ds->grid = snewn(w*h, unsigned char);
1053     memset(ds->grid, 255, w*h);
1054
1055     ds->started = FALSE;
1056     ds->bgcolour = -1;
1057
1058     return ds;
1059 }
1060
1061 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1062 {
1063     if (ds->drag_background)
1064         blitter_free(dr, ds->drag_background);
1065     sfree(ds->grid);
1066     sfree(ds);
1067 }
1068
1069 static void draw_tile(drawing *dr, game_drawstate *ds,
1070                       int x, int y, int v, int bgcolour)
1071 {
1072     int cursor = 0, jumping = 0, bg;
1073
1074     if (bgcolour >= 0) {
1075         draw_rect(dr, x, y, TILESIZE, TILESIZE, bgcolour);
1076     }
1077     if (v >= GRID_JUMPING) {
1078         jumping = 1; v -= GRID_JUMPING;
1079     }
1080     if (v >= GRID_CURSOR) {
1081         cursor = 1; v -= GRID_CURSOR;
1082     }
1083
1084     if (v == GRID_HOLE) {
1085         bg = cursor ? COL_HIGHLIGHT : COL_LOWLIGHT;
1086         assert(!jumping); /* can't jump from a hole! */
1087         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/4,
1088                     bg, bg);
1089     } else if (v == GRID_PEG) {
1090         bg = (cursor || jumping) ? COL_CURSOR : COL_PEG;
1091         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/3,
1092                     bg, bg);
1093         bg = (!cursor || jumping) ? COL_PEG : COL_CURSOR;
1094         draw_circle(dr, x+TILESIZE/2, y+TILESIZE/2, TILESIZE/4,
1095                     bg, bg);
1096     }
1097
1098     draw_update(dr, x, y, TILESIZE, TILESIZE);
1099 }
1100
1101 static void game_redraw(drawing *dr, game_drawstate *ds,
1102                         const game_state *oldstate, const game_state *state,
1103                         int dir, const game_ui *ui,
1104                         float animtime, float flashtime)
1105 {
1106     int w = state->w, h = state->h;
1107     int x, y;
1108     int bgcolour;
1109
1110     if (flashtime > 0) {
1111         int frame = (int)(flashtime / FLASH_FRAME);
1112         bgcolour = (frame % 2 ? COL_LOWLIGHT : COL_HIGHLIGHT);
1113     } else
1114         bgcolour = COL_BACKGROUND;
1115
1116     /*
1117      * Erase the sprite currently being dragged, if any.
1118      */
1119     if (ds->dragging) {
1120         assert(ds->drag_background);
1121         blitter_load(dr, ds->drag_background, ds->dragx, ds->dragy);
1122         draw_update(dr, ds->dragx, ds->dragy, TILESIZE, TILESIZE);
1123         ds->dragging = FALSE;
1124     }
1125
1126     if (!ds->started) {
1127         draw_rect(dr, 0, 0,
1128                   TILESIZE * state->w + 2 * BORDER,
1129                   TILESIZE * state->h + 2 * BORDER, COL_BACKGROUND);
1130
1131         /*
1132          * Draw relief marks around all the squares that aren't
1133          * GRID_OBST.
1134          */
1135         for (y = 0; y < h; y++)
1136             for (x = 0; x < w; x++)
1137                 if (state->grid[y*w+x] != GRID_OBST) {
1138                     /*
1139                      * First pass: draw the full relief square.
1140                      */
1141                     int coords[6];
1142                     coords[0] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1143                     coords[1] = COORD(y) - HIGHLIGHT_WIDTH;
1144                     coords[2] = COORD(x) - HIGHLIGHT_WIDTH;
1145                     coords[3] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1146                     coords[4] = COORD(x) - HIGHLIGHT_WIDTH;
1147                     coords[5] = COORD(y) - HIGHLIGHT_WIDTH;
1148                     draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1149                     coords[4] = COORD(x+1) + HIGHLIGHT_WIDTH - 1;
1150                     coords[5] = COORD(y+1) + HIGHLIGHT_WIDTH - 1;
1151                     draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
1152                 }
1153         for (y = 0; y < h; y++)
1154             for (x = 0; x < w; x++)
1155                 if (state->grid[y*w+x] != GRID_OBST) {
1156                     /*
1157                      * Second pass: draw everything but the two
1158                      * diagonal corners.
1159                      */
1160                     draw_rect(dr, COORD(x) - HIGHLIGHT_WIDTH,
1161                               COORD(y) - HIGHLIGHT_WIDTH,
1162                               TILESIZE + HIGHLIGHT_WIDTH,
1163                               TILESIZE + HIGHLIGHT_WIDTH, COL_HIGHLIGHT);
1164                     draw_rect(dr, COORD(x),
1165                               COORD(y),
1166                               TILESIZE + HIGHLIGHT_WIDTH,
1167                               TILESIZE + HIGHLIGHT_WIDTH, COL_LOWLIGHT);
1168                 }
1169         for (y = 0; y < h; y++)
1170             for (x = 0; x < w; x++)
1171                 if (state->grid[y*w+x] != GRID_OBST) {
1172                     /*
1173                      * Third pass: draw a trapezium on each edge.
1174                      */
1175                     int coords[8];
1176                     int dx, dy, s, sn, c;
1177
1178                     for (dx = 0; dx < 2; dx++) {
1179                         dy = 1 - dx;
1180                         for (s = 0; s < 2; s++) {
1181                             sn = 2*s - 1;
1182                             c = s ? COL_LOWLIGHT : COL_HIGHLIGHT;
1183
1184                             coords[0] = COORD(x) + (s*dx)*(TILESIZE-1);
1185                             coords[1] = COORD(y) + (s*dy)*(TILESIZE-1);
1186                             coords[2] = COORD(x) + (s*dx+dy)*(TILESIZE-1);
1187                             coords[3] = COORD(y) + (s*dy+dx)*(TILESIZE-1);
1188                             coords[4] = coords[2] - HIGHLIGHT_WIDTH * (dy-sn*dx);
1189                             coords[5] = coords[3] - HIGHLIGHT_WIDTH * (dx-sn*dy);
1190                             coords[6] = coords[0] + HIGHLIGHT_WIDTH * (dy+sn*dx);
1191                             coords[7] = coords[1] + HIGHLIGHT_WIDTH * (dx+sn*dy);
1192                             draw_polygon(dr, coords, 4, c, c);
1193                         }
1194                     }
1195                 }
1196         for (y = 0; y < h; y++)
1197             for (x = 0; x < w; x++)
1198                 if (state->grid[y*w+x] != GRID_OBST) {
1199                     /*
1200                      * Second pass: draw everything but the two
1201                      * diagonal corners.
1202                      */
1203                     draw_rect(dr, COORD(x),
1204                               COORD(y),
1205                               TILESIZE,
1206                               TILESIZE, COL_BACKGROUND);
1207                 }
1208
1209         ds->started = TRUE;
1210
1211         draw_update(dr, 0, 0,
1212                     TILESIZE * state->w + 2 * BORDER,
1213                     TILESIZE * state->h + 2 * BORDER);
1214     }
1215
1216     /*
1217      * Loop over the grid redrawing anything that looks as if it
1218      * needs it.
1219      */
1220     for (y = 0; y < h; y++)
1221         for (x = 0; x < w; x++) {
1222             int v;
1223
1224             v = state->grid[y*w+x];
1225             /*
1226              * Blank the source of a drag so it looks as if the
1227              * user picked the peg up physically.
1228              */
1229             if (ui->dragging && ui->sx == x && ui->sy == y && v == GRID_PEG)
1230                 v = GRID_HOLE;
1231
1232             if (ui->cur_visible && ui->cur_x == x && ui->cur_y == y)
1233                 v += ui->cur_jumping ? GRID_JUMPING : GRID_CURSOR;
1234
1235             if (v != GRID_OBST &&
1236                 (bgcolour != ds->bgcolour || /* always redraw when flashing */
1237                  v != ds->grid[y*w+x])) {
1238                 draw_tile(dr, ds, COORD(x), COORD(y), v, bgcolour);
1239                 ds->grid[y*w+x] = v;
1240             }
1241         }
1242
1243     /*
1244      * Draw the dragging sprite if any.
1245      */
1246     if (ui->dragging) {
1247         ds->dragging = TRUE;
1248         ds->dragx = ui->dx - TILESIZE/2;
1249         ds->dragy = ui->dy - TILESIZE/2;
1250         blitter_save(dr, ds->drag_background, ds->dragx, ds->dragy);
1251         draw_tile(dr, ds, ds->dragx, ds->dragy, GRID_PEG, -1);
1252     }
1253
1254     ds->bgcolour = bgcolour;
1255 }
1256
1257 static float game_anim_length(const game_state *oldstate,
1258                               const game_state *newstate, int dir, game_ui *ui)
1259 {
1260     return 0.0F;
1261 }
1262
1263 static float game_flash_length(const game_state *oldstate,
1264                                const game_state *newstate, int dir, game_ui *ui)
1265 {
1266     if (!oldstate->completed && newstate->completed)
1267         return 2 * FLASH_FRAME;
1268     else
1269         return 0.0F;
1270 }
1271
1272 static int game_status(const game_state *state)
1273 {
1274     /*
1275      * Dead-end situations are assumed to be rescuable by Undo, so we
1276      * don't bother to identify them and return -1.
1277      */
1278     return state->completed ? +1 : 0;
1279 }
1280
1281 static int game_timing_state(const game_state *state, game_ui *ui)
1282 {
1283     return TRUE;
1284 }
1285
1286 static void game_print_size(const game_params *params, float *x, float *y)
1287 {
1288 }
1289
1290 static void game_print(drawing *dr, const game_state *state, int tilesize)
1291 {
1292 }
1293
1294 #ifdef COMBINED
1295 #define thegame pegs
1296 #endif
1297
1298 const struct game thegame = {
1299     "Pegs", "games.pegs", "pegs",
1300     default_params,
1301     game_fetch_preset, NULL,
1302     decode_params,
1303     encode_params,
1304     free_params,
1305     dup_params,
1306     TRUE, game_configure, custom_params,
1307     validate_params,
1308     new_game_desc,
1309     validate_desc,
1310     new_game,
1311     dup_game,
1312     free_game,
1313     FALSE, solve_game,
1314     TRUE, game_can_format_as_text_now, game_text_format,
1315     new_ui,
1316     free_ui,
1317     encode_ui,
1318     decode_ui,
1319     game_changed_state,
1320     interpret_move,
1321     execute_move,
1322     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1323     game_colours,
1324     game_new_drawstate,
1325     game_free_drawstate,
1326     game_redraw,
1327     game_anim_length,
1328     game_flash_length,
1329     game_status,
1330     FALSE, FALSE, game_print_size, game_print,
1331     FALSE,                             /* wants_statusbar */
1332     FALSE, game_timing_state,
1333     0,                                 /* flags */
1334 };
1335
1336 /* vim: set shiftwidth=4 tabstop=8: */