| 1 | /* |
| 2 | * Experimental grid generator for Nikoli's `Number Link' puzzle. |
| 3 | */ |
| 4 | |
| 5 | #include <stdio.h> |
| 6 | #include <stdlib.h> |
| 7 | #include <assert.h> |
| 8 | #include "puzzles.h" |
| 9 | |
| 10 | /* |
| 11 | * 2005-07-08: This is currently a Path grid generator which will |
| 12 | * construct valid grids at a plausible speed. However, the grids |
| 13 | * are not of suitable quality to be used directly as puzzles. |
| 14 | * |
| 15 | * The basic strategy is to start with an empty grid, and |
| 16 | * repeatedly either (a) add a new path to it, or (b) extend one |
| 17 | * end of a path by one square in some direction and push other |
| 18 | * paths into new shapes in the process. The effect of this is that |
| 19 | * we are able to construct a set of paths which between them fill |
| 20 | * the entire grid. |
| 21 | * |
| 22 | * Quality issues: if we set the main loop to do (a) where possible |
| 23 | * and (b) only where necessary, we end up with a grid containing a |
| 24 | * few too many small paths, which therefore doesn't make for an |
| 25 | * interesting puzzle. If we reverse the priority so that we do (b) |
| 26 | * where possible and (a) only where necessary, we end up with some |
| 27 | * staggeringly interwoven grids with very very few separate paths, |
| 28 | * but the result of this is that there's invariably a solution |
| 29 | * other than the intended one which leaves many grid squares |
| 30 | * unfilled. There's also a separate problem which is that many |
| 31 | * grids have really boring and obvious paths in them, such as the |
| 32 | * entire bottom row of the grid being taken up by a single path. |
| 33 | * |
| 34 | * It's not impossible that a few tweaks might eliminate or reduce |
| 35 | * the incidence of boring paths, and might also find a happy |
| 36 | * medium between too many and too few. There remains the question |
| 37 | * of unique solutions, however. I fear there is no alternative but |
| 38 | * to write - somehow! - a solver. |
| 39 | * |
| 40 | * While I'm here, some notes on UI strategy for the parts of the |
| 41 | * puzzle implementation that _aren't_ the generator: |
| 42 | * |
| 43 | * - data model is to track connections between adjacent squares, |
| 44 | * so that you aren't limited to extending a path out from each |
| 45 | * number but can also mark sections of path which you know |
| 46 | * _will_ come in handy later. |
| 47 | * |
| 48 | * - user interface is to click in one square and drag to an |
| 49 | * adjacent one, thus creating a link between them. We can |
| 50 | * probably tolerate rapid mouse motion causing a drag directly |
| 51 | * to a square which is a rook move away, but any other rapid |
| 52 | * motion is ambiguous and probably the best option is to wait |
| 53 | * until the mouse returns to a square we know how to reach. |
| 54 | * |
| 55 | * - a drag causing the current path to backtrack has the effect |
| 56 | * of removing bits of it. |
| 57 | * |
| 58 | * - the UI should enforce at all times the constraint that at |
| 59 | * most two links can come into any square. |
| 60 | * |
| 61 | * - my Cunning Plan for actually implementing this: the game_ui |
| 62 | * contains a grid-sized array, which is copied from the current |
| 63 | * game_state on starting a drag. While a drag is active, the |
| 64 | * contents of the game_ui is adjusted with every mouse motion, |
| 65 | * and is displayed _in place_ of the game_state itself. On |
| 66 | * termination of a drag, the game_ui array is copied back into |
| 67 | * the new game_state (or rather, a string move is encoded which |
| 68 | * has precisely the set of link changes to cause that effect). |
| 69 | */ |
| 70 | |
| 71 | /* |
| 72 | * Standard notation for directions. |
| 73 | */ |
| 74 | #define L 0 |
| 75 | #define U 1 |
| 76 | #define R 2 |
| 77 | #define D 3 |
| 78 | #define DX(dir) ( (dir)==L ? -1 : (dir)==R ? +1 : 0) |
| 79 | #define DY(dir) ( (dir)==U ? -1 : (dir)==D ? +1 : 0) |
| 80 | |
| 81 | /* |
| 82 | * Perform a breadth-first search over a grid of squares with the |
| 83 | * colour of square (X,Y) given by grid[Y*w+X]. The search begins |
| 84 | * at (x,y), and finds all squares which are the same colour as |
| 85 | * (x,y) and reachable from it by orthogonal moves. On return: |
| 86 | * - dist[Y*w+X] gives the distance of (X,Y) from (x,y), or -1 if |
| 87 | * unreachable or a different colour |
| 88 | * - the returned value is the number of reachable squares, |
| 89 | * including (x,y) itself |
| 90 | * - list[0] up to list[returned value - 1] list those squares, in |
| 91 | * increasing order of distance from (x,y) (and in arbitrary |
| 92 | * order within that). |
| 93 | */ |
| 94 | static int bfs(int w, int h, int *grid, int x, int y, int *dist, int *list) |
| 95 | { |
| 96 | int i, j, c, listsize, listdone; |
| 97 | |
| 98 | /* |
| 99 | * Start by clearing the output arrays. |
| 100 | */ |
| 101 | for (i = 0; i < w*h; i++) |
| 102 | dist[i] = list[i] = -1; |
| 103 | |
| 104 | /* |
| 105 | * Set up the initial list. |
| 106 | */ |
| 107 | listsize = 1; |
| 108 | listdone = 0; |
| 109 | list[0] = y*w+x; |
| 110 | dist[y*w+x] = 0; |
| 111 | c = grid[y*w+x]; |
| 112 | |
| 113 | /* |
| 114 | * Repeatedly process a square and add any extra squares to the |
| 115 | * end of list. |
| 116 | */ |
| 117 | while (listdone < listsize) { |
| 118 | i = list[listdone++]; |
| 119 | y = i / w; |
| 120 | x = i % w; |
| 121 | for (j = 0; j < 4; j++) { |
| 122 | int xx, yy, ii; |
| 123 | |
| 124 | xx = x + DX(j); |
| 125 | yy = y + DY(j); |
| 126 | ii = yy*w+xx; |
| 127 | |
| 128 | if (xx >= 0 && xx < w && yy >= 0 && yy < h && |
| 129 | grid[ii] == c && dist[ii] == -1) { |
| 130 | dist[ii] = dist[i] + 1; |
| 131 | assert(listsize < w*h); |
| 132 | list[listsize++] = ii; |
| 133 | } |
| 134 | } |
| 135 | } |
| 136 | |
| 137 | return listsize; |
| 138 | } |
| 139 | |
| 140 | struct genctx { |
| 141 | int w, h; |
| 142 | int *grid, *sparegrid, *sparegrid2, *sparegrid3; |
| 143 | int *dist, *list; |
| 144 | |
| 145 | int npaths, pathsize; |
| 146 | int *pathends, *sparepathends; /* 2*npaths entries */ |
| 147 | int *pathspare; /* npaths entries */ |
| 148 | int *extends; /* 8*npaths entries */ |
| 149 | }; |
| 150 | |
| 151 | static struct genctx *new_genctx(int w, int h) |
| 152 | { |
| 153 | struct genctx *ctx = snew(struct genctx); |
| 154 | ctx->w = w; |
| 155 | ctx->h = h; |
| 156 | ctx->grid = snewn(w * h, int); |
| 157 | ctx->sparegrid = snewn(w * h, int); |
| 158 | ctx->sparegrid2 = snewn(w * h, int); |
| 159 | ctx->sparegrid3 = snewn(w * h, int); |
| 160 | ctx->dist = snewn(w * h, int); |
| 161 | ctx->list = snewn(w * h, int); |
| 162 | ctx->npaths = ctx->pathsize = 0; |
| 163 | ctx->pathends = ctx->sparepathends = ctx->pathspare = ctx->extends = NULL; |
| 164 | return ctx; |
| 165 | } |
| 166 | |
| 167 | static void free_genctx(struct genctx *ctx) |
| 168 | { |
| 169 | sfree(ctx->grid); |
| 170 | sfree(ctx->sparegrid); |
| 171 | sfree(ctx->sparegrid2); |
| 172 | sfree(ctx->sparegrid3); |
| 173 | sfree(ctx->dist); |
| 174 | sfree(ctx->list); |
| 175 | sfree(ctx->pathends); |
| 176 | sfree(ctx->sparepathends); |
| 177 | sfree(ctx->pathspare); |
| 178 | sfree(ctx->extends); |
| 179 | } |
| 180 | |
| 181 | static int newpath(struct genctx *ctx) |
| 182 | { |
| 183 | int n; |
| 184 | |
| 185 | n = ctx->npaths++; |
| 186 | if (ctx->npaths > ctx->pathsize) { |
| 187 | ctx->pathsize += 16; |
| 188 | ctx->pathends = sresize(ctx->pathends, ctx->pathsize*2, int); |
| 189 | ctx->sparepathends = sresize(ctx->sparepathends, ctx->pathsize*2, int); |
| 190 | ctx->pathspare = sresize(ctx->pathspare, ctx->pathsize, int); |
| 191 | ctx->extends = sresize(ctx->extends, ctx->pathsize*8, int); |
| 192 | } |
| 193 | return n; |
| 194 | } |
| 195 | |
| 196 | static int is_endpoint(struct genctx *ctx, int x, int y) |
| 197 | { |
| 198 | int w = ctx->w, h = ctx->h, c; |
| 199 | |
| 200 | assert(x >= 0 && x < w && y >= 0 && y < h); |
| 201 | |
| 202 | c = ctx->grid[y*w+x]; |
| 203 | if (c < 0) |
| 204 | return FALSE; /* empty square is not an endpoint! */ |
| 205 | assert(c >= 0 && c < ctx->npaths); |
| 206 | if (ctx->pathends[c*2] == y*w+x || ctx->pathends[c*2+1] == y*w+x) |
| 207 | return TRUE; |
| 208 | return FALSE; |
| 209 | } |
| 210 | |
| 211 | /* |
| 212 | * Tries to extend a path by one square in the given direction, |
| 213 | * pushing other paths around if necessary. Returns TRUE on success |
| 214 | * or FALSE on failure. |
| 215 | */ |
| 216 | static int extend_path(struct genctx *ctx, int path, int end, int direction) |
| 217 | { |
| 218 | int w = ctx->w, h = ctx->h; |
| 219 | int x, y, xe, ye, cut; |
| 220 | int i, j, jp, n, first, last; |
| 221 | |
| 222 | assert(path >= 0 && path < ctx->npaths); |
| 223 | assert(end == 0 || end == 1); |
| 224 | |
| 225 | /* |
| 226 | * Find the endpoint of the path and the point we plan to |
| 227 | * extend it into. |
| 228 | */ |
| 229 | y = ctx->pathends[path * 2 + end] / w; |
| 230 | x = ctx->pathends[path * 2 + end] % w; |
| 231 | assert(x >= 0 && x < w && y >= 0 && y < h); |
| 232 | |
| 233 | xe = x + DX(direction); |
| 234 | ye = y + DY(direction); |
| 235 | if (xe < 0 || xe >= w || ye < 0 || ye >= h) |
| 236 | return FALSE; /* could not extend in this direction */ |
| 237 | |
| 238 | /* |
| 239 | * We don't extend paths _directly_ into endpoints of other |
| 240 | * paths, although we don't mind too much if a knock-on effect |
| 241 | * of an extension is to push part of another path into a third |
| 242 | * path's endpoint. |
| 243 | */ |
| 244 | if (is_endpoint(ctx, xe, ye)) |
| 245 | return FALSE; |
| 246 | |
| 247 | /* |
| 248 | * We can't extend a path back the way it came. |
| 249 | */ |
| 250 | if (ctx->grid[ye*w+xe] == path) |
| 251 | return FALSE; |
| 252 | |
| 253 | /* |
| 254 | * Paths may not double back on themselves. Check if the new |
| 255 | * point is adjacent to any point of this path other than (x,y). |
| 256 | */ |
| 257 | for (j = 0; j < 4; j++) { |
| 258 | int xf, yf; |
| 259 | |
| 260 | xf = xe + DX(j); |
| 261 | yf = ye + DY(j); |
| 262 | |
| 263 | if (xf >= 0 && xf < w && yf >= 0 && yf < h && |
| 264 | (xf != x || yf != y) && ctx->grid[yf*w+xf] == path) |
| 265 | return FALSE; |
| 266 | } |
| 267 | |
| 268 | /* |
| 269 | * Now we're convinced it's valid to _attempt_ the extension. |
| 270 | * It may still fail if we run out of space to push other paths |
| 271 | * into. |
| 272 | * |
| 273 | * So now we can set up our temporary data structures. We will |
| 274 | * need: |
| 275 | * |
| 276 | * - a spare copy of the grid on which to gradually move paths |
| 277 | * around (sparegrid) |
| 278 | * |
| 279 | * - a second spare copy with which to remember how paths |
| 280 | * looked just before being cut (sparegrid2). FIXME: is |
| 281 | * sparegrid2 necessary? right now it's never different from |
| 282 | * grid itself |
| 283 | * |
| 284 | * - a third spare copy with which to do the internal |
| 285 | * calculations involved in reconstituting a cut path |
| 286 | * (sparegrid3) |
| 287 | * |
| 288 | * - something to track which paths currently need |
| 289 | * reconstituting after being cut, and which have already |
| 290 | * been cut (pathspare) |
| 291 | * |
| 292 | * - a spare copy of pathends to store the altered states in |
| 293 | * (sparepathends) |
| 294 | */ |
| 295 | memcpy(ctx->sparegrid, ctx->grid, w*h*sizeof(int)); |
| 296 | memcpy(ctx->sparegrid2, ctx->grid, w*h*sizeof(int)); |
| 297 | memcpy(ctx->sparepathends, ctx->pathends, ctx->npaths*2*sizeof(int)); |
| 298 | for (i = 0; i < ctx->npaths; i++) |
| 299 | ctx->pathspare[i] = 0; /* 0=untouched, 1=broken, 2=fixed */ |
| 300 | |
| 301 | /* |
| 302 | * Working in sparegrid, actually extend the path. If it cuts |
| 303 | * another, begin a loop in which we restore any cut path by |
| 304 | * moving it out of the way. |
| 305 | */ |
| 306 | cut = ctx->sparegrid[ye*w+xe]; |
| 307 | ctx->sparegrid[ye*w+xe] = path; |
| 308 | ctx->sparepathends[path*2+end] = ye*w+xe; |
| 309 | ctx->pathspare[path] = 2; /* this one is sacrosanct */ |
| 310 | if (cut >= 0) { |
| 311 | assert(cut >= 0 && cut < ctx->npaths); |
| 312 | ctx->pathspare[cut] = 1; /* broken */ |
| 313 | |
| 314 | while (1) { |
| 315 | for (i = 0; i < ctx->npaths; i++) |
| 316 | if (ctx->pathspare[i] == 1) |
| 317 | break; |
| 318 | if (i == ctx->npaths) |
| 319 | break; /* we're done */ |
| 320 | |
| 321 | /* |
| 322 | * Path i needs restoring. So walk along its original |
| 323 | * track (as given in sparegrid2) and see where it's |
| 324 | * been cut. Where it has, surround the cut points in |
| 325 | * the same colour, without overwriting already-fixed |
| 326 | * paths. |
| 327 | */ |
| 328 | memcpy(ctx->sparegrid3, ctx->sparegrid, w*h*sizeof(int)); |
| 329 | n = bfs(w, h, ctx->sparegrid2, |
| 330 | ctx->pathends[i*2] % w, ctx->pathends[i*2] / w, |
| 331 | ctx->dist, ctx->list); |
| 332 | first = last = -1; |
| 333 | if (ctx->sparegrid3[ctx->pathends[i*2]] != i || |
| 334 | ctx->sparegrid3[ctx->pathends[i*2+1]] != i) return FALSE;/* FIXME */ |
| 335 | for (j = 0; j < n; j++) { |
| 336 | jp = ctx->list[j]; |
| 337 | assert(ctx->dist[jp] == j); |
| 338 | assert(ctx->sparegrid2[jp] == i); |
| 339 | |
| 340 | /* |
| 341 | * Wipe out the original path in sparegrid. |
| 342 | */ |
| 343 | if (ctx->sparegrid[jp] == i) |
| 344 | ctx->sparegrid[jp] = -1; |
| 345 | |
| 346 | /* |
| 347 | * Be prepared to shorten the path at either end if |
| 348 | * the endpoints have been stomped on. |
| 349 | */ |
| 350 | if (ctx->sparegrid3[jp] == i) { |
| 351 | if (first < 0) |
| 352 | first = jp; |
| 353 | last = jp; |
| 354 | } |
| 355 | |
| 356 | if (ctx->sparegrid3[jp] != i) { |
| 357 | int jx = jp % w, jy = jp / w; |
| 358 | int dx, dy; |
| 359 | for (dy = -1; dy <= +1; dy++) |
| 360 | for (dx = -1; dx <= +1; dx++) { |
| 361 | int newp, newv; |
| 362 | if (!dy && !dx) |
| 363 | continue; /* central square */ |
| 364 | if (jx+dx < 0 || jx+dx >= w || |
| 365 | jy+dy < 0 || jy+dy >= h) |
| 366 | continue; /* out of range */ |
| 367 | newp = (jy+dy)*w+(jx+dx); |
| 368 | newv = ctx->sparegrid3[newp]; |
| 369 | if (newv >= 0 && (newv == i || |
| 370 | ctx->pathspare[newv] == 2)) |
| 371 | continue; /* can't use this square */ |
| 372 | ctx->sparegrid3[newp] = i; |
| 373 | } |
| 374 | } |
| 375 | } |
| 376 | |
| 377 | if (first < 0 || last < 0) |
| 378 | return FALSE; /* path is completely wiped out! */ |
| 379 | |
| 380 | /* |
| 381 | * Now we've covered sparegrid3 in possible squares for |
| 382 | * the new layout of path i. Find the actual layout |
| 383 | * we're going to use by bfs: we want the shortest path |
| 384 | * from one endpoint to the other. |
| 385 | */ |
| 386 | n = bfs(w, h, ctx->sparegrid3, first % w, first / w, |
| 387 | ctx->dist, ctx->list); |
| 388 | if (ctx->dist[last] < 2) { |
| 389 | /* |
| 390 | * Either there is no way to get between the path's |
| 391 | * endpoints, or the remaining endpoints simply |
| 392 | * aren't far enough apart to make the path viable |
| 393 | * any more. This means the entire push operation |
| 394 | * has failed. |
| 395 | */ |
| 396 | return FALSE; |
| 397 | } |
| 398 | |
| 399 | /* |
| 400 | * Write the new path into sparegrid. Also save the new |
| 401 | * endpoint locations, in case they've changed. |
| 402 | */ |
| 403 | jp = last; |
| 404 | j = ctx->dist[jp]; |
| 405 | while (1) { |
| 406 | int d; |
| 407 | |
| 408 | if (ctx->sparegrid[jp] >= 0) { |
| 409 | if (ctx->pathspare[ctx->sparegrid[jp]] == 2) |
| 410 | return FALSE; /* somehow we've hit a fixed path */ |
| 411 | ctx->pathspare[ctx->sparegrid[jp]] = 1; /* broken */ |
| 412 | } |
| 413 | ctx->sparegrid[jp] = i; |
| 414 | |
| 415 | if (j == 0) |
| 416 | break; |
| 417 | |
| 418 | /* |
| 419 | * Now look at the neighbours of jp to find one |
| 420 | * which has dist[] one less. |
| 421 | */ |
| 422 | for (d = 0; d < 4; d++) { |
| 423 | int jx = (jp % w) + DX(d), jy = (jp / w) + DY(d); |
| 424 | if (jx >= 0 && jx < w && jy >= 0 && jy < w && |
| 425 | ctx->dist[jy*w+jx] == j-1) { |
| 426 | jp = jy*w+jx; |
| 427 | j--; |
| 428 | break; |
| 429 | } |
| 430 | } |
| 431 | assert(d < 4); |
| 432 | } |
| 433 | |
| 434 | ctx->sparepathends[i*2] = first; |
| 435 | ctx->sparepathends[i*2+1] = last; |
| 436 | //printf("new ends of path %d: %d,%d\n", i, first, last); |
| 437 | ctx->pathspare[i] = 2; /* fixed */ |
| 438 | } |
| 439 | } |
| 440 | |
| 441 | /* |
| 442 | * If we got here, the extension was successful! |
| 443 | */ |
| 444 | memcpy(ctx->grid, ctx->sparegrid, w*h*sizeof(int)); |
| 445 | memcpy(ctx->pathends, ctx->sparepathends, ctx->npaths*2*sizeof(int)); |
| 446 | return TRUE; |
| 447 | } |
| 448 | |
| 449 | /* |
| 450 | * Tries to add a new path to the grid. |
| 451 | */ |
| 452 | static int add_path(struct genctx *ctx, random_state *rs) |
| 453 | { |
| 454 | int w = ctx->w, h = ctx->h; |
| 455 | int i, ii, n; |
| 456 | |
| 457 | /* |
| 458 | * Our strategy is: |
| 459 | * - randomly choose an empty square in the grid |
| 460 | * - do a BFS from that point to find a long path starting |
| 461 | * from it |
| 462 | * - if we run out of viable empty squares, return failure. |
| 463 | */ |
| 464 | |
| 465 | /* |
| 466 | * Use `sparegrid' to collect a list of empty squares. |
| 467 | */ |
| 468 | n = 0; |
| 469 | for (i = 0; i < w*h; i++) |
| 470 | if (ctx->grid[i] == -1) |
| 471 | ctx->sparegrid[n++] = i; |
| 472 | |
| 473 | /* |
| 474 | * Shuffle the grid. |
| 475 | */ |
| 476 | for (i = n; i-- > 1 ;) { |
| 477 | int k = random_upto(rs, i+1); |
| 478 | if (k != i) { |
| 479 | int t = ctx->sparegrid[i]; |
| 480 | ctx->sparegrid[i] = ctx->sparegrid[k]; |
| 481 | ctx->sparegrid[k] = t; |
| 482 | } |
| 483 | } |
| 484 | |
| 485 | /* |
| 486 | * Loop over it trying to add paths. This looks like a |
| 487 | * horrifying N^4 algorithm (that is, (w*h)^2), but I predict |
| 488 | * that in fact the worst case will very rarely arise because |
| 489 | * when there's lots of grid space an attempt will succeed very |
| 490 | * quickly. |
| 491 | */ |
| 492 | for (ii = 0; ii < n; ii++) { |
| 493 | int i = ctx->sparegrid[ii]; |
| 494 | int y = i / w, x = i % w, nsq; |
| 495 | int r, c, j; |
| 496 | |
| 497 | /* |
| 498 | * BFS from here to find long paths. |
| 499 | */ |
| 500 | nsq = bfs(w, h, ctx->grid, x, y, ctx->dist, ctx->list); |
| 501 | |
| 502 | /* |
| 503 | * If there aren't any long enough, give up immediately. |
| 504 | */ |
| 505 | assert(nsq > 0); /* must be the start square at least! */ |
| 506 | if (ctx->dist[ctx->list[nsq-1]] < 3) |
| 507 | continue; |
| 508 | |
| 509 | /* |
| 510 | * Find the first viable endpoint in ctx->list (i.e. the |
| 511 | * first point with distance at least three). I could |
| 512 | * binary-search for this, but that would be O(log N) |
| 513 | * whereas in fact I can get a constant time bound by just |
| 514 | * searching up from the start - after all, there can be at |
| 515 | * most 13 points at _less_ than distance 3 from the |
| 516 | * starting one! |
| 517 | */ |
| 518 | for (j = 0; j < nsq; j++) |
| 519 | if (ctx->dist[ctx->list[j]] >= 3) |
| 520 | break; |
| 521 | assert(j < nsq); /* we tested above that there was one */ |
| 522 | |
| 523 | /* |
| 524 | * Now we know that any element of `list' between j and nsq |
| 525 | * would be valid in principle. However, we want a few long |
| 526 | * paths rather than many small ones, so select only those |
| 527 | * elements which are either the maximum length or one |
| 528 | * below it. |
| 529 | */ |
| 530 | while (ctx->dist[ctx->list[j]] + 1 < ctx->dist[ctx->list[nsq-1]]) |
| 531 | j++; |
| 532 | r = j + random_upto(rs, nsq - j); |
| 533 | j = ctx->list[r]; |
| 534 | |
| 535 | /* |
| 536 | * And that's our endpoint. Mark the new path on the grid. |
| 537 | */ |
| 538 | c = newpath(ctx); |
| 539 | ctx->pathends[c*2] = i; |
| 540 | ctx->pathends[c*2+1] = j; |
| 541 | ctx->grid[j] = c; |
| 542 | while (j != i) { |
| 543 | int d, np, index, pts[4]; |
| 544 | np = 0; |
| 545 | for (d = 0; d < 4; d++) { |
| 546 | int xn = (j % w) + DX(d), yn = (j / w) + DY(d); |
| 547 | if (xn >= 0 && xn < w && yn >= 0 && yn < w && |
| 548 | ctx->dist[yn*w+xn] == ctx->dist[j] - 1) |
| 549 | pts[np++] = yn*w+xn; |
| 550 | } |
| 551 | if (np > 1) |
| 552 | index = random_upto(rs, np); |
| 553 | else |
| 554 | index = 0; |
| 555 | j = pts[index]; |
| 556 | ctx->grid[j] = c; |
| 557 | } |
| 558 | |
| 559 | return TRUE; |
| 560 | } |
| 561 | |
| 562 | return FALSE; |
| 563 | } |
| 564 | |
| 565 | /* |
| 566 | * The main grid generation loop. |
| 567 | */ |
| 568 | static void gridgen_mainloop(struct genctx *ctx, random_state *rs) |
| 569 | { |
| 570 | int w = ctx->w, h = ctx->h; |
| 571 | int i, n; |
| 572 | |
| 573 | /* |
| 574 | * The generation algorithm doesn't always converge. Loop round |
| 575 | * until it does. |
| 576 | */ |
| 577 | while (1) { |
| 578 | for (i = 0; i < w*h; i++) |
| 579 | ctx->grid[i] = -1; |
| 580 | ctx->npaths = 0; |
| 581 | |
| 582 | while (1) { |
| 583 | /* |
| 584 | * See if the grid is full. |
| 585 | */ |
| 586 | for (i = 0; i < w*h; i++) |
| 587 | if (ctx->grid[i] < 0) |
| 588 | break; |
| 589 | if (i == w*h) |
| 590 | return; |
| 591 | |
| 592 | #ifdef GENERATION_DIAGNOSTICS |
| 593 | { |
| 594 | int x, y; |
| 595 | for (y = 0; y < h; y++) { |
| 596 | printf("|"); |
| 597 | for (x = 0; x < w; x++) { |
| 598 | if (ctx->grid[y*w+x] >= 0) |
| 599 | printf("%2d", ctx->grid[y*w+x]); |
| 600 | else |
| 601 | printf(" ."); |
| 602 | } |
| 603 | printf(" |\n"); |
| 604 | } |
| 605 | } |
| 606 | #endif |
| 607 | /* |
| 608 | * Try adding a path. |
| 609 | */ |
| 610 | if (add_path(ctx, rs)) { |
| 611 | #ifdef GENERATION_DIAGNOSTICS |
| 612 | printf("added path\n"); |
| 613 | #endif |
| 614 | continue; |
| 615 | } |
| 616 | |
| 617 | /* |
| 618 | * Try extending a path. First list all the possible |
| 619 | * extensions. |
| 620 | */ |
| 621 | for (i = 0; i < ctx->npaths * 8; i++) |
| 622 | ctx->extends[i] = i; |
| 623 | n = i; |
| 624 | |
| 625 | /* |
| 626 | * Then shuffle the list. |
| 627 | */ |
| 628 | for (i = n; i-- > 1 ;) { |
| 629 | int k = random_upto(rs, i+1); |
| 630 | if (k != i) { |
| 631 | int t = ctx->extends[i]; |
| 632 | ctx->extends[i] = ctx->extends[k]; |
| 633 | ctx->extends[k] = t; |
| 634 | } |
| 635 | } |
| 636 | |
| 637 | /* |
| 638 | * Now try each one in turn until one works. |
| 639 | */ |
| 640 | for (i = 0; i < n; i++) { |
| 641 | int p, d, e; |
| 642 | p = ctx->extends[i]; |
| 643 | d = p % 4; |
| 644 | p /= 4; |
| 645 | e = p % 2; |
| 646 | p /= 2; |
| 647 | |
| 648 | #ifdef GENERATION_DIAGNOSTICS |
| 649 | printf("trying to extend path %d end %d (%d,%d) in dir %d\n", p, e, |
| 650 | ctx->pathends[p*2+e] % w, |
| 651 | ctx->pathends[p*2+e] / w, d); |
| 652 | #endif |
| 653 | if (extend_path(ctx, p, e, d)) { |
| 654 | #ifdef GENERATION_DIAGNOSTICS |
| 655 | printf("extended path %d end %d (%d,%d) in dir %d\n", p, e, |
| 656 | ctx->pathends[p*2+e] % w, |
| 657 | ctx->pathends[p*2+e] / w, d); |
| 658 | #endif |
| 659 | break; |
| 660 | } |
| 661 | } |
| 662 | |
| 663 | if (i < n) |
| 664 | continue; |
| 665 | |
| 666 | break; |
| 667 | } |
| 668 | } |
| 669 | } |
| 670 | |
| 671 | /* |
| 672 | * Wrapper function which deals with the boring bits such as |
| 673 | * removing the solution from the generated grid, shuffling the |
| 674 | * numeric labels and creating/disposing of the context structure. |
| 675 | */ |
| 676 | static int *gridgen(int w, int h, random_state *rs) |
| 677 | { |
| 678 | struct genctx *ctx; |
| 679 | int *ret; |
| 680 | int i; |
| 681 | |
| 682 | ctx = new_genctx(w, h); |
| 683 | |
| 684 | gridgen_mainloop(ctx, rs); |
| 685 | |
| 686 | /* |
| 687 | * There is likely to be an ordering bias in the numbers |
| 688 | * (longer paths on lower numbers due to there having been more |
| 689 | * grid space when laying them down). So we must shuffle the |
| 690 | * numbers. We use ctx->pathspare for this. |
| 691 | * |
| 692 | * This is also as good a time as any to shift to numbering |
| 693 | * from 1, for display to the user. |
| 694 | */ |
| 695 | for (i = 0; i < ctx->npaths; i++) |
| 696 | ctx->pathspare[i] = i+1; |
| 697 | for (i = ctx->npaths; i-- > 1 ;) { |
| 698 | int k = random_upto(rs, i+1); |
| 699 | if (k != i) { |
| 700 | int t = ctx->pathspare[i]; |
| 701 | ctx->pathspare[i] = ctx->pathspare[k]; |
| 702 | ctx->pathspare[k] = t; |
| 703 | } |
| 704 | } |
| 705 | |
| 706 | /* FIXME: remove this at some point! */ |
| 707 | { |
| 708 | int y, x; |
| 709 | for (y = 0; y < h; y++) { |
| 710 | printf("|"); |
| 711 | for (x = 0; x < w; x++) { |
| 712 | assert(ctx->grid[y*w+x] >= 0); |
| 713 | printf("%2d", ctx->pathspare[ctx->grid[y*w+x]]); |
| 714 | } |
| 715 | printf(" |\n"); |
| 716 | } |
| 717 | printf("\n"); |
| 718 | } |
| 719 | |
| 720 | /* |
| 721 | * Clear the grid, and write in just the endpoints. |
| 722 | */ |
| 723 | for (i = 0; i < w*h; i++) |
| 724 | ctx->grid[i] = 0; |
| 725 | for (i = 0; i < ctx->npaths; i++) { |
| 726 | ctx->grid[ctx->pathends[i*2]] = |
| 727 | ctx->grid[ctx->pathends[i*2+1]] = ctx->pathspare[i]; |
| 728 | } |
| 729 | |
| 730 | ret = ctx->grid; |
| 731 | ctx->grid = NULL; |
| 732 | |
| 733 | free_genctx(ctx); |
| 734 | |
| 735 | return ret; |
| 736 | } |
| 737 | |
| 738 | #ifdef TEST_GEN |
| 739 | |
| 740 | #define TEST_GENERAL |
| 741 | |
| 742 | int main(void) |
| 743 | { |
| 744 | int w = 10, h = 8; |
| 745 | random_state *rs = random_init("12345", 5); |
| 746 | int x, y, i, *grid; |
| 747 | |
| 748 | for (i = 0; i < 10; i++) { |
| 749 | grid = gridgen(w, h, rs); |
| 750 | |
| 751 | for (y = 0; y < h; y++) { |
| 752 | printf("|"); |
| 753 | for (x = 0; x < w; x++) { |
| 754 | if (grid[y*w+x] > 0) |
| 755 | printf("%2d", grid[y*w+x]); |
| 756 | else |
| 757 | printf(" ."); |
| 758 | } |
| 759 | printf(" |\n"); |
| 760 | } |
| 761 | printf("\n"); |
| 762 | |
| 763 | sfree(grid); |
| 764 | } |
| 765 | |
| 766 | return 0; |
| 767 | } |
| 768 | #endif |
| 769 | |
| 770 | #ifdef TEST_GENERAL |
| 771 | #include <stdarg.h> |
| 772 | |
| 773 | void fatal(char *fmt, ...) |
| 774 | { |
| 775 | va_list ap; |
| 776 | |
| 777 | fprintf(stderr, "fatal error: "); |
| 778 | |
| 779 | va_start(ap, fmt); |
| 780 | vfprintf(stderr, fmt, ap); |
| 781 | va_end(ap); |
| 782 | |
| 783 | fprintf(stderr, "\n"); |
| 784 | exit(1); |
| 785 | } |
| 786 | #endif |