guess.c

   1 /*
   2  * guess.c: Mastermind clone.
   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
  14 #define FLASH_FRAME 0.5F
  15
  16 enum {
  17     COL_BACKGROUND,
  18     COL_FRAME, COL_CURSOR, COL_FLASH, COL_HOLD,
  19     COL_EMPTY, /* must be COL_1 - 1 */
  20     COL_1, COL_2, COL_3, COL_4, COL_5, COL_6, COL_7, COL_8, COL_9, COL_10,
  21     COL_CORRECTPLACE, COL_CORRECTCOLOUR,
  22     NCOLOURS
  23 };
  24
  25 struct game_params {
  26     int ncolours, npegs, nguesses;
  27     int allow_blank, allow_multiple;
  28 };
  29
  30 #define FEEDBACK_CORRECTPLACE  1
  31 #define FEEDBACK_CORRECTCOLOUR 2
  32
  33 typedef struct pegrow {
  34     int npegs;
  35     int *pegs;          /* 0 is 'empty' */
  36     int *feedback;      /* may well be unused */
  37 } *pegrow;
  38
  39 struct game_state {
  40     game_params params;
  41     pegrow *guesses;  /* length params->nguesses */
  42     int *holds;
  43     pegrow solution;
  44     int next_go; /* from 0 to nguesses-1;
  45                     if next_go == nguesses then they've lost. */
  46     int solved;   /* +1 = win, -1 = lose, 0 = still playing */
  47 };
  48
  49 static game_params *default_params(void)
  50 {
  51     game_params *ret = snew(game_params);
  52
  53     /* AFAIK this is the canonical Mastermind ruleset. */
  54     ret->ncolours = 6;
  55     ret->npegs = 4;
  56     ret->nguesses = 10;
  57
  58     ret->allow_blank = 0;
  59     ret->allow_multiple = 1;
  60
  61     return ret;
  62 }
  63
  64 static void free_params(game_params *params)
  65 {
  66     sfree(params);
  67 }
  68
  69 static game_params *dup_params(const game_params *params)
  70 {
  71     game_params *ret = snew(game_params);
  72     *ret = *params;                    /* structure copy */
  73     return ret;
  74 }
  75
  76 static const struct {
  77     const char *name;
  78     game_params params;
  79 } guess_presets[] = {
  80     {"Standard", {6, 4, 10, FALSE, TRUE}},
  81     {"Super", {8, 5, 12, FALSE, TRUE}},
  82 };
  83
  84
  85 static int game_fetch_preset(int i, char **name, game_params **params)
  86 {
  87     if (i < 0 || i >= lenof(guess_presets))
  88         return FALSE;
  89
  90     *name = dupstr(guess_presets[i].name);
  91     /*
  92      * get round annoying const issues
  93      */
  94     {
  95         game_params tmp = guess_presets[i].params;
  96         *params = dup_params(&tmp);
  97     }
  98
  99     return TRUE;
 100 }
 101
 102 static void decode_params(game_params *params, char const *string)
 103 {
 104     char const *p = string;
 105     game_params *defs = default_params();
 106
 107     *params = *defs; free_params(defs);
 108
 109     while (*p) {
 110         switch (*p++) {
 111         case 'c':
 112             params->ncolours = atoi(p);
 113             while (*p && isdigit((unsigned char)*p)) p++;
 114             break;
 115
 116         case 'p':
 117             params->npegs = atoi(p);
 118             while (*p && isdigit((unsigned char)*p)) p++;
 119             break;
 120
 121         case 'g':
 122             params->nguesses = atoi(p);
 123             while (*p && isdigit((unsigned char)*p)) p++;
 124             break;
 125
 126         case 'b':
 127             params->allow_blank = 1;
 128             break;
 129
 130         case 'B':
 131             params->allow_blank = 0;
 132             break;
 133
 134         case 'm':
 135             params->allow_multiple = 1;
 136             break;
 137
 138         case 'M':
 139             params->allow_multiple = 0;
 140             break;
 141
 142         default:
 143             ;
 144         }
 145     }
 146 }
 147
 148 static char *encode_params(const game_params *params, int full)
 149 {
 150     char data[256];
 151
 152     sprintf(data, "c%dp%dg%d%s%s",
 153             params->ncolours, params->npegs, params->nguesses,
 154             params->allow_blank ? "b" : "B", params->allow_multiple ? "m" : "M");
 155
 156     return dupstr(data);
 157 }
 158
 159 static config_item *game_configure(const game_params *params)
 160 {
 161     config_item *ret;
 162     char buf[80];
 163
 164     ret = snewn(6, config_item);
 165
 166     ret[0].name = "Colours";
 167     ret[0].type = C_STRING;
 168     sprintf(buf, "%d", params->ncolours);
 169     ret[0].u.string.sval = dupstr(buf);
 170
 171     ret[1].name = "Pegs per guess";
 172     ret[1].type = C_STRING;
 173     sprintf(buf, "%d", params->npegs);
 174     ret[1].u.string.sval = dupstr(buf);
 175
 176     ret[2].name = "Guesses";
 177     ret[2].type = C_STRING;
 178     sprintf(buf, "%d", params->nguesses);
 179     ret[2].u.string.sval = dupstr(buf);
 180
 181     ret[3].name = "Allow blanks";
 182     ret[3].type = C_BOOLEAN;
 183     ret[3].u.boolean.bval = params->allow_blank;
 184
 185     ret[4].name = "Allow duplicates";
 186     ret[4].type = C_BOOLEAN;
 187     ret[4].u.boolean.bval = params->allow_multiple;
 188
 189     ret[5].name = NULL;
 190     ret[5].type = C_END;
 191
 192     return ret;
 193 }
 194
 195 static game_params *custom_params(const config_item *cfg)
 196 {
 197     game_params *ret = snew(game_params);
 198
 199     ret->ncolours = atoi(cfg[0].u.string.sval);
 200     ret->npegs = atoi(cfg[1].u.string.sval);
 201     ret->nguesses = atoi(cfg[2].u.string.sval);
 202
 203     ret->allow_blank = cfg[3].u.boolean.bval;
 204     ret->allow_multiple = cfg[4].u.boolean.bval;
 205
 206     return ret;
 207 }
 208
 209 static const char *validate_params(const game_params *params, int full)
 210 {
 211     if (params->ncolours < 2 || params->npegs < 2)
 212         return "Trivial solutions are uninteresting";
 213     /* NB as well as the no. of colours we define, max(ncolours) must
 214      * also fit in an unsigned char; see new_game_desc. */
 215     if (params->ncolours > 10)
 216         return "Too many colours";
 217     if (params->nguesses < 1)
 218         return "Must have at least one guess";
 219     if (!params->allow_multiple && params->ncolours < params->npegs)
 220         return "Disallowing multiple colours requires at least as many colours as pegs";
 221     return NULL;
 222 }
 223
 224 static pegrow new_pegrow(int npegs)
 225 {
 226     pegrow pegs = snew(struct pegrow);
 227
 228     pegs->npegs = npegs;
 229     pegs->pegs = snewn(pegs->npegs, int);
 230     memset(pegs->pegs, 0, pegs->npegs * sizeof(int));
 231     pegs->feedback = snewn(pegs->npegs, int);
 232     memset(pegs->feedback, 0, pegs->npegs * sizeof(int));
 233
 234     return pegs;
 235 }
 236
 237 static pegrow dup_pegrow(pegrow pegs)
 238 {
 239     pegrow newpegs = new_pegrow(pegs->npegs);
 240
 241     memcpy(newpegs->pegs, pegs->pegs, newpegs->npegs * sizeof(int));
 242     memcpy(newpegs->feedback, pegs->feedback, newpegs->npegs * sizeof(int));
 243
 244     return newpegs;
 245 }
 246
 247 static void invalidate_pegrow(pegrow pegs)
 248 {
 249     memset(pegs->pegs, -1, pegs->npegs * sizeof(int));
 250     memset(pegs->feedback, -1, pegs->npegs * sizeof(int));
 251 }
 252
 253 static void free_pegrow(pegrow pegs)
 254 {
 255     sfree(pegs->pegs);
 256     sfree(pegs->feedback);
 257     sfree(pegs);
 258 }
 259
 260 static char *new_game_desc(const game_params *params, random_state *rs,
 261                            char **aux, int interactive)
 262 {
 263     unsigned char *bmp = snewn(params->npegs, unsigned char);
 264     char *ret;
 265     int i, c;
 266     pegrow colcount = new_pegrow(params->ncolours);
 267
 268     for (i = 0; i < params->npegs; i++) {
 269 newcol:
 270         c = random_upto(rs, params->ncolours);
 271         if (!params->allow_multiple && colcount->pegs[c]) goto newcol;
 272         colcount->pegs[c]++;
 273         bmp[i] = (unsigned char)(c+1);
 274     }
 275     obfuscate_bitmap(bmp, params->npegs*8, FALSE);
 276
 277     ret = bin2hex(bmp, params->npegs);
 278     sfree(bmp);
 279     free_pegrow(colcount);
 280     return ret;
 281 }
 282
 283 static const char *validate_desc(const game_params *params, const char *desc)
 284 {
 285     unsigned char *bmp;
 286     int i;
 287
 288     /* desc is just an (obfuscated) bitmap of the solution; check that
 289      * it's the correct length and (when unobfuscated) contains only
 290      * sensible colours. */
 291     if (strlen(desc) != params->npegs * 2)
 292         return "Game description is wrong length";
 293     bmp = hex2bin(desc, params->npegs);
 294     obfuscate_bitmap(bmp, params->npegs*8, TRUE);
 295     for (i = 0; i < params->npegs; i++) {
 296         if (bmp[i] < 1 || bmp[i] > params->ncolours) {
 297             sfree(bmp);
 298             return "Game description is corrupted";
 299         }
 300     }
 301     sfree(bmp);
 302
 303     return NULL;
 304 }
 305
 306 static game_state *new_game(midend *me, const game_params *params,
 307                             const char *desc)
 308 {
 309     game_state *state = snew(game_state);
 310     unsigned char *bmp;
 311     int i;
 312
 313     state->params = *params;
 314     state->guesses = snewn(params->nguesses, pegrow);
 315     for (i = 0; i < params->nguesses; i++)
 316         state->guesses[i] = new_pegrow(params->npegs);
 317     state->holds = snewn(params->npegs, int);
 318     state->solution = new_pegrow(params->npegs);
 319
 320     bmp = hex2bin(desc, params->npegs);
 321     obfuscate_bitmap(bmp, params->npegs*8, TRUE);
 322     for (i = 0; i < params->npegs; i++)
 323         state->solution->pegs[i] = (int)bmp[i];
 324     sfree(bmp);
 325
 326     memset(state->holds, 0, sizeof(int) * params->npegs);
 327     state->next_go = state->solved = 0;
 328
 329     return state;
 330 }
 331
 332 static game_state *dup_game(const game_state *state)
 333 {
 334     game_state *ret = snew(game_state);
 335     int i;
 336
 337     *ret = *state;
 338
 339     ret->guesses = snewn(state->params.nguesses, pegrow);
 340     for (i = 0; i < state->params.nguesses; i++)
 341         ret->guesses[i] = dup_pegrow(state->guesses[i]);
 342     ret->holds = snewn(state->params.npegs, int);
 343     memcpy(ret->holds, state->holds, sizeof(int) * state->params.npegs);
 344     ret->solution = dup_pegrow(state->solution);
 345
 346     return ret;
 347 }
 348
 349 static void free_game(game_state *state)
 350 {
 351     int i;
 352
 353     free_pegrow(state->solution);
 354     for (i = 0; i < state->params.nguesses; i++)
 355         free_pegrow(state->guesses[i]);
 356     sfree(state->holds);
 357     sfree(state->guesses);
 358
 359     sfree(state);
 360 }
 361
 362 static char *solve_game(const game_state *state, const game_state *currstate,
 363                         const char *aux, const char **error)
 364 {
 365     return dupstr("S");
 366 }
 367
 368 static int game_can_format_as_text_now(const game_params *params)
 369 {
 370     return TRUE;
 371 }
 372
 373 static char *game_text_format(const game_state *state)
 374 {
 375     return NULL;
 376 }
 377
 378 static int is_markable(const game_params *params, pegrow pegs)
 379 {
 380     int i, nset = 0, nrequired, ret = 0;
 381     pegrow colcount = new_pegrow(params->ncolours);
 382
 383     nrequired = params->allow_blank ? 1 : params->npegs;
 384
 385     for (i = 0; i < params->npegs; i++) {
 386         int c = pegs->pegs[i];
 387         if (c > 0) {
 388             colcount->pegs[c-1]++;
 389             nset++;
 390         }
 391     }
 392     if (nset < nrequired) goto done;
 393
 394     if (!params->allow_multiple) {
 395         for (i = 0; i < params->ncolours; i++) {
 396             if (colcount->pegs[i] > 1) goto done;
 397         }
 398     }
 399     ret = 1;
 400 done:
 401     free_pegrow(colcount);
 402     return ret;
 403 }
 404
 405 struct game_ui {
 406     game_params params;
 407     pegrow curr_pegs; /* half-finished current move */
 408     int *holds;
 409     int colour_cur;   /* position of up-down colour picker cursor */
 410     int peg_cur;      /* position of left-right peg picker cursor */
 411     int display_cur, markable;
 412
 413     int drag_col, drag_x, drag_y; /* x and y are *center* of peg! */
 414     int drag_opeg; /* peg index, if dragged from a peg (from current guess), otherwise -1 */
 415
 416     int show_labels;                   /* label the colours with letters */
 417     pegrow hint;
 418 };
 419
 420 static game_ui *new_ui(const game_state *state)
 421 {
 422     game_ui *ui = snew(game_ui);
 423     memset(ui, 0, sizeof(game_ui));
 424     ui->params = state->params;        /* structure copy */
 425     ui->curr_pegs = new_pegrow(state->params.npegs);
 426     ui->holds = snewn(state->params.npegs, int);
 427     memset(ui->holds, 0, sizeof(int)*state->params.npegs);
 428     ui->drag_opeg = -1;
 429     return ui;
 430 }
 431
 432 static void free_ui(game_ui *ui)
 433 {
 434     if (ui->hint)
 435         free_pegrow(ui->hint);
 436     free_pegrow(ui->curr_pegs);
 437     sfree(ui->holds);
 438     sfree(ui);
 439 }
 440
 441 static char *encode_ui(const game_ui *ui)
 442 {
 443     char *ret, *p;
 444     const char *sep;
 445     int i;
 446
 447     /*
 448      * For this game it's worth storing the contents of the current
 449      * guess, and the current set of holds.
 450      */
 451     ret = snewn(40 * ui->curr_pegs->npegs, char);
 452     p = ret;
 453     sep = "";
 454     for (i = 0; i < ui->curr_pegs->npegs; i++) {
 455         p += sprintf(p, "%s%d%s", sep, ui->curr_pegs->pegs[i],
 456                      ui->holds[i] ? "_" : "");
 457         sep = ",";
 458     }
 459     *p++ = '\0';
 460     assert(p - ret < 40 * ui->curr_pegs->npegs);
 461     return sresize(ret, p - ret, char);
 462 }
 463
 464 static void decode_ui(game_ui *ui, const char *encoding)
 465 {
 466     int i;
 467     const char *p = encoding;
 468     for (i = 0; i < ui->curr_pegs->npegs; i++) {
 469         ui->curr_pegs->pegs[i] = atoi(p);
 470         while (*p && isdigit((unsigned char)*p)) p++;
 471         if (*p == '_') {
 472             /* NB: old versions didn't store holds */
 473             ui->holds[i] = 1;
 474             p++;
 475         } else
 476             ui->holds[i] = 0;
 477         if (*p == ',') p++;
 478     }
 479     ui->markable = is_markable(&ui->params, ui->curr_pegs);
 480 }
 481
 482 static void game_changed_state(game_ui *ui, const game_state *oldstate,
 483                                const game_state *newstate)
 484 {
 485     int i;
 486
 487     if (newstate->next_go < oldstate->next_go) {
 488         sfree(ui->hint);
 489         ui->hint = NULL;
 490     }
 491
 492     /* Implement holds, clear other pegs.
 493      * This does something that is arguably the Right Thing even
 494      * for undo. */
 495     for (i = 0; i < newstate->solution->npegs; i++) {
 496         if (newstate->solved)
 497             ui->holds[i] = 0;
 498         else
 499             ui->holds[i] = newstate->holds[i];
 500         if (newstate->solved || (newstate->next_go == 0) || !ui->holds[i]) {
 501             ui->curr_pegs->pegs[i] = 0;
 502         } else
 503             ui->curr_pegs->pegs[i] =
 504                 newstate->guesses[newstate->next_go-1]->pegs[i];
 505     }
 506     ui->markable = is_markable(&newstate->params, ui->curr_pegs);
 507     /* Clean up cursor position */
 508     if (!ui->markable && ui->peg_cur == newstate->solution->npegs)
 509         ui->peg_cur--;
 510 }
 511
 512 #define PEGSZ   (ds->pegsz)
 513 #define PEGOFF  (ds->pegsz + ds->gapsz)
 514 #define HINTSZ  (ds->hintsz)
 515 #define HINTOFF (ds->hintsz + ds->gapsz)
 516
 517 #define GAP     (ds->gapsz)
 518 #define CGAP    (ds->gapsz / 2)
 519
 520 #define PEGRAD  (ds->pegrad)
 521 #define HINTRAD (ds->hintrad)
 522
 523 #define COL_OX          (ds->colx)
 524 #define COL_OY          (ds->coly)
 525 #define COL_X(c)        (COL_OX)
 526 #define COL_Y(c)        (COL_OY + (c)*PEGOFF)
 527 #define COL_W           PEGOFF
 528 #define COL_H           (ds->colours->npegs*PEGOFF)
 529
 530 #define GUESS_OX        (ds->guessx)
 531 #define GUESS_OY        (ds->guessy)
 532 #define GUESS_X(g,p)    (GUESS_OX + (p)*PEGOFF)
 533 #define GUESS_Y(g,p)    (GUESS_OY + (g)*PEGOFF)
 534 #define GUESS_W         (ds->solution->npegs*PEGOFF)
 535 #define GUESS_H         (ds->nguesses*PEGOFF)
 536
 537 #define HINT_OX         (GUESS_OX + GUESS_W + ds->gapsz)
 538 #define HINT_OY         (GUESS_OY + (PEGSZ - HINTOFF - HINTSZ) / 2)
 539 #define HINT_X(g)       HINT_OX
 540 #define HINT_Y(g)       (HINT_OY + (g)*PEGOFF)
 541 #define HINT_W          ((ds->hintw*HINTOFF) - GAP)
 542 #define HINT_H          GUESS_H
 543
 544 #define SOLN_OX         GUESS_OX
 545 #define SOLN_OY         (GUESS_OY + GUESS_H + ds->gapsz + 2)
 546 #define SOLN_W          GUESS_W
 547 #define SOLN_H          PEGOFF
 548
 549 struct game_drawstate {
 550     int nguesses;
 551     pegrow *guesses;    /* same size as state->guesses */
 552     pegrow solution;    /* only displayed if state->solved */
 553     pegrow colours;     /* length ncolours, not npegs */
 554
 555     int pegsz, hintsz, gapsz; /* peg size (diameter), etc. */
 556     int pegrad, hintrad;      /* radius of peg, hint */
 557     int border;
 558     int colx, coly;     /* origin of colours vertical bar */
 559     int guessx, guessy; /* origin of guesses */
 560     int solnx, solny;   /* origin of solution */
 561     int hintw;          /* no. of hint tiles we're wide per row */
 562     int w, h, started, solved;
 563
 564     int next_go;
 565
 566     blitter *blit_peg;
 567     int drag_col, blit_ox, blit_oy;
 568 };
 569
 570 static void set_peg(const game_params *params, game_ui *ui, int peg, int col)
 571 {
 572     ui->curr_pegs->pegs[peg] = col;
 573     ui->markable = is_markable(params, ui->curr_pegs);
 574 }
 575
 576 static int mark_pegs(pegrow guess, const pegrow solution, int ncols)
 577 {
 578     int nc_place = 0, nc_colour = 0, i, j;
 579
 580     assert(guess && solution && (guess->npegs == solution->npegs));
 581
 582     for (i = 0; i < guess->npegs; i++) {
 583         if (guess->pegs[i] == solution->pegs[i]) nc_place++;
 584     }
 585
 586     /* slight bit of cleverness: we have the following formula, from
 587      * http://mathworld.wolfram.com/Mastermind.html that gives:
 588      *
 589      * nc_colour = sum(colours, min(#solution, #guess)) - nc_place
 590      *
 591      * I think this is due to Knuth.
 592      */
 593     for (i = 1; i <= ncols; i++) {
 594         int n_guess = 0, n_solution = 0;
 595         for (j = 0; j < guess->npegs; j++) {
 596             if (guess->pegs[j] == i) n_guess++;
 597             if (solution->pegs[j] == i) n_solution++;
 598         }
 599         nc_colour += min(n_guess, n_solution);
 600     }
 601     nc_colour -= nc_place;
 602
 603     debug(("mark_pegs, %d pegs, %d right place, %d right colour",
 604            guess->npegs, nc_place, nc_colour));
 605     assert((nc_colour + nc_place) <= guess->npegs);
 606
 607     memset(guess->feedback, 0, guess->npegs*sizeof(int));
 608     for (i = 0, j = 0; i < nc_place; i++)
 609         guess->feedback[j++] = FEEDBACK_CORRECTPLACE;
 610     for (i = 0; i < nc_colour; i++)
 611         guess->feedback[j++] = FEEDBACK_CORRECTCOLOUR;
 612
 613     return nc_place;
 614 }
 615
 616 static char *encode_move(const game_state *from, game_ui *ui)
 617 {
 618     char *buf, *p;
 619     const char *sep;
 620     int len, i;
 621
 622     len = ui->curr_pegs->npegs * 20 + 2;
 623     buf = snewn(len, char);
 624     p = buf;
 625     *p++ = 'G';
 626     sep = "";
 627     for (i = 0; i < ui->curr_pegs->npegs; i++) {
 628         p += sprintf(p, "%s%d%s", sep, ui->curr_pegs->pegs[i],
 629                      ui->holds[i] ? "_" : "");
 630         sep = ",";
 631     }
 632     *p++ = '\0';
 633     assert(p - buf <= len);
 634     buf = sresize(buf, len, char);
 635
 636     return buf;
 637 }
 638
 639 static void compute_hint(const game_state *state, game_ui *ui)
 640 {
 641     /* Suggest the lexicographically first row consistent with all
 642      * previous feedback.  This is not only a useful hint, but also
 643      * a reasonable strategy if applied consistently.  If the user
 644      * uses hints in every turn, they may be able to intuit this
 645      * strategy, or one similar to it.  I (Jonas Kölker) came up
 646      * with something close to it without seeing it in action. */
 647
 648     /* Some performance characteristics: I want to ask for each n,
 649      * how many solutions are guessed in exactly n guesses if you
 650      * use the hint in each turn.
 651      *
 652      * With 4 pegs and 6 colours you get the following histogram:
 653      *
 654      *  1 guesses:     1 solution
 655      *  2 guesses:     4 solutions
 656      *  3 guesses:    25 solutions
 657      *  4 guesses:   108 solutions
 658      *  5 guesses:   305 solutions
 659      *  6 guesses:   602 solutions
 660      *  7 guesses:   196 solutions
 661      *  8 guesses:    49 solutions
 662      *  9 guesses:     6 solutions
 663      * (note: the tenth guess is never necessary.)
 664      *
 665      * With 5 pegs and 8 colours you get the following histogram:
 666      *
 667      *  1 guesses:     1 solution
 668      *  2 guesses:     5 solutions
 669      *  3 guesses:    43 solutions
 670      *  4 guesses:   278 solutions
 671      *  5 guesses:  1240 solutions
 672      *  6 guesses:  3515 solutions
 673      *  7 guesses:  7564 solutions
 674      *  8 guesses: 14086 solutions
 675      *  9 guesses:  4614 solutions
 676      * 10 guesses:  1239 solutions
 677      * 11 guesses:   175 solutions
 678      * 12 guesses:     7 solutions
 679      * 13 guesses:     1 solution
 680      *
 681      * The solution which takes too many guesses is {8, 8, 5, 6, 7}.
 682      * The game ID is c8p5g12Bm:4991e5e41a. */
 683
 684     int mincolour = 1, maxcolour = 0, i, j;
 685
 686     /* For large values of npegs and ncolours, the lexicographically
 687      * next guess make take a while to find.  Finding upper and
 688      * lower limits on which colours we have to consider will speed
 689      * this up, as will caching our progress from one invocation to
 690      * the next.  The latter strategy works, since if we have ruled
 691      * out a candidate we will never reverse this judgment in the
 692      * light of new information.  Removing information, i.e. undo,
 693      * will require us to backtrack somehow.  We backtrack by fully
 694      * forgetting our progress (and recomputing it if required). */
 695
 696     for (i = 0; i < state->next_go; ++i)
 697         for (j = 0; j < state->params.npegs; ++j)
 698             if (state->guesses[i]->pegs[j] > maxcolour)
 699                 maxcolour = state->guesses[i]->pegs[j];
 700     maxcolour = min(maxcolour + 1, state->params.ncolours);
 701
 702 increase_mincolour:
 703     for (i = 0; i < state->next_go; ++i) {
 704         if (state->guesses[i]->feedback[0])
 705             goto next_iteration;
 706         for (j = 0; j < state->params.npegs; ++j)
 707             if (state->guesses[i]->pegs[j] != mincolour)
 708                 goto next_iteration;
 709         ++mincolour;
 710         goto increase_mincolour;
 711     next_iteration:
 712         ;
 713     }
 714
 715     if (!ui->hint) {
 716         ui->hint = new_pegrow(state->params.npegs);
 717         for (i = 0; i < state->params.npegs; ++i)
 718             ui->hint->pegs[i] = 1;
 719     }
 720
 721     while (ui->hint->pegs[0] <= state->params.ncolours) {
 722         for (i = 0; i < state->next_go; ++i) {
 723             mark_pegs(ui->hint, state->guesses[i], maxcolour);
 724             for (j = 0; j < state->params.npegs; ++j)
 725                 if (ui->hint->feedback[j] != state->guesses[i]->feedback[j])
 726                     goto increment_pegrow;
 727         }
 728         /* a valid guess was found; install it and return */
 729         for (i = 0; i < state->params.npegs; ++i)
 730             ui->curr_pegs->pegs[i] = ui->hint->pegs[i];
 731
 732         ui->markable = TRUE;
 733         ui->peg_cur = state->params.npegs;
 734         ui->display_cur = 1;
 735         return;
 736
 737     increment_pegrow:
 738         for (i = ui->hint->npegs;
 739              ++ui->hint->pegs[--i], i && ui->hint->pegs[i] > maxcolour;
 740              ui->hint->pegs[i] = mincolour);
 741     }
 742     /* No solution is compatible with the given hints.  Impossible! */
 743     /* (hack new_game_desc to create invalid solutions to get here) */
 744
 745     /* For some values of npegs and ncolours, the hinting function takes a
 746      * long time to complete.  To visually indicate completion with failure,
 747      * should it ever happen, update the ui in some trivial way.  This gives
 748      * the user a sense of broken(ish)ness and futility. */
 749     if (!ui->display_cur) {
 750         ui->display_cur = 1;
 751     } else if (state->params.npegs == 1) {
 752         ui->display_cur = 0;
 753     } else {
 754         ui->peg_cur = (ui->peg_cur + 1) % state->params.npegs;
 755     }
 756 }
 757
 758 static char *interpret_move(const game_state *from, game_ui *ui,
 759                             const game_drawstate *ds,
 760                             int x, int y, int button)
 761 {
 762     int over_col = 0;           /* one-indexed */
 763     int over_guess = -1;        /* zero-indexed */
 764     int over_past_guess_y = -1; /* zero-indexed */
 765     int over_past_guess_x = -1; /* zero-indexed */
 766     int over_hint = 0;          /* zero or one */
 767     char *ret = NULL;
 768
 769     int guess_ox = GUESS_X(from->next_go, 0);
 770     int guess_oy = GUESS_Y(from->next_go, 0);
 771
 772     /*
 773      * Enable or disable labels on colours.
 774      */
 775     if (button == 'l' || button == 'L') {
 776         ui->show_labels = !ui->show_labels;
 777         return UI_UPDATE;
 778     }
 779
 780     if (from->solved) return NULL;
 781
 782     if (x >= COL_OX && x < (COL_OX + COL_W) &&
 783         y >= COL_OY && y < (COL_OY + COL_H)) {
 784         over_col = ((y - COL_OY) / PEGOFF) + 1;
 785         assert(over_col >= 1 && over_col <= ds->colours->npegs);
 786     } else if (x >= guess_ox &&
 787                y >= guess_oy && y < (guess_oy + GUESS_H)) {
 788         if (x < (guess_ox + GUESS_W)) {
 789             over_guess = (x - guess_ox) / PEGOFF;
 790             assert(over_guess >= 0 && over_guess < ds->solution->npegs);
 791         } else {
 792             over_hint = 1;
 793         }
 794     } else if (x >= guess_ox && x < (guess_ox + GUESS_W) &&
 795                y >= GUESS_OY && y < guess_oy) {
 796         over_past_guess_y = (y - GUESS_OY) / PEGOFF;
 797         over_past_guess_x = (x - guess_ox) / PEGOFF;
 798         assert(over_past_guess_y >= 0 && over_past_guess_y < from->next_go);
 799         assert(over_past_guess_x >= 0 && over_past_guess_x < ds->solution->npegs);
 800     }
 801     debug(("make_move: over_col %d, over_guess %d, over_hint %d,"
 802            " over_past_guess (%d,%d)", over_col, over_guess, over_hint,
 803            over_past_guess_x, over_past_guess_y));
 804
 805     assert(ds->blit_peg);
 806
 807     /* mouse input */
 808     if (button == LEFT_BUTTON) {
 809         if (over_col > 0) {
 810             ui->drag_col = over_col;
 811             ui->drag_opeg = -1;
 812             debug(("Start dragging from colours"));
 813         } else if (over_guess > -1) {
 814             int col = ui->curr_pegs->pegs[over_guess];
 815             if (col) {
 816                 ui->drag_col = col;
 817                 ui->drag_opeg = over_guess;
 818                 debug(("Start dragging from a guess"));
 819             }
 820         } else if (over_past_guess_y > -1) {
 821             int col =
 822                 from->guesses[over_past_guess_y]->pegs[over_past_guess_x];
 823             if (col) {
 824                 ui->drag_col = col;
 825                 ui->drag_opeg = -1;
 826                 debug(("Start dragging from a past guess"));
 827             }
 828         }
 829         if (ui->drag_col) {
 830             ui->drag_x = x;
 831             ui->drag_y = y;
 832             debug(("Start dragging, col = %d, (%d,%d)",
 833                    ui->drag_col, ui->drag_x, ui->drag_y));
 834             ret = UI_UPDATE;
 835         }
 836     } else if (button == LEFT_DRAG && ui->drag_col) {
 837         ui->drag_x = x;
 838         ui->drag_y = y;
 839         debug(("Keep dragging, (%d,%d)", ui->drag_x, ui->drag_y));
 840         ret = UI_UPDATE;
 841     } else if (button == LEFT_RELEASE && ui->drag_col) {
 842         if (over_guess > -1) {
 843             debug(("Dropping colour %d onto guess peg %d",
 844                    ui->drag_col, over_guess));
 845             set_peg(&from->params, ui, over_guess, ui->drag_col);
 846         } else {
 847             if (ui->drag_opeg > -1) {
 848                 debug(("Removing colour %d from peg %d",
 849                        ui->drag_col, ui->drag_opeg));
 850                 set_peg(&from->params, ui, ui->drag_opeg, 0);
 851             }
 852         }
 853         ui->drag_col = 0;
 854         ui->drag_opeg = -1;
 855         ui->display_cur = 0;
 856         debug(("Stop dragging."));
 857         ret = UI_UPDATE;
 858     } else if (button == RIGHT_BUTTON) {
 859         if (over_guess > -1) {
 860             /* we use ths feedback in the game_ui to signify
 861              * 'carry this peg to the next guess as well'. */
 862             ui->holds[over_guess] = 1 - ui->holds[over_guess];
 863             ret = UI_UPDATE;
 864         }
 865     } else if (button == LEFT_RELEASE && over_hint && ui->markable) {
 866         /* NB this won't trigger if on the end of a drag; that's on
 867          * purpose, in case you drop by mistake... */
 868         ret = encode_move(from, ui);
 869     }
 870
 871     /* keyboard input */
 872     if (button == CURSOR_UP || button == CURSOR_DOWN) {
 873         ui->display_cur = 1;
 874         if (button == CURSOR_DOWN && (ui->colour_cur+1) < from->params.ncolours)
 875             ui->colour_cur++;
 876         if (button == CURSOR_UP && ui->colour_cur > 0)
 877             ui->colour_cur--;
 878         ret = UI_UPDATE;
 879     } else if (button == 'h' || button == 'H' || button == '?') {
 880         compute_hint(from, ui);
 881         ret = UI_UPDATE;
 882     } else if (button == CURSOR_LEFT || button == CURSOR_RIGHT) {
 883         int maxcur = from->params.npegs;
 884         if (ui->markable) maxcur++;
 885
 886         ui->display_cur = 1;
 887         if (button == CURSOR_RIGHT && (ui->peg_cur+1) < maxcur)
 888             ui->peg_cur++;
 889         if (button == CURSOR_LEFT && ui->peg_cur > 0)
 890             ui->peg_cur--;
 891         ret = UI_UPDATE;
 892     } else if (IS_CURSOR_SELECT(button)) {
 893         ui->display_cur = 1;
 894         if (ui->peg_cur == from->params.npegs) {
 895             ret = encode_move(from, ui);
 896         } else {
 897             set_peg(&from->params, ui, ui->peg_cur, ui->colour_cur+1);
 898             ret = UI_UPDATE;
 899         }
 900     } else if (button == 'D' || button == 'd' || button == '\b') {
 901         ui->display_cur = 1;
 902         set_peg(&from->params, ui, ui->peg_cur, 0);
 903         ret = UI_UPDATE;
 904     } else if (button == CURSOR_SELECT2) {
 905         if (ui->peg_cur == from->params.npegs)
 906             return NULL;
 907         ui->display_cur = 1;
 908         ui->holds[ui->peg_cur] = 1 - ui->holds[ui->peg_cur];
 909         ret = UI_UPDATE;
 910     }
 911     return ret;
 912 }
 913
 914 static game_state *execute_move(const game_state *from, const char *move)
 915 {
 916     int i, nc_place;
 917     game_state *ret;
 918     const char *p;
 919
 920     if (!strcmp(move, "S")) {
 921         ret = dup_game(from);
 922         ret->solved = -1;
 923         return ret;
 924     } else if (move[0] == 'G') {
 925         p = move+1;
 926
 927         ret = dup_game(from);
 928
 929         for (i = 0; i < from->solution->npegs; i++) {
 930             int val = atoi(p);
 931             int min_colour = from->params.allow_blank? 0 : 1;
 932             if (val < min_colour || val > from->params.ncolours) {
 933                 free_game(ret);
 934                 return NULL;
 935             }
 936             ret->guesses[from->next_go]->pegs[i] = atoi(p);
 937             while (*p && isdigit((unsigned char)*p)) p++;
 938             if (*p == '_') {
 939                 ret->holds[i] = 1;
 940                 p++;
 941             } else
 942                 ret->holds[i] = 0;
 943             if (*p == ',') p++;
 944         }
 945
 946         nc_place = mark_pegs(ret->guesses[from->next_go], ret->solution, ret->params.ncolours);
 947
 948         if (nc_place == ret->solution->npegs) {
 949             ret->solved = +1; /* win! */
 950         } else {
 951             ret->next_go = from->next_go + 1;
 952             if (ret->next_go >= ret->params.nguesses)
 953                 ret->solved = -1; /* lose, meaning we show the pegs. */
 954         }
 955
 956         return ret;
 957     } else
 958         return NULL;
 959 }
 960
 961 /* ----------------------------------------------------------------------
 962  * Drawing routines.
 963  */
 964
 965 #define PEG_PREFER_SZ 32
 966
 967 /* next three are multipliers for pegsz. It will look much nicer if
 968  * (2*PEG_HINT) + PEG_GAP = 1.0 as the hints are formatted like that. */
 969 #define PEG_GAP   0.10
 970 #define PEG_HINT  0.35
 971
 972 #define BORDER    0.5
 973
 974 static void game_compute_size(const game_params *params, int tilesize,
 975                               int *x, int *y)
 976 {
 977     double hmul, vmul_c, vmul_g, vmul;
 978     int hintw = (params->npegs+1)/2;
 979
 980     hmul = BORDER   * 2.0 +               /* border */
 981            1.0      * 2.0 +               /* vertical colour bar */
 982            1.0      * params->npegs +     /* guess pegs */
 983            PEG_GAP  * params->npegs +     /* guess gaps */
 984            PEG_HINT * hintw +             /* hint pegs */
 985            PEG_GAP  * (hintw - 1);        /* hint gaps */
 986
 987     vmul_c = BORDER  * 2.0 +                    /* border */
 988              1.0     * params->ncolours +       /* colour pegs */
 989              PEG_GAP * (params->ncolours - 1);  /* colour gaps */
 990
 991     vmul_g = BORDER  * 2.0 +                    /* border */
 992              1.0     * (params->nguesses + 1) + /* guesses plus solution */
 993              PEG_GAP * (params->nguesses + 1);  /* gaps plus gap above soln */
 994
 995     vmul = max(vmul_c, vmul_g);
 996
 997     *x = (int)ceil((double)tilesize * hmul);
 998     *y = (int)ceil((double)tilesize * vmul);
 999 }
1000
1001 static void game_set_size(drawing *dr, game_drawstate *ds,
1002                           const game_params *params, int tilesize)
1003 {
1004     int colh, guessh;
1005
1006     ds->pegsz = tilesize;
1007
1008     ds->hintsz = (int)((double)ds->pegsz * PEG_HINT);
1009     ds->gapsz  = (int)((double)ds->pegsz * PEG_GAP);
1010     ds->border = (int)((double)ds->pegsz * BORDER);
1011
1012     ds->pegrad  = (ds->pegsz -1)/2; /* radius of peg to fit in pegsz (which is 2r+1) */
1013     ds->hintrad = (ds->hintsz-1)/2;
1014
1015     colh = ((ds->pegsz + ds->gapsz) * params->ncolours) - ds->gapsz;
1016     guessh = ((ds->pegsz + ds->gapsz) * params->nguesses);      /* guesses */
1017     guessh += ds->gapsz + ds->pegsz;                            /* solution */
1018
1019     game_compute_size(params, tilesize, &ds->w, &ds->h);
1020     ds->colx = ds->border;
1021     ds->coly = (ds->h - colh) / 2;
1022
1023     ds->guessx = ds->solnx = ds->border + ds->pegsz * 2;     /* border + colours */
1024     ds->guessy = (ds->h - guessh) / 2;
1025     ds->solny = ds->guessy + ((ds->pegsz + ds->gapsz) * params->nguesses) + ds->gapsz;
1026
1027     assert(ds->pegsz > 0);
1028     assert(!ds->blit_peg);             /* set_size is never called twice */
1029     ds->blit_peg = blitter_new(dr, ds->pegsz+2, ds->pegsz+2);
1030 }
1031
1032 static float *game_colours(frontend *fe, int *ncolours)
1033 {
1034     float *ret = snewn(3 * NCOLOURS, float), max;
1035     int i;
1036
1037     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1038
1039     /* red */
1040     ret[COL_1 * 3 + 0] = 1.0F;
1041     ret[COL_1 * 3 + 1] = 0.0F;
1042     ret[COL_1 * 3 + 2] = 0.0F;
1043
1044     /* yellow */
1045     ret[COL_2 * 3 + 0] = 1.0F;
1046     ret[COL_2 * 3 + 1] = 1.0F;
1047     ret[COL_2 * 3 + 2] = 0.0F;
1048
1049     /* green */
1050     ret[COL_3 * 3 + 0] = 0.0F;
1051     ret[COL_3 * 3 + 1] = 1.0F;
1052     ret[COL_3 * 3 + 2] = 0.0F;
1053
1054     /* blue */
1055     ret[COL_4 * 3 + 0] = 0.2F;
1056     ret[COL_4 * 3 + 1] = 0.3F;
1057     ret[COL_4 * 3 + 2] = 1.0F;
1058
1059     /* orange */
1060     ret[COL_5 * 3 + 0] = 1.0F;
1061     ret[COL_5 * 3 + 1] = 0.5F;
1062     ret[COL_5 * 3 + 2] = 0.0F;
1063
1064     /* purple */
1065     ret[COL_6 * 3 + 0] = 0.5F;
1066     ret[COL_6 * 3 + 1] = 0.0F;
1067     ret[COL_6 * 3 + 2] = 0.7F;
1068
1069     /* brown */
1070     ret[COL_7 * 3 + 0] = 0.5F;
1071     ret[COL_7 * 3 + 1] = 0.3F;
1072     ret[COL_7 * 3 + 2] = 0.3F;
1073
1074     /* light blue */
1075     ret[COL_8 * 3 + 0] = 0.4F;
1076     ret[COL_8 * 3 + 1] = 0.8F;
1077     ret[COL_8 * 3 + 2] = 1.0F;
1078
1079     /* light green */
1080     ret[COL_9 * 3 + 0] = 0.7F;
1081     ret[COL_9 * 3 + 1] = 1.0F;
1082     ret[COL_9 * 3 + 2] = 0.7F;
1083
1084     /* pink */
1085     ret[COL_10 * 3 + 0] = 1.0F;
1086     ret[COL_10 * 3 + 1] = 0.6F;
1087     ret[COL_10 * 3 + 2] = 1.0F;
1088
1089     ret[COL_FRAME * 3 + 0] = 0.0F;
1090     ret[COL_FRAME * 3 + 1] = 0.0F;
1091     ret[COL_FRAME * 3 + 2] = 0.0F;
1092
1093     ret[COL_CURSOR * 3 + 0] = 0.0F;
1094     ret[COL_CURSOR * 3 + 1] = 0.0F;
1095     ret[COL_CURSOR * 3 + 2] = 0.0F;
1096
1097     ret[COL_FLASH * 3 + 0] = 0.5F;
1098     ret[COL_FLASH * 3 + 1] = 1.0F;
1099     ret[COL_FLASH * 3 + 2] = 1.0F;
1100
1101     ret[COL_HOLD * 3 + 0] = 1.0F;
1102     ret[COL_HOLD * 3 + 1] = 0.5F;
1103     ret[COL_HOLD * 3 + 2] = 0.5F;
1104
1105     ret[COL_CORRECTPLACE*3 + 0] = 0.0F;
1106     ret[COL_CORRECTPLACE*3 + 1] = 0.0F;
1107     ret[COL_CORRECTPLACE*3 + 2] = 0.0F;
1108
1109     ret[COL_CORRECTCOLOUR*3 + 0] = 1.0F;
1110     ret[COL_CORRECTCOLOUR*3 + 1] = 1.0F;
1111     ret[COL_CORRECTCOLOUR*3 + 2] = 1.0F;
1112
1113     /* We want to make sure we can distinguish COL_CORRECTCOLOUR
1114      * (which we hard-code as white) from COL_BACKGROUND (which
1115      * could default to white on some platforms).
1116      * Code borrowed from fifteen.c. */
1117     max = ret[COL_BACKGROUND*3];
1118     for (i = 1; i < 3; i++)
1119         if (ret[COL_BACKGROUND*3+i] > max)
1120             max = ret[COL_BACKGROUND*3+i];
1121     if (max * 1.2F > 1.0F) {
1122         for (i = 0; i < 3; i++)
1123             ret[COL_BACKGROUND*3+i] /= (max * 1.2F);
1124     }
1125
1126     /* We also want to be able to tell the difference between BACKGROUND
1127      * and EMPTY, for similar distinguishing-hint reasons. */
1128     ret[COL_EMPTY * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 2.0F / 3.0F;
1129     ret[COL_EMPTY * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 2.0F / 3.0F;
1130     ret[COL_EMPTY * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] * 2.0F / 3.0F;
1131
1132     *ncolours = NCOLOURS;
1133     return ret;
1134 }
1135
1136 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1137 {
1138     struct game_drawstate *ds = snew(struct game_drawstate);
1139     int i;
1140
1141     memset(ds, 0, sizeof(struct game_drawstate));
1142
1143     ds->guesses = snewn(state->params.nguesses, pegrow);
1144     ds->nguesses = state->params.nguesses;
1145     for (i = 0; i < state->params.nguesses; i++) {
1146         ds->guesses[i] = new_pegrow(state->params.npegs);
1147         invalidate_pegrow(ds->guesses[i]);
1148     }
1149     ds->solution = new_pegrow(state->params.npegs);
1150     invalidate_pegrow(ds->solution);
1151     ds->colours = new_pegrow(state->params.ncolours);
1152     invalidate_pegrow(ds->colours);
1153
1154     ds->hintw = (state->params.npegs+1)/2; /* must round up */
1155
1156     ds->blit_peg = NULL;
1157
1158     return ds;
1159 }
1160
1161 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1162 {
1163     int i;
1164
1165     if (ds->blit_peg) blitter_free(dr, ds->blit_peg);
1166     free_pegrow(ds->colours);
1167     free_pegrow(ds->solution);
1168     for (i = 0; i < ds->nguesses; i++)
1169         free_pegrow(ds->guesses[i]);
1170     sfree(ds->guesses);
1171     sfree(ds);
1172 }
1173
1174 static void draw_peg(drawing *dr, game_drawstate *ds, int cx, int cy,
1175                      int moving, int labelled, int col)
1176 {
1177     /*
1178      * Some platforms antialias circles, which means we shouldn't
1179      * overwrite a circle of one colour with a circle of another
1180      * colour without erasing the background first. However, if the
1181      * peg is the one being dragged, we don't erase the background
1182      * because we _want_ it to alpha-blend nicely into whatever's
1183      * behind it.
1184      */
1185     if (!moving)
1186         draw_rect(dr, cx-CGAP, cy-CGAP, PEGSZ+CGAP*2, PEGSZ+CGAP*2,
1187                   COL_BACKGROUND);
1188     if (PEGRAD > 0) {
1189         draw_circle(dr, cx+PEGRAD, cy+PEGRAD, PEGRAD,
1190                     COL_EMPTY + col, (col ? COL_FRAME : COL_EMPTY));
1191     } else
1192         draw_rect(dr, cx, cy, PEGSZ, PEGSZ, COL_EMPTY + col);
1193
1194     if (labelled && col) {
1195         char buf[2];
1196         buf[0] = 'a'-1 + col;
1197         buf[1] = '\0';
1198         draw_text(dr, cx+PEGRAD, cy+PEGRAD, FONT_VARIABLE, PEGRAD,
1199                   ALIGN_HCENTRE|ALIGN_VCENTRE, COL_FRAME, buf);
1200     }
1201
1202     draw_update(dr, cx-CGAP, cy-CGAP, PEGSZ+CGAP*2, PEGSZ+CGAP*2);
1203 }
1204
1205 static void draw_cursor(drawing *dr, game_drawstate *ds, int x, int y)
1206 {
1207     draw_circle(dr, x+PEGRAD, y+PEGRAD, PEGRAD+CGAP, -1, COL_CURSOR);
1208
1209     draw_update(dr, x-CGAP, y-CGAP, PEGSZ+CGAP*2, PEGSZ+CGAP*2);
1210 }
1211
1212 static void guess_redraw(drawing *dr, game_drawstate *ds, int guess,
1213                          pegrow src, int *holds, int cur_col, int force,
1214                          int labelled)
1215 {
1216     pegrow dest;
1217     int rowx, rowy, i, scol;
1218
1219     if (guess == -1) {
1220         dest = ds->solution;
1221         rowx = SOLN_OX;
1222         rowy = SOLN_OY;
1223     } else {
1224         dest = ds->guesses[guess];
1225         rowx = GUESS_X(guess,0);
1226         rowy = GUESS_Y(guess,0);
1227     }
1228     if (src) assert(src->npegs == dest->npegs);
1229
1230     for (i = 0; i < dest->npegs; i++) {
1231         scol = src ? src->pegs[i] : 0;
1232         if (i == cur_col)
1233             scol |= 0x1000;
1234         if (holds && holds[i])
1235             scol |= 0x2000;
1236         if (labelled)
1237             scol |= 0x4000;
1238         if ((dest->pegs[i] != scol) || force) {
1239             draw_peg(dr, ds, rowx + PEGOFF * i, rowy, FALSE, labelled,
1240                      scol &~ 0x7000);
1241             /*
1242              * Hold marker.
1243              */
1244             draw_rect(dr, rowx + PEGOFF * i, rowy + PEGSZ + ds->gapsz/2,
1245                       PEGSZ, 2, (scol & 0x2000 ? COL_HOLD : COL_BACKGROUND));
1246             draw_update(dr, rowx + PEGOFF * i, rowy + PEGSZ + ds->gapsz/2,
1247                         PEGSZ, 2);
1248             if (scol & 0x1000)
1249                 draw_cursor(dr, ds, rowx + PEGOFF * i, rowy);
1250         }
1251         dest->pegs[i] = scol;
1252     }
1253 }
1254
1255 static void hint_redraw(drawing *dr, game_drawstate *ds, int guess,
1256                         pegrow src, int force, int cursor, int markable)
1257 {
1258     pegrow dest = ds->guesses[guess];
1259     int rowx, rowy, i, scol, col, hintlen;
1260     int need_redraw;
1261     int emptycol = (markable ? COL_FLASH : COL_EMPTY);
1262
1263     if (src) assert(src->npegs == dest->npegs);
1264
1265     hintlen = (dest->npegs + 1)/2;
1266
1267     /*
1268      * Because of the possible presence of the cursor around this
1269      * entire section, we redraw all or none of it but never part.
1270      */
1271     need_redraw = FALSE;
1272
1273     for (i = 0; i < dest->npegs; i++) {
1274         scol = src ? src->feedback[i] : 0;
1275         if (i == 0 && cursor)
1276             scol |= 0x1000;
1277         if (i == 0 && markable)
1278             scol |= 0x2000;
1279         if ((scol != dest->feedback[i]) || force) {
1280             need_redraw = TRUE;
1281         }
1282         dest->feedback[i] = scol;
1283     }
1284
1285     if (need_redraw) {
1286         int hinth = HINTSZ + GAP + HINTSZ;
1287         int hx,hy,hw,hh;
1288
1289         hx = HINT_X(guess)-GAP; hy = HINT_Y(guess)-GAP;
1290         hw = HINT_W+GAP*2; hh = hinth+GAP*2;
1291
1292         /* erase a large background rectangle */
1293         draw_rect(dr, hx, hy, hw, hh, COL_BACKGROUND);
1294
1295         for (i = 0; i < dest->npegs; i++) {
1296             scol = src ? src->feedback[i] : 0;
1297             col = ((scol == FEEDBACK_CORRECTPLACE) ? COL_CORRECTPLACE :
1298                    (scol == FEEDBACK_CORRECTCOLOUR) ? COL_CORRECTCOLOUR :
1299                    emptycol);
1300
1301             rowx = HINT_X(guess);
1302             rowy = HINT_Y(guess);
1303             if (i < hintlen) {
1304                 rowx += HINTOFF * i;
1305             } else {
1306                 rowx += HINTOFF * (i - hintlen);
1307                 rowy += HINTOFF;
1308             }
1309             if (HINTRAD > 0) {
1310                 draw_circle(dr, rowx+HINTRAD, rowy+HINTRAD, HINTRAD, col,
1311                             (col == emptycol ? emptycol : COL_FRAME));
1312             } else {
1313                 draw_rect(dr, rowx, rowy, HINTSZ, HINTSZ, col);
1314             }
1315         }
1316         if (cursor) {
1317             int x1,y1,x2,y2;
1318             x1 = hx + CGAP; y1 = hy + CGAP;
1319             x2 = hx + hw - CGAP; y2 = hy + hh - CGAP;
1320             draw_line(dr, x1, y1, x2, y1, COL_CURSOR);
1321             draw_line(dr, x2, y1, x2, y2, COL_CURSOR);
1322             draw_line(dr, x2, y2, x1, y2, COL_CURSOR);
1323             draw_line(dr, x1, y2, x1, y1, COL_CURSOR);
1324         }
1325
1326         draw_update(dr, hx, hy, hw, hh);
1327     }
1328 }
1329
1330 static void currmove_redraw(drawing *dr, game_drawstate *ds, int guess, int col)
1331 {
1332     int ox = GUESS_X(guess, 0), oy = GUESS_Y(guess, 0), off = PEGSZ/4;
1333
1334     draw_rect(dr, ox-off-1, oy, 2, PEGSZ, col);
1335     draw_update(dr, ox-off-1, oy, 2, PEGSZ);
1336 }
1337
1338 static void game_redraw(drawing *dr, game_drawstate *ds,
1339                         const game_state *oldstate, const game_state *state,
1340                         int dir, const game_ui *ui,
1341                         float animtime, float flashtime)
1342 {
1343     int i, new_move;
1344
1345     new_move = (state->next_go != ds->next_go) || !ds->started;
1346
1347     if (!ds->started) {
1348       draw_rect(dr, 0, 0, ds->w, ds->h, COL_BACKGROUND);
1349       draw_rect(dr, SOLN_OX, SOLN_OY - ds->gapsz - 1, SOLN_W, 2, COL_FRAME);
1350       draw_update(dr, 0, 0, ds->w, ds->h);
1351     }
1352
1353     if (ds->drag_col != 0) {
1354         debug(("Loading from blitter."));
1355         blitter_load(dr, ds->blit_peg, ds->blit_ox, ds->blit_oy);
1356         draw_update(dr, ds->blit_ox, ds->blit_oy, PEGSZ, PEGSZ);
1357     }
1358
1359     /* draw the colours */
1360     for (i = 0; i < state->params.ncolours; i++) {
1361         int val = i+1;
1362         if (ui->display_cur && ui->colour_cur == i)
1363             val |= 0x1000;
1364         if (ui->show_labels)
1365             val |= 0x2000;
1366         if (ds->colours->pegs[i] != val) {
1367             draw_peg(dr, ds, COL_X(i), COL_Y(i), FALSE, ui->show_labels, i+1);
1368             if (val & 0x1000)
1369                 draw_cursor(dr, ds, COL_X(i), COL_Y(i));
1370             ds->colours->pegs[i] = val;
1371         }
1372     }
1373
1374     /* draw the guesses (so far) and the hints
1375      * (in reverse order to avoid trampling holds, and postponing the
1376      * next_go'th to not overrender the top of the circular cursor) */
1377     for (i = state->params.nguesses - 1; i >= 0; i--) {
1378         if (i < state->next_go || state->solved) {
1379             /* this info is stored in the game_state already */
1380             guess_redraw(dr, ds, i, state->guesses[i], NULL, -1, 0,
1381                          ui->show_labels);
1382             hint_redraw(dr, ds, i, state->guesses[i],
1383                         i == (state->next_go-1) ? 1 : 0, FALSE, FALSE);
1384         } else if (i > state->next_go) {
1385             /* we've not got here yet; it's blank. */
1386             guess_redraw(dr, ds, i, NULL, NULL, -1, 0, ui->show_labels);
1387             hint_redraw(dr, ds, i, NULL, 0, FALSE, FALSE);
1388         }
1389     }
1390     if (!state->solved) {
1391         /* this is the one we're on; the (incomplete) guess is stored in
1392          * the game_ui. */
1393         guess_redraw(dr, ds, state->next_go, ui->curr_pegs,
1394                      ui->holds, ui->display_cur ? ui->peg_cur : -1, 0,
1395                      ui->show_labels);
1396         hint_redraw(dr, ds, state->next_go, NULL, 1,
1397                     ui->display_cur && ui->peg_cur == state->params.npegs,
1398                     ui->markable);
1399     }
1400
1401     /* draw the 'current move' and 'able to mark' sign. */
1402     if (new_move)
1403         currmove_redraw(dr, ds, ds->next_go, COL_BACKGROUND);
1404     if (!state->solved)
1405         currmove_redraw(dr, ds, state->next_go, COL_HOLD);
1406
1407     /* draw the solution (or the big rectangle) */
1408     if ((!state->solved ^ !ds->solved) || !ds->started) {
1409         draw_rect(dr, SOLN_OX, SOLN_OY, SOLN_W, SOLN_H,
1410                   state->solved ? COL_BACKGROUND : COL_EMPTY);
1411         draw_update(dr, SOLN_OX, SOLN_OY, SOLN_W, SOLN_H);
1412     }
1413     if (state->solved)
1414         guess_redraw(dr, ds, -1, state->solution, NULL, -1, !ds->solved,
1415                      ui->show_labels);
1416     ds->solved = state->solved;
1417
1418     ds->next_go = state->next_go;
1419
1420     /* if ui->drag_col != 0, save the screen to the blitter,
1421      * draw the peg where we saved, and set ds->drag_* == ui->drag_*. */
1422     if (ui->drag_col != 0) {
1423         int ox = ui->drag_x - (PEGSZ/2);
1424         int oy = ui->drag_y - (PEGSZ/2);
1425         ds->blit_ox = ox - 1; ds->blit_oy = oy - 1;
1426         debug(("Saving to blitter at (%d,%d)", ds->blit_ox, ds->blit_oy));
1427         blitter_save(dr, ds->blit_peg, ds->blit_ox, ds->blit_oy);
1428         draw_peg(dr, ds, ox, oy, TRUE, ui->show_labels, ui->drag_col);
1429     }
1430     ds->drag_col = ui->drag_col;
1431
1432     ds->started = 1;
1433 }
1434
1435 static float game_anim_length(const game_state *oldstate,
1436                               const game_state *newstate, int dir, game_ui *ui)
1437 {
1438     return 0.0F;
1439 }
1440
1441 static float game_flash_length(const game_state *oldstate,
1442                                const game_state *newstate, int dir, game_ui *ui)
1443 {
1444     return 0.0F;
1445 }
1446
1447 static int game_status(const game_state *state)
1448 {
1449     /*
1450      * We return nonzero whenever the solution has been revealed, even
1451      * (on spoiler grounds) if it wasn't guessed correctly. The
1452      * correct return value from this function is already in
1453      * state->solved.
1454      */
1455     return state->solved;
1456 }
1457
1458 static int game_timing_state(const game_state *state, game_ui *ui)
1459 {
1460     return TRUE;
1461 }
1462
1463 static void game_print_size(const game_params *params, float *x, float *y)
1464 {
1465 }
1466
1467 static void game_print(drawing *dr, const game_state *state, int tilesize)
1468 {
1469 }
1470
1471 #ifdef COMBINED
1472 #define thegame guess
1473 #endif
1474
1475 const struct game thegame = {
1476     "Guess", "games.guess", "guess",
1477     default_params,
1478     game_fetch_preset, NULL,
1479     decode_params,
1480     encode_params,
1481     free_params,
1482     dup_params,
1483     TRUE, game_configure, custom_params,
1484     validate_params,
1485     new_game_desc,
1486     validate_desc,
1487     new_game,
1488     dup_game,
1489     free_game,
1490     TRUE, solve_game,
1491     FALSE, game_can_format_as_text_now, game_text_format,
1492     new_ui,
1493     free_ui,
1494     encode_ui,
1495     decode_ui,
1496     game_changed_state,
1497     interpret_move,
1498     execute_move,
1499     PEG_PREFER_SZ, game_compute_size, game_set_size,
1500     game_colours,
1501     game_new_drawstate,
1502     game_free_drawstate,
1503     game_redraw,
1504     game_anim_length,
1505     game_flash_length,
1506     game_status,
1507     FALSE, FALSE, game_print_size, game_print,
1508     FALSE,                             /* wants_statusbar */
1509     FALSE, game_timing_state,
1510     0,                                 /* flags */
1511 };
1512
1513 /* vim: set shiftwidth=4 tabstop=8: */