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