diff options
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/path.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/path.c | 883 |
1 files changed, 0 insertions, 883 deletions
diff --git a/apps/plugins/puzzles/src/unfinished/path.c b/apps/plugins/puzzles/src/unfinished/path.c deleted file mode 100644 index fe5a47fd2a..0000000000 --- a/apps/plugins/puzzles/src/unfinished/path.c +++ /dev/null @@ -1,883 +0,0 @@ -/* - * Experimental grid generator for Nikoli's `Number Link' puzzle. - */ - -#include <stdio.h> -#include <stdlib.h> -#include <assert.h> -#include "puzzles.h" - -/* - * 2005-07-08: This is currently a Path grid generator which will - * construct valid grids at a plausible speed. However, the grids - * are not of suitable quality to be used directly as puzzles. - * - * The basic strategy is to start with an empty grid, and - * repeatedly either (a) add a new path to it, or (b) extend one - * end of a path by one square in some direction and push other - * paths into new shapes in the process. The effect of this is that - * we are able to construct a set of paths which between them fill - * the entire grid. - * - * Quality issues: if we set the main loop to do (a) where possible - * and (b) only where necessary, we end up with a grid containing a - * few too many small paths, which therefore doesn't make for an - * interesting puzzle. If we reverse the priority so that we do (b) - * where possible and (a) only where necessary, we end up with some - * staggeringly interwoven grids with very very few separate paths, - * but the result of this is that there's invariably a solution - * other than the intended one which leaves many grid squares - * unfilled. There's also a separate problem which is that many - * grids have really boring and obvious paths in them, such as the - * entire bottom row of the grid being taken up by a single path. - * - * It's not impossible that a few tweaks might eliminate or reduce - * the incidence of boring paths, and might also find a happy - * medium between too many and too few. There remains the question - * of unique solutions, however. I fear there is no alternative but - * to write - somehow! - a solver. - * - * While I'm here, some notes on UI strategy for the parts of the - * puzzle implementation that _aren't_ the generator: - * - * - data model is to track connections between adjacent squares, - * so that you aren't limited to extending a path out from each - * number but can also mark sections of path which you know - * _will_ come in handy later. - * - * - user interface is to click in one square and drag to an - * adjacent one, thus creating a link between them. We can - * probably tolerate rapid mouse motion causing a drag directly - * to a square which is a rook move away, but any other rapid - * motion is ambiguous and probably the best option is to wait - * until the mouse returns to a square we know how to reach. - * - * - a drag causing the current path to backtrack has the effect - * of removing bits of it. - * - * - the UI should enforce at all times the constraint that at - * most two links can come into any square. - * - * - my Cunning Plan for actually implementing this: the game_ui - * contains a grid-sized array, which is copied from the current - * game_state on starting a drag. While a drag is active, the - * contents of the game_ui is adjusted with every mouse motion, - * and is displayed _in place_ of the game_state itself. On - * termination of a drag, the game_ui array is copied back into - * the new game_state (or rather, a string move is encoded which - * has precisely the set of link changes to cause that effect). - */ - -/* - * 2020-05-11: some thoughts on a solver. - * - * Consider this example puzzle, from Wikipedia: - * - * ---4--- - * -3--25- - * ---31-- - * ---5--- - * ------- - * --1---- - * 2---4-- - * - * The kind of deduction that a human wants to make here is: which way - * does the path between the 4s go? In particular, does it go round - * the left of the W-shaped cluster of endpoints, or round the right - * of it? It's clear at a glance that it must go to the right, because - * _any_ path between the 4s that goes to the left of that cluster, no - * matter what detailed direction it takes, will disconnect the - * remaining grid squares into two components, with the two 2s not in - * the same component. So we immediately know that the path between - * the 4s _must_ go round the right-hand side of the grid. - * - * How do you model that global and topological reasoning in a - * computer? - * - * The most plausible idea I've seen so far is to use fundamental - * groups. The fundamental group of loops based at a given point in a - * space is a free group, under loop concatenation and up to homotopy, - * generated by the loops that go in each direction around each hole - * in the space. In this case, the 'holes' are clues, or connected - * groups of clues. - * - * So you might be able to enumerate all the homotopy classes of paths - * between (say) the two 4s as follows. Start with any old path - * between them (say, find the first one that breadth-first search - * will give you). Choose one of the 4s to regard as the base point - * (arbitrarily). Then breadth-first search among the space of _paths_ - * by the following procedure. Given a candidate path, append to it - * each of the possible loops that starts from the base point, - * circumnavigates one clue cluster, and returns to the base point. - * The result will typically be a path that retraces its steps and - * self-intersects. Now adjust it homotopically so that it doesn't. If - * that can't be done, then we haven't generated a fresh candidate - * path; if it can, then we've got a new path that is not homotopic to - * any path we already had, so add it to our list and queue it up to - * become the starting point of this search later. - * - * The idea is that this should exhaustively enumerate, up to - * homotopy, the different ways in which the two 4s can connect to - * each other within the constraint that you have to actually fit the - * path non-self-intersectingly into this grid. Then you can keep a - * list of those homotopy classes in mind, and start ruling them out - * by techniques like the connectivity approach described above. - * Hopefully you end up narrowing down to few enough homotopy classes - * that you can deduce something concrete about actual squares of the - * grid - for example, here, that if the path between 4s has to go - * round the right, then we know some specific squares it must go - * through, so we can fill those in. And then, having filled in a - * piece of the middle of a path, you can now regard connecting the - * ultimate endpoints to that mid-section as two separate subproblems, - * so you've reduced to a simpler instance of the same puzzle. - * - * But I don't know whether all of this actually works. I more or less - * believe the process for enumerating elements of the free group; but - * I'm not as confident that when you find a group element that won't - * fit in the grid, you'll never have to consider its descendants in - * the BFS either. And I'm assuming that 'unwind the self-intersection - * homotopically' is a thing that can actually be turned into a - * sensible algorithm. - * - * -------- - * - * Another thing that might be needed is to characterise _which_ - * homotopy class a given path is in. - * - * For this I think it's sufficient to choose a collection of paths - * along the _edges_ of the square grid, each of which connects two of - * the holes in the grid (including the grid exterior, which counts as - * a huge hole), such that they form a spanning tree between the - * holes. Then assign each of those paths an orientation, so that - * crossing it in one direction counts as 'positive' and the other - * 'negative'. Now analyse a candidate path from one square to another - * by following it and noting down which of those paths it crosses in - * which direction, then simplifying the result like a free group word - * (i.e. adjacent + and - crossings of the same path cancel out). - * - * -------- - * - * If we choose those paths to be of minimal length, then we can get - * an upper bound on the number of homotopy classes by observing that - * you can't traverse any of those barriers more times than will fit - * non-self-intersectingly in the grid. That might be an alternative - * method of bounding the search through the fundamental group to only - * finitely many possibilities. - */ - -/* - * Standard notation for directions. - */ -#define L 0 -#define U 1 -#define R 2 -#define D 3 -#define DX(dir) ( (dir)==L ? -1 : (dir)==R ? +1 : 0) -#define DY(dir) ( (dir)==U ? -1 : (dir)==D ? +1 : 0) - -/* - * Perform a breadth-first search over a grid of squares with the - * colour of square (X,Y) given by grid[Y*w+X]. The search begins - * at (x,y), and finds all squares which are the same colour as - * (x,y) and reachable from it by orthogonal moves. On return: - * - dist[Y*w+X] gives the distance of (X,Y) from (x,y), or -1 if - * unreachable or a different colour - * - the returned value is the number of reachable squares, - * including (x,y) itself - * - list[0] up to list[returned value - 1] list those squares, in - * increasing order of distance from (x,y) (and in arbitrary - * order within that). - */ -static int bfs(int w, int h, int *grid, int x, int y, int *dist, int *list) -{ - int i, j, c, listsize, listdone; - - /* - * Start by clearing the output arrays. - */ - for (i = 0; i < w*h; i++) - dist[i] = list[i] = -1; - - /* - * Set up the initial list. - */ - listsize = 1; - listdone = 0; - list[0] = y*w+x; - dist[y*w+x] = 0; - c = grid[y*w+x]; - - /* - * Repeatedly process a square and add any extra squares to the - * end of list. - */ - while (listdone < listsize) { - i = list[listdone++]; - y = i / w; - x = i % w; - for (j = 0; j < 4; j++) { - int xx, yy, ii; - - xx = x + DX(j); - yy = y + DY(j); - ii = yy*w+xx; - - if (xx >= 0 && xx < w && yy >= 0 && yy < h && - grid[ii] == c && dist[ii] == -1) { - dist[ii] = dist[i] + 1; - assert(listsize < w*h); - list[listsize++] = ii; - } - } - } - - return listsize; -} - -struct genctx { - int w, h; - int *grid, *sparegrid, *sparegrid2, *sparegrid3; - int *dist, *list; - - int npaths, pathsize; - int *pathends, *sparepathends; /* 2*npaths entries */ - int *pathspare; /* npaths entries */ - int *extends; /* 8*npaths entries */ -}; - -static struct genctx *new_genctx(int w, int h) -{ - struct genctx *ctx = snew(struct genctx); - ctx->w = w; - ctx->h = h; - ctx->grid = snewn(w * h, int); - ctx->sparegrid = snewn(w * h, int); - ctx->sparegrid2 = snewn(w * h, int); - ctx->sparegrid3 = snewn(w * h, int); - ctx->dist = snewn(w * h, int); - ctx->list = snewn(w * h, int); - ctx->npaths = ctx->pathsize = 0; - ctx->pathends = ctx->sparepathends = ctx->pathspare = ctx->extends = NULL; - return ctx; -} - -static void free_genctx(struct genctx *ctx) -{ - sfree(ctx->grid); - sfree(ctx->sparegrid); - sfree(ctx->sparegrid2); - sfree(ctx->sparegrid3); - sfree(ctx->dist); - sfree(ctx->list); - sfree(ctx->pathends); - sfree(ctx->sparepathends); - sfree(ctx->pathspare); - sfree(ctx->extends); -} - -static int newpath(struct genctx *ctx) -{ - int n; - - n = ctx->npaths++; - if (ctx->npaths > ctx->pathsize) { - ctx->pathsize += 16; - ctx->pathends = sresize(ctx->pathends, ctx->pathsize*2, int); - ctx->sparepathends = sresize(ctx->sparepathends, ctx->pathsize*2, int); - ctx->pathspare = sresize(ctx->pathspare, ctx->pathsize, int); - ctx->extends = sresize(ctx->extends, ctx->pathsize*8, int); - } - return n; -} - -static int is_endpoint(struct genctx *ctx, int x, int y) -{ - int w = ctx->w, h = ctx->h, c; - - assert(x >= 0 && x < w && y >= 0 && y < h); - - c = ctx->grid[y*w+x]; - if (c < 0) - return false; /* empty square is not an endpoint! */ - assert(c >= 0 && c < ctx->npaths); - if (ctx->pathends[c*2] == y*w+x || ctx->pathends[c*2+1] == y*w+x) - return true; - return false; -} - -/* - * Tries to extend a path by one square in the given direction, - * pushing other paths around if necessary. Returns true on success - * or false on failure. - */ -static int extend_path(struct genctx *ctx, int path, int end, int direction) -{ - int w = ctx->w, h = ctx->h; - int x, y, xe, ye, cut; - int i, j, jp, n, first, last; - - assert(path >= 0 && path < ctx->npaths); - assert(end == 0 || end == 1); - - /* - * Find the endpoint of the path and the point we plan to - * extend it into. - */ - y = ctx->pathends[path * 2 + end] / w; - x = ctx->pathends[path * 2 + end] % w; - assert(x >= 0 && x < w && y >= 0 && y < h); - - xe = x + DX(direction); - ye = y + DY(direction); - if (xe < 0 || xe >= w || ye < 0 || ye >= h) - return false; /* could not extend in this direction */ - - /* - * We don't extend paths _directly_ into endpoints of other - * paths, although we don't mind too much if a knock-on effect - * of an extension is to push part of another path into a third - * path's endpoint. - */ - if (is_endpoint(ctx, xe, ye)) - return false; - - /* - * We can't extend a path back the way it came. - */ - if (ctx->grid[ye*w+xe] == path) - return false; - - /* - * Paths may not double back on themselves. Check if the new - * point is adjacent to any point of this path other than (x,y). - */ - for (j = 0; j < 4; j++) { - int xf, yf; - - xf = xe + DX(j); - yf = ye + DY(j); - - if (xf >= 0 && xf < w && yf >= 0 && yf < h && - (xf != x || yf != y) && ctx->grid[yf*w+xf] == path) - return false; - } - - /* - * Now we're convinced it's valid to _attempt_ the extension. - * It may still fail if we run out of space to push other paths - * into. - * - * So now we can set up our temporary data structures. We will - * need: - * - * - a spare copy of the grid on which to gradually move paths - * around (sparegrid) - * - * - a second spare copy with which to remember how paths - * looked just before being cut (sparegrid2). FIXME: is - * sparegrid2 necessary? right now it's never different from - * grid itself - * - * - a third spare copy with which to do the internal - * calculations involved in reconstituting a cut path - * (sparegrid3) - * - * - something to track which paths currently need - * reconstituting after being cut, and which have already - * been cut (pathspare) - * - * - a spare copy of pathends to store the altered states in - * (sparepathends) - */ - memcpy(ctx->sparegrid, ctx->grid, w*h*sizeof(int)); - memcpy(ctx->sparegrid2, ctx->grid, w*h*sizeof(int)); - memcpy(ctx->sparepathends, ctx->pathends, ctx->npaths*2*sizeof(int)); - for (i = 0; i < ctx->npaths; i++) - ctx->pathspare[i] = 0; /* 0=untouched, 1=broken, 2=fixed */ - - /* - * Working in sparegrid, actually extend the path. If it cuts - * another, begin a loop in which we restore any cut path by - * moving it out of the way. - */ - cut = ctx->sparegrid[ye*w+xe]; - ctx->sparegrid[ye*w+xe] = path; - ctx->sparepathends[path*2+end] = ye*w+xe; - ctx->pathspare[path] = 2; /* this one is sacrosanct */ - if (cut >= 0) { - assert(cut >= 0 && cut < ctx->npaths); - ctx->pathspare[cut] = 1; /* broken */ - - while (1) { - for (i = 0; i < ctx->npaths; i++) - if (ctx->pathspare[i] == 1) - break; - if (i == ctx->npaths) - break; /* we're done */ - - /* - * Path i needs restoring. So walk along its original - * track (as given in sparegrid2) and see where it's - * been cut. Where it has, surround the cut points in - * the same colour, without overwriting already-fixed - * paths. - */ - memcpy(ctx->sparegrid3, ctx->sparegrid, w*h*sizeof(int)); - n = bfs(w, h, ctx->sparegrid2, - ctx->pathends[i*2] % w, ctx->pathends[i*2] / w, - ctx->dist, ctx->list); - first = last = -1; -if (ctx->sparegrid3[ctx->pathends[i*2]] != i || - ctx->sparegrid3[ctx->pathends[i*2+1]] != i) return false;/* FIXME */ - for (j = 0; j < n; j++) { - jp = ctx->list[j]; - assert(ctx->dist[jp] == j); - assert(ctx->sparegrid2[jp] == i); - - /* - * Wipe out the original path in sparegrid. - */ - if (ctx->sparegrid[jp] == i) - ctx->sparegrid[jp] = -1; - - /* - * Be prepared to shorten the path at either end if - * the endpoints have been stomped on. - */ - if (ctx->sparegrid3[jp] == i) { - if (first < 0) - first = jp; - last = jp; - } - - if (ctx->sparegrid3[jp] != i) { - int jx = jp % w, jy = jp / w; - int dx, dy; - for (dy = -1; dy <= +1; dy++) - for (dx = -1; dx <= +1; dx++) { - int newp, newv; - if (!dy && !dx) - continue; /* central square */ - if (jx+dx < 0 || jx+dx >= w || - jy+dy < 0 || jy+dy >= h) - continue; /* out of range */ - newp = (jy+dy)*w+(jx+dx); - newv = ctx->sparegrid3[newp]; - if (newv >= 0 && (newv == i || - ctx->pathspare[newv] == 2)) - continue; /* can't use this square */ - ctx->sparegrid3[newp] = i; - } - } - } - - if (first < 0 || last < 0) - return false; /* path is completely wiped out! */ - - /* - * Now we've covered sparegrid3 in possible squares for - * the new layout of path i. Find the actual layout - * we're going to use by bfs: we want the shortest path - * from one endpoint to the other. - */ - n = bfs(w, h, ctx->sparegrid3, first % w, first / w, - ctx->dist, ctx->list); - if (ctx->dist[last] < 2) { - /* - * Either there is no way to get between the path's - * endpoints, or the remaining endpoints simply - * aren't far enough apart to make the path viable - * any more. This means the entire push operation - * has failed. - */ - return false; - } - - /* - * Write the new path into sparegrid. Also save the new - * endpoint locations, in case they've changed. - */ - jp = last; - j = ctx->dist[jp]; - while (1) { - int d; - - if (ctx->sparegrid[jp] >= 0) { - if (ctx->pathspare[ctx->sparegrid[jp]] == 2) - return false; /* somehow we've hit a fixed path */ - ctx->pathspare[ctx->sparegrid[jp]] = 1; /* broken */ - } - ctx->sparegrid[jp] = i; - - if (j == 0) - break; - - /* - * Now look at the neighbours of jp to find one - * which has dist[] one less. - */ - for (d = 0; d < 4; d++) { - int jx = (jp % w) + DX(d), jy = (jp / w) + DY(d); - if (jx >= 0 && jx < w && jy >= 0 && jy < w && - ctx->dist[jy*w+jx] == j-1) { - jp = jy*w+jx; - j--; - break; - } - } - assert(d < 4); - } - - ctx->sparepathends[i*2] = first; - ctx->sparepathends[i*2+1] = last; -//printf("new ends of path %d: %d,%d\n", i, first, last); - ctx->pathspare[i] = 2; /* fixed */ - } - } - - /* - * If we got here, the extension was successful! - */ - memcpy(ctx->grid, ctx->sparegrid, w*h*sizeof(int)); - memcpy(ctx->pathends, ctx->sparepathends, ctx->npaths*2*sizeof(int)); - return true; -} - -/* - * Tries to add a new path to the grid. - */ -static int add_path(struct genctx *ctx, random_state *rs) -{ - int w = ctx->w, h = ctx->h; - int i, ii, n; - - /* - * Our strategy is: - * - randomly choose an empty square in the grid - * - do a BFS from that point to find a long path starting - * from it - * - if we run out of viable empty squares, return failure. - */ - - /* - * Use `sparegrid' to collect a list of empty squares. - */ - n = 0; - for (i = 0; i < w*h; i++) - if (ctx->grid[i] == -1) - ctx->sparegrid[n++] = i; - - /* - * Shuffle the grid. - */ - for (i = n; i-- > 1 ;) { - int k = random_upto(rs, i+1); - if (k != i) { - int t = ctx->sparegrid[i]; - ctx->sparegrid[i] = ctx->sparegrid[k]; - ctx->sparegrid[k] = t; - } - } - - /* - * Loop over it trying to add paths. This looks like a - * horrifying N^4 algorithm (that is, (w*h)^2), but I predict - * that in fact the worst case will very rarely arise because - * when there's lots of grid space an attempt will succeed very - * quickly. - */ - for (ii = 0; ii < n; ii++) { - int i = ctx->sparegrid[ii]; - int y = i / w, x = i % w, nsq; - int r, c, j; - - /* - * BFS from here to find long paths. - */ - nsq = bfs(w, h, ctx->grid, x, y, ctx->dist, ctx->list); - - /* - * If there aren't any long enough, give up immediately. - */ - assert(nsq > 0); /* must be the start square at least! */ - if (ctx->dist[ctx->list[nsq-1]] < 3) - continue; - - /* - * Find the first viable endpoint in ctx->list (i.e. the - * first point with distance at least three). I could - * binary-search for this, but that would be O(log N) - * whereas in fact I can get a constant time bound by just - * searching up from the start - after all, there can be at - * most 13 points at _less_ than distance 3 from the - * starting one! - */ - for (j = 0; j < nsq; j++) - if (ctx->dist[ctx->list[j]] >= 3) - break; - assert(j < nsq); /* we tested above that there was one */ - - /* - * Now we know that any element of `list' between j and nsq - * would be valid in principle. However, we want a few long - * paths rather than many small ones, so select only those - * elements which are either the maximum length or one - * below it. - */ - while (ctx->dist[ctx->list[j]] + 1 < ctx->dist[ctx->list[nsq-1]]) - j++; - r = j + random_upto(rs, nsq - j); - j = ctx->list[r]; - - /* - * And that's our endpoint. Mark the new path on the grid. - */ - c = newpath(ctx); - ctx->pathends[c*2] = i; - ctx->pathends[c*2+1] = j; - ctx->grid[j] = c; - while (j != i) { - int d, np, index, pts[4]; - np = 0; - for (d = 0; d < 4; d++) { - int xn = (j % w) + DX(d), yn = (j / w) + DY(d); - if (xn >= 0 && xn < w && yn >= 0 && yn < w && - ctx->dist[yn*w+xn] == ctx->dist[j] - 1) - pts[np++] = yn*w+xn; - } - if (np > 1) - index = random_upto(rs, np); - else - index = 0; - j = pts[index]; - ctx->grid[j] = c; - } - - return true; - } - - return false; -} - -/* - * The main grid generation loop. - */ -static void gridgen_mainloop(struct genctx *ctx, random_state *rs) -{ - int w = ctx->w, h = ctx->h; - int i, n; - - /* - * The generation algorithm doesn't always converge. Loop round - * until it does. - */ - while (1) { - for (i = 0; i < w*h; i++) - ctx->grid[i] = -1; - ctx->npaths = 0; - - while (1) { - /* - * See if the grid is full. - */ - for (i = 0; i < w*h; i++) - if (ctx->grid[i] < 0) - break; - if (i == w*h) - return; - -#ifdef GENERATION_DIAGNOSTICS - { - int x, y; - for (y = 0; y < h; y++) { - printf("|"); - for (x = 0; x < w; x++) { - if (ctx->grid[y*w+x] >= 0) - printf("%2d", ctx->grid[y*w+x]); - else - printf(" ."); - } - printf(" |\n"); - } - } -#endif - /* - * Try adding a path. - */ - if (add_path(ctx, rs)) { -#ifdef GENERATION_DIAGNOSTICS - printf("added path\n"); -#endif - continue; - } - - /* - * Try extending a path. First list all the possible - * extensions. - */ - for (i = 0; i < ctx->npaths * 8; i++) - ctx->extends[i] = i; - n = i; - - /* - * Then shuffle the list. - */ - for (i = n; i-- > 1 ;) { - int k = random_upto(rs, i+1); - if (k != i) { - int t = ctx->extends[i]; - ctx->extends[i] = ctx->extends[k]; - ctx->extends[k] = t; - } - } - - /* - * Now try each one in turn until one works. - */ - for (i = 0; i < n; i++) { - int p, d, e; - p = ctx->extends[i]; - d = p % 4; - p /= 4; - e = p % 2; - p /= 2; - -#ifdef GENERATION_DIAGNOSTICS - printf("trying to extend path %d end %d (%d,%d) in dir %d\n", p, e, - ctx->pathends[p*2+e] % w, - ctx->pathends[p*2+e] / w, d); -#endif - if (extend_path(ctx, p, e, d)) { -#ifdef GENERATION_DIAGNOSTICS - printf("extended path %d end %d (%d,%d) in dir %d\n", p, e, - ctx->pathends[p*2+e] % w, - ctx->pathends[p*2+e] / w, d); -#endif - break; - } - } - - if (i < n) - continue; - - break; - } - } -} - -/* - * Wrapper function which deals with the boring bits such as - * removing the solution from the generated grid, shuffling the - * numeric labels and creating/disposing of the context structure. - */ -static int *gridgen(int w, int h, random_state *rs) -{ - struct genctx *ctx; - int *ret; - int i; - - ctx = new_genctx(w, h); - - gridgen_mainloop(ctx, rs); - - /* - * There is likely to be an ordering bias in the numbers - * (longer paths on lower numbers due to there having been more - * grid space when laying them down). So we must shuffle the - * numbers. We use ctx->pathspare for this. - * - * This is also as good a time as any to shift to numbering - * from 1, for display to the user. - */ - for (i = 0; i < ctx->npaths; i++) - ctx->pathspare[i] = i+1; - for (i = ctx->npaths; i-- > 1 ;) { - int k = random_upto(rs, i+1); - if (k != i) { - int t = ctx->pathspare[i]; - ctx->pathspare[i] = ctx->pathspare[k]; - ctx->pathspare[k] = t; - } - } - - /* FIXME: remove this at some point! */ - { - int y, x; - for (y = 0; y < h; y++) { - printf("|"); - for (x = 0; x < w; x++) { - assert(ctx->grid[y*w+x] >= 0); - printf("%2d", ctx->pathspare[ctx->grid[y*w+x]]); - } - printf(" |\n"); - } - printf("\n"); - } - - /* - * Clear the grid, and write in just the endpoints. - */ - for (i = 0; i < w*h; i++) - ctx->grid[i] = 0; - for (i = 0; i < ctx->npaths; i++) { - ctx->grid[ctx->pathends[i*2]] = - ctx->grid[ctx->pathends[i*2+1]] = ctx->pathspare[i]; - } - - ret = ctx->grid; - ctx->grid = NULL; - - free_genctx(ctx); - - return ret; -} - -#ifdef TEST_GEN - -#define TEST_GENERAL - -int main(void) -{ - int w = 10, h = 8; - random_state *rs = random_init("12345", 5); - int x, y, i, *grid; - - for (i = 0; i < 10; i++) { - grid = gridgen(w, h, rs); - - for (y = 0; y < h; y++) { - printf("|"); - for (x = 0; x < w; x++) { - if (grid[y*w+x] > 0) - printf("%2d", grid[y*w+x]); - else - printf(" ."); - } - printf(" |\n"); - } - printf("\n"); - - sfree(grid); - } - - return 0; -} -#endif - -#ifdef TEST_GENERAL -#include <stdarg.h> - -void fatal(const char *fmt, ...) -{ - va_list ap; - - fprintf(stderr, "fatal error: "); - - va_start(ap, fmt); - vfprintf(stderr, fmt, ap); - va_end(ap); - - fprintf(stderr, "\n"); - exit(1); -} -#endif |