2 * inertia.c: Game involving navigating round a grid picking up
5 * Game rules and basic generator design by Ben Olmstead.
6 * This re-implementation was written by Simon Tatham.
18 /* Used in the game_state */
25 /* Used in the game IDs */
28 /* Used in the game generation */
31 /* Used only in the game_drawstate*/
35 #define DP1 (DIRECTIONS+1)
36 #define DX(dir) ( (dir) & 3 ? (((dir) & 7) > 4 ? -1 : +1) : 0 )
37 #define DY(dir) ( DX((dir)+6) )
40 * Lvalue macro which expects x and y to be in range.
42 #define LV_AT(w, h, grid, x, y) ( (grid)[(y)*(w)+(x)] )
45 * Rvalue macro which can cope with x and y being out of range.
47 #define AT(w, h, grid, x, y) ( (x)<0 || (x)>=(w) || (y)<0 || (y)>=(h) ? \
48 WALL : LV_AT(w, h, grid, x, y) )
86 static game_params
*default_params(void)
88 game_params
*ret
= snew(game_params
);
96 static void free_params(game_params
*params
)
101 static game_params
*dup_params(game_params
*params
)
103 game_params
*ret
= snew(game_params
);
104 *ret
= *params
; /* structure copy */
108 static const struct game_params inertia_presets
[] = {
114 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
120 if (i
< 0 || i
>= lenof(inertia_presets
))
123 p
= inertia_presets
[i
];
124 ret
= dup_params(&p
);
125 sprintf(namebuf
, "%dx%d", ret
->w
, ret
->h
);
126 retname
= dupstr(namebuf
);
133 static void decode_params(game_params
*params
, char const *string
)
135 params
->w
= params
->h
= atoi(string
);
136 while (*string
&& isdigit((unsigned char)*string
)) string
++;
137 if (*string
== 'x') {
139 params
->h
= atoi(string
);
143 static char *encode_params(game_params
*params
, int full
)
147 sprintf(data
, "%dx%d", params
->w
, params
->h
);
152 static config_item
*game_configure(game_params
*params
)
157 ret
= snewn(3, config_item
);
159 ret
[0].name
= "Width";
160 ret
[0].type
= C_STRING
;
161 sprintf(buf
, "%d", params
->w
);
162 ret
[0].sval
= dupstr(buf
);
165 ret
[1].name
= "Height";
166 ret
[1].type
= C_STRING
;
167 sprintf(buf
, "%d", params
->h
);
168 ret
[1].sval
= dupstr(buf
);
179 static game_params
*custom_params(config_item
*cfg
)
181 game_params
*ret
= snew(game_params
);
183 ret
->w
= atoi(cfg
[0].sval
);
184 ret
->h
= atoi(cfg
[1].sval
);
189 static char *validate_params(game_params
*params
, int full
)
192 * Avoid completely degenerate cases which only have one
193 * row/column. We probably could generate completable puzzles
194 * of that shape, but they'd be forced to be extremely boring
195 * and at large sizes would take a while to happen upon at
198 if (params
->w
< 2 || params
->h
< 2)
199 return "Width and height must both be at least two";
202 * The grid construction algorithm creates 1/5 as many gems as
203 * grid squares, and must create at least one gem to have an
204 * actual puzzle. However, an area-five grid is ruled out by
205 * the above constraint, so the practical minimum is six.
207 if (params
->w
* params
->h
< 6)
208 return "Grid area must be at least six squares";
213 /* ----------------------------------------------------------------------
214 * Solver used by grid generator.
217 struct solver_scratch
{
218 unsigned char *reachable_from
, *reachable_to
;
222 static struct solver_scratch
*new_scratch(int w
, int h
)
224 struct solver_scratch
*sc
= snew(struct solver_scratch
);
226 sc
->reachable_from
= snewn(w
* h
* DIRECTIONS
, unsigned char);
227 sc
->reachable_to
= snewn(w
* h
* DIRECTIONS
, unsigned char);
228 sc
->positions
= snewn(w
* h
* DIRECTIONS
, int);
233 static void free_scratch(struct solver_scratch
*sc
)
235 sfree(sc
->reachable_from
);
236 sfree(sc
->reachable_to
);
237 sfree(sc
->positions
);
241 static int can_go(int w
, int h
, char *grid
,
242 int x1
, int y1
, int dir1
, int x2
, int y2
, int dir2
)
245 * Returns TRUE if we can transition directly from (x1,y1)
246 * going in direction dir1, to (x2,y2) going in direction dir2.
250 * If we're actually in the middle of an unoccupyable square,
251 * we cannot make any move.
253 if (AT(w
, h
, grid
, x1
, y1
) == WALL
||
254 AT(w
, h
, grid
, x1
, y1
) == MINE
)
258 * If a move is capable of stopping at x1,y1,dir1, and x2,y2 is
259 * the same coordinate as x1,y1, then we can make the
260 * transition (by stopping and changing direction).
262 * For this to be the case, we have to either have a wall
263 * beyond x1,y1,dir1, or have a stop on x1,y1.
265 if (x2
== x1
&& y2
== y1
&&
266 (AT(w
, h
, grid
, x1
, y1
) == STOP
||
267 AT(w
, h
, grid
, x1
, y1
) == START
||
268 AT(w
, h
, grid
, x1
+DX(dir1
), y1
+DY(dir1
)) == WALL
))
272 * If a move is capable of continuing here, then x1,y1,dir1 can
273 * move one space further on.
275 if (x2
== x1
+DX(dir1
) && y2
== y1
+DY(dir1
) && dir1
== dir2
&&
276 (AT(w
, h
, grid
, x2
, y2
) == BLANK
||
277 AT(w
, h
, grid
, x2
, y2
) == GEM
||
278 AT(w
, h
, grid
, x2
, y2
) == STOP
||
279 AT(w
, h
, grid
, x2
, y2
) == START
))
288 static int find_gem_candidates(int w
, int h
, char *grid
,
289 struct solver_scratch
*sc
)
293 int sx
, sy
, gx
, gy
, gd
, pass
, possgems
;
296 * This function finds all the candidate gem squares, which are
297 * precisely those squares which can be picked up on a loop
298 * from the starting point back to the starting point. Doing
299 * this may involve passing through such a square in the middle
300 * of a move; so simple breadth-first search over the _squares_
301 * of the grid isn't quite adequate, because it might be that
302 * we can only reach a gem from the start by moving over it in
303 * one direction, but can only return to the start if we were
304 * moving over it in another direction.
306 * Instead, we BFS over a space which mentions each grid square
307 * eight times - once for each direction. We also BFS twice:
308 * once to find out what square+direction pairs we can reach
309 * _from_ the start point, and once to find out what pairs we
310 * can reach the start point from. Then a square is reachable
311 * if any of the eight directions for that square has both
315 memset(sc
->reachable_from
, 0, wh
* DIRECTIONS
);
316 memset(sc
->reachable_to
, 0, wh
* DIRECTIONS
);
319 * Find the starting square.
321 sx
= -1; /* placate optimiser */
322 for (sy
= 0; sy
< h
; sy
++) {
323 for (sx
= 0; sx
< w
; sx
++)
324 if (AT(w
, h
, grid
, sx
, sy
) == START
)
331 for (pass
= 0; pass
< 2; pass
++) {
332 unsigned char *reachable
= (pass
== 0 ? sc
->reachable_from
:
334 int sign
= (pass
== 0 ?
+1 : -1);
337 #ifdef SOLVER_DIAGNOSTICS
338 printf("starting pass %d\n", pass
);
342 * `head' and `tail' are indices within sc->positions which
343 * track the list of board positions left to process.
346 for (dir
= 0; dir
< DIRECTIONS
; dir
++) {
347 int index
= (sy
*w
+sx
)*DIRECTIONS
+dir
;
348 sc
->positions
[tail
++] = index
;
349 reachable
[index
] = TRUE
;
350 #ifdef SOLVER_DIAGNOSTICS
351 printf("starting point %d,%d,%d\n", sx
, sy
, dir
);
356 * Now repeatedly pick an element off the list and process
359 while (head
< tail
) {
360 int index
= sc
->positions
[head
++];
361 int dir
= index
% DIRECTIONS
;
362 int x
= (index
/ DIRECTIONS
) % w
;
363 int y
= index
/ (w
* DIRECTIONS
);
364 int n
, x2
, y2
, d2
, i2
;
366 #ifdef SOLVER_DIAGNOSTICS
367 printf("processing point %d,%d,%d\n", x
, y
, dir
);
370 * The places we attempt to switch to here are:
371 * - each possible direction change (all the other
372 * directions in this square)
373 * - one step further in the direction we're going (or
374 * one step back, if we're in the reachable_to pass).
376 for (n
= -1; n
< DIRECTIONS
; n
++) {
378 x2
= x
+ sign
* DX(dir
);
379 y2
= y
+ sign
* DY(dir
);
386 i2
= (y2
*w
+x2
)*DIRECTIONS
+d2
;
387 if (x2
>= 0 && x2
< w
&&
391 #ifdef SOLVER_DIAGNOSTICS
392 printf(" trying point %d,%d,%d", x2
, y2
, d2
);
395 ok
= can_go(w
, h
, grid
, x
, y
, dir
, x2
, y2
, d2
);
397 ok
= can_go(w
, h
, grid
, x2
, y2
, d2
, x
, y
, dir
);
398 #ifdef SOLVER_DIAGNOSTICS
399 printf(" - %sok\n", ok ?
"" : "not ");
402 sc
->positions
[tail
++] = i2
;
403 reachable
[i2
] = TRUE
;
411 * And that should be it. Now all we have to do is find the
412 * squares for which there exists _some_ direction such that
413 * the square plus that direction form a tuple which is both
414 * reachable from the start and reachable to the start.
417 for (gy
= 0; gy
< h
; gy
++)
418 for (gx
= 0; gx
< w
; gx
++)
419 if (AT(w
, h
, grid
, gx
, gy
) == BLANK
) {
420 for (gd
= 0; gd
< DIRECTIONS
; gd
++) {
421 int index
= (gy
*w
+gx
)*DIRECTIONS
+gd
;
422 if (sc
->reachable_from
[index
] && sc
->reachable_to
[index
]) {
423 #ifdef SOLVER_DIAGNOSTICS
424 printf("space at %d,%d is reachable via"
425 " direction %d\n", gx
, gy
, gd
);
427 LV_AT(w
, h
, grid
, gx
, gy
) = POSSGEM
;
437 /* ----------------------------------------------------------------------
438 * Grid generation code.
441 static char *gengrid(int w
, int h
, random_state
*rs
)
444 char *grid
= snewn(wh
+1, char);
445 struct solver_scratch
*sc
= new_scratch(w
, h
);
446 int maxdist_threshold
, tries
;
448 maxdist_threshold
= 2;
454 int *dist
, *list
, head
, tail
, maxdist
;
457 * We're going to fill the grid with the five basic piece
458 * types in about 1/5 proportion. For the moment, though,
459 * we leave out the gems, because we'll put those in
460 * _after_ we run the solver to tell us where the viable
464 for (j
= 0; j
< wh
/5; j
++)
466 for (j
= 0; j
< wh
/5; j
++)
468 for (j
= 0; j
< wh
/5; j
++)
474 shuffle(grid
, wh
, sizeof(*grid
), rs
);
477 * Find the viable gem locations, and immediately give up
478 * and try again if there aren't enough of them.
480 possgems
= find_gem_candidates(w
, h
, grid
, sc
);
485 * We _could_ now select wh/5 of the POSSGEMs and set them
486 * to GEM, and have a viable level. However, there's a
487 * chance that a large chunk of the level will turn out to
488 * be unreachable, so first we test for that.
490 * We do this by finding the largest distance from any
491 * square to the nearest POSSGEM, by breadth-first search.
492 * If this is above a critical threshold, we abort and try
495 * (This search is purely geometric, without regard to
496 * walls and long ways round.)
498 dist
= sc
->positions
;
499 list
= sc
->positions
+ wh
;
500 for (i
= 0; i
< wh
; i
++)
503 for (i
= 0; i
< wh
; i
++)
504 if (grid
[i
] == POSSGEM
) {
509 while (head
< tail
) {
513 if (maxdist
< dist
[pos
])
519 for (d
= 0; d
< DIRECTIONS
; d
++) {
525 if (x2
>= 0 && x2
< w
&& y2
>= 0 && y2
< h
) {
528 dist
[p2
] = dist
[pos
] + 1;
534 assert(head
== wh
&& tail
== wh
);
537 * Now abandon this grid and go round again if maxdist is
538 * above the required threshold.
540 * We can safely start the threshold as low as 2. As we
541 * accumulate failed generation attempts, we gradually
542 * raise it as we get more desperate.
544 if (maxdist
> maxdist_threshold
) {
554 * Now our reachable squares are plausibly evenly
555 * distributed over the grid. I'm not actually going to
556 * _enforce_ that I place the gems in such a way as not to
557 * increase that maxdist value; I'm now just going to trust
558 * to the RNG to pick a sensible subset of the POSSGEMs.
561 for (i
= 0; i
< wh
; i
++)
562 if (grid
[i
] == POSSGEM
)
564 shuffle(list
, j
, sizeof(*list
), rs
);
565 for (i
= 0; i
< j
; i
++)
566 grid
[list
[i
]] = (i
< wh
/5 ? GEM
: BLANK
);
577 static char *new_game_desc(game_params
*params
, random_state
*rs
,
578 char **aux
, int interactive
)
580 return gengrid(params
->w
, params
->h
, rs
);
583 static char *validate_desc(game_params
*params
, char *desc
)
585 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
586 int starts
= 0, gems
= 0, i
;
588 for (i
= 0; i
< wh
; i
++) {
590 return "Not enough data to fill grid";
591 if (desc
[i
] != WALL
&& desc
[i
] != START
&& desc
[i
] != STOP
&&
592 desc
[i
] != GEM
&& desc
[i
] != MINE
&& desc
[i
] != BLANK
)
593 return "Unrecognised character in game description";
594 if (desc
[i
] == START
)
600 return "Too much data to fill grid";
602 return "No starting square specified";
604 return "More than one starting square specified";
606 return "No gems specified";
611 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
613 int w
= params
->w
, h
= params
->h
, wh
= w
*h
;
615 game_state
*state
= snew(game_state
);
617 state
->p
= *params
; /* structure copy */
619 state
->grid
= snewn(wh
, char);
620 assert(strlen(desc
) == wh
);
621 memcpy(state
->grid
, desc
, wh
);
623 state
->px
= state
->py
= -1;
625 for (i
= 0; i
< wh
; i
++) {
626 if (state
->grid
[i
] == START
) {
627 state
->grid
[i
] = STOP
;
630 } else if (state
->grid
[i
] == GEM
) {
635 assert(state
->gems
> 0);
636 assert(state
->px
>= 0 && state
->py
>= 0);
638 state
->distance_moved
= 0;
641 state
->cheated
= FALSE
;
648 static game_state
*dup_game(game_state
*state
)
650 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
;
651 game_state
*ret
= snew(game_state
);
656 ret
->gems
= state
->gems
;
657 ret
->grid
= snewn(wh
, char);
658 ret
->distance_moved
= state
->distance_moved
;
660 memcpy(ret
->grid
, state
->grid
, wh
);
661 ret
->cheated
= state
->cheated
;
662 ret
->soln
= state
->soln
;
664 ret
->soln
->refcount
++;
665 ret
->solnpos
= state
->solnpos
;
670 static void free_game(game_state
*state
)
672 if (state
->soln
&& --state
->soln
->refcount
== 0) {
673 sfree(state
->soln
->list
);
681 * Internal function used by solver.
683 static int move_goes_to(int w
, int h
, char *grid
, int x
, int y
, int d
)
688 * See where we'd get to if we made this move.
690 dr
= -1; /* placate optimiser */
692 if (AT(w
, h
, grid
, x
+DX(d
), y
+DY(d
)) == WALL
) {
693 dr
= DIRECTIONS
; /* hit a wall, so end up stationary */
698 if (AT(w
, h
, grid
, x
, y
) == STOP
) {
699 dr
= DIRECTIONS
; /* hit a stop, so end up stationary */
702 if (AT(w
, h
, grid
, x
, y
) == GEM
) {
703 dr
= d
; /* hit a gem, so we're still moving */
706 if (AT(w
, h
, grid
, x
, y
) == MINE
)
707 return -1; /* hit a mine, so move is invalid */
710 return (y
*w
+x
)*DP1
+dr
;
713 static int compare_integers(const void *av
, const void *bv
)
715 const int *a
= (const int *)av
;
716 const int *b
= (const int *)bv
;
725 static char *solve_game(game_state
*state
, game_state
*currstate
,
726 char *aux
, char **error
)
728 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
;
729 int *nodes
, *nodeindex
, *edges
, *backedges
, *edgei
, *backedgei
, *circuit
;
731 int *dist
, *dist2
, *list
;
733 int circuitlen
, circuitsize
;
734 int head
, tail
, pass
, i
, j
, n
, x
, y
, d
, dd
;
735 char *err
, *soln
, *p
;
738 * Solving Inertia is a question of first building up the graph
739 * of where you can get to from where, and secondly finding a
740 * tour of the graph which takes in every gem.
742 * This is of course a close cousin of the travelling salesman
743 * problem, which is NP-complete; so I rather doubt that any
744 * _optimal_ tour can be found in plausible time. Hence I'll
745 * restrict myself to merely finding a not-too-bad one.
747 * First construct the graph, by bfsing out move by move from
748 * the current player position. Graph vertices will be
749 * - every endpoint of a move (place the ball can be
751 * - every gem (place the ball can go through in motion).
752 * Vertices of this type have an associated direction, since
753 * if a gem can be collected by sliding through it in two
754 * different directions it doesn't follow that you can
755 * change direction at it.
757 * I'm going to refer to a non-directional vertex as
758 * (y*w+x)*DP1+DIRECTIONS, and a directional one as
763 * nodeindex[] maps node codes as shown above to numeric
764 * indices in the nodes[] array.
766 nodeindex
= snewn(DP1
*wh
, int);
767 for (i
= 0; i
< DP1
*wh
; i
++)
771 * Do the bfs to find all the interesting graph nodes.
773 nodes
= snewn(DP1
*wh
, int);
776 nodes
[tail
] = (currstate
->py
* w
+ currstate
->px
) * DP1
+ DIRECTIONS
;
777 nodeindex
[nodes
[0]] = tail
;
780 while (head
< tail
) {
781 int nc
= nodes
[head
++], nnc
;
786 * Plot all possible moves from this node. If the node is
787 * directed, there's only one.
789 for (dd
= 0; dd
< DIRECTIONS
; dd
++) {
794 if (d
< DIRECTIONS
&& d
!= dd
)
797 nnc
= move_goes_to(w
, h
, currstate
->grid
, x
, y
, dd
);
798 if (nnc
>= 0 && nnc
!= nc
) {
799 if (nodeindex
[nnc
] < 0) {
801 nodeindex
[nnc
] = tail
;
810 * Now we know how many nodes we have, allocate the edge array
811 * and go through setting up the edges.
813 edges
= snewn(DIRECTIONS
*n
, int);
814 edgei
= snewn(n
+1, int);
817 for (i
= 0; i
< n
; i
++) {
827 for (dd
= 0; dd
< DIRECTIONS
; dd
++) {
830 if (d
>= DIRECTIONS
|| d
== dd
) {
831 nnc
= move_goes_to(w
, h
, currstate
->grid
, x
, y
, dd
);
833 if (nnc
>= 0 && nnc
!= nc
)
834 edges
[nedges
++] = nodeindex
[nnc
];
841 * Now set up the backedges array.
843 backedges
= snewn(nedges
, int);
844 backedgei
= snewn(n
+1, int);
845 for (i
= j
= 0; i
< nedges
; i
++) {
846 while (j
+1 < n
&& i
>= edgei
[j
+1])
848 backedges
[i
] = edges
[i
] * n
+ j
;
850 qsort(backedges
, nedges
, sizeof(int), compare_integers
);
852 for (i
= j
= 0; i
< nedges
; i
++) {
853 int k
= backedges
[i
] / n
;
858 backedgei
[n
] = nedges
;
861 * Set up the initial tour. At all times, our tour is a circuit
862 * of graph vertices (which may, and probably will often,
863 * repeat vertices). To begin with, it's got exactly one vertex
864 * in it, which is the player's current starting point.
867 circuit
= snewn(circuitsize
, int);
869 circuit
[circuitlen
++] = 0; /* node index 0 is the starting posn */
872 * Track which gems are as yet unvisited.
874 unvisited
= snewn(wh
, int);
875 for (i
= 0; i
< wh
; i
++)
876 unvisited
[i
] = FALSE
;
877 for (i
= 0; i
< wh
; i
++)
878 if (currstate
->grid
[i
] == GEM
)
882 * Allocate space for doing bfses inside the main loop.
884 dist
= snewn(n
, int);
885 dist2
= snewn(n
, int);
886 list
= snewn(n
, int);
892 * Now enter the main loop, in each iteration of which we
893 * extend the tour to take in an as yet uncollected gem.
896 int target
, n1
, n2
, bestdist
, extralen
, targetpos
;
898 #ifdef TSP_DIAGNOSTICS
899 printf("circuit is");
900 for (i
= 0; i
< circuitlen
; i
++) {
901 int nc
= nodes
[circuit
[i
]];
902 printf(" (%d,%d,%d)", nc
/DP1
%w
, nc
/(DP1
*w
), nc
%DP1
);
905 printf("moves are ");
906 x
= nodes
[circuit
[0]] / DP1
% w
;
907 y
= nodes
[circuit
[0]] / DP1
/ w
;
908 for (i
= 1; i
< circuitlen
; i
++) {
910 if (nodes
[circuit
[i
]] % DP1
!= DIRECTIONS
)
912 x2
= nodes
[circuit
[i
]] / DP1
% w
;
913 y2
= nodes
[circuit
[i
]] / DP1
/ w
;
914 dx
= (x2
> x ?
+1 : x2
< x ?
-1 : 0);
915 dy
= (y2
> y ?
+1 : y2
< y ?
-1 : 0);
916 for (d
= 0; d
< DIRECTIONS
; d
++)
917 if (DX(d
) == dx
&& DY(d
) == dy
)
918 printf("%c", "89632147"[d
]);
926 * First, start a pair of bfses at _every_ vertex currently
927 * in the tour, and extend them outwards to find the
928 * nearest as yet unreached gem vertex.
930 * This is largely a heuristic: we could pick _any_ doubly
931 * reachable node here and still get a valid tour as
932 * output. I hope that picking a nearby one will result in
933 * generally good tours.
935 for (pass
= 0; pass
< 2; pass
++) {
936 int *ep
= (pass
== 0 ? edges
: backedges
);
937 int *ei
= (pass
== 0 ? edgei
: backedgei
);
938 int *dp
= (pass
== 0 ? dist
: dist2
);
940 for (i
= 0; i
< n
; i
++)
942 for (i
= 0; i
< circuitlen
; i
++) {
949 while (head
< tail
) {
950 int ni
= list
[head
++];
951 for (i
= ei
[ni
]; i
< ei
[ni
+1]; i
++) {
953 if (ti
>= 0 && dp
[ti
] < 0) {
960 /* Now find the nearest unvisited gem. */
963 for (i
= 0; i
< n
; i
++) {
964 if (unvisited
[nodes
[i
] / DP1
] &&
965 dist
[i
] >= 0 && dist2
[i
] >= 0) {
966 int thisdist
= dist
[i
] + dist2
[i
];
967 if (bestdist
< 0 || bestdist
> thisdist
) {
976 * If we get to here, we haven't found a gem we can get
977 * at all, which means we terminate this loop.
983 * Now we have a graph vertex at list[tail-1] which is an
984 * unvisited gem. We want to add that vertex to our tour.
985 * So we run two more breadth-first searches: one starting
986 * from that vertex and following forward edges, and
987 * another starting from the same vertex and following
988 * backward edges. This allows us to determine, for each
989 * node on the current tour, how quickly we can get both to
990 * and from the target vertex from that node.
992 #ifdef TSP_DIAGNOSTICS
993 printf("target node is %d (%d,%d,%d)\n", target
, nodes
[target
]/DP1
%w
,
994 nodes
[target
]/DP1
/w
, nodes
[target
]%DP1
);
997 for (pass
= 0; pass
< 2; pass
++) {
998 int *ep
= (pass
== 0 ? edges
: backedges
);
999 int *ei
= (pass
== 0 ? edgei
: backedgei
);
1000 int *dp
= (pass
== 0 ? dist
: dist2
);
1002 for (i
= 0; i
< n
; i
++)
1007 list
[tail
++] = target
;
1009 while (head
< tail
) {
1010 int ni
= list
[head
++];
1011 for (i
= ei
[ni
]; i
< ei
[ni
+1]; i
++) {
1013 if (ti
>= 0 && dp
[ti
] < 0) {
1014 dp
[ti
] = dp
[ni
] + 1;
1015 /*printf("pass %d: set dist of vertex %d to %d (via %d)\n", pass, ti, dp[ti], ni);*/
1023 * Now for every node n, dist[n] gives the length of the
1024 * shortest path from the target vertex to n, and dist2[n]
1025 * gives the length of the shortest path from n to the
1028 * Our next step is to search linearly along the tour to
1029 * find the optimum place to insert a trip to the target
1030 * vertex and back. Our two options are either
1031 * (a) to find two adjacent vertices A,B in the tour and
1032 * replace the edge A->B with the path A->target->B
1033 * (b) to find a single vertex X in the tour and replace
1034 * it with the complete round trip X->target->X.
1035 * We do whichever takes the fewest moves.
1039 for (i
= 0; i
< circuitlen
; i
++) {
1043 * Try a round trip from vertex i.
1045 if (dist
[circuit
[i
]] >= 0 &&
1046 dist2
[circuit
[i
]] >= 0) {
1047 thisdist
= dist
[circuit
[i
]] + dist2
[circuit
[i
]];
1048 if (bestdist
< 0 || thisdist
< bestdist
) {
1049 bestdist
= thisdist
;
1055 * Try a trip from vertex i via target to vertex i+1.
1057 if (i
+1 < circuitlen
&&
1058 dist2
[circuit
[i
]] >= 0 &&
1059 dist
[circuit
[i
+1]] >= 0) {
1060 thisdist
= dist2
[circuit
[i
]] + dist
[circuit
[i
+1]];
1061 if (bestdist
< 0 || thisdist
< bestdist
) {
1062 bestdist
= thisdist
;
1070 * We couldn't find a round trip taking in this gem _at
1073 err
= "Unable to find a solution from this starting point";
1076 #ifdef TSP_DIAGNOSTICS
1077 printf("insertion point: n1=%d, n2=%d, dist=%d\n", n1
, n2
, bestdist
);
1080 #ifdef TSP_DIAGNOSTICS
1081 printf("circuit before lengthening is");
1082 for (i
= 0; i
< circuitlen
; i
++) {
1083 printf(" %d", circuit
[i
]);
1089 * Now actually lengthen the tour to take in this round
1092 extralen
= dist2
[circuit
[n1
]] + dist
[circuit
[n2
]];
1095 circuitlen
+= extralen
;
1096 if (circuitlen
>= circuitsize
) {
1097 circuitsize
= circuitlen
+ 256;
1098 circuit
= sresize(circuit
, circuitsize
, int);
1100 memmove(circuit
+ n2
+ extralen
, circuit
+ n2
,
1101 (circuitlen
- n2
- extralen
) * sizeof(int));
1104 #ifdef TSP_DIAGNOSTICS
1105 printf("circuit in middle of lengthening is");
1106 for (i
= 0; i
< circuitlen
; i
++) {
1107 printf(" %d", circuit
[i
]);
1113 * Find the shortest-path routes to and from the target,
1114 * and write them into the circuit.
1116 targetpos
= n1
+ dist2
[circuit
[n1
]];
1117 assert(targetpos
- dist2
[circuit
[n1
]] == n1
);
1118 assert(targetpos
+ dist
[circuit
[n2
]] == n2
);
1119 for (pass
= 0; pass
< 2; pass
++) {
1120 int dir
= (pass
== 0 ?
-1 : +1);
1121 int *ep
= (pass
== 0 ? backedges
: edges
);
1122 int *ei
= (pass
== 0 ? backedgei
: edgei
);
1123 int *dp
= (pass
== 0 ? dist
: dist2
);
1124 int nn
= (pass
== 0 ? n2
: n1
);
1125 int ni
= circuit
[nn
], ti
, dest
= nn
;
1133 /*printf("pass %d: looking at vertex %d\n", pass, ni);*/
1134 for (i
= ei
[ni
]; i
< ei
[ni
+1]; i
++) {
1136 if (ti
>= 0 && dp
[ti
] == dp
[ni
] - 1)
1139 assert(i
< ei
[ni
+1] && ti
>= 0);
1144 #ifdef TSP_DIAGNOSTICS
1145 printf("circuit after lengthening is");
1146 for (i
= 0; i
< circuitlen
; i
++) {
1147 printf(" %d", circuit
[i
]);
1153 * Finally, mark all gems that the new piece of circuit
1154 * passes through as visited.
1156 for (i
= n1
; i
<= n2
; i
++) {
1157 int pos
= nodes
[circuit
[i
]] / DP1
;
1158 assert(pos
>= 0 && pos
< wh
);
1159 unvisited
[pos
] = FALSE
;
1163 #ifdef TSP_DIAGNOSTICS
1164 printf("before reduction, moves are ");
1165 x
= nodes
[circuit
[0]] / DP1
% w
;
1166 y
= nodes
[circuit
[0]] / DP1
/ w
;
1167 for (i
= 1; i
< circuitlen
; i
++) {
1169 if (nodes
[circuit
[i
]] % DP1
!= DIRECTIONS
)
1171 x2
= nodes
[circuit
[i
]] / DP1
% w
;
1172 y2
= nodes
[circuit
[i
]] / DP1
/ w
;
1173 dx
= (x2
> x ?
+1 : x2
< x ?
-1 : 0);
1174 dy
= (y2
> y ?
+1 : y2
< y ?
-1 : 0);
1175 for (d
= 0; d
< DIRECTIONS
; d
++)
1176 if (DX(d
) == dx
&& DY(d
) == dy
)
1177 printf("%c", "89632147"[d
]);
1185 * That's got a basic solution. Now optimise it by removing
1186 * redundant sections of the circuit: it's entirely possible
1187 * that a piece of circuit we carefully inserted at one stage
1188 * to collect a gem has become pointless because the steps
1189 * required to collect some _later_ gem necessarily passed
1190 * through the same one.
1192 * So first we go through and work out how many times each gem
1193 * is collected. Then we look for maximal sections of circuit
1194 * which are redundant in the sense that their removal would
1195 * not reduce any gem's collection count to zero, and replace
1196 * each one with a bfs-derived fastest path between their
1200 int oldlen
= circuitlen
;
1203 for (dir
= +1; dir
>= -1; dir
-= 2) {
1205 for (i
= 0; i
< wh
; i
++)
1207 for (i
= 0; i
< circuitlen
; i
++) {
1208 int xy
= nodes
[circuit
[i
]] / DP1
;
1209 if (currstate
->grid
[xy
] == GEM
)
1214 * If there's any gem we didn't end up visiting at all,
1217 for (i
= 0; i
< wh
; i
++) {
1218 if (currstate
->grid
[i
] == GEM
&& unvisited
[i
] == 0) {
1219 err
= "Unable to find a solution from this starting point";
1226 for (i
= j
= (dir
> 0 ?
0 : circuitlen
-1);
1227 i
< circuitlen
&& i
>= 0;
1229 int xy
= nodes
[circuit
[i
]] / DP1
;
1230 if (currstate
->grid
[xy
] == GEM
&& unvisited
[xy
] > 1) {
1232 } else if (currstate
->grid
[xy
] == GEM
|| i
== circuitlen
-1) {
1234 * circuit[i] collects a gem for the only time,
1235 * or is the last node in the circuit.
1236 * Therefore it cannot be removed; so we now
1237 * want to replace the path from circuit[j] to
1238 * circuit[i] with a bfs-shortest path.
1240 int p
, q
, k
, dest
, ni
, ti
, thisdist
;
1243 * Set up the upper and lower bounds of the
1249 #ifdef TSP_DIAGNOSTICS
1250 printf("optimising section from %d - %d\n", p
, q
);
1253 for (k
= 0; k
< n
; k
++)
1257 dist
[circuit
[p
]] = 0;
1258 list
[tail
++] = circuit
[p
];
1260 while (head
< tail
&& dist
[circuit
[q
]] < 0) {
1261 int ni
= list
[head
++];
1262 for (k
= edgei
[ni
]; k
< edgei
[ni
+1]; k
++) {
1264 if (ti
>= 0 && dist
[ti
] < 0) {
1265 dist
[ti
] = dist
[ni
] + 1;
1271 thisdist
= dist
[circuit
[q
]];
1272 assert(thisdist
>= 0 && thisdist
<= q
-p
);
1274 memmove(circuit
+p
+thisdist
, circuit
+q
,
1275 (circuitlen
- q
) * sizeof(int));
1281 i
= q
; /* resume loop from the right place */
1283 #ifdef TSP_DIAGNOSTICS
1284 printf("new section runs from %d - %d\n", p
, q
);
1292 /* printf("dest=%d circuitlen=%d ni=%d dist[ni]=%d\n", dest, circuitlen, ni, dist[ni]); */
1298 for (k
= backedgei
[ni
]; k
< backedgei
[ni
+1]; k
++) {
1300 if (ti
>= 0 && dist
[ti
] == dist
[ni
] - 1)
1303 assert(k
< backedgei
[ni
+1] && ti
>= 0);
1308 * Now re-increment the visit counts for the
1312 int xy
= nodes
[circuit
[p
]] / DP1
;
1313 if (currstate
->grid
[xy
] == GEM
)
1319 #ifdef TSP_DIAGNOSTICS
1320 printf("during reduction, circuit is");
1321 for (k
= 0; k
< circuitlen
; k
++) {
1322 int nc
= nodes
[circuit
[k
]];
1323 printf(" (%d,%d,%d)", nc
/DP1
%w
, nc
/(DP1
*w
), nc
%DP1
);
1326 printf("moves are ");
1327 x
= nodes
[circuit
[0]] / DP1
% w
;
1328 y
= nodes
[circuit
[0]] / DP1
/ w
;
1329 for (k
= 1; k
< circuitlen
; k
++) {
1331 if (nodes
[circuit
[k
]] % DP1
!= DIRECTIONS
)
1333 x2
= nodes
[circuit
[k
]] / DP1
% w
;
1334 y2
= nodes
[circuit
[k
]] / DP1
/ w
;
1335 dx
= (x2
> x ?
+1 : x2
< x ?
-1 : 0);
1336 dy
= (y2
> y ?
+1 : y2
< y ?
-1 : 0);
1337 for (d
= 0; d
< DIRECTIONS
; d
++)
1338 if (DX(d
) == dx
&& DY(d
) == dy
)
1339 printf("%c", "89632147"[d
]);
1348 #ifdef TSP_DIAGNOSTICS
1349 printf("after reduction, moves are ");
1350 x
= nodes
[circuit
[0]] / DP1
% w
;
1351 y
= nodes
[circuit
[0]] / DP1
/ w
;
1352 for (i
= 1; i
< circuitlen
; i
++) {
1354 if (nodes
[circuit
[i
]] % DP1
!= DIRECTIONS
)
1356 x2
= nodes
[circuit
[i
]] / DP1
% w
;
1357 y2
= nodes
[circuit
[i
]] / DP1
/ w
;
1358 dx
= (x2
> x ?
+1 : x2
< x ?
-1 : 0);
1359 dy
= (y2
> y ?
+1 : y2
< y ?
-1 : 0);
1360 for (d
= 0; d
< DIRECTIONS
; d
++)
1361 if (DX(d
) == dx
&& DY(d
) == dy
)
1362 printf("%c", "89632147"[d
]);
1371 * If we've managed an entire reduction pass in each
1372 * direction and not made the solution any shorter, we're
1375 if (circuitlen
== oldlen
)
1380 * Encode the solution as a move string.
1383 soln
= snewn(circuitlen
+2, char);
1386 x
= nodes
[circuit
[0]] / DP1
% w
;
1387 y
= nodes
[circuit
[0]] / DP1
/ w
;
1388 for (i
= 1; i
< circuitlen
; i
++) {
1390 if (nodes
[circuit
[i
]] % DP1
!= DIRECTIONS
)
1392 x2
= nodes
[circuit
[i
]] / DP1
% w
;
1393 y2
= nodes
[circuit
[i
]] / DP1
/ w
;
1394 dx
= (x2
> x ?
+1 : x2
< x ?
-1 : 0);
1395 dy
= (y2
> y ?
+1 : y2
< y ?
-1 : 0);
1396 for (d
= 0; d
< DIRECTIONS
; d
++)
1397 if (DX(d
) == dx
&& DY(d
) == dy
) {
1401 assert(d
< DIRECTIONS
);
1406 assert(p
- soln
< circuitlen
+2);
1427 static char *game_text_format(game_state
*state
)
1440 static game_ui
*new_ui(game_state
*state
)
1442 game_ui
*ui
= snew(game_ui
);
1443 ui
->anim_length
= 0.0F
;
1446 ui
->just_made_move
= FALSE
;
1447 ui
->just_died
= FALSE
;
1451 static void free_ui(game_ui
*ui
)
1456 static char *encode_ui(game_ui
*ui
)
1460 * The deaths counter needs preserving across a serialisation.
1462 sprintf(buf
, "D%d", ui
->deaths
);
1466 static void decode_ui(game_ui
*ui
, char *encoding
)
1469 sscanf(encoding
, "D%d%n", &ui
->deaths
, &p
);
1472 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1473 game_state
*newstate
)
1476 * Increment the deaths counter. We only do this if
1477 * ui->just_made_move is set (redoing a suicide move doesn't
1478 * kill you _again_), and also we only do it if the game wasn't
1479 * already completed (once you're finished, you can play).
1481 if (!oldstate
->dead
&& newstate
->dead
&& ui
->just_made_move
&&
1484 ui
->just_died
= TRUE
;
1486 ui
->just_died
= FALSE
;
1488 ui
->just_made_move
= FALSE
;
1491 struct game_drawstate
{
1495 unsigned short *grid
;
1496 blitter
*player_background
;
1497 int player_bg_saved
, pbgx
, pbgy
;
1500 #define PREFERRED_TILESIZE 32
1501 #define TILESIZE (ds->tilesize)
1502 #define BORDER (TILESIZE)
1503 #define HIGHLIGHT_WIDTH (TILESIZE / 10)
1504 #define COORD(x) ( (x) * TILESIZE + BORDER )
1505 #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
1507 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1508 int x
, int y
, int button
)
1510 int w
= state
->p
.w
, h
= state
->p
.h
/*, wh = w*h */;
1516 if (button
== LEFT_BUTTON
) {
1518 * Mouse-clicking near the target point (or, more
1519 * accurately, in the appropriate octant) is an alternative
1520 * way to input moves.
1523 if (FROMCOORD(x
) != state
->px
|| FROMCOORD(y
) != state
->py
) {
1527 dx
= FROMCOORD(x
) - state
->px
;
1528 dy
= FROMCOORD(y
) - state
->py
;
1529 /* I pass dx,dy rather than dy,dx so that the octants
1530 * end up the right way round. */
1531 angle
= atan2(dx
, -dy
);
1533 angle
= (angle
+ (PI
/8)) / (PI
/4);
1534 assert(angle
> -16.0F
);
1535 dir
= (int)(angle
+ 16.0F
) & 7;
1537 } else if (button
== CURSOR_UP
|| button
== (MOD_NUM_KEYPAD
| '8'))
1539 else if (button
== CURSOR_DOWN
|| button
== (MOD_NUM_KEYPAD
| '2'))
1541 else if (button
== CURSOR_LEFT
|| button
== (MOD_NUM_KEYPAD
| '4'))
1543 else if (button
== CURSOR_RIGHT
|| button
== (MOD_NUM_KEYPAD
| '6'))
1545 else if (button
== (MOD_NUM_KEYPAD
| '7'))
1547 else if (button
== (MOD_NUM_KEYPAD
| '1'))
1549 else if (button
== (MOD_NUM_KEYPAD
| '9'))
1551 else if (button
== (MOD_NUM_KEYPAD
| '3'))
1553 else if (button
== ' ' && state
->soln
&& state
->solnpos
< state
->soln
->len
)
1554 dir
= state
->soln
->list
[state
->solnpos
];
1560 * Reject the move if we can't make it at all due to a wall
1563 if (AT(w
, h
, state
->grid
, state
->px
+DX(dir
), state
->py
+DY(dir
)) == WALL
)
1567 * Reject the move if we're dead!
1573 * Otherwise, we can make the move. All we need to specify is
1576 ui
->just_made_move
= TRUE
;
1577 sprintf(buf
, "%d", dir
);
1581 static game_state
*execute_move(game_state
*state
, char *move
)
1583 int w
= state
->p
.w
, h
= state
->p
.h
/*, wh = w*h */;
1592 * This is a solve move, so we don't actually _change_ the
1593 * grid but merely set up a stored solution path.
1599 sol
->list
= snewn(len
, unsigned char);
1600 for (i
= 0; i
< len
; i
++)
1601 sol
->list
[i
] = move
[i
] - '0';
1602 ret
= dup_game(state
);
1603 ret
->cheated
= TRUE
;
1611 if (dir
< 0 || dir
>= DIRECTIONS
)
1612 return NULL
; /* huh? */
1617 if (AT(w
, h
, state
->grid
, state
->px
+DX(dir
), state
->py
+DY(dir
)) == WALL
)
1618 return NULL
; /* wall in the way! */
1621 * Now make the move.
1623 ret
= dup_game(state
);
1624 ret
->distance_moved
= 0;
1628 ret
->distance_moved
++;
1630 if (AT(w
, h
, ret
->grid
, ret
->px
, ret
->py
) == GEM
) {
1631 LV_AT(w
, h
, ret
->grid
, ret
->px
, ret
->py
) = BLANK
;
1635 if (AT(w
, h
, ret
->grid
, ret
->px
, ret
->py
) == MINE
) {
1640 if (AT(w
, h
, ret
->grid
, ret
->px
, ret
->py
) == STOP
||
1641 AT(w
, h
, ret
->grid
, ret
->px
+DX(dir
),
1642 ret
->py
+DY(dir
)) == WALL
)
1648 * If this move is the correct next one in the stored
1649 * solution path, advance solnpos.
1651 if (ret
->soln
->list
[ret
->solnpos
] == dir
&&
1652 ret
->solnpos
+1 < ret
->soln
->len
) {
1656 * Otherwise, the user has strayed from the path, so
1657 * the path is no longer valid.
1659 ret
->soln
->refcount
--;
1660 assert(ret
->soln
->refcount
> 0);/* `state' at least still exists */
1669 /* ----------------------------------------------------------------------
1673 static void game_compute_size(game_params
*params
, int tilesize
,
1676 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1677 struct { int tilesize
; } ads
, *ds
= &ads
;
1678 ads
.tilesize
= tilesize
;
1680 *x
= 2 * BORDER
+ 1 + params
->w
* TILESIZE
;
1681 *y
= 2 * BORDER
+ 1 + params
->h
* TILESIZE
;
1684 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1685 game_params
*params
, int tilesize
)
1687 ds
->tilesize
= tilesize
;
1689 assert(!ds
->player_background
); /* set_size is never called twice */
1690 assert(!ds
->player_bg_saved
);
1692 ds
->player_background
= blitter_new(dr
, TILESIZE
, TILESIZE
);
1695 static float *game_colours(frontend
*fe
, int *ncolours
)
1697 float *ret
= snewn(3 * NCOLOURS
, float);
1700 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
1702 ret
[COL_OUTLINE
* 3 + 0] = 0.0F
;
1703 ret
[COL_OUTLINE
* 3 + 1] = 0.0F
;
1704 ret
[COL_OUTLINE
* 3 + 2] = 0.0F
;
1706 ret
[COL_PLAYER
* 3 + 0] = 0.0F
;
1707 ret
[COL_PLAYER
* 3 + 1] = 1.0F
;
1708 ret
[COL_PLAYER
* 3 + 2] = 0.0F
;
1710 ret
[COL_DEAD_PLAYER
* 3 + 0] = 1.0F
;
1711 ret
[COL_DEAD_PLAYER
* 3 + 1] = 0.0F
;
1712 ret
[COL_DEAD_PLAYER
* 3 + 2] = 0.0F
;
1714 ret
[COL_MINE
* 3 + 0] = 0.0F
;
1715 ret
[COL_MINE
* 3 + 1] = 0.0F
;
1716 ret
[COL_MINE
* 3 + 2] = 0.0F
;
1718 ret
[COL_GEM
* 3 + 0] = 0.6F
;
1719 ret
[COL_GEM
* 3 + 1] = 1.0F
;
1720 ret
[COL_GEM
* 3 + 2] = 1.0F
;
1722 for (i
= 0; i
< 3; i
++) {
1723 ret
[COL_WALL
* 3 + i
] = (3 * ret
[COL_BACKGROUND
* 3 + i
] +
1724 1 * ret
[COL_HIGHLIGHT
* 3 + i
]) / 4;
1727 ret
[COL_HINT
* 3 + 0] = 1.0F
;
1728 ret
[COL_HINT
* 3 + 1] = 1.0F
;
1729 ret
[COL_HINT
* 3 + 2] = 0.0F
;
1731 *ncolours
= NCOLOURS
;
1735 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1737 int w
= state
->p
.w
, h
= state
->p
.h
, wh
= w
*h
;
1738 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1743 /* We can't allocate the blitter rectangle for the player background
1744 * until we know what size to make it. */
1745 ds
->player_background
= NULL
;
1746 ds
->player_bg_saved
= FALSE
;
1747 ds
->pbgx
= ds
->pbgy
= -1;
1749 ds
->p
= state
->p
; /* structure copy */
1750 ds
->started
= FALSE
;
1751 ds
->grid
= snewn(wh
, unsigned short);
1752 for (i
= 0; i
< wh
; i
++)
1753 ds
->grid
[i
] = UNDRAWN
;
1758 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1760 if (ds
->player_background
)
1761 blitter_free(dr
, ds
->player_background
);
1766 static void draw_player(drawing
*dr
, game_drawstate
*ds
, int x
, int y
,
1767 int dead
, int hintdir
)
1770 int coords
[DIRECTIONS
*4];
1773 for (d
= 0; d
< DIRECTIONS
; d
++) {
1774 float x1
, y1
, x2
, y2
, x3
, y3
, len
;
1778 len
= sqrt(x1
*x1
+y1
*y1
); x1
/= len
; y1
/= len
;
1782 len
= sqrt(x3
*x3
+y3
*y3
); x3
/= len
; y3
/= len
;
1787 coords
[d
*4+0] = x
+ TILESIZE
/2 + (int)((TILESIZE
*3/7) * x1
);
1788 coords
[d
*4+1] = y
+ TILESIZE
/2 + (int)((TILESIZE
*3/7) * y1
);
1789 coords
[d
*4+2] = x
+ TILESIZE
/2 + (int)((TILESIZE
*3/7) * x2
);
1790 coords
[d
*4+3] = y
+ TILESIZE
/2 + (int)((TILESIZE
*3/7) * y2
);
1792 draw_polygon(dr
, coords
, DIRECTIONS
*2, COL_DEAD_PLAYER
, COL_OUTLINE
);
1794 draw_circle(dr
, x
+ TILESIZE
/2, y
+ TILESIZE
/2,
1795 TILESIZE
/3, COL_PLAYER
, COL_OUTLINE
);
1798 if (!dead
&& hintdir
>= 0) {
1799 float scale
= (DX(hintdir
) && DY(hintdir
) ?
0.8F
: 1.0F
);
1800 int ax
= (TILESIZE
*2/5) * scale
* DX(hintdir
);
1801 int ay
= (TILESIZE
*2/5) * scale
* DY(hintdir
);
1802 int px
= -ay
, py
= ax
;
1803 int ox
= x
+ TILESIZE
/2, oy
= y
+ TILESIZE
/2;
1809 *c
++ = ox
+ px
/9 + ax
*2/3;
1810 *c
++ = oy
+ py
/9 + ay
*2/3;
1811 *c
++ = ox
+ px
/3 + ax
*2/3;
1812 *c
++ = oy
+ py
/3 + ay
*2/3;
1815 *c
++ = ox
- px
/3 + ax
*2/3;
1816 *c
++ = oy
- py
/3 + ay
*2/3;
1817 *c
++ = ox
- px
/9 + ax
*2/3;
1818 *c
++ = oy
- py
/9 + ay
*2/3;
1821 draw_polygon(dr
, coords
, 7, COL_HINT
, COL_OUTLINE
);
1824 draw_update(dr
, x
, y
, TILESIZE
, TILESIZE
);
1827 #define FLASH_DEAD 0x100
1828 #define FLASH_WIN 0x200
1829 #define FLASH_MASK 0x300
1831 static void draw_tile(drawing
*dr
, game_drawstate
*ds
, int x
, int y
, int v
)
1833 int tx
= COORD(x
), ty
= COORD(y
);
1834 int bg
= (v
& FLASH_DEAD ? COL_DEAD_PLAYER
:
1835 v
& FLASH_WIN ? COL_HIGHLIGHT
: COL_BACKGROUND
);
1839 clip(dr
, tx
+1, ty
+1, TILESIZE
-1, TILESIZE
-1);
1840 draw_rect(dr
, tx
+1, ty
+1, TILESIZE
-1, TILESIZE
-1, bg
);
1845 coords
[0] = tx
+ TILESIZE
;
1846 coords
[1] = ty
+ TILESIZE
;
1847 coords
[2] = tx
+ TILESIZE
;
1850 coords
[5] = ty
+ TILESIZE
;
1851 draw_polygon(dr
, coords
, 3, COL_LOWLIGHT
, COL_LOWLIGHT
);
1855 draw_polygon(dr
, coords
, 3, COL_HIGHLIGHT
, COL_HIGHLIGHT
);
1857 draw_rect(dr
, tx
+ 1 + HIGHLIGHT_WIDTH
, ty
+ 1 + HIGHLIGHT_WIDTH
,
1858 TILESIZE
- 2*HIGHLIGHT_WIDTH
,
1859 TILESIZE
- 2*HIGHLIGHT_WIDTH
, COL_WALL
);
1860 } else if (v
== MINE
) {
1861 int cx
= tx
+ TILESIZE
/ 2;
1862 int cy
= ty
+ TILESIZE
/ 2;
1863 int r
= TILESIZE
/ 2 - 3;
1865 int xdx
= 1, xdy
= 0, ydx
= 0, ydy
= 1;
1868 for (i
= 0; i
< 4*5*2; i
+= 5*2) {
1869 coords
[i
+2*0+0] = cx
- r
/6*xdx
+ r
*4/5*ydx
;
1870 coords
[i
+2*0+1] = cy
- r
/6*xdy
+ r
*4/5*ydy
;
1871 coords
[i
+2*1+0] = cx
- r
/6*xdx
+ r
*ydx
;
1872 coords
[i
+2*1+1] = cy
- r
/6*xdy
+ r
*ydy
;
1873 coords
[i
+2*2+0] = cx
+ r
/6*xdx
+ r
*ydx
;
1874 coords
[i
+2*2+1] = cy
+ r
/6*xdy
+ r
*ydy
;
1875 coords
[i
+2*3+0] = cx
+ r
/6*xdx
+ r
*4/5*ydx
;
1876 coords
[i
+2*3+1] = cy
+ r
/6*xdy
+ r
*4/5*ydy
;
1877 coords
[i
+2*4+0] = cx
+ r
*3/5*xdx
+ r
*3/5*ydx
;
1878 coords
[i
+2*4+1] = cy
+ r
*3/5*xdy
+ r
*3/5*ydy
;
1888 draw_polygon(dr
, coords
, 5*4, COL_MINE
, COL_MINE
);
1890 draw_rect(dr
, cx
-r
/3, cy
-r
/3, r
/3, r
/4, COL_HIGHLIGHT
);
1891 } else if (v
== STOP
) {
1892 draw_circle(dr
, tx
+ TILESIZE
/2, ty
+ TILESIZE
/2,
1893 TILESIZE
*3/7, -1, COL_OUTLINE
);
1894 draw_rect(dr
, tx
+ TILESIZE
*3/7, ty
+1,
1895 TILESIZE
- 2*(TILESIZE
*3/7) + 1, TILESIZE
-1, bg
);
1896 draw_rect(dr
, tx
+1, ty
+ TILESIZE
*3/7,
1897 TILESIZE
-1, TILESIZE
- 2*(TILESIZE
*3/7) + 1, bg
);
1898 } else if (v
== GEM
) {
1901 coords
[0] = tx
+TILESIZE
/2;
1902 coords
[1] = ty
+TILESIZE
*1/7;
1903 coords
[2] = tx
+TILESIZE
*1/7;
1904 coords
[3] = ty
+TILESIZE
/2;
1905 coords
[4] = tx
+TILESIZE
/2;
1906 coords
[5] = ty
+TILESIZE
-TILESIZE
*1/7;
1907 coords
[6] = tx
+TILESIZE
-TILESIZE
*1/7;
1908 coords
[7] = ty
+TILESIZE
/2;
1910 draw_polygon(dr
, coords
, 4, COL_GEM
, COL_OUTLINE
);
1914 draw_update(dr
, tx
, ty
, TILESIZE
, TILESIZE
);
1917 #define BASE_ANIM_LENGTH 0.1F
1918 #define FLASH_LENGTH 0.3F
1920 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1921 game_state
*state
, int dir
, game_ui
*ui
,
1922 float animtime
, float flashtime
)
1924 int w
= state
->p
.w
, h
= state
->p
.h
/*, wh = w*h */;
1933 !((int)(flashtime
* 3 / FLASH_LENGTH
) % 2))
1934 flashtype
= ui
->flashtype
;
1939 * Erase the player sprite.
1941 if (ds
->player_bg_saved
) {
1942 assert(ds
->player_background
);
1943 blitter_load(dr
, ds
->player_background
, ds
->pbgx
, ds
->pbgy
);
1944 draw_update(dr
, ds
->pbgx
, ds
->pbgy
, TILESIZE
, TILESIZE
);
1945 ds
->player_bg_saved
= FALSE
;
1949 * Initialise a fresh drawstate.
1955 * Blank out the window initially.
1957 game_compute_size(&ds
->p
, TILESIZE
, &wid
, &ht
);
1958 draw_rect(dr
, 0, 0, wid
, ht
, COL_BACKGROUND
);
1959 draw_update(dr
, 0, 0, wid
, ht
);
1962 * Draw the grid lines.
1964 for (y
= 0; y
<= h
; y
++)
1965 draw_line(dr
, COORD(0), COORD(y
), COORD(w
), COORD(y
),
1967 for (x
= 0; x
<= w
; x
++)
1968 draw_line(dr
, COORD(x
), COORD(0), COORD(x
), COORD(h
),
1975 * If we're in the process of animating a move, let's start by
1976 * working out how far the player has moved from their _older_
1980 ap
= animtime
/ ui
->anim_length
;
1981 player_dist
= ap
* (dir
> 0 ? state
: oldstate
)->distance_moved
;
1988 * Draw the grid contents.
1990 * We count the gems as we go round this loop, for the purposes
1991 * of the status bar. Of course we have a gems counter in the
1992 * game_state already, but if we do the counting in this loop
1993 * then it tracks gems being picked up in a sliding move, and
1994 * updates one by one.
1997 for (y
= 0; y
< h
; y
++)
1998 for (x
= 0; x
< w
; x
++) {
1999 unsigned short v
= (unsigned char)state
->grid
[y
*w
+x
];
2002 * Special case: if the player is in the process of
2003 * moving over a gem, we draw the gem iff they haven't
2006 if (oldstate
&& oldstate
->grid
[y
*w
+x
] != state
->grid
[y
*w
+x
]) {
2008 * Compute the distance from this square to the
2009 * original player position.
2011 int dist
= max(abs(x
- oldstate
->px
), abs(y
- oldstate
->py
));
2014 * If the player has reached here, use the new grid
2015 * element. Otherwise use the old one.
2017 if (player_dist
< dist
)
2018 v
= oldstate
->grid
[y
*w
+x
];
2020 v
= state
->grid
[y
*w
+x
];
2024 * Special case: erase the mine the dead player is
2025 * sitting on. Only at the end of the move.
2027 if (v
== MINE
&& !oldstate
&& state
->dead
&&
2028 x
== state
->px
&& y
== state
->py
)
2036 if (ds
->grid
[y
*w
+x
] != v
) {
2037 draw_tile(dr
, ds
, x
, y
, v
);
2038 ds
->grid
[y
*w
+x
] = v
;
2043 * Gem counter in the status bar. We replace it with
2044 * `COMPLETED!' when it reaches zero ... or rather, when the
2045 * _current state_'s gem counter is zero. (Thus, `Gems: 0' is
2046 * shown between the collection of the last gem and the
2047 * completion of the move animation that did it.)
2049 if (state
->dead
&& (!oldstate
|| oldstate
->dead
)) {
2050 sprintf(status
, "DEAD!");
2051 } else if (state
->gems
|| (oldstate
&& oldstate
->gems
)) {
2053 sprintf(status
, "Auto-solver used. ");
2056 sprintf(status
+ strlen(status
), "Gems: %d", gems
);
2057 } else if (state
->cheated
) {
2058 sprintf(status
, "Auto-solved.");
2060 sprintf(status
, "COMPLETED!");
2062 /* We subtract one from the visible death counter if we're still
2063 * animating the move at the end of which the death took place. */
2064 deaths
= ui
->deaths
;
2065 if (oldstate
&& ui
->just_died
) {
2070 sprintf(status
+ strlen(status
), " Deaths: %d", deaths
);
2071 status_bar(dr
, status
);
2074 * Draw the player sprite.
2076 assert(!ds
->player_bg_saved
);
2077 assert(ds
->player_background
);
2080 nx
= COORD(state
->px
);
2081 ny
= COORD(state
->py
);
2083 ox
= COORD(oldstate
->px
);
2084 oy
= COORD(oldstate
->py
);
2089 ds
->pbgx
= ox
+ ap
* (nx
- ox
);
2090 ds
->pbgy
= oy
+ ap
* (ny
- oy
);
2092 blitter_save(dr
, ds
->player_background
, ds
->pbgx
, ds
->pbgy
);
2093 draw_player(dr
, ds
, ds
->pbgx
, ds
->pbgy
,
2094 (state
->dead
&& !oldstate
),
2095 (!oldstate
&& state
->soln ?
2096 state
->soln
->list
[state
->solnpos
] : -1));
2097 ds
->player_bg_saved
= TRUE
;
2100 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2101 int dir
, game_ui
*ui
)
2105 dist
= newstate
->distance_moved
;
2107 dist
= oldstate
->distance_moved
;
2108 ui
->anim_length
= sqrt(dist
) * BASE_ANIM_LENGTH
;
2109 return ui
->anim_length
;
2112 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2113 int dir
, game_ui
*ui
)
2115 if (!oldstate
->dead
&& newstate
->dead
) {
2116 ui
->flashtype
= FLASH_DEAD
;
2117 return FLASH_LENGTH
;
2118 } else if (oldstate
->gems
&& !newstate
->gems
) {
2119 ui
->flashtype
= FLASH_WIN
;
2120 return FLASH_LENGTH
;
2125 static int game_timing_state(game_state
*state
, game_ui
*ui
)
2130 static void game_print_size(game_params
*params
, float *x
, float *y
)
2134 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
2139 #define thegame inertia
2142 const struct game thegame
= {
2143 "Inertia", "games.inertia",
2150 TRUE
, game_configure
, custom_params
,
2158 FALSE
, game_text_format
,
2166 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
2169 game_free_drawstate
,
2173 FALSE
, FALSE
, game_print_size
, game_print
,
2174 TRUE
, /* wants_statusbar */
2175 FALSE
, game_timing_state
,