diff options
Diffstat (limited to 'apps/plugins/puzzles/src/unfinished/sokoban.c')
-rw-r--r-- | apps/plugins/puzzles/src/unfinished/sokoban.c | 1476 |
1 files changed, 1476 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/unfinished/sokoban.c b/apps/plugins/puzzles/src/unfinished/sokoban.c new file mode 100644 index 0000000000..1f3c688af1 --- /dev/null +++ b/apps/plugins/puzzles/src/unfinished/sokoban.c | |||
@@ -0,0 +1,1476 @@ | |||
1 | /* | ||
2 | * sokoban.c: An implementation of the well-known Sokoban barrel- | ||
3 | * pushing game. Random generation is too simplistic to be | ||
4 | * credible, but the rest of the gameplay works well enough to use | ||
5 | * it with hand-written level descriptions. | ||
6 | */ | ||
7 | |||
8 | /* | ||
9 | * TODO: | ||
10 | * | ||
11 | * - I think it would be better to ditch the `prev' array, and | ||
12 | * instead make the `dist' array strictly monotonic (by having | ||
13 | * each distance be something like I*A+S, where A is the grid | ||
14 | * area, I the number of INITIAL squares trampled on, and S the | ||
15 | * number of harmless spaces moved through). This would permit | ||
16 | * the path-tracing when a pull is actually made to choose | ||
17 | * randomly from all the possible shortest routes, which would | ||
18 | * be superior in terms of eliminating directional bias. | ||
19 | * + So when tracing the path back to the current px,py, we | ||
20 | * look at all four adjacent squares, find the minimum | ||
21 | * distance, check that it's _strictly smaller_ than that of | ||
22 | * the current square, and restrict our choice to precisely | ||
23 | * those squares with that minimum distance. | ||
24 | * + The other place `prev' is currently used is in the check | ||
25 | * for consistency of a pull. We would have to replace the | ||
26 | * check for whether prev[ny*w+nx]==oy*w+ox with a check that | ||
27 | * made sure there was at least one adjacent square with a | ||
28 | * smaller distance which _wasn't_ oy*w+ox. Then when we did | ||
29 | * the path-tracing we'd also have to take this special case | ||
30 | * into account. | ||
31 | * | ||
32 | * - More discriminating choice of pull. (Snigger.) | ||
33 | * + favour putting targets in clumps | ||
34 | * + try to shoot for a reasonably consistent number of barrels | ||
35 | * (adjust willingness to generate a new barrel depending on | ||
36 | * how many are already present) | ||
37 | * + adjust willingness to break new ground depending on how | ||
38 | * much is already broken | ||
39 | * | ||
40 | * - generation time parameters: | ||
41 | * + enable NetHack mode (and find a better place for the hole) | ||
42 | * + decide how many of the remaining Is should be walls | ||
43 | * | ||
44 | * - at the end of generation, randomly position the starting | ||
45 | * player coordinates, probably by (somehow) reusing the same | ||
46 | * bfs currently inside the loop. | ||
47 | * | ||
48 | * - possible backtracking? | ||
49 | * | ||
50 | * - IWBNI we could spot completely unreachable bits of level at | ||
51 | * the outside, and not bother drawing grid lines for them. The | ||
52 | * NH levels currently look a bit weird with grid lines on the | ||
53 | * outside of the boundary. | ||
54 | */ | ||
55 | |||
56 | #include <stdio.h> | ||
57 | #include <stdlib.h> | ||
58 | #include <string.h> | ||
59 | #include <assert.h> | ||
60 | #include <ctype.h> | ||
61 | #ifdef NO_TGMATH_H | ||
62 | # include <math.h> | ||
63 | #else | ||
64 | # include <tgmath.h> | ||
65 | #endif | ||
66 | |||
67 | #include "puzzles.h" | ||
68 | |||
69 | /* | ||
70 | * Various subsets of these constants are used during game | ||
71 | * generation, game play, game IDs and the game_drawstate. | ||
72 | */ | ||
73 | #define INITIAL 'i' /* used only in game generation */ | ||
74 | #define SPACE 's' | ||
75 | #define WALL 'w' | ||
76 | #define PIT 'p' | ||
77 | #define DEEP_PIT 'd' | ||
78 | #define TARGET 't' | ||
79 | #define BARREL 'b' | ||
80 | #define BARRELTARGET 'f' /* target is 'f'illed */ | ||
81 | #define PLAYER 'u' /* yo'u'; used in game IDs */ | ||
82 | #define PLAYERTARGET 'v' /* bad letter: v is to u as t is to s */ | ||
83 | #define INVALID '!' /* used in drawstate to force redraw */ | ||
84 | /* | ||
85 | * We also support the use of any capital letter as a barrel, which | ||
86 | * will be displayed with that letter as a label. (This facilitates | ||
87 | * people distributing annotated game IDs for particular Sokoban | ||
88 | * levels, so they can accompany them with verbal instructions | ||
89 | * about pushing particular barrels in particular ways.) Therefore, | ||
90 | * to find out whether something is a barrel, we need a test | ||
91 | * function which does a bit more than just comparing to BARREL. | ||
92 | * | ||
93 | * When resting on target squares, capital-letter barrels are | ||
94 | * replaced with their control-character value (A -> ^A). | ||
95 | */ | ||
96 | #define IS_PLAYER(c) ( (c)==PLAYER || (c)==PLAYERTARGET ) | ||
97 | #define IS_BARREL(c) ( (c)==BARREL || (c)==BARRELTARGET || \ | ||
98 | ((c)>='A' && (c)<='Z') || ((c)>=1 && (c)<=26) ) | ||
99 | #define IS_ON_TARGET(c) ( (c)==TARGET || (c)==BARRELTARGET || \ | ||
100 | (c)==PLAYERTARGET || ((c)>=1 && (c)<=26) ) | ||
101 | #define TARGETISE(b) ( (b)==BARREL ? BARRELTARGET : (b)-('A'-1) ) | ||
102 | #define DETARGETISE(b) ( (b)==BARRELTARGET ? BARREL : (b)+('A'-1) ) | ||
103 | #define BARREL_LABEL(b) ( (b)>='A'&&(b)<='Z' ? (b) : \ | ||
104 | (b)>=1 && (b)<=26 ? (b)+('A'-1) : 0 ) | ||
105 | |||
106 | #define DX(d) (d == 0 ? -1 : d == 2 ? +1 : 0) | ||
107 | #define DY(d) (d == 1 ? -1 : d == 3 ? +1 : 0) | ||
108 | |||
109 | #define FLASH_LENGTH 0.3F | ||
110 | |||
111 | enum { | ||
112 | COL_BACKGROUND, | ||
113 | COL_TARGET, | ||
114 | COL_PIT, | ||
115 | COL_DEEP_PIT, | ||
116 | COL_BARREL, | ||
117 | COL_PLAYER, | ||
118 | COL_TEXT, | ||
119 | COL_GRID, | ||
120 | COL_OUTLINE, | ||
121 | COL_HIGHLIGHT, | ||
122 | COL_LOWLIGHT, | ||
123 | COL_WALL, | ||
124 | NCOLOURS | ||
125 | }; | ||
126 | |||
127 | struct game_params { | ||
128 | int w, h; | ||
129 | /* | ||
130 | * FIXME: a parameter involving degree of filling in? | ||
131 | */ | ||
132 | }; | ||
133 | |||
134 | struct game_state { | ||
135 | game_params p; | ||
136 | unsigned char *grid; | ||
137 | int px, py; | ||
138 | bool completed; | ||
139 | }; | ||
140 | |||
141 | static game_params *default_params(void) | ||
142 | { | ||
143 | game_params *ret = snew(game_params); | ||
144 | |||
145 | ret->w = 12; | ||
146 | ret->h = 10; | ||
147 | |||
148 | return ret; | ||
149 | } | ||
150 | |||
151 | static void free_params(game_params *params) | ||
152 | { | ||
153 | sfree(params); | ||
154 | } | ||
155 | |||
156 | static game_params *dup_params(const game_params *params) | ||
157 | { | ||
158 | game_params *ret = snew(game_params); | ||
159 | *ret = *params; /* structure copy */ | ||
160 | return ret; | ||
161 | } | ||
162 | |||
163 | static const struct game_params sokoban_presets[] = { | ||
164 | { 12, 10 }, | ||
165 | { 16, 12 }, | ||
166 | { 20, 16 }, | ||
167 | }; | ||
168 | |||
169 | static bool game_fetch_preset(int i, char **name, game_params **params) | ||
170 | { | ||
171 | game_params p, *ret; | ||
172 | char *retname; | ||
173 | char namebuf[80]; | ||
174 | |||
175 | if (i < 0 || i >= lenof(sokoban_presets)) | ||
176 | return false; | ||
177 | |||
178 | p = sokoban_presets[i]; | ||
179 | ret = dup_params(&p); | ||
180 | sprintf(namebuf, "%dx%d", ret->w, ret->h); | ||
181 | retname = dupstr(namebuf); | ||
182 | |||
183 | *params = ret; | ||
184 | *name = retname; | ||
185 | return true; | ||
186 | } | ||
187 | |||
188 | static void decode_params(game_params *params, char const *string) | ||
189 | { | ||
190 | params->w = params->h = atoi(string); | ||
191 | while (*string && isdigit((unsigned char)*string)) string++; | ||
192 | if (*string == 'x') { | ||
193 | string++; | ||
194 | params->h = atoi(string); | ||
195 | } | ||
196 | } | ||
197 | |||
198 | static char *encode_params(const game_params *params, bool full) | ||
199 | { | ||
200 | char data[256]; | ||
201 | |||
202 | sprintf(data, "%dx%d", params->w, params->h); | ||
203 | |||
204 | return dupstr(data); | ||
205 | } | ||
206 | |||
207 | static config_item *game_configure(const game_params *params) | ||
208 | { | ||
209 | config_item *ret; | ||
210 | char buf[80]; | ||
211 | |||
212 | ret = snewn(3, config_item); | ||
213 | |||
214 | ret[0].name = "Width"; | ||
215 | ret[0].type = C_STRING; | ||
216 | sprintf(buf, "%d", params->w); | ||
217 | ret[0].u.string.sval = dupstr(buf); | ||
218 | |||
219 | ret[1].name = "Height"; | ||
220 | ret[1].type = C_STRING; | ||
221 | sprintf(buf, "%d", params->h); | ||
222 | ret[1].u.string.sval = dupstr(buf); | ||
223 | |||
224 | ret[2].name = NULL; | ||
225 | ret[2].type = C_END; | ||
226 | |||
227 | return ret; | ||
228 | } | ||
229 | |||
230 | static game_params *custom_params(const config_item *cfg) | ||
231 | { | ||
232 | game_params *ret = snew(game_params); | ||
233 | |||
234 | ret->w = atoi(cfg[0].u.string.sval); | ||
235 | ret->h = atoi(cfg[1].u.string.sval); | ||
236 | |||
237 | return ret; | ||
238 | } | ||
239 | |||
240 | static const char *validate_params(const game_params *params, bool full) | ||
241 | { | ||
242 | if (params->w < 4 || params->h < 4) | ||
243 | return "Width and height must both be at least 4"; | ||
244 | |||
245 | return NULL; | ||
246 | } | ||
247 | |||
248 | /* ---------------------------------------------------------------------- | ||
249 | * Game generation mechanism. | ||
250 | * | ||
251 | * To generate a Sokoban level, we begin with a completely blank | ||
252 | * grid and make valid inverse moves. Grid squares can be in a | ||
253 | * number of states. The states are: | ||
254 | * | ||
255 | * - INITIAL: this square has not as yet been touched by any | ||
256 | * inverse move, which essentially means we haven't decided what | ||
257 | * it is yet. | ||
258 | * | ||
259 | * - SPACE: this square is a space. | ||
260 | * | ||
261 | * - TARGET: this square is a space which is also the target for a | ||
262 | * barrel. | ||
263 | * | ||
264 | * - BARREL: this square contains a barrel. | ||
265 | * | ||
266 | * - BARRELTARGET: this square contains a barrel _on_ a target. | ||
267 | * | ||
268 | * - WALL: this square is a wall. | ||
269 | * | ||
270 | * - PLAYER: this square contains the player. | ||
271 | * | ||
272 | * - PLAYERTARGET: this square contains the player on a target. | ||
273 | * | ||
274 | * We begin with every square of the in state INITIAL, apart from a | ||
275 | * solid ring of WALLs around the edge. We randomly position the | ||
276 | * PLAYER somewhere. Thereafter our valid moves are: | ||
277 | * | ||
278 | * - to move the PLAYER in one direction _pulling_ a barrel after | ||
279 | * us. For this to work, we must have SPACE or INITIAL in the | ||
280 | * direction we're moving, and BARREL or BARRELTARGET in the | ||
281 | * direction we're moving away from. We leave SPACE or TARGET | ||
282 | * respectively in the vacated square. | ||
283 | * | ||
284 | * - to create a new barrel by transforming an INITIAL square into | ||
285 | * BARRELTARGET. | ||
286 | * | ||
287 | * - to move the PLAYER freely through SPACE and TARGET squares, | ||
288 | * leaving SPACE or TARGET where it started. | ||
289 | * | ||
290 | * - to move the player through INITIAL squares, carving a tunnel | ||
291 | * of SPACEs as it goes. | ||
292 | * | ||
293 | * We try to avoid destroying INITIAL squares wherever possible (if | ||
294 | * there's a path to where we want to be using only SPACE, then we | ||
295 | * should always use that). At the end of generation, every square | ||
296 | * still in state INITIAL is one which was not required at any | ||
297 | * point during generation, which means we can randomly choose | ||
298 | * whether to make it SPACE or WALL. | ||
299 | * | ||
300 | * It's unclear as yet what the right strategy for wall placement | ||
301 | * should be. Too few WALLs will yield many alternative solutions | ||
302 | * to the puzzle, whereas too many might rule out so many | ||
303 | * possibilities that the intended solution becomes obvious. | ||
304 | */ | ||
305 | |||
306 | static void sokoban_generate(int w, int h, unsigned char *grid, int moves, | ||
307 | bool nethack, random_state *rs) | ||
308 | { | ||
309 | struct pull { | ||
310 | int ox, oy, nx, ny, score; | ||
311 | }; | ||
312 | |||
313 | struct pull *pulls; | ||
314 | int *dist, *prev, *heap; | ||
315 | int x, y, px, py, i, j, d, heapsize, npulls; | ||
316 | |||
317 | pulls = snewn(w * h * 4, struct pull); | ||
318 | dist = snewn(w * h, int); | ||
319 | prev = snewn(w * h, int); | ||
320 | heap = snewn(w * h, int); | ||
321 | |||
322 | /* | ||
323 | * Configure the initial grid. | ||
324 | */ | ||
325 | for (y = 0; y < h; y++) | ||
326 | for (x = 0; x < w; x++) | ||
327 | grid[y*w+x] = (x == 0 || y == 0 || x == w-1 || y == h-1 ? | ||
328 | WALL : INITIAL); | ||
329 | if (nethack) | ||
330 | grid[1] = DEEP_PIT; | ||
331 | |||
332 | /* | ||
333 | * Place the player. | ||
334 | */ | ||
335 | i = random_upto(rs, (w-2) * (h-2)); | ||
336 | x = 1 + i % (w-2); | ||
337 | y = 1 + i / (w-2); | ||
338 | grid[y*w+x] = SPACE; | ||
339 | px = x; | ||
340 | py = y; | ||
341 | |||
342 | /* | ||
343 | * Now loop around making random inverse Sokoban moves. In this | ||
344 | * loop we aim to make one actual barrel-pull per iteration, | ||
345 | * plus as many free moves as are necessary to get into | ||
346 | * position for that pull. | ||
347 | */ | ||
348 | while (moves-- >= 0) { | ||
349 | /* | ||
350 | * First enumerate all the viable barrel-pulls we can | ||
351 | * possibly make, counting two pulls of the same barrel in | ||
352 | * different directions as different. We also include pulls | ||
353 | * we can perform by creating a new barrel. Each pull is | ||
354 | * marked with the amount of violence it would have to do | ||
355 | * to the grid. | ||
356 | */ | ||
357 | npulls = 0; | ||
358 | for (y = 0; y < h; y++) | ||
359 | for (x = 0; x < w; x++) | ||
360 | for (d = 0; d < 4; d++) { | ||
361 | int dx = DX(d); | ||
362 | int dy = DY(d); | ||
363 | int nx = x + dx, ny = y + dy; | ||
364 | int npx = nx + dx, npy = ny + dy; | ||
365 | int score = 0; | ||
366 | |||
367 | /* | ||
368 | * The candidate move is to put the player at | ||
369 | * (nx,ny), and move him to (npx,npy), pulling | ||
370 | * a barrel at (x,y) to (nx,ny). So first we | ||
371 | * must check that all those squares are within | ||
372 | * the boundaries of the grid. For this it is | ||
373 | * sufficient to check npx,npy. | ||
374 | */ | ||
375 | if (npx < 0 || npx >= w || npy < 0 || npy >= h) | ||
376 | continue; | ||
377 | |||
378 | /* | ||
379 | * (x,y) must either be a barrel, or a square | ||
380 | * which we can convert into a barrel. | ||
381 | */ | ||
382 | switch (grid[y*w+x]) { | ||
383 | case BARREL: case BARRELTARGET: | ||
384 | break; | ||
385 | case INITIAL: | ||
386 | if (nethack) | ||
387 | continue; | ||
388 | score += 10 /* new_barrel_score */; | ||
389 | break; | ||
390 | case DEEP_PIT: | ||
391 | if (!nethack) | ||
392 | continue; | ||
393 | break; | ||
394 | default: | ||
395 | continue; | ||
396 | } | ||
397 | |||
398 | /* | ||
399 | * (nx,ny) must either be a space, or a square | ||
400 | * which we can convert into a space. | ||
401 | */ | ||
402 | switch (grid[ny*w+nx]) { | ||
403 | case SPACE: case TARGET: | ||
404 | break; | ||
405 | case INITIAL: | ||
406 | score += 3 /* new_space_score */; | ||
407 | break; | ||
408 | default: | ||
409 | continue; | ||
410 | } | ||
411 | |||
412 | /* | ||
413 | * (npx,npy) must also either be a space, or a | ||
414 | * square which we can convert into a space. | ||
415 | */ | ||
416 | switch (grid[npy*w+npx]) { | ||
417 | case SPACE: case TARGET: | ||
418 | break; | ||
419 | case INITIAL: | ||
420 | score += 3 /* new_space_score */; | ||
421 | break; | ||
422 | default: | ||
423 | continue; | ||
424 | } | ||
425 | |||
426 | /* | ||
427 | * That's sufficient to tag this as a possible | ||
428 | * pull right now. We still don't know if we | ||
429 | * can reach the required player position, but | ||
430 | * that's a job for the subsequent BFS phase to | ||
431 | * tell us. | ||
432 | */ | ||
433 | pulls[npulls].ox = x; | ||
434 | pulls[npulls].oy = y; | ||
435 | pulls[npulls].nx = nx; | ||
436 | pulls[npulls].ny = ny; | ||
437 | pulls[npulls].score = score; | ||
438 | #ifdef GENERATION_DIAGNOSTICS | ||
439 | printf("found potential pull: (%d,%d)-(%d,%d) cost %d\n", | ||
440 | pulls[npulls].ox, pulls[npulls].oy, | ||
441 | pulls[npulls].nx, pulls[npulls].ny, | ||
442 | pulls[npulls].score); | ||
443 | #endif | ||
444 | npulls++; | ||
445 | } | ||
446 | #ifdef GENERATION_DIAGNOSTICS | ||
447 | printf("found %d potential pulls\n", npulls); | ||
448 | #endif | ||
449 | |||
450 | /* | ||
451 | * If there are no pulls available at all, we give up. | ||
452 | * | ||
453 | * (FIXME: or perhaps backtrack?) | ||
454 | */ | ||
455 | if (npulls == 0) | ||
456 | break; | ||
457 | |||
458 | /* | ||
459 | * Now we do a BFS from our current position, to find all | ||
460 | * the squares we can get the player into. | ||
461 | * | ||
462 | * This BFS is unusually tricky. We want to give a positive | ||
463 | * distance only to squares which we have to carve through | ||
464 | * INITIALs to get to, which means we can't just stick | ||
465 | * every square we reach on the end of our to-do list. | ||
466 | * Instead, we must maintain our list as a proper priority | ||
467 | * queue. | ||
468 | */ | ||
469 | for (i = 0; i < w*h; i++) | ||
470 | dist[i] = prev[i] = -1; | ||
471 | |||
472 | heap[0] = py*w+px; | ||
473 | heapsize = 1; | ||
474 | dist[py*w+px] = 0; | ||
475 | |||
476 | #define PARENT(n) ( ((n)-1)/2 ) | ||
477 | #define LCHILD(n) ( 2*(n)+1 ) | ||
478 | #define RCHILD(n) ( 2*(n)+2 ) | ||
479 | #define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0) | ||
480 | |||
481 | while (heapsize > 0) { | ||
482 | /* | ||
483 | * Pull the smallest element off the heap: it's at | ||
484 | * position 0. Move the arbitrary element from the very | ||
485 | * end of the heap into position 0. | ||
486 | */ | ||
487 | y = heap[0] / w; | ||
488 | x = heap[0] % w; | ||
489 | |||
490 | heapsize--; | ||
491 | heap[0] = heap[heapsize]; | ||
492 | |||
493 | /* | ||
494 | * Now repeatedly move that arbitrary element down the | ||
495 | * heap by swapping it with the more suitable of its | ||
496 | * children. | ||
497 | */ | ||
498 | i = 0; | ||
499 | while (1) { | ||
500 | int lc, rc; | ||
501 | |||
502 | lc = LCHILD(i); | ||
503 | rc = RCHILD(i); | ||
504 | |||
505 | if (lc >= heapsize) | ||
506 | break; /* we've hit bottom */ | ||
507 | |||
508 | if (rc >= heapsize) { | ||
509 | /* | ||
510 | * Special case: there is only one child to | ||
511 | * check. | ||
512 | */ | ||
513 | if (dist[heap[i]] > dist[heap[lc]]) | ||
514 | SWAP(heap[i], heap[lc]); | ||
515 | |||
516 | /* _Now_ we've hit bottom. */ | ||
517 | break; | ||
518 | } else { | ||
519 | /* | ||
520 | * The common case: there are two children and | ||
521 | * we must check them both. | ||
522 | */ | ||
523 | if (dist[heap[i]] > dist[heap[lc]] || | ||
524 | dist[heap[i]] > dist[heap[rc]]) { | ||
525 | /* | ||
526 | * Pick the more appropriate child to swap with | ||
527 | * (i.e. the one which would want to be the | ||
528 | * parent if one were above the other - as one | ||
529 | * is about to be). | ||
530 | */ | ||
531 | if (dist[heap[lc]] > dist[heap[rc]]) { | ||
532 | SWAP(heap[i], heap[rc]); | ||
533 | i = rc; | ||
534 | } else { | ||
535 | SWAP(heap[i], heap[lc]); | ||
536 | i = lc; | ||
537 | } | ||
538 | } else { | ||
539 | /* This element is in the right place; we're done. */ | ||
540 | break; | ||
541 | } | ||
542 | } | ||
543 | } | ||
544 | |||
545 | /* | ||
546 | * OK, that's given us (x,y) for this phase of the | ||
547 | * search. Now try all directions from here. | ||
548 | */ | ||
549 | |||
550 | for (d = 0; d < 4; d++) { | ||
551 | int dx = DX(d); | ||
552 | int dy = DY(d); | ||
553 | int nx = x + dx, ny = y + dy; | ||
554 | if (nx < 0 || nx >= w || ny < 0 || ny >= h) | ||
555 | continue; | ||
556 | if (grid[ny*w+nx] != SPACE && grid[ny*w+nx] != TARGET && | ||
557 | grid[ny*w+nx] != INITIAL) | ||
558 | continue; | ||
559 | if (dist[ny*w+nx] == -1) { | ||
560 | dist[ny*w+nx] = dist[y*w+x] + (grid[ny*w+nx] == INITIAL); | ||
561 | prev[ny*w+nx] = y*w+x; | ||
562 | |||
563 | /* | ||
564 | * Now insert ny*w+nx at the end of the heap, | ||
565 | * and move it down to its appropriate resting | ||
566 | * place. | ||
567 | */ | ||
568 | i = heapsize; | ||
569 | heap[heapsize++] = ny*w+nx; | ||
570 | |||
571 | /* | ||
572 | * Swap element n with its parent repeatedly to | ||
573 | * preserve the heap property. | ||
574 | */ | ||
575 | |||
576 | while (i > 0) { | ||
577 | int p = PARENT(i); | ||
578 | |||
579 | if (dist[heap[p]] > dist[heap[i]]) { | ||
580 | SWAP(heap[p], heap[i]); | ||
581 | i = p; | ||
582 | } else | ||
583 | break; | ||
584 | } | ||
585 | } | ||
586 | } | ||
587 | } | ||
588 | |||
589 | #undef PARENT | ||
590 | #undef LCHILD | ||
591 | #undef RCHILD | ||
592 | #undef SWAP | ||
593 | |||
594 | #ifdef GENERATION_DIAGNOSTICS | ||
595 | printf("distance map:\n"); | ||
596 | for (i = 0; i < h; i++) { | ||
597 | for (j = 0; j < w; j++) { | ||
598 | int d = dist[i*w+j]; | ||
599 | int c; | ||
600 | if (d < 0) | ||
601 | c = '#'; | ||
602 | else if (d >= 36) | ||
603 | c = '!'; | ||
604 | else if (d >= 10) | ||
605 | c = 'A' - 10 + d; | ||
606 | else | ||
607 | c = '0' + d; | ||
608 | putchar(c); | ||
609 | } | ||
610 | putchar('\n'); | ||
611 | } | ||
612 | #endif | ||
613 | |||
614 | /* | ||
615 | * Now we can go back through the `pulls' array, adjusting | ||
616 | * the score for each pull depending on how hard it is to | ||
617 | * reach its starting point, and also throwing out any | ||
618 | * whose starting points are genuinely unreachable even | ||
619 | * with the possibility of carving through INITIAL squares. | ||
620 | */ | ||
621 | for (i = j = 0; i < npulls; i++) { | ||
622 | #ifdef GENERATION_DIAGNOSTICS | ||
623 | printf("potential pull (%d,%d)-(%d,%d)", | ||
624 | pulls[i].ox, pulls[i].oy, | ||
625 | pulls[i].nx, pulls[i].ny); | ||
626 | #endif | ||
627 | x = pulls[i].nx; | ||
628 | y = pulls[i].ny; | ||
629 | if (dist[y*w+x] < 0) { | ||
630 | #ifdef GENERATION_DIAGNOSTICS | ||
631 | printf(" unreachable\n"); | ||
632 | #endif | ||
633 | continue; /* this pull isn't feasible at all */ | ||
634 | } else { | ||
635 | /* | ||
636 | * Another nasty special case we have to check is | ||
637 | * whether the initial barrel location (ox,oy) is | ||
638 | * on the path used to reach the square. This can | ||
639 | * occur if that square is in state INITIAL: the | ||
640 | * pull is initially considered valid on the basis | ||
641 | * that the INITIAL can become BARRELTARGET, and | ||
642 | * it's also considered reachable on the basis that | ||
643 | * INITIAL can be turned into SPACE, but it can't | ||
644 | * be both at once. | ||
645 | * | ||
646 | * Fortunately, if (ox,oy) is on the path at all, | ||
647 | * it must be only one space from the end, so this | ||
648 | * is easy to spot and rule out. | ||
649 | */ | ||
650 | if (prev[y*w+x] == pulls[i].oy*w+pulls[i].ox) { | ||
651 | #ifdef GENERATION_DIAGNOSTICS | ||
652 | printf(" goes through itself\n"); | ||
653 | #endif | ||
654 | continue; /* this pull isn't feasible at all */ | ||
655 | } | ||
656 | pulls[j] = pulls[i]; /* structure copy */ | ||
657 | pulls[j].score += dist[y*w+x] * 3 /* new_space_score */; | ||
658 | #ifdef GENERATION_DIAGNOSTICS | ||
659 | printf(" reachable at distance %d (cost now %d)\n", | ||
660 | dist[y*w+x], pulls[j].score); | ||
661 | #endif | ||
662 | j++; | ||
663 | } | ||
664 | } | ||
665 | npulls = j; | ||
666 | |||
667 | /* | ||
668 | * Again, if there are no pulls available at all, we give | ||
669 | * up. | ||
670 | * | ||
671 | * (FIXME: or perhaps backtrack?) | ||
672 | */ | ||
673 | if (npulls == 0) | ||
674 | break; | ||
675 | |||
676 | /* | ||
677 | * Now choose which pull to make. On the one hand we should | ||
678 | * prefer pulls which do less damage to the INITIAL squares | ||
679 | * (thus, ones for which we can already get into position | ||
680 | * via existing SPACEs, and for which the barrel already | ||
681 | * exists and doesn't have to be invented); on the other, | ||
682 | * we want to avoid _always_ preferring such pulls, on the | ||
683 | * grounds that that will lead to levels without very much | ||
684 | * stuff in. | ||
685 | * | ||
686 | * When creating new barrels, we prefer creations which are | ||
687 | * next to existing TARGET squares. | ||
688 | * | ||
689 | * FIXME: for the moment I'll make this very simple indeed. | ||
690 | */ | ||
691 | i = random_upto(rs, npulls); | ||
692 | |||
693 | /* | ||
694 | * Actually make the pull, including carving a path to get | ||
695 | * to the site if necessary. | ||
696 | */ | ||
697 | x = pulls[i].nx; | ||
698 | y = pulls[i].ny; | ||
699 | while (prev[y*w+x] >= 0) { | ||
700 | int p; | ||
701 | |||
702 | if (grid[y*w+x] == INITIAL) | ||
703 | grid[y*w+x] = SPACE; | ||
704 | |||
705 | p = prev[y*w+x]; | ||
706 | y = p / w; | ||
707 | x = p % w; | ||
708 | } | ||
709 | px = 2*pulls[i].nx - pulls[i].ox; | ||
710 | py = 2*pulls[i].ny - pulls[i].oy; | ||
711 | if (grid[py*w+px] == INITIAL) | ||
712 | grid[py*w+px] = SPACE; | ||
713 | if (grid[pulls[i].ny*w+pulls[i].nx] == TARGET) | ||
714 | grid[pulls[i].ny*w+pulls[i].nx] = BARRELTARGET; | ||
715 | else | ||
716 | grid[pulls[i].ny*w+pulls[i].nx] = BARREL; | ||
717 | if (grid[pulls[i].oy*w+pulls[i].ox] == BARREL) | ||
718 | grid[pulls[i].oy*w+pulls[i].ox] = SPACE; | ||
719 | else if (grid[pulls[i].oy*w+pulls[i].ox] != DEEP_PIT) | ||
720 | grid[pulls[i].oy*w+pulls[i].ox] = TARGET; | ||
721 | } | ||
722 | |||
723 | sfree(heap); | ||
724 | sfree(prev); | ||
725 | sfree(dist); | ||
726 | sfree(pulls); | ||
727 | |||
728 | if (grid[py*w+px] == TARGET) | ||
729 | grid[py*w+px] = PLAYERTARGET; | ||
730 | else | ||
731 | grid[py*w+px] = PLAYER; | ||
732 | } | ||
733 | |||
734 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
735 | char **aux, bool interactive) | ||
736 | { | ||
737 | int w = params->w, h = params->h; | ||
738 | char *desc; | ||
739 | int desclen, descpos, descsize, prev, count; | ||
740 | unsigned char *grid; | ||
741 | int i, j; | ||
742 | |||
743 | /* | ||
744 | * FIXME: perhaps some more interesting means of choosing how | ||
745 | * many moves to try? | ||
746 | */ | ||
747 | grid = snewn(w*h, unsigned char); | ||
748 | sokoban_generate(w, h, grid, w*h, false, rs); | ||
749 | |||
750 | desclen = descpos = descsize = 0; | ||
751 | desc = NULL; | ||
752 | prev = -1; | ||
753 | count = 0; | ||
754 | for (i = 0; i < w*h; i++) { | ||
755 | if (descsize < desclen + 40) { | ||
756 | descsize = desclen + 100; | ||
757 | desc = sresize(desc, descsize, char); | ||
758 | desc[desclen] = '\0'; | ||
759 | } | ||
760 | switch (grid[i]) { | ||
761 | case INITIAL: | ||
762 | j = 'w'; /* FIXME: make some of these 's'? */ | ||
763 | break; | ||
764 | case SPACE: | ||
765 | j = 's'; | ||
766 | break; | ||
767 | case WALL: | ||
768 | j = 'w'; | ||
769 | break; | ||
770 | case TARGET: | ||
771 | j = 't'; | ||
772 | break; | ||
773 | case BARREL: | ||
774 | j = 'b'; | ||
775 | break; | ||
776 | case BARRELTARGET: | ||
777 | j = 'f'; | ||
778 | break; | ||
779 | case DEEP_PIT: | ||
780 | j = 'd'; | ||
781 | break; | ||
782 | case PLAYER: | ||
783 | j = 'u'; | ||
784 | break; | ||
785 | case PLAYERTARGET: | ||
786 | j = 'v'; | ||
787 | break; | ||
788 | default: | ||
789 | j = '?'; | ||
790 | break; | ||
791 | } | ||
792 | assert(j != '?'); | ||
793 | if (j != prev) { | ||
794 | desc[desclen++] = j; | ||
795 | descpos = desclen; | ||
796 | prev = j; | ||
797 | count = 1; | ||
798 | } else { | ||
799 | count++; | ||
800 | desclen = descpos + sprintf(desc+descpos, "%d", count); | ||
801 | } | ||
802 | } | ||
803 | |||
804 | sfree(grid); | ||
805 | |||
806 | return desc; | ||
807 | } | ||
808 | |||
809 | static const char *validate_desc(const game_params *params, const char *desc) | ||
810 | { | ||
811 | int w = params->w, h = params->h; | ||
812 | int area = 0; | ||
813 | int nplayers = 0; | ||
814 | |||
815 | while (*desc) { | ||
816 | int c = *desc++; | ||
817 | int n = 1; | ||
818 | if (*desc && isdigit((unsigned char)*desc)) { | ||
819 | n = atoi(desc); | ||
820 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
821 | } | ||
822 | |||
823 | area += n; | ||
824 | |||
825 | if (c == PLAYER || c == PLAYERTARGET) | ||
826 | nplayers += n; | ||
827 | else if (c == INITIAL || c == SPACE || c == WALL || c == TARGET || | ||
828 | c == PIT || c == DEEP_PIT || IS_BARREL(c)) | ||
829 | /* ok */; | ||
830 | else | ||
831 | return "Invalid character in game description"; | ||
832 | } | ||
833 | |||
834 | if (area > w*h) | ||
835 | return "Too much data in game description"; | ||
836 | if (area < w*h) | ||
837 | return "Too little data in game description"; | ||
838 | if (nplayers < 1) | ||
839 | return "No starting player position specified"; | ||
840 | if (nplayers > 1) | ||
841 | return "More than one starting player position specified"; | ||
842 | |||
843 | return NULL; | ||
844 | } | ||
845 | |||
846 | static game_state *new_game(midend *me, const game_params *params, | ||
847 | const char *desc) | ||
848 | { | ||
849 | int w = params->w, h = params->h; | ||
850 | game_state *state = snew(game_state); | ||
851 | int i; | ||
852 | |||
853 | state->p = *params; /* structure copy */ | ||
854 | state->grid = snewn(w*h, unsigned char); | ||
855 | state->px = state->py = -1; | ||
856 | state->completed = false; | ||
857 | |||
858 | i = 0; | ||
859 | |||
860 | while (*desc) { | ||
861 | int c = *desc++; | ||
862 | int n = 1; | ||
863 | if (*desc && isdigit((unsigned char)*desc)) { | ||
864 | n = atoi(desc); | ||
865 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
866 | } | ||
867 | |||
868 | if (c == PLAYER || c == PLAYERTARGET) { | ||
869 | state->py = i / w; | ||
870 | state->px = i % w; | ||
871 | c = IS_ON_TARGET(c) ? TARGET : SPACE; | ||
872 | } | ||
873 | |||
874 | while (n-- > 0) | ||
875 | state->grid[i++] = c; | ||
876 | } | ||
877 | |||
878 | assert(i == w*h); | ||
879 | assert(state->px != -1 && state->py != -1); | ||
880 | |||
881 | return state; | ||
882 | } | ||
883 | |||
884 | static game_state *dup_game(const game_state *state) | ||
885 | { | ||
886 | int w = state->p.w, h = state->p.h; | ||
887 | game_state *ret = snew(game_state); | ||
888 | |||
889 | ret->p = state->p; /* structure copy */ | ||
890 | ret->grid = snewn(w*h, unsigned char); | ||
891 | memcpy(ret->grid, state->grid, w*h); | ||
892 | ret->px = state->px; | ||
893 | ret->py = state->py; | ||
894 | ret->completed = state->completed; | ||
895 | |||
896 | return ret; | ||
897 | } | ||
898 | |||
899 | static void free_game(game_state *state) | ||
900 | { | ||
901 | sfree(state->grid); | ||
902 | sfree(state); | ||
903 | } | ||
904 | |||
905 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
906 | const char *aux, const char **error) | ||
907 | { | ||
908 | return NULL; | ||
909 | } | ||
910 | |||
911 | static bool game_can_format_as_text_now(const game_params *params) | ||
912 | { | ||
913 | return true; | ||
914 | } | ||
915 | |||
916 | static char *game_text_format(const game_state *state) | ||
917 | { | ||
918 | return NULL; | ||
919 | } | ||
920 | |||
921 | static game_ui *new_ui(const game_state *state) | ||
922 | { | ||
923 | return NULL; | ||
924 | } | ||
925 | |||
926 | static void free_ui(game_ui *ui) | ||
927 | { | ||
928 | } | ||
929 | |||
930 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
931 | const game_state *newstate) | ||
932 | { | ||
933 | } | ||
934 | |||
935 | struct game_drawstate { | ||
936 | game_params p; | ||
937 | int tilesize; | ||
938 | bool started; | ||
939 | unsigned short *grid; | ||
940 | }; | ||
941 | |||
942 | #define PREFERRED_TILESIZE 32 | ||
943 | #define TILESIZE (ds->tilesize) | ||
944 | #define BORDER (TILESIZE) | ||
945 | #define HIGHLIGHT_WIDTH (TILESIZE / 10) | ||
946 | #define COORD(x) ( (x) * TILESIZE + BORDER ) | ||
947 | #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) | ||
948 | |||
949 | /* | ||
950 | * I'm going to need to do most of the move-type analysis in both | ||
951 | * interpret_move and execute_move, so I'll abstract it out into a | ||
952 | * subfunction. move_type() returns -1 for an illegal move, 0 for a | ||
953 | * movement, and 1 for a push. | ||
954 | */ | ||
955 | static int move_type(const game_state *state, int dx, int dy) | ||
956 | { | ||
957 | int w = state->p.w, h = state->p.h; | ||
958 | int px = state->px, py = state->py; | ||
959 | int nx, ny, nbx, nby; | ||
960 | |||
961 | assert(dx >= -1 && dx <= +1); | ||
962 | assert(dy >= -1 && dy <= +1); | ||
963 | assert(dx || dy); | ||
964 | |||
965 | nx = px + dx; | ||
966 | ny = py + dy; | ||
967 | |||
968 | /* | ||
969 | * Disallow any move that goes off the grid. | ||
970 | */ | ||
971 | if (nx < 0 || nx >= w || ny < 0 || ny >= h) | ||
972 | return -1; | ||
973 | |||
974 | /* | ||
975 | * Examine the target square of the move to see whether it's a | ||
976 | * space, a barrel, or a wall. | ||
977 | */ | ||
978 | |||
979 | if (state->grid[ny*w+nx] == WALL || | ||
980 | state->grid[ny*w+nx] == PIT || | ||
981 | state->grid[ny*w+nx] == DEEP_PIT) | ||
982 | return -1; /* this one's easy; just disallow it */ | ||
983 | |||
984 | if (IS_BARREL(state->grid[ny*w+nx])) { | ||
985 | /* | ||
986 | * This is a push move. For a start, that means it must not | ||
987 | * be diagonal. | ||
988 | */ | ||
989 | if (dy && dx) | ||
990 | return -1; | ||
991 | |||
992 | /* | ||
993 | * Now find the location of the third square involved in | ||
994 | * the push, and stop if it's off the edge. | ||
995 | */ | ||
996 | nbx = nx + dx; | ||
997 | nby = ny + dy; | ||
998 | if (nbx < 0 || nbx >= w || nby < 0 || nby >= h) | ||
999 | return -1; | ||
1000 | |||
1001 | /* | ||
1002 | * That third square must be able to accept a barrel. | ||
1003 | */ | ||
1004 | if (state->grid[nby*w+nbx] == SPACE || | ||
1005 | state->grid[nby*w+nbx] == TARGET || | ||
1006 | state->grid[nby*w+nbx] == PIT || | ||
1007 | state->grid[nby*w+nbx] == DEEP_PIT) { | ||
1008 | /* | ||
1009 | * The push is valid. | ||
1010 | */ | ||
1011 | return 1; | ||
1012 | } else { | ||
1013 | return -1; | ||
1014 | } | ||
1015 | } else { | ||
1016 | /* | ||
1017 | * This is just an ordinary move. We've already checked the | ||
1018 | * target square, so the only thing left to check is that a | ||
1019 | * diagonal move has a space on one side to have notionally | ||
1020 | * gone through. | ||
1021 | */ | ||
1022 | if (dx && dy && | ||
1023 | state->grid[(py+dy)*w+px] != SPACE && | ||
1024 | state->grid[(py+dy)*w+px] != TARGET && | ||
1025 | state->grid[py*w+(px+dx)] != SPACE && | ||
1026 | state->grid[py*w+(px+dx)] != TARGET) | ||
1027 | return -1; | ||
1028 | |||
1029 | /* | ||
1030 | * Otherwise, the move is valid. | ||
1031 | */ | ||
1032 | return 0; | ||
1033 | } | ||
1034 | } | ||
1035 | |||
1036 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1037 | const game_drawstate *ds, | ||
1038 | int x, int y, int button) | ||
1039 | { | ||
1040 | int dx=0, dy=0; | ||
1041 | char *move; | ||
1042 | |||
1043 | /* | ||
1044 | * Diagonal movement is supported as it is in NetHack: it's | ||
1045 | * for movement only (never pushing), and one of the two | ||
1046 | * squares adjacent to both the source and destination | ||
1047 | * squares must be free to move through. In other words, it | ||
1048 | * is only a shorthand for two orthogonal moves and cannot | ||
1049 | * change the nature of the actual puzzle game. | ||
1050 | */ | ||
1051 | if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8')) | ||
1052 | dx = 0, dy = -1; | ||
1053 | else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2')) | ||
1054 | dx = 0, dy = +1; | ||
1055 | else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4')) | ||
1056 | dx = -1, dy = 0; | ||
1057 | else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6')) | ||
1058 | dx = +1, dy = 0; | ||
1059 | else if (button == (MOD_NUM_KEYPAD | '7')) | ||
1060 | dx = -1, dy = -1; | ||
1061 | else if (button == (MOD_NUM_KEYPAD | '9')) | ||
1062 | dx = +1, dy = -1; | ||
1063 | else if (button == (MOD_NUM_KEYPAD | '1')) | ||
1064 | dx = -1, dy = +1; | ||
1065 | else if (button == (MOD_NUM_KEYPAD | '3')) | ||
1066 | dx = +1, dy = +1; | ||
1067 | else if (button == LEFT_BUTTON) | ||
1068 | { | ||
1069 | if(x < COORD(state->px)) | ||
1070 | dx = -1; | ||
1071 | else if (x > COORD(state->px + 1)) | ||
1072 | dx = 1; | ||
1073 | if(y < COORD(state->py)) | ||
1074 | dy = -1; | ||
1075 | else if (y > COORD(state->py + 1)) | ||
1076 | dy = 1; | ||
1077 | } | ||
1078 | else | ||
1079 | return NULL; | ||
1080 | |||
1081 | if((dx == 0) && (dy == 0)) | ||
1082 | return(NULL); | ||
1083 | |||
1084 | if (move_type(state, dx, dy) < 0) | ||
1085 | return NULL; | ||
1086 | |||
1087 | move = snewn(2, char); | ||
1088 | move[1] = '\0'; | ||
1089 | move[0] = '5' - 3*dy + dx; | ||
1090 | return move; | ||
1091 | } | ||
1092 | |||
1093 | static game_state *execute_move(const game_state *state, const char *move) | ||
1094 | { | ||
1095 | int w = state->p.w, h = state->p.h; | ||
1096 | int px = state->px, py = state->py; | ||
1097 | int dx, dy, nx, ny, nbx, nby, type, m, i; | ||
1098 | bool freebarrels, freetargets; | ||
1099 | game_state *ret; | ||
1100 | |||
1101 | if (*move < '1' || *move == '5' || *move > '9' || move[1]) | ||
1102 | return NULL; /* invalid move string */ | ||
1103 | |||
1104 | m = *move - '0'; | ||
1105 | dx = (m + 2) % 3 - 1; | ||
1106 | dy = 2 - (m + 2) / 3; | ||
1107 | type = move_type(state, dx, dy); | ||
1108 | if (type < 0) | ||
1109 | return NULL; | ||
1110 | |||
1111 | ret = dup_game(state); | ||
1112 | |||
1113 | nx = px + dx; | ||
1114 | ny = py + dy; | ||
1115 | nbx = nx + dx; | ||
1116 | nby = ny + dy; | ||
1117 | |||
1118 | if (type) { | ||
1119 | int b; | ||
1120 | |||
1121 | /* | ||
1122 | * Push. | ||
1123 | */ | ||
1124 | b = ret->grid[ny*w+nx]; | ||
1125 | if (IS_ON_TARGET(b)) { | ||
1126 | ret->grid[ny*w+nx] = TARGET; | ||
1127 | b = DETARGETISE(b); | ||
1128 | } else | ||
1129 | ret->grid[ny*w+nx] = SPACE; | ||
1130 | |||
1131 | if (ret->grid[nby*w+nbx] == PIT) | ||
1132 | ret->grid[nby*w+nbx] = SPACE; | ||
1133 | else if (ret->grid[nby*w+nbx] == DEEP_PIT) | ||
1134 | /* do nothing - the pit eats the barrel and remains there */; | ||
1135 | else if (ret->grid[nby*w+nbx] == TARGET) | ||
1136 | ret->grid[nby*w+nbx] = TARGETISE(b); | ||
1137 | else | ||
1138 | ret->grid[nby*w+nbx] = b; | ||
1139 | } | ||
1140 | |||
1141 | ret->px = nx; | ||
1142 | ret->py = ny; | ||
1143 | |||
1144 | /* | ||
1145 | * Check for completion. This is surprisingly complicated, | ||
1146 | * given the presence of pits and deep pits, and also the fact | ||
1147 | * that some Sokoban levels with pits have fewer pits than | ||
1148 | * barrels (due to providing spares, e.g. NetHack's). I think | ||
1149 | * the completion condition in fact must be that the game | ||
1150 | * cannot become any _more_ complete. That is, _either_ there | ||
1151 | * are no remaining barrels not on targets, _or_ there is a | ||
1152 | * good reason why any such barrels cannot be placed. The only | ||
1153 | * available good reason is that there are no remaining pits, | ||
1154 | * no free target squares, and no deep pits at all. | ||
1155 | */ | ||
1156 | if (!ret->completed) { | ||
1157 | freebarrels = false; | ||
1158 | freetargets = false; | ||
1159 | for (i = 0; i < w*h; i++) { | ||
1160 | int v = ret->grid[i]; | ||
1161 | |||
1162 | if (IS_BARREL(v) && !IS_ON_TARGET(v)) | ||
1163 | freebarrels = true; | ||
1164 | if (v == DEEP_PIT || v == PIT || | ||
1165 | (!IS_BARREL(v) && IS_ON_TARGET(v))) | ||
1166 | freetargets = true; | ||
1167 | } | ||
1168 | |||
1169 | if (!freebarrels || !freetargets) | ||
1170 | ret->completed = true; | ||
1171 | } | ||
1172 | |||
1173 | return ret; | ||
1174 | } | ||
1175 | |||
1176 | /* ---------------------------------------------------------------------- | ||
1177 | * Drawing routines. | ||
1178 | */ | ||
1179 | |||
1180 | static void game_compute_size(const game_params *params, int tilesize, | ||
1181 | const game_ui *ui, int *x, int *y) | ||
1182 | { | ||
1183 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1184 | struct { int tilesize; } ads, *ds = &ads; | ||
1185 | ads.tilesize = tilesize; | ||
1186 | |||
1187 | *x = 2 * BORDER + 1 + params->w * TILESIZE; | ||
1188 | *y = 2 * BORDER + 1 + params->h * TILESIZE; | ||
1189 | } | ||
1190 | |||
1191 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1192 | const game_params *params, int tilesize) | ||
1193 | { | ||
1194 | ds->tilesize = tilesize; | ||
1195 | } | ||
1196 | |||
1197 | static float *game_colours(frontend *fe, int *ncolours) | ||
1198 | { | ||
1199 | float *ret = snewn(3 * NCOLOURS, float); | ||
1200 | int i; | ||
1201 | |||
1202 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); | ||
1203 | |||
1204 | ret[COL_OUTLINE * 3 + 0] = 0.0F; | ||
1205 | ret[COL_OUTLINE * 3 + 1] = 0.0F; | ||
1206 | ret[COL_OUTLINE * 3 + 2] = 0.0F; | ||
1207 | |||
1208 | ret[COL_PLAYER * 3 + 0] = 0.0F; | ||
1209 | ret[COL_PLAYER * 3 + 1] = 1.0F; | ||
1210 | ret[COL_PLAYER * 3 + 2] = 0.0F; | ||
1211 | |||
1212 | ret[COL_BARREL * 3 + 0] = 0.6F; | ||
1213 | ret[COL_BARREL * 3 + 1] = 0.3F; | ||
1214 | ret[COL_BARREL * 3 + 2] = 0.0F; | ||
1215 | |||
1216 | ret[COL_TARGET * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0]; | ||
1217 | ret[COL_TARGET * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1]; | ||
1218 | ret[COL_TARGET * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2]; | ||
1219 | |||
1220 | ret[COL_PIT * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0] / 2; | ||
1221 | ret[COL_PIT * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1] / 2; | ||
1222 | ret[COL_PIT * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2] / 2; | ||
1223 | |||
1224 | ret[COL_DEEP_PIT * 3 + 0] = 0.0F; | ||
1225 | ret[COL_DEEP_PIT * 3 + 1] = 0.0F; | ||
1226 | ret[COL_DEEP_PIT * 3 + 2] = 0.0F; | ||
1227 | |||
1228 | ret[COL_TEXT * 3 + 0] = 1.0F; | ||
1229 | ret[COL_TEXT * 3 + 1] = 1.0F; | ||
1230 | ret[COL_TEXT * 3 + 2] = 1.0F; | ||
1231 | |||
1232 | ret[COL_GRID * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0]; | ||
1233 | ret[COL_GRID * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1]; | ||
1234 | ret[COL_GRID * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2]; | ||
1235 | |||
1236 | ret[COL_OUTLINE * 3 + 0] = 0.0F; | ||
1237 | ret[COL_OUTLINE * 3 + 1] = 0.0F; | ||
1238 | ret[COL_OUTLINE * 3 + 2] = 0.0F; | ||
1239 | |||
1240 | for (i = 0; i < 3; i++) { | ||
1241 | ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] + | ||
1242 | 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4; | ||
1243 | } | ||
1244 | |||
1245 | *ncolours = NCOLOURS; | ||
1246 | return ret; | ||
1247 | } | ||
1248 | |||
1249 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1250 | { | ||
1251 | int w = state->p.w, h = state->p.h; | ||
1252 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1253 | int i; | ||
1254 | |||
1255 | ds->tilesize = 0; | ||
1256 | ds->p = state->p; /* structure copy */ | ||
1257 | ds->grid = snewn(w*h, unsigned short); | ||
1258 | for (i = 0; i < w*h; i++) | ||
1259 | ds->grid[i] = INVALID; | ||
1260 | ds->started = false; | ||
1261 | |||
1262 | return ds; | ||
1263 | } | ||
1264 | |||
1265 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1266 | { | ||
1267 | sfree(ds->grid); | ||
1268 | sfree(ds); | ||
1269 | } | ||
1270 | |||
1271 | static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v) | ||
1272 | { | ||
1273 | int tx = COORD(x), ty = COORD(y); | ||
1274 | int bg = (v & 0x100 ? COL_HIGHLIGHT : COL_BACKGROUND); | ||
1275 | |||
1276 | v &= 0xFF; | ||
1277 | |||
1278 | clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1); | ||
1279 | draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg); | ||
1280 | |||
1281 | if (v == WALL) { | ||
1282 | int coords[6]; | ||
1283 | |||
1284 | coords[0] = tx + TILESIZE; | ||
1285 | coords[1] = ty + TILESIZE; | ||
1286 | coords[2] = tx + TILESIZE; | ||
1287 | coords[3] = ty + 1; | ||
1288 | coords[4] = tx + 1; | ||
1289 | coords[5] = ty + TILESIZE; | ||
1290 | draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT); | ||
1291 | |||
1292 | coords[0] = tx + 1; | ||
1293 | coords[1] = ty + 1; | ||
1294 | draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); | ||
1295 | |||
1296 | draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH, | ||
1297 | TILESIZE - 2*HIGHLIGHT_WIDTH, | ||
1298 | TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL); | ||
1299 | } else if (v == PIT) { | ||
1300 | draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, | ||
1301 | TILESIZE*3/7, COL_PIT, COL_OUTLINE); | ||
1302 | } else if (v == DEEP_PIT) { | ||
1303 | draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, | ||
1304 | TILESIZE*3/7, COL_DEEP_PIT, COL_OUTLINE); | ||
1305 | } else { | ||
1306 | if (IS_ON_TARGET(v)) { | ||
1307 | draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, | ||
1308 | TILESIZE*3/7, COL_TARGET, COL_OUTLINE); | ||
1309 | } | ||
1310 | if (IS_PLAYER(v)) { | ||
1311 | draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, | ||
1312 | TILESIZE/3, COL_PLAYER, COL_OUTLINE); | ||
1313 | } else if (IS_BARREL(v)) { | ||
1314 | char str[2]; | ||
1315 | |||
1316 | draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2, | ||
1317 | TILESIZE/3, COL_BARREL, COL_OUTLINE); | ||
1318 | str[1] = '\0'; | ||
1319 | str[0] = BARREL_LABEL(v); | ||
1320 | if (str[0]) { | ||
1321 | draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, | ||
1322 | FONT_VARIABLE, TILESIZE/2, | ||
1323 | ALIGN_VCENTRE | ALIGN_HCENTRE, COL_TEXT, str); | ||
1324 | } | ||
1325 | } | ||
1326 | } | ||
1327 | |||
1328 | unclip(dr); | ||
1329 | draw_update(dr, tx, ty, TILESIZE, TILESIZE); | ||
1330 | } | ||
1331 | |||
1332 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1333 | const game_state *oldstate, const game_state *state, | ||
1334 | int dir, const game_ui *ui, | ||
1335 | float animtime, float flashtime) | ||
1336 | { | ||
1337 | int w = state->p.w, h = state->p.h /*, wh = w*h */; | ||
1338 | int x, y; | ||
1339 | int flashtype; | ||
1340 | |||
1341 | if (flashtime && | ||
1342 | !((int)(flashtime * 3 / FLASH_LENGTH) % 2)) | ||
1343 | flashtype = 0x100; | ||
1344 | else | ||
1345 | flashtype = 0; | ||
1346 | |||
1347 | /* | ||
1348 | * Initialise a fresh drawstate. | ||
1349 | */ | ||
1350 | if (!ds->started) { | ||
1351 | /* | ||
1352 | * Draw the grid lines. | ||
1353 | */ | ||
1354 | for (y = 0; y <= h; y++) | ||
1355 | draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y), | ||
1356 | COL_LOWLIGHT); | ||
1357 | for (x = 0; x <= w; x++) | ||
1358 | draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h), | ||
1359 | COL_LOWLIGHT); | ||
1360 | |||
1361 | ds->started = true; | ||
1362 | } | ||
1363 | |||
1364 | /* | ||
1365 | * Draw the grid contents. | ||
1366 | */ | ||
1367 | for (y = 0; y < h; y++) | ||
1368 | for (x = 0; x < w; x++) { | ||
1369 | int v = state->grid[y*w+x]; | ||
1370 | if (y == state->py && x == state->px) { | ||
1371 | if (v == TARGET) | ||
1372 | v = PLAYERTARGET; | ||
1373 | else { | ||
1374 | assert(v == SPACE); | ||
1375 | v = PLAYER; | ||
1376 | } | ||
1377 | } | ||
1378 | |||
1379 | v |= flashtype; | ||
1380 | |||
1381 | if (ds->grid[y*w+x] != v) { | ||
1382 | draw_tile(dr, ds, x, y, v); | ||
1383 | ds->grid[y*w+x] = v; | ||
1384 | } | ||
1385 | } | ||
1386 | |||
1387 | } | ||
1388 | |||
1389 | static float game_anim_length(const game_state *oldstate, | ||
1390 | const game_state *newstate, int dir, game_ui *ui) | ||
1391 | { | ||
1392 | return 0.0F; | ||
1393 | } | ||
1394 | |||
1395 | static float game_flash_length(const game_state *oldstate, | ||
1396 | const game_state *newstate, int dir, game_ui *ui) | ||
1397 | { | ||
1398 | if (!oldstate->completed && newstate->completed) | ||
1399 | return FLASH_LENGTH; | ||
1400 | else | ||
1401 | return 0.0F; | ||
1402 | } | ||
1403 | |||
1404 | static void game_get_cursor_location(const game_ui *ui, | ||
1405 | const game_drawstate *ds, | ||
1406 | const game_state *state, | ||
1407 | const game_params *params, | ||
1408 | int *x, int *y, int *w, int *h) | ||
1409 | { | ||
1410 | } | ||
1411 | |||
1412 | static int game_status(const game_state *state) | ||
1413 | { | ||
1414 | return state->completed ? +1 : 0; | ||
1415 | } | ||
1416 | |||
1417 | static bool game_timing_state(const game_state *state, game_ui *ui) | ||
1418 | { | ||
1419 | return true; | ||
1420 | } | ||
1421 | |||
1422 | static void game_print_size(const game_params *params, const game_ui *ui, | ||
1423 | float *x, float *y) | ||
1424 | { | ||
1425 | } | ||
1426 | |||
1427 | static void game_print(drawing *dr, const game_state *state, const game_ui *ui, | ||
1428 | int tilesize) | ||
1429 | { | ||
1430 | } | ||
1431 | |||
1432 | #ifdef COMBINED | ||
1433 | #define thegame sokoban | ||
1434 | #endif | ||
1435 | |||
1436 | const struct game thegame = { | ||
1437 | "Sokoban", NULL, NULL, | ||
1438 | default_params, | ||
1439 | game_fetch_preset, NULL, | ||
1440 | decode_params, | ||
1441 | encode_params, | ||
1442 | free_params, | ||
1443 | dup_params, | ||
1444 | true, game_configure, custom_params, | ||
1445 | validate_params, | ||
1446 | new_game_desc, | ||
1447 | validate_desc, | ||
1448 | new_game, | ||
1449 | dup_game, | ||
1450 | free_game, | ||
1451 | false, solve_game, | ||
1452 | false, game_can_format_as_text_now, game_text_format, | ||
1453 | NULL, NULL, /* get_prefs, set_prefs */ | ||
1454 | new_ui, | ||
1455 | free_ui, | ||
1456 | NULL, /* encode_ui */ | ||
1457 | NULL, /* decode_ui */ | ||
1458 | NULL, /* game_request_keys */ | ||
1459 | game_changed_state, | ||
1460 | NULL, /* current_key_label */ | ||
1461 | interpret_move, | ||
1462 | execute_move, | ||
1463 | PREFERRED_TILESIZE, game_compute_size, game_set_size, | ||
1464 | game_colours, | ||
1465 | game_new_drawstate, | ||
1466 | game_free_drawstate, | ||
1467 | game_redraw, | ||
1468 | game_anim_length, | ||
1469 | game_flash_length, | ||
1470 | game_get_cursor_location, | ||
1471 | game_status, | ||
1472 | false, false, game_print_size, game_print, | ||
1473 | false, /* wants_statusbar */ | ||
1474 | false, game_timing_state, | ||
1475 | 0, /* flags */ | ||
1476 | }; | ||