f278dcf4 |
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 |