diff options
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/path.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/path.c | 786 |
1 files changed, 786 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/unfinished/path.c b/apps/plugins/puzzles/src/unfinished/path.c new file mode 100644 index 0000000000..61d6c61c6a --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/path.c | |||
@@ -0,0 +1,786 @@ | |||
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 | ||