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