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