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