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/unfinished/slide.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/unfinished/slide.c')
-rw-r--r-- | apps/plugins/puzzles/unfinished/slide.c | 2445 |
1 files changed, 2445 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/unfinished/slide.c b/apps/plugins/puzzles/unfinished/slide.c new file mode 100644 index 0000000000..b1aa04bc90 --- /dev/null +++ b/apps/plugins/puzzles/unfinished/slide.c | |||
@@ -0,0 +1,2445 @@ | |||
1 | /* | ||
2 | * slide.c: Implementation of the block-sliding puzzle `Klotski'. | ||
3 | */ | ||
4 | |||
5 | /* | ||
6 | * TODO: | ||
7 | * | ||
8 | * - Improve the generator. | ||
9 | * * actually, we seem to be mostly sensible already now. I | ||
10 | * want more choice over the type of main block and location | ||
11 | * of the exit/target, and I think I probably ought to give | ||
12 | * up on compactness and just bite the bullet and have the | ||
13 | * target area right outside the main wall, but mostly I | ||
14 | * think it's OK. | ||
15 | * * the move limit tends to make the game _slower_ to | ||
16 | * generate, which is odd. Perhaps investigate why. | ||
17 | * | ||
18 | * - Improve the graphics. | ||
19 | * * All the colours are a bit wishy-washy. _Some_ dark | ||
20 | * colours would surely not be excessive? Probably darken | ||
21 | * the tiles, the walls and the main block, and leave the | ||
22 | * target marker pale. | ||
23 | * * The cattle grid effect is still disgusting. Think of | ||
24 | * something completely different. | ||
25 | * * The highlight for next-piece-to-move in the solver is | ||
26 | * excessive, and the shadow blends in too well with the | ||
27 | * piece lowlights. Adjust both. | ||
28 | */ | ||
29 | |||
30 | #include <stdio.h> | ||
31 | #include <stdlib.h> | ||
32 | #include <string.h> | ||
33 | #include <assert.h> | ||
34 | #include <ctype.h> | ||
35 | #include <math.h> | ||
36 | |||
37 | #include "puzzles.h" | ||
38 | #include "tree234.h" | ||
39 | |||
40 | /* | ||
41 | * The implementation of this game revolves around the insight | ||
42 | * which makes an exhaustive-search solver feasible: although | ||
43 | * there are many blocks which can be rearranged in many ways, any | ||
44 | * two blocks of the same shape are _indistinguishable_ and hence | ||
45 | * the number of _distinct_ board layouts is generally much | ||
46 | * smaller. So we adopt a representation for board layouts which | ||
47 | * is inherently canonical, i.e. there are no two distinct | ||
48 | * representations which encode indistinguishable layouts. | ||
49 | * | ||
50 | * The way we do this is to encode each square of the board, in | ||
51 | * the normal left-to-right top-to-bottom order, as being one of | ||
52 | * the following things: | ||
53 | * - the first square (in the given order) of a block (`anchor') | ||
54 | * - special case of the above: the anchor for the _main_ block | ||
55 | * (i.e. the one which the aim of the game is to get to the | ||
56 | * target position) | ||
57 | * - a subsequent square of a block whose previous square was N | ||
58 | * squares ago | ||
59 | * - an impassable wall | ||
60 | * | ||
61 | * (We also separately store data about which board positions are | ||
62 | * forcefields only passable by the main block. We can't encode | ||
63 | * that in the main board data, because then the main block would | ||
64 | * destroy forcefields as it went over them.) | ||
65 | * | ||
66 | * Hence, for example, a 2x2 square block would be encoded as | ||
67 | * ANCHOR, followed by DIST(1), and w-2 squares later on there | ||
68 | * would be DIST(w-1) followed by DIST(1). So if you start at the | ||
69 | * last of those squares, the DIST numbers give you a linked list | ||
70 | * pointing back through all the other squares in the same block. | ||
71 | * | ||
72 | * So the solver simply does a bfs over all reachable positions, | ||
73 | * encoding them in this format and storing them in a tree234 to | ||
74 | * ensure it doesn't ever revisit an already-analysed position. | ||
75 | */ | ||
76 | |||
77 | enum { | ||
78 | /* | ||
79 | * The colours are arranged here so that every base colour is | ||
80 | * directly followed by its highlight colour and then its | ||
81 | * lowlight colour. Do not break this, or draw_tile() will get | ||
82 | * confused. | ||
83 | */ | ||
84 | COL_BACKGROUND, | ||
85 | COL_HIGHLIGHT, | ||
86 | COL_LOWLIGHT, | ||
87 | COL_DRAGGING, | ||
88 | COL_DRAGGING_HIGHLIGHT, | ||
89 | COL_DRAGGING_LOWLIGHT, | ||
90 | COL_MAIN, | ||
91 | COL_MAIN_HIGHLIGHT, | ||
92 | COL_MAIN_LOWLIGHT, | ||
93 | COL_MAIN_DRAGGING, | ||
94 | COL_MAIN_DRAGGING_HIGHLIGHT, | ||
95 | COL_MAIN_DRAGGING_LOWLIGHT, | ||
96 | COL_TARGET, | ||
97 | COL_TARGET_HIGHLIGHT, | ||
98 | COL_TARGET_LOWLIGHT, | ||
99 | NCOLOURS | ||
100 | }; | ||
101 | |||
102 | /* | ||
103 | * Board layout is a simple array of bytes. Each byte holds: | ||
104 | */ | ||
105 | #define ANCHOR 255 /* top-left-most square of some piece */ | ||
106 | #define MAINANCHOR 254 /* anchor of _main_ piece */ | ||
107 | #define EMPTY 253 /* empty square */ | ||
108 | #define WALL 252 /* immovable wall */ | ||
109 | #define MAXDIST 251 | ||
110 | /* all other values indicate distance back to previous square of same block */ | ||
111 | #define ISDIST(x) ( (unsigned char)((x)-1) <= MAXDIST-1 ) | ||
112 | #define DIST(x) (x) | ||
113 | #define ISANCHOR(x) ( (x)==ANCHOR || (x)==MAINANCHOR ) | ||
114 | #define ISBLOCK(x) ( ISANCHOR(x) || ISDIST(x) ) | ||
115 | |||
116 | /* | ||
117 | * MAXDIST is the largest DIST value we can encode. This must | ||
118 | * therefore also be the maximum puzzle width in theory (although | ||
119 | * solver running time will dictate a much smaller limit in | ||
120 | * practice). | ||
121 | */ | ||
122 | #define MAXWID MAXDIST | ||
123 | |||
124 | struct game_params { | ||
125 | int w, h; | ||
126 | int maxmoves; | ||
127 | }; | ||
128 | |||
129 | struct game_immutable_state { | ||
130 | int refcount; | ||
131 | unsigned char *forcefield; | ||
132 | }; | ||
133 | |||
134 | struct game_solution { | ||
135 | int nmoves; | ||
136 | int *moves; /* just like from solve_board() */ | ||
137 | int refcount; | ||
138 | }; | ||
139 | |||
140 | struct game_state { | ||
141 | int w, h; | ||
142 | unsigned char *board; | ||
143 | int tx, ty; /* target coords for MAINANCHOR */ | ||
144 | int minmoves; /* for display only */ | ||
145 | int lastmoved, lastmoved_pos; /* for move counting */ | ||
146 | int movecount; | ||
147 | int completed; | ||
148 | int cheated; | ||
149 | struct game_immutable_state *imm; | ||
150 | struct game_solution *soln; | ||
151 | int soln_index; | ||
152 | }; | ||
153 | |||
154 | static game_params *default_params(void) | ||
155 | { | ||
156 | game_params *ret = snew(game_params); | ||
157 | |||
158 | ret->w = 7; | ||
159 | ret->h = 6; | ||
160 | ret->maxmoves = 40; | ||
161 | |||
162 | return ret; | ||
163 | } | ||
164 | |||
165 | static const struct game_params slide_presets[] = { | ||
166 | {7, 6, 25}, | ||
167 | {7, 6, -1}, | ||
168 | {8, 6, -1}, | ||
169 | }; | ||
170 | |||
171 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
172 | { | ||
173 | game_params *ret; | ||
174 | char str[80]; | ||
175 | |||
176 | if (i < 0 || i >= lenof(slide_presets)) | ||
177 | return FALSE; | ||
178 | |||
179 | ret = snew(game_params); | ||
180 | *ret = slide_presets[i]; | ||
181 | |||
182 | sprintf(str, "%dx%d", ret->w, ret->h); | ||
183 | if (ret->maxmoves >= 0) | ||
184 | sprintf(str + strlen(str), ", max %d moves", ret->maxmoves); | ||
185 | else | ||
186 | sprintf(str + strlen(str), ", no move limit"); | ||
187 | |||
188 | *name = dupstr(str); | ||
189 | *params = ret; | ||
190 | return TRUE; | ||
191 | } | ||
192 | |||
193 | static void free_params(game_params *params) | ||
194 | { | ||
195 | sfree(params); | ||
196 | } | ||
197 | |||
198 | static game_params *dup_params(const game_params *params) | ||
199 | { | ||
200 | game_params *ret = snew(game_params); | ||
201 | *ret = *params; /* structure copy */ | ||
202 | return ret; | ||
203 | } | ||
204 | |||
205 | static void decode_params(game_params *params, char const *string) | ||
206 | { | ||
207 | params->w = params->h = atoi(string); | ||
208 | while (*string && isdigit((unsigned char)*string)) string++; | ||
209 | if (*string == 'x') { | ||
210 | string++; | ||
211 | params->h = atoi(string); | ||
212 | while (*string && isdigit((unsigned char)*string)) string++; | ||
213 | } | ||
214 | if (*string == 'm') { | ||
215 | string++; | ||
216 | params->maxmoves = atoi(string); | ||
217 | while (*string && isdigit((unsigned char)*string)) string++; | ||
218 | } else if (*string == 'u') { | ||
219 | string++; | ||
220 | params->maxmoves = -1; | ||
221 | } | ||
222 | } | ||
223 | |||
224 | static char *encode_params(const game_params *params, int full) | ||
225 | { | ||
226 | char data[256]; | ||
227 | |||
228 | sprintf(data, "%dx%d", params->w, params->h); | ||
229 | if (params->maxmoves >= 0) | ||
230 | sprintf(data + strlen(data), "m%d", params->maxmoves); | ||
231 | else | ||
232 | sprintf(data + strlen(data), "u"); | ||
233 | |||
234 | return dupstr(data); | ||
235 | } | ||
236 | |||
237 | static config_item *game_configure(const game_params *params) | ||
238 | { | ||
239 | config_item *ret; | ||
240 | char buf[80]; | ||
241 | |||
242 | ret = snewn(4, config_item); | ||
243 | |||
244 | ret[0].name = "Width"; | ||
245 | ret[0].type = C_STRING; | ||
246 | sprintf(buf, "%d", params->w); | ||
247 | ret[0].sval = dupstr(buf); | ||
248 | ret[0].ival = 0; | ||
249 | |||
250 | ret[1].name = "Height"; | ||
251 | ret[1].type = C_STRING; | ||
252 | sprintf(buf, "%d", params->h); | ||
253 | ret[1].sval = dupstr(buf); | ||
254 | ret[1].ival = 0; | ||
255 | |||
256 | ret[2].name = "Solution length limit"; | ||
257 | ret[2].type = C_STRING; | ||
258 | sprintf(buf, "%d", params->maxmoves); | ||
259 | ret[2].sval = dupstr(buf); | ||
260 | ret[2].ival = 0; | ||
261 | |||
262 | ret[3].name = NULL; | ||
263 | ret[3].type = C_END; | ||
264 | ret[3].sval = NULL; | ||
265 | ret[3].ival = 0; | ||
266 | |||
267 | return ret; | ||
268 | } | ||
269 | |||
270 | static game_params *custom_params(const config_item *cfg) | ||
271 | { | ||
272 | game_params *ret = snew(game_params); | ||
273 | |||
274 | ret->w = atoi(cfg[0].sval); | ||
275 | ret->h = atoi(cfg[1].sval); | ||
276 | ret->maxmoves = atoi(cfg[2].sval); | ||
277 | |||
278 | return ret; | ||
279 | } | ||
280 | |||
281 | static char *validate_params(const game_params *params, int full) | ||
282 | { | ||
283 | if (params->w > MAXWID) | ||
284 | return "Width must be at most " STR(MAXWID); | ||
285 | |||
286 | if (params->w < 5) | ||
287 | return "Width must be at least 5"; | ||
288 | if (params->h < 4) | ||
289 | return "Height must be at least 4"; | ||
290 | |||
291 | return NULL; | ||
292 | } | ||
293 | |||
294 | static char *board_text_format(int w, int h, unsigned char *data, | ||
295 | unsigned char *forcefield) | ||
296 | { | ||
297 | int wh = w*h; | ||
298 | int *dsf = snew_dsf(wh); | ||
299 | int i, x, y; | ||
300 | int retpos, retlen = (w*2+2)*(h*2+1)+1; | ||
301 | char *ret = snewn(retlen, char); | ||
302 | |||
303 | for (i = 0; i < wh; i++) | ||
304 | if (ISDIST(data[i])) | ||
305 | dsf_merge(dsf, i - data[i], i); | ||
306 | retpos = 0; | ||
307 | for (y = 0; y < 2*h+1; y++) { | ||
308 | for (x = 0; x < 2*w+1; x++) { | ||
309 | int v; | ||
310 | int i = (y/2)*w+(x/2); | ||
311 | |||
312 | #define dtype(i) (ISBLOCK(data[i]) ? \ | ||
313 | dsf_canonify(dsf, i) : data[i]) | ||
314 | #define dchar(t) ((t)==EMPTY ? ' ' : (t)==WALL ? '#' : \ | ||
315 | data[t] == MAINANCHOR ? '*' : '%') | ||
316 | |||
317 | if (y % 2 && x % 2) { | ||
318 | int j = dtype(i); | ||
319 | v = dchar(j); | ||
320 | } else if (y % 2 && !(x % 2)) { | ||
321 | int j1 = (x > 0 ? dtype(i-1) : -1); | ||
322 | int j2 = (x < 2*w ? dtype(i) : -1); | ||
323 | if (j1 != j2) | ||
324 | v = '|'; | ||
325 | else | ||
326 | v = dchar(j1); | ||
327 | } else if (!(y % 2) && (x % 2)) { | ||
328 | int j1 = (y > 0 ? dtype(i-w) : -1); | ||
329 | int j2 = (y < 2*h ? dtype(i) : -1); | ||
330 | if (j1 != j2) | ||
331 | v = '-'; | ||
332 | else | ||
333 | v = dchar(j1); | ||
334 | } else { | ||
335 | int j1 = (x > 0 && y > 0 ? dtype(i-w-1) : -1); | ||
336 | int j2 = (x > 0 && y < 2*h ? dtype(i-1) : -1); | ||
337 | int j3 = (x < 2*w && y > 0 ? dtype(i-w) : -1); | ||
338 | int j4 = (x < 2*w && y < 2*h ? dtype(i) : -1); | ||
339 | if (j1 == j2 && j2 == j3 && j3 == j4) | ||
340 | v = dchar(j1); | ||
341 | else if (j1 == j2 && j3 == j4) | ||
342 | v = '|'; | ||
343 | else if (j1 == j3 && j2 == j4) | ||
344 | v = '-'; | ||
345 | else | ||
346 | v = '+'; | ||
347 | } | ||
348 | |||
349 | assert(retpos < retlen); | ||
350 | ret[retpos++] = v; | ||
351 | } | ||
352 | assert(retpos < retlen); | ||
353 | ret[retpos++] = '\n'; | ||
354 | } | ||
355 | assert(retpos < retlen); | ||
356 | ret[retpos++] = '\0'; | ||
357 | assert(retpos == retlen); | ||
358 | |||
359 | return ret; | ||
360 | } | ||
361 | |||
362 | /* ---------------------------------------------------------------------- | ||
363 | * Solver. | ||
364 | */ | ||
365 | |||
366 | /* | ||
367 | * During solver execution, the set of visited board positions is | ||
368 | * stored as a tree234 of the following structures. `w', `h' and | ||
369 | * `data' are obvious in meaning; `dist' represents the minimum | ||
370 | * distance to reach this position from the starting point. | ||
371 | * | ||
372 | * `prev' links each board to the board position from which it was | ||
373 | * most efficiently derived. | ||
374 | */ | ||
375 | struct board { | ||
376 | int w, h; | ||
377 | int dist; | ||
378 | struct board *prev; | ||
379 | unsigned char *data; | ||
380 | }; | ||
381 | |||
382 | static int boardcmp(void *av, void *bv) | ||
383 | { | ||
384 | struct board *a = (struct board *)av; | ||
385 | struct board *b = (struct board *)bv; | ||
386 | return memcmp(a->data, b->data, a->w * a->h); | ||
387 | } | ||
388 | |||
389 | static struct board *newboard(int w, int h, unsigned char *data) | ||
390 | { | ||
391 | struct board *b = malloc(sizeof(struct board) + w*h); | ||
392 | b->data = (unsigned char *)b + sizeof(struct board); | ||
393 | memcpy(b->data, data, w*h); | ||
394 | b->w = w; | ||
395 | b->h = h; | ||
396 | b->dist = -1; | ||
397 | b->prev = NULL; | ||
398 | return b; | ||
399 | } | ||
400 | |||
401 | /* | ||
402 | * The actual solver. Given a board, attempt to find the minimum | ||
403 | * length of move sequence which moves MAINANCHOR to (tx,ty), or | ||
404 | * -1 if no solution exists. Returns that minimum length. | ||
405 | * | ||
406 | * Also, if `moveout' is provided, writes out the moves in the | ||
407 | * form of a sequence of pairs of integers indicating the source | ||
408 | * and destination points of the anchor of the moved piece in each | ||
409 | * move. Exactly twice as many integers are written as the number | ||
410 | * returned from solve_board(), and `moveout' receives an int * | ||
411 | * which is a pointer to a dynamically allocated array. | ||
412 | */ | ||
413 | static int solve_board(int w, int h, unsigned char *board, | ||
414 | unsigned char *forcefield, int tx, int ty, | ||
415 | int movelimit, int **moveout) | ||
416 | { | ||
417 | int wh = w*h; | ||
418 | struct board *b, *b2, *b3; | ||
419 | int *next, *anchors, *which; | ||
420 | int *movereached, *movequeue, mqhead, mqtail; | ||
421 | tree234 *sorted, *queue; | ||
422 | int i, j, dir; | ||
423 | int qlen, lastdist; | ||
424 | int ret; | ||
425 | |||
426 | #ifdef SOLVER_DIAGNOSTICS | ||
427 | { | ||
428 | char *t = board_text_format(w, h, board); | ||
429 | for (i = 0; i < h; i++) { | ||
430 | for (j = 0; j < w; j++) { | ||
431 | int c = board[i*w+j]; | ||
432 | if (ISDIST(c)) | ||
433 | printf("D%-3d", c); | ||
434 | else if (c == MAINANCHOR) | ||
435 | printf("M "); | ||
436 | else if (c == ANCHOR) | ||
437 | printf("A "); | ||
438 | else if (c == WALL) | ||
439 | printf("W "); | ||
440 | else if (c == EMPTY) | ||
441 | printf("E "); | ||
442 | } | ||
443 | printf("\n"); | ||
444 | } | ||
445 | |||
446 | printf("Starting solver for:\n%s\n", t); | ||
447 | sfree(t); | ||
448 | } | ||
449 | #endif | ||
450 | |||
451 | sorted = newtree234(boardcmp); | ||
452 | queue = newtree234(NULL); | ||
453 | |||
454 | b = newboard(w, h, board); | ||
455 | b->dist = 0; | ||
456 | add234(sorted, b); | ||
457 | addpos234(queue, b, 0); | ||
458 | qlen = 1; | ||
459 | |||
460 | next = snewn(wh, int); | ||
461 | anchors = snewn(wh, int); | ||
462 | which = snewn(wh, int); | ||
463 | movereached = snewn(wh, int); | ||
464 | movequeue = snewn(wh, int); | ||
465 | lastdist = -1; | ||
466 | |||
467 | while ((b = delpos234(queue, 0)) != NULL) { | ||
468 | qlen--; | ||
469 | if (movelimit >= 0 && b->dist >= movelimit) { | ||
470 | /* | ||
471 | * The problem is not soluble in under `movelimit' | ||
472 | * moves, so we can quit right now. | ||
473 | */ | ||
474 | b2 = NULL; | ||
475 | goto done; | ||
476 | } | ||
477 | if (b->dist != lastdist) { | ||
478 | #ifdef SOLVER_DIAGNOSTICS | ||
479 | printf("dist %d (%d)\n", b->dist, count234(sorted)); | ||
480 | #endif | ||
481 | lastdist = b->dist; | ||
482 | } | ||
483 | /* | ||
484 | * Find all the anchors and form a linked list of the | ||
485 | * squares within each block. | ||
486 | */ | ||
487 | for (i = 0; i < wh; i++) { | ||
488 | next[i] = -1; | ||
489 | anchors[i] = FALSE; | ||
490 | which[i] = -1; | ||
491 | if (ISANCHOR(b->data[i])) { | ||
492 | anchors[i] = TRUE; | ||
493 | which[i] = i; | ||
494 | } else if (ISDIST(b->data[i])) { | ||
495 | j = i - b->data[i]; | ||
496 | next[j] = i; | ||
497 | which[i] = which[j]; | ||
498 | } | ||
499 | } | ||
500 | |||
501 | /* | ||
502 | * For each anchor, do an array-based BFS to find all the | ||
503 | * places we can slide it to. | ||
504 | */ | ||
505 | for (i = 0; i < wh; i++) { | ||
506 | if (!anchors[i]) | ||
507 | continue; | ||
508 | |||
509 | mqhead = mqtail = 0; | ||
510 | for (j = 0; j < wh; j++) | ||
511 | movereached[j] = FALSE; | ||
512 | movequeue[mqtail++] = i; | ||
513 | while (mqhead < mqtail) { | ||
514 | int pos = movequeue[mqhead++]; | ||
515 | |||
516 | /* | ||
517 | * Try to move in each direction from here. | ||
518 | */ | ||
519 | for (dir = 0; dir < 4; dir++) { | ||
520 | int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0); | ||
521 | int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0); | ||
522 | int offset = dy*w + dx; | ||
523 | int newpos = pos + offset; | ||
524 | int d = newpos - i; | ||
525 | |||
526 | /* | ||
527 | * For each square involved in this block, | ||
528 | * check to see if the square d spaces away | ||
529 | * from it is either empty or part of the same | ||
530 | * block. | ||
531 | */ | ||
532 | for (j = i; j >= 0; j = next[j]) { | ||
533 | int jy = (pos+j-i) / w + dy, jx = (pos+j-i) % w + dx; | ||
534 | if (jy >= 0 && jy < h && jx >= 0 && jx < w && | ||
535 | ((b->data[j+d] == EMPTY || which[j+d] == i) && | ||
536 | (b->data[i] == MAINANCHOR || !forcefield[j+d]))) | ||
537 | /* ok */; | ||
538 | else | ||
539 | break; | ||
540 | } | ||
541 | if (j >= 0) | ||
542 | continue; /* this direction wasn't feasible */ | ||
543 | |||
544 | /* | ||
545 | * If we've already tried moving this piece | ||
546 | * here, leave it. | ||
547 | */ | ||
548 | if (movereached[newpos]) | ||
549 | continue; | ||
550 | movereached[newpos] = TRUE; | ||
551 | movequeue[mqtail++] = newpos; | ||
552 | |||
553 | /* | ||
554 | * We have a viable move. Make it. | ||
555 | */ | ||
556 | b2 = newboard(w, h, b->data); | ||
557 | for (j = i; j >= 0; j = next[j]) | ||
558 | b2->data[j] = EMPTY; | ||
559 | for (j = i; j >= 0; j = next[j]) | ||
560 | b2->data[j+d] = b->data[j]; | ||
561 | |||
562 | b3 = add234(sorted, b2); | ||
563 | if (b3 != b2) { | ||
564 | sfree(b2); /* we already got one */ | ||
565 | } else { | ||
566 | b2->dist = b->dist + 1; | ||
567 | b2->prev = b; | ||
568 | addpos234(queue, b2, qlen++); | ||
569 | if (b2->data[ty*w+tx] == MAINANCHOR) | ||
570 | goto done; /* search completed! */ | ||
571 | } | ||
572 | } | ||
573 | } | ||
574 | } | ||
575 | } | ||
576 | b2 = NULL; | ||
577 | |||
578 | done: | ||
579 | |||
580 | if (b2) { | ||
581 | ret = b2->dist; | ||
582 | if (moveout) { | ||
583 | /* | ||
584 | * Now b2 represents the solved position. Backtrack to | ||
585 | * output the solution. | ||
586 | */ | ||
587 | *moveout = snewn(ret * 2, int); | ||
588 | j = ret * 2; | ||
589 | |||
590 | while (b2->prev) { | ||
591 | int from = -1, to = -1; | ||
592 | |||
593 | b = b2->prev; | ||
594 | |||
595 | /* | ||
596 | * Scan b and b2 to find out which piece has | ||
597 | * moved. | ||
598 | */ | ||
599 | for (i = 0; i < wh; i++) { | ||
600 | if (ISANCHOR(b->data[i]) && !ISANCHOR(b2->data[i])) { | ||
601 | assert(from == -1); | ||
602 | from = i; | ||
603 | } else if (!ISANCHOR(b->data[i]) && ISANCHOR(b2->data[i])){ | ||
604 | assert(to == -1); | ||
605 | to = i; | ||
606 | } | ||
607 | } | ||
608 | |||
609 | assert(from >= 0 && to >= 0); | ||
610 | assert(j >= 2); | ||
611 | (*moveout)[--j] = to; | ||
612 | (*moveout)[--j] = from; | ||
613 | |||
614 | b2 = b; | ||
615 | } | ||
616 | assert(j == 0); | ||
617 | } | ||
618 | } else { | ||
619 | ret = -1; /* no solution */ | ||
620 | if (moveout) | ||
621 | *moveout = NULL; | ||
622 | } | ||
623 | |||
624 | freetree234(queue); | ||
625 | |||
626 | while ((b = delpos234(sorted, 0)) != NULL) | ||
627 | sfree(b); | ||
628 | freetree234(sorted); | ||
629 | |||
630 | sfree(next); | ||
631 | sfree(anchors); | ||
632 | sfree(movereached); | ||
633 | sfree(movequeue); | ||
634 | sfree(which); | ||
635 | |||
636 | return ret; | ||
637 | } | ||
638 | |||
639 | /* ---------------------------------------------------------------------- | ||
640 | * Random board generation. | ||
641 | */ | ||
642 | |||
643 | static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves, | ||
644 | random_state *rs, unsigned char **rboard, | ||
645 | unsigned char **rforcefield, int movelimit) | ||
646 | { | ||
647 | int wh = w*h; | ||
648 | unsigned char *board, *board2, *forcefield; | ||
649 | unsigned char *tried_merge; | ||
650 | int *dsf; | ||
651 | int *list, nlist, pos; | ||
652 | int tx, ty; | ||
653 | int i, j; | ||
654 | int moves = 0; /* placate optimiser */ | ||
655 | |||
656 | /* | ||
657 | * Set up a board and fill it with singletons, except for a | ||
658 | * border of walls. | ||
659 | */ | ||
660 | board = snewn(wh, unsigned char); | ||
661 | forcefield = snewn(wh, unsigned char); | ||
662 | board2 = snewn(wh, unsigned char); | ||
663 | memset(board, ANCHOR, wh); | ||
664 | memset(forcefield, FALSE, wh); | ||
665 | for (i = 0; i < w; i++) | ||
666 | board[i] = board[i+w*(h-1)] = WALL; | ||
667 | for (i = 0; i < h; i++) | ||
668 | board[i*w] = board[i*w+(w-1)] = WALL; | ||
669 | |||
670 | tried_merge = snewn(wh * wh, unsigned char); | ||
671 | memset(tried_merge, 0, wh*wh); | ||
672 | dsf = snew_dsf(wh); | ||
673 | |||
674 | /* | ||
675 | * Invent a main piece at one extreme. (FIXME: vary the | ||
676 | * extreme, and the piece.) | ||
677 | */ | ||
678 | board[w+1] = MAINANCHOR; | ||
679 | board[w+2] = DIST(1); | ||
680 | board[w*2+1] = DIST(w-1); | ||
681 | board[w*2+2] = DIST(1); | ||
682 | |||
683 | /* | ||
684 | * Invent a target position. (FIXME: vary this too.) | ||
685 | */ | ||
686 | tx = w-2; | ||
687 | ty = h-3; | ||
688 | forcefield[ty*w+tx+1] = forcefield[(ty+1)*w+tx+1] = TRUE; | ||
689 | board[ty*w+tx+1] = board[(ty+1)*w+tx+1] = EMPTY; | ||
690 | |||
691 | /* | ||
692 | * Gradually remove singletons until the game becomes soluble. | ||
693 | */ | ||
694 | for (j = w; j-- > 0 ;) | ||
695 | for (i = h; i-- > 0 ;) | ||
696 | if (board[i*w+j] == ANCHOR) { | ||
697 | /* | ||
698 | * See if the board is already soluble. | ||
699 | */ | ||
700 | if ((moves = solve_board(w, h, board, forcefield, | ||
701 | tx, ty, movelimit, NULL)) >= 0) | ||
702 | goto soluble; | ||
703 | |||
704 | /* | ||
705 | * Otherwise, remove this piece. | ||
706 | */ | ||
707 | board[i*w+j] = EMPTY; | ||
708 | } | ||
709 | assert(!"We shouldn't get here"); | ||
710 | soluble: | ||
711 | |||
712 | /* | ||
713 | * Make a list of all the inter-block edges on the board. | ||
714 | */ | ||
715 | list = snewn(wh*2, int); | ||
716 | nlist = 0; | ||
717 | for (i = 0; i+1 < w; i++) | ||
718 | for (j = 0; j < h; j++) | ||
719 | list[nlist++] = (j*w+i) * 2 + 0; /* edge to the right of j*w+i */ | ||
720 | for (j = 0; j+1 < h; j++) | ||
721 | for (i = 0; i < w; i++) | ||
722 | list[nlist++] = (j*w+i) * 2 + 1; /* edge below j*w+i */ | ||
723 | |||
724 | /* | ||
725 | * Now go through that list in random order, trying to merge | ||
726 | * the blocks on each side of each edge. | ||
727 | */ | ||
728 | shuffle(list, nlist, sizeof(*list), rs); | ||
729 | while (nlist > 0) { | ||
730 | int x1, y1, p1, c1; | ||
731 | int x2, y2, p2, c2; | ||
732 | |||
733 | pos = list[--nlist]; | ||
734 | y1 = y2 = pos / (w*2); | ||
735 | x1 = x2 = (pos / 2) % w; | ||
736 | if (pos % 2) | ||
737 | y2++; | ||
738 | else | ||
739 | x2++; | ||
740 | p1 = y1*w+x1; | ||
741 | p2 = y2*w+x2; | ||
742 | |||
743 | /* | ||
744 | * Immediately abandon the attempt if we've already tried | ||
745 | * to merge the same pair of blocks along a different | ||
746 | * edge. | ||
747 | */ | ||
748 | c1 = dsf_canonify(dsf, p1); | ||
749 | c2 = dsf_canonify(dsf, p2); | ||
750 | if (tried_merge[c1 * wh + c2]) | ||
751 | continue; | ||
752 | |||
753 | /* | ||
754 | * In order to be mergeable, these two squares must each | ||
755 | * either be, or belong to, a non-main anchor, and their | ||
756 | * anchors must also be distinct. | ||
757 | */ | ||
758 | if (!ISBLOCK(board[p1]) || !ISBLOCK(board[p2])) | ||
759 | continue; | ||
760 | while (ISDIST(board[p1])) | ||
761 | p1 -= board[p1]; | ||
762 | while (ISDIST(board[p2])) | ||
763 | p2 -= board[p2]; | ||
764 | if (board[p1] == MAINANCHOR || board[p2] == MAINANCHOR || p1 == p2) | ||
765 | continue; | ||
766 | |||
767 | /* | ||
768 | * We can merge these blocks. Try it, and see if the | ||
769 | * puzzle remains soluble. | ||
770 | */ | ||
771 | memcpy(board2, board, wh); | ||
772 | j = -1; | ||
773 | while (p1 < wh || p2 < wh) { | ||
774 | /* | ||
775 | * p1 and p2 are the squares at the head of each block | ||
776 | * list. Pick the smaller one and put it on the output | ||
777 | * block list. | ||
778 | */ | ||
779 | i = min(p1, p2); | ||
780 | if (j < 0) { | ||
781 | board[i] = ANCHOR; | ||
782 | } else { | ||
783 | assert(i - j <= MAXDIST); | ||
784 | board[i] = DIST(i - j); | ||
785 | } | ||
786 | j = i; | ||
787 | |||
788 | /* | ||
789 | * Now advance whichever list that came from. | ||
790 | */ | ||
791 | if (i == p1) { | ||
792 | do { | ||
793 | p1++; | ||
794 | } while (p1 < wh && board[p1] != DIST(p1-i)); | ||
795 | } else { | ||
796 | do { | ||
797 | p2++; | ||
798 | } while (p2 < wh && board[p2] != DIST(p2-i)); | ||
799 | } | ||
800 | } | ||
801 | j = solve_board(w, h, board, forcefield, tx, ty, movelimit, NULL); | ||
802 | if (j < 0) { | ||
803 | /* | ||
804 | * Didn't work. Revert the merge. | ||
805 | */ | ||
806 | memcpy(board, board2, wh); | ||
807 | tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE; | ||
808 | } else { | ||
809 | int c; | ||
810 | |||
811 | moves = j; | ||
812 | |||
813 | dsf_merge(dsf, c1, c2); | ||
814 | c = dsf_canonify(dsf, c1); | ||
815 | for (i = 0; i < wh; i++) | ||
816 | tried_merge[c*wh+i] = (tried_merge[c1*wh+i] | | ||
817 | tried_merge[c2*wh+i]); | ||
818 | for (i = 0; i < wh; i++) | ||
819 | tried_merge[i*wh+c] = (tried_merge[i*wh+c1] | | ||
820 | tried_merge[i*wh+c2]); | ||
821 | } | ||
822 | } | ||
823 | |||
824 | sfree(dsf); | ||
825 | sfree(list); | ||
826 | sfree(tried_merge); | ||
827 | sfree(board2); | ||
828 | |||
829 | *rtx = tx; | ||
830 | *rty = ty; | ||
831 | *rboard = board; | ||
832 | *rforcefield = forcefield; | ||
833 | *minmoves = moves; | ||
834 | } | ||
835 | |||
836 | /* ---------------------------------------------------------------------- | ||
837 | * End of solver/generator code. | ||
838 | */ | ||
839 | |||
840 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
841 | char **aux, int interactive) | ||
842 | { | ||
843 | int w = params->w, h = params->h, wh = w*h; | ||
844 | int tx, ty, minmoves; | ||
845 | unsigned char *board, *forcefield; | ||
846 | char *ret, *p; | ||
847 | int i; | ||
848 | |||
849 | generate_board(params->w, params->h, &tx, &ty, &minmoves, rs, | ||
850 | &board, &forcefield, params->maxmoves); | ||
851 | #ifdef GENERATOR_DIAGNOSTICS | ||
852 | { | ||
853 | char *t = board_text_format(params->w, params->h, board); | ||
854 | printf("%s\n", t); | ||
855 | sfree(t); | ||
856 | } | ||
857 | #endif | ||
858 | |||
859 | /* | ||
860 | * Encode as a game ID. | ||
861 | */ | ||
862 | ret = snewn(wh * 6 + 40, char); | ||
863 | p = ret; | ||
864 | i = 0; | ||
865 | while (i < wh) { | ||
866 | if (ISDIST(board[i])) { | ||
867 | p += sprintf(p, "d%d", board[i]); | ||
868 | i++; | ||
869 | } else { | ||
870 | int count = 1; | ||
871 | int b = board[i], f = forcefield[i]; | ||
872 | int c = (b == ANCHOR ? 'a' : | ||
873 | b == MAINANCHOR ? 'm' : | ||
874 | b == EMPTY ? 'e' : | ||
875 | /* b == WALL ? */ 'w'); | ||
876 | if (f) *p++ = 'f'; | ||
877 | *p++ = c; | ||
878 | i++; | ||
879 | while (i < wh && board[i] == b && forcefield[i] == f) | ||
880 | i++, count++; | ||
881 | if (count > 1) | ||
882 | p += sprintf(p, "%d", count); | ||
883 | } | ||
884 | } | ||
885 | p += sprintf(p, ",%d,%d,%d", tx, ty, minmoves); | ||
886 | ret = sresize(ret, p+1 - ret, char); | ||
887 | |||
888 | sfree(board); | ||
889 | sfree(forcefield); | ||
890 | |||
891 | return ret; | ||
892 | } | ||
893 | |||
894 | static char *validate_desc(const game_params *params, const char *desc) | ||
895 | { | ||
896 | int w = params->w, h = params->h, wh = w*h; | ||
897 | int *active, *link; | ||
898 | int mains = 0; | ||
899 | int i, tx, ty, minmoves; | ||
900 | char *ret; | ||
901 | |||
902 | active = snewn(wh, int); | ||
903 | link = snewn(wh, int); | ||
904 | i = 0; | ||
905 | |||
906 | while (*desc && *desc != ',') { | ||
907 | if (i >= wh) { | ||
908 | ret = "Too much data in game description"; | ||
909 | goto done; | ||
910 | } | ||
911 | link[i] = -1; | ||
912 | active[i] = FALSE; | ||
913 | if (*desc == 'f' || *desc == 'F') { | ||
914 | desc++; | ||
915 | if (!*desc) { | ||
916 | ret = "Expected another character after 'f' in game " | ||
917 | "description"; | ||
918 | goto done; | ||
919 | } | ||
920 | } | ||
921 | |||
922 | if (*desc == 'd' || *desc == 'D') { | ||
923 | int dist; | ||
924 | |||
925 | desc++; | ||
926 | if (!isdigit((unsigned char)*desc)) { | ||
927 | ret = "Expected a number after 'd' in game description"; | ||
928 | goto done; | ||
929 | } | ||
930 | dist = atoi(desc); | ||
931 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
932 | |||
933 | if (dist <= 0 || dist > i) { | ||
934 | ret = "Out-of-range number after 'd' in game description"; | ||
935 | goto done; | ||
936 | } | ||
937 | |||
938 | if (!active[i - dist]) { | ||
939 | ret = "Invalid back-reference in game description"; | ||
940 | goto done; | ||
941 | } | ||
942 | |||
943 | link[i] = i - dist; | ||
944 | |||
945 | active[i] = TRUE; | ||
946 | active[link[i]] = FALSE; | ||
947 | i++; | ||
948 | } else { | ||
949 | int c = *desc++; | ||
950 | int count = 1; | ||
951 | |||
952 | if (!strchr("aAmMeEwW", c)) { | ||
953 | ret = "Invalid character in game description"; | ||
954 | goto done; | ||
955 | } | ||
956 | if (isdigit((unsigned char)*desc)) { | ||
957 | count = atoi(desc); | ||
958 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
959 | } | ||
960 | if (i + count > wh) { | ||
961 | ret = "Too much data in game description"; | ||
962 | goto done; | ||
963 | } | ||
964 | while (count-- > 0) { | ||
965 | active[i] = (strchr("aAmM", c) != NULL); | ||
966 | link[i] = -1; | ||
967 | if (strchr("mM", c) != NULL) { | ||
968 | mains++; | ||
969 | } | ||
970 | i++; | ||
971 | } | ||
972 | } | ||
973 | } | ||
974 | if (mains != 1) { | ||
975 | ret = (mains == 0 ? "No main piece specified in game description" : | ||
976 | "More than one main piece specified in game description"); | ||
977 | goto done; | ||
978 | } | ||
979 | if (i < wh) { | ||
980 | ret = "Not enough data in game description"; | ||
981 | goto done; | ||
982 | } | ||
983 | |||
984 | /* | ||
985 | * Now read the target coordinates. | ||
986 | */ | ||
987 | i = sscanf(desc, ",%d,%d,%d", &tx, &ty, &minmoves); | ||
988 | if (i < 2) { | ||
989 | ret = "No target coordinates specified"; | ||
990 | goto done; | ||
991 | /* | ||
992 | * (but minmoves is optional) | ||
993 | */ | ||
994 | } | ||
995 | |||
996 | ret = NULL; | ||
997 | |||
998 | done: | ||
999 | sfree(active); | ||
1000 | sfree(link); | ||
1001 | return ret; | ||
1002 | } | ||
1003 | |||
1004 | static game_state *new_game(midend *me, const game_params *params, | ||
1005 | const char *desc) | ||
1006 | { | ||
1007 | int w = params->w, h = params->h, wh = w*h; | ||
1008 | game_state *state; | ||
1009 | int i; | ||
1010 | |||
1011 | state = snew(game_state); | ||
1012 | state->w = w; | ||
1013 | state->h = h; | ||
1014 | state->board = snewn(wh, unsigned char); | ||
1015 | state->lastmoved = state->lastmoved_pos = -1; | ||
1016 | state->movecount = 0; | ||
1017 | state->imm = snew(struct game_immutable_state); | ||
1018 | state->imm->refcount = 1; | ||
1019 | state->imm->forcefield = snewn(wh, unsigned char); | ||
1020 | |||
1021 | i = 0; | ||
1022 | |||
1023 | while (*desc && *desc != ',') { | ||
1024 | int f = FALSE; | ||
1025 | |||
1026 | assert(i < wh); | ||
1027 | |||
1028 | if (*desc == 'f') { | ||
1029 | f = TRUE; | ||
1030 | desc++; | ||
1031 | assert(*desc); | ||
1032 | } | ||
1033 | |||
1034 | if (*desc == 'd' || *desc == 'D') { | ||
1035 | int dist; | ||
1036 | |||
1037 | desc++; | ||
1038 | dist = atoi(desc); | ||
1039 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
1040 | |||
1041 | state->board[i] = DIST(dist); | ||
1042 | state->imm->forcefield[i] = f; | ||
1043 | |||
1044 | i++; | ||
1045 | } else { | ||
1046 | int c = *desc++; | ||
1047 | int count = 1; | ||
1048 | |||
1049 | if (isdigit((unsigned char)*desc)) { | ||
1050 | count = atoi(desc); | ||
1051 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
1052 | } | ||
1053 | assert(i + count <= wh); | ||
1054 | |||
1055 | c = (c == 'a' || c == 'A' ? ANCHOR : | ||
1056 | c == 'm' || c == 'M' ? MAINANCHOR : | ||
1057 | c == 'e' || c == 'E' ? EMPTY : | ||
1058 | /* c == 'w' || c == 'W' ? */ WALL); | ||
1059 | |||
1060 | while (count-- > 0) { | ||
1061 | state->board[i] = c; | ||
1062 | state->imm->forcefield[i] = f; | ||
1063 | i++; | ||
1064 | } | ||
1065 | } | ||
1066 | } | ||
1067 | |||
1068 | /* | ||
1069 | * Now read the target coordinates. | ||
1070 | */ | ||
1071 | state->tx = state->ty = 0; | ||
1072 | state->minmoves = -1; | ||
1073 | i = sscanf(desc, ",%d,%d,%d", &state->tx, &state->ty, &state->minmoves); | ||
1074 | |||
1075 | if (state->board[state->ty*w+state->tx] == MAINANCHOR) | ||
1076 | state->completed = 0; /* already complete! */ | ||
1077 | else | ||
1078 | state->completed = -1; | ||
1079 | |||
1080 | state->cheated = FALSE; | ||
1081 | state->soln = NULL; | ||
1082 | state->soln_index = -1; | ||
1083 | |||
1084 | return state; | ||
1085 | } | ||
1086 | |||
1087 | static game_state *dup_game(const game_state *state) | ||
1088 | { | ||
1089 | int w = state->w, h = state->h, wh = w*h; | ||
1090 | game_state *ret = snew(game_state); | ||
1091 | |||
1092 | ret->w = state->w; | ||
1093 | ret->h = state->h; | ||
1094 | ret->board = snewn(wh, unsigned char); | ||
1095 | memcpy(ret->board, state->board, wh); | ||
1096 | ret->tx = state->tx; | ||
1097 | ret->ty = state->ty; | ||
1098 | ret->minmoves = state->minmoves; | ||
1099 | ret->lastmoved = state->lastmoved; | ||
1100 | ret->lastmoved_pos = state->lastmoved_pos; | ||
1101 | ret->movecount = state->movecount; | ||
1102 | ret->completed = state->completed; | ||
1103 | ret->cheated = state->cheated; | ||
1104 | ret->imm = state->imm; | ||
1105 | ret->imm->refcount++; | ||
1106 | ret->soln = state->soln; | ||
1107 | ret->soln_index = state->soln_index; | ||
1108 | if (ret->soln) | ||
1109 | ret->soln->refcount++; | ||
1110 | |||
1111 | return ret; | ||
1112 | } | ||
1113 | |||
1114 | static void free_game(game_state *state) | ||
1115 | { | ||
1116 | if (--state->imm->refcount <= 0) { | ||
1117 | sfree(state->imm->forcefield); | ||
1118 | sfree(state->imm); | ||
1119 | } | ||
1120 | if (state->soln && --state->soln->refcount <= 0) { | ||
1121 | sfree(state->soln->moves); | ||
1122 | sfree(state->soln); | ||
1123 | } | ||
1124 | sfree(state->board); | ||
1125 | sfree(state); | ||
1126 | } | ||
1127 | |||
1128 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1129 | const char *aux, char **error) | ||
1130 | { | ||
1131 | int *moves; | ||
1132 | int nmoves; | ||
1133 | int i; | ||
1134 | char *ret, *p, sep; | ||
1135 | |||
1136 | /* | ||
1137 | * Run the solver and attempt to find the shortest solution | ||
1138 | * from the current position. | ||
1139 | */ | ||
1140 | nmoves = solve_board(state->w, state->h, state->board, | ||
1141 | state->imm->forcefield, state->tx, state->ty, | ||
1142 | -1, &moves); | ||
1143 | |||
1144 | if (nmoves < 0) { | ||
1145 | *error = "Unable to find a solution to this puzzle"; | ||
1146 | return NULL; | ||
1147 | } | ||
1148 | if (nmoves == 0) { | ||
1149 | *error = "Puzzle is already solved"; | ||
1150 | return NULL; | ||
1151 | } | ||
1152 | |||
1153 | /* | ||
1154 | * Encode the resulting solution as a move string. | ||
1155 | */ | ||
1156 | ret = snewn(nmoves * 40, char); | ||
1157 | p = ret; | ||
1158 | sep = 'S'; | ||
1159 | |||
1160 | for (i = 0; i < nmoves; i++) { | ||
1161 | p += sprintf(p, "%c%d-%d", sep, moves[i*2], moves[i*2+1]); | ||
1162 | sep = ','; | ||
1163 | } | ||
1164 | |||
1165 | sfree(moves); | ||
1166 | assert(p - ret < nmoves * 40); | ||
1167 | ret = sresize(ret, p+1 - ret, char); | ||
1168 | |||
1169 | return ret; | ||
1170 | } | ||
1171 | |||
1172 | static int game_can_format_as_text_now(const game_params *params) | ||
1173 | { | ||
1174 | return TRUE; | ||
1175 | } | ||
1176 | |||
1177 | static char *game_text_format(const game_state *state) | ||
1178 | { | ||
1179 | return board_text_format(state->w, state->h, state->board, | ||
1180 | state->imm->forcefield); | ||
1181 | } | ||
1182 | |||
1183 | struct game_ui { | ||
1184 | int dragging; | ||
1185 | int drag_anchor; | ||
1186 | int drag_offset_x, drag_offset_y; | ||
1187 | int drag_currpos; | ||
1188 | unsigned char *reachable; | ||
1189 | int *bfs_queue; /* used as scratch in interpret_move */ | ||
1190 | }; | ||
1191 | |||
1192 | static game_ui *new_ui(const game_state *state) | ||
1193 | { | ||
1194 | int w = state->w, h = state->h, wh = w*h; | ||
1195 | game_ui *ui = snew(game_ui); | ||
1196 | |||
1197 | ui->dragging = FALSE; | ||
1198 | ui->drag_anchor = ui->drag_currpos = -1; | ||
1199 | ui->drag_offset_x = ui->drag_offset_y = -1; | ||
1200 | ui->reachable = snewn(wh, unsigned char); | ||
1201 | memset(ui->reachable, 0, wh); | ||
1202 | ui->bfs_queue = snewn(wh, int); | ||
1203 | |||
1204 | return ui; | ||
1205 | } | ||
1206 | |||
1207 | static void free_ui(game_ui *ui) | ||
1208 | { | ||
1209 | sfree(ui->bfs_queue); | ||
1210 | sfree(ui->reachable); | ||
1211 | sfree(ui); | ||
1212 | } | ||
1213 | |||
1214 | static char *encode_ui(const game_ui *ui) | ||
1215 | { | ||
1216 | return NULL; | ||
1217 | } | ||
1218 | |||
1219 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1220 | { | ||
1221 | } | ||
1222 | |||
1223 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1224 | const game_state *newstate) | ||
1225 | { | ||
1226 | } | ||
1227 | |||
1228 | #define PREFERRED_TILESIZE 32 | ||
1229 | #define TILESIZE (ds->tilesize) | ||
1230 | #define BORDER (TILESIZE/2) | ||
1231 | #define COORD(x) ( (x) * TILESIZE + BORDER ) | ||
1232 | #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) | ||
1233 | #define BORDER_WIDTH (1 + TILESIZE/20) | ||
1234 | #define HIGHLIGHT_WIDTH (1 + TILESIZE/16) | ||
1235 | |||
1236 | #define FLASH_INTERVAL 0.10F | ||
1237 | #define FLASH_TIME 3*FLASH_INTERVAL | ||
1238 | |||
1239 | struct game_drawstate { | ||
1240 | int tilesize; | ||
1241 | int w, h; | ||
1242 | unsigned long *grid; /* what's currently displayed */ | ||
1243 | int started; | ||
1244 | }; | ||
1245 | |||
1246 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1247 | const game_drawstate *ds, | ||
1248 | int x, int y, int button) | ||
1249 | { | ||
1250 | int w = state->w, h = state->h, wh = w*h; | ||
1251 | int tx, ty, i, j; | ||
1252 | int qhead, qtail; | ||
1253 | |||
1254 | if (button == LEFT_BUTTON) { | ||
1255 | tx = FROMCOORD(x); | ||
1256 | ty = FROMCOORD(y); | ||
1257 | |||
1258 | if (tx < 0 || tx >= w || ty < 0 || ty >= h || | ||
1259 | !ISBLOCK(state->board[ty*w+tx])) | ||
1260 | return NULL; /* this click has no effect */ | ||
1261 | |||
1262 | /* | ||
1263 | * User has clicked on a block. Find the block's anchor | ||
1264 | * and register that we've started dragging it. | ||
1265 | */ | ||
1266 | i = ty*w+tx; | ||
1267 | while (ISDIST(state->board[i])) | ||
1268 | i -= state->board[i]; | ||
1269 | assert(i >= 0 && i < wh); | ||
1270 | |||
1271 | ui->dragging = TRUE; | ||
1272 | ui->drag_anchor = i; | ||
1273 | ui->drag_offset_x = tx - (i % w); | ||
1274 | ui->drag_offset_y = ty - (i / w); | ||
1275 | ui->drag_currpos = i; | ||
1276 | |||
1277 | /* | ||
1278 | * Now we immediately bfs out from the current location of | ||
1279 | * the anchor, to find all the places to which this block | ||
1280 | * can be dragged. | ||
1281 | */ | ||
1282 | memset(ui->reachable, FALSE, wh); | ||
1283 | qhead = qtail = 0; | ||
1284 | ui->reachable[i] = TRUE; | ||
1285 | ui->bfs_queue[qtail++] = i; | ||
1286 | for (j = i; j < wh; j++) | ||
1287 | if (state->board[j] == DIST(j - i)) | ||
1288 | i = j; | ||
1289 | while (qhead < qtail) { | ||
1290 | int pos = ui->bfs_queue[qhead++]; | ||
1291 | int x = pos % w, y = pos / w; | ||
1292 | int dir; | ||
1293 | |||
1294 | for (dir = 0; dir < 4; dir++) { | ||
1295 | int dx = (dir == 0 ? -1 : dir == 1 ? +1 : 0); | ||
1296 | int dy = (dir == 2 ? -1 : dir == 3 ? +1 : 0); | ||
1297 | int newpos; | ||
1298 | |||
1299 | if (x + dx < 0 || x + dx >= w || | ||
1300 | y + dy < 0 || y + dy >= h) | ||
1301 | continue; | ||
1302 | |||
1303 | newpos = pos + dy*w + dx; | ||
1304 | if (ui->reachable[newpos]) | ||
1305 | continue; /* already done this one */ | ||
1306 | |||
1307 | /* | ||
1308 | * Now search the grid to see if the block we're | ||
1309 | * dragging could fit into this space. | ||
1310 | */ | ||
1311 | for (j = i; j >= 0; j = (ISDIST(state->board[j]) ? | ||
1312 | j - state->board[j] : -1)) { | ||
1313 | int jx = (j+pos-ui->drag_anchor) % w; | ||
1314 | int jy = (j+pos-ui->drag_anchor) / w; | ||
1315 | int j2; | ||
1316 | |||
1317 | if (jx + dx < 0 || jx + dx >= w || | ||
1318 | jy + dy < 0 || jy + dy >= h) | ||
1319 | break; /* this position isn't valid at all */ | ||
1320 | |||
1321 | j2 = (j+pos-ui->drag_anchor) + dy*w + dx; | ||
1322 | |||
1323 | if (state->board[j2] == EMPTY && | ||
1324 | (!state->imm->forcefield[j2] || | ||
1325 | state->board[ui->drag_anchor] == MAINANCHOR)) | ||
1326 | continue; | ||
1327 | while (ISDIST(state->board[j2])) | ||
1328 | j2 -= state->board[j2]; | ||
1329 | assert(j2 >= 0 && j2 < wh); | ||
1330 | if (j2 == ui->drag_anchor) | ||
1331 | continue; | ||
1332 | else | ||
1333 | break; | ||
1334 | } | ||
1335 | |||
1336 | if (j < 0) { | ||
1337 | /* | ||
1338 | * If we got to the end of that loop without | ||
1339 | * disqualifying this position, mark it as | ||
1340 | * reachable for this drag. | ||
1341 | */ | ||
1342 | ui->reachable[newpos] = TRUE; | ||
1343 | ui->bfs_queue[qtail++] = newpos; | ||
1344 | } | ||
1345 | } | ||
1346 | } | ||
1347 | |||
1348 | /* | ||
1349 | * And that's it. Update the display to reflect the start | ||
1350 | * of a drag. | ||
1351 | */ | ||
1352 | return ""; | ||
1353 | } else if (button == LEFT_DRAG && ui->dragging) { | ||
1354 | int dist, distlimit, dx, dy, s, px, py; | ||
1355 | |||
1356 | tx = FROMCOORD(x); | ||
1357 | ty = FROMCOORD(y); | ||
1358 | |||
1359 | tx -= ui->drag_offset_x; | ||
1360 | ty -= ui->drag_offset_y; | ||
1361 | |||
1362 | /* | ||
1363 | * Now search outwards from (tx,ty), in order of Manhattan | ||
1364 | * distance, until we find a reachable square. | ||
1365 | */ | ||
1366 | distlimit = w+tx; | ||
1367 | distlimit = max(distlimit, h+ty); | ||
1368 | distlimit = max(distlimit, tx); | ||
1369 | distlimit = max(distlimit, ty); | ||
1370 | for (dist = 0; dist <= distlimit; dist++) { | ||
1371 | for (dx = -dist; dx <= dist; dx++) | ||
1372 | for (s = -1; s <= +1; s += 2) { | ||
1373 | dy = s * (dist - abs(dx)); | ||
1374 | px = tx + dx; | ||
1375 | py = ty + dy; | ||
1376 | if (px >= 0 && px < w && py >= 0 && py < h && | ||
1377 | ui->reachable[py*w+px]) { | ||
1378 | ui->drag_currpos = py*w+px; | ||
1379 | return ""; | ||
1380 | } | ||
1381 | } | ||
1382 | } | ||
1383 | return NULL; /* give up - this drag has no effect */ | ||
1384 | } else if (button == LEFT_RELEASE && ui->dragging) { | ||
1385 | char data[256], *str; | ||
1386 | |||
1387 | /* | ||
1388 | * Terminate the drag, and if the piece has actually moved | ||
1389 | * then return a move string quoting the old and new | ||
1390 | * locations of the piece's anchor. | ||
1391 | */ | ||
1392 | if (ui->drag_anchor != ui->drag_currpos) { | ||
1393 | sprintf(data, "M%d-%d", ui->drag_anchor, ui->drag_currpos); | ||
1394 | str = dupstr(data); | ||
1395 | } else | ||
1396 | str = ""; /* null move; just update the UI */ | ||
1397 | |||
1398 | ui->dragging = FALSE; | ||
1399 | ui->drag_anchor = ui->drag_currpos = -1; | ||
1400 | ui->drag_offset_x = ui->drag_offset_y = -1; | ||
1401 | memset(ui->reachable, 0, wh); | ||
1402 | |||
1403 | return str; | ||
1404 | } else if (button == ' ' && state->soln) { | ||
1405 | /* | ||
1406 | * Make the next move in the stored solution. | ||
1407 | */ | ||
1408 | char data[256]; | ||
1409 | int a1, a2; | ||
1410 | |||
1411 | a1 = state->soln->moves[state->soln_index*2]; | ||
1412 | a2 = state->soln->moves[state->soln_index*2+1]; | ||
1413 | if (a1 == state->lastmoved_pos) | ||
1414 | a1 = state->lastmoved; | ||
1415 | |||
1416 | sprintf(data, "M%d-%d", a1, a2); | ||
1417 | return dupstr(data); | ||
1418 | } | ||
1419 | |||
1420 | return NULL; | ||
1421 | } | ||
1422 | |||
1423 | static int move_piece(int w, int h, const unsigned char *src, | ||
1424 | unsigned char *dst, unsigned char *ff, int from, int to) | ||
1425 | { | ||
1426 | int wh = w*h; | ||
1427 | int i, j; | ||
1428 | |||
1429 | if (!ISANCHOR(dst[from])) | ||
1430 | return FALSE; | ||
1431 | |||
1432 | /* | ||
1433 | * Scan to the far end of the piece's linked list. | ||
1434 | */ | ||
1435 | for (i = j = from; j < wh; j++) | ||
1436 | if (src[j] == DIST(j - i)) | ||
1437 | i = j; | ||
1438 | |||
1439 | /* | ||
1440 | * Remove the piece from its old location in the new | ||
1441 | * game state. | ||
1442 | */ | ||
1443 | for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) | ||
1444 | dst[j] = EMPTY; | ||
1445 | |||
1446 | /* | ||
1447 | * And put it back in at the new location. | ||
1448 | */ | ||
1449 | for (j = i; j >= 0; j = (ISDIST(src[j]) ? j - src[j] : -1)) { | ||
1450 | int jn = j + to - from; | ||
1451 | if (jn < 0 || jn >= wh) | ||
1452 | return FALSE; | ||
1453 | if (dst[jn] == EMPTY && (!ff[jn] || src[from] == MAINANCHOR)) { | ||
1454 | dst[jn] = src[j]; | ||
1455 | } else { | ||
1456 | return FALSE; | ||
1457 | } | ||
1458 | } | ||
1459 | |||
1460 | return TRUE; | ||
1461 | } | ||
1462 | |||
1463 | static game_state *execute_move(const game_state *state, const char *move) | ||
1464 | { | ||
1465 | int w = state->w, h = state->h /* , wh = w*h */; | ||
1466 | char c; | ||
1467 | int a1, a2, n, movesize; | ||
1468 | game_state *ret = dup_game(state); | ||
1469 | |||
1470 | while (*move) { | ||
1471 | c = *move; | ||
1472 | if (c == 'S') { | ||
1473 | /* | ||
1474 | * This is a solve move, so we just set up a stored | ||
1475 | * solution path. | ||
1476 | */ | ||
1477 | if (ret->soln && --ret->soln->refcount <= 0) { | ||
1478 | sfree(ret->soln->moves); | ||
1479 | sfree(ret->soln); | ||
1480 | } | ||
1481 | ret->soln = snew(struct game_solution); | ||
1482 | ret->soln->nmoves = 0; | ||
1483 | ret->soln->moves = NULL; | ||
1484 | ret->soln->refcount = 1; | ||
1485 | ret->soln_index = 0; | ||
1486 | ret->cheated = TRUE; | ||
1487 | |||
1488 | movesize = 0; | ||
1489 | move++; | ||
1490 | while (1) { | ||
1491 | if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2) { | ||
1492 | free_game(ret); | ||
1493 | return NULL; | ||
1494 | } | ||
1495 | |||
1496 | /* | ||
1497 | * Special case: if the first move in the solution | ||
1498 | * involves the piece for which we already have a | ||
1499 | * partial stored move, adjust the source point to | ||
1500 | * the original starting point of that piece. | ||
1501 | */ | ||
1502 | if (ret->soln->nmoves == 0 && a1 == ret->lastmoved) | ||
1503 | a1 = ret->lastmoved_pos; | ||
1504 | |||
1505 | if (ret->soln->nmoves >= movesize) { | ||
1506 | movesize = (ret->soln->nmoves + 48) * 4 / 3; | ||
1507 | ret->soln->moves = sresize(ret->soln->moves, | ||
1508 | 2*movesize, int); | ||
1509 | } | ||
1510 | |||
1511 | ret->soln->moves[2*ret->soln->nmoves] = a1; | ||
1512 | ret->soln->moves[2*ret->soln->nmoves+1] = a2; | ||
1513 | ret->soln->nmoves++; | ||
1514 | move += n; | ||
1515 | if (*move != ',') | ||
1516 | break; | ||
1517 | move++; /* eat comma */ | ||
1518 | } | ||
1519 | } else if (c == 'M') { | ||
1520 | move++; | ||
1521 | if (sscanf(move, "%d-%d%n", &a1, &a2, &n) != 2 || | ||
1522 | !move_piece(w, h, state->board, ret->board, | ||
1523 | state->imm->forcefield, a1, a2)) { | ||
1524 | free_game(ret); | ||
1525 | return NULL; | ||
1526 | } | ||
1527 | if (a1 == ret->lastmoved) { | ||
1528 | /* | ||
1529 | * If the player has moved the same piece as they | ||
1530 | * moved last time, don't increment the move | ||
1531 | * count. In fact, if they've put the piece back | ||
1532 | * where it started from, _decrement_ the move | ||
1533 | * count. | ||
1534 | */ | ||
1535 | if (a2 == ret->lastmoved_pos) { | ||
1536 | ret->movecount--; /* reverted last move */ | ||
1537 | ret->lastmoved = ret->lastmoved_pos = -1; | ||
1538 | } else { | ||
1539 | ret->lastmoved = a2; | ||
1540 | /* don't change lastmoved_pos */ | ||
1541 | } | ||
1542 | } else { | ||
1543 | ret->lastmoved = a2; | ||
1544 | ret->lastmoved_pos = a1; | ||
1545 | ret->movecount++; | ||
1546 | } | ||
1547 | |||
1548 | /* | ||
1549 | * If we have a stored solution path, see if we've | ||
1550 | * strayed from it or successfully made the next move | ||
1551 | * along it. | ||
1552 | */ | ||
1553 | if (ret->soln && ret->lastmoved_pos >= 0) { | ||
1554 | if (ret->lastmoved_pos != | ||
1555 | ret->soln->moves[ret->soln_index*2]) { | ||
1556 | /* strayed from the path */ | ||
1557 | ret->soln->refcount--; | ||
1558 | assert(ret->soln->refcount > 0); | ||
1559 | /* `state' at least still exists */ | ||
1560 | ret->soln = NULL; | ||
1561 | ret->soln_index = -1; | ||
1562 | } else if (ret->lastmoved == | ||
1563 | ret->soln->moves[ret->soln_index*2+1]) { | ||
1564 | /* advanced along the path */ | ||
1565 | ret->soln_index++; | ||
1566 | if (ret->soln_index >= ret->soln->nmoves) { | ||
1567 | /* finished the path! */ | ||
1568 | ret->soln->refcount--; | ||
1569 | assert(ret->soln->refcount > 0); | ||
1570 | /* `state' at least still exists */ | ||
1571 | ret->soln = NULL; | ||
1572 | ret->soln_index = -1; | ||
1573 | } | ||
1574 | } | ||
1575 | } | ||
1576 | |||
1577 | if (ret->board[a2] == MAINANCHOR && | ||
1578 | a2 == ret->ty * w + ret->tx && ret->completed < 0) | ||
1579 | ret->completed = ret->movecount; | ||
1580 | move += n; | ||
1581 | } else { | ||
1582 | free_game(ret); | ||
1583 | return NULL; | ||
1584 | } | ||
1585 | if (*move == ';') | ||
1586 | move++; | ||
1587 | else if (*move) { | ||
1588 | free_game(ret); | ||
1589 | return NULL; | ||
1590 | } | ||
1591 | } | ||
1592 | |||
1593 | return ret; | ||
1594 | } | ||
1595 | |||
1596 | /* ---------------------------------------------------------------------- | ||
1597 | * Drawing routines. | ||
1598 | */ | ||
1599 | |||
1600 | static void game_compute_size(const game_params *params, int tilesize, | ||
1601 | int *x, int *y) | ||
1602 | { | ||
1603 | /* fool the macros */ | ||
1604 | struct dummy { int tilesize; } dummy, *ds = &dummy; | ||
1605 | dummy.tilesize = tilesize; | ||
1606 | |||
1607 | *x = params->w * TILESIZE + 2*BORDER; | ||
1608 | *y = params->h * TILESIZE + 2*BORDER; | ||
1609 | } | ||
1610 | |||
1611 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1612 | const game_params *params, int tilesize) | ||
1613 | { | ||
1614 | ds->tilesize = tilesize; | ||
1615 | } | ||
1616 | |||
1617 | static void raise_colour(float *target, float *src, float *limit) | ||
1618 | { | ||
1619 | int i; | ||
1620 | for (i = 0; i < 3; i++) | ||
1621 | target[i] = (2*src[i] + limit[i]) / 3; | ||
1622 | } | ||
1623 | |||
1624 | static float *game_colours(frontend *fe, int *ncolours) | ||
1625 | { | ||
1626 | float *ret = snewn(3 * NCOLOURS, float); | ||
1627 | |||
1628 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); | ||
1629 | |||
1630 | /* | ||
1631 | * When dragging a tile, we light it up a bit. | ||
1632 | */ | ||
1633 | raise_colour(ret+3*COL_DRAGGING, | ||
1634 | ret+3*COL_BACKGROUND, ret+3*COL_HIGHLIGHT); | ||
1635 | raise_colour(ret+3*COL_DRAGGING_HIGHLIGHT, | ||
1636 | ret+3*COL_HIGHLIGHT, ret+3*COL_HIGHLIGHT); | ||
1637 | raise_colour(ret+3*COL_DRAGGING_LOWLIGHT, | ||
1638 | ret+3*COL_LOWLIGHT, ret+3*COL_HIGHLIGHT); | ||
1639 | |||
1640 | /* | ||
1641 | * The main tile is tinted blue. | ||
1642 | */ | ||
1643 | ret[COL_MAIN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0]; | ||
1644 | ret[COL_MAIN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1]; | ||
1645 | ret[COL_MAIN * 3 + 2] = ret[COL_HIGHLIGHT * 3 + 2]; | ||
1646 | game_mkhighlight_specific(fe, ret, COL_MAIN, | ||
1647 | COL_MAIN_HIGHLIGHT, COL_MAIN_LOWLIGHT); | ||
1648 | |||
1649 | /* | ||
1650 | * And we light that up a bit too when dragging. | ||
1651 | */ | ||
1652 | raise_colour(ret+3*COL_MAIN_DRAGGING, | ||
1653 | ret+3*COL_MAIN, ret+3*COL_MAIN_HIGHLIGHT); | ||
1654 | raise_colour(ret+3*COL_MAIN_DRAGGING_HIGHLIGHT, | ||
1655 | ret+3*COL_MAIN_HIGHLIGHT, ret+3*COL_MAIN_HIGHLIGHT); | ||
1656 | raise_colour(ret+3*COL_MAIN_DRAGGING_LOWLIGHT, | ||
1657 | ret+3*COL_MAIN_LOWLIGHT, ret+3*COL_MAIN_HIGHLIGHT); | ||
1658 | |||
1659 | /* | ||
1660 | * The target area on the floor is tinted green. | ||
1661 | */ | ||
1662 | ret[COL_TARGET * 3 + 0] = ret[COL_BACKGROUND * 3 + 0]; | ||
1663 | ret[COL_TARGET * 3 + 1] = ret[COL_HIGHLIGHT * 3 + 1]; | ||
1664 | ret[COL_TARGET * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; | ||
1665 | game_mkhighlight_specific(fe, ret, COL_TARGET, | ||
1666 | COL_TARGET_HIGHLIGHT, COL_TARGET_LOWLIGHT); | ||
1667 | |||
1668 | *ncolours = NCOLOURS; | ||
1669 | return ret; | ||
1670 | } | ||
1671 | |||
1672 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1673 | { | ||
1674 | int w = state->w, h = state->h, wh = w*h; | ||
1675 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1676 | int i; | ||
1677 | |||
1678 | ds->tilesize = 0; | ||
1679 | ds->w = w; | ||
1680 | ds->h = h; | ||
1681 | ds->started = FALSE; | ||
1682 | ds->grid = snewn(wh, unsigned long); | ||
1683 | for (i = 0; i < wh; i++) | ||
1684 | ds->grid[i] = ~(unsigned long)0; | ||
1685 | |||
1686 | return ds; | ||
1687 | } | ||
1688 | |||
1689 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1690 | { | ||
1691 | sfree(ds->grid); | ||
1692 | sfree(ds); | ||
1693 | } | ||
1694 | |||
1695 | #define BG_NORMAL 0x00000001UL | ||
1696 | #define BG_TARGET 0x00000002UL | ||
1697 | #define BG_FORCEFIELD 0x00000004UL | ||
1698 | #define FLASH_LOW 0x00000008UL | ||
1699 | #define FLASH_HIGH 0x00000010UL | ||
1700 | #define FG_WALL 0x00000020UL | ||
1701 | #define FG_MAIN 0x00000040UL | ||
1702 | #define FG_NORMAL 0x00000080UL | ||
1703 | #define FG_DRAGGING 0x00000100UL | ||
1704 | #define FG_SHADOW 0x00000200UL | ||
1705 | #define FG_SOLVEPIECE 0x00000400UL | ||
1706 | #define FG_MAINPIECESH 11 | ||
1707 | #define FG_SHADOWSH 19 | ||
1708 | |||
1709 | #define PIECE_LBORDER 0x00000001UL | ||
1710 | #define PIECE_TBORDER 0x00000002UL | ||
1711 | #define PIECE_RBORDER 0x00000004UL | ||
1712 | #define PIECE_BBORDER 0x00000008UL | ||
1713 | #define PIECE_TLCORNER 0x00000010UL | ||
1714 | #define PIECE_TRCORNER 0x00000020UL | ||
1715 | #define PIECE_BLCORNER 0x00000040UL | ||
1716 | #define PIECE_BRCORNER 0x00000080UL | ||
1717 | #define PIECE_MASK 0x000000FFUL | ||
1718 | |||
1719 | /* | ||
1720 | * Utility function. | ||
1721 | */ | ||
1722 | #define TYPE_MASK 0xF000 | ||
1723 | #define COL_MASK 0x0FFF | ||
1724 | #define TYPE_RECT 0x0000 | ||
1725 | #define TYPE_TLCIRC 0x4000 | ||
1726 | #define TYPE_TRCIRC 0x5000 | ||
1727 | #define TYPE_BLCIRC 0x6000 | ||
1728 | #define TYPE_BRCIRC 0x7000 | ||
1729 | static void maybe_rect(drawing *dr, int x, int y, int w, int h, | ||
1730 | int coltype, int col2) | ||
1731 | { | ||
1732 | int colour = coltype & COL_MASK, type = coltype & TYPE_MASK; | ||
1733 | |||
1734 | if (colour > NCOLOURS) | ||
1735 | return; | ||
1736 | if (type == TYPE_RECT) { | ||
1737 | draw_rect(dr, x, y, w, h, colour); | ||
1738 | } else { | ||
1739 | int cx, cy, r; | ||
1740 | |||
1741 | clip(dr, x, y, w, h); | ||
1742 | |||
1743 | cx = x; | ||
1744 | cy = y; | ||
1745 | r = w-1; | ||
1746 | if (type & 0x1000) | ||
1747 | cx += r; | ||
1748 | if (type & 0x2000) | ||
1749 | cy += r; | ||
1750 | |||
1751 | if (col2 == -1 || col2 == coltype) { | ||
1752 | assert(w == h); | ||
1753 | draw_circle(dr, cx, cy, r, colour, colour); | ||
1754 | } else { | ||
1755 | /* | ||
1756 | * We aim to draw a quadrant of a circle in two | ||
1757 | * different colours. We do this using Bresenham's | ||
1758 | * algorithm directly, because the Puzzles drawing API | ||
1759 | * doesn't have a draw-sector primitive. | ||
1760 | */ | ||
1761 | int bx, by, bd, bd2; | ||
1762 | int xm = (type & 0x1000 ? -1 : +1); | ||
1763 | int ym = (type & 0x2000 ? -1 : +1); | ||
1764 | |||
1765 | by = r; | ||
1766 | bx = 0; | ||
1767 | bd = 0; | ||
1768 | while (by >= bx) { | ||
1769 | /* | ||
1770 | * Plot the point. | ||
1771 | */ | ||
1772 | { | ||
1773 | int x1 = cx+xm*bx, y1 = cy+ym*bx; | ||
1774 | int x2, y2; | ||
1775 | |||
1776 | x2 = cx+xm*by; y2 = y1; | ||
1777 | draw_rect(dr, min(x1,x2), min(y1,y2), | ||
1778 | abs(x1-x2)+1, abs(y1-y2)+1, colour); | ||
1779 | x2 = x1; y2 = cy+ym*by; | ||
1780 | draw_rect(dr, min(x1,x2), min(y1,y2), | ||
1781 | abs(x1-x2)+1, abs(y1-y2)+1, col2); | ||
1782 | } | ||
1783 | |||
1784 | bd += 2*bx + 1; | ||
1785 | bd2 = bd - (2*by - 1); | ||
1786 | if (abs(bd2) < abs(bd)) { | ||
1787 | bd = bd2; | ||
1788 | by--; | ||
1789 | } | ||
1790 | bx++; | ||
1791 | } | ||
1792 | } | ||
1793 | |||
1794 | unclip(dr); | ||
1795 | } | ||
1796 | } | ||
1797 | |||
1798 | static void draw_wallpart(drawing *dr, game_drawstate *ds, | ||
1799 | int tx, int ty, unsigned long val, | ||
1800 | int cl, int cc, int ch) | ||
1801 | { | ||
1802 | int coords[6]; | ||
1803 | |||
1804 | draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc); | ||
1805 | if (val & PIECE_LBORDER) | ||
1806 | draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, TILESIZE, | ||
1807 | ch); | ||
1808 | if (val & PIECE_RBORDER) | ||
1809 | draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, | ||
1810 | HIGHLIGHT_WIDTH, TILESIZE, cl); | ||
1811 | if (val & PIECE_TBORDER) | ||
1812 | draw_rect(dr, tx, ty, TILESIZE, HIGHLIGHT_WIDTH, ch); | ||
1813 | if (val & PIECE_BBORDER) | ||
1814 | draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, | ||
1815 | TILESIZE, HIGHLIGHT_WIDTH, cl); | ||
1816 | if (!((PIECE_BBORDER | PIECE_LBORDER) &~ val)) { | ||
1817 | draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, | ||
1818 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl); | ||
1819 | clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, | ||
1820 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH); | ||
1821 | coords[0] = tx - 1; | ||
1822 | coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1; | ||
1823 | coords[2] = tx + HIGHLIGHT_WIDTH; | ||
1824 | coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1; | ||
1825 | coords[4] = tx - 1; | ||
1826 | coords[5] = ty + TILESIZE; | ||
1827 | draw_polygon(dr, coords, 3, ch, ch); | ||
1828 | unclip(dr); | ||
1829 | } else if (val & PIECE_BLCORNER) { | ||
1830 | draw_rect(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, | ||
1831 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch); | ||
1832 | clip(dr, tx, ty+TILESIZE-HIGHLIGHT_WIDTH, | ||
1833 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH); | ||
1834 | coords[0] = tx - 1; | ||
1835 | coords[1] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1; | ||
1836 | coords[2] = tx + HIGHLIGHT_WIDTH; | ||
1837 | coords[3] = ty + TILESIZE - HIGHLIGHT_WIDTH - 1; | ||
1838 | coords[4] = tx - 1; | ||
1839 | coords[5] = ty + TILESIZE; | ||
1840 | draw_polygon(dr, coords, 3, cl, cl); | ||
1841 | unclip(dr); | ||
1842 | } | ||
1843 | if (!((PIECE_TBORDER | PIECE_RBORDER) &~ val)) { | ||
1844 | draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, | ||
1845 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl); | ||
1846 | clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, | ||
1847 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH); | ||
1848 | coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1; | ||
1849 | coords[1] = ty - 1; | ||
1850 | coords[2] = tx + TILESIZE; | ||
1851 | coords[3] = ty - 1; | ||
1852 | coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1; | ||
1853 | coords[5] = ty + HIGHLIGHT_WIDTH; | ||
1854 | draw_polygon(dr, coords, 3, ch, ch); | ||
1855 | unclip(dr); | ||
1856 | } else if (val & PIECE_TRCORNER) { | ||
1857 | draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, | ||
1858 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch); | ||
1859 | clip(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, ty, | ||
1860 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH); | ||
1861 | coords[0] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1; | ||
1862 | coords[1] = ty - 1; | ||
1863 | coords[2] = tx + TILESIZE; | ||
1864 | coords[3] = ty - 1; | ||
1865 | coords[4] = tx + TILESIZE - HIGHLIGHT_WIDTH - 1; | ||
1866 | coords[5] = ty + HIGHLIGHT_WIDTH; | ||
1867 | draw_polygon(dr, coords, 3, cl, cl); | ||
1868 | unclip(dr); | ||
1869 | } | ||
1870 | if (val & PIECE_TLCORNER) | ||
1871 | draw_rect(dr, tx, ty, HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, ch); | ||
1872 | if (val & PIECE_BRCORNER) | ||
1873 | draw_rect(dr, tx+TILESIZE-HIGHLIGHT_WIDTH, | ||
1874 | ty+TILESIZE-HIGHLIGHT_WIDTH, | ||
1875 | HIGHLIGHT_WIDTH, HIGHLIGHT_WIDTH, cl); | ||
1876 | } | ||
1877 | |||
1878 | static void draw_piecepart(drawing *dr, game_drawstate *ds, | ||
1879 | int tx, int ty, unsigned long val, | ||
1880 | int cl, int cc, int ch) | ||
1881 | { | ||
1882 | int x[6], y[6]; | ||
1883 | |||
1884 | /* | ||
1885 | * Drawing the blocks is hellishly fiddly. The blocks don't | ||
1886 | * stretch to the full size of the tile; there's a border | ||
1887 | * around them of size BORDER_WIDTH. Then they have bevelled | ||
1888 | * borders of size HIGHLIGHT_WIDTH, and also rounded corners. | ||
1889 | * | ||
1890 | * I tried for some time to find a clean and clever way to | ||
1891 | * figure out what needed drawing from the corner and border | ||
1892 | * flags, but in the end the cleanest way I could find was the | ||
1893 | * following. We divide the grid square into 25 parts by | ||
1894 | * ruling four horizontal and four vertical lines across it; | ||
1895 | * those lines are at BORDER_WIDTH and BORDER_WIDTH + | ||
1896 | * HIGHLIGHT_WIDTH from the top, from the bottom, from the | ||
1897 | * left and from the right. Then we carefully consider each of | ||
1898 | * the resulting 25 sections of square, and decide separately | ||
1899 | * what needs to go in it based on the flags. In complicated | ||
1900 | * cases there can be up to five possibilities affecting any | ||
1901 | * given section (no corner or border flags, just the corner | ||
1902 | * flag, one border flag, the other border flag, both border | ||
1903 | * flags). So there's a lot of very fiddly logic here and all | ||
1904 | * I could really think to do was give it my best shot and | ||
1905 | * then test it and correct all the typos. Not fun to write, | ||
1906 | * and I'm sure it isn't fun to read either, but it seems to | ||
1907 | * work. | ||
1908 | */ | ||
1909 | |||
1910 | x[0] = tx; | ||
1911 | x[1] = x[0] + BORDER_WIDTH; | ||
1912 | x[2] = x[1] + HIGHLIGHT_WIDTH; | ||
1913 | x[5] = tx + TILESIZE; | ||
1914 | x[4] = x[5] - BORDER_WIDTH; | ||
1915 | x[3] = x[4] - HIGHLIGHT_WIDTH; | ||
1916 | |||
1917 | y[0] = ty; | ||
1918 | y[1] = y[0] + BORDER_WIDTH; | ||
1919 | y[2] = y[1] + HIGHLIGHT_WIDTH; | ||
1920 | y[5] = ty + TILESIZE; | ||
1921 | y[4] = y[5] - BORDER_WIDTH; | ||
1922 | y[3] = y[4] - HIGHLIGHT_WIDTH; | ||
1923 | |||
1924 | #define RECT(p,q) x[p], y[q], x[(p)+1]-x[p], y[(q)+1]-y[q] | ||
1925 | |||
1926 | maybe_rect(dr, RECT(0,0), | ||
1927 | (val & (PIECE_TLCORNER | PIECE_TBORDER | | ||
1928 | PIECE_LBORDER)) ? -1 : cc, -1); | ||
1929 | maybe_rect(dr, RECT(1,0), | ||
1930 | (val & PIECE_TLCORNER) ? ch : (val & PIECE_TBORDER) ? -1 : | ||
1931 | (val & PIECE_LBORDER) ? ch : cc, -1); | ||
1932 | maybe_rect(dr, RECT(2,0), | ||
1933 | (val & PIECE_TBORDER) ? -1 : cc, -1); | ||
1934 | maybe_rect(dr, RECT(3,0), | ||
1935 | (val & PIECE_TRCORNER) ? cl : (val & PIECE_TBORDER) ? -1 : | ||
1936 | (val & PIECE_RBORDER) ? cl : cc, -1); | ||
1937 | maybe_rect(dr, RECT(4,0), | ||
1938 | (val & (PIECE_TRCORNER | PIECE_TBORDER | | ||
1939 | PIECE_RBORDER)) ? -1 : cc, -1); | ||
1940 | maybe_rect(dr, RECT(0,1), | ||
1941 | (val & PIECE_TLCORNER) ? ch : (val & PIECE_LBORDER) ? -1 : | ||
1942 | (val & PIECE_TBORDER) ? ch : cc, -1); | ||
1943 | maybe_rect(dr, RECT(1,1), | ||
1944 | (val & PIECE_TLCORNER) ? cc : -1, -1); | ||
1945 | maybe_rect(dr, RECT(1,1), | ||
1946 | (val & PIECE_TLCORNER) ? ch | TYPE_TLCIRC : | ||
1947 | !((PIECE_TBORDER | PIECE_LBORDER) &~ val) ? ch | TYPE_BRCIRC : | ||
1948 | (val & (PIECE_TBORDER | PIECE_LBORDER)) ? ch : cc, -1); | ||
1949 | maybe_rect(dr, RECT(2,1), | ||
1950 | (val & PIECE_TBORDER) ? ch : cc, -1); | ||
1951 | maybe_rect(dr, RECT(3,1), | ||
1952 | (val & PIECE_TRCORNER) ? cc : -1, -1); | ||
1953 | maybe_rect(dr, RECT(3,1), | ||
1954 | (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_TBORDER ? ch : | ||
1955 | (val & (PIECE_TBORDER | PIECE_RBORDER)) == PIECE_RBORDER ? cl : | ||
1956 | !((PIECE_TBORDER|PIECE_RBORDER) &~ val) ? cl | TYPE_BLCIRC : | ||
1957 | (val & PIECE_TRCORNER) ? cl | TYPE_TRCIRC : | ||
1958 | cc, ch); | ||
1959 | maybe_rect(dr, RECT(4,1), | ||
1960 | (val & PIECE_TRCORNER) ? ch : (val & PIECE_RBORDER) ? -1 : | ||
1961 | (val & PIECE_TBORDER) ? ch : cc, -1); | ||
1962 | maybe_rect(dr, RECT(0,2), | ||
1963 | (val & PIECE_LBORDER) ? -1 : cc, -1); | ||
1964 | maybe_rect(dr, RECT(1,2), | ||
1965 | (val & PIECE_LBORDER) ? ch : cc, -1); | ||
1966 | maybe_rect(dr, RECT(2,2), | ||
1967 | cc, -1); | ||
1968 | maybe_rect(dr, RECT(3,2), | ||
1969 | (val & PIECE_RBORDER) ? cl : cc, -1); | ||
1970 | maybe_rect(dr, RECT(4,2), | ||
1971 | (val & PIECE_RBORDER) ? -1 : cc, -1); | ||
1972 | maybe_rect(dr, RECT(0,3), | ||
1973 | (val & PIECE_BLCORNER) ? cl : (val & PIECE_LBORDER) ? -1 : | ||
1974 | (val & PIECE_BBORDER) ? cl : cc, -1); | ||
1975 | maybe_rect(dr, RECT(1,3), | ||
1976 | (val & PIECE_BLCORNER) ? cc : -1, -1); | ||
1977 | maybe_rect(dr, RECT(1,3), | ||
1978 | (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_BBORDER ? cl : | ||
1979 | (val & (PIECE_BBORDER | PIECE_LBORDER)) == PIECE_LBORDER ? ch : | ||
1980 | !((PIECE_BBORDER|PIECE_LBORDER) &~ val) ? ch | TYPE_TRCIRC : | ||
1981 | (val & PIECE_BLCORNER) ? ch | TYPE_BLCIRC : | ||
1982 | cc, cl); | ||
1983 | maybe_rect(dr, RECT(2,3), | ||
1984 | (val & PIECE_BBORDER) ? cl : cc, -1); | ||
1985 | maybe_rect(dr, RECT(3,3), | ||
1986 | (val & PIECE_BRCORNER) ? cc : -1, -1); | ||
1987 | maybe_rect(dr, RECT(3,3), | ||
1988 | (val & PIECE_BRCORNER) ? cl | TYPE_BRCIRC : | ||
1989 | !((PIECE_BBORDER | PIECE_RBORDER) &~ val) ? cl | TYPE_TLCIRC : | ||
1990 | (val & (PIECE_BBORDER | PIECE_RBORDER)) ? cl : cc, -1); | ||
1991 | maybe_rect(dr, RECT(4,3), | ||
1992 | (val & PIECE_BRCORNER) ? cl : (val & PIECE_RBORDER) ? -1 : | ||
1993 | (val & PIECE_BBORDER) ? cl : cc, -1); | ||
1994 | maybe_rect(dr, RECT(0,4), | ||
1995 | (val & (PIECE_BLCORNER | PIECE_BBORDER | | ||
1996 | PIECE_LBORDER)) ? -1 : cc, -1); | ||
1997 | maybe_rect(dr, RECT(1,4), | ||
1998 | (val & PIECE_BLCORNER) ? ch : (val & PIECE_BBORDER) ? -1 : | ||
1999 | (val & PIECE_LBORDER) ? ch : cc, -1); | ||
2000 | maybe_rect(dr, RECT(2,4), | ||
2001 | (val & PIECE_BBORDER) ? -1 : cc, -1); | ||
2002 | maybe_rect(dr, RECT(3,4), | ||
2003 | (val & PIECE_BRCORNER) ? cl : (val & PIECE_BBORDER) ? -1 : | ||
2004 | (val & PIECE_RBORDER) ? cl : cc, -1); | ||
2005 | maybe_rect(dr, RECT(4,4), | ||
2006 | (val & (PIECE_BRCORNER | PIECE_BBORDER | | ||
2007 | PIECE_RBORDER)) ? -1 : cc, -1); | ||
2008 | |||
2009 | #undef RECT | ||
2010 | } | ||
2011 | |||
2012 | static void draw_tile(drawing *dr, game_drawstate *ds, | ||
2013 | int x, int y, unsigned long val) | ||
2014 | { | ||
2015 | int tx = COORD(x), ty = COORD(y); | ||
2016 | int cc, ch, cl; | ||
2017 | |||
2018 | /* | ||
2019 | * Draw the tile background. | ||
2020 | */ | ||
2021 | if (val & BG_TARGET) | ||
2022 | cc = COL_TARGET; | ||
2023 | else | ||
2024 | cc = COL_BACKGROUND; | ||
2025 | ch = cc+1; | ||
2026 | cl = cc+2; | ||
2027 | if (val & FLASH_LOW) | ||
2028 | cc = cl; | ||
2029 | else if (val & FLASH_HIGH) | ||
2030 | cc = ch; | ||
2031 | |||
2032 | draw_rect(dr, tx, ty, TILESIZE, TILESIZE, cc); | ||
2033 | if (val & BG_FORCEFIELD) { | ||
2034 | /* | ||
2035 | * Cattle-grid effect to indicate that nothing but the | ||
2036 | * main block can slide over this square. | ||
2037 | */ | ||
2038 | int n = 3 * (TILESIZE / (3*HIGHLIGHT_WIDTH)); | ||
2039 | int i; | ||
2040 | |||
2041 | for (i = 1; i < n; i += 3) { | ||
2042 | draw_rect(dr, tx,ty+(TILESIZE*i/n), TILESIZE,HIGHLIGHT_WIDTH, cl); | ||
2043 | draw_rect(dr, tx+(TILESIZE*i/n),ty, HIGHLIGHT_WIDTH,TILESIZE, cl); | ||
2044 | } | ||
2045 | } | ||
2046 | |||
2047 | /* | ||
2048 | * Draw the tile midground: a shadow of a block, for | ||
2049 | * displaying partial solutions. | ||
2050 | */ | ||
2051 | if (val & FG_SHADOW) { | ||
2052 | draw_piecepart(dr, ds, tx, ty, (val >> FG_SHADOWSH) & PIECE_MASK, | ||
2053 | cl, cl, cl); | ||
2054 | } | ||
2055 | |||
2056 | /* | ||
2057 | * Draw the tile foreground, i.e. some section of a block or | ||
2058 | * wall. | ||
2059 | */ | ||
2060 | if (val & FG_WALL) { | ||
2061 | cc = COL_BACKGROUND; | ||
2062 | ch = cc+1; | ||
2063 | cl = cc+2; | ||
2064 | if (val & FLASH_LOW) | ||
2065 | cc = cl; | ||
2066 | else if (val & FLASH_HIGH) | ||
2067 | cc = ch; | ||
2068 | |||
2069 | draw_wallpart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK, | ||
2070 | cl, cc, ch); | ||
2071 | } else if (val & (FG_MAIN | FG_NORMAL)) { | ||
2072 | if (val & FG_DRAGGING) | ||
2073 | cc = (val & FG_MAIN ? COL_MAIN_DRAGGING : COL_DRAGGING); | ||
2074 | else | ||
2075 | cc = (val & FG_MAIN ? COL_MAIN : COL_BACKGROUND); | ||
2076 | ch = cc+1; | ||
2077 | cl = cc+2; | ||
2078 | |||
2079 | if (val & FLASH_LOW) | ||
2080 | cc = cl; | ||
2081 | else if (val & (FLASH_HIGH | FG_SOLVEPIECE)) | ||
2082 | cc = ch; | ||
2083 | |||
2084 | draw_piecepart(dr, ds, tx, ty, (val >> FG_MAINPIECESH) & PIECE_MASK, | ||
2085 | cl, cc, ch); | ||
2086 | } | ||
2087 | |||
2088 | draw_update(dr, tx, ty, TILESIZE, TILESIZE); | ||
2089 | } | ||
2090 | |||
2091 | static unsigned long find_piecepart(int w, int h, int *dsf, int x, int y) | ||
2092 | { | ||
2093 | int i = y*w+x; | ||
2094 | int canon = dsf_canonify(dsf, i); | ||
2095 | unsigned long val = 0; | ||
2096 | |||
2097 | if (x == 0 || canon != dsf_canonify(dsf, i-1)) | ||
2098 | val |= PIECE_LBORDER; | ||
2099 | if (y== 0 || canon != dsf_canonify(dsf, i-w)) | ||
2100 | val |= PIECE_TBORDER; | ||
2101 | if (x == w-1 || canon != dsf_canonify(dsf, i+1)) | ||
2102 | val |= PIECE_RBORDER; | ||
2103 | if (y == h-1 || canon != dsf_canonify(dsf, i+w)) | ||
2104 | val |= PIECE_BBORDER; | ||
2105 | if (!(val & (PIECE_TBORDER | PIECE_LBORDER)) && | ||
2106 | canon != dsf_canonify(dsf, i-1-w)) | ||
2107 | val |= PIECE_TLCORNER; | ||
2108 | if (!(val & (PIECE_TBORDER | PIECE_RBORDER)) && | ||
2109 | canon != dsf_canonify(dsf, i+1-w)) | ||
2110 | val |= PIECE_TRCORNER; | ||
2111 | if (!(val & (PIECE_BBORDER | PIECE_LBORDER)) && | ||
2112 | canon != dsf_canonify(dsf, i-1+w)) | ||
2113 | val |= PIECE_BLCORNER; | ||
2114 | if (!(val & (PIECE_BBORDER | PIECE_RBORDER)) && | ||
2115 | canon != dsf_canonify(dsf, i+1+w)) | ||
2116 | val |= PIECE_BRCORNER; | ||
2117 | return val; | ||
2118 | } | ||
2119 | |||
2120 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2121 | const game_state *oldstate, const game_state *state, | ||
2122 | int dir, const game_ui *ui, | ||
2123 | float animtime, float flashtime) | ||
2124 | { | ||
2125 | int w = state->w, h = state->h, wh = w*h; | ||
2126 | unsigned char *board; | ||
2127 | int *dsf; | ||
2128 | int x, y, mainanchor, mainpos, dragpos, solvepos, solvesrc, solvedst; | ||
2129 | |||
2130 | if (!ds->started) { | ||
2131 | /* | ||
2132 | * The initial contents of the window are not guaranteed | ||
2133 | * and can vary with front ends. To be on the safe side, | ||
2134 | * all games should start by drawing a big | ||
2135 | * background-colour rectangle covering the whole window. | ||
2136 | */ | ||
2137 | draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND); | ||
2138 | ds->started = TRUE; | ||
2139 | } | ||
2140 | |||
2141 | /* | ||
2142 | * Construct the board we'll be displaying (which may be | ||
2143 | * different from the one in state if ui describes a drag in | ||
2144 | * progress). | ||
2145 | */ | ||
2146 | board = snewn(wh, unsigned char); | ||
2147 | memcpy(board, state->board, wh); | ||
2148 | if (ui->dragging) { | ||
2149 | int mpret = move_piece(w, h, state->board, board, | ||
2150 | state->imm->forcefield, | ||
2151 | ui->drag_anchor, ui->drag_currpos); | ||
2152 | assert(mpret); | ||
2153 | } | ||
2154 | |||
2155 | if (state->soln) { | ||
2156 | solvesrc = state->soln->moves[state->soln_index*2]; | ||
2157 | solvedst = state->soln->moves[state->soln_index*2+1]; | ||
2158 | if (solvesrc == state->lastmoved_pos) | ||
2159 | solvesrc = state->lastmoved; | ||
2160 | if (solvesrc == ui->drag_anchor) | ||
2161 | solvesrc = ui->drag_currpos; | ||
2162 | } else | ||
2163 | solvesrc = solvedst = -1; | ||
2164 | |||
2165 | /* | ||
2166 | * Build a dsf out of that board, so we can conveniently tell | ||
2167 | * which edges are connected and which aren't. | ||
2168 | */ | ||
2169 | dsf = snew_dsf(wh); | ||
2170 | mainanchor = -1; | ||
2171 | for (y = 0; y < h; y++) | ||
2172 | for (x = 0; x < w; x++) { | ||
2173 | int i = y*w+x; | ||
2174 | |||
2175 | if (ISDIST(board[i])) | ||
2176 | dsf_merge(dsf, i, i - board[i]); | ||
2177 | if (board[i] == MAINANCHOR) | ||
2178 | mainanchor = i; | ||
2179 | if (board[i] == WALL) { | ||
2180 | if (x > 0 && board[i-1] == WALL) | ||
2181 | dsf_merge(dsf, i, i-1); | ||
2182 | if (y > 0 && board[i-w] == WALL) | ||
2183 | dsf_merge(dsf, i, i-w); | ||
2184 | } | ||
2185 | } | ||
2186 | assert(mainanchor >= 0); | ||
2187 | mainpos = dsf_canonify(dsf, mainanchor); | ||
2188 | dragpos = ui->drag_currpos > 0 ? dsf_canonify(dsf, ui->drag_currpos) : -1; | ||
2189 | solvepos = solvesrc >= 0 ? dsf_canonify(dsf, solvesrc) : -1; | ||
2190 | |||
2191 | /* | ||
2192 | * Now we can construct the data about what we want to draw. | ||
2193 | */ | ||
2194 | for (y = 0; y < h; y++) | ||
2195 | for (x = 0; x < w; x++) { | ||
2196 | int i = y*w+x; | ||
2197 | int j; | ||
2198 | unsigned long val; | ||
2199 | int canon; | ||
2200 | |||
2201 | /* | ||
2202 | * See if this square is part of the target area. | ||
2203 | */ | ||
2204 | j = i + mainanchor - (state->ty * w + state->tx); | ||
2205 | while (j >= 0 && j < wh && ISDIST(board[j])) | ||
2206 | j -= board[j]; | ||
2207 | if (j == mainanchor) | ||
2208 | val = BG_TARGET; | ||
2209 | else | ||
2210 | val = BG_NORMAL; | ||
2211 | |||
2212 | if (state->imm->forcefield[i]) | ||
2213 | val |= BG_FORCEFIELD; | ||
2214 | |||
2215 | if (flashtime > 0) { | ||
2216 | int flashtype = (int)(flashtime / FLASH_INTERVAL) & 1; | ||
2217 | val |= (flashtype ? FLASH_LOW : FLASH_HIGH); | ||
2218 | } | ||
2219 | |||
2220 | if (board[i] != EMPTY) { | ||
2221 | canon = dsf_canonify(dsf, i); | ||
2222 | |||
2223 | if (board[i] == WALL) | ||
2224 | val |= FG_WALL; | ||
2225 | else if (canon == mainpos) | ||
2226 | val |= FG_MAIN; | ||
2227 | else | ||
2228 | val |= FG_NORMAL; | ||
2229 | if (canon == dragpos) | ||
2230 | val |= FG_DRAGGING; | ||
2231 | if (canon == solvepos) | ||
2232 | val |= FG_SOLVEPIECE; | ||
2233 | |||
2234 | /* | ||
2235 | * Now look around to see if other squares | ||
2236 | * belonging to the same block are adjacent to us. | ||
2237 | */ | ||
2238 | val |= find_piecepart(w, h, dsf, x, y) << FG_MAINPIECESH; | ||
2239 | } | ||
2240 | |||
2241 | /* | ||
2242 | * If we're in the middle of showing a solution, | ||
2243 | * display a shadow piece for the target of the | ||
2244 | * current move. | ||
2245 | */ | ||
2246 | if (solvepos >= 0) { | ||
2247 | int si = i - solvedst + solvesrc; | ||
2248 | if (si >= 0 && si < wh && dsf_canonify(dsf, si) == solvepos) { | ||
2249 | val |= find_piecepart(w, h, dsf, | ||
2250 | si % w, si / w) << FG_SHADOWSH; | ||
2251 | val |= FG_SHADOW; | ||
2252 | } | ||
2253 | } | ||
2254 | |||
2255 | if (val != ds->grid[i]) { | ||
2256 | draw_tile(dr, ds, x, y, val); | ||
2257 | ds->grid[i] = val; | ||
2258 | } | ||
2259 | } | ||
2260 | |||
2261 | /* | ||
2262 | * Update the status bar. | ||
2263 | */ | ||
2264 | { | ||
2265 | char statusbuf[256]; | ||
2266 | |||
2267 | sprintf(statusbuf, "%sMoves: %d", | ||
2268 | (state->completed >= 0 ? | ||
2269 | (state->cheated ? "Auto-solved. " : "COMPLETED! ") : | ||
2270 | (state->cheated ? "Auto-solver used. " : "")), | ||
2271 | (state->completed >= 0 ? state->completed : state->movecount)); | ||
2272 | if (state->minmoves >= 0) | ||
2273 | sprintf(statusbuf+strlen(statusbuf), " (min %d)", | ||
2274 | state->minmoves); | ||
2275 | |||
2276 | status_bar(dr, statusbuf); | ||
2277 | } | ||
2278 | |||
2279 | sfree(dsf); | ||
2280 | sfree(board); | ||
2281 | } | ||
2282 | |||
2283 | static float game_anim_length(const game_state *oldstate, | ||
2284 | const game_state *newstate, int dir, game_ui *ui) | ||
2285 | { | ||
2286 | return 0.0F; | ||
2287 | } | ||
2288 | |||
2289 | static float game_flash_length(const game_state *oldstate, | ||
2290 | const game_state *newstate, int dir, game_ui *ui) | ||
2291 | { | ||
2292 | if (oldstate->completed < 0 && newstate->completed >= 0) | ||
2293 | return FLASH_TIME; | ||
2294 | |||
2295 | return 0.0F; | ||
2296 | } | ||
2297 | |||
2298 | static int game_status(const game_state *state) | ||
2299 | { | ||
2300 | return state->completed ? +1 : 0; | ||
2301 | } | ||
2302 | |||
2303 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
2304 | { | ||
2305 | return TRUE; | ||
2306 | } | ||
2307 | |||
2308 | static void game_print_size(const game_params *params, float *x, float *y) | ||
2309 | { | ||
2310 | } | ||
2311 | |||
2312 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
2313 | { | ||
2314 | } | ||
2315 | |||
2316 | #ifdef COMBINED | ||
2317 | #define thegame slide | ||
2318 | #endif | ||
2319 | |||
2320 | const struct game thegame = { | ||
2321 | "Slide", NULL, NULL, | ||
2322 | default_params, | ||
2323 | game_fetch_preset, | ||
2324 | decode_params, | ||
2325 | encode_params, | ||
2326 | free_params, | ||
2327 | dup_params, | ||
2328 | TRUE, game_configure, custom_params, | ||
2329 | validate_params, | ||
2330 | new_game_desc, | ||
2331 | validate_desc, | ||
2332 | new_game, | ||
2333 | dup_game, | ||
2334 | free_game, | ||
2335 | TRUE, solve_game, | ||
2336 | TRUE, game_can_format_as_text_now, game_text_format, | ||
2337 | new_ui, | ||
2338 | free_ui, | ||
2339 | encode_ui, | ||
2340 | decode_ui, | ||
2341 | game_changed_state, | ||
2342 | interpret_move, | ||
2343 | execute_move, | ||
2344 | PREFERRED_TILESIZE, game_compute_size, game_set_size, | ||
2345 | game_colours, | ||
2346 | game_new_drawstate, | ||
2347 | game_free_drawstate, | ||
2348 | game_redraw, | ||
2349 | game_anim_length, | ||
2350 | game_flash_length, | ||
2351 | game_status, | ||
2352 | FALSE, FALSE, game_print_size, game_print, | ||
2353 | TRUE, /* wants_statusbar */ | ||
2354 | FALSE, game_timing_state, | ||
2355 | 0, /* flags */ | ||
2356 | }; | ||
2357 | |||
2358 | #ifdef STANDALONE_SOLVER | ||
2359 | |||
2360 | #include <stdarg.h> | ||
2361 | |||
2362 | int main(int argc, char **argv) | ||
2363 | { | ||
2364 | game_params *p; | ||
2365 | game_state *s; | ||
2366 | char *id = NULL, *desc, *err; | ||
2367 | int count = FALSE; | ||
2368 | int ret; | ||
2369 | int *moves; | ||
2370 | |||
2371 | while (--argc > 0) { | ||
2372 | char *p = *++argv; | ||
2373 | /* | ||
2374 | if (!strcmp(p, "-v")) { | ||
2375 | verbose = TRUE; | ||
2376 | } else | ||
2377 | */ | ||
2378 | if (!strcmp(p, "-c")) { | ||
2379 | count = TRUE; | ||
2380 | } else if (*p == '-') { | ||
2381 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2382 | return 1; | ||
2383 | } else { | ||
2384 | id = p; | ||
2385 | } | ||
2386 | } | ||
2387 | |||
2388 | if (!id) { | ||
2389 | fprintf(stderr, "usage: %s [-c | -v] <game_id>\n", argv[0]); | ||
2390 | return 1; | ||
2391 | } | ||
2392 | |||
2393 | desc = strchr(id, ':'); | ||
2394 | if (!desc) { | ||
2395 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
2396 | return 1; | ||
2397 | } | ||
2398 | *desc++ = '\0'; | ||
2399 | |||
2400 | p = default_params(); | ||
2401 | decode_params(p, id); | ||
2402 | err = validate_desc(p, desc); | ||
2403 | if (err) { | ||
2404 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
2405 | return 1; | ||
2406 | } | ||
2407 | s = new_game(NULL, p, desc); | ||
2408 | |||
2409 | ret = solve_board(s->w, s->h, s->board, s->imm->forcefield, | ||
2410 | s->tx, s->ty, -1, &moves); | ||
2411 | if (ret < 0) { | ||
2412 | printf("No solution found\n"); | ||
2413 | } else { | ||
2414 | int index = 0; | ||
2415 | if (count) { | ||
2416 | printf("%d moves required\n", ret); | ||
2417 | return 0; | ||
2418 | } | ||
2419 | while (1) { | ||
2420 | int moveret; | ||
2421 | char *text = board_text_format(s->w, s->h, s->board, | ||
2422 | s->imm->forcefield); | ||
2423 | game_state *s2; | ||
2424 | |||
2425 | printf("position %d:\n%s", index, text); | ||
2426 | |||
2427 | if (index >= ret) | ||
2428 | break; | ||
2429 | |||
2430 | s2 = dup_game(s); | ||
2431 | moveret = move_piece(s->w, s->h, s->board, | ||
2432 | s2->board, s->imm->forcefield, | ||
2433 | moves[index*2], moves[index*2+1]); | ||
2434 | assert(moveret); | ||
2435 | |||
2436 | free_game(s); | ||
2437 | s = s2; | ||
2438 | index++; | ||
2439 | } | ||
2440 | } | ||
2441 | |||
2442 | return 0; | ||
2443 | } | ||
2444 | |||
2445 | #endif | ||