diff options
author | Franklin Wei <franklin@rockbox.org> | 2024-08-18 21:14:07 -0400 |
---|---|---|
committer | Franklin Wei <franklin@rockbox.org> | 2024-08-25 19:30:01 -0400 |
commit | eca00638aeab59cf03287b9f298c86a6de1b5a9a (patch) | |
tree | 32f14d7c1a05f86b2ba7e91be647233570203599 /apps/plugins/puzzles/src/unfinished/path.c | |
parent | 3dd69ce23e3089ac78c512f02e59406d05302fa4 (diff) | |
download | rockbox-eca00638aeab59cf03287b9f298c86a6de1b5a9a.tar.gz rockbox-eca00638aeab59cf03287b9f298c86a6de1b5a9a.zip |
puzzles: add Slide and Sokoban.
This enables two of the "unfinished" puzzles. Slide requires a new "sticky
mouse mode" to enable dragging. The help system is disabled for these
puzzles, since they lack manual chapters.
Group is currently unplayable due to lack of request_keys() support, which
will need to be added upstream. Separate fails to draw anything.
Change-Id: I7bcff3679ac5b10b0f39c5eaa19a36b4b1fe8d53
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/path.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/path.c | 866 |
1 files changed, 866 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..2515ed0b71 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/path.c | |||
@@ -0,0 +1,866 @@ | |||
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 | */ | ||
192 | static 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 | |||
238 | struct 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 | |||
249 | static 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 | |||
265 | static 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 | |||
279 | static 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 | |||
294 | static 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 | */ | ||
314 | static 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; | ||
431 | if (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 | */ | ||
550 | static 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 | */ | ||
666 | static 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 | */ | ||
774 | static 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 | |||
840 | int 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 | ||