| 1 | /* |
| 2 | * galaxies.c: implementation of 'Tentai Show' from Nikoli, |
| 3 | * also sometimes called 'Spiral Galaxies'. |
| 4 | * |
| 5 | * Notes: |
| 6 | * |
| 7 | * Grid is stored as size (2n-1), holding edges as well as spaces |
| 8 | * (and thus vertices too, at edge intersections). |
| 9 | * |
| 10 | * Any dot will thus be positioned at one of our grid points, |
| 11 | * which saves any faffing with half-of-a-square stuff. |
| 12 | * |
| 13 | * Edges have on/off state; obviously the actual edges of the |
| 14 | * board are fixed to on, and everything else starts as off. |
| 15 | * |
| 16 | * TTD: |
| 17 | * Cleverer solver |
| 18 | * Think about how to display remote groups of tiles? |
| 19 | * |
| 20 | * Bugs: |
| 21 | * |
| 22 | * Notable puzzle IDs: |
| 23 | * |
| 24 | * Nikoli's example [web site has wrong highlighting] |
| 25 | * (at http://www.nikoli.co.jp/en/puzzles/astronomical_show/): |
| 26 | * 5x5:eBbbMlaBbOEnf |
| 27 | * |
| 28 | * The 'spiral galaxies puzzles are NP-complete' paper |
| 29 | * (at http://www.stetson.edu/~efriedma/papers/spiral.pdf): |
| 30 | * 7x7:chpgdqqqoezdddki |
| 31 | * |
| 32 | * Puzzle competition pdf examples |
| 33 | * (at http://www.puzzleratings.org/Yurekli2006puz.pdf): |
| 34 | * 6x6:EDbaMucCohbrecEi |
| 35 | * 10x10:beFbufEEzowDlxldibMHezBQzCdcFzjlci |
| 36 | * 13x13:dCemIHFFkJajjgDfdbdBzdzEgjccoPOcztHjBczLDjczqktJjmpreivvNcggFi |
| 37 | * |
| 38 | */ |
| 39 | |
| 40 | #include <stdio.h> |
| 41 | #include <stdlib.h> |
| 42 | #include <string.h> |
| 43 | #include <assert.h> |
| 44 | #include <ctype.h> |
| 45 | #include <math.h> |
| 46 | |
| 47 | #include "puzzles.h" |
| 48 | |
| 49 | #ifdef DEBUGGING |
| 50 | #define solvep debug |
| 51 | #else |
| 52 | int solver_show_working; |
| 53 | #define solvep(x) do { if (solver_show_working) { printf x; } } while(0) |
| 54 | #endif |
| 55 | |
| 56 | enum { |
| 57 | COL_BACKGROUND, |
| 58 | COL_WHITEBG, |
| 59 | COL_BLACKBG, |
| 60 | COL_WHITEDOT, |
| 61 | COL_BLACKDOT, |
| 62 | COL_GRID, |
| 63 | COL_EDGE, |
| 64 | COL_ARROW, |
| 65 | NCOLOURS |
| 66 | }; |
| 67 | |
| 68 | #define DIFFLIST(A) \ |
| 69 | A(NORMAL,Normal,n) \ |
| 70 | A(UNREASONABLE,Unreasonable,u) |
| 71 | |
| 72 | #define ENUM(upper,title,lower) DIFF_ ## upper, |
| 73 | #define TITLE(upper,title,lower) #title, |
| 74 | #define ENCODE(upper,title,lower) #lower |
| 75 | #define CONFIG(upper,title,lower) ":" #title |
| 76 | enum { DIFFLIST(ENUM) |
| 77 | DIFF_IMPOSSIBLE, DIFF_AMBIGUOUS, DIFF_UNFINISHED, DIFF_MAX }; |
| 78 | static char const *const galaxies_diffnames[] = { |
| 79 | DIFFLIST(TITLE) "Impossible", "Ambiguous", "Unfinished" }; |
| 80 | static char const galaxies_diffchars[] = DIFFLIST(ENCODE); |
| 81 | #define DIFFCONFIG DIFFLIST(CONFIG) |
| 82 | |
| 83 | struct game_params { |
| 84 | /* X and Y is the area of the board as seen by |
| 85 | * the user, not the (2n+1) area the game uses. */ |
| 86 | int w, h, diff; |
| 87 | }; |
| 88 | |
| 89 | enum { s_tile, s_edge, s_vertex }; |
| 90 | |
| 91 | #define F_DOT 1 /* there's a dot here */ |
| 92 | #define F_EDGE_SET 2 /* the edge is set */ |
| 93 | #define F_TILE_ASSOC 4 /* this tile is associated with a dot. */ |
| 94 | #define F_DOT_BLACK 8 /* (ui only) dot is black. */ |
| 95 | #define F_MARK 16 /* scratch flag */ |
| 96 | #define F_REACHABLE 32 |
| 97 | #define F_SCRATCH 64 |
| 98 | #define F_MULTIPLE 128 |
| 99 | #define F_DOT_HOLD 256 |
| 100 | #define F_GOOD 512 |
| 101 | |
| 102 | typedef struct space { |
| 103 | int x, y; /* its position */ |
| 104 | int type; |
| 105 | unsigned int flags; |
| 106 | int dotx, doty; /* if flags & F_TILE_ASSOC */ |
| 107 | int nassoc; /* if flags & F_DOT */ |
| 108 | } space; |
| 109 | |
| 110 | #define INGRID(s,x,y) ((x) >= 0 && (y) >= 0 && \ |
| 111 | (x) < (state)->sx && (y) < (state)->sy) |
| 112 | #define INUI(s,x,y) ((x) > 0 && (y) > 0 && \ |
| 113 | (x) < ((state)->sx-1) && (y) < ((state)->sy-1)) |
| 114 | |
| 115 | #define GRID(s,g,x,y) ((s)->g[((y)*(s)->sx)+(x)]) |
| 116 | #define SPACE(s,x,y) GRID(s,grid,x,y) |
| 117 | |
| 118 | struct game_state { |
| 119 | int w, h; /* size from params */ |
| 120 | int sx, sy; /* allocated size, (2x-1)*(2y-1) */ |
| 121 | space *grid; |
| 122 | int completed, used_solve; |
| 123 | int ndots; |
| 124 | space **dots; |
| 125 | |
| 126 | midend *me; /* to call supersede_game_desc */ |
| 127 | int cdiff; /* difficulty of current puzzle (for status bar), |
| 128 | or -1 if stale. */ |
| 129 | }; |
| 130 | |
| 131 | /* ---------------------------------------------------------- |
| 132 | * Game parameters and presets |
| 133 | */ |
| 134 | |
| 135 | /* make up some sensible default sizes */ |
| 136 | |
| 137 | #define DEFAULT_PRESET 0 |
| 138 | |
| 139 | static const game_params galaxies_presets[] = { |
| 140 | { 7, 7, DIFF_NORMAL }, |
| 141 | { 7, 7, DIFF_UNREASONABLE }, |
| 142 | { 10, 10, DIFF_NORMAL }, |
| 143 | { 15, 15, DIFF_NORMAL }, |
| 144 | }; |
| 145 | |
| 146 | static int game_fetch_preset(int i, char **name, game_params **params) |
| 147 | { |
| 148 | game_params *ret; |
| 149 | char buf[80]; |
| 150 | |
| 151 | if (i < 0 || i >= lenof(galaxies_presets)) |
| 152 | return FALSE; |
| 153 | |
| 154 | ret = snew(game_params); |
| 155 | *ret = galaxies_presets[i]; /* structure copy */ |
| 156 | |
| 157 | sprintf(buf, "%dx%d %s", ret->w, ret->h, |
| 158 | galaxies_diffnames[ret->diff]); |
| 159 | |
| 160 | if (name) *name = dupstr(buf); |
| 161 | *params = ret; |
| 162 | return TRUE; |
| 163 | } |
| 164 | |
| 165 | static game_params *default_params(void) |
| 166 | { |
| 167 | game_params *ret; |
| 168 | game_fetch_preset(DEFAULT_PRESET, NULL, &ret); |
| 169 | return ret; |
| 170 | } |
| 171 | |
| 172 | static void free_params(game_params *params) |
| 173 | { |
| 174 | sfree(params); |
| 175 | } |
| 176 | |
| 177 | static game_params *dup_params(game_params *params) |
| 178 | { |
| 179 | game_params *ret = snew(game_params); |
| 180 | *ret = *params; /* structure copy */ |
| 181 | return ret; |
| 182 | } |
| 183 | |
| 184 | static void decode_params(game_params *params, char const *string) |
| 185 | { |
| 186 | params->h = params->w = atoi(string); |
| 187 | params->diff = DIFF_NORMAL; |
| 188 | while (*string && isdigit((unsigned char)*string)) string++; |
| 189 | if (*string == 'x') { |
| 190 | string++; |
| 191 | params->h = atoi(string); |
| 192 | while (*string && isdigit((unsigned char)*string)) string++; |
| 193 | } |
| 194 | if (*string == 'd') { |
| 195 | int i; |
| 196 | string++; |
| 197 | for (i = 0; i <= DIFF_UNREASONABLE; i++) |
| 198 | if (*string == galaxies_diffchars[i]) |
| 199 | params->diff = i; |
| 200 | if (*string) string++; |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | static char *encode_params(game_params *params, int full) |
| 205 | { |
| 206 | char str[80]; |
| 207 | sprintf(str, "%dx%d", params->w, params->h); |
| 208 | if (full) |
| 209 | sprintf(str + strlen(str), "d%c", galaxies_diffchars[params->diff]); |
| 210 | return dupstr(str); |
| 211 | } |
| 212 | |
| 213 | static config_item *game_configure(game_params *params) |
| 214 | { |
| 215 | config_item *ret; |
| 216 | char buf[80]; |
| 217 | |
| 218 | ret = snewn(4, config_item); |
| 219 | |
| 220 | ret[0].name = "Width"; |
| 221 | ret[0].type = C_STRING; |
| 222 | sprintf(buf, "%d", params->w); |
| 223 | ret[0].sval = dupstr(buf); |
| 224 | ret[0].ival = 0; |
| 225 | |
| 226 | ret[1].name = "Height"; |
| 227 | ret[1].type = C_STRING; |
| 228 | sprintf(buf, "%d", params->h); |
| 229 | ret[1].sval = dupstr(buf); |
| 230 | ret[1].ival = 0; |
| 231 | |
| 232 | ret[2].name = "Difficulty"; |
| 233 | ret[2].type = C_CHOICES; |
| 234 | ret[2].sval = DIFFCONFIG; |
| 235 | ret[2].ival = params->diff; |
| 236 | |
| 237 | ret[3].name = NULL; |
| 238 | ret[3].type = C_END; |
| 239 | ret[3].sval = NULL; |
| 240 | ret[3].ival = 0; |
| 241 | |
| 242 | return ret; |
| 243 | } |
| 244 | |
| 245 | static game_params *custom_params(config_item *cfg) |
| 246 | { |
| 247 | game_params *ret = snew(game_params); |
| 248 | |
| 249 | ret->w = atoi(cfg[0].sval); |
| 250 | ret->h = atoi(cfg[1].sval); |
| 251 | ret->diff = cfg[2].ival; |
| 252 | |
| 253 | return ret; |
| 254 | } |
| 255 | |
| 256 | static char *validate_params(game_params *params, int full) |
| 257 | { |
| 258 | if (params->w < 3 || params->h < 3) |
| 259 | return "Width and height must both be at least 3"; |
| 260 | /* |
| 261 | * This shouldn't be able to happen at all, since decode_params |
| 262 | * and custom_params will never generate anything that isn't |
| 263 | * within range. |
| 264 | */ |
| 265 | assert(params->diff <= DIFF_UNREASONABLE); |
| 266 | |
| 267 | return NULL; |
| 268 | } |
| 269 | |
| 270 | /* ---------------------------------------------------------- |
| 271 | * Game utility functions. |
| 272 | */ |
| 273 | |
| 274 | static void add_dot(space *space) { |
| 275 | assert(!(space->flags & F_DOT)); |
| 276 | space->flags |= F_DOT; |
| 277 | space->nassoc = 0; |
| 278 | } |
| 279 | |
| 280 | static void remove_dot(space *space) { |
| 281 | assert(space->flags & F_DOT); |
| 282 | space->flags &= ~F_DOT; |
| 283 | } |
| 284 | |
| 285 | static void remove_assoc(game_state *state, space *tile) { |
| 286 | if (tile->flags & F_TILE_ASSOC) { |
| 287 | SPACE(state, tile->dotx, tile->doty).nassoc--; |
| 288 | tile->flags &= ~F_TILE_ASSOC; |
| 289 | tile->dotx = -1; |
| 290 | tile->doty = -1; |
| 291 | } |
| 292 | } |
| 293 | |
| 294 | static void add_assoc(game_state *state, space *tile, space *dot) { |
| 295 | remove_assoc(state, tile); |
| 296 | |
| 297 | tile->flags |= F_TILE_ASSOC; |
| 298 | tile->dotx = dot->x; |
| 299 | tile->doty = dot->y; |
| 300 | dot->nassoc++; |
| 301 | /*debug(("add_assoc sp %d %d --> dot %d,%d, new nassoc %d.\n", |
| 302 | tile->x, tile->y, dot->x, dot->y, dot->nassoc));*/ |
| 303 | } |
| 304 | |
| 305 | static struct space *sp2dot(game_state *state, int x, int y) |
| 306 | { |
| 307 | struct space *sp = &SPACE(state, x, y); |
| 308 | if (!(sp->flags & F_TILE_ASSOC)) return NULL; |
| 309 | return &SPACE(state, sp->dotx, sp->doty); |
| 310 | } |
| 311 | |
| 312 | #define IS_VERTICAL_EDGE(x) ((x % 2) == 0) |
| 313 | |
| 314 | static char *game_text_format(game_state *state) |
| 315 | { |
| 316 | int maxlen = (state->sx+1)*state->sy, x, y; |
| 317 | char *ret, *p; |
| 318 | space *sp; |
| 319 | |
| 320 | ret = snewn(maxlen+1, char); |
| 321 | p = ret; |
| 322 | |
| 323 | for (y = 0; y < state->sy; y++) { |
| 324 | for (x = 0; x < state->sx; x++) { |
| 325 | sp = &SPACE(state, x, y); |
| 326 | if (sp->flags & F_DOT) |
| 327 | *p++ = 'o'; |
| 328 | else if (sp->flags & (F_REACHABLE|F_MULTIPLE|F_MARK)) |
| 329 | *p++ = (sp->flags & F_MULTIPLE) ? 'M' : |
| 330 | (sp->flags & F_REACHABLE) ? 'R' : 'X'; |
| 331 | else { |
| 332 | switch (sp->type) { |
| 333 | case s_tile: |
| 334 | if (sp->flags & F_TILE_ASSOC) { |
| 335 | space *dot = sp2dot(state, sp->x, sp->y); |
| 336 | if (dot->flags & F_DOT) |
| 337 | *p++ = (dot->flags & F_DOT_BLACK) ? 'B' : 'W'; |
| 338 | else |
| 339 | *p++ = '?'; /* association with not-a-dot. */ |
| 340 | } else |
| 341 | *p++ = ' '; |
| 342 | break; |
| 343 | |
| 344 | case s_vertex: |
| 345 | *p++ = '+'; |
| 346 | break; |
| 347 | |
| 348 | case s_edge: |
| 349 | if (sp->flags & F_EDGE_SET) |
| 350 | *p++ = (IS_VERTICAL_EDGE(x)) ? '|' : '-'; |
| 351 | else |
| 352 | *p++ = ' '; |
| 353 | break; |
| 354 | |
| 355 | default: |
| 356 | assert(!"shouldn't get here!"); |
| 357 | } |
| 358 | } |
| 359 | } |
| 360 | *p++ = '\n'; |
| 361 | } |
| 362 | |
| 363 | assert(p - ret == maxlen); |
| 364 | *p = '\0'; |
| 365 | |
| 366 | return ret; |
| 367 | } |
| 368 | |
| 369 | static void dbg_state(game_state *state) |
| 370 | { |
| 371 | #ifdef DEBUGGING |
| 372 | char *temp = game_text_format(state); |
| 373 | debug(("%s\n", temp)); |
| 374 | sfree(temp); |
| 375 | #endif |
| 376 | } |
| 377 | |
| 378 | /* Space-enumeration callbacks should all return 1 for 'progress made', |
| 379 | * -1 for 'impossible', and 0 otherwise. */ |
| 380 | typedef int (*space_cb)(game_state *state, space *sp, void *ctx); |
| 381 | |
| 382 | #define IMPOSSIBLE_QUITS 1 |
| 383 | |
| 384 | static int foreach_sub(game_state *state, space_cb cb, unsigned int f, |
| 385 | void *ctx, int startx, int starty) |
| 386 | { |
| 387 | int x, y, progress = 0, impossible = 0, ret; |
| 388 | space *sp; |
| 389 | |
| 390 | for (y = starty; y < state->sy; y += 2) { |
| 391 | sp = &SPACE(state, startx, y); |
| 392 | for (x = startx; x < state->sx; x += 2) { |
| 393 | ret = cb(state, sp, ctx); |
| 394 | if (ret == -1) { |
| 395 | if (f & IMPOSSIBLE_QUITS) return -1; |
| 396 | impossible = -1; |
| 397 | } else if (ret == 1) { |
| 398 | progress = 1; |
| 399 | } |
| 400 | sp += 2; |
| 401 | } |
| 402 | } |
| 403 | return impossible ? -1 : progress; |
| 404 | } |
| 405 | |
| 406 | static int foreach_tile(game_state *state, space_cb cb, unsigned int f, |
| 407 | void *ctx) |
| 408 | { |
| 409 | return foreach_sub(state, cb, f, ctx, 1, 1); |
| 410 | } |
| 411 | |
| 412 | static int foreach_edge(game_state *state, space_cb cb, unsigned int f, |
| 413 | void *ctx) |
| 414 | { |
| 415 | int ret1, ret2; |
| 416 | |
| 417 | ret1 = foreach_sub(state, cb, f, ctx, 0, 1); |
| 418 | ret2 = foreach_sub(state, cb, f, ctx, 1, 0); |
| 419 | |
| 420 | if (ret1 == -1 || ret2 == -1) return -1; |
| 421 | return (ret1 || ret2) ? 1 : 0; |
| 422 | } |
| 423 | |
| 424 | #if 0 |
| 425 | static int foreach_vertex(game_state *state, space_cb cb, unsigned int f, |
| 426 | void *ctx) |
| 427 | { |
| 428 | return foreach_sub(state, cb, f, ctx, 0, 0); |
| 429 | } |
| 430 | #endif |
| 431 | |
| 432 | #if 0 |
| 433 | static int is_same_assoc(game_state *state, |
| 434 | int x1, int y1, int x2, int y2) |
| 435 | { |
| 436 | struct space *s1, *s2; |
| 437 | |
| 438 | if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2)) |
| 439 | return 0; |
| 440 | |
| 441 | s1 = &SPACE(state, x1, y1); |
| 442 | s2 = &SPACE(state, x2, y2); |
| 443 | assert(s1->type == s_tile && s2->type == s_tile); |
| 444 | if ((s1->flags & F_TILE_ASSOC) && (s2->flags & F_TILE_ASSOC) && |
| 445 | s1->dotx == s2->dotx && s1->doty == s2->doty) |
| 446 | return 1; |
| 447 | return 0; /* 0 if not same or not both associated. */ |
| 448 | } |
| 449 | #endif |
| 450 | |
| 451 | #if 0 |
| 452 | static int edges_into_vertex(game_state *state, |
| 453 | int x, int y) |
| 454 | { |
| 455 | int dx, dy, nx, ny, count = 0; |
| 456 | |
| 457 | assert(SPACE(state, x, y).type == s_vertex); |
| 458 | for (dx = -1; dx <= 1; dx++) { |
| 459 | for (dy = -1; dy <= 1; dy++) { |
| 460 | if (dx != 0 && dy != 0) continue; |
| 461 | if (dx == 0 && dy == 0) continue; |
| 462 | |
| 463 | nx = x+dx; ny = y+dy; |
| 464 | if (!INGRID(state, nx, ny)) continue; |
| 465 | assert(SPACE(state, nx, ny).type == s_edge); |
| 466 | if (SPACE(state, nx, ny).flags & F_EDGE_SET) |
| 467 | count++; |
| 468 | } |
| 469 | } |
| 470 | return count; |
| 471 | } |
| 472 | #endif |
| 473 | |
| 474 | static struct space *space_opposite_dot(struct game_state *state, |
| 475 | struct space *sp, struct space *dot) |
| 476 | { |
| 477 | int dx, dy, tx, ty; |
| 478 | space *sp2; |
| 479 | |
| 480 | dx = sp->x - dot->x; |
| 481 | dy = sp->y - dot->y; |
| 482 | tx = dot->x - dx; |
| 483 | ty = dot->y - dy; |
| 484 | if (!INGRID(state, tx, ty)) return NULL; |
| 485 | |
| 486 | sp2 = &SPACE(state, tx, ty); |
| 487 | assert(sp2->type == sp->type); |
| 488 | return sp2; |
| 489 | } |
| 490 | |
| 491 | static struct space *tile_opposite(struct game_state *state, struct space *sp) |
| 492 | { |
| 493 | struct space *dot; |
| 494 | |
| 495 | assert(sp->flags & F_TILE_ASSOC); |
| 496 | dot = &SPACE(state, sp->dotx, sp->doty); |
| 497 | return space_opposite_dot(state, sp, dot); |
| 498 | } |
| 499 | |
| 500 | static int dotfortile(game_state *state, space *tile, space *dot) |
| 501 | { |
| 502 | space *tile_opp = space_opposite_dot(state, tile, dot); |
| 503 | |
| 504 | if (!tile_opp) return 0; /* opposite would be off grid */ |
| 505 | if (tile_opp->flags & F_TILE_ASSOC && |
| 506 | (tile_opp->dotx != dot->x || tile_opp->doty != dot->y)) |
| 507 | return 0; /* opposite already associated with diff. dot */ |
| 508 | return 1; |
| 509 | } |
| 510 | |
| 511 | static void adjacencies(struct game_state *state, struct space *sp, |
| 512 | struct space **a1s, struct space **a2s) |
| 513 | { |
| 514 | int dxs[4] = {-1, 1, 0, 0}, dys[4] = {0, 0, -1, 1}; |
| 515 | int n, x, y; |
| 516 | |
| 517 | /* this function needs optimising. */ |
| 518 | |
| 519 | for (n = 0; n < 4; n++) { |
| 520 | x = sp->x+dxs[n]; |
| 521 | y = sp->y+dys[n]; |
| 522 | |
| 523 | if (INGRID(state, x, y)) { |
| 524 | a1s[n] = &SPACE(state, x, y); |
| 525 | |
| 526 | x += dxs[n]; y += dys[n]; |
| 527 | |
| 528 | if (INGRID(state, x, y)) |
| 529 | a2s[n] = &SPACE(state, x, y); |
| 530 | else |
| 531 | a2s[n] = NULL; |
| 532 | } else { |
| 533 | a1s[n] = a2s[n] = NULL; |
| 534 | } |
| 535 | } |
| 536 | } |
| 537 | |
| 538 | static int outline_tile_fordot(game_state *state, space *tile, int mark) |
| 539 | { |
| 540 | struct space *tadj[4], *eadj[4]; |
| 541 | int i, didsth = 0, edge, same; |
| 542 | |
| 543 | assert(tile->type == s_tile); |
| 544 | adjacencies(state, tile, eadj, tadj); |
| 545 | for (i = 0; i < 4; i++) { |
| 546 | if (!eadj[i]) continue; |
| 547 | |
| 548 | edge = (eadj[i]->flags & F_EDGE_SET) ? 1 : 0; |
| 549 | if (tadj[i]) { |
| 550 | if (!(tile->flags & F_TILE_ASSOC)) |
| 551 | same = (tadj[i]->flags & F_TILE_ASSOC) ? 0 : 1; |
| 552 | else |
| 553 | same = ((tadj[i]->flags & F_TILE_ASSOC) && |
| 554 | tile->dotx == tadj[i]->dotx && |
| 555 | tile->doty == tadj[i]->doty) ? 1 : 0; |
| 556 | } else |
| 557 | same = 0; |
| 558 | |
| 559 | if (!edge && !same) { |
| 560 | if (mark) eadj[i]->flags |= F_EDGE_SET; |
| 561 | didsth = 1; |
| 562 | } else if (edge && same) { |
| 563 | if (mark) eadj[i]->flags &= ~F_EDGE_SET; |
| 564 | didsth = 1; |
| 565 | } |
| 566 | } |
| 567 | return didsth; |
| 568 | } |
| 569 | |
| 570 | static void tiles_from_edge(struct game_state *state, |
| 571 | struct space *sp, struct space **ts) |
| 572 | { |
| 573 | int xs[2], ys[2]; |
| 574 | |
| 575 | if (IS_VERTICAL_EDGE(sp->x)) { |
| 576 | xs[0] = sp->x-1; ys[0] = sp->y; |
| 577 | xs[1] = sp->x+1; ys[1] = sp->y; |
| 578 | } else { |
| 579 | xs[0] = sp->x; ys[0] = sp->y-1; |
| 580 | xs[1] = sp->x; ys[1] = sp->y+1; |
| 581 | } |
| 582 | ts[0] = INGRID(state, xs[0], ys[0]) ? &SPACE(state, xs[0], ys[0]) : NULL; |
| 583 | ts[1] = INGRID(state, xs[1], ys[1]) ? &SPACE(state, xs[1], ys[1]) : NULL; |
| 584 | } |
| 585 | |
| 586 | /* Check all tiles are associated with something, and all shapes |
| 587 | * are the correct symmetry (i.e. all tiles have a matching tile |
| 588 | * the opposite direction from the dot) */ |
| 589 | static int cccb_assoc(game_state *state, space *tile, void *unused) |
| 590 | { |
| 591 | assert(tile->type == s_tile); |
| 592 | |
| 593 | if (!(tile->flags & F_TILE_ASSOC)) return -1; |
| 594 | return 0; |
| 595 | } |
| 596 | |
| 597 | struct dgs_ctx { |
| 598 | space *dot; |
| 599 | int ndots; |
| 600 | }; |
| 601 | |
| 602 | static int dgs_cb_check(game_state *state, space *tile, void *vctx) |
| 603 | { |
| 604 | struct dgs_ctx *ctx = (struct dgs_ctx *)vctx; |
| 605 | space *opp; |
| 606 | |
| 607 | if (!(tile->flags & F_TILE_ASSOC)) return 0; |
| 608 | if (tile->dotx != ctx->dot->x || |
| 609 | tile->doty != ctx->dot->y) return 0; |
| 610 | |
| 611 | ctx->ndots += 1; |
| 612 | |
| 613 | /* Check this tile has an opposite associated with same dot. */ |
| 614 | opp = tile_opposite(state, tile); |
| 615 | if (!opp || !(opp->flags & F_TILE_ASSOC)) return -1; |
| 616 | if (opp->dotx != tile->dotx || opp->doty != tile->doty) return -1; |
| 617 | |
| 618 | /* Check its edges are correct */ |
| 619 | if (outline_tile_fordot(state, tile, 0) == 1) |
| 620 | return -1; /* there was some fixing required, we're wrong. */ |
| 621 | |
| 622 | return 0; |
| 623 | } |
| 624 | |
| 625 | static int dot_good_shape(game_state *state, space *dot, int mark) |
| 626 | { |
| 627 | struct dgs_ctx ctx; |
| 628 | |
| 629 | ctx.dot = dot; |
| 630 | ctx.ndots = 0; |
| 631 | |
| 632 | if (mark) dot->flags &= ~F_GOOD; |
| 633 | |
| 634 | if (foreach_tile(state, dgs_cb_check, 0, &ctx) == -1) |
| 635 | return 0; |
| 636 | if (ctx.ndots == 0) return 0; /* no dots assoc. with tile. */ |
| 637 | |
| 638 | if (mark) { |
| 639 | debug(("marking dot %d,%d good tile.\n", dot->x, dot->y)); |
| 640 | dot->flags |= F_GOOD; |
| 641 | } |
| 642 | return 1; |
| 643 | } |
| 644 | |
| 645 | static int check_complete(game_state *state, int mark_errors) |
| 646 | { |
| 647 | int i, complete = 1; |
| 648 | |
| 649 | /* Are all tiles associated? */ |
| 650 | if (foreach_tile(state, cccb_assoc, 0, NULL) == -1) |
| 651 | complete = 0; |
| 652 | |
| 653 | /* Check all dots are associated, and their tiles are well-formed. */ |
| 654 | for (i = 0; i < state->ndots; i++) { |
| 655 | if (!dot_good_shape(state, state->dots[i], mark_errors)) |
| 656 | complete = 0; |
| 657 | } |
| 658 | |
| 659 | /*if (complete == 1) printf("Complete!\n");*/ |
| 660 | return complete; |
| 661 | } |
| 662 | |
| 663 | /* Returns a move string for use by 'solve'; if you don't want the |
| 664 | * initial 'S;' use ret[2]. */ |
| 665 | static char *diff_game(game_state *src, game_state *dest, int issolve) |
| 666 | { |
| 667 | int movelen = 0, movesize = 256, x, y, len; |
| 668 | char *move = snewn(movesize, char), buf[80], *sep = ""; |
| 669 | char achar = issolve ? 'a' : 'A'; |
| 670 | space *sps, *spd; |
| 671 | |
| 672 | assert(src->sx == dest->sx && src->sy == dest->sy); |
| 673 | |
| 674 | if (issolve) { |
| 675 | move[movelen++] = 'S'; |
| 676 | sep = ";"; |
| 677 | } |
| 678 | move[movelen] = '\0'; |
| 679 | for (x = 0; x < src->sx; x++) { |
| 680 | for (y = 0; y < src->sy; y++) { |
| 681 | sps = &SPACE(src, x, y); |
| 682 | spd = &SPACE(dest, x, y); |
| 683 | |
| 684 | assert(sps->type == spd->type); |
| 685 | |
| 686 | len = 0; |
| 687 | if (sps->type == s_tile) { |
| 688 | if ((sps->flags & F_TILE_ASSOC) && |
| 689 | (spd->flags & F_TILE_ASSOC)) { |
| 690 | if (sps->dotx != spd->dotx || |
| 691 | sps->doty != spd->doty) |
| 692 | /* Both associated; change association, if different */ |
| 693 | len = sprintf(buf, "%s%c%d,%d,%d,%d", sep, |
| 694 | (int)achar, x, y, spd->dotx, spd->doty); |
| 695 | } else if (sps->flags & F_TILE_ASSOC) |
| 696 | /* Only src associated; remove. */ |
| 697 | len = sprintf(buf, "%sU%d,%d", sep, x, y); |
| 698 | else if (spd->flags & F_TILE_ASSOC) |
| 699 | /* Only dest associated; add. */ |
| 700 | len = sprintf(buf, "%s%c%d,%d,%d,%d", sep, |
| 701 | (int)achar, x, y, spd->dotx, spd->doty); |
| 702 | } else if (sps->type == s_edge) { |
| 703 | if ((sps->flags & F_EDGE_SET) != (spd->flags & F_EDGE_SET)) |
| 704 | /* edge flags are different; flip them. */ |
| 705 | len = sprintf(buf, "%sE%d,%d", sep, x, y); |
| 706 | } |
| 707 | if (len) { |
| 708 | if (movelen + len >= movesize) { |
| 709 | movesize = movelen + len + 256; |
| 710 | move = sresize(move, movesize, char); |
| 711 | } |
| 712 | strcpy(move + movelen, buf); |
| 713 | movelen += len; |
| 714 | sep = ";"; |
| 715 | } |
| 716 | } |
| 717 | } |
| 718 | debug(("diff_game src then dest:\n")); |
| 719 | dbg_state(src); |
| 720 | dbg_state(dest); |
| 721 | debug(("diff string %s\n", move)); |
| 722 | return move; |
| 723 | } |
| 724 | |
| 725 | /* Returns 1 if a dot here would not be too close to any other dots |
| 726 | * (and would avoid other game furniture). */ |
| 727 | static int dot_is_possible(game_state *state, space *sp, int allow_assoc) |
| 728 | { |
| 729 | int bx = 0, by = 0, dx, dy; |
| 730 | space *adj; |
| 731 | |
| 732 | switch (sp->type) { |
| 733 | case s_tile: |
| 734 | bx = by = 1; break; |
| 735 | case s_edge: |
| 736 | if (IS_VERTICAL_EDGE(sp->x)) { |
| 737 | bx = 2; by = 1; |
| 738 | } else { |
| 739 | bx = 1; by = 2; |
| 740 | } |
| 741 | break; |
| 742 | case s_vertex: |
| 743 | bx = by = 2; break; |
| 744 | } |
| 745 | |
| 746 | for (dx = -bx; dx <= bx; dx++) { |
| 747 | for (dy = -by; dy <= by; dy++) { |
| 748 | if (!INGRID(state, sp->x+dx, sp->y+dy)) continue; |
| 749 | |
| 750 | adj = &SPACE(state, sp->x+dx, sp->y+dy); |
| 751 | |
| 752 | if (!allow_assoc && (adj->flags & F_TILE_ASSOC)) |
| 753 | return 0; |
| 754 | |
| 755 | if (dx != 0 || dy != 0) { |
| 756 | /* Other than our own square, no dots nearby. */ |
| 757 | if (adj->flags & (F_DOT)) |
| 758 | return 0; |
| 759 | } |
| 760 | |
| 761 | /* We don't want edges within our rectangle |
| 762 | * (but don't care about edges on the edge) */ |
| 763 | if (abs(dx) < bx && abs(dy) < by && |
| 764 | adj->flags & F_EDGE_SET) |
| 765 | return 0; |
| 766 | } |
| 767 | } |
| 768 | return 1; |
| 769 | } |
| 770 | |
| 771 | /* ---------------------------------------------------------- |
| 772 | * Game generation, structure creation, and descriptions. |
| 773 | */ |
| 774 | |
| 775 | static game_state *blank_game(int w, int h) |
| 776 | { |
| 777 | game_state *state = snew(game_state); |
| 778 | int x, y; |
| 779 | |
| 780 | state->w = w; |
| 781 | state->h = h; |
| 782 | |
| 783 | state->sx = (w*2)+1; |
| 784 | state->sy = (h*2)+1; |
| 785 | state->grid = snewn(state->sx * state->sy, struct space); |
| 786 | state->completed = state->used_solve = 0; |
| 787 | |
| 788 | for (x = 0; x < state->sx; x++) { |
| 789 | for (y = 0; y < state->sy; y++) { |
| 790 | struct space *sp = &SPACE(state, x, y); |
| 791 | memset(sp, 0, sizeof(struct space)); |
| 792 | sp->x = x; |
| 793 | sp->y = y; |
| 794 | if ((x % 2) == 0 && (y % 2) == 0) |
| 795 | sp->type = s_vertex; |
| 796 | else if ((x % 2) == 0 || (y % 2) == 0) { |
| 797 | sp->type = s_edge; |
| 798 | if (x == 0 || y == 0 || x == state->sx-1 || y == state->sy-1) |
| 799 | sp->flags |= F_EDGE_SET; |
| 800 | } else |
| 801 | sp->type = s_tile; |
| 802 | } |
| 803 | } |
| 804 | |
| 805 | state->ndots = 0; |
| 806 | state->dots = NULL; |
| 807 | |
| 808 | state->me = NULL; /* filled in by new_game. */ |
| 809 | state->cdiff = -1; |
| 810 | |
| 811 | return state; |
| 812 | } |
| 813 | |
| 814 | static void game_update_dots(game_state *state) |
| 815 | { |
| 816 | int i, n, sz = state->sx * state->sy; |
| 817 | |
| 818 | if (state->dots) sfree(state->dots); |
| 819 | state->ndots = 0; |
| 820 | |
| 821 | for (i = 0; i < sz; i++) { |
| 822 | if (state->grid[i].flags & F_DOT) state->ndots++; |
| 823 | } |
| 824 | state->dots = snewn(state->ndots, space *); |
| 825 | n = 0; |
| 826 | for (i = 0; i < sz; i++) { |
| 827 | if (state->grid[i].flags & F_DOT) |
| 828 | state->dots[n++] = &state->grid[i]; |
| 829 | } |
| 830 | } |
| 831 | |
| 832 | static void clear_game(game_state *state, int cleardots) |
| 833 | { |
| 834 | int x, y; |
| 835 | |
| 836 | /* don't erase edge flags around outline! */ |
| 837 | for (x = 1; x < state->sx-1; x++) { |
| 838 | for (y = 1; y < state->sy-1; y++) { |
| 839 | if (cleardots) |
| 840 | SPACE(state, x, y).flags = 0; |
| 841 | else |
| 842 | SPACE(state, x, y).flags &= (F_DOT|F_DOT_BLACK); |
| 843 | } |
| 844 | } |
| 845 | if (cleardots) game_update_dots(state); |
| 846 | } |
| 847 | |
| 848 | static game_state *dup_game(game_state *state) |
| 849 | { |
| 850 | game_state *ret = blank_game(state->w, state->h); |
| 851 | |
| 852 | ret->completed = state->completed; |
| 853 | ret->used_solve = state->used_solve; |
| 854 | |
| 855 | memcpy(ret->grid, state->grid, |
| 856 | ret->sx*ret->sy*sizeof(struct space)); |
| 857 | |
| 858 | game_update_dots(ret); |
| 859 | |
| 860 | ret->me = state->me; |
| 861 | ret->cdiff = state->cdiff; |
| 862 | |
| 863 | return ret; |
| 864 | } |
| 865 | |
| 866 | static void free_game(game_state *state) |
| 867 | { |
| 868 | if (state->dots) sfree(state->dots); |
| 869 | sfree(state->grid); |
| 870 | sfree(state); |
| 871 | } |
| 872 | |
| 873 | /* Game description is a sequence of letters representing the number |
| 874 | * of spaces (a = 0, y = 24) before the next dot; a-y for a white dot, |
| 875 | * and A-Y for a black dot. 'z' is 25 spaces (and no dot). |
| 876 | * |
| 877 | * I know it's a bitch to generate by hand, so we provide |
| 878 | * an edit mode. |
| 879 | */ |
| 880 | |
| 881 | static char *encode_game(game_state *state) |
| 882 | { |
| 883 | char *desc, *p; |
| 884 | int run, x, y, area; |
| 885 | unsigned int f; |
| 886 | |
| 887 | area = (state->sx-2) * (state->sy-2); |
| 888 | |
| 889 | desc = snewn(area, char); |
| 890 | p = desc; |
| 891 | run = 0; |
| 892 | for (y = 1; y < state->sy-1; y++) { |
| 893 | for (x = 1; x < state->sx-1; x++) { |
| 894 | f = SPACE(state, x, y).flags; |
| 895 | |
| 896 | /* a/A is 0 spaces between, b/B is 1 space, ... |
| 897 | * y/Y is 24 spaces, za/zA is 25 spaces, ... |
| 898 | * It's easier to count from 0 because we then |
| 899 | * don't have to special-case the top left-hand corner |
| 900 | * (which could be a dot with 0 spaces before it). */ |
| 901 | if (!(f & F_DOT)) |
| 902 | run++; |
| 903 | else { |
| 904 | while (run > 24) { |
| 905 | *p++ = 'z'; |
| 906 | run -= 25; |
| 907 | } |
| 908 | *p++ = ((f & F_DOT_BLACK) ? 'A' : 'a') + run; |
| 909 | run = 0; |
| 910 | } |
| 911 | } |
| 912 | } |
| 913 | assert(p - desc < area); |
| 914 | *p++ = '\0'; |
| 915 | desc = sresize(desc, p - desc, char); |
| 916 | |
| 917 | return desc; |
| 918 | } |
| 919 | |
| 920 | struct movedot { |
| 921 | int op; |
| 922 | space *olddot, *newdot; |
| 923 | }; |
| 924 | |
| 925 | enum { MD_CHECK, MD_MOVE }; |
| 926 | |
| 927 | static int movedot_cb(game_state *state, space *tile, void *vctx) |
| 928 | { |
| 929 | struct movedot *md = (struct movedot *)vctx; |
| 930 | space *newopp = NULL; |
| 931 | |
| 932 | assert(tile->type == s_tile); |
| 933 | assert(md->olddot && md->newdot); |
| 934 | |
| 935 | if (!(tile->flags & F_TILE_ASSOC)) return 0; |
| 936 | if (tile->dotx != md->olddot->x || tile->doty != md->olddot->y) |
| 937 | return 0; |
| 938 | |
| 939 | newopp = space_opposite_dot(state, tile, md->newdot); |
| 940 | |
| 941 | switch (md->op) { |
| 942 | case MD_CHECK: |
| 943 | /* If the tile is associated with the old dot, check its |
| 944 | * opposite wrt the _new_ dot is empty or same assoc. */ |
| 945 | if (!newopp) return -1; /* no new opposite */ |
| 946 | if (newopp->flags & F_TILE_ASSOC) { |
| 947 | if (newopp->dotx != md->olddot->x || |
| 948 | newopp->doty != md->olddot->y) |
| 949 | return -1; /* associated, but wrong dot. */ |
| 950 | } |
| 951 | break; |
| 952 | |
| 953 | case MD_MOVE: |
| 954 | /* Move dot associations: anything that was associated |
| 955 | * with the old dot, and its opposite wrt the new dot, |
| 956 | * become associated with the new dot. */ |
| 957 | assert(newopp); |
| 958 | debug(("Associating %d,%d and %d,%d with new dot %d,%d.\n", |
| 959 | tile->x, tile->y, newopp->x, newopp->y, |
| 960 | md->newdot->x, md->newdot->y)); |
| 961 | add_assoc(state, tile, md->newdot); |
| 962 | add_assoc(state, newopp, md->newdot); |
| 963 | return 1; /* we did something! */ |
| 964 | } |
| 965 | return 0; |
| 966 | } |
| 967 | |
| 968 | /* For the given dot, first see if we could expand it into all the given |
| 969 | * extra spaces (by checking for empty spaces on the far side), and then |
| 970 | * see if we can move the dot to shift the CoG to include the new spaces. |
| 971 | */ |
| 972 | static int dot_expand_or_move(game_state *state, space *dot, |
| 973 | space **toadd, int nadd) |
| 974 | { |
| 975 | space *tileopp; |
| 976 | int i, ret, nnew, cx, cy; |
| 977 | struct movedot md; |
| 978 | |
| 979 | debug(("dot_expand_or_move: %d tiles for dot %d,%d\n", |
| 980 | nadd, dot->x, dot->y)); |
| 981 | for (i = 0; i < nadd; i++) |
| 982 | debug(("dot_expand_or_move: dot %d,%d\n", |
| 983 | toadd[i]->x, toadd[i]->y)); |
| 984 | assert(dot->flags & F_DOT); |
| 985 | |
| 986 | /* First off, could we just expand the current dot's tile to cover |
| 987 | * the space(s) passed in and their opposites? */ |
| 988 | for (i = 0; i < nadd; i++) { |
| 989 | tileopp = space_opposite_dot(state, toadd[i], dot); |
| 990 | if (!tileopp) goto noexpand; |
| 991 | if (tileopp->flags & F_TILE_ASSOC) goto noexpand; |
| 992 | } |
| 993 | /* OK, all spaces have valid empty opposites: associate spaces and |
| 994 | * opposites with our dot. */ |
| 995 | for (i = 0; i < nadd; i++) { |
| 996 | tileopp = space_opposite_dot(state, toadd[i], dot); |
| 997 | add_assoc(state, toadd[i], dot); |
| 998 | add_assoc(state, tileopp, dot); |
| 999 | debug(("Added associations %d,%d and %d,%d --> %d,%d\n", |
| 1000 | toadd[i]->x, toadd[i]->y, |
| 1001 | tileopp->x, tileopp->y, |
| 1002 | dot->x, dot->y)); |
| 1003 | dbg_state(state); |
| 1004 | } |
| 1005 | return 1; |
| 1006 | |
| 1007 | noexpand: |
| 1008 | /* Otherwise, try to move dot so as to encompass given spaces: */ |
| 1009 | /* first, alculate the 'centre of gravity' of the new dot. */ |
| 1010 | nnew = dot->nassoc + nadd; /* number of tiles assoc. with new dot. */ |
| 1011 | cx = dot->x * dot->nassoc; |
| 1012 | cy = dot->y * dot->nassoc; |
| 1013 | for (i = 0; i < nadd; i++) { |
| 1014 | cx += toadd[i]->x; |
| 1015 | cy += toadd[i]->y; |
| 1016 | } |
| 1017 | /* If the CoG isn't a whole number, it's not possible. */ |
| 1018 | if ((cx % nnew) != 0 || (cy % nnew) != 0) { |
| 1019 | debug(("Unable to move dot %d,%d, CoG not whole number.\n", |
| 1020 | dot->x, dot->y)); |
| 1021 | return 0; |
| 1022 | } |
| 1023 | cx /= nnew; cy /= nnew; |
| 1024 | |
| 1025 | /* Check whether all spaces in the old tile would have a good |
| 1026 | * opposite wrt the new dot. */ |
| 1027 | md.olddot = dot; |
| 1028 | md.newdot = &SPACE(state, cx, cy); |
| 1029 | md.op = MD_CHECK; |
| 1030 | ret = foreach_tile(state, movedot_cb, IMPOSSIBLE_QUITS, &md); |
| 1031 | if (ret == -1) { |
| 1032 | debug(("Unable to move dot %d,%d, new dot not symmetrical.\n", |
| 1033 | dot->x, dot->y)); |
| 1034 | return 0; |
| 1035 | } |
| 1036 | /* Also check whether all spaces we're adding would have a good |
| 1037 | * opposite wrt the new dot. */ |
| 1038 | for (i = 0; i < nadd; i++) { |
| 1039 | tileopp = space_opposite_dot(state, toadd[i], md.newdot); |
| 1040 | if (tileopp && (tileopp->flags & F_TILE_ASSOC) && |
| 1041 | (tileopp->dotx != dot->x || tileopp->doty != dot->y)) { |
| 1042 | tileopp = NULL; |
| 1043 | } |
| 1044 | if (!tileopp) { |
| 1045 | debug(("Unable to move dot %d,%d, new dot not symmetrical.\n", |
| 1046 | dot->x, dot->y)); |
| 1047 | return 0; |
| 1048 | } |
| 1049 | } |
| 1050 | |
| 1051 | /* If we've got here, we're ok. First, associate all of 'toadd' |
| 1052 | * with the _old_ dot (so they'll get fixed up, with their opposites, |
| 1053 | * in the next step). */ |
| 1054 | for (i = 0; i < nadd; i++) { |
| 1055 | debug(("Associating to-add %d,%d with old dot %d,%d.\n", |
| 1056 | toadd[i]->x, toadd[i]->y, dot->x, dot->y)); |
| 1057 | add_assoc(state, toadd[i], dot); |
| 1058 | } |
| 1059 | |
| 1060 | /* Finally, move the dot and fix up all the old associations. */ |
| 1061 | debug(("Moving dot at %d,%d to %d,%d\n", |
| 1062 | dot->x, dot->y, md.newdot->x, md.newdot->y)); |
| 1063 | remove_dot(dot); |
| 1064 | add_dot(md.newdot); |
| 1065 | |
| 1066 | md.op = MD_MOVE; |
| 1067 | ret = foreach_tile(state, movedot_cb, 0, &md); |
| 1068 | assert(ret == 1); |
| 1069 | dbg_state(state); |
| 1070 | |
| 1071 | return 1; |
| 1072 | } |
| 1073 | |
| 1074 | /* Hard-code to a max. of 2x2 squares, for speed (less malloc) */ |
| 1075 | #define MAX_TOADD 4 |
| 1076 | #define MAX_OUTSIDE 8 |
| 1077 | |
| 1078 | #define MAX_TILE_PERC 20 |
| 1079 | |
| 1080 | static int generate_try_block(game_state *state, random_state *rs, |
| 1081 | int x1, int y1, int x2, int y2) |
| 1082 | { |
| 1083 | int x, y, nadd = 0, nout = 0, i, maxsz; |
| 1084 | space *sp, *toadd[MAX_TOADD], *outside[MAX_OUTSIDE], *dot; |
| 1085 | |
| 1086 | if (!INGRID(state, x1, y1) || !INGRID(state, x2, y2)) return 0; |
| 1087 | |
| 1088 | /* We limit the maximum size of tiles to be ~2*sqrt(area); so, |
| 1089 | * a 5x5 grid shouldn't have anything >10 tiles, a 20x20 grid |
| 1090 | * nothing >40 tiles. */ |
| 1091 | maxsz = (int)sqrt((double)(state->w * state->h)) * 2; |
| 1092 | debug(("generate_try_block, maxsz %d\n", maxsz)); |
| 1093 | |
| 1094 | /* Make a static list of the spaces; if any space is already |
| 1095 | * associated then quit immediately. */ |
| 1096 | for (x = x1; x <= x2; x += 2) { |
| 1097 | for (y = y1; y <= y2; y += 2) { |
| 1098 | assert(nadd < MAX_TOADD); |
| 1099 | sp = &SPACE(state, x, y); |
| 1100 | assert(sp->type == s_tile); |
| 1101 | if (sp->flags & F_TILE_ASSOC) return 0; |
| 1102 | toadd[nadd++] = sp; |
| 1103 | } |
| 1104 | } |
| 1105 | |
| 1106 | /* Make a list of the spaces outside of our block, and shuffle it. */ |
| 1107 | #define OUTSIDE(x, y) do { \ |
| 1108 | if (INGRID(state, (x), (y))) { \ |
| 1109 | assert(nout < MAX_OUTSIDE); \ |
| 1110 | outside[nout++] = &SPACE(state, (x), (y)); \ |
| 1111 | } \ |
| 1112 | } while(0) |
| 1113 | for (x = x1; x <= x2; x += 2) { |
| 1114 | OUTSIDE(x, y1-2); |
| 1115 | OUTSIDE(x, y2+2); |
| 1116 | } |
| 1117 | for (y = y1; y <= y2; y += 2) { |
| 1118 | OUTSIDE(x1-2, y); |
| 1119 | OUTSIDE(x2+2, y); |
| 1120 | } |
| 1121 | shuffle(outside, nout, sizeof(space *), rs); |
| 1122 | |
| 1123 | for (i = 0; i < nout; i++) { |
| 1124 | if (!(outside[i]->flags & F_TILE_ASSOC)) continue; |
| 1125 | dot = &SPACE(state, outside[i]->dotx, outside[i]->doty); |
| 1126 | if (dot->nassoc >= maxsz) { |
| 1127 | debug(("Not adding to dot %d,%d, large enough (%d) already.\n", |
| 1128 | dot->x, dot->y, dot->nassoc)); |
| 1129 | continue; |
| 1130 | } |
| 1131 | if (dot_expand_or_move(state, dot, toadd, nadd)) return 1; |
| 1132 | } |
| 1133 | return 0; |
| 1134 | } |
| 1135 | |
| 1136 | #ifdef STANDALONE_SOLVER |
| 1137 | int maxtries; |
| 1138 | #define MAXTRIES maxtries |
| 1139 | #else |
| 1140 | #define MAXTRIES 50 |
| 1141 | #endif |
| 1142 | |
| 1143 | static int solver_obvious_dot(game_state *state,space *dot); |
| 1144 | |
| 1145 | #define GP_DOTS 1 |
| 1146 | |
| 1147 | static void generate_pass(game_state *state, random_state *rs, int *scratch, |
| 1148 | int perc, unsigned int flags) |
| 1149 | { |
| 1150 | int sz = state->sx*state->sy, nspc, i, ret; |
| 1151 | |
| 1152 | shuffle(scratch, sz, sizeof(int), rs); |
| 1153 | |
| 1154 | /* This bug took me a, er, little while to track down. On PalmOS, |
| 1155 | * which has 16-bit signed ints, puzzles over about 9x9 started |
| 1156 | * failing to generate because the nspc calculation would start |
| 1157 | * to overflow, causing the dots not to be filled in properly. */ |
| 1158 | nspc = (int)(((long)perc * (long)sz) / 100L); |
| 1159 | debug(("generate_pass: %d%% (%d of %dx%d) squares, flags 0x%x\n", |
| 1160 | perc, nspc, state->sx, state->sy, flags)); |
| 1161 | |
| 1162 | for (i = 0; i < nspc; i++) { |
| 1163 | space *sp = &state->grid[scratch[i]]; |
| 1164 | int x1 = sp->x, y1 = sp->y, x2 = sp->x, y2 = sp->y; |
| 1165 | |
| 1166 | if (sp->type == s_edge) { |
| 1167 | if (IS_VERTICAL_EDGE(sp->x)) { |
| 1168 | x1--; x2++; |
| 1169 | } else { |
| 1170 | y1--; y2++; |
| 1171 | } |
| 1172 | } |
| 1173 | if (sp->type != s_vertex) { |
| 1174 | /* heuristic; expanding from vertices tends to generate lots of |
| 1175 | * too-big regions of tiles. */ |
| 1176 | if (generate_try_block(state, rs, x1, y1, x2, y2)) |
| 1177 | continue; /* we expanded successfully. */ |
| 1178 | } |
| 1179 | |
| 1180 | if (!(flags & GP_DOTS)) continue; |
| 1181 | |
| 1182 | if ((sp->type == s_edge) && (i % 2)) { |
| 1183 | debug(("Omitting edge %d,%d as half-of.\n", sp->x, sp->y)); |
| 1184 | continue; |
| 1185 | } |
| 1186 | |
| 1187 | /* If we've got here we might want to put a dot down. Check |
| 1188 | * if we can, and add one if so. */ |
| 1189 | if (dot_is_possible(state, sp, 0)) { |
| 1190 | add_dot(sp); |
| 1191 | ret = solver_obvious_dot(state, sp); |
| 1192 | assert(ret != -1); |
| 1193 | debug(("Added dot (and obvious associations) at %d,%d\n", |
| 1194 | sp->x, sp->y)); |
| 1195 | dbg_state(state); |
| 1196 | } |
| 1197 | } |
| 1198 | dbg_state(state); |
| 1199 | } |
| 1200 | |
| 1201 | static int solver_state(game_state *state, int maxdiff); |
| 1202 | |
| 1203 | static char *new_game_desc(game_params *params, random_state *rs, |
| 1204 | char **aux, int interactive) |
| 1205 | { |
| 1206 | game_state *state = blank_game(params->w, params->h), *copy; |
| 1207 | char *desc; |
| 1208 | int *scratch, sz = state->sx*state->sy, i; |
| 1209 | int diff, ntries = 0; |
| 1210 | |
| 1211 | /* Random list of squares to try and process, one-by-one. */ |
| 1212 | scratch = snewn(sz, int); |
| 1213 | for (i = 0; i < sz; i++) scratch[i] = i; |
| 1214 | |
| 1215 | generate: |
| 1216 | clear_game(state, 1); |
| 1217 | ntries++; |
| 1218 | |
| 1219 | /* generate_pass(state, rs, scratch, 10, GP_DOTS); */ |
| 1220 | /* generate_pass(state, rs, scratch, 100, 0); */ |
| 1221 | generate_pass(state, rs, scratch, 100, GP_DOTS); |
| 1222 | |
| 1223 | game_update_dots(state); |
| 1224 | |
| 1225 | #ifdef DEBUGGING |
| 1226 | { |
| 1227 | char *tmp = encode_game(state); |
| 1228 | debug(("new_game_desc state %dx%d:%s\n", params->w, params->h, tmp)); |
| 1229 | sfree(tmp); |
| 1230 | } |
| 1231 | #endif |
| 1232 | |
| 1233 | copy = dup_game(state); |
| 1234 | clear_game(copy, 0); |
| 1235 | dbg_state(copy); |
| 1236 | diff = solver_state(copy, params->diff); |
| 1237 | free_game(copy); |
| 1238 | |
| 1239 | assert(diff != DIFF_IMPOSSIBLE); |
| 1240 | if (diff != params->diff) { |
| 1241 | /* |
| 1242 | * We'll grudgingly accept a too-easy puzzle, but we must |
| 1243 | * _not_ permit a too-hard one (one which the solver |
| 1244 | * couldn't handle at all). |
| 1245 | */ |
| 1246 | if (diff > params->diff || |
| 1247 | ntries < MAXTRIES) goto generate; |
| 1248 | } |
| 1249 | |
| 1250 | desc = encode_game(state); |
| 1251 | #ifndef STANDALONE_SOLVER |
| 1252 | debug(("new_game_desc generated: \n")); |
| 1253 | dbg_state(state); |
| 1254 | #endif |
| 1255 | |
| 1256 | free_game(state); |
| 1257 | sfree(scratch); |
| 1258 | |
| 1259 | return desc; |
| 1260 | } |
| 1261 | |
| 1262 | static int solver_obvious(game_state *state); |
| 1263 | |
| 1264 | static int dots_too_close(game_state *state) |
| 1265 | { |
| 1266 | /* Quick-and-dirty check, using half the solver: |
| 1267 | * solver_obvious will only fail if the dots are |
| 1268 | * too close together, so dot-proximity associations |
| 1269 | * overlap. */ |
| 1270 | game_state *tmp = dup_game(state); |
| 1271 | int ret = solver_obvious(tmp); |
| 1272 | free_game(tmp); |
| 1273 | return (ret == -1) ? 1 : 0; |
| 1274 | } |
| 1275 | |
| 1276 | static game_state *load_game(game_params *params, char *desc, |
| 1277 | char **why_r) |
| 1278 | { |
| 1279 | game_state *state = blank_game(params->w, params->h); |
| 1280 | char *why = NULL; |
| 1281 | int i, x, y, n; |
| 1282 | unsigned int df; |
| 1283 | |
| 1284 | i = 0; |
| 1285 | while (*desc) { |
| 1286 | n = *desc++; |
| 1287 | if (n == 'z') { |
| 1288 | i += 25; |
| 1289 | continue; |
| 1290 | } |
| 1291 | if (n >= 'a' && n <= 'y') { |
| 1292 | i += n - 'a'; |
| 1293 | df = 0; |
| 1294 | } else if (n >= 'A' && n <= 'Y') { |
| 1295 | i += n - 'A'; |
| 1296 | df = F_DOT_BLACK; |
| 1297 | } else { |
| 1298 | why = "Invalid characters in game description"; goto fail; |
| 1299 | } |
| 1300 | /* if we got here we incremented i and have a dot to add. */ |
| 1301 | y = (i / (state->sx-2)) + 1; |
| 1302 | x = (i % (state->sx-2)) + 1; |
| 1303 | if (!INUI(state, x, y)) { |
| 1304 | why = "Too much data to fit in grid"; goto fail; |
| 1305 | } |
| 1306 | add_dot(&SPACE(state, x, y)); |
| 1307 | SPACE(state, x, y).flags |= df; |
| 1308 | i++; |
| 1309 | } |
| 1310 | game_update_dots(state); |
| 1311 | |
| 1312 | if (dots_too_close(state)) { |
| 1313 | why = "Dots too close together"; goto fail; |
| 1314 | } |
| 1315 | |
| 1316 | return state; |
| 1317 | |
| 1318 | fail: |
| 1319 | free_game(state); |
| 1320 | if (why_r) *why_r = why; |
| 1321 | return NULL; |
| 1322 | } |
| 1323 | |
| 1324 | static char *validate_desc(game_params *params, char *desc) |
| 1325 | { |
| 1326 | char *why = NULL; |
| 1327 | game_state *dummy = load_game(params, desc, &why); |
| 1328 | if (dummy) { |
| 1329 | free_game(dummy); |
| 1330 | assert(!why); |
| 1331 | } else |
| 1332 | assert(why); |
| 1333 | return why; |
| 1334 | } |
| 1335 | |
| 1336 | static game_state *new_game(midend *me, game_params *params, char *desc) |
| 1337 | { |
| 1338 | game_state *state = load_game(params, desc, NULL); |
| 1339 | if (!state) { |
| 1340 | assert("Unable to load ?validated game."); |
| 1341 | return NULL; |
| 1342 | } |
| 1343 | #ifdef EDITOR |
| 1344 | state->me = me; |
| 1345 | #endif |
| 1346 | return state; |
| 1347 | } |
| 1348 | |
| 1349 | /* ---------------------------------------------------------- |
| 1350 | * Solver and all its little wizards. |
| 1351 | */ |
| 1352 | |
| 1353 | int solver_recurse_depth; |
| 1354 | |
| 1355 | typedef struct solver_ctx { |
| 1356 | game_state *state; |
| 1357 | int sz; /* state->sx * state->sy */ |
| 1358 | space **scratch; /* size sz */ |
| 1359 | |
| 1360 | } solver_ctx; |
| 1361 | |
| 1362 | static solver_ctx *new_solver(game_state *state) |
| 1363 | { |
| 1364 | solver_ctx *sctx = snew(solver_ctx); |
| 1365 | sctx->state = state; |
| 1366 | sctx->sz = state->sx*state->sy; |
| 1367 | sctx->scratch = snewn(sctx->sz, space *); |
| 1368 | return sctx; |
| 1369 | } |
| 1370 | |
| 1371 | static void free_solver(solver_ctx *sctx) |
| 1372 | { |
| 1373 | sfree(sctx->scratch); |
| 1374 | sfree(sctx); |
| 1375 | } |
| 1376 | |
| 1377 | /* Solver ideas so far: |
| 1378 | * |
| 1379 | * For any empty space, work out how many dots it could associate |
| 1380 | * with: |
| 1381 | * it needs line-of-sight |
| 1382 | * it needs an empty space on the far side |
| 1383 | * any adjacent lines need corresponding line possibilities. |
| 1384 | */ |
| 1385 | |
| 1386 | /* The solver_ctx should keep a list of dot positions, for quicker looping. |
| 1387 | * |
| 1388 | * Solver techniques, in order of difficulty: |
| 1389 | * obvious adjacency to dots |
| 1390 | * transferring tiles to opposite side |
| 1391 | * transferring lines to opposite side |
| 1392 | * one possible dot for a given tile based on opposite availability |
| 1393 | * tile with 3 definite edges next to an associated tile must associate |
| 1394 | with same dot. |
| 1395 | * |
| 1396 | * one possible dot for a given tile based on line-of-sight |
| 1397 | */ |
| 1398 | |
| 1399 | static int solver_add_assoc(game_state *state, space *tile, int dx, int dy, |
| 1400 | const char *why) |
| 1401 | { |
| 1402 | space *dot, *tile_opp; |
| 1403 | |
| 1404 | dot = &SPACE(state, dx, dy); |
| 1405 | tile_opp = space_opposite_dot(state, tile, dot); |
| 1406 | |
| 1407 | assert(tile->type == s_tile); |
| 1408 | if (tile->flags & F_TILE_ASSOC) { |
| 1409 | if ((tile->dotx != dx) || (tile->doty != dy)) { |
| 1410 | solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; " |
| 1411 | "already --> %d,%d.\n", |
| 1412 | solver_recurse_depth*4, "", |
| 1413 | tile->x, tile->y, dx, dy, why, |
| 1414 | tile->dotx, tile->doty)); |
| 1415 | return -1; |
| 1416 | } |
| 1417 | return 0; /* no-op */ |
| 1418 | } |
| 1419 | if (!tile_opp) { |
| 1420 | solvep(("%*s%d,%d --> %d,%d impossible, no opposite tile.\n", |
| 1421 | solver_recurse_depth*4, "", tile->x, tile->y, dx, dy)); |
| 1422 | return -1; |
| 1423 | } |
| 1424 | if (tile_opp->flags & F_TILE_ASSOC && |
| 1425 | (tile_opp->dotx != dx || tile_opp->doty != dy)) { |
| 1426 | solvep(("%*sSet %d,%d --> %d,%d (%s) impossible; " |
| 1427 | "opposite already --> %d,%d.\n", |
| 1428 | solver_recurse_depth*4, "", |
| 1429 | tile->x, tile->y, dx, dy, why, |
| 1430 | tile_opp->dotx, tile_opp->doty)); |
| 1431 | return -1; |
| 1432 | } |
| 1433 | |
| 1434 | add_assoc(state, tile, dot); |
| 1435 | add_assoc(state, tile_opp, dot); |
| 1436 | solvep(("%*sSetting %d,%d --> %d,%d (%s).\n", |
| 1437 | solver_recurse_depth*4, "", |
| 1438 | tile->x, tile->y,dx, dy, why)); |
| 1439 | solvep(("%*sSetting %d,%d --> %d,%d (%s, opposite).\n", |
| 1440 | solver_recurse_depth*4, "", |
| 1441 | tile_opp->x, tile_opp->y, dx, dy, why)); |
| 1442 | return 1; |
| 1443 | } |
| 1444 | |
| 1445 | static int solver_obvious_dot(game_state *state, space *dot) |
| 1446 | { |
| 1447 | int dx, dy, ret, didsth = 0; |
| 1448 | space *tile; |
| 1449 | |
| 1450 | debug(("%*ssolver_obvious_dot for %d,%d.\n", |
| 1451 | solver_recurse_depth*4, "", dot->x, dot->y)); |
| 1452 | |
| 1453 | assert(dot->flags & F_DOT); |
| 1454 | for (dx = -1; dx <= 1; dx++) { |
| 1455 | for (dy = -1; dy <= 1; dy++) { |
| 1456 | if (!INGRID(state, dot->x+dx, dot->y+dy)) continue; |
| 1457 | |
| 1458 | tile = &SPACE(state, dot->x+dx, dot->y+dy); |
| 1459 | if (tile->type == s_tile) { |
| 1460 | ret = solver_add_assoc(state, tile, dot->x, dot->y, |
| 1461 | "next to dot"); |
| 1462 | if (ret < 0) return -1; |
| 1463 | if (ret > 0) didsth = 1; |
| 1464 | } |
| 1465 | } |
| 1466 | } |
| 1467 | return didsth; |
| 1468 | } |
| 1469 | |
| 1470 | static int solver_obvious(game_state *state) |
| 1471 | { |
| 1472 | int i, didsth = 0, ret; |
| 1473 | |
| 1474 | debug(("%*ssolver_obvious.\n", solver_recurse_depth*4, "")); |
| 1475 | |
| 1476 | for (i = 0; i < state->ndots; i++) { |
| 1477 | ret = solver_obvious_dot(state, state->dots[i]); |
| 1478 | if (ret < 0) return -1; |
| 1479 | if (ret > 0) didsth = 1; |
| 1480 | } |
| 1481 | return didsth; |
| 1482 | } |
| 1483 | |
| 1484 | static int solver_lines_opposite_cb(game_state *state, space *edge, void *ctx) |
| 1485 | { |
| 1486 | int didsth = 0, n, dx, dy; |
| 1487 | space *tiles[2], *tile_opp, *edge_opp; |
| 1488 | |
| 1489 | assert(edge->type == s_edge); |
| 1490 | |
| 1491 | tiles_from_edge(state, edge, tiles); |
| 1492 | |
| 1493 | /* if tiles[0] && tiles[1] && they're both associated |
| 1494 | * and they're both associated with different dots, |
| 1495 | * ensure the line is set. */ |
| 1496 | if (!(edge->flags & F_EDGE_SET) && |
| 1497 | tiles[0] && tiles[1] && |
| 1498 | (tiles[0]->flags & F_TILE_ASSOC) && |
| 1499 | (tiles[1]->flags & F_TILE_ASSOC) && |
| 1500 | (tiles[0]->dotx != tiles[1]->dotx || |
| 1501 | tiles[0]->doty != tiles[1]->doty)) { |
| 1502 | /* No edge, but the two adjacent tiles are both |
| 1503 | * associated with different dots; add the edge. */ |
| 1504 | solvep(("%*sSetting edge %d,%d - tiles different dots.\n", |
| 1505 | solver_recurse_depth*4, "", edge->x, edge->y)); |
| 1506 | edge->flags |= F_EDGE_SET; |
| 1507 | didsth = 1; |
| 1508 | } |
| 1509 | |
| 1510 | if (!(edge->flags & F_EDGE_SET)) return didsth; |
| 1511 | for (n = 0; n < 2; n++) { |
| 1512 | if (!tiles[n]) continue; |
| 1513 | assert(tiles[n]->type == s_tile); |
| 1514 | if (!(tiles[n]->flags & F_TILE_ASSOC)) continue; |
| 1515 | |
| 1516 | tile_opp = tile_opposite(state, tiles[n]); |
| 1517 | if (!tile_opp) { |
| 1518 | solvep(("%*simpossible: edge %d,%d has assoc. tile %d,%d" |
| 1519 | " with no opposite.\n", |
| 1520 | solver_recurse_depth*4, "", |
| 1521 | edge->x, edge->y, tiles[n]->x, tiles[n]->y)); |
| 1522 | /* edge of tile has no opposite edge (off grid?); |
| 1523 | * this is impossible. */ |
| 1524 | return -1; |
| 1525 | } |
| 1526 | |
| 1527 | dx = tiles[n]->x - edge->x; |
| 1528 | dy = tiles[n]->y - edge->y; |
| 1529 | assert(INGRID(state, tile_opp->x+dx, tile_opp->y+dy)); |
| 1530 | edge_opp = &SPACE(state, tile_opp->x+dx, tile_opp->y+dy); |
| 1531 | if (!(edge_opp->flags & F_EDGE_SET)) { |
| 1532 | solvep(("%*sSetting edge %d,%d as opposite %d,%d\n", |
| 1533 | solver_recurse_depth*4, "", |
| 1534 | tile_opp->x-dx, tile_opp->y-dy, edge->x, edge->y)); |
| 1535 | edge_opp->flags |= F_EDGE_SET; |
| 1536 | didsth = 1; |
| 1537 | } |
| 1538 | } |
| 1539 | return didsth; |
| 1540 | } |
| 1541 | |
| 1542 | static int solver_spaces_oneposs_cb(game_state *state, space *tile, void *ctx) |
| 1543 | { |
| 1544 | int n, eset, ret; |
| 1545 | struct space *edgeadj[4], *tileadj[4]; |
| 1546 | int dotx, doty; |
| 1547 | |
| 1548 | assert(tile->type == s_tile); |
| 1549 | if (tile->flags & F_TILE_ASSOC) return 0; |
| 1550 | |
| 1551 | adjacencies(state, tile, edgeadj, tileadj); |
| 1552 | |
| 1553 | /* Empty tile. If each edge is either set, or associated with |
| 1554 | * the same dot, we must also associate with dot. */ |
| 1555 | eset = 0; dotx = -1; doty = -1; |
| 1556 | for (n = 0; n < 4; n++) { |
| 1557 | assert(edgeadj[n]); |
| 1558 | assert(edgeadj[n]->type == s_edge); |
| 1559 | if (edgeadj[n]->flags & F_EDGE_SET) { |
| 1560 | eset++; |
| 1561 | } else { |
| 1562 | assert(tileadj[n]); |
| 1563 | assert(tileadj[n]->type == s_tile); |
| 1564 | |
| 1565 | /* If an adjacent tile is empty we can't make any deductions.*/ |
| 1566 | if (!(tileadj[n]->flags & F_TILE_ASSOC)) |
| 1567 | return 0; |
| 1568 | |
| 1569 | /* If an adjacent tile is assoc. with a different dot |
| 1570 | * we can't make any deductions. */ |
| 1571 | if (dotx != -1 && doty != -1 && |
| 1572 | (tileadj[n]->dotx != dotx || |
| 1573 | tileadj[n]->doty != doty)) |
| 1574 | return 0; |
| 1575 | |
| 1576 | dotx = tileadj[n]->dotx; |
| 1577 | doty = tileadj[n]->doty; |
| 1578 | } |
| 1579 | } |
| 1580 | if (eset == 4) { |
| 1581 | solvep(("%*simpossible: empty tile %d,%d has 4 edges\n", |
| 1582 | solver_recurse_depth*4, "", |
| 1583 | tile->x, tile->y)); |
| 1584 | return -1; |
| 1585 | } |
| 1586 | assert(dotx != -1 && doty != -1); |
| 1587 | |
| 1588 | ret = solver_add_assoc(state, tile, dotx, doty, "rest are edges"); |
| 1589 | if (ret == -1) return -1; |
| 1590 | assert(ret != 0); /* really should have done something. */ |
| 1591 | |
| 1592 | return 1; |
| 1593 | } |
| 1594 | |
| 1595 | /* Improved algorithm for tracking line-of-sight from dots, and not spaces. |
| 1596 | * |
| 1597 | * The solver_ctx already stores a list of dots: the algorithm proceeds by |
| 1598 | * expanding outwards from each dot in turn, expanding first to the boundary |
| 1599 | * of its currently-connected tile and then to all empty tiles that could see |
| 1600 | * it. Empty tiles will be flagged with a 'can see dot <x,y>' sticker. |
| 1601 | * |
| 1602 | * Expansion will happen by (symmetrically opposite) pairs of squares; if |
| 1603 | * a square hasn't an opposite number there's no point trying to expand through |
| 1604 | * it. Empty tiles will therefore also be tagged in pairs. |
| 1605 | * |
| 1606 | * If an empty tile already has a 'can see dot <x,y>' tag from a previous dot, |
| 1607 | * it (and its partner) gets untagged (or, rather, a 'can see two dots' tag) |
| 1608 | * because we're looking for single-dot possibilities. |
| 1609 | * |
| 1610 | * Once we've gone through all the dots, any which still have a 'can see dot' |
| 1611 | * tag get associated with that dot (because it must have been the only one); |
| 1612 | * any without any tag (i.e. that could see _no_ dots) cause an impossibility |
| 1613 | * marked. |
| 1614 | * |
| 1615 | * The expansion will happen each time with a stored list of (space *) pairs, |
| 1616 | * rather than a mark-and-sweep idea; that's horrifically inefficient. |
| 1617 | * |
| 1618 | * expansion algorithm: |
| 1619 | * |
| 1620 | * * allocate list of (space *) the size of s->sx*s->sy. |
| 1621 | * * allocate second grid for (flags, dotx, doty) size of sx*sy. |
| 1622 | * |
| 1623 | * clear second grid (flags = 0, all dotx and doty = 0) |
| 1624 | * flags: F_REACHABLE, F_MULTIPLE |
| 1625 | * |
| 1626 | * |
| 1627 | * * for each dot, start with one pair of tiles that are associated with it -- |
| 1628 | * * vertex --> (dx+1, dy+1), (dx-1, dy-1) |
| 1629 | * * edge --> (adj1, adj2) |
| 1630 | * * tile --> (tile, tile) ??? |
| 1631 | * * mark that pair of tiles with F_MARK, clear all other F_MARKs. |
| 1632 | * * add two tiles to start of list. |
| 1633 | * |
| 1634 | * set start = 0, end = next = 2 |
| 1635 | * |
| 1636 | * from (start to end-1, step 2) { |
| 1637 | * * we have two tiles (t1, t2), opposites wrt our dot. |
| 1638 | * * for each (at1) sensible adjacent tile to t1 (i.e. not past an edge): |
| 1639 | * * work out at2 as the opposite to at1 |
| 1640 | * * assert at1 and at2 have the same F_MARK values. |
| 1641 | * * if at1 & F_MARK ignore it (we've been there on a previous sweep) |
| 1642 | * * if either are associated with a different dot |
| 1643 | * * mark both with F_MARK (so we ignore them later) |
| 1644 | * * otherwise (assoc. with our dot, or empty): |
| 1645 | * * mark both with F_MARK |
| 1646 | * * add their space * values to the end of the list, set next += 2. |
| 1647 | * } |
| 1648 | * |
| 1649 | * if (end == next) |
| 1650 | * * we didn't add any new squares; exit the loop. |
| 1651 | * else |
| 1652 | * * set start = next+1, end = next. go round again |
| 1653 | * |
| 1654 | * We've finished expanding from the dot. Now, for each square we have |
| 1655 | * in our list (--> each square with F_MARK): |
| 1656 | * * if the tile is empty: |
| 1657 | * * if F_REACHABLE was already set |
| 1658 | * * set F_MULTIPLE |
| 1659 | * * otherwise |
| 1660 | * * set F_REACHABLE, set dotx and doty to our dot. |
| 1661 | * |
| 1662 | * Then, continue the whole thing for each dot in turn. |
| 1663 | * |
| 1664 | * Once we've done for each dot, go through the entire grid looking for |
| 1665 | * empty tiles: for each empty tile: |
| 1666 | * if F_REACHABLE and not F_MULTIPLE, set that dot (and its double) |
| 1667 | * if !F_REACHABLE, return as impossible. |
| 1668 | * |
| 1669 | */ |
| 1670 | |
| 1671 | /* Returns 1 if this tile is either already associated with this dot, |
| 1672 | * or blank. */ |
| 1673 | static int solver_expand_checkdot(space *tile, space *dot) |
| 1674 | { |
| 1675 | if (!(tile->flags & F_TILE_ASSOC)) return 1; |
| 1676 | if (tile->dotx == dot->x && tile->doty == dot->y) return 1; |
| 1677 | return 0; |
| 1678 | } |
| 1679 | |
| 1680 | static void solver_expand_fromdot(game_state *state, space *dot, solver_ctx *sctx) |
| 1681 | { |
| 1682 | int i, j, x, y, start, end, next; |
| 1683 | space *sp; |
| 1684 | |
| 1685 | /* Clear the grid of the (space) flags we'll use. */ |
| 1686 | |
| 1687 | /* This is well optimised; analysis showed that: |
| 1688 | for (i = 0; i < sctx->sz; i++) state->grid[i].flags &= ~F_MARK; |
| 1689 | took up ~85% of the total function time! */ |
| 1690 | for (y = 1; y < state->sy; y += 2) { |
| 1691 | sp = &SPACE(state, 1, y); |
| 1692 | for (x = 1; x < state->sx; x += 2, sp += 2) |
| 1693 | sp->flags &= ~F_MARK; |
| 1694 | } |
| 1695 | |
| 1696 | /* Seed the list of marked squares with two that must be associated |
| 1697 | * with our dot (possibly the same space) */ |
| 1698 | if (dot->type == s_tile) { |
| 1699 | sctx->scratch[0] = sctx->scratch[1] = dot; |
| 1700 | } else if (dot->type == s_edge) { |
| 1701 | tiles_from_edge(state, dot, sctx->scratch); |
| 1702 | } else if (dot->type == s_vertex) { |
| 1703 | /* pick two of the opposite ones arbitrarily. */ |
| 1704 | sctx->scratch[0] = &SPACE(state, dot->x-1, dot->y-1); |
| 1705 | sctx->scratch[1] = &SPACE(state, dot->x+1, dot->y+1); |
| 1706 | } |
| 1707 | assert(sctx->scratch[0]->flags & F_TILE_ASSOC); |
| 1708 | assert(sctx->scratch[1]->flags & F_TILE_ASSOC); |
| 1709 | |
| 1710 | sctx->scratch[0]->flags |= F_MARK; |
| 1711 | sctx->scratch[1]->flags |= F_MARK; |
| 1712 | |
| 1713 | debug(("%*sexpand from dot %d,%d seeded with %d,%d and %d,%d.\n", |
| 1714 | solver_recurse_depth*4, "", dot->x, dot->y, |
| 1715 | sctx->scratch[0]->x, sctx->scratch[0]->y, |
| 1716 | sctx->scratch[1]->x, sctx->scratch[1]->y)); |
| 1717 | |
| 1718 | start = 0; end = 2; next = 2; |
| 1719 | |
| 1720 | expand: |
| 1721 | debug(("%*sexpand: start %d, end %d, next %d\n", |
| 1722 | solver_recurse_depth*4, "", start, end, next)); |
| 1723 | for (i = start; i < end; i += 2) { |
| 1724 | space *t1 = sctx->scratch[i]/*, *t2 = sctx->scratch[i+1]*/; |
| 1725 | space *edges[4], *tileadj[4], *tileadj2; |
| 1726 | |
| 1727 | adjacencies(state, t1, edges, tileadj); |
| 1728 | |
| 1729 | for (j = 0; j < 4; j++) { |
| 1730 | assert(edges[j]); |
| 1731 | if (edges[j]->flags & F_EDGE_SET) continue; |
| 1732 | assert(tileadj[j]); |
| 1733 | |
| 1734 | if (tileadj[j]->flags & F_MARK) continue; /* seen before. */ |
| 1735 | |
| 1736 | /* We have a tile adjacent to t1; find its opposite. */ |
| 1737 | tileadj2 = space_opposite_dot(state, tileadj[j], dot); |
| 1738 | if (!tileadj2) { |
| 1739 | debug(("%*sMarking %d,%d, no opposite.\n", |
| 1740 | solver_recurse_depth*4, "", |
| 1741 | tileadj[j]->x, tileadj[j]->y)); |
| 1742 | tileadj[j]->flags |= F_MARK; |
| 1743 | continue; /* no opposite, so mark for next time. */ |
| 1744 | } |
| 1745 | /* If the tile had an opposite we should have either seen both of |
| 1746 | * these, or neither of these, before. */ |
| 1747 | assert(!(tileadj2->flags & F_MARK)); |
| 1748 | |
| 1749 | if (solver_expand_checkdot(tileadj[j], dot) && |
| 1750 | solver_expand_checkdot(tileadj2, dot)) { |
| 1751 | /* Both tiles could associate with this dot; add them to |
| 1752 | * our list. */ |
| 1753 | debug(("%*sAdding %d,%d and %d,%d to possibles list.\n", |
| 1754 | solver_recurse_depth*4, "", |
| 1755 | tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y)); |
| 1756 | sctx->scratch[next++] = tileadj[j]; |
| 1757 | sctx->scratch[next++] = tileadj2; |
| 1758 | } |
| 1759 | /* Either way, we've seen these tiles already so mark them. */ |
| 1760 | debug(("%*sMarking %d,%d and %d,%d.\n", |
| 1761 | solver_recurse_depth*4, "", |
| 1762 | tileadj[j]->x, tileadj[j]->y, tileadj2->x, tileadj2->y)); |
| 1763 | tileadj[j]->flags |= F_MARK; |
| 1764 | tileadj2->flags |= F_MARK; |
| 1765 | } |
| 1766 | } |
| 1767 | if (next > end) { |
| 1768 | /* We added more squares; go back and try again. */ |
| 1769 | start = end; end = next; goto expand; |
| 1770 | } |
| 1771 | |
| 1772 | /* We've expanded as far as we can go. Now we update the main flags |
| 1773 | * on all tiles we've expanded into -- if they were empty, we have |
| 1774 | * found possible associations for this dot. */ |
| 1775 | for (i = 0; i < end; i++) { |
| 1776 | if (sctx->scratch[i]->flags & F_TILE_ASSOC) continue; |
| 1777 | if (sctx->scratch[i]->flags & F_REACHABLE) { |
| 1778 | /* This is (at least) the second dot this tile could |
| 1779 | * associate with. */ |
| 1780 | debug(("%*sempty tile %d,%d could assoc. other dot %d,%d\n", |
| 1781 | solver_recurse_depth*4, "", |
| 1782 | sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y)); |
| 1783 | sctx->scratch[i]->flags |= F_MULTIPLE; |
| 1784 | } else { |
| 1785 | /* This is the first (possibly only) dot. */ |
| 1786 | debug(("%*sempty tile %d,%d could assoc. 1st dot %d,%d\n", |
| 1787 | solver_recurse_depth*4, "", |
| 1788 | sctx->scratch[i]->x, sctx->scratch[i]->y, dot->x, dot->y)); |
| 1789 | sctx->scratch[i]->flags |= F_REACHABLE; |
| 1790 | sctx->scratch[i]->dotx = dot->x; |
| 1791 | sctx->scratch[i]->doty = dot->y; |
| 1792 | } |
| 1793 | } |
| 1794 | dbg_state(state); |
| 1795 | } |
| 1796 | |
| 1797 | static int solver_expand_postcb(game_state *state, space *tile, void *ctx) |
| 1798 | { |
| 1799 | assert(tile->type == s_tile); |
| 1800 | |
| 1801 | if (tile->flags & F_TILE_ASSOC) return 0; |
| 1802 | |
| 1803 | if (!(tile->flags & F_REACHABLE)) { |
| 1804 | solvep(("%*simpossible: space (%d,%d) can reach no dots.\n", |
| 1805 | solver_recurse_depth*4, "", tile->x, tile->y)); |
| 1806 | return -1; |
| 1807 | } |
| 1808 | if (tile->flags & F_MULTIPLE) return 0; |
| 1809 | |
| 1810 | return solver_add_assoc(state, tile, tile->dotx, tile->doty, |
| 1811 | "single possible dot after expansion"); |
| 1812 | } |
| 1813 | |
| 1814 | static int solver_expand_dots(game_state *state, solver_ctx *sctx) |
| 1815 | { |
| 1816 | int i; |
| 1817 | |
| 1818 | for (i = 0; i < sctx->sz; i++) |
| 1819 | state->grid[i].flags &= ~(F_REACHABLE|F_MULTIPLE); |
| 1820 | |
| 1821 | for (i = 0; i < state->ndots; i++) |
| 1822 | solver_expand_fromdot(state, state->dots[i], sctx); |
| 1823 | |
| 1824 | return foreach_tile(state, solver_expand_postcb, IMPOSSIBLE_QUITS, sctx); |
| 1825 | } |
| 1826 | |
| 1827 | struct recurse_ctx { |
| 1828 | space *best; |
| 1829 | int bestn; |
| 1830 | }; |
| 1831 | |
| 1832 | static int solver_recurse_cb(game_state *state, space *tile, void *ctx) |
| 1833 | { |
| 1834 | struct recurse_ctx *rctx = (struct recurse_ctx *)ctx; |
| 1835 | int i, n = 0; |
| 1836 | |
| 1837 | assert(tile->type == s_tile); |
| 1838 | if (tile->flags & F_TILE_ASSOC) return 0; |
| 1839 | |
| 1840 | /* We're unassociated: count up all the dots we could associate with. */ |
| 1841 | for (i = 0; i < state->ndots; i++) { |
| 1842 | if (dotfortile(state, tile, state->dots[i])) |
| 1843 | n++; |
| 1844 | } |
| 1845 | if (n > rctx->bestn) { |
| 1846 | rctx->bestn = n; |
| 1847 | rctx->best = tile; |
| 1848 | } |
| 1849 | return 0; |
| 1850 | } |
| 1851 | |
| 1852 | static int solver_state(game_state *state, int maxdiff); |
| 1853 | |
| 1854 | #define MAXRECURSE 5 |
| 1855 | |
| 1856 | static int solver_recurse(game_state *state, int maxdiff) |
| 1857 | { |
| 1858 | int diff = DIFF_IMPOSSIBLE, ret, n, gsz = state->sx * state->sy; |
| 1859 | space *ingrid, *outgrid = NULL, *bestopp; |
| 1860 | struct recurse_ctx rctx; |
| 1861 | |
| 1862 | if (solver_recurse_depth >= MAXRECURSE) { |
| 1863 | solvep(("Limiting recursion to %d, returning.", MAXRECURSE)); |
| 1864 | return DIFF_UNFINISHED; |
| 1865 | } |
| 1866 | |
| 1867 | /* Work out the cell to recurse on; go through all unassociated tiles |
| 1868 | * and find which one has the most possible dots it could associate |
| 1869 | * with. */ |
| 1870 | rctx.best = NULL; |
| 1871 | rctx.bestn = 0; |
| 1872 | |
| 1873 | foreach_tile(state, solver_recurse_cb, 0, &rctx); |
| 1874 | if (rctx.bestn == 0) return DIFF_IMPOSSIBLE; /* or assert? */ |
| 1875 | assert(rctx.best); |
| 1876 | |
| 1877 | solvep(("%*sRecursing around %d,%d, with %d possible dots.\n", |
| 1878 | solver_recurse_depth*4, "", |
| 1879 | rctx.best->x, rctx.best->y, rctx.bestn)); |
| 1880 | |
| 1881 | #ifdef STANDALONE_SOLVER |
| 1882 | solver_recurse_depth++; |
| 1883 | #endif |
| 1884 | |
| 1885 | ingrid = snewn(gsz, struct space); |
| 1886 | memcpy(ingrid, state->grid, gsz * sizeof(struct space)); |
| 1887 | |
| 1888 | for (n = 0; n < state->ndots; n++) { |
| 1889 | memcpy(state->grid, ingrid, gsz * sizeof(struct space)); |
| 1890 | |
| 1891 | if (!dotfortile(state, rctx.best, state->dots[n])) continue; |
| 1892 | |
| 1893 | /* set cell (temporarily) pointing to that dot. */ |
| 1894 | solver_add_assoc(state, rctx.best, |
| 1895 | state->dots[n]->x, state->dots[n]->y, |
| 1896 | "Attempting for recursion"); |
| 1897 | |
| 1898 | ret = solver_state(state, maxdiff); |
| 1899 | |
| 1900 | if (diff == DIFF_IMPOSSIBLE && ret != DIFF_IMPOSSIBLE) { |
| 1901 | /* we found our first solved grid; copy it away. */ |
| 1902 | assert(!outgrid); |
| 1903 | outgrid = snewn(gsz, struct space); |
| 1904 | memcpy(outgrid, state->grid, gsz * sizeof(struct space)); |
| 1905 | } |
| 1906 | /* reset cell back to unassociated. */ |
| 1907 | bestopp = tile_opposite(state, rctx.best); |
| 1908 | assert(bestopp && bestopp->flags & F_TILE_ASSOC); |
| 1909 | |
| 1910 | remove_assoc(state, rctx.best); |
| 1911 | remove_assoc(state, bestopp); |
| 1912 | |
| 1913 | if (ret == DIFF_AMBIGUOUS || ret == DIFF_UNFINISHED) |
| 1914 | diff = ret; |
| 1915 | else if (ret == DIFF_IMPOSSIBLE) |
| 1916 | /* no change */; |
| 1917 | else { |
| 1918 | /* precisely one solution */ |
| 1919 | if (diff == DIFF_IMPOSSIBLE) |
| 1920 | diff = DIFF_UNREASONABLE; |
| 1921 | else |
| 1922 | diff = DIFF_AMBIGUOUS; |
| 1923 | } |
| 1924 | /* if we've found >1 solution, or ran out of recursion, |
| 1925 | * give up immediately. */ |
| 1926 | if (diff == DIFF_AMBIGUOUS || diff == DIFF_UNFINISHED) |
| 1927 | break; |
| 1928 | } |
| 1929 | |
| 1930 | #ifdef STANDALONE_SOLVER |
| 1931 | solver_recurse_depth--; |
| 1932 | #endif |
| 1933 | |
| 1934 | if (outgrid) { |
| 1935 | /* we found (at least one) soln; copy it back to state */ |
| 1936 | memcpy(state->grid, outgrid, gsz * sizeof(struct space)); |
| 1937 | sfree(outgrid); |
| 1938 | } |
| 1939 | sfree(ingrid); |
| 1940 | return diff; |
| 1941 | } |
| 1942 | |
| 1943 | static int solver_state(game_state *state, int maxdiff) |
| 1944 | { |
| 1945 | solver_ctx *sctx = new_solver(state); |
| 1946 | int ret, diff = DIFF_NORMAL; |
| 1947 | |
| 1948 | ret = solver_obvious(state); |
| 1949 | if (ret < 0) { |
| 1950 | diff = DIFF_IMPOSSIBLE; |
| 1951 | goto got_result; |
| 1952 | } |
| 1953 | |
| 1954 | #define CHECKRET(d) do { \ |
| 1955 | if (ret < 0) { diff = DIFF_IMPOSSIBLE; goto got_result; } \ |
| 1956 | if (ret > 0) { diff = max(diff, (d)); goto cont; } \ |
| 1957 | } while(0) |
| 1958 | |
| 1959 | while (1) { |
| 1960 | cont: |
| 1961 | ret = foreach_edge(state, solver_lines_opposite_cb, |
| 1962 | IMPOSSIBLE_QUITS, sctx); |
| 1963 | CHECKRET(DIFF_NORMAL); |
| 1964 | |
| 1965 | ret = foreach_tile(state, solver_spaces_oneposs_cb, |
| 1966 | IMPOSSIBLE_QUITS, sctx); |
| 1967 | CHECKRET(DIFF_NORMAL); |
| 1968 | |
| 1969 | ret = solver_expand_dots(state, sctx); |
| 1970 | CHECKRET(DIFF_NORMAL); |
| 1971 | |
| 1972 | if (maxdiff <= DIFF_NORMAL) |
| 1973 | break; |
| 1974 | |
| 1975 | /* harder still? */ |
| 1976 | |
| 1977 | /* if we reach here, we've made no deductions, so we terminate. */ |
| 1978 | break; |
| 1979 | } |
| 1980 | |
| 1981 | if (check_complete(state, 0)) goto got_result; |
| 1982 | |
| 1983 | diff = (maxdiff >= DIFF_UNREASONABLE) ? |
| 1984 | solver_recurse(state, maxdiff) : DIFF_UNFINISHED; |
| 1985 | |
| 1986 | got_result: |
| 1987 | free_solver(sctx); |
| 1988 | #ifndef STANDALONE_SOLVER |
| 1989 | debug(("solver_state ends:\n")); |
| 1990 | dbg_state(state); |
| 1991 | #endif |
| 1992 | |
| 1993 | return diff; |
| 1994 | } |
| 1995 | |
| 1996 | #ifndef EDITOR |
| 1997 | static char *solve_game(game_state *state, game_state *currstate, |
| 1998 | char *aux, char **error) |
| 1999 | { |
| 2000 | game_state *tosolve; |
| 2001 | char *ret; |
| 2002 | int i; |
| 2003 | int diff; |
| 2004 | |
| 2005 | tosolve = dup_game(currstate); |
| 2006 | diff = solver_state(tosolve, DIFF_UNREASONABLE); |
| 2007 | if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) { |
| 2008 | debug(("solve_game solved with current state.\n")); |
| 2009 | goto solved; |
| 2010 | } |
| 2011 | free_game(tosolve); |
| 2012 | |
| 2013 | tosolve = dup_game(state); |
| 2014 | diff = solver_state(tosolve, DIFF_UNREASONABLE); |
| 2015 | if (diff != DIFF_UNFINISHED && diff != DIFF_IMPOSSIBLE) { |
| 2016 | debug(("solve_game solved with original state.\n")); |
| 2017 | goto solved; |
| 2018 | } |
| 2019 | free_game(tosolve); |
| 2020 | |
| 2021 | return NULL; |
| 2022 | |
| 2023 | solved: |
| 2024 | /* |
| 2025 | * Clear tile associations: the solution will only include the |
| 2026 | * edges. |
| 2027 | */ |
| 2028 | for (i = 0; i < tosolve->sx*tosolve->sy; i++) |
| 2029 | tosolve->grid[i].flags &= ~F_TILE_ASSOC; |
| 2030 | ret = diff_game(currstate, tosolve, 1); |
| 2031 | free_game(tosolve); |
| 2032 | return ret; |
| 2033 | } |
| 2034 | #endif |
| 2035 | |
| 2036 | /* ---------------------------------------------------------- |
| 2037 | * User interface. |
| 2038 | */ |
| 2039 | |
| 2040 | struct game_ui { |
| 2041 | int dragging; |
| 2042 | int dx, dy; /* pixel coords of drag pos. */ |
| 2043 | int dotx, doty; /* grid coords of dot we're dragging from. */ |
| 2044 | int srcx, srcy; /* grid coords of drag start */ |
| 2045 | }; |
| 2046 | |
| 2047 | static game_ui *new_ui(game_state *state) |
| 2048 | { |
| 2049 | game_ui *ui = snew(game_ui); |
| 2050 | ui->dragging = FALSE; |
| 2051 | return ui; |
| 2052 | } |
| 2053 | |
| 2054 | static void free_ui(game_ui *ui) |
| 2055 | { |
| 2056 | sfree(ui); |
| 2057 | } |
| 2058 | |
| 2059 | static char *encode_ui(game_ui *ui) |
| 2060 | { |
| 2061 | return NULL; |
| 2062 | } |
| 2063 | |
| 2064 | static void decode_ui(game_ui *ui, char *encoding) |
| 2065 | { |
| 2066 | } |
| 2067 | |
| 2068 | static void game_changed_state(game_ui *ui, game_state *oldstate, |
| 2069 | game_state *newstate) |
| 2070 | { |
| 2071 | } |
| 2072 | |
| 2073 | #define FLASH_TIME 0.15F |
| 2074 | |
| 2075 | #define PREFERRED_TILE_SIZE 32 |
| 2076 | #define TILE_SIZE (ds->tilesize) |
| 2077 | #define DOT_SIZE (TILE_SIZE / 4) |
| 2078 | #define EDGE_THICKNESS (TILE_SIZE / 16) |
| 2079 | #define BORDER TILE_SIZE |
| 2080 | |
| 2081 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) |
| 2082 | #define SCOORD(x) ( ((x) * TILE_SIZE)/2 + BORDER ) |
| 2083 | #define FROMCOORD(x) ( ((x) - BORDER) / TILE_SIZE ) |
| 2084 | |
| 2085 | #define DRAW_WIDTH (BORDER * 2 + ds->w * TILE_SIZE) |
| 2086 | #define DRAW_HEIGHT (BORDER * 2 + ds->h * TILE_SIZE) |
| 2087 | |
| 2088 | struct game_drawstate { |
| 2089 | int started; |
| 2090 | int w, h; |
| 2091 | int tilesize; |
| 2092 | unsigned long *grid; |
| 2093 | int *dx, *dy; |
| 2094 | blitter *bl; |
| 2095 | |
| 2096 | int dragging, dragx, dragy; |
| 2097 | |
| 2098 | int *colour_scratch; |
| 2099 | }; |
| 2100 | |
| 2101 | #define CORNER_TOLERANCE 0.15F |
| 2102 | #define CENTRE_TOLERANCE 0.15F |
| 2103 | |
| 2104 | /* |
| 2105 | * Round FP coordinates to the centre of the nearest edge. |
| 2106 | */ |
| 2107 | #ifndef EDITOR |
| 2108 | static void coord_round_to_edge(float x, float y, int *xr, int *yr) |
| 2109 | { |
| 2110 | float xs, ys, xv, yv, dx, dy; |
| 2111 | |
| 2112 | /* |
| 2113 | * Find the nearest square-centre. |
| 2114 | */ |
| 2115 | xs = (float)floor(x) + 0.5F; |
| 2116 | ys = (float)floor(y) + 0.5F; |
| 2117 | |
| 2118 | /* |
| 2119 | * Find the nearest grid vertex. |
| 2120 | */ |
| 2121 | xv = (float)floor(x + 0.5F); |
| 2122 | yv = (float)floor(y + 0.5F); |
| 2123 | |
| 2124 | /* |
| 2125 | * Determine whether the horizontal or vertical edge from that |
| 2126 | * vertex alongside that square is closer to us, by comparing |
| 2127 | * distances from the square cente. |
| 2128 | */ |
| 2129 | dx = (float)fabs(x - xs); |
| 2130 | dy = (float)fabs(y - ys); |
| 2131 | if (dx > dy) { |
| 2132 | /* Vertical edge: x-coord of corner, |
| 2133 | * y-coord of square centre. */ |
| 2134 | *xr = 2 * (int)xv; |
| 2135 | *yr = 1 + 2 * (int)floor(ys); |
| 2136 | } else { |
| 2137 | /* Horizontal edge: x-coord of square centre, |
| 2138 | * y-coord of corner. */ |
| 2139 | *xr = 1 + 2 * (int)floor(xs); |
| 2140 | *yr = 2 * (int)yv; |
| 2141 | } |
| 2142 | } |
| 2143 | #endif |
| 2144 | |
| 2145 | #ifdef EDITOR |
| 2146 | static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, |
| 2147 | int x, int y, int button) |
| 2148 | { |
| 2149 | char buf[80]; |
| 2150 | int px, py; |
| 2151 | struct space *sp; |
| 2152 | |
| 2153 | px = 2*FROMCOORD((float)x) + 0.5; |
| 2154 | py = 2*FROMCOORD((float)y) + 0.5; |
| 2155 | |
| 2156 | state->cdiff = -1; |
| 2157 | |
| 2158 | if (button == 'C' || button == 'c') return dupstr("C"); |
| 2159 | |
| 2160 | if (button == 'S' || button == 's') { |
| 2161 | char *ret; |
| 2162 | game_state *tmp = dup_game(state); |
| 2163 | state->cdiff = solver_state(tmp, DIFF_UNREASONABLE-1); |
| 2164 | ret = diff_game(state, tmp, 0); |
| 2165 | free_game(tmp); |
| 2166 | return ret; |
| 2167 | } |
| 2168 | |
| 2169 | if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { |
| 2170 | if (!INUI(state, px, py)) return NULL; |
| 2171 | sp = &SPACE(state, px, py); |
| 2172 | if (!dot_is_possible(state, sp, 1)) return NULL; |
| 2173 | sprintf(buf, "%c%d,%d", |
| 2174 | (char)((button == LEFT_BUTTON) ? 'D' : 'd'), px, py); |
| 2175 | return dupstr(buf); |
| 2176 | } |
| 2177 | |
| 2178 | return NULL; |
| 2179 | } |
| 2180 | #else |
| 2181 | static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, |
| 2182 | int x, int y, int button) |
| 2183 | { |
| 2184 | /* UI operations (play mode): |
| 2185 | * |
| 2186 | * Toggle edge (set/unset) (left-click on edge) |
| 2187 | * Associate space with dot (left-drag from dot) |
| 2188 | * Unassociate space (left-drag from space off grid) |
| 2189 | * Autofill lines around shape? (right-click?) |
| 2190 | * |
| 2191 | * (edit mode; will clear all lines/associations) |
| 2192 | * |
| 2193 | * Add or remove dot (left-click) |
| 2194 | */ |
| 2195 | char buf[80]; |
| 2196 | const char *sep; |
| 2197 | int px, py; |
| 2198 | struct space *sp, *dot; |
| 2199 | |
| 2200 | if (button == 'H' || button == 'h' || |
| 2201 | button == 'S' || button == 's') { |
| 2202 | char *ret; |
| 2203 | game_state *tmp = dup_game(state); |
| 2204 | if (button == 'H' || button == 'h') |
| 2205 | solver_obvious(tmp); |
| 2206 | else |
| 2207 | solver_state(tmp, DIFF_UNREASONABLE-1); |
| 2208 | ret = diff_game(state, tmp, 1); |
| 2209 | free_game(tmp); |
| 2210 | return ret; |
| 2211 | } |
| 2212 | |
| 2213 | if (button == LEFT_BUTTON) { |
| 2214 | coord_round_to_edge(FROMCOORD((float)x), FROMCOORD((float)y), |
| 2215 | &px, &py); |
| 2216 | |
| 2217 | if (!INUI(state, px, py)) return NULL; |
| 2218 | |
| 2219 | sp = &SPACE(state, px, py); |
| 2220 | assert(sp->type == s_edge); |
| 2221 | { |
| 2222 | sprintf(buf, "E%d,%d", px, py); |
| 2223 | return dupstr(buf); |
| 2224 | } |
| 2225 | } else if (button == RIGHT_BUTTON) { |
| 2226 | int px1, py1; |
| 2227 | |
| 2228 | px = (int)(2*FROMCOORD((float)x) + 0.5); |
| 2229 | py = (int)(2*FROMCOORD((float)y) + 0.5); |
| 2230 | |
| 2231 | dot = NULL; |
| 2232 | |
| 2233 | /* |
| 2234 | * If there's a dot anywhere nearby, we pick up an arrow |
| 2235 | * pointing at that dot. |
| 2236 | */ |
| 2237 | for (py1 = py-1; py1 <= py+1; py1++) |
| 2238 | for (px1 = px-1; px1 <= px+1; px1++) { |
| 2239 | if (px1 >= 0 && px1 < state->sx && |
| 2240 | py1 >= 0 && py1 < state->sx && |
| 2241 | x >= SCOORD(px1-1) && x < SCOORD(px1+1) && |
| 2242 | y >= SCOORD(py1-1) && y < SCOORD(py1+1) && |
| 2243 | SPACE(state, px1, py1).flags & F_DOT) { |
| 2244 | /* |
| 2245 | * Found a dot. Begin a drag from it. |
| 2246 | */ |
| 2247 | dot = &SPACE(state, px1, py1); |
| 2248 | ui->srcx = px1; |
| 2249 | ui->srcy = py1; |
| 2250 | goto done; /* multi-level break */ |
| 2251 | } |
| 2252 | } |
| 2253 | |
| 2254 | /* |
| 2255 | * Otherwise, find the nearest _square_, and pick up the |
| 2256 | * same arrow as it's got on it, if any. |
| 2257 | */ |
| 2258 | if (!dot) { |
| 2259 | px = 2*FROMCOORD(x+TILE_SIZE) - 1; |
| 2260 | py = 2*FROMCOORD(y+TILE_SIZE) - 1; |
| 2261 | if (px >= 0 && px < state->sx && py >= 0 && py < state->sx) { |
| 2262 | sp = &SPACE(state, px, py); |
| 2263 | if (sp->flags & F_TILE_ASSOC) { |
| 2264 | dot = &SPACE(state, sp->dotx, sp->doty); |
| 2265 | ui->srcx = px; |
| 2266 | ui->srcy = py; |
| 2267 | } |
| 2268 | } |
| 2269 | } |
| 2270 | |
| 2271 | done: |
| 2272 | /* |
| 2273 | * Now, if we've managed to find a dot, begin a drag. |
| 2274 | */ |
| 2275 | if (dot) { |
| 2276 | ui->dragging = TRUE; |
| 2277 | ui->dx = x; |
| 2278 | ui->dy = y; |
| 2279 | ui->dotx = dot->x; |
| 2280 | ui->doty = dot->y; |
| 2281 | return ""; |
| 2282 | } |
| 2283 | } else if (button == RIGHT_DRAG && ui->dragging) { |
| 2284 | /* just move the drag coords. */ |
| 2285 | ui->dx = x; |
| 2286 | ui->dy = y; |
| 2287 | return ""; |
| 2288 | } else if (button == RIGHT_RELEASE && ui->dragging) { |
| 2289 | ui->dragging = FALSE; |
| 2290 | |
| 2291 | /* |
| 2292 | * Drags are always targeted at a single square. |
| 2293 | */ |
| 2294 | px = 2*FROMCOORD(x+TILE_SIZE) - 1; |
| 2295 | py = 2*FROMCOORD(y+TILE_SIZE) - 1; |
| 2296 | |
| 2297 | /* |
| 2298 | * Dragging an arrow on to the same square it started from |
| 2299 | * is a null move; just update the ui and finish. |
| 2300 | */ |
| 2301 | if (px == ui->srcx && py == ui->srcy) |
| 2302 | return ""; |
| 2303 | |
| 2304 | sep = ""; |
| 2305 | buf[0] = '\0'; |
| 2306 | |
| 2307 | /* |
| 2308 | * Otherwise, we remove the arrow from its starting |
| 2309 | * square if we didn't start from a dot... |
| 2310 | */ |
| 2311 | if ((ui->srcx != ui->dotx || ui->srcy != ui->doty) && |
| 2312 | SPACE(state, ui->srcx, ui->srcy).flags & F_TILE_ASSOC) { |
| 2313 | sprintf(buf + strlen(buf), "%sU%d,%d", sep, ui->srcx, ui->srcy); |
| 2314 | sep = ";"; |
| 2315 | } |
| 2316 | |
| 2317 | /* |
| 2318 | * ... and if the square we're moving it _to_ is valid, we |
| 2319 | * add one there instead. |
| 2320 | */ |
| 2321 | if (INUI(state, px, py)) { |
| 2322 | sp = &SPACE(state, px, py); |
| 2323 | |
| 2324 | if (!(sp->flags & F_DOT) && !(sp->flags & F_TILE_ASSOC)) |
| 2325 | sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d", |
| 2326 | sep, px, py, ui->dotx, ui->doty); |
| 2327 | } |
| 2328 | |
| 2329 | if (buf[0]) |
| 2330 | return dupstr(buf); |
| 2331 | else |
| 2332 | return ""; |
| 2333 | } |
| 2334 | |
| 2335 | return NULL; |
| 2336 | } |
| 2337 | #endif |
| 2338 | |
| 2339 | static int check_complete_in_play(game_state *state, int *dsf, int *colours) |
| 2340 | { |
| 2341 | int w = state->w, h = state->h; |
| 2342 | int x, y, i, ret; |
| 2343 | |
| 2344 | int free_dsf; |
| 2345 | struct sqdata { |
| 2346 | int minx, miny, maxx, maxy; |
| 2347 | int cx, cy; |
| 2348 | int valid, colour; |
| 2349 | } *sqdata; |
| 2350 | |
| 2351 | if (!dsf) { |
| 2352 | dsf = snew_dsf(w*h); |
| 2353 | free_dsf = TRUE; |
| 2354 | } else { |
| 2355 | dsf_init(dsf, w*h); |
| 2356 | free_dsf = FALSE; |
| 2357 | } |
| 2358 | |
| 2359 | /* |
| 2360 | * During actual game play, completion checking is done on the |
| 2361 | * basis of the edges rather than the square associations. So |
| 2362 | * first we must go through the grid figuring out the connected |
| 2363 | * components into which the edges divide it. |
| 2364 | */ |
| 2365 | for (y = 0; y < h; y++) |
| 2366 | for (x = 0; x < w; x++) { |
| 2367 | if (y+1 < h && !(SPACE(state, 2*x+1, 2*y+2).flags & F_EDGE_SET)) |
| 2368 | dsf_merge(dsf, y*w+x, (y+1)*w+x); |
| 2369 | if (x+1 < w && !(SPACE(state, 2*x+2, 2*y+1).flags & F_EDGE_SET)) |
| 2370 | dsf_merge(dsf, y*w+x, y*w+(x+1)); |
| 2371 | } |
| 2372 | |
| 2373 | /* |
| 2374 | * That gives us our connected components. Now, for each |
| 2375 | * component, decide whether it's _valid_. A valid component is |
| 2376 | * one which: |
| 2377 | * |
| 2378 | * - is 180-degree rotationally symmetric |
| 2379 | * - has a dot at its centre of symmetry |
| 2380 | * - has no other dots anywhere within it (including on its |
| 2381 | * boundary) |
| 2382 | * - contains no internal edges (i.e. edges separating two |
| 2383 | * squares which are both part of the component). |
| 2384 | */ |
| 2385 | |
| 2386 | /* |
| 2387 | * First, go through the grid finding the bounding box of each |
| 2388 | * component. |
| 2389 | */ |
| 2390 | sqdata = snewn(w*h, struct sqdata); |
| 2391 | for (i = 0; i < w*h; i++) { |
| 2392 | sqdata[i].minx = w+1; |
| 2393 | sqdata[i].miny = h+1; |
| 2394 | sqdata[i].maxx = sqdata[i].maxy = -1; |
| 2395 | sqdata[i].valid = FALSE; |
| 2396 | } |
| 2397 | for (y = 0; y < h; y++) |
| 2398 | for (x = 0; x < w; x++) { |
| 2399 | i = dsf_canonify(dsf, y*w+x); |
| 2400 | if (sqdata[i].minx > x) |
| 2401 | sqdata[i].minx = x; |
| 2402 | if (sqdata[i].maxx < x) |
| 2403 | sqdata[i].maxx = x; |
| 2404 | if (sqdata[i].miny > y) |
| 2405 | sqdata[i].miny = y; |
| 2406 | if (sqdata[i].maxy < y) |
| 2407 | sqdata[i].maxy = y; |
| 2408 | sqdata[i].valid = TRUE; |
| 2409 | } |
| 2410 | |
| 2411 | /* |
| 2412 | * Now we're in a position to loop over each actual component |
| 2413 | * and figure out where its centre of symmetry has to be if |
| 2414 | * it's anywhere. |
| 2415 | */ |
| 2416 | for (i = 0; i < w*h; i++) |
| 2417 | if (sqdata[i].valid) { |
| 2418 | sqdata[i].cx = sqdata[i].minx + sqdata[i].maxx + 1; |
| 2419 | sqdata[i].cy = sqdata[i].miny + sqdata[i].maxy + 1; |
| 2420 | if (!(SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT)) |
| 2421 | sqdata[i].valid = FALSE; /* no dot at centre of symmetry */ |
| 2422 | if (SPACE(state, sqdata[i].cx, sqdata[i].cy).flags & F_DOT_BLACK) |
| 2423 | sqdata[i].colour = 2; |
| 2424 | else |
| 2425 | sqdata[i].colour = 1; |
| 2426 | } |
| 2427 | |
| 2428 | /* |
| 2429 | * Now we loop over the whole grid again, this time finding |
| 2430 | * extraneous dots (any dot which wholly or partially overlaps |
| 2431 | * a square and is not at the centre of symmetry of that |
| 2432 | * square's component disqualifies the component from validity) |
| 2433 | * and extraneous edges (any edge separating two squares |
| 2434 | * belonging to the same component also disqualifies that |
| 2435 | * component). |
| 2436 | */ |
| 2437 | for (y = 1; y < state->sy-1; y++) |
| 2438 | for (x = 1; x < state->sx-1; x++) { |
| 2439 | space *sp = &SPACE(state, x, y); |
| 2440 | |
| 2441 | if (sp->flags & F_DOT) { |
| 2442 | /* |
| 2443 | * There's a dot here. Use it to disqualify any |
| 2444 | * component which deserves it. |
| 2445 | */ |
| 2446 | int cx, cy; |
| 2447 | for (cy = (y-1) >> 1; cy <= y >> 1; cy++) |
| 2448 | for (cx = (x-1) >> 1; cx <= x >> 1; cx++) { |
| 2449 | i = dsf_canonify(dsf, cy*w+cx); |
| 2450 | if (x != sqdata[i].cx || y != sqdata[i].cy) |
| 2451 | sqdata[i].valid = FALSE; |
| 2452 | } |
| 2453 | } |
| 2454 | |
| 2455 | if (sp->flags & F_EDGE_SET) { |
| 2456 | /* |
| 2457 | * There's an edge here. Use it to disqualify a |
| 2458 | * component if necessary. |
| 2459 | */ |
| 2460 | int cx1 = (x-1) >> 1, cx2 = x >> 1; |
| 2461 | int cy1 = (y-1) >> 1, cy2 = y >> 1; |
| 2462 | assert((cx1==cx2) ^ (cy1==cy2)); |
| 2463 | i = dsf_canonify(dsf, cy1*w+cx1); |
| 2464 | if (i == dsf_canonify(dsf, cy2*w+cx2)) |
| 2465 | sqdata[i].valid = FALSE; |
| 2466 | } |
| 2467 | } |
| 2468 | |
| 2469 | /* |
| 2470 | * And finally we test rotational symmetry: for each square in |
| 2471 | * the grid, find which component it's in, test that that |
| 2472 | * component also has a square in the symmetric position, and |
| 2473 | * disqualify it if it doesn't. |
| 2474 | */ |
| 2475 | for (y = 0; y < h; y++) |
| 2476 | for (x = 0; x < w; x++) { |
| 2477 | int x2, y2; |
| 2478 | |
| 2479 | i = dsf_canonify(dsf, y*w+x); |
| 2480 | |
| 2481 | x2 = sqdata[i].cx - 1 - x; |
| 2482 | y2 = sqdata[i].cy - 1 - y; |
| 2483 | if (i != dsf_canonify(dsf, y2*w+x2)) |
| 2484 | sqdata[i].valid = FALSE; |
| 2485 | } |
| 2486 | |
| 2487 | /* |
| 2488 | * That's it. We now have all the connected components marked |
| 2489 | * as valid or not valid. So now we return a `colours' array if |
| 2490 | * we were asked for one, and also we return an overall |
| 2491 | * true/false value depending on whether _every_ square in the |
| 2492 | * grid is part of a valid component. |
| 2493 | */ |
| 2494 | ret = TRUE; |
| 2495 | for (i = 0; i < w*h; i++) { |
| 2496 | int ci = dsf_canonify(dsf, i); |
| 2497 | int thisok = sqdata[ci].valid; |
| 2498 | if (colours) |
| 2499 | colours[i] = thisok ? sqdata[ci].colour : 0; |
| 2500 | ret = ret && thisok; |
| 2501 | } |
| 2502 | |
| 2503 | sfree(sqdata); |
| 2504 | if (free_dsf) |
| 2505 | sfree(dsf); |
| 2506 | |
| 2507 | return ret; |
| 2508 | } |
| 2509 | |
| 2510 | static game_state *execute_move(game_state *state, char *move) |
| 2511 | { |
| 2512 | int x, y, ax, ay, n, dx, dy; |
| 2513 | game_state *ret = dup_game(state); |
| 2514 | struct space *sp, *dot; |
| 2515 | |
| 2516 | debug(("%s\n", move)); |
| 2517 | |
| 2518 | while (*move) { |
| 2519 | char c = *move; |
| 2520 | if (c == 'E' || c == 'U' || c == 'M' |
| 2521 | #ifdef EDITOR |
| 2522 | || c == 'D' || c == 'd' |
| 2523 | #endif |
| 2524 | ) { |
| 2525 | move++; |
| 2526 | if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || |
| 2527 | !INUI(state, x, y)) |
| 2528 | goto badmove; |
| 2529 | |
| 2530 | sp = &SPACE(ret, x, y); |
| 2531 | #ifdef EDITOR |
| 2532 | if (c == 'D' || c == 'd') { |
| 2533 | unsigned int currf, newf, maskf; |
| 2534 | |
| 2535 | if (!dot_is_possible(state, sp, 1)) goto badmove; |
| 2536 | |
| 2537 | newf = F_DOT | (c == 'd' ? F_DOT_BLACK : 0); |
| 2538 | currf = GRID(ret, grid, x, y).flags; |
| 2539 | maskf = F_DOT | F_DOT_BLACK; |
| 2540 | /* if we clicked 'white dot': |
| 2541 | * white --> empty, empty --> white, black --> white. |
| 2542 | * if we clicker 'black dot': |
| 2543 | * black --> empty, empty --> black, white --> black. |
| 2544 | */ |
| 2545 | if (currf & maskf) { |
| 2546 | sp->flags &= ~maskf; |
| 2547 | if ((currf & maskf) != newf) |
| 2548 | sp->flags |= newf; |
| 2549 | } else |
| 2550 | sp->flags |= newf; |
| 2551 | sp->nassoc = 0; /* edit-mode disallows associations. */ |
| 2552 | game_update_dots(ret); |
| 2553 | } else |
| 2554 | #endif |
| 2555 | if (c == 'E') { |
| 2556 | if (sp->type != s_edge) goto badmove; |
| 2557 | sp->flags ^= F_EDGE_SET; |
| 2558 | } else if (c == 'U') { |
| 2559 | if (sp->type != s_tile || !(sp->flags & F_TILE_ASSOC)) |
| 2560 | goto badmove; |
| 2561 | remove_assoc(ret, sp); |
| 2562 | } else if (c == 'M') { |
| 2563 | if (!(sp->flags & F_DOT)) goto badmove; |
| 2564 | sp->flags ^= F_DOT_HOLD; |
| 2565 | } |
| 2566 | move += n; |
| 2567 | } else if (c == 'A' || c == 'a') { |
| 2568 | move++; |
| 2569 | if (sscanf(move, "%d,%d,%d,%d%n", &x, &y, &ax, &ay, &n) != 4 || |
| 2570 | x < 1 || y < 1 || x >= (state->sx-1) || y >= (state->sy-1) || |
| 2571 | ax < 1 || ay < 1 || ax >= (state->sx-1) || ay >= (state->sy-1)) |
| 2572 | goto badmove; |
| 2573 | |
| 2574 | dot = &GRID(ret, grid, ax, ay); |
| 2575 | if (!(dot->flags & F_DOT))goto badmove; |
| 2576 | if (dot->flags & F_DOT_HOLD) goto badmove; |
| 2577 | |
| 2578 | for (dx = -1; dx <= 1; dx++) { |
| 2579 | for (dy = -1; dy <= 1; dy++) { |
| 2580 | sp = &GRID(ret, grid, x+dx, y+dy); |
| 2581 | if (sp->type != s_tile) continue; |
| 2582 | if (sp->flags & F_TILE_ASSOC) { |
| 2583 | space *dot = &SPACE(state, sp->dotx, sp->doty); |
| 2584 | if (dot->flags & F_DOT_HOLD) continue; |
| 2585 | } |
| 2586 | add_assoc(state, sp, dot); |
| 2587 | } |
| 2588 | } |
| 2589 | move += n; |
| 2590 | #ifdef EDITOR |
| 2591 | } else if (c == 'C') { |
| 2592 | move++; |
| 2593 | clear_game(ret, 1); |
| 2594 | #endif |
| 2595 | } else if (c == 'S') { |
| 2596 | move++; |
| 2597 | ret->used_solve = 1; |
| 2598 | } else |
| 2599 | goto badmove; |
| 2600 | |
| 2601 | if (*move == ';') |
| 2602 | move++; |
| 2603 | else if (*move) |
| 2604 | goto badmove; |
| 2605 | } |
| 2606 | if (check_complete_in_play(ret, NULL, NULL)) |
| 2607 | ret->completed = 1; |
| 2608 | return ret; |
| 2609 | |
| 2610 | badmove: |
| 2611 | free_game(ret); |
| 2612 | return NULL; |
| 2613 | } |
| 2614 | |
| 2615 | /* ---------------------------------------------------------------------- |
| 2616 | * Drawing routines. |
| 2617 | */ |
| 2618 | |
| 2619 | /* Lines will be much smaller size than squares; say, 1/8 the size? |
| 2620 | * |
| 2621 | * Need a 'top-left corner of location XxY' to take this into account; |
| 2622 | * alternaticaly, that could give the middle of that location, and the |
| 2623 | * drawing code would just know the expected dimensions. |
| 2624 | * |
| 2625 | * We also need something to take a click and work out what it was |
| 2626 | * we were interested in. Clicking on vertices is required because |
| 2627 | * we may want to drag from them, for example. |
| 2628 | */ |
| 2629 | |
| 2630 | static void game_compute_size(game_params *params, int sz, |
| 2631 | int *x, int *y) |
| 2632 | { |
| 2633 | struct { int tilesize, w, h; } ads, *ds = &ads; |
| 2634 | |
| 2635 | ds->tilesize = sz; |
| 2636 | ds->w = params->w; |
| 2637 | ds->h = params->h; |
| 2638 | |
| 2639 | *x = DRAW_WIDTH; |
| 2640 | *y = DRAW_HEIGHT; |
| 2641 | } |
| 2642 | |
| 2643 | static void game_set_size(drawing *dr, game_drawstate *ds, |
| 2644 | game_params *params, int sz) |
| 2645 | { |
| 2646 | ds->tilesize = sz; |
| 2647 | |
| 2648 | assert(TILE_SIZE > 0); |
| 2649 | |
| 2650 | assert(!ds->bl); |
| 2651 | ds->bl = blitter_new(dr, TILE_SIZE, TILE_SIZE); |
| 2652 | } |
| 2653 | |
| 2654 | static float *game_colours(frontend *fe, int *ncolours) |
| 2655 | { |
| 2656 | float *ret = snewn(3 * NCOLOURS, float); |
| 2657 | int i; |
| 2658 | |
| 2659 | /* |
| 2660 | * We call game_mkhighlight to ensure the background colour |
| 2661 | * isn't completely white. We don't actually use the high- and |
| 2662 | * lowlight colours it generates. |
| 2663 | */ |
| 2664 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_WHITEBG, COL_BLACKBG); |
| 2665 | |
| 2666 | for (i = 0; i < 3; i++) { |
| 2667 | /* |
| 2668 | * Currently, white dots and white-background squares are |
| 2669 | * both pure white. |
| 2670 | */ |
| 2671 | ret[COL_WHITEDOT * 3 + i] = 1.0F; |
| 2672 | ret[COL_WHITEBG * 3 + i] = 1.0F; |
| 2673 | |
| 2674 | /* |
| 2675 | * But black-background squares are a dark grey, whereas |
| 2676 | * black dots are really black. |
| 2677 | */ |
| 2678 | ret[COL_BLACKDOT * 3 + i] = 0.0F; |
| 2679 | ret[COL_BLACKBG * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.3F; |
| 2680 | |
| 2681 | /* |
| 2682 | * In unfilled squares, we draw a faint gridwork. |
| 2683 | */ |
| 2684 | ret[COL_GRID * 3 + i] = ret[COL_BACKGROUND * 3 + i] * 0.8F; |
| 2685 | |
| 2686 | /* |
| 2687 | * Edges and arrows are filled in in pure black. |
| 2688 | */ |
| 2689 | ret[COL_EDGE * 3 + i] = 0.0F; |
| 2690 | ret[COL_ARROW * 3 + i] = 0.0F; |
| 2691 | } |
| 2692 | |
| 2693 | #ifdef EDITOR |
| 2694 | /* tinge the edit background to bluey */ |
| 2695 | ret[COL_BACKGROUND * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.8F; |
| 2696 | ret[COL_BACKGROUND * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.8F; |
| 2697 | ret[COL_BACKGROUND * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 1.4F; |
| 2698 | if (ret[COL_BACKGROUND * 3 + 2] > 1.0F) ret[COL_BACKGROUND * 3 + 2] = 1.0F; |
| 2699 | #endif |
| 2700 | |
| 2701 | *ncolours = NCOLOURS; |
| 2702 | return ret; |
| 2703 | } |
| 2704 | |
| 2705 | static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) |
| 2706 | { |
| 2707 | struct game_drawstate *ds = snew(struct game_drawstate); |
| 2708 | int i; |
| 2709 | |
| 2710 | ds->started = 0; |
| 2711 | ds->w = state->w; |
| 2712 | ds->h = state->h; |
| 2713 | |
| 2714 | ds->grid = snewn(ds->w*ds->h, unsigned long); |
| 2715 | for (i = 0; i < ds->w*ds->h; i++) |
| 2716 | ds->grid[i] = 0xFFFFFFFFUL; |
| 2717 | ds->dx = snewn(ds->w*ds->h, int); |
| 2718 | ds->dy = snewn(ds->w*ds->h, int); |
| 2719 | |
| 2720 | ds->bl = NULL; |
| 2721 | ds->dragging = FALSE; |
| 2722 | ds->dragx = ds->dragy = 0; |
| 2723 | |
| 2724 | ds->colour_scratch = snewn(ds->w * ds->h, int); |
| 2725 | |
| 2726 | return ds; |
| 2727 | } |
| 2728 | |
| 2729 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) |
| 2730 | { |
| 2731 | sfree(ds->colour_scratch); |
| 2732 | if (ds->bl) blitter_free(dr, ds->bl); |
| 2733 | sfree(ds->dx); |
| 2734 | sfree(ds->dy); |
| 2735 | sfree(ds->grid); |
| 2736 | sfree(ds); |
| 2737 | } |
| 2738 | |
| 2739 | #define DRAW_EDGE_L 0x0001 |
| 2740 | #define DRAW_EDGE_R 0x0002 |
| 2741 | #define DRAW_EDGE_U 0x0004 |
| 2742 | #define DRAW_EDGE_D 0x0008 |
| 2743 | #define DRAW_CORNER_UL 0x0010 |
| 2744 | #define DRAW_CORNER_UR 0x0020 |
| 2745 | #define DRAW_CORNER_DL 0x0040 |
| 2746 | #define DRAW_CORNER_DR 0x0080 |
| 2747 | #define DRAW_WHITE 0x0100 |
| 2748 | #define DRAW_BLACK 0x0200 |
| 2749 | #define DRAW_ARROW 0x0400 |
| 2750 | #define DOT_SHIFT_C 11 |
| 2751 | #define DOT_SHIFT_M 2 |
| 2752 | #define DOT_WHITE 1UL |
| 2753 | #define DOT_BLACK 2UL |
| 2754 | |
| 2755 | /* |
| 2756 | * Draw an arrow centred on (cx,cy), pointing in the direction |
| 2757 | * (ddx,ddy). (I.e. pointing at the point (cx+ddx, cy+ddy). |
| 2758 | */ |
| 2759 | static void draw_arrow(drawing *dr, game_drawstate *ds, |
| 2760 | int cx, int cy, int ddx, int ddy) |
| 2761 | { |
| 2762 | float vlen = (float)sqrt(ddx*ddx+ddy*ddy); |
| 2763 | float xdx = ddx/vlen, xdy = ddy/vlen; |
| 2764 | float ydx = -xdy, ydy = xdx; |
| 2765 | int e1x = cx + (int)(xdx*TILE_SIZE/3), e1y = cy + (int)(xdy*TILE_SIZE/3); |
| 2766 | int e2x = cx - (int)(xdx*TILE_SIZE/3), e2y = cy - (int)(xdy*TILE_SIZE/3); |
| 2767 | int adx = (int)((ydx-xdx)*TILE_SIZE/8), ady = (int)((ydy-xdy)*TILE_SIZE/8); |
| 2768 | int adx2 = (int)((-ydx-xdx)*TILE_SIZE/8), ady2 = (int)((-ydy-xdy)*TILE_SIZE/8); |
| 2769 | |
| 2770 | draw_line(dr, e1x, e1y, e2x, e2y, COL_ARROW); |
| 2771 | draw_line(dr, e1x, e1y, e1x+adx, e1y+ady, COL_ARROW); |
| 2772 | draw_line(dr, e1x, e1y, e1x+adx2, e1y+ady2, COL_ARROW); |
| 2773 | } |
| 2774 | |
| 2775 | static void draw_square(drawing *dr, game_drawstate *ds, int x, int y, |
| 2776 | unsigned long flags, int ddx, int ddy) |
| 2777 | { |
| 2778 | int lx = COORD(x), ly = COORD(y); |
| 2779 | int dx, dy; |
| 2780 | int gridcol; |
| 2781 | |
| 2782 | clip(dr, lx, ly, TILE_SIZE, TILE_SIZE); |
| 2783 | |
| 2784 | /* |
| 2785 | * Draw the tile background. |
| 2786 | */ |
| 2787 | draw_rect(dr, lx, ly, TILE_SIZE, TILE_SIZE, |
| 2788 | (flags & DRAW_WHITE ? COL_WHITEBG : |
| 2789 | flags & DRAW_BLACK ? COL_BLACKBG : COL_BACKGROUND)); |
| 2790 | |
| 2791 | /* |
| 2792 | * Draw the grid. |
| 2793 | */ |
| 2794 | gridcol = (flags & DRAW_BLACK ? COL_BLACKDOT : COL_GRID); |
| 2795 | draw_rect(dr, lx, ly, 1, TILE_SIZE, gridcol); |
| 2796 | draw_rect(dr, lx, ly, TILE_SIZE, 1, gridcol); |
| 2797 | |
| 2798 | /* |
| 2799 | * Draw the arrow. |
| 2800 | */ |
| 2801 | if (flags & DRAW_ARROW) |
| 2802 | draw_arrow(dr, ds, lx + TILE_SIZE/2, ly + TILE_SIZE/2, ddx, ddy); |
| 2803 | |
| 2804 | /* |
| 2805 | * Draw the edges. |
| 2806 | */ |
| 2807 | if (flags & DRAW_EDGE_L) |
| 2808 | draw_rect(dr, lx, ly, EDGE_THICKNESS, TILE_SIZE, COL_EDGE); |
| 2809 | if (flags & DRAW_EDGE_R) |
| 2810 | draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly, |
| 2811 | EDGE_THICKNESS - 1, TILE_SIZE, COL_EDGE); |
| 2812 | if (flags & DRAW_EDGE_U) |
| 2813 | draw_rect(dr, lx, ly, TILE_SIZE, EDGE_THICKNESS, COL_EDGE); |
| 2814 | if (flags & DRAW_EDGE_D) |
| 2815 | draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1, |
| 2816 | TILE_SIZE, EDGE_THICKNESS - 1, COL_EDGE); |
| 2817 | if (flags & DRAW_CORNER_UL) |
| 2818 | draw_rect(dr, lx, ly, EDGE_THICKNESS, EDGE_THICKNESS, COL_EDGE); |
| 2819 | if (flags & DRAW_CORNER_UR) |
| 2820 | draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, ly, |
| 2821 | EDGE_THICKNESS - 1, EDGE_THICKNESS, COL_EDGE); |
| 2822 | if (flags & DRAW_CORNER_DL) |
| 2823 | draw_rect(dr, lx, ly + TILE_SIZE - EDGE_THICKNESS + 1, |
| 2824 | EDGE_THICKNESS, EDGE_THICKNESS - 1, COL_EDGE); |
| 2825 | if (flags & DRAW_CORNER_DR) |
| 2826 | draw_rect(dr, lx + TILE_SIZE - EDGE_THICKNESS + 1, |
| 2827 | ly + TILE_SIZE - EDGE_THICKNESS + 1, |
| 2828 | EDGE_THICKNESS - 1, EDGE_THICKNESS - 1, COL_EDGE); |
| 2829 | |
| 2830 | /* |
| 2831 | * Draw the dots. |
| 2832 | */ |
| 2833 | for (dy = 0; dy < 3; dy++) |
| 2834 | for (dx = 0; dx < 3; dx++) { |
| 2835 | int dotval = (flags >> (DOT_SHIFT_C + DOT_SHIFT_M*(dy*3+dx))); |
| 2836 | dotval &= (1 << DOT_SHIFT_M)-1; |
| 2837 | |
| 2838 | if (dotval) |
| 2839 | draw_circle(dr, lx+dx*TILE_SIZE/2, ly+dy*TILE_SIZE/2, |
| 2840 | DOT_SIZE, |
| 2841 | (dotval == 1 ? COL_WHITEDOT : COL_BLACKDOT), |
| 2842 | COL_BLACKDOT); |
| 2843 | } |
| 2844 | |
| 2845 | unclip(dr); |
| 2846 | draw_update(dr, lx, ly, TILE_SIZE, TILE_SIZE); |
| 2847 | } |
| 2848 | |
| 2849 | static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, |
| 2850 | game_state *state, int dir, game_ui *ui, |
| 2851 | float animtime, float flashtime) |
| 2852 | { |
| 2853 | int w = ds->w, h = ds->h; |
| 2854 | int x, y, flashing = FALSE; |
| 2855 | |
| 2856 | if (flashtime > 0) { |
| 2857 | int frame = (int)(flashtime / FLASH_TIME); |
| 2858 | flashing = (frame % 2 == 0); |
| 2859 | } |
| 2860 | |
| 2861 | if (ds->dragging) { |
| 2862 | assert(ds->bl); |
| 2863 | blitter_load(dr, ds->bl, ds->dragx, ds->dragy); |
| 2864 | draw_update(dr, ds->dragx, ds->dragy, TILE_SIZE, TILE_SIZE); |
| 2865 | ds->dragging = FALSE; |
| 2866 | } |
| 2867 | |
| 2868 | if (!ds->started) { |
| 2869 | draw_rect(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT, COL_BACKGROUND); |
| 2870 | draw_rect(dr, BORDER - EDGE_THICKNESS + 1, BORDER - EDGE_THICKNESS + 1, |
| 2871 | w*TILE_SIZE + EDGE_THICKNESS*2 - 1, |
| 2872 | h*TILE_SIZE + EDGE_THICKNESS*2 - 1, COL_EDGE); |
| 2873 | draw_update(dr, 0, 0, DRAW_WIDTH, DRAW_HEIGHT); |
| 2874 | ds->started = TRUE; |
| 2875 | } |
| 2876 | |
| 2877 | check_complete_in_play(state, NULL, ds->colour_scratch); |
| 2878 | |
| 2879 | for (y = 0; y < h; y++) |
| 2880 | for (x = 0; x < w; x++) { |
| 2881 | unsigned long flags = 0; |
| 2882 | int ddx = 0, ddy = 0; |
| 2883 | space *sp; |
| 2884 | int dx, dy; |
| 2885 | |
| 2886 | /* |
| 2887 | * Set up the flags for this square. Firstly, see if we |
| 2888 | * have edges. |
| 2889 | */ |
| 2890 | if (SPACE(state, x*2, y*2+1).flags & F_EDGE_SET) |
| 2891 | flags |= DRAW_EDGE_L; |
| 2892 | if (SPACE(state, x*2+2, y*2+1).flags & F_EDGE_SET) |
| 2893 | flags |= DRAW_EDGE_R; |
| 2894 | if (SPACE(state, x*2+1, y*2).flags & F_EDGE_SET) |
| 2895 | flags |= DRAW_EDGE_U; |
| 2896 | if (SPACE(state, x*2+1, y*2+2).flags & F_EDGE_SET) |
| 2897 | flags |= DRAW_EDGE_D; |
| 2898 | |
| 2899 | /* |
| 2900 | * Also, mark corners of neighbouring edges. |
| 2901 | */ |
| 2902 | if ((x > 0 && SPACE(state, x*2-1, y*2).flags & F_EDGE_SET) || |
| 2903 | (y > 0 && SPACE(state, x*2, y*2-1).flags & F_EDGE_SET)) |
| 2904 | flags |= DRAW_CORNER_UL; |
| 2905 | if ((x+1 < w && SPACE(state, x*2+3, y*2).flags & F_EDGE_SET) || |
| 2906 | (y > 0 && SPACE(state, x*2+2, y*2-1).flags & F_EDGE_SET)) |
| 2907 | flags |= DRAW_CORNER_UR; |
| 2908 | if ((x > 0 && SPACE(state, x*2-1, y*2+2).flags & F_EDGE_SET) || |
| 2909 | (y+1 < h && SPACE(state, x*2, y*2+3).flags & F_EDGE_SET)) |
| 2910 | flags |= DRAW_CORNER_DL; |
| 2911 | if ((x+1 < w && SPACE(state, x*2+3, y*2+2).flags & F_EDGE_SET) || |
| 2912 | (y+1 < h && SPACE(state, x*2+2, y*2+3).flags & F_EDGE_SET)) |
| 2913 | flags |= DRAW_CORNER_DR; |
| 2914 | |
| 2915 | /* |
| 2916 | * If this square is part of a valid region, paint it |
| 2917 | * that region's colour. Exception: if we're flashing, |
| 2918 | * everything goes briefly back to background colour. |
| 2919 | */ |
| 2920 | sp = &SPACE(state, x*2+1, y*2+1); |
| 2921 | if (ds->colour_scratch[y*w+x] && !flashing) { |
| 2922 | flags |= (ds->colour_scratch[y*w+x] == 2 ? |
| 2923 | DRAW_BLACK : DRAW_WHITE); |
| 2924 | } |
| 2925 | |
| 2926 | /* |
| 2927 | * If this square is associated with a dot but it isn't |
| 2928 | * part of a valid region, draw an arrow in it pointing |
| 2929 | * in the direction of that dot. |
| 2930 | * |
| 2931 | * Exception: if this is the source point of an active |
| 2932 | * drag, we don't draw the arrow. |
| 2933 | */ |
| 2934 | if ((sp->flags & F_TILE_ASSOC) && !ds->colour_scratch[y*w+x]) { |
| 2935 | if (ui->dragging && ui->srcx == x*2+1 && ui->srcy == y*2+1) { |
| 2936 | /* don't do it */ |
| 2937 | } else if (sp->doty != y*2+1 || sp->dotx != x*2+1) { |
| 2938 | flags |= DRAW_ARROW; |
| 2939 | ddy = sp->doty - (y*2+1); |
| 2940 | ddx = sp->dotx - (x*2+1); |
| 2941 | } |
| 2942 | } |
| 2943 | |
| 2944 | /* |
| 2945 | * Now go through the nine possible places we could |
| 2946 | * have dots. |
| 2947 | */ |
| 2948 | for (dy = 0; dy < 3; dy++) |
| 2949 | for (dx = 0; dx < 3; dx++) { |
| 2950 | sp = &SPACE(state, x*2+dx, y*2+dy); |
| 2951 | if (sp->flags & F_DOT) { |
| 2952 | unsigned long dotval = (sp->flags & F_DOT_BLACK ? |
| 2953 | DOT_BLACK : DOT_WHITE); |
| 2954 | flags |= dotval << (DOT_SHIFT_C + |
| 2955 | DOT_SHIFT_M*(dy*3+dx)); |
| 2956 | } |
| 2957 | } |
| 2958 | |
| 2959 | /* |
| 2960 | * Now we have everything we're going to need. Draw the |
| 2961 | * square. |
| 2962 | */ |
| 2963 | if (ds->grid[y*w+x] != flags || |
| 2964 | ds->dx[y*w+x] != ddx || |
| 2965 | ds->dy[y*w+x] != ddy) { |
| 2966 | draw_square(dr, ds, x, y, flags, ddx, ddy); |
| 2967 | ds->grid[y*w+x] = flags; |
| 2968 | ds->dx[y*w+x] = ddx; |
| 2969 | ds->dy[y*w+x] = ddy; |
| 2970 | } |
| 2971 | } |
| 2972 | |
| 2973 | if (ui->dragging) { |
| 2974 | ds->dragging = TRUE; |
| 2975 | ds->dragx = ui->dx - TILE_SIZE/2; |
| 2976 | ds->dragy = ui->dy - TILE_SIZE/2; |
| 2977 | blitter_save(dr, ds->bl, ds->dragx, ds->dragy); |
| 2978 | draw_arrow(dr, ds, ui->dx, ui->dy, |
| 2979 | SCOORD(ui->dotx) - ui->dx, |
| 2980 | SCOORD(ui->doty) - ui->dy); |
| 2981 | } |
| 2982 | #ifdef EDITOR |
| 2983 | { |
| 2984 | char buf[256]; |
| 2985 | if (state->cdiff != -1) |
| 2986 | sprintf(buf, "Puzzle is %s.", galaxies_diffnames[state->cdiff]); |
| 2987 | else |
| 2988 | buf[0] = '\0'; |
| 2989 | status_bar(dr, buf); |
| 2990 | } |
| 2991 | #endif |
| 2992 | } |
| 2993 | |
| 2994 | static float game_anim_length(game_state *oldstate, game_state *newstate, |
| 2995 | int dir, game_ui *ui) |
| 2996 | { |
| 2997 | return 0.0F; |
| 2998 | } |
| 2999 | |
| 3000 | static float game_flash_length(game_state *oldstate, game_state *newstate, |
| 3001 | int dir, game_ui *ui) |
| 3002 | { |
| 3003 | if ((!oldstate->completed && newstate->completed) && |
| 3004 | !(newstate->used_solve)) |
| 3005 | return 3 * FLASH_TIME; |
| 3006 | else |
| 3007 | return 0.0F; |
| 3008 | } |
| 3009 | |
| 3010 | static int game_timing_state(game_state *state, game_ui *ui) |
| 3011 | { |
| 3012 | return TRUE; |
| 3013 | } |
| 3014 | |
| 3015 | #ifndef EDITOR |
| 3016 | static void game_print_size(game_params *params, float *x, float *y) |
| 3017 | { |
| 3018 | int pw, ph; |
| 3019 | |
| 3020 | /* |
| 3021 | * 8mm squares by default. (There isn't all that much detail |
| 3022 | * that needs to go in each square.) |
| 3023 | */ |
| 3024 | game_compute_size(params, 800, &pw, &ph); |
| 3025 | *x = pw / 100.0F; |
| 3026 | *y = ph / 100.0F; |
| 3027 | } |
| 3028 | |
| 3029 | static void game_print(drawing *dr, game_state *state, int sz) |
| 3030 | { |
| 3031 | int w = state->w, h = state->h; |
| 3032 | int white, black, blackish; |
| 3033 | int x, y, i, j; |
| 3034 | int *colours, *dsf; |
| 3035 | int *coords = NULL; |
| 3036 | int ncoords = 0, coordsize = 0; |
| 3037 | |
| 3038 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ |
| 3039 | game_drawstate ads, *ds = &ads; |
| 3040 | ds->tilesize = sz; |
| 3041 | |
| 3042 | white = print_grey_colour(dr, HATCH_CLEAR, 1.0F); |
| 3043 | black = print_grey_colour(dr, HATCH_SOLID, 0.0F); |
| 3044 | blackish = print_grey_colour(dr, HATCH_X, 0.5F); |
| 3045 | |
| 3046 | /* |
| 3047 | * Get the completion information. |
| 3048 | */ |
| 3049 | dsf = snewn(w * h, int); |
| 3050 | colours = snewn(w * h, int); |
| 3051 | check_complete_in_play(state, dsf, colours); |
| 3052 | |
| 3053 | /* |
| 3054 | * Draw the grid. |
| 3055 | */ |
| 3056 | print_line_width(dr, TILE_SIZE / 64); |
| 3057 | for (x = 1; x < w; x++) |
| 3058 | draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), black); |
| 3059 | for (y = 1; y < h; y++) |
| 3060 | draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), black); |
| 3061 | |
| 3062 | /* |
| 3063 | * Shade the completed regions. Just in case any particular |
| 3064 | * printing platform deals badly with adjacent |
| 3065 | * similarly-hatched regions, we'll fill each one as a single |
| 3066 | * polygon. |
| 3067 | */ |
| 3068 | for (i = 0; i < w*h; i++) { |
| 3069 | j = dsf_canonify(dsf, i); |
| 3070 | if (colours[j] != 0) { |
| 3071 | int dx, dy, t; |
| 3072 | |
| 3073 | /* |
| 3074 | * This is the first square we've run into belonging to |
| 3075 | * this polyomino, which means an edge of the polyomino |
| 3076 | * is certain to be to our left. (After we finish |
| 3077 | * tracing round it, we'll set the colours[] entry to |
| 3078 | * zero to prevent accidentally doing it again.) |
| 3079 | */ |
| 3080 | |
| 3081 | x = i % w; |
| 3082 | y = i / w; |
| 3083 | dx = -1; |
| 3084 | dy = 0; |
| 3085 | ncoords = 0; |
| 3086 | while (1) { |
| 3087 | /* |
| 3088 | * We are currently sitting on square (x,y), which |
| 3089 | * we know to be in our polyomino, and we also know |
| 3090 | * that (x+dx,y+dy) is not. The way I visualise |
| 3091 | * this is that we're standing to the right of a |
| 3092 | * boundary line, stretching our left arm out to |
| 3093 | * point to the exterior square on the far side. |
| 3094 | */ |
| 3095 | |
| 3096 | /* |
| 3097 | * First, check if we've gone round the entire |
| 3098 | * polyomino. |
| 3099 | */ |
| 3100 | if (ncoords > 0 && |
| 3101 | (x == i%w && y == i/w && dx == -1 && dy == 0)) |
| 3102 | break; |
| 3103 | |
| 3104 | /* |
| 3105 | * Add to our coordinate list the coordinate |
| 3106 | * backwards and to the left of where we are. |
| 3107 | */ |
| 3108 | if (ncoords + 2 > coordsize) { |
| 3109 | coordsize = (ncoords * 3 / 2) + 64; |
| 3110 | coords = sresize(coords, coordsize, int); |
| 3111 | } |
| 3112 | coords[ncoords++] = COORD((2*x+1 + dx + dy) / 2); |
| 3113 | coords[ncoords++] = COORD((2*y+1 + dy - dx) / 2); |
| 3114 | |
| 3115 | /* |
| 3116 | * Follow the edge round. If the square directly in |
| 3117 | * front of us is not part of the polyomino, we |
| 3118 | * turn right; if it is and so is the square in |
| 3119 | * front of (x+dx,y+dy), we turn left; otherwise we |
| 3120 | * go straight on. |
| 3121 | */ |
| 3122 | if (x-dy < 0 || x-dy >= w || y+dx < 0 || y+dx >= h || |
| 3123 | dsf_canonify(dsf, (y+dx)*w+(x-dy)) != j) { |
| 3124 | /* Turn right. */ |
| 3125 | t = dx; |
| 3126 | dx = -dy; |
| 3127 | dy = t; |
| 3128 | } else if (x+dx-dy >= 0 && x+dx-dy < w && |
| 3129 | y+dy+dx >= 0 && y+dy+dx < h && |
| 3130 | dsf_canonify(dsf, (y+dy+dx)*w+(x+dx-dy)) == j) { |
| 3131 | /* Turn left. */ |
| 3132 | x += dx; |
| 3133 | y += dy; |
| 3134 | t = dx; |
| 3135 | dx = dy; |
| 3136 | dy = -t; |
| 3137 | x -= dx; |
| 3138 | y -= dy; |
| 3139 | } else { |
| 3140 | /* Straight on. */ |
| 3141 | x -= dy; |
| 3142 | y += dx; |
| 3143 | } |
| 3144 | } |
| 3145 | |
| 3146 | /* |
| 3147 | * Now we have our polygon complete, so fill it. |
| 3148 | */ |
| 3149 | draw_polygon(dr, coords, ncoords/2, |
| 3150 | colours[j] == 2 ? blackish : -1, black); |
| 3151 | |
| 3152 | /* |
| 3153 | * And mark this polyomino as done. |
| 3154 | */ |
| 3155 | colours[j] = 0; |
| 3156 | } |
| 3157 | } |
| 3158 | |
| 3159 | /* |
| 3160 | * Draw the edges. |
| 3161 | */ |
| 3162 | for (y = 0; y <= h; y++) |
| 3163 | for (x = 0; x <= w; x++) { |
| 3164 | if (x < w && SPACE(state, x*2+1, y*2).flags & F_EDGE_SET) |
| 3165 | draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS, |
| 3166 | EDGE_THICKNESS * 2 + TILE_SIZE, EDGE_THICKNESS * 2, |
| 3167 | black); |
| 3168 | if (y < h && SPACE(state, x*2, y*2+1).flags & F_EDGE_SET) |
| 3169 | draw_rect(dr, COORD(x)-EDGE_THICKNESS, COORD(y)-EDGE_THICKNESS, |
| 3170 | EDGE_THICKNESS * 2, EDGE_THICKNESS * 2 + TILE_SIZE, |
| 3171 | black); |
| 3172 | } |
| 3173 | |
| 3174 | /* |
| 3175 | * Draw the dots. |
| 3176 | */ |
| 3177 | for (y = 0; y <= 2*h; y++) |
| 3178 | for (x = 0; x <= 2*w; x++) |
| 3179 | if (SPACE(state, x, y).flags & F_DOT) { |
| 3180 | draw_circle(dr, (int)COORD(x/2.0), (int)COORD(y/2.0), DOT_SIZE, |
| 3181 | (SPACE(state, x, y).flags & F_DOT_BLACK ? |
| 3182 | black : white), black); |
| 3183 | } |
| 3184 | |
| 3185 | sfree(dsf); |
| 3186 | sfree(colours); |
| 3187 | sfree(coords); |
| 3188 | } |
| 3189 | #endif |
| 3190 | |
| 3191 | #ifdef COMBINED |
| 3192 | #define thegame galaxies |
| 3193 | #endif |
| 3194 | |
| 3195 | const struct game thegame = { |
| 3196 | "Galaxies", "games.galaxies", "galaxies", |
| 3197 | default_params, |
| 3198 | game_fetch_preset, |
| 3199 | decode_params, |
| 3200 | encode_params, |
| 3201 | free_params, |
| 3202 | dup_params, |
| 3203 | TRUE, game_configure, custom_params, |
| 3204 | validate_params, |
| 3205 | new_game_desc, |
| 3206 | validate_desc, |
| 3207 | new_game, |
| 3208 | dup_game, |
| 3209 | free_game, |
| 3210 | #ifdef EDITOR |
| 3211 | FALSE, NULL, |
| 3212 | #else |
| 3213 | TRUE, solve_game, |
| 3214 | #endif |
| 3215 | TRUE, game_text_format, |
| 3216 | new_ui, |
| 3217 | free_ui, |
| 3218 | encode_ui, |
| 3219 | decode_ui, |
| 3220 | game_changed_state, |
| 3221 | interpret_move, |
| 3222 | execute_move, |
| 3223 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, |
| 3224 | game_colours, |
| 3225 | game_new_drawstate, |
| 3226 | game_free_drawstate, |
| 3227 | game_redraw, |
| 3228 | game_anim_length, |
| 3229 | game_flash_length, |
| 3230 | #ifdef EDITOR |
| 3231 | FALSE, FALSE, NULL, NULL, |
| 3232 | TRUE, /* wants_statusbar */ |
| 3233 | #else |
| 3234 | TRUE, FALSE, game_print_size, game_print, |
| 3235 | FALSE, /* wants_statusbar */ |
| 3236 | #endif |
| 3237 | FALSE, game_timing_state, |
| 3238 | REQUIRE_RBUTTON, /* flags */ |
| 3239 | }; |
| 3240 | |
| 3241 | #ifdef STANDALONE_SOLVER |
| 3242 | |
| 3243 | const char *quis; |
| 3244 | |
| 3245 | #include <time.h> |
| 3246 | |
| 3247 | static void usage_exit(const char *msg) |
| 3248 | { |
| 3249 | if (msg) |
| 3250 | fprintf(stderr, "%s: %s\n", quis, msg); |
| 3251 | fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis); |
| 3252 | exit(1); |
| 3253 | } |
| 3254 | |
| 3255 | static void dump_state(game_state *state) |
| 3256 | { |
| 3257 | char *temp = game_text_format(state); |
| 3258 | printf("%s\n", temp); |
| 3259 | sfree(temp); |
| 3260 | } |
| 3261 | |
| 3262 | static int gen(game_params *p, random_state *rs, int debug) |
| 3263 | { |
| 3264 | char *desc; |
| 3265 | int diff; |
| 3266 | game_state *state; |
| 3267 | |
| 3268 | #ifndef DEBUGGING |
| 3269 | solver_show_working = debug; |
| 3270 | #endif |
| 3271 | printf("Generating a %dx%d %s puzzle.\n", |
| 3272 | p->w, p->h, galaxies_diffnames[p->diff]); |
| 3273 | |
| 3274 | desc = new_game_desc(p, rs, NULL, 0); |
| 3275 | state = new_game(NULL, p, desc); |
| 3276 | dump_state(state); |
| 3277 | |
| 3278 | diff = solver_state(state, DIFF_UNREASONABLE); |
| 3279 | printf("Generated %s game %dx%d:%s\n", |
| 3280 | galaxies_diffnames[diff], p->w, p->h, desc); |
| 3281 | dump_state(state); |
| 3282 | |
| 3283 | free_game(state); |
| 3284 | sfree(desc); |
| 3285 | |
| 3286 | return diff; |
| 3287 | } |
| 3288 | |
| 3289 | static void soak(game_params *p, random_state *rs) |
| 3290 | { |
| 3291 | time_t tt_start, tt_now, tt_last; |
| 3292 | char *desc; |
| 3293 | game_state *st; |
| 3294 | int diff, n = 0, i, diffs[DIFF_MAX], ndots = 0, nspaces = 0; |
| 3295 | |
| 3296 | #ifndef DEBUGGING |
| 3297 | solver_show_working = 0; |
| 3298 | #endif |
| 3299 | tt_start = tt_now = time(NULL); |
| 3300 | for (i = 0; i < DIFF_MAX; i++) diffs[i] = 0; |
| 3301 | maxtries = 1; |
| 3302 | |
| 3303 | printf("Soak-generating a %dx%d grid, max. diff %s.\n", |
| 3304 | p->w, p->h, galaxies_diffnames[p->diff]); |
| 3305 | printf(" ["); |
| 3306 | for (i = 0; i < DIFF_MAX; i++) |
| 3307 | printf("%s%s", (i == 0) ? "" : ", ", galaxies_diffnames[i]); |
| 3308 | printf("]\n"); |
| 3309 | |
| 3310 | while (1) { |
| 3311 | desc = new_game_desc(p, rs, NULL, 0); |
| 3312 | st = new_game(NULL, p, desc); |
| 3313 | diff = solver_state(st, p->diff); |
| 3314 | nspaces += st->w*st->h; |
| 3315 | for (i = 0; i < st->sx*st->sy; i++) |
| 3316 | if (st->grid[i].flags & F_DOT) ndots++; |
| 3317 | free_game(st); |
| 3318 | sfree(desc); |
| 3319 | |
| 3320 | diffs[diff]++; |
| 3321 | n++; |
| 3322 | tt_last = time(NULL); |
| 3323 | if (tt_last > tt_now) { |
| 3324 | tt_now = tt_last; |
| 3325 | printf("%d total, %3.1f/s, [", |
| 3326 | n, (double)n / ((double)tt_now - tt_start)); |
| 3327 | for (i = 0; i < DIFF_MAX; i++) |
| 3328 | printf("%s%.1f%%", (i == 0) ? "" : ", ", |
| 3329 | 100.0 * ((double)diffs[i] / (double)n)); |
| 3330 | printf("], %.1f%% dots\n", |
| 3331 | 100.0 * ((double)ndots / (double)nspaces)); |
| 3332 | } |
| 3333 | } |
| 3334 | } |
| 3335 | |
| 3336 | int main(int argc, char **argv) |
| 3337 | { |
| 3338 | game_params *p; |
| 3339 | char *id = NULL, *desc, *err; |
| 3340 | game_state *s; |
| 3341 | int diff, do_soak = 0, verbose = 0; |
| 3342 | random_state *rs; |
| 3343 | time_t seed = time(NULL); |
| 3344 | |
| 3345 | quis = argv[0]; |
| 3346 | while (--argc > 0) { |
| 3347 | char *p = *++argv; |
| 3348 | if (!strcmp(p, "-v")) { |
| 3349 | verbose = 1; |
| 3350 | } else if (!strcmp(p, "--seed")) { |
| 3351 | if (argc == 0) usage_exit("--seed needs an argument"); |
| 3352 | seed = (time_t)atoi(*++argv); |
| 3353 | argc--; |
| 3354 | } else if (!strcmp(p, "--soak")) { |
| 3355 | do_soak = 1; |
| 3356 | } else if (*p == '-') { |
| 3357 | usage_exit("unrecognised option"); |
| 3358 | } else { |
| 3359 | id = p; |
| 3360 | } |
| 3361 | } |
| 3362 | |
| 3363 | maxtries = 50; |
| 3364 | |
| 3365 | p = default_params(); |
| 3366 | rs = random_new((void*)&seed, sizeof(time_t)); |
| 3367 | |
| 3368 | if (do_soak) { |
| 3369 | if (!id) usage_exit("need one argument for --soak"); |
| 3370 | decode_params(p, *argv); |
| 3371 | soak(p, rs); |
| 3372 | return 0; |
| 3373 | } |
| 3374 | |
| 3375 | if (!id) { |
| 3376 | while (1) { |
| 3377 | p->w = random_upto(rs, 15) + 3; |
| 3378 | p->h = random_upto(rs, 15) + 3; |
| 3379 | p->diff = random_upto(rs, DIFF_UNREASONABLE); |
| 3380 | diff = gen(p, rs, 0); |
| 3381 | } |
| 3382 | return 0; |
| 3383 | } |
| 3384 | |
| 3385 | desc = strchr(id, ':'); |
| 3386 | if (!desc) { |
| 3387 | decode_params(p, id); |
| 3388 | gen(p, rs, verbose); |
| 3389 | } else { |
| 3390 | #ifndef DEBUGGING |
| 3391 | solver_show_working = 1; |
| 3392 | #endif |
| 3393 | *desc++ = '\0'; |
| 3394 | decode_params(p, id); |
| 3395 | err = validate_desc(p, desc); |
| 3396 | if (err) { |
| 3397 | fprintf(stderr, "%s: %s\n", argv[0], err); |
| 3398 | exit(1); |
| 3399 | } |
| 3400 | s = new_game(NULL, p, desc); |
| 3401 | diff = solver_state(s, DIFF_UNREASONABLE); |
| 3402 | dump_state(s); |
| 3403 | printf("Puzzle is %s.\n", galaxies_diffnames[diff]); |
| 3404 | free_game(s); |
| 3405 | } |
| 3406 | |
| 3407 | free_params(p); |
| 3408 | |
| 3409 | return 0; |
| 3410 | } |
| 3411 | |
| 3412 | #endif |
| 3413 | |
| 3414 | /* vim: set shiftwidth=4 tabstop=8: */ |