diff options
author | Franklin Wei <frankhwei536@gmail.com> | 2016-11-20 15:16:41 -0500 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2016-12-18 18:13:22 +0100 |
commit | 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 (patch) | |
tree | 8e7f2d6b0cbdb5d15c13457b2c3e1de69f598440 /apps/plugins/puzzles/palisade.c | |
parent | 3ee79724f6fb033d50e26ef37b33d3f8cedf0c5b (diff) | |
download | rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.tar.gz rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.zip |
Port of Simon Tatham's Puzzle Collection
Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9
MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.
Currently builds one plugin per puzzle (about 40 in total, around 100K
each on ARM), but can easily be made to build a single monolithic
overlay (800K or so on ARM).
The following games are at least partially broken for various reasons,
and have been disabled on this commit:
Cube: failed assertion with "Icosahedron" setting
Keen: input issues
Mines: weird stuff happens on target
Palisade: input issues
Solo: input issues, occasional crash on target
Towers: input issues
Undead: input issues
Unequal: input and drawing issues (concave polys)
Untangle: input issues
Features left to do:
- In-game help system
- Figure out the weird bugs
Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368
Diffstat (limited to 'apps/plugins/puzzles/palisade.c')
-rw-r--r-- | apps/plugins/puzzles/palisade.c | 1383 |
1 files changed, 1383 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/palisade.c b/apps/plugins/puzzles/palisade.c new file mode 100644 index 0000000000..c5f1b62022 --- /dev/null +++ b/apps/plugins/puzzles/palisade.c | |||
@@ -0,0 +1,1383 @@ | |||
1 | /* -*- indent-tabs-mode: nil; tab-width: 1000 -*- */ | ||
2 | |||
3 | /* | ||
4 | * palisade.c: Nikoli's `Five Cells' puzzle. | ||
5 | * | ||
6 | * See http://nikoli.co.jp/en/puzzles/five_cells.html | ||
7 | */ | ||
8 | |||
9 | /* TODO: | ||
10 | * | ||
11 | * - better solver: implement the sketched-out deductions | ||
12 | * | ||
13 | * - improve the victory flash? | ||
14 | * - the LINE_NOs look ugly against COL_FLASH. | ||
15 | * - white-blink the edges (instead), a la loopy? | ||
16 | */ | ||
17 | |||
18 | #include "rbassert.h" | ||
19 | #include <ctype.h> | ||
20 | #include <stdarg.h> | ||
21 | #include <stdio.h> | ||
22 | #include <stdlib.h> | ||
23 | #include <string.h> | ||
24 | |||
25 | #include "puzzles.h" | ||
26 | |||
27 | #define setmem(ptr, byte, len) memset((ptr), (byte), (len) * sizeof (ptr)[0]) | ||
28 | #define scopy(dst, src, len) memcpy((dst), (src), (len) * sizeof (dst)[0]) | ||
29 | #define dupmem(p, n) memcpy(smalloc(n * sizeof (*p)), p, n * sizeof (*p)) | ||
30 | #define snewa(ptr, len) (ptr) = smalloc((len) * sizeof (*ptr)) | ||
31 | #define clone(ptr) (dupmem((ptr), 1)) | ||
32 | |||
33 | static char *string(int n, const char *fmt, ...) | ||
34 | { | ||
35 | va_list va; | ||
36 | char *ret; | ||
37 | int m; | ||
38 | va_start(va, fmt); | ||
39 | m = vsprintf(snewa(ret, n + 1), fmt, va); | ||
40 | va_end(va); | ||
41 | if (m > n) fatal("memory corruption"); | ||
42 | return ret; | ||
43 | } | ||
44 | |||
45 | struct game_params { | ||
46 | int w, h, k; | ||
47 | }; | ||
48 | |||
49 | typedef char clue; | ||
50 | typedef unsigned char borderflag; | ||
51 | |||
52 | typedef struct shared_state { | ||
53 | game_params params; | ||
54 | clue *clues; | ||
55 | int refcount; | ||
56 | } shared_state; | ||
57 | |||
58 | struct game_state { | ||
59 | shared_state *shared; | ||
60 | borderflag *borders; /* length w*h */ | ||
61 | |||
62 | unsigned int completed: 1; | ||
63 | unsigned int cheated: 1; | ||
64 | }; | ||
65 | |||
66 | #define DEFAULT_PRESET 0 | ||
67 | static struct game_params presets[] = { | ||
68 | {5, 5, 5}, {8, 6, 6}, {10, 8, 8}, {15, 12, 10} | ||
69 | /* I definitely want 5x5n5 since that gives "Five Cells" its name. | ||
70 | * But how about the others? By which criteria do I choose? */ | ||
71 | }; | ||
72 | |||
73 | static game_params *default_params(void) | ||
74 | { | ||
75 | return clone(&presets[DEFAULT_PRESET]); | ||
76 | } | ||
77 | |||
78 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
79 | { | ||
80 | if (i < 0 || i >= lenof(presets)) return FALSE; | ||
81 | |||
82 | *params = clone(&presets[i]); | ||
83 | *name = string(60, "%d x %d, regions of size %d", | ||
84 | presets[i].w, presets[i].h, presets[i].k); | ||
85 | |||
86 | return TRUE; | ||
87 | } | ||
88 | |||
89 | static void free_params(game_params *params) | ||
90 | { | ||
91 | sfree(params); | ||
92 | } | ||
93 | |||
94 | static game_params *dup_params(const game_params *params) | ||
95 | { | ||
96 | return clone(params); | ||
97 | } | ||
98 | |||
99 | static void decode_params(game_params *params, char const *string) | ||
100 | { | ||
101 | params->w = params->h = params->k = atoi(string); | ||
102 | while (*string && isdigit((unsigned char)*string)) ++string; | ||
103 | if (*string == 'x') { | ||
104 | params->h = atoi(++string); | ||
105 | while (*string && isdigit((unsigned char)*string)) ++string; | ||
106 | } | ||
107 | if (*string == 'n') params->k = atoi(++string); | ||
108 | } | ||
109 | |||
110 | static char *encode_params(const game_params *params, int full) | ||
111 | { | ||
112 | return string(40, "%dx%dn%d", params->w, params->h, params->k); | ||
113 | } | ||
114 | |||
115 | #define CONFIG(i, nm, ty, iv, sv) \ | ||
116 | (ret[i].name = nm, ret[i].type = ty, ret[i].ival = iv, ret[i].sval = sv) | ||
117 | |||
118 | static config_item *game_configure(const game_params *params) | ||
119 | { | ||
120 | config_item *ret = snewn(4, config_item); | ||
121 | |||
122 | CONFIG(0, "Width", C_STRING, 0, string(20, "%d", params->w)); | ||
123 | CONFIG(1, "Height", C_STRING, 0, string(20, "%d", params->h)); | ||
124 | CONFIG(2, "Region size", C_STRING, 0, string(20, "%d", params->k)); | ||
125 | CONFIG(3, NULL, C_END, 0, NULL); | ||
126 | |||
127 | return ret; | ||
128 | } | ||
129 | |||
130 | static game_params *custom_params(const config_item *cfg) | ||
131 | { | ||
132 | game_params *params = snew(game_params); | ||
133 | |||
134 | params->w = atoi(cfg[0].sval); | ||
135 | params->h = atoi(cfg[1].sval); | ||
136 | params->k = atoi(cfg[2].sval); | ||
137 | |||
138 | return params; | ||
139 | } | ||
140 | |||
141 | /* +---+ << The one possible domino (up to symmetry). +---+---+ | ||
142 | * | 3 | | 3 | 3 | | ||
143 | * | | If two dominos are adjacent as depicted here >> +---+---+ | ||
144 | * | 3 | then it's ambiguous whether the edge between | 3 | 3 | | ||
145 | * +---+ the dominos is horizontal or vertical. +---+---+ | ||
146 | */ | ||
147 | |||
148 | static char *validate_params(const game_params *params, int full) | ||
149 | { | ||
150 | int w = params->w, h = params->h, k = params->k, wh = w * h; | ||
151 | |||
152 | if (k < 1) return "Region size must be at least one"; | ||
153 | if (w < 1) return "Width must be at least one"; | ||
154 | if (h < 1) return "Height must be at least one"; | ||
155 | if (wh % k) return "Region size must divide grid area"; | ||
156 | |||
157 | if (!full) return NULL; /* succeed partial validation */ | ||
158 | |||
159 | /* MAYBE FIXME: we (just?) don't have the UI for winning these. */ | ||
160 | if (k == wh) return "Region size must be less than the grid area"; | ||
161 | assert (k < wh); /* or wh % k != 0 */ | ||
162 | |||
163 | if (k == 2 && w != 1 && h != 1) | ||
164 | return "Region size can't be two unless width or height is one"; | ||
165 | |||
166 | return NULL; /* succeed full validation */ | ||
167 | } | ||
168 | |||
169 | /* --- Solver ------------------------------------------------------- */ | ||
170 | |||
171 | /* the solver may write at will to these arrays, but shouldn't free them */ | ||
172 | /* it's up to the client to dup/free as needed */ | ||
173 | typedef struct solver_ctx { | ||
174 | const game_params *params; /* also in shared_state */ | ||
175 | clue *clues; /* also in shared_state */ | ||
176 | borderflag *borders; /* also in game_state */ | ||
177 | int *dsf; /* particular to the solver */ | ||
178 | } solver_ctx; | ||
179 | |||
180 | /* Deductions: | ||
181 | * | ||
182 | * - If two adjacent clues do not have a border between them, this | ||
183 | * gives a lower limit on the size of their region (which is also an | ||
184 | * upper limit if both clues are 3). Rule out any non-border which | ||
185 | * would make its region either too large or too small. | ||
186 | * | ||
187 | * - If a clue, k, is adjacent to k borders or (4 - k) non-borders, | ||
188 | * the remaining edges incident to the clue are readily decided. | ||
189 | * | ||
190 | * - If a region has only one other region (e.g. square) to grow into | ||
191 | * and it's not of full size yet, grow it into that one region. | ||
192 | * | ||
193 | * - If two regions are adjacent and their combined size would be too | ||
194 | * large, put an edge between them. | ||
195 | * | ||
196 | * - If a border is adjacent to two non-borders, its last vertex-mate | ||
197 | * must also be a border. If a maybe-border is adjacent to three | ||
198 | * nonborders, the maybe-border is a non-border. | ||
199 | * | ||
200 | * - If a clue square is adjacent to several squares belonging to the | ||
201 | * same region, and enabling (disabling) those borders would violate | ||
202 | * the clue, those borders must be disabled (enabled). | ||
203 | * | ||
204 | * - If there's a path crossing only non-borders between two squares, | ||
205 | * the maybe-border between them is a non-border. | ||
206 | * (This is implicitly computed in the dsf representation) | ||
207 | */ | ||
208 | |||
209 | /* TODO deductions: | ||
210 | * | ||
211 | * If a vertex is adjacent to a LINE_YES and (4-3)*LINE_NO, at least | ||
212 | * one of the last two edges are LINE_YES. If they're adjacent to a | ||
213 | * 1, then the other two edges incident to that 1 are LINE_NO. | ||
214 | * | ||
215 | * For each square: set all as unknown, then for each k-omino and each | ||
216 | * way of placing it on that square, if that way is consistent with | ||
217 | * the board, mark its edges and interior as possible LINE_YES and | ||
218 | * LINE_NO, respectively. When all k-ominos are through, see what | ||
219 | * isn't possible and remove those impossibilities from the board. | ||
220 | * (Sounds pretty nasty for k > 4 or so.) | ||
221 | * | ||
222 | * A black-bordered subregion must have a size divisible by k. So, | ||
223 | * draw a graph with one node per dsf component and edges between | ||
224 | * those dsf components which have adjacent squares. Identify cut | ||
225 | * vertices and edges. If a cut-vertex-delimited component contains a | ||
226 | * number of squares not divisible by k, cut vertex not included, then | ||
227 | * the cut vertex must belong to the component. If it has exactly one | ||
228 | * edge _out_ of the component, the line(s) corresponding to that edge | ||
229 | * are all LINE_YES (i.e. a BORDER()). | ||
230 | * (This sounds complicated, but visually it is rather easy.) | ||
231 | * | ||
232 | * [Look at loopy and see how the at-least/-most k out of m edges | ||
233 | * thing is done. See how it is propagated across multiple squares.] | ||
234 | */ | ||
235 | |||
236 | #define EMPTY (~0) | ||
237 | |||
238 | #define BIT(i) (1 << (i)) | ||
239 | #define BORDER(i) BIT(i) | ||
240 | #define BORDER_U BORDER(0) | ||
241 | #define BORDER_R BORDER(1) | ||
242 | #define BORDER_D BORDER(2) | ||
243 | #define BORDER_L BORDER(3) | ||
244 | #define FLIP(i) ((i) ^ 2) | ||
245 | #define BORDER_MASK (BORDER_U|BORDER_R|BORDER_D|BORDER_L) | ||
246 | #define DISABLED(border) ((border) << 4) | ||
247 | #define UNDISABLED(border) ((border) >> 4) | ||
248 | |||
249 | static const int dx[4] = { 0, +1, 0, -1}; | ||
250 | static const int dy[4] = {-1, 0, +1, 0}; | ||
251 | static const int bitcount[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4}; | ||
252 | /* bitcount[x & BORDER_MASK] == number of enabled borders */ | ||
253 | |||
254 | #define COMPUTE_J (-1) | ||
255 | |||
256 | static void connect(solver_ctx *ctx, int i, int j) | ||
257 | { | ||
258 | dsf_merge(ctx->dsf, i, j); | ||
259 | } | ||
260 | |||
261 | static int connected(solver_ctx *ctx, int i, int j, int dir) | ||
262 | { | ||
263 | if (j == COMPUTE_J) j = i + dx[dir] + ctx->params->w*dy[dir]; | ||
264 | return dsf_canonify(ctx->dsf, i) == dsf_canonify(ctx->dsf, j); | ||
265 | } | ||
266 | |||
267 | static void disconnect(solver_ctx *ctx, int i, int j, int dir) | ||
268 | { | ||
269 | if (j == COMPUTE_J) j = i + dx[dir] + ctx->params->w*dy[dir]; | ||
270 | ctx->borders[i] |= BORDER(dir); | ||
271 | ctx->borders[j] |= BORDER(FLIP(dir)); | ||
272 | } | ||
273 | |||
274 | static int disconnected(solver_ctx *ctx, int i, int j, int dir) | ||
275 | { | ||
276 | assert (j == COMPUTE_J || j == i + dx[dir] + ctx->params->w*dy[dir]); | ||
277 | return ctx->borders[i] & BORDER(dir); | ||
278 | } | ||
279 | |||
280 | static int maybe(solver_ctx *ctx, int i, int j, int dir) | ||
281 | { | ||
282 | assert (j == COMPUTE_J || j == i + dx[dir] + ctx->params->w*dy[dir]); | ||
283 | return !disconnected(ctx, i, j, dir) && !connected(ctx, i, j, dir); | ||
284 | /* the ordering is important: disconnected works for invalid | ||
285 | * squares (i.e. out of bounds), connected doesn't. */ | ||
286 | } | ||
287 | |||
288 | static void solver_connected_clues_versus_region_size(solver_ctx *ctx) | ||
289 | { | ||
290 | int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir; | ||
291 | |||
292 | /* If i is connected to j and i has borders with p of the | ||
293 | * remaining three squares and j with q of the remaining three | ||
294 | * squares, then the region has size at least 1+(3-p) + 1+(3-q). | ||
295 | * If p = q = 3 then the region has size exactly 2. */ | ||
296 | |||
297 | for (i = 0; i < wh; ++i) { | ||
298 | if (ctx->clues[i] == EMPTY) continue; | ||
299 | for (dir = 0; dir < 4; ++dir) { | ||
300 | int j = i + dx[dir] + w*dy[dir]; | ||
301 | if (disconnected(ctx, i, j, dir)) continue; | ||
302 | if (ctx->clues[j] == EMPTY) continue; | ||
303 | if ((8 - ctx->clues[i] - ctx->clues[j] > ctx->params->k) || | ||
304 | (ctx->clues[i] == 3 && ctx->clues[j] == 3 && | ||
305 | ctx->params->k != 2)) | ||
306 | { | ||
307 | disconnect(ctx, i, j, dir); | ||
308 | /* changed = TRUE, but this is a one-shot... */ | ||
309 | } | ||
310 | } | ||
311 | } | ||
312 | } | ||
313 | |||
314 | static int solver_number_exhausted(solver_ctx *ctx) | ||
315 | { | ||
316 | int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir, off; | ||
317 | int changed = FALSE; | ||
318 | |||
319 | for (i = 0; i < wh; ++i) { | ||
320 | if (ctx->clues[i] == EMPTY) continue; | ||
321 | |||
322 | if (bitcount[(ctx->borders[i] & BORDER_MASK)] == ctx->clues[i]) { | ||
323 | for (dir = 0; dir < 4; ++dir) { | ||
324 | int j = i + dx[dir] + w*dy[dir]; | ||
325 | if (!maybe(ctx, i, j, dir)) continue; | ||
326 | connect(ctx, i, j); | ||
327 | changed = TRUE; | ||
328 | } | ||
329 | continue; | ||
330 | } | ||
331 | |||
332 | for (off = dir = 0; dir < 4; ++dir) { | ||
333 | int j = i + dx[dir] + w*dy[dir]; | ||
334 | if (!disconnected(ctx, i, j, dir) && connected(ctx, i, j, dir)) | ||
335 | ++off; /* ^^^ bounds checking before ^^^^^ */ | ||
336 | } | ||
337 | |||
338 | if (ctx->clues[i] == 4 - off) | ||
339 | for (dir = 0; dir < 4; ++dir) { | ||
340 | int j = i + dx[dir] + w*dy[dir]; | ||
341 | if (!maybe(ctx, i, j, dir)) continue; | ||
342 | disconnect(ctx, i, j, dir); | ||
343 | changed = TRUE; | ||
344 | } | ||
345 | } | ||
346 | |||
347 | return changed; | ||
348 | } | ||
349 | |||
350 | static int solver_not_too_big(solver_ctx *ctx) | ||
351 | { | ||
352 | int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir; | ||
353 | int changed = FALSE; | ||
354 | |||
355 | for (i = 0; i < wh; ++i) { | ||
356 | int size = dsf_size(ctx->dsf, i); | ||
357 | for (dir = 0; dir < 4; ++dir) { | ||
358 | int j = i + dx[dir] + w*dy[dir]; | ||
359 | if (!maybe(ctx, i, j, dir)) continue; | ||
360 | if (size + dsf_size(ctx->dsf, j) <= ctx->params->k) continue; | ||
361 | disconnect(ctx, i, j, dir); | ||
362 | changed = TRUE; | ||
363 | } | ||
364 | } | ||
365 | |||
366 | return changed; | ||
367 | } | ||
368 | |||
369 | static int solver_not_too_small(solver_ctx *ctx) | ||
370 | { | ||
371 | int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dir; | ||
372 | int *outs, k = ctx->params->k, ci, changed = FALSE; | ||
373 | |||
374 | snewa(outs, wh); | ||
375 | setmem(outs, -1, wh); | ||
376 | |||
377 | for (i = 0; i < wh; ++i) { | ||
378 | ci = dsf_canonify(ctx->dsf, i); | ||
379 | if (dsf_size(ctx->dsf, ci) == k) continue; | ||
380 | for (dir = 0; dir < 4; ++dir) { | ||
381 | int j = i + dx[dir] + w*dy[dir]; | ||
382 | if (!maybe(ctx, i, j, dir)) continue; | ||
383 | if (outs[ci] == -1) outs[ci] = dsf_canonify(ctx->dsf, j); | ||
384 | else if (outs[ci] != dsf_canonify(ctx->dsf, j)) outs[ci] = -2; | ||
385 | } | ||
386 | } | ||
387 | |||
388 | for (i = 0; i < wh; ++i) { | ||
389 | int j = outs[i]; | ||
390 | if (i != dsf_canonify(ctx->dsf, i)) continue; | ||
391 | if (j < 0) continue; | ||
392 | connect(ctx, i, j); /* only one place for i to grow */ | ||
393 | changed = TRUE; | ||
394 | } | ||
395 | |||
396 | sfree(outs); | ||
397 | return changed; | ||
398 | } | ||
399 | |||
400 | static int solver_no_dangling_edges(solver_ctx *ctx) | ||
401 | { | ||
402 | int w = ctx->params->w, h = ctx->params->h, r, c; | ||
403 | int changed = FALSE; | ||
404 | |||
405 | /* for each vertex */ | ||
406 | for (r = 1; r < h; ++r) | ||
407 | for (c = 1; c < w; ++c) { | ||
408 | int i = r * w + c, j = i - w - 1, noline = 0, dir; | ||
409 | int squares[4], e = -1, f = -1, de = -1, df = -1; | ||
410 | |||
411 | /* feels hacky: I align these with BORDER_[U0 R1 D2 L3] */ | ||
412 | squares[1] = squares[2] = j; | ||
413 | squares[0] = squares[3] = i; | ||
414 | |||
415 | /* for each edge adjacent to the vertex */ | ||
416 | for (dir = 0; dir < 4; ++dir) | ||
417 | if (!connected(ctx, squares[dir], COMPUTE_J, dir)) { | ||
418 | df = dir; | ||
419 | f = squares[df]; | ||
420 | if (e != -1) continue; | ||
421 | e = f; | ||
422 | de = df; | ||
423 | } else ++noline; | ||
424 | |||
425 | if (4 - noline == 1) { | ||
426 | assert (e != -1); | ||
427 | disconnect(ctx, e, COMPUTE_J, de); | ||
428 | changed = TRUE; | ||
429 | continue; | ||
430 | } | ||
431 | |||
432 | if (4 - noline != 2) continue; | ||
433 | |||
434 | assert (e != -1); | ||
435 | assert (f != -1); | ||
436 | |||
437 | if (ctx->borders[e] & BORDER(de)) { | ||
438 | if (!(ctx->borders[f] & BORDER(df))) { | ||
439 | disconnect(ctx, f, COMPUTE_J, df); | ||
440 | changed = TRUE; | ||
441 | } | ||
442 | } else if (ctx->borders[f] & BORDER(df)) { | ||
443 | disconnect(ctx, e, COMPUTE_J, de); | ||
444 | changed = TRUE; | ||
445 | } | ||
446 | } | ||
447 | |||
448 | return changed; | ||
449 | } | ||
450 | |||
451 | static int solver_equivalent_edges(solver_ctx *ctx) | ||
452 | { | ||
453 | int w = ctx->params->w, h = ctx->params->h, wh = w*h, i, dirj; | ||
454 | int changed = FALSE; | ||
455 | |||
456 | /* if a square is adjacent to two connected squares, the two | ||
457 | * borders (i,j) and (i,k) are either both on or both off. */ | ||
458 | |||
459 | for (i = 0; i < wh; ++i) { | ||
460 | int n_on = 0, n_off = 0; | ||
461 | if (ctx->clues[i] < 1 || ctx->clues[i] > 3) continue; | ||
462 | |||
463 | if (ctx->clues[i] == 2 /* don't need it otherwise */) | ||
464 | for (dirj = 0; dirj < 4; ++dirj) { | ||
465 | int j = i + dx[dirj] + w*dy[dirj]; | ||
466 | if (disconnected(ctx, i, j, dirj)) ++n_on; | ||
467 | else if (connected(ctx, i, j, dirj)) ++n_off; | ||
468 | } | ||
469 | |||
470 | for (dirj = 0; dirj < 4; ++dirj) { | ||
471 | int j = i + dx[dirj] + w*dy[dirj], dirk; | ||
472 | if (!maybe(ctx, i, j, dirj)) continue; | ||
473 | |||
474 | for (dirk = dirj + 1; dirk < 4; ++dirk) { | ||
475 | int k = i + dx[dirk] + w*dy[dirk]; | ||
476 | if (!maybe(ctx, i, k, dirk)) continue; | ||
477 | if (!connected(ctx, j, k, -1)) continue; | ||
478 | |||
479 | if (n_on + 2 > ctx->clues[i]) { | ||
480 | connect(ctx, i, j); | ||
481 | connect(ctx, i, k); | ||
482 | changed = TRUE; | ||
483 | } else if (n_off + 2 > 4 - ctx->clues[i]) { | ||
484 | disconnect(ctx, i, j, dirj); | ||
485 | disconnect(ctx, i, k, dirk); | ||
486 | changed = TRUE; | ||
487 | } | ||
488 | } | ||
489 | } | ||
490 | } | ||
491 | |||
492 | return changed; | ||
493 | } | ||
494 | |||
495 | #define UNVISITED 6 | ||
496 | |||
497 | /* build connected components in `dsf', along the lines of `borders'. */ | ||
498 | static void dfs_dsf(int i, int w, borderflag *border, int *dsf, int black) | ||
499 | { | ||
500 | int dir; | ||
501 | for (dir = 0; dir < 4; ++dir) { | ||
502 | int ii = i + dx[dir] + w*dy[dir], bdir = BORDER(dir); | ||
503 | if (black ? (border[i] & bdir) : !(border[i] & DISABLED(bdir))) | ||
504 | continue; | ||
505 | if (dsf[ii] != UNVISITED) continue; | ||
506 | dsf_merge(dsf, i, ii); | ||
507 | dfs_dsf(ii, w, border, dsf, black); | ||
508 | } | ||
509 | } | ||
510 | |||
511 | static int is_solved(const game_params *params, clue *clues, | ||
512 | borderflag *border) | ||
513 | { | ||
514 | int w = params->w, h = params->h, wh = w*h, k = params->k; | ||
515 | int i, x, y; | ||
516 | int *dsf = snew_dsf(wh); | ||
517 | |||
518 | assert (dsf[0] == UNVISITED); /* check: UNVISITED and dsf.c match up */ | ||
519 | |||
520 | /* | ||
521 | * A game is solved if: | ||
522 | * | ||
523 | * - the borders drawn on the grid divide it into connected | ||
524 | * components such that every square is in a component of the | ||
525 | * correct size | ||
526 | * - the borders also satisfy the clue set | ||
527 | */ | ||
528 | for (i = 0; i < wh; ++i) { | ||
529 | if (dsf[i] == UNVISITED) dfs_dsf(i, params->w, border, dsf, TRUE); | ||
530 | if (dsf_size(dsf, i) != k) goto error; | ||
531 | if (clues[i] == EMPTY) continue; | ||
532 | if (clues[i] != bitcount[border[i] & BORDER_MASK]) goto error; | ||
533 | } | ||
534 | |||
535 | /* | ||
536 | * ... and thirdly: | ||
537 | * | ||
538 | * - there are no *stray* borders, in that every border is | ||
539 | * actually part of the division between two components. | ||
540 | * Otherwise you could cheat by finding a subdivision which did | ||
541 | * not *exceed* any clue square's counter, and then adding a | ||
542 | * few extra edges. | ||
543 | */ | ||
544 | for (y = 0; y < h; y++) { | ||
545 | for (x = 0; x < w; x++) { | ||
546 | if (x+1 < w && (border[y*w+x] & BORDER_R) && | ||
547 | dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, y*w+(x+1))) | ||
548 | goto error; | ||
549 | if (y+1 < h && (border[y*w+x] & BORDER_D) && | ||
550 | dsf_canonify(dsf, y*w+x) == dsf_canonify(dsf, (y+1)*w+x)) | ||
551 | goto error; | ||
552 | } | ||
553 | } | ||
554 | |||
555 | sfree(dsf); | ||
556 | return TRUE; | ||
557 | |||
558 | error: | ||
559 | sfree(dsf); | ||
560 | return FALSE; | ||
561 | } | ||
562 | |||
563 | static int solver(const game_params *params, clue *clues, borderflag *borders) | ||
564 | { | ||
565 | int w = params->w, h = params->h, wh = w*h, changed; | ||
566 | solver_ctx ctx; | ||
567 | |||
568 | ctx.params = params; | ||
569 | ctx.clues = clues; | ||
570 | ctx.borders = borders; | ||
571 | ctx.dsf = snew_dsf(wh); | ||
572 | |||
573 | solver_connected_clues_versus_region_size(&ctx); /* idempotent */ | ||
574 | do { | ||
575 | changed = FALSE; | ||
576 | changed |= solver_number_exhausted(&ctx); | ||
577 | changed |= solver_not_too_big(&ctx); | ||
578 | changed |= solver_not_too_small(&ctx); | ||
579 | changed |= solver_no_dangling_edges(&ctx); | ||
580 | changed |= solver_equivalent_edges(&ctx); | ||
581 | } while (changed); | ||
582 | |||
583 | sfree(ctx.dsf); | ||
584 | |||
585 | return is_solved(params, clues, borders); | ||
586 | } | ||
587 | |||
588 | /* --- Generator ---------------------------------------------------- */ | ||
589 | |||
590 | static void init_borders(int w, int h, borderflag *borders) | ||
591 | { | ||
592 | int r, c; | ||
593 | setmem(borders, 0, w*h); | ||
594 | for (c = 0; c < w; ++c) { | ||
595 | borders[c] |= BORDER_U; | ||
596 | borders[w*h-1 - c] |= BORDER_D; | ||
597 | } | ||
598 | for (r = 0; r < h; ++r) { | ||
599 | borders[r*w] |= BORDER_L; | ||
600 | borders[w*h-1 - r*w] |= BORDER_R; | ||
601 | } | ||
602 | } | ||
603 | |||
604 | #define OUT_OF_BOUNDS(x, y, w, h) \ | ||
605 | ((x) < 0 || (x) >= (w) || (y) < 0 || (y) >= (h)) | ||
606 | |||
607 | #define xshuffle(ptr, len, rs) shuffle((ptr), (len), sizeof (ptr)[0], (rs)) | ||
608 | |||
609 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
610 | char **aux, int interactive) | ||
611 | { | ||
612 | int w = params->w, h = params->h, wh = w*h, k = params->k; | ||
613 | |||
614 | clue *numbers = snewn(wh + 1, clue), *p; | ||
615 | borderflag *rim = snewn(wh, borderflag); | ||
616 | borderflag *scratch_borders = snewn(wh, borderflag); | ||
617 | |||
618 | char *soln = snewa(*aux, wh + 2); | ||
619 | int *shuf = snewn(wh, int); | ||
620 | int *dsf = NULL, i, r, c; | ||
621 | |||
622 | int attempts = 0; | ||
623 | |||
624 | for (i = 0; i < wh; ++i) shuf[i] = i; | ||
625 | xshuffle(shuf, wh, rs); | ||
626 | |||
627 | init_borders(w, h, rim); | ||
628 | |||
629 | assert (!('@' & BORDER_MASK)); | ||
630 | *soln++ = 'S'; | ||
631 | soln[wh] = '\0'; | ||
632 | |||
633 | do { | ||
634 | ++attempts; | ||
635 | setmem(soln, '@', wh); | ||
636 | |||
637 | sfree(dsf); | ||
638 | dsf = divvy_rectangle(w, h, k, rs); | ||
639 | |||
640 | for (r = 0; r < h; ++r) | ||
641 | for (c = 0; c < w; ++c) { | ||
642 | int i = r * w + c, dir; | ||
643 | numbers[i] = 0; | ||
644 | for (dir = 0; dir < 4; ++dir) { | ||
645 | int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc; | ||
646 | if (OUT_OF_BOUNDS(cc, rr, w, h) || | ||
647 | dsf_canonify(dsf, i) != dsf_canonify(dsf, ii)) { | ||
648 | ++numbers[i]; | ||
649 | soln[i] |= BORDER(dir); | ||
650 | } | ||
651 | } | ||
652 | } | ||
653 | |||
654 | scopy(scratch_borders, rim, wh); | ||
655 | } while (!solver(params, numbers, scratch_borders)); | ||
656 | |||
657 | for (i = 0; i < wh; ++i) { | ||
658 | int j = shuf[i]; | ||
659 | clue copy = numbers[j]; | ||
660 | |||
661 | scopy(scratch_borders, rim, wh); | ||
662 | numbers[j] = EMPTY; /* strip away unnecssary clues */ | ||
663 | if (!solver(params, numbers, scratch_borders)) | ||
664 | numbers[j] = copy; | ||
665 | } | ||
666 | |||
667 | numbers[wh] = '\0'; | ||
668 | |||
669 | sfree(scratch_borders); | ||
670 | sfree(rim); | ||
671 | sfree(shuf); | ||
672 | sfree(dsf); | ||
673 | |||
674 | p = numbers; | ||
675 | r = 0; | ||
676 | for (i = 0; i < wh; ++i) { | ||
677 | if (numbers[i] != EMPTY) { | ||
678 | while (r) { | ||
679 | while (r > 26) { | ||
680 | *p++ = 'z'; | ||
681 | r -= 26; | ||
682 | } | ||
683 | *p++ = 'a'-1 + r; | ||
684 | r = 0; | ||
685 | } | ||
686 | *p++ = '0' + numbers[i]; | ||
687 | } else ++r; | ||
688 | } | ||
689 | *p++ = '\0'; | ||
690 | |||
691 | return sresize(numbers, p - numbers, clue); | ||
692 | } | ||
693 | |||
694 | static char *validate_desc(const game_params *params, const char *desc) | ||
695 | { | ||
696 | |||
697 | int w = params->w, h = params->h, wh = w*h, squares = 0; | ||
698 | |||
699 | for (/* nop */; *desc; ++desc) { | ||
700 | if (islower((unsigned char)*desc)) { | ||
701 | squares += *desc - 'a' + 1; | ||
702 | } else if (isdigit((unsigned char)*desc)) { | ||
703 | if (*desc > '4') { | ||
704 | static char buf[] = "Invalid (too large) number: '5'"; | ||
705 | assert (isdigit((unsigned char)buf[lenof(buf) - 3])); | ||
706 | buf[lenof(buf) - 3] = *desc; /* ... or 6, 7, 8, 9 :-) */ | ||
707 | return buf; | ||
708 | } | ||
709 | ++squares; | ||
710 | } else if (isprint((unsigned char)*desc)) { | ||
711 | static char buf[] = "Invalid character in data: '?'"; | ||
712 | buf[lenof(buf) - 3] = *desc; | ||
713 | return buf; | ||
714 | } else return "Invalid (unprintable) character in data"; | ||
715 | } | ||
716 | |||
717 | if (squares > wh) return "Data describes too many squares"; | ||
718 | |||
719 | return NULL; | ||
720 | } | ||
721 | |||
722 | static game_state *new_game(midend *me, const game_params *params, | ||
723 | const char *desc) | ||
724 | { | ||
725 | int w = params->w, h = params->h, wh = w*h, i; | ||
726 | game_state *state = snew(game_state); | ||
727 | |||
728 | state->shared = snew(shared_state); | ||
729 | state->shared->refcount = 1; | ||
730 | state->shared->params = *params; /* struct copy */ | ||
731 | snewa(state->shared->clues, wh); | ||
732 | |||
733 | setmem(state->shared->clues, EMPTY, wh); | ||
734 | for (i = 0; *desc; ++desc) { | ||
735 | if (isdigit((unsigned char)*desc)) state->shared->clues[i++] = *desc - '0'; | ||
736 | else if (isalpha((unsigned char)*desc)) i += *desc - 'a' + 1; | ||
737 | } | ||
738 | |||
739 | snewa(state->borders, wh); | ||
740 | init_borders(w, h, state->borders); | ||
741 | |||
742 | state->completed = (params->k == wh); | ||
743 | state->cheated = FALSE; | ||
744 | |||
745 | return state; | ||
746 | } | ||
747 | |||
748 | static game_state *dup_game(const game_state *state) | ||
749 | { | ||
750 | int wh = state->shared->params.w * state->shared->params.h; | ||
751 | game_state *ret = snew(game_state); | ||
752 | |||
753 | ret->borders = dupmem(state->borders, wh); | ||
754 | |||
755 | ret->shared = state->shared; | ||
756 | ++ret->shared->refcount; | ||
757 | |||
758 | ret->completed = state->completed; | ||
759 | ret->cheated = state->cheated; | ||
760 | |||
761 | return ret; | ||
762 | } | ||
763 | |||
764 | static void free_game(game_state *state) | ||
765 | { | ||
766 | if (--state->shared->refcount == 0) { | ||
767 | sfree(state->shared->clues); | ||
768 | sfree(state->shared); | ||
769 | } | ||
770 | sfree(state->borders); | ||
771 | sfree(state); | ||
772 | } | ||
773 | |||
774 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
775 | const char *aux, char **error) | ||
776 | { | ||
777 | int w = state->shared->params.w, h = state->shared->params.h, wh = w*h; | ||
778 | borderflag *move; | ||
779 | |||
780 | if (aux) return dupstr(aux); | ||
781 | |||
782 | snewa(move, wh + 2); | ||
783 | |||
784 | move[0] = 'S'; | ||
785 | init_borders(w, h, move + 1); | ||
786 | move[wh + 1] = '\0'; | ||
787 | |||
788 | if (solver(&state->shared->params, state->shared->clues, move + 1)) { | ||
789 | int i; | ||
790 | for (i = 0; i < wh; i++) | ||
791 | move[i+1] |= '@'; /* turn into sensible ASCII */ | ||
792 | return (char *) move; | ||
793 | } | ||
794 | |||
795 | *error = "Sorry, I can't solve this puzzle"; | ||
796 | sfree(move); | ||
797 | return NULL; | ||
798 | |||
799 | { | ||
800 | /* compile-time-assert (borderflag is-a-kind-of char). | ||
801 | * | ||
802 | * depends on zero-size arrays being disallowed. GCC says | ||
803 | * ISO C forbids this, pointing to [-Werror=edantic]. Also, | ||
804 | * it depends on type-checking of (obviously) dead code. */ | ||
805 | borderflag b[sizeof (borderflag) == sizeof (char)]; | ||
806 | char c = b[0]; b[0] = c; | ||
807 | /* we could at least in principle put this anywhere, but it | ||
808 | * seems silly to not put it where the assumption is used. */ | ||
809 | } | ||
810 | } | ||
811 | |||
812 | static int game_can_format_as_text_now(const game_params *params) | ||
813 | { | ||
814 | return TRUE; | ||
815 | } | ||
816 | |||
817 | static char *game_text_format(const game_state *state) | ||
818 | { | ||
819 | int w = state->shared->params.w, h = state->shared->params.h, r, c; | ||
820 | int cw = 4, ch = 2, gw = cw*w + 2, gh = ch * h + 1, len = gw * gh; | ||
821 | char *board; | ||
822 | |||
823 | setmem(snewa(board, len + 1), ' ', len); | ||
824 | for (r = 0; r < h; ++r) { | ||
825 | for (c = 0; c < w; ++c) { | ||
826 | int cell = r*ch*gw + cw*c, center = cell + gw*ch/2 + cw/2; | ||
827 | int i = r * w + c, clue = state->shared->clues[i]; | ||
828 | |||
829 | if (clue != EMPTY) board[center] = '0' + clue; | ||
830 | |||
831 | board[cell] = '+'; | ||
832 | |||
833 | if (state->borders[i] & BORDER_U) | ||
834 | setmem(board + cell + 1, '-', cw - 1); | ||
835 | else if (state->borders[i] & DISABLED(BORDER_U)) | ||
836 | board[cell + cw / 2] = 'x'; | ||
837 | |||
838 | if (state->borders[i] & BORDER_L) | ||
839 | board[cell + gw] = '|'; | ||
840 | else if (state->borders[i] & DISABLED(BORDER_L)) | ||
841 | board[cell + gw] = 'x'; | ||
842 | } | ||
843 | |||
844 | for (c = 0; c < ch; ++c) { | ||
845 | board[(r*ch + c)*gw + gw - 2] = c ? '|' : '+'; | ||
846 | board[(r*ch + c)*gw + gw - 1] = '\n'; | ||
847 | } | ||
848 | } | ||
849 | |||
850 | scopy(board + len - gw, board, gw); | ||
851 | board[len] = '\0'; | ||
852 | |||
853 | return board; | ||
854 | } | ||
855 | |||
856 | struct game_ui { | ||
857 | int x, y; | ||
858 | unsigned int show: 1; | ||
859 | }; | ||
860 | |||
861 | static game_ui *new_ui(const game_state *state) | ||
862 | { | ||
863 | game_ui *ui = snew(game_ui); | ||
864 | ui->x = ui->y = 0; | ||
865 | ui->show = FALSE; | ||
866 | return ui; | ||
867 | } | ||
868 | |||
869 | static void free_ui(game_ui *ui) | ||
870 | { | ||
871 | sfree(ui); | ||
872 | } | ||
873 | |||
874 | static char *encode_ui(const game_ui *ui) | ||
875 | { | ||
876 | return NULL; | ||
877 | } | ||
878 | |||
879 | static void decode_ui(game_ui *ui, const char *encoding) | ||
880 | { | ||
881 | assert (encoding == NULL); | ||
882 | } | ||
883 | |||
884 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
885 | const game_state *newstate) | ||
886 | { | ||
887 | } | ||
888 | |||
889 | typedef unsigned short dsflags; | ||
890 | |||
891 | struct game_drawstate { | ||
892 | int tilesize; | ||
893 | dsflags *grid; | ||
894 | }; | ||
895 | |||
896 | #define TILESIZE (ds->tilesize) | ||
897 | #define MARGIN (ds->tilesize / 2) | ||
898 | #define WIDTH (1 + (TILESIZE >= 16) + (TILESIZE >= 32) + (TILESIZE >= 64)) | ||
899 | #define CENTER ((ds->tilesize / 2) + WIDTH/2) | ||
900 | |||
901 | #define FROMCOORD(x) (((x) - MARGIN) / TILESIZE) | ||
902 | |||
903 | enum {MAYBE_LEFT, MAYBE_RIGHT, ON_LEFT, ON_RIGHT, OFF_LEFT, OFF_RIGHT}; | ||
904 | |||
905 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
906 | const game_drawstate *ds, int x, int y, int button) | ||
907 | { | ||
908 | int w = state->shared->params.w, h = state->shared->params.h; | ||
909 | int control = button & MOD_CTRL, shift = button & MOD_SHFT; | ||
910 | |||
911 | button &= ~MOD_MASK; | ||
912 | |||
913 | if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { | ||
914 | int gx = FROMCOORD(x), gy = FROMCOORD(y), possible = BORDER_MASK; | ||
915 | int px = (x - MARGIN) % TILESIZE, py = (y - MARGIN) % TILESIZE; | ||
916 | int hx, hy, dir, i; | ||
917 | |||
918 | if (OUT_OF_BOUNDS(gx, gy, w, h)) return NULL; | ||
919 | |||
920 | ui->x = gx; | ||
921 | ui->y = gy; | ||
922 | |||
923 | /* find edge closest to click point */ | ||
924 | possible &=~ (2*px < TILESIZE ? BORDER_R : BORDER_L); | ||
925 | possible &=~ (2*py < TILESIZE ? BORDER_D : BORDER_U); | ||
926 | px = min(px, TILESIZE - px); | ||
927 | py = min(py, TILESIZE - py); | ||
928 | possible &=~ (px < py ? (BORDER_U|BORDER_D) : (BORDER_L|BORDER_R)); | ||
929 | |||
930 | for (dir = 0; dir < 4 && BORDER(dir) != possible; ++dir); | ||
931 | if (dir == 4) return NULL; /* there's not exactly one such edge */ | ||
932 | |||
933 | hx = gx + dx[dir]; | ||
934 | hy = gy + dy[dir]; | ||
935 | |||
936 | if (OUT_OF_BOUNDS(hx, hy, w, h)) return NULL; | ||
937 | |||
938 | ui->show = FALSE; | ||
939 | |||
940 | i = gy * w + gx; | ||
941 | switch ((button == RIGHT_BUTTON) | | ||
942 | ((state->borders[i] & BORDER(dir)) >> dir << 1) | | ||
943 | ((state->borders[i] & DISABLED(BORDER(dir))) >> dir >> 2)) { | ||
944 | |||
945 | case MAYBE_LEFT: | ||
946 | case ON_LEFT: | ||
947 | case ON_RIGHT: | ||
948 | return string(80, "F%d,%d,%dF%d,%d,%d", | ||
949 | gx, gy, BORDER(dir), | ||
950 | hx, hy, BORDER(FLIP(dir))); | ||
951 | |||
952 | case MAYBE_RIGHT: | ||
953 | case OFF_LEFT: | ||
954 | case OFF_RIGHT: | ||
955 | return string(80, "F%d,%d,%dF%d,%d,%d", | ||
956 | gx, gy, DISABLED(BORDER(dir)), | ||
957 | hx, hy, DISABLED(BORDER(FLIP(dir)))); | ||
958 | } | ||
959 | } | ||
960 | |||
961 | if (IS_CURSOR_MOVE(button)) { | ||
962 | ui->show = TRUE; | ||
963 | if (control || shift) { | ||
964 | borderflag flag = 0, newflag; | ||
965 | int dir, i = ui->y * w + ui->x; | ||
966 | x = ui->x; | ||
967 | y = ui->y; | ||
968 | move_cursor(button, &x, &y, w, h, FALSE); | ||
969 | if (OUT_OF_BOUNDS(x, y, w, h)) return NULL; | ||
970 | |||
971 | for (dir = 0; dir < 4; ++dir) | ||
972 | if (dx[dir] == x - ui->x && dy[dir] == y - ui->y) break; | ||
973 | if (dir == 4) return NULL; /* how the ... ?! */ | ||
974 | |||
975 | if (control) flag |= BORDER(dir); | ||
976 | if (shift) flag |= DISABLED(BORDER(dir)); | ||
977 | |||
978 | newflag = state->borders[i] ^ flag; | ||
979 | if (newflag & BORDER(dir) && newflag & DISABLED(BORDER(dir))) | ||
980 | return NULL; | ||
981 | |||
982 | newflag = 0; | ||
983 | if (control) newflag |= BORDER(FLIP(dir)); | ||
984 | if (shift) newflag |= DISABLED(BORDER(FLIP(dir))); | ||
985 | return string(80, "F%d,%d,%dF%d,%d,%d", | ||
986 | ui->x, ui->y, flag, x, y, newflag); | ||
987 | } else { | ||
988 | move_cursor(button, &ui->x, &ui->y, w, h, FALSE); | ||
989 | return ""; | ||
990 | } | ||
991 | } | ||
992 | |||
993 | return NULL; | ||
994 | } | ||
995 | |||
996 | static game_state *execute_move(const game_state *state, const char *move) | ||
997 | { | ||
998 | int w = state->shared->params.w, h = state->shared->params.h, wh = w * h; | ||
999 | game_state *ret = dup_game(state); | ||
1000 | int nchars, x, y, flag; | ||
1001 | |||
1002 | if (*move == 'S') { | ||
1003 | int i; | ||
1004 | ++move; | ||
1005 | for (i = 0; i < wh && move[i]; ++i) | ||
1006 | ret->borders[i] = | ||
1007 | (move[i] & BORDER_MASK) | DISABLED(~move[i] & BORDER_MASK); | ||
1008 | if (i < wh || move[i]) return NULL; /* leaks `ret', then we die */ | ||
1009 | ret->cheated = ret->completed = TRUE; | ||
1010 | return ret; | ||
1011 | } | ||
1012 | |||
1013 | while (sscanf(move, "F%d,%d,%d%n", &x, &y, &flag, &nchars) == 3 && | ||
1014 | !OUT_OF_BOUNDS(x, y, w, h)) { | ||
1015 | move += nchars; | ||
1016 | ret->borders[y*w + x] ^= flag; | ||
1017 | } | ||
1018 | |||
1019 | if (*move) return NULL; /* leaks `ret', then we die */ | ||
1020 | |||
1021 | if (!ret->completed) | ||
1022 | ret->completed = is_solved(&ret->shared->params, ret->shared->clues, | ||
1023 | ret->borders); | ||
1024 | |||
1025 | return ret; | ||
1026 | } | ||
1027 | |||
1028 | /* --- Drawing routines --------------------------------------------- */ | ||
1029 | |||
1030 | static void game_compute_size(const game_params *params, int tilesize, | ||
1031 | int *x, int *y) | ||
1032 | { | ||
1033 | *x = (params->w + 1) * tilesize; | ||
1034 | *y = (params->h + 1) * tilesize; | ||
1035 | } | ||
1036 | |||
1037 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1038 | const game_params *params, int tilesize) | ||
1039 | { | ||
1040 | ds->tilesize = tilesize; | ||
1041 | } | ||
1042 | |||
1043 | enum { | ||
1044 | COL_BACKGROUND, | ||
1045 | COL_FLASH, | ||
1046 | COL_GRID, | ||
1047 | COL_CLUE = COL_GRID, | ||
1048 | COL_LINE_YES = COL_GRID, | ||
1049 | COL_LINE_MAYBE, | ||
1050 | COL_LINE_NO, | ||
1051 | COL_ERROR, | ||
1052 | |||
1053 | NCOLOURS | ||
1054 | }; | ||
1055 | |||
1056 | #define COLOUR(i, r, g, b) \ | ||
1057 | ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b))) | ||
1058 | #define DARKER 0.9F | ||
1059 | |||
1060 | static float *game_colours(frontend *fe, int *ncolours) | ||
1061 | { | ||
1062 | float *ret = snewn(3 * NCOLOURS, float); | ||
1063 | |||
1064 | game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_FLASH); | ||
1065 | |||
1066 | COLOUR(COL_GRID, 0.0F, 0.0F, 0.0F); /* black */ | ||
1067 | COLOUR(COL_ERROR, 1.0F, 0.0F, 0.0F); /* red */ | ||
1068 | |||
1069 | COLOUR(COL_LINE_MAYBE, /* yellow */ | ||
1070 | ret[COL_BACKGROUND*3 + 0] * DARKER, | ||
1071 | ret[COL_BACKGROUND*3 + 1] * DARKER, | ||
1072 | 0.0F); | ||
1073 | |||
1074 | COLOUR(COL_LINE_NO, | ||
1075 | ret[COL_BACKGROUND*3 + 0] * DARKER, | ||
1076 | ret[COL_BACKGROUND*3 + 1] * DARKER, | ||
1077 | ret[COL_BACKGROUND*3 + 2] * DARKER); | ||
1078 | |||
1079 | *ncolours = NCOLOURS; | ||
1080 | return ret; | ||
1081 | } | ||
1082 | #undef COLOUR | ||
1083 | |||
1084 | #define BORDER_ERROR(x) ((x) << 8) | ||
1085 | #define F_ERROR_U BORDER_ERROR(BORDER_U) /* BIT( 8) */ | ||
1086 | #define F_ERROR_R BORDER_ERROR(BORDER_R) /* BIT( 9) */ | ||
1087 | #define F_ERROR_D BORDER_ERROR(BORDER_D) /* BIT(10) */ | ||
1088 | #define F_ERROR_L BORDER_ERROR(BORDER_L) /* BIT(11) */ | ||
1089 | #define F_ERROR_CLUE BIT(12) | ||
1090 | #define F_FLASH BIT(13) | ||
1091 | #define F_CURSOR BIT(14) | ||
1092 | |||
1093 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1094 | { | ||
1095 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1096 | |||
1097 | ds->tilesize = 0; | ||
1098 | ds->grid = NULL; | ||
1099 | |||
1100 | return ds; | ||
1101 | } | ||
1102 | |||
1103 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1104 | { | ||
1105 | sfree(ds->grid); | ||
1106 | sfree(ds); | ||
1107 | } | ||
1108 | |||
1109 | #define COLOUR(border) \ | ||
1110 | (flags & BORDER_ERROR((border)) ? COL_ERROR : \ | ||
1111 | flags & (border) ? COL_LINE_YES : \ | ||
1112 | flags & DISABLED((border)) ? COL_LINE_NO : \ | ||
1113 | COL_LINE_MAYBE) | ||
1114 | |||
1115 | static void draw_tile(drawing *dr, game_drawstate *ds, int r, int c, | ||
1116 | dsflags flags, int clue) | ||
1117 | { | ||
1118 | int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r; | ||
1119 | |||
1120 | clip(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH); /* { */ | ||
1121 | |||
1122 | draw_rect(dr, x + WIDTH, y + WIDTH, TILESIZE - WIDTH, TILESIZE - WIDTH, | ||
1123 | (flags & F_FLASH ? COL_FLASH : COL_BACKGROUND)); | ||
1124 | |||
1125 | if (flags & F_CURSOR) | ||
1126 | draw_rect_corners(dr, x + CENTER, y + CENTER, TILESIZE / 3, COL_GRID); | ||
1127 | |||
1128 | if (clue != EMPTY) { | ||
1129 | char buf[2]; | ||
1130 | buf[0] = '0' + clue; | ||
1131 | buf[1] = '\0'; | ||
1132 | draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE, | ||
1133 | TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE, | ||
1134 | (flags & F_ERROR_CLUE ? COL_ERROR : COL_CLUE), buf); | ||
1135 | } | ||
1136 | |||
1137 | |||
1138 | #define ts TILESIZE | ||
1139 | #define w WIDTH | ||
1140 | draw_rect(dr, x + w, y, ts - w, w, COLOUR(BORDER_U)); | ||
1141 | draw_rect(dr, x + ts, y + w, w, ts - w, COLOUR(BORDER_R)); | ||
1142 | draw_rect(dr, x + w, y + ts, ts - w, w, COLOUR(BORDER_D)); | ||
1143 | draw_rect(dr, x, y + w, w, ts - w, COLOUR(BORDER_L)); | ||
1144 | #undef ts | ||
1145 | #undef w | ||
1146 | |||
1147 | unclip(dr); /* } */ | ||
1148 | draw_update(dr, x, y, TILESIZE + WIDTH, TILESIZE + WIDTH); | ||
1149 | } | ||
1150 | |||
1151 | #define FLASH_TIME 0.7F | ||
1152 | |||
1153 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1154 | const game_state *oldstate, const game_state *state, | ||
1155 | int dir, const game_ui *ui, | ||
1156 | float animtime, float flashtime) | ||
1157 | { | ||
1158 | int w = state->shared->params.w, h = state->shared->params.h, wh = w*h; | ||
1159 | int r, c, i, flash = ((int) (flashtime * 5 / FLASH_TIME)) % 2; | ||
1160 | int *black_border_dsf = snew_dsf(wh), *yellow_border_dsf = snew_dsf(wh); | ||
1161 | int k = state->shared->params.k; | ||
1162 | |||
1163 | if (!ds->grid) { | ||
1164 | char buf[40]; | ||
1165 | int bgw = (w+1) * ds->tilesize, bgh = (h+1) * ds->tilesize; | ||
1166 | draw_rect(dr, 0, 0, bgw, bgh, COL_BACKGROUND); | ||
1167 | |||
1168 | for (r = 0; r <= h; ++r) | ||
1169 | for (c = 0; c <= w; ++c) | ||
1170 | draw_rect(dr, MARGIN + TILESIZE * c, MARGIN + TILESIZE * r, | ||
1171 | WIDTH, WIDTH, COL_GRID); | ||
1172 | draw_update(dr, 0, 0, bgw, bgh); | ||
1173 | |||
1174 | snewa(ds->grid, wh); | ||
1175 | setmem(ds->grid, ~0, wh); | ||
1176 | |||
1177 | sprintf(buf, "Region size: %d", state->shared->params.k); | ||
1178 | status_bar(dr, buf); | ||
1179 | } | ||
1180 | |||
1181 | for (i = 0; i < wh; ++i) { | ||
1182 | if (black_border_dsf[i] == UNVISITED) | ||
1183 | dfs_dsf(i, w, state->borders, black_border_dsf, TRUE); | ||
1184 | if (yellow_border_dsf[i] == UNVISITED) | ||
1185 | dfs_dsf(i, w, state->borders, yellow_border_dsf, FALSE); | ||
1186 | } | ||
1187 | |||
1188 | for (r = 0; r < h; ++r) | ||
1189 | for (c = 0; c < w; ++c) { | ||
1190 | int i = r * w + c, clue = state->shared->clues[i], flags, dir; | ||
1191 | int on = bitcount[state->borders[i] & BORDER_MASK]; | ||
1192 | int off = bitcount[(state->borders[i] >> 4) & BORDER_MASK]; | ||
1193 | |||
1194 | flags = state->borders[i]; | ||
1195 | |||
1196 | if (flash) flags |= F_FLASH; | ||
1197 | |||
1198 | if (clue != EMPTY && (on > clue || clue > 4 - off)) | ||
1199 | flags |= F_ERROR_CLUE; | ||
1200 | |||
1201 | if (ui->show && ui->x == c && ui->y == r) | ||
1202 | flags |= F_CURSOR; | ||
1203 | |||
1204 | /* border errors */ | ||
1205 | for (dir = 0; dir < 4; ++dir) { | ||
1206 | int rr = r + dy[dir], cc = c + dx[dir], ii = rr * w + cc; | ||
1207 | |||
1208 | if (OUT_OF_BOUNDS(cc, rr, w, h)) continue; | ||
1209 | |||
1210 | /* we draw each border twice, except the outermost | ||
1211 | * big border, so we have to check for errors on | ||
1212 | * both sides of each border.*/ | ||
1213 | if (/* region too large */ | ||
1214 | ((dsf_size(yellow_border_dsf, i) > k || | ||
1215 | dsf_size(yellow_border_dsf, ii) > k) && | ||
1216 | (dsf_canonify(yellow_border_dsf, i) != | ||
1217 | dsf_canonify(yellow_border_dsf, ii))) | ||
1218 | |||
1219 | || | ||
1220 | /* region too small */ | ||
1221 | ((dsf_size(black_border_dsf, i) < k || | ||
1222 | dsf_size(black_border_dsf, ii) < k) && | ||
1223 | dsf_canonify(black_border_dsf, i) != | ||
1224 | dsf_canonify(black_border_dsf, ii)) | ||
1225 | |||
1226 | || | ||
1227 | /* dangling borders within a single region */ | ||
1228 | ((state->borders[i] & BORDER(dir)) && | ||
1229 | /* we know it's a single region because there's a | ||
1230 | * path crossing no border from i to ii... */ | ||
1231 | (dsf_canonify(yellow_border_dsf, i) == | ||
1232 | dsf_canonify(yellow_border_dsf, ii) || | ||
1233 | /* or because any such border would be an error */ | ||
1234 | (dsf_size(black_border_dsf, i) <= k && | ||
1235 | dsf_canonify(black_border_dsf, i) == | ||
1236 | dsf_canonify(black_border_dsf, ii))))) | ||
1237 | |||
1238 | flags |= BORDER_ERROR(BORDER(dir)); | ||
1239 | } | ||
1240 | |||
1241 | if (flags == ds->grid[i]) continue; | ||
1242 | ds->grid[i] = flags; | ||
1243 | draw_tile(dr, ds, r, c, ds->grid[i], clue); | ||
1244 | } | ||
1245 | |||
1246 | sfree(black_border_dsf); | ||
1247 | sfree(yellow_border_dsf); | ||
1248 | } | ||
1249 | |||
1250 | static float game_anim_length(const game_state *oldstate, | ||
1251 | const game_state *newstate, | ||
1252 | int dir, game_ui *ui) | ||
1253 | { | ||
1254 | return 0.0F; | ||
1255 | } | ||
1256 | |||
1257 | static float game_flash_length(const game_state *oldstate, | ||
1258 | const game_state *newstate, | ||
1259 | int dir, game_ui *ui) | ||
1260 | { | ||
1261 | if (newstate->completed && !newstate->cheated && !oldstate->completed) | ||
1262 | return FLASH_TIME; | ||
1263 | return 0.0F; | ||
1264 | } | ||
1265 | |||
1266 | static int game_status(const game_state *state) | ||
1267 | { | ||
1268 | return state->completed ? +1 : 0; | ||
1269 | } | ||
1270 | |||
1271 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1272 | { | ||
1273 | assert (!"this shouldn't get called"); | ||
1274 | return 0; /* placate optimiser */ | ||
1275 | } | ||
1276 | |||
1277 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1278 | { | ||
1279 | int pw, ph; | ||
1280 | |||
1281 | game_compute_size(params, 700, &pw, &ph); /* 7mm, like loopy */ | ||
1282 | |||
1283 | *x = pw / 100.0F; | ||
1284 | *y = ph / 100.0F; | ||
1285 | } | ||
1286 | |||
1287 | static void print_line(drawing *dr, int x1, int y1, int x2, int y2, | ||
1288 | int colour, int full) | ||
1289 | { | ||
1290 | if (!full) { | ||
1291 | int i, subdivisions = 8; | ||
1292 | for (i = 1; i < subdivisions; ++i) { | ||
1293 | int x = (x1 * (subdivisions - i) + x2 * i) / subdivisions; | ||
1294 | int y = (y1 * (subdivisions - i) + y2 * i) / subdivisions; | ||
1295 | draw_circle(dr, x, y, 3, colour, colour); | ||
1296 | } | ||
1297 | } else draw_line(dr, x1, y1, x2, y2, colour); | ||
1298 | } | ||
1299 | |||
1300 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1301 | { | ||
1302 | int w = state->shared->params.w, h = state->shared->params.h; | ||
1303 | int ink = print_mono_colour(dr, 0); | ||
1304 | game_drawstate for_tilesize_macros, *ds = &for_tilesize_macros; | ||
1305 | int r, c; | ||
1306 | |||
1307 | ds->tilesize = tilesize; | ||
1308 | |||
1309 | for (r = 0; r < h; ++r) | ||
1310 | for (c = 0; c < w; ++c) { | ||
1311 | int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r; | ||
1312 | int i = r * w + c, clue = state->shared->clues[i]; | ||
1313 | |||
1314 | if (clue != EMPTY) { | ||
1315 | char buf[2]; | ||
1316 | buf[0] = '0' + clue; | ||
1317 | buf[1] = '\0'; | ||
1318 | draw_text(dr, x + CENTER, y + CENTER, FONT_VARIABLE, | ||
1319 | TILESIZE / 2, ALIGN_VCENTRE | ALIGN_HCENTRE, | ||
1320 | ink, buf); | ||
1321 | } | ||
1322 | |||
1323 | #define ts TILESIZE | ||
1324 | #define FULL(DIR) (state->borders[i] & (BORDER_ ## DIR)) | ||
1325 | print_line(dr, x, y, x + ts, y, ink, FULL(U)); | ||
1326 | print_line(dr, x + ts, y, x + ts, y + ts, ink, FULL(R)); | ||
1327 | print_line(dr, x, y + ts, x + ts, y + ts, ink, FULL(D)); | ||
1328 | print_line(dr, x, y, x, y + ts, ink, FULL(L)); | ||
1329 | #undef ts | ||
1330 | #undef FULL | ||
1331 | } | ||
1332 | |||
1333 | for (r = 1; r < h; ++r) | ||
1334 | for (c = 1; c < w; ++c) { | ||
1335 | int j = r * w + c, i = j - 1 - w; | ||
1336 | int x = MARGIN + TILESIZE * c, y = MARGIN + TILESIZE * r; | ||
1337 | if (state->borders[i] & (BORDER_D|BORDER_R)) continue; | ||
1338 | if (state->borders[j] & (BORDER_U|BORDER_L)) continue; | ||
1339 | draw_circle(dr, x, y, 3, ink, ink); | ||
1340 | } | ||
1341 | } | ||
1342 | |||
1343 | #ifdef COMBINED | ||
1344 | #define thegame palisade | ||
1345 | #endif | ||
1346 | |||
1347 | const struct game thegame = { | ||
1348 | "Palisade", "games.palisade", "palisade", | ||
1349 | default_params, | ||
1350 | game_fetch_preset, | ||
1351 | decode_params, | ||
1352 | encode_params, | ||
1353 | free_params, | ||
1354 | dup_params, | ||
1355 | TRUE, game_configure, custom_params, | ||
1356 | validate_params, | ||
1357 | new_game_desc, | ||
1358 | validate_desc, | ||
1359 | new_game, | ||
1360 | dup_game, | ||
1361 | free_game, | ||
1362 | TRUE, solve_game, | ||
1363 | TRUE, game_can_format_as_text_now, game_text_format, | ||
1364 | new_ui, | ||
1365 | free_ui, | ||
1366 | encode_ui, | ||
1367 | decode_ui, | ||
1368 | game_changed_state, | ||
1369 | interpret_move, | ||
1370 | execute_move, | ||
1371 | 48, game_compute_size, game_set_size, | ||
1372 | game_colours, | ||
1373 | game_new_drawstate, | ||
1374 | game_free_drawstate, | ||
1375 | game_redraw, | ||
1376 | game_anim_length, | ||
1377 | game_flash_length, | ||
1378 | game_status, | ||
1379 | TRUE, FALSE, game_print_size, game_print, | ||
1380 | TRUE, /* wants_statusbar */ | ||
1381 | FALSE, game_timing_state, | ||
1382 | 0, /* flags */ | ||
1383 | }; | ||