2 * undead: Implementation of Haunted Mirror Mazes
4 * http://www.janko.at/Raetsel/Spukschloss/index.htm
6 * Puzzle definition is the total number of each monster type, the
7 * grid definition, and the list of sightings (clockwise, starting
8 * from top left corner)
10 * Example: (Janko puzzle No. 1,
11 * http://www.janko.at/Raetsel/Spukschloss/001.a.htm )
13 * Ghosts: 0 Vampires: 2 Zombies: 6
22 * would be encoded into:
23 * 4x4:0,2,6,LLaRLaRaRaRdL,2,1,1,1,2,2,2,2,2,2,3,3,3,0,0,1
25 * Additionally, the game description can contain monsters fixed at a
26 * certain grid position. The internal generator does not (yet) use
27 * this feature, but this is needed to enter puzzles like Janko No.
28 * 14, which is encoded as:
29 * 8x5:12,12,0,LaRbLaRaLaRLbRaVaVaGRaRaRaLbLaRbRLb,0,2,0,2,2,1,2,1,3,1,0,1,8,4,3,0,0,2,3,2,7,2,1,6,2,1
59 #define ENUM(upper,title,lower) DIFF_ ## upper,
60 #define TITLE(upper,title,lower) #title,
61 #define ENCODE(upper,title,lower) #lower
62 #define CONFIG(upper,title,lower) ":" #title
63 enum { DIFFLIST(ENUM
) DIFFCOUNT
};
64 static char const *const undead_diffnames
[] = { DIFFLIST(TITLE
) "(count)" };
65 static char const undead_diffchars
[] = DIFFLIST(ENCODE
);
66 #define DIFFCONFIG DIFFLIST(CONFIG)
69 int w
; /* Grid width */
70 int h
; /* Grid height */
71 int diff
; /* Puzzle difficulty */
74 static const struct game_params undead_presets
[] = {
76 { 4, 4, DIFF_NORMAL
},
77 { 4, 4, DIFF_TRICKY
},
79 { 5, 5, DIFF_NORMAL
},
80 { 5, 5, DIFF_TRICKY
},
85 #define DEFAULT_PRESET 1
87 static game_params
*default_params(void) {
88 game_params
*ret
= snew(game_params
);
90 *ret
= undead_presets
[DEFAULT_PRESET
];
94 static int game_fetch_preset(int i
, char **name
, game_params
**params
) {
98 if (i
< 0 || i
>= lenof(undead_presets
)) return FALSE
;
100 ret
= default_params();
101 *ret
= undead_presets
[i
]; /* struct copy */
104 sprintf(buf
, "%dx%d %s",
105 undead_presets
[i
].w
, undead_presets
[i
].h
,
106 undead_diffnames
[undead_presets
[i
].diff
]);
112 static void free_params(game_params
*params
) {
116 static game_params
*dup_params(game_params
*params
) {
117 game_params
*ret
= snew(game_params
);
118 *ret
= *params
; /* structure copy */
122 static void decode_params(game_params
*params
, char const *string
) {
123 params
->w
= params
->h
= atoi(string
);
125 while (*string
&& isdigit((unsigned char) *string
)) ++string
;
126 if (*string
== 'x') {
128 params
->h
= atoi(string
);
129 while (*string
&& isdigit((unsigned char)*string
)) string
++;
132 params
->diff
= DIFF_NORMAL
;
133 if (*string
== 'd') {
136 for (i
= 0; i
< DIFFCOUNT
; i
++)
137 if (*string
== undead_diffchars
[i
])
139 if (*string
) string
++;
145 static char *encode_params(game_params
*params
, int full
) {
147 sprintf(buf
, "%dx%d", params
->w
, params
->h
);
149 sprintf(buf
+ strlen(buf
), "d%c", undead_diffchars
[params
->diff
]);
153 static config_item
*game_configure(game_params
*params
) {
157 ret
= snewn(4, 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
);
171 ret
[2].name
= "Difficulty";
172 ret
[2].type
= C_CHOICES
;
173 ret
[2].sval
= DIFFCONFIG
;
174 ret
[2].ival
= params
->diff
;
184 static game_params
*custom_params(config_item
*cfg
) {
185 game_params
*ret
= snew(game_params
);
187 ret
->w
= atoi(cfg
[0].sval
);
188 ret
->h
= atoi(cfg
[1].sval
);
189 ret
->diff
= cfg
[2].ival
;
193 static char *validate_params(game_params
*params
, int full
) {
194 if ((params
->w
* params
->h
) > 54) return "Grid is too big";
195 if (params
->w
< 3) return "Width must be at least 3";
196 if (params
->h
< 3) return "Height must be at least 3";
197 if (params
->diff
>= DIFFCOUNT
) return "Unknown difficulty rating";
201 /* --------------------------------------------------------------- */
202 /* Game state allocation, deallocation. */
218 struct game_params params
;
220 int num_ghosts
,num_vampires
,num_zombies
,num_total
;
230 struct game_common
*common
;
232 unsigned char *pencils
;
233 unsigned char *cell_errors
;
234 unsigned char *hint_errors
;
235 unsigned char count_errors
[3];
240 static game_state
*new_state(game_params
*params
) {
242 game_state
*state
= snew(game_state
);
243 state
->common
= snew(struct game_common
);
245 state
->common
->refcount
= 1;
246 state
->common
->params
.w
= params
->w
;
247 state
->common
->params
.h
= params
->h
;
248 state
->common
->params
.diff
= params
->diff
;
250 state
->common
->wh
= (state
->common
->params
.w
+2) * (state
->common
->params
.h
+2);
252 state
->common
->num_ghosts
= 0;
253 state
->common
->num_vampires
= 0;
254 state
->common
->num_zombies
= 0;
255 state
->common
->num_total
= 0;
257 state
->common
->grid
= snewn(state
->common
->wh
, int);
258 state
->common
->xinfo
= snewn(state
->common
->wh
, int);
259 state
->common
->fixed
= NULL
;
260 state
->common
->solved
= FALSE
;
262 state
->common
->num_paths
=
263 state
->common
->params
.w
+ state
->common
->params
.h
;
264 state
->common
->paths
= snewn(state
->common
->num_paths
, struct path
);
266 for (i
=0;i
<state
->common
->num_paths
;i
++) {
267 state
->common
->paths
[i
].length
= 0;
268 state
->common
->paths
[i
].grid_start
= -1;
269 state
->common
->paths
[i
].grid_end
= -1;
270 state
->common
->paths
[i
].num_monsters
= 0;
271 state
->common
->paths
[i
].sightings_start
= 0;
272 state
->common
->paths
[i
].sightings_end
= 0;
273 state
->common
->paths
[i
].p
= snewn(state
->common
->wh
,int);
274 state
->common
->paths
[i
].xy
= snewn(state
->common
->wh
,int);
275 state
->common
->paths
[i
].mapping
= snewn(state
->common
->wh
,int);
279 state
->pencils
= NULL
;
281 state
->cell_errors
= snewn(state
->common
->wh
, unsigned char);
282 for (i
=0;i
<state
->common
->wh
;i
++)
283 state
->cell_errors
[i
] = FALSE
;
284 state
->hint_errors
= snewn(2*state
->common
->num_paths
, unsigned char);
285 for (i
=0;i
<2*state
->common
->num_paths
;i
++)
286 state
->hint_errors
[i
] = FALSE
;
288 state
->count_errors
[i
] = FALSE
;
290 state
->solved
= FALSE
;
291 state
->cheated
= FALSE
;
296 static game_state
*dup_game(game_state
*state
) {
297 game_state
*ret
= snew(game_state
);
299 ret
->common
= state
->common
;
300 ret
->common
->refcount
++;
302 if (state
->guess
!= NULL
) {
303 ret
->guess
= snewn(ret
->common
->num_total
,int);
304 memcpy(ret
->guess
, state
->guess
, ret
->common
->num_total
*sizeof(int));
306 else ret
->guess
= NULL
;
308 if (state
->pencils
!= NULL
) {
309 ret
->pencils
= snewn(ret
->common
->num_total
,unsigned char);
310 memcpy(ret
->pencils
, state
->pencils
,
311 ret
->common
->num_total
*sizeof(unsigned char));
313 else ret
->pencils
= NULL
;
315 if (state
->cell_errors
!= NULL
) {
316 ret
->cell_errors
= snewn(ret
->common
->wh
,unsigned char);
317 memcpy(ret
->cell_errors
, state
->cell_errors
,
318 ret
->common
->wh
*sizeof(unsigned char));
320 else ret
->cell_errors
= NULL
;
322 if (state
->hint_errors
!= NULL
) {
323 ret
->hint_errors
= snewn(2*ret
->common
->num_paths
,unsigned char);
324 memcpy(ret
->hint_errors
, state
->hint_errors
,
325 2*ret
->common
->num_paths
*sizeof(unsigned char));
327 else ret
->hint_errors
= NULL
;
329 ret
->count_errors
[0] = state
->count_errors
[0];
330 ret
->count_errors
[1] = state
->count_errors
[1];
331 ret
->count_errors
[2] = state
->count_errors
[2];
333 ret
->solved
= state
->solved
;
334 ret
->cheated
= state
->cheated
;
339 static void free_game(game_state
*state
) {
342 state
->common
->refcount
--;
343 if (state
->common
->refcount
== 0) {
344 for (i
=0;i
<state
->common
->num_paths
;i
++) {
345 sfree(state
->common
->paths
[i
].mapping
);
346 sfree(state
->common
->paths
[i
].xy
);
347 sfree(state
->common
->paths
[i
].p
);
349 sfree(state
->common
->paths
);
350 sfree(state
->common
->xinfo
);
351 sfree(state
->common
->grid
);
352 if (state
->common
->fixed
!= NULL
) sfree(state
->common
->fixed
);
353 sfree(state
->common
);
355 if (state
->hint_errors
!= NULL
) sfree(state
->hint_errors
);
356 if (state
->cell_errors
!= NULL
) sfree(state
->cell_errors
);
357 if (state
->pencils
!= NULL
) sfree(state
->pencils
);
358 if (state
->guess
!= NULL
) sfree(state
->guess
);
364 /* --------------------------------------------------------------- */
365 /* Puzzle generator */
378 /* grid walk directions */
387 int range2grid(int rangeno
, int width
, int height
, int *x
, int *y
) {
390 *x
= 0; *y
= 0; return DIRECTION_NONE
;
392 if (rangeno
< width
) {
393 *x
= rangeno
+1; *y
= 0; return DIRECTION_DOWN
;
395 rangeno
= rangeno
- width
;
396 if (rangeno
< height
) {
397 *x
= width
+1; *y
= rangeno
+1; return DIRECTION_LEFT
;
399 rangeno
= rangeno
- height
;
400 if (rangeno
< width
) {
401 *x
= width
-rangeno
; *y
= height
+1; return DIRECTION_UP
;
403 rangeno
= rangeno
- width
;
404 if (rangeno
< height
) {
405 *x
= 0; *y
= height
-rangeno
; return DIRECTION_RIGHT
;
408 return DIRECTION_NONE
;
411 int grid2range(int x
, int y
, int w
, int h
) {
412 if (x
>0 && x
<w
+1 && y
>0 && y
<h
+1) return -1;
413 if (x
<0 || x
>w
+1 || y
<0 || y
>h
+1) return -1;
414 if ((x
== 0 || x
==w
+1) && (y
==0 || y
==h
+1)) return -1;
415 if (y
==0) return x
-1;
416 if (x
==(w
+1)) return y
-1+w
;
417 if (y
==(h
+1)) return 2*w
+ h
- x
;
421 void make_paths(game_state
*state
) {
425 for (i
=0;i
<2*(state
->common
->params
.w
+ state
->common
->params
.h
);i
++) {
427 int j
,k
,num_monsters
;
431 /* Check whether inverse path is already in list */
432 for (j
=0;j
<count
;j
++) {
433 if (i
== state
->common
->paths
[j
].grid_end
) {
440 /* We found a new path through the mirror maze */
441 state
->common
->paths
[count
].grid_start
= i
;
442 dir
= range2grid(i
, state
->common
->params
.w
,
443 state
->common
->params
.h
,&x
,&y
);
444 state
->common
->paths
[count
].sightings_start
=
445 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)];
449 if (dir
== DIRECTION_DOWN
) y
++;
450 else if (dir
== DIRECTION_LEFT
) x
--;
451 else if (dir
== DIRECTION_UP
) y
--;
452 else if (dir
== DIRECTION_RIGHT
) x
++;
454 r
= grid2range(x
, y
, state
->common
->params
.w
,
455 state
->common
->params
.h
);
457 state
->common
->paths
[count
].grid_end
= r
;
458 state
->common
->paths
[count
].sightings_end
=
459 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)];
463 c
= state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)];
464 state
->common
->paths
[count
].xy
[state
->common
->paths
[count
].length
] =
465 x
+y
*(state
->common
->params
.w
+2);
466 if (c
== CELL_MIRROR_L
) {
467 state
->common
->paths
[count
].p
[state
->common
->paths
[count
].length
] = -1;
468 if (dir
== DIRECTION_DOWN
) dir
= DIRECTION_RIGHT
;
469 else if (dir
== DIRECTION_LEFT
) dir
= DIRECTION_UP
;
470 else if (dir
== DIRECTION_UP
) dir
= DIRECTION_LEFT
;
471 else if (dir
== DIRECTION_RIGHT
) dir
= DIRECTION_DOWN
;
473 else if (c
== CELL_MIRROR_R
) {
474 state
->common
->paths
[count
].p
[state
->common
->paths
[count
].length
] = -1;
475 if (dir
== DIRECTION_DOWN
) dir
= DIRECTION_LEFT
;
476 else if (dir
== DIRECTION_LEFT
) dir
= DIRECTION_DOWN
;
477 else if (dir
== DIRECTION_UP
) dir
= DIRECTION_RIGHT
;
478 else if (dir
== DIRECTION_RIGHT
) dir
= DIRECTION_UP
;
481 state
->common
->paths
[count
].p
[state
->common
->paths
[count
].length
] =
482 state
->common
->xinfo
[x
+y
*(state
->common
->params
.w
+2)];
484 state
->common
->paths
[count
].length
++;
486 /* Count unique monster entries in each path */
487 state
->common
->paths
[count
].num_monsters
= 0;
488 for (j
=0;j
<state
->common
->num_total
;j
++) {
490 for (k
=0;k
<state
->common
->paths
[count
].length
;k
++)
491 if (state
->common
->paths
[count
].p
[k
] == j
)
493 if (num_monsters
> 0)
494 state
->common
->paths
[count
].num_monsters
++;
497 /* Generate mapping vector */
499 for (p
=0;p
<state
->common
->paths
[count
].length
;p
++) {
501 m
= state
->common
->paths
[count
].p
[p
];
502 if (m
== -1) continue;
505 if (state
->common
->paths
[count
].mapping
[j
] == m
) found
= TRUE
;
506 if (!found
) state
->common
->paths
[count
].mapping
[c
++] = m
;
519 int next_list(struct guess
*g
, int pos
) {
522 if ((g
->guess
[pos
] == 1 && g
->possible
[pos
] == 1) ||
523 (g
->guess
[pos
] == 2 && (g
->possible
[pos
] == 3 ||
524 g
->possible
[pos
] == 2)) ||
527 if (g
->guess
[pos
] == 1 && (g
->possible
[pos
] == 3 ||
528 g
->possible
[pos
] == 7)) {
529 g
->guess
[pos
] = 2; return TRUE
;
531 if (g
->guess
[pos
] == 1 && g
->possible
[pos
] == 5) {
532 g
->guess
[pos
] = 4; return TRUE
;
534 if (g
->guess
[pos
] == 2 && (g
->possible
[pos
] == 6 || g
->possible
[pos
] == 7)) {
535 g
->guess
[pos
] = 4; return TRUE
;
539 if (g
->guess
[pos
] == 1) {
540 if (g
->possible
[pos
] == 1) {
541 return next_list(g
,pos
-1);
543 if (g
->possible
[pos
] == 3 || g
->possible
[pos
] == 7) {
544 g
->guess
[pos
] = 2; return TRUE
;
546 if (g
->possible
[pos
] == 5) {
547 g
->guess
[pos
] = 4; return TRUE
;
551 if (g
->guess
[pos
] == 2) {
552 if (g
->possible
[pos
] == 2) {
553 return next_list(g
,pos
-1);
555 if (g
->possible
[pos
] == 3) {
556 g
->guess
[pos
] = 1; return next_list(g
,pos
-1);
558 if (g
->possible
[pos
] == 6 || g
->possible
[pos
] == 7) {
559 g
->guess
[pos
] = 4; return TRUE
;
563 if (g
->guess
[pos
] == 4) {
564 if (g
->possible
[pos
] == 5 || g
->possible
[pos
] == 7) {
565 g
->guess
[pos
] = 1; return next_list(g
,pos
-1);
567 if (g
->possible
[pos
] == 6) {
568 g
->guess
[pos
] = 2; return next_list(g
,pos
-1);
570 if (g
->possible
[pos
] == 4) {
571 return next_list(g
,pos
-1);
577 void get_unique(game_state
*state
, int counter
, random_state
*rs
) {
579 int p
,i
,c
,count_uniques
;
580 struct guess path_guess
;
592 } views
, single_views
, loop_views
, test_views
;
594 struct entry test_entry
;
596 path_guess
.length
= state
->common
->paths
[counter
].num_monsters
;
597 path_guess
.guess
= snewn(path_guess
.length
,int);
598 path_guess
.possible
= snewn(path_guess
.length
,int);
599 for (i
=0;i
<path_guess
.length
;i
++)
600 path_guess
.guess
[i
] = path_guess
.possible
[i
] = 0;
602 for (p
=0;p
<path_guess
.length
;p
++) {
603 path_guess
.possible
[p
] =
604 state
->guess
[state
->common
->paths
[counter
].mapping
[p
]];
605 switch (path_guess
.possible
[p
]) {
606 case 1: path_guess
.guess
[p
] = 1; break;
607 case 2: path_guess
.guess
[p
] = 2; break;
608 case 3: path_guess
.guess
[p
] = 1; break;
609 case 4: path_guess
.guess
[p
] = 4; break;
610 case 5: path_guess
.guess
[p
] = 1; break;
611 case 6: path_guess
.guess
[p
] = 2; break;
612 case 7: path_guess
.guess
[p
] = 1; break;
622 views
.node
= snewn(1,struct entry
);
623 views
.node
->link
= views
.head
;
624 views
.node
->guess
= snewn(path_guess
.length
,int);
625 views
.head
= views
.node
;
626 views
.node
->start_view
= 0;
627 views
.node
->end_view
= 0;
628 memcpy(views
.node
->guess
, path_guess
.guess
,
629 path_guess
.length
*sizeof(int));
632 for (p
=0;p
<state
->common
->paths
[counter
].length
;p
++) {
633 if (state
->common
->paths
[counter
].p
[p
] == -1) mirror
= TRUE
;
635 for (i
=0;i
<path_guess
.length
;i
++) {
636 if (state
->common
->paths
[counter
].p
[p
] ==
637 state
->common
->paths
[counter
].mapping
[i
]) {
638 if (path_guess
.guess
[i
] == 1 && mirror
== TRUE
)
639 views
.node
->start_view
++;
640 if (path_guess
.guess
[i
] == 2 && mirror
== FALSE
)
641 views
.node
->start_view
++;
642 if (path_guess
.guess
[i
] == 4)
643 views
.node
->start_view
++;
650 for (p
=state
->common
->paths
[counter
].length
-1;p
>=0;p
--) {
651 if (state
->common
->paths
[counter
].p
[p
] == -1) mirror
= TRUE
;
653 for (i
=0;i
<path_guess
.length
;i
++) {
654 if (state
->common
->paths
[counter
].p
[p
] ==
655 state
->common
->paths
[counter
].mapping
[i
]) {
656 if (path_guess
.guess
[i
] == 1 && mirror
== TRUE
)
657 views
.node
->end_view
++;
658 if (path_guess
.guess
[i
] == 2 && mirror
== FALSE
)
659 views
.node
->end_view
++;
660 if (path_guess
.guess
[i
] == 4)
661 views
.node
->end_view
++;
667 } while (next_list(&path_guess
, path_guess
.length
-1));
669 /* extract single entries from view list */
671 test_views
.head
= views
.head
;
672 test_views
.node
= views
.node
;
674 test_entry
.guess
= snewn(path_guess
.length
,int);
676 single_views
.head
= NULL
;
677 single_views
.node
= NULL
;
680 while (test_views
.head
!= NULL
) {
681 test_views
.node
= test_views
.head
;
682 test_views
.head
= test_views
.head
->link
;
684 loop_views
.head
= views
.head
;
685 loop_views
.node
= views
.node
;
686 while (loop_views
.head
!= NULL
) {
687 loop_views
.node
= loop_views
.head
;
688 loop_views
.head
= loop_views
.head
->link
;
689 if (test_views
.node
->start_view
== loop_views
.node
->start_view
&&
690 test_views
.node
->end_view
== loop_views
.node
->end_view
)
694 single_views
.node
= snewn(1,struct entry
);
695 single_views
.node
->link
= single_views
.head
;
696 single_views
.node
->guess
= snewn(path_guess
.length
,int);
697 single_views
.head
= single_views
.node
;
698 single_views
.node
->start_view
= test_views
.node
->start_view
;
699 single_views
.node
->end_view
= test_views
.node
->end_view
;
700 memcpy(single_views
.node
->guess
, test_views
.node
->guess
,
701 path_guess
.length
*sizeof(int));
706 if (count_uniques
> 0) {
707 test_entry
.start_view
= 0;
708 test_entry
.end_view
= 0;
709 /* Choose one unique guess per random */
710 /* While we are busy with looping through single_views, we
711 * conveniently free the linked list single_view */
712 c
= random_upto(rs
,count_uniques
);
713 while(single_views
.head
!= NULL
) {
714 single_views
.node
= single_views
.head
;
715 single_views
.head
= single_views
.head
->link
;
717 memcpy(test_entry
.guess
, single_views
.node
->guess
,
718 path_guess
.length
*sizeof(int));
719 test_entry
.start_view
= single_views
.node
->start_view
;
720 test_entry
.end_view
= single_views
.node
->end_view
;
722 sfree(single_views
.node
->guess
);
723 sfree(single_views
.node
);
726 /* Modify state_guess according to path_guess.mapping */
727 for (i
=0;i
<path_guess
.length
;i
++)
728 state
->guess
[state
->common
->paths
[counter
].mapping
[i
]] =
732 sfree(test_entry
.guess
);
734 while (views
.head
!= NULL
) {
735 views
.node
= views
.head
;
736 views
.head
= views
.head
->link
;
737 sfree(views
.node
->guess
);
741 sfree(path_guess
.possible
);
742 sfree(path_guess
.guess
);
747 int count_monsters(game_state
*state
,
748 int *cGhost
, int *cVampire
, int *cZombie
) {
752 *cGhost
= *cVampire
= *cZombie
= cNone
= 0;
754 for (i
=0;i
<state
->common
->num_total
;i
++) {
755 if (state
->guess
[i
] == 1) (*cGhost
)++;
756 else if (state
->guess
[i
] == 2) (*cVampire
)++;
757 else if (state
->guess
[i
] == 4) (*cZombie
)++;
764 int check_numbers(game_state
*state
, int *guess
) {
767 int count_ghosts
, count_vampires
, count_zombies
;
769 count_ghosts
= count_vampires
= count_zombies
= 0;
770 for (i
=0;i
<state
->common
->num_total
;i
++) {
771 if (guess
[i
] == 1) count_ghosts
++;
772 if (guess
[i
] == 2) count_vampires
++;
773 if (guess
[i
] == 4) count_zombies
++;
778 if (count_ghosts
> state
->common
->num_ghosts
) valid
= FALSE
;
779 if (count_vampires
> state
->common
->num_vampires
) valid
= FALSE
;
780 if (count_zombies
> state
->common
->num_zombies
) valid
= FALSE
;
785 int check_solution(int *g
, struct path path
) {
792 for (i
=0;i
<path
.length
;i
++) {
793 if (path
.p
[i
] == -1) mirror
= TRUE
;
795 if (g
[path
.p
[i
]] == 1 && mirror
) count
++;
796 else if (g
[path
.p
[i
]] == 2 && !mirror
) count
++;
797 else if (g
[path
.p
[i
]] == 4) count
++;
800 if (count
!= path
.sightings_start
) return FALSE
;
804 for (i
=path
.length
-1;i
>=0;i
--) {
805 if (path
.p
[i
] == -1) mirror
= TRUE
;
807 if (g
[path
.p
[i
]] == 1 && mirror
) count
++;
808 else if (g
[path
.p
[i
]] == 2 && !mirror
) count
++;
809 else if (g
[path
.p
[i
]] == 4) count
++;
812 if (count
!= path
.sightings_end
) return FALSE
;
817 int solve_iterative(game_state
*state
, struct path
*paths
) {
827 loop
.length
= state
->common
->num_total
;
828 guess
= snewn(state
->common
->num_total
,int);
829 possible
= snewn(state
->common
->num_total
,int);
831 for (i
=0;i
<state
->common
->num_total
;i
++) {
832 guess
[i
] = state
->guess
[i
];
836 for (p
=0;p
<state
->common
->num_paths
;p
++) {
837 if (paths
[p
].num_monsters
> 0) {
838 loop
.length
= paths
[p
].num_monsters
;
839 loop
.guess
= snewn(paths
[p
].num_monsters
,int);
840 loop
.possible
= snewn(paths
[p
].num_monsters
,int);
842 for (i
=0;i
<paths
[p
].num_monsters
;i
++) {
843 switch (state
->guess
[paths
[p
].mapping
[i
]]) {
844 case 1: loop
.guess
[i
] = 1; break;
845 case 2: loop
.guess
[i
] = 2; break;
846 case 3: loop
.guess
[i
] = 1; break;
847 case 4: loop
.guess
[i
] = 4; break;
848 case 5: loop
.guess
[i
] = 1; break;
849 case 6: loop
.guess
[i
] = 2; break;
850 case 7: loop
.guess
[i
] = 1; break;
852 loop
.possible
[i
] = state
->guess
[paths
[p
].mapping
[i
]];
853 possible
[paths
[p
].mapping
[i
]] = 0;
857 for (i
=0;i
<state
->common
->num_total
;i
++) {
858 guess
[i
] = state
->guess
[i
];
861 for (i
=0;i
<paths
[p
].num_monsters
;i
++)
862 guess
[paths
[p
].mapping
[i
]] = loop
.guess
[count
++];
863 if (check_numbers(state
,guess
) &&
864 check_solution(guess
,paths
[p
]))
865 for (j
=0;j
<paths
[p
].num_monsters
;j
++)
866 possible
[paths
[p
].mapping
[j
]] |= loop
.guess
[j
];
867 if (!next_list(&loop
,loop
.length
-1)) break;
869 for (i
=0;i
<paths
[p
].num_monsters
;i
++)
870 state
->guess
[paths
[p
].mapping
[i
]] &=
871 possible
[paths
[p
].mapping
[i
]];
872 sfree(loop
.possible
);
877 for (i
=0;i
<state
->common
->num_total
;i
++) {
878 if (state
->guess
[i
] == 3 || state
->guess
[i
] == 5 ||
879 state
->guess
[i
] == 6 || state
->guess
[i
] == 7) {
880 solved
= FALSE
; break;
890 int solve_bruteforce(game_state
*state
, struct path
*paths
) {
892 int number_solutions
;
897 loop
.guess
= snewn(state
->common
->num_total
,int);
898 loop
.possible
= snewn(state
->common
->num_total
,int);
900 for (i
=0;i
<state
->common
->num_total
;i
++) {
901 loop
.possible
[i
] = state
->guess
[i
];
902 switch (state
->guess
[i
]) {
903 case 1: loop
.guess
[i
] = 1; break;
904 case 2: loop
.guess
[i
] = 2; break;
905 case 3: loop
.guess
[i
] = 1; break;
906 case 4: loop
.guess
[i
] = 4; break;
907 case 5: loop
.guess
[i
] = 1; break;
908 case 6: loop
.guess
[i
] = 2; break;
909 case 7: loop
.guess
[i
] = 1; break;
914 number_solutions
= 0;
919 if (!check_numbers(state
,loop
.guess
)) correct
= FALSE
;
921 for (p
=0;p
<state
->common
->num_paths
;p
++)
922 if (!check_solution(loop
.guess
,paths
[p
])) {
923 correct
= FALSE
; break;
928 if(number_solutions
> 1) {
932 for (i
=0;i
<state
->common
->num_total
;i
++)
933 state
->guess
[i
] = loop
.guess
[i
];
935 if (!next_list(&loop
,state
->common
->num_total
-1)) {
940 sfree(loop
.possible
);
946 int path_cmp(const void *a
, const void *b
) {
947 const struct path
*pa
= (const struct path
*)a
;
948 const struct path
*pb
= (const struct path
*)b
;
949 return pa
->num_monsters
- pb
->num_monsters
;
952 static char *new_game_desc(game_params
*params
, random_state
*rs
,
953 char **aux
, int interactive
) {
954 int i
,count
,c
,w
,h
,r
,p
,g
;
957 /* Variables for puzzle generation algorithm */
960 int count_ghosts
, count_vampires
, count_zombies
;
964 /* Variables for solver algorithm */
965 int solved_iterative
, solved_bruteforce
, contains_inconsistency
,
970 /* Variables for game description generation */
977 new = new_state(params
);
980 /* Fill grid with random mirrors and (later to be populated)
981 * empty monster cells */
983 for (h
=1;h
<new->common
->params
.h
+1;h
++)
984 for (w
=1;w
<new->common
->params
.w
+1;w
++) {
985 c
= random_upto(rs
,5);
987 new->common
->grid
[w
+h
*(new->common
->params
.w
+2)] = CELL_EMPTY
;
988 new->common
->xinfo
[w
+h
*(new->common
->params
.w
+2)] = count
++;
991 new->common
->grid
[w
+h
*(new->common
->params
.w
+2)] =
993 new->common
->xinfo
[w
+h
*(new->common
->params
.w
+2)] = -1;
996 new->common
->grid
[w
+h
*(new->common
->params
.w
+2)] =
998 new->common
->xinfo
[w
+h
*(new->common
->params
.w
+2)] = -1;
1001 new->common
->num_total
= count
; /* Total number of monsters in maze */
1003 /* Puzzle is boring if it has too few monster cells. Discard
1004 * grid, make new grid */
1005 if (new->common
->num_total
<= 4) {
1010 /* Monsters / Mirrors ratio should be balanced */
1011 ratio
= (float)new->common
->num_total
/
1012 (float)(new->common
->params
.w
* new->common
->params
.h
);
1013 if (ratio
< 0.48 || ratio
> 0.78) {
1018 /* Assign clue identifiers */
1019 for (r
=0;r
<2*(new->common
->params
.w
+new->common
->params
.h
);r
++) {
1021 gridno
= range2grid(r
,new->common
->params
.w
,new->common
->params
.h
,
1023 new->common
->grid
[x
+y
*(new->common
->params
.w
+2)] = gridno
;
1024 new->common
->xinfo
[x
+y
*(new->common
->params
.w
+2)] = 0;
1026 /* The four corners don't matter at all for the game. Set them
1027 * all to zero, just to have a nice data structure */
1028 new->common
->grid
[0] = 0;
1029 new->common
->xinfo
[0] = 0;
1030 new->common
->grid
[new->common
->params
.w
+1] = 0;
1031 new->common
->xinfo
[new->common
->params
.w
+1] = 0;
1032 new->common
->grid
[new->common
->params
.w
+1 + (new->common
->params
.h
+1)*(new->common
->params
.w
+2)] = 0;
1033 new->common
->xinfo
[new->common
->params
.w
+1 + (new->common
->params
.h
+1)*(new->common
->params
.w
+2)] = 0;
1034 new->common
->grid
[(new->common
->params
.h
+1)*(new->common
->params
.w
+2)] = 0;
1035 new->common
->xinfo
[(new->common
->params
.h
+1)*(new->common
->params
.w
+2)] = 0;
1037 /* Initialize solution vector */
1038 new->guess
= snewn(new->common
->num_total
,int);
1039 for (g
=0;g
<new->common
->num_total
;g
++) new->guess
[g
] = 7;
1041 /* Initialize fixed flag from common. Not needed for the
1042 * puzzle generator; initialize it for having clean code */
1043 new->common
->fixed
= snewn(new->common
->num_total
,int);
1044 for (g
=0;g
<new->common
->num_total
;g
++)
1045 new->common
->fixed
[g
] = FALSE
;
1047 /* paths generation */
1050 /* Grid is invalid if max. path length > threshold. Discard
1051 * grid, make new one */
1052 switch (new->common
->params
.diff
) {
1053 case DIFF_EASY
: max_length
= min(new->common
->params
.w
,new->common
->params
.h
) + 1; break;
1054 case DIFF_NORMAL
: max_length
= (max(new->common
->params
.w
,new->common
->params
.h
) * 3) / 2; break;
1055 case DIFF_TRICKY
: max_length
= 9; break;
1056 default: max_length
= 9; break;
1059 for (p
=0;p
<new->common
->num_paths
;p
++) {
1060 if (new->common
->paths
[p
].num_monsters
> max_length
) {
1069 qsort(new->common
->paths
, new->common
->num_paths
,
1070 sizeof(struct path
), path_cmp
);
1072 /* Grid monster initialization */
1073 /* For easy puzzles, we try to fill nearly the whole grid
1074 with unique solution paths (up to 2) For more difficult
1075 puzzles, we fill only roughly half the grid, and choose
1076 random monsters for the rest For hard puzzles, we fill
1077 even less paths with unique solutions */
1079 switch (new->common
->params
.diff
) {
1080 case DIFF_EASY
: filling
= 2; break;
1081 case DIFF_NORMAL
: filling
= min( (new->common
->params
.w
+new->common
->params
.h
) , (new->common
->num_total
)/2 ); break;
1082 case DIFF_TRICKY
: filling
= max( (new->common
->params
.w
+new->common
->params
.h
) , (new->common
->num_total
)/2 ); break;
1083 default: filling
= 0; break;
1087 while ( (count_monsters(new, &count_ghosts
, &count_vampires
,
1088 &count_zombies
)) > filling
) {
1089 if ((count
) >= new->common
->num_paths
) break;
1090 if (new->common
->paths
[count
].num_monsters
== 0) {
1094 get_unique(new,count
,rs
);
1098 /* Fill any remaining ambiguous entries with random monsters */
1099 for(g
=0;g
<new->common
->num_total
;g
++) {
1100 if (new->guess
[g
] == 7) {
1101 r
= random_upto(rs
,3);
1102 new->guess
[g
] = (r
== 0) ?
1 : ( (r
== 1) ?
2 : 4 );
1106 /* Determine all hints */
1107 count_monsters(new, &new->common
->num_ghosts
,
1108 &new->common
->num_vampires
, &new->common
->num_zombies
);
1110 /* Puzzle is trivial if it has only one type of monster. Discard. */
1111 if ((new->common
->num_ghosts
== 0 && new->common
->num_vampires
== 0) ||
1112 (new->common
->num_ghosts
== 0 && new->common
->num_zombies
== 0) ||
1113 (new->common
->num_vampires
== 0 && new->common
->num_zombies
== 0)) {
1118 /* Discard puzzle if difficulty Tricky, and it has only 1
1119 * member of any monster type */
1120 if (new->common
->params
.diff
== DIFF_TRICKY
&&
1121 (new->common
->num_ghosts
<= 1 ||
1122 new->common
->num_vampires
<= 1 || new->common
->num_zombies
<= 1)) {
1127 for (w
=1;w
<new->common
->params
.w
+1;w
++)
1128 for (h
=1;h
<new->common
->params
.h
+1;h
++) {
1129 c
= new->common
->xinfo
[w
+h
*(new->common
->params
.w
+2)];
1131 if (new->guess
[c
] == 1) new->common
->grid
[w
+h
*(new->common
->params
.w
+2)] = CELL_GHOST
;
1132 if (new->guess
[c
] == 2) new->common
->grid
[w
+h
*(new->common
->params
.w
+2)] = CELL_VAMPIRE
;
1133 if (new->guess
[c
] == 4) new->common
->grid
[w
+h
*(new->common
->params
.w
+2)] = CELL_ZOMBIE
;
1137 /* Prepare path information needed by the solver (containing all hints) */
1138 for (p
=0;p
<new->common
->num_paths
;p
++) {
1141 new->common
->paths
[p
].sightings_start
= 0;
1142 new->common
->paths
[p
].sightings_end
= 0;
1145 for (g
=0;g
<new->common
->paths
[p
].length
;g
++) {
1147 if (new->common
->paths
[p
].p
[g
] == -1) mirror
= TRUE
;
1149 if (new->guess
[new->common
->paths
[p
].p
[g
]] == 1 && mirror
== TRUE
) (new->common
->paths
[p
].sightings_start
)++;
1150 else if (new->guess
[new->common
->paths
[p
].p
[g
]] == 2 && mirror
== FALSE
) (new->common
->paths
[p
].sightings_start
)++;
1151 else if (new->guess
[new->common
->paths
[p
].p
[g
]] == 4) (new->common
->paths
[p
].sightings_start
)++;
1156 for (g
=new->common
->paths
[p
].length
-1;g
>=0;g
--) {
1157 if (new->common
->paths
[p
].p
[g
] == -1) mirror
= TRUE
;
1159 if (new->guess
[new->common
->paths
[p
].p
[g
]] == 1 && mirror
== TRUE
) (new->common
->paths
[p
].sightings_end
)++;
1160 else if (new->guess
[new->common
->paths
[p
].p
[g
]] == 2 && mirror
== FALSE
) (new->common
->paths
[p
].sightings_end
)++;
1161 else if (new->guess
[new->common
->paths
[p
].p
[g
]] == 4) (new->common
->paths
[p
].sightings_end
)++;
1165 range2grid(new->common
->paths
[p
].grid_start
,
1166 new->common
->params
.w
,new->common
->params
.h
,&x
,&y
);
1167 new->common
->grid
[x
+y
*(new->common
->params
.w
+2)] =
1168 new->common
->paths
[p
].sightings_start
;
1169 range2grid(new->common
->paths
[p
].grid_end
,
1170 new->common
->params
.w
,new->common
->params
.h
,&x
,&y
);
1171 new->common
->grid
[x
+y
*(new->common
->params
.w
+2)] =
1172 new->common
->paths
[p
].sightings_end
;
1175 /* Try to solve the puzzle with the iterative solver */
1176 old_guess
= snewn(new->common
->num_total
,int);
1177 for (p
=0;p
<new->common
->num_total
;p
++) {
1181 iterative_depth
= 0;
1182 solved_iterative
= FALSE
;
1183 contains_inconsistency
= FALSE
;
1184 count_ambiguous
= 0;
1189 solved_iterative
= solve_iterative(new,new->common
->paths
);
1191 for (p
=0;p
<new->common
->num_total
;p
++) {
1192 if (new->guess
[p
] != old_guess
[p
]) no_change
= FALSE
;
1193 old_guess
[p
] = new->guess
[p
];
1194 if (new->guess
[p
] == 0) contains_inconsistency
= TRUE
;
1196 if (solved_iterative
|| no_change
) break;
1199 /* If necessary, try to solve the puzzle with the brute-force solver */
1200 solved_bruteforce
= FALSE
;
1201 if (new->common
->params
.diff
!= DIFF_EASY
&&
1202 !solved_iterative
&& !contains_inconsistency
) {
1203 for (p
=0;p
<new->common
->num_total
;p
++)
1204 if (new->guess
[p
] != 1 && new->guess
[p
] != 2 &&
1205 new->guess
[p
] != 4) count_ambiguous
++;
1207 solved_bruteforce
= solve_bruteforce(new, new->common
->paths
);
1210 /* Determine puzzle difficulty level */
1211 if (new->common
->params
.diff
== DIFF_EASY
&& solved_iterative
&&
1212 iterative_depth
<= 3 && !contains_inconsistency
) {
1213 /* printf("Puzzle level: EASY Level %d Ratio %f Ambiguous %d (Found after %i tries)\n",iterative_depth, ratio, count_ambiguous, i); */
1217 if (new->common
->params
.diff
== DIFF_NORMAL
&&
1218 ((solved_iterative
&& iterative_depth
> 3) ||
1219 (solved_bruteforce
&& count_ambiguous
< 4)) &&
1220 !contains_inconsistency
) {
1221 /* printf("Puzzle level: NORMAL Level %d Ratio %f Ambiguous %d (Found after %d tries)\n", iterative_depth, ratio, count_ambiguous, i); */
1224 if (new->common
->params
.diff
== DIFF_TRICKY
&&
1225 solved_bruteforce
&& iterative_depth
> 0 &&
1226 count_ambiguous
>= 4 && !contains_inconsistency
) {
1227 /* printf("Puzzle level: TRICKY Level %d Ratio %f Ambiguous %d (Found after %d tries)\n", iterative_depth, ratio, count_ambiguous, i); */
1231 /* If puzzle is not solvable or does not satisfy the desired
1232 * difficulty level, free memory and start from scratch */
1238 /* We have a valid puzzle! */
1240 desc
= snewn(10 + new->common
->wh
+
1241 6*(new->common
->params
.w
+ new->common
->params
.h
), char);
1244 /* Encode monster counts */
1245 e
+= sprintf(e
, "%d,", new->common
->num_ghosts
);
1246 e
+= sprintf(e
, "%d,", new->common
->num_vampires
);
1247 e
+= sprintf(e
, "%d,", new->common
->num_zombies
);
1251 for (y
=1;y
<new->common
->params
.h
+1;y
++)
1252 for (x
=1;x
<new->common
->params
.w
+1;x
++) {
1253 c
= new->common
->grid
[x
+y
*(new->common
->params
.w
+2)];
1258 if (c
!= CELL_MIRROR_L
&& c
!= CELL_MIRROR_R
) {
1261 else if (c
== CELL_MIRROR_L
) {
1262 if (count
> 0) *e
++ = (count
-1 + 'a');
1267 if (count
> 0) *e
++ = (count
-1 + 'a');
1272 if (count
> 0) *e
++ = (count
-1 + 'a');
1275 for (p
=0;p
<2*(new->common
->params
.w
+ new->common
->params
.h
);p
++) {
1276 range2grid(p
,new->common
->params
.w
,new->common
->params
.h
,&x
,&y
);
1277 e
+= sprintf(e
, ",%d", new->common
->grid
[x
+y
*(new->common
->params
.w
+2)]);
1281 desc
= sresize(desc
, e
- desc
, char);
1289 void num2grid(int num
, int width
, int height
, int *x
, int *y
) {
1295 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
) {
1300 game_state
*state
= new_state(params
);
1302 state
->common
->num_ghosts
= atoi(desc
);
1303 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1305 state
->common
->num_vampires
= atoi(desc
);
1306 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1308 state
->common
->num_zombies
= atoi(desc
);
1309 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1312 state
->common
->num_total
= state
->common
->num_ghosts
+ state
->common
->num_vampires
+ state
->common
->num_zombies
;
1314 state
->guess
= snewn(state
->common
->num_total
,int);
1315 state
->pencils
= snewn(state
->common
->num_total
,unsigned char);
1316 state
->common
->fixed
= snewn(state
->common
->num_total
,int);
1317 for (i
=0;i
<state
->common
->num_total
;i
++) {
1318 state
->guess
[i
] = 7;
1319 state
->pencils
[i
] = 0;
1320 state
->common
->fixed
[i
] = FALSE
;
1322 for (i
=0;i
<state
->common
->wh
;i
++)
1323 state
->cell_errors
[i
] = FALSE
;
1324 for (i
=0;i
<2*state
->common
->num_paths
;i
++)
1325 state
->hint_errors
[i
] = FALSE
;
1327 state
->count_errors
[i
] = FALSE
;
1331 while (*desc
!= ',') {
1336 num2grid(n
,state
->common
->params
.w
,state
->common
->params
.h
,&x
,&y
);
1337 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)] = CELL_MIRROR_L
;
1338 state
->common
->xinfo
[x
+y
*(state
->common
->params
.w
+2)] = -1;
1341 else if (*desc
== 'R') {
1342 num2grid(n
,state
->common
->params
.w
,state
->common
->params
.h
,&x
,&y
);
1343 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)] = CELL_MIRROR_R
;
1344 state
->common
->xinfo
[x
+y
*(state
->common
->params
.w
+2)] = -1;
1347 else if (*desc
== 'G') {
1348 num2grid(n
,state
->common
->params
.w
,state
->common
->params
.h
,&x
,&y
);
1349 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)] = CELL_GHOST
;
1350 state
->common
->xinfo
[x
+y
*(state
->common
->params
.w
+2)] = count
;
1351 state
->guess
[count
] = 1;
1352 state
->common
->fixed
[count
++] = TRUE
;
1355 else if (*desc
== 'V') {
1356 num2grid(n
,state
->common
->params
.w
,state
->common
->params
.h
,&x
,&y
);
1357 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)] = CELL_VAMPIRE
;
1358 state
->common
->xinfo
[x
+y
*(state
->common
->params
.w
+2)] = count
;
1359 state
->guess
[count
] = 2;
1360 state
->common
->fixed
[count
++] = TRUE
;
1363 else if (*desc
== 'Z') {
1364 num2grid(n
,state
->common
->params
.w
,state
->common
->params
.h
,&x
,&y
);
1365 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)] = CELL_ZOMBIE
;
1366 state
->common
->xinfo
[x
+y
*(state
->common
->params
.w
+2)] = count
;
1367 state
->guess
[count
] = 4;
1368 state
->common
->fixed
[count
++] = TRUE
;
1372 c
= *desc
- ('a' -1);
1374 num2grid(n
,state
->common
->params
.w
,state
->common
->params
.h
,&x
,&y
);
1375 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)] = CELL_EMPTY
;
1376 state
->common
->xinfo
[x
+y
*(state
->common
->params
.w
+2)] = count
;
1377 state
->guess
[count
] = 7;
1378 state
->common
->fixed
[count
++] = FALSE
;
1386 for (i
=0;i
<2*(state
->common
->params
.w
+ state
->common
->params
.h
);i
++) {
1390 sights
= atoi(desc
);
1391 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1395 range2grid(i
,state
->common
->params
.w
,state
->common
->params
.h
,&x
,&y
);
1396 state
->common
->grid
[x
+y
*(state
->common
->params
.w
+2)] = sights
;
1397 state
->common
->xinfo
[x
+y
*(state
->common
->params
.w
+2)] = -2;
1400 state
->common
->grid
[0] = 0;
1401 state
->common
->xinfo
[0] = -2;
1402 state
->common
->grid
[state
->common
->params
.w
+1] = 0;
1403 state
->common
->xinfo
[state
->common
->params
.w
+1] = -2;
1404 state
->common
->grid
[state
->common
->params
.w
+1 + (state
->common
->params
.h
+1)*(state
->common
->params
.w
+2)] = 0;
1405 state
->common
->xinfo
[state
->common
->params
.w
+1 + (state
->common
->params
.h
+1)*(state
->common
->params
.w
+2)] = -2;
1406 state
->common
->grid
[(state
->common
->params
.h
+1)*(state
->common
->params
.w
+2)] = 0;
1407 state
->common
->xinfo
[(state
->common
->params
.h
+1)*(state
->common
->params
.w
+2)] = -2;
1410 qsort(state
->common
->paths
, state
->common
->num_paths
, sizeof(struct path
), path_cmp
);
1415 static char *validate_desc(game_params
*params
, char *desc
) {
1417 int w
= params
->w
, h
= params
->h
;
1422 char *desc_s
= desc
;
1425 if (!*desc
) return "Faulty game description";
1426 while (*desc
&& isdigit((unsigned char)*desc
)) { desc
++; }
1427 if (*desc
!= ',') return "Invalid character in number list";
1432 area
= monsters
= monster_count
= 0;
1434 monster_count
+= atoi(desc
);
1435 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
1438 while (*desc
&& *desc
!= ',') {
1439 if (*desc
>= 'a' && *desc
<= 'z') {
1440 area
+= *desc
- 'a' +1; monsters
+= *desc
- 'a' +1;
1441 } else if (*desc
== 'G' || *desc
== 'V' || *desc
== 'Z') {
1443 } else if (*desc
== 'L' || *desc
== 'R') {
1446 return "Invalid character in grid specification";
1449 if (area
< wh
) return "Not enough data to fill grid";
1450 else if (area
> wh
) return "Too much data to fill grid";
1451 if (monsters
!= monster_count
)
1452 return "Monster numbers do not match grid spaces";
1454 for (i
= 0; i
< 2*(w
+h
); i
++) {
1455 if (!*desc
) return "Not enough numbers given after grid specification";
1456 else if (*desc
!= ',') return "Invalid character in number list";
1458 while (*desc
&& isdigit((unsigned char)*desc
)) { desc
++; }
1461 if (*desc
) return "Unexpected additional data at end of game description";
1466 static char *solve_game(game_state
*state_start
, game_state
*currstate
, char *aux
, char **error
) {
1469 int iterative_depth
;
1470 int solved_iterative
, solved_bruteforce
, contains_inconsistency
,
1476 game_state
*solve_state
= dup_game(currstate
);
1478 old_guess
= snewn(solve_state
->common
->num_total
,int);
1479 for (p
=0;p
<solve_state
->common
->num_total
;p
++) {
1480 if (solve_state
->common
->fixed
[p
]) {
1481 old_guess
[p
] = solve_state
->guess
[p
] = state_start
->guess
[p
];
1484 old_guess
[p
] = solve_state
->guess
[p
] = 7;
1487 iterative_depth
= 0;
1488 solved_iterative
= FALSE
;
1489 contains_inconsistency
= FALSE
;
1490 count_ambiguous
= 0;
1492 /* Try to solve the puzzle with the iterative solver */
1497 solve_iterative(solve_state
,solve_state
->common
->paths
);
1499 for (p
=0;p
<solve_state
->common
->num_total
;p
++) {
1500 if (solve_state
->guess
[p
] != old_guess
[p
]) no_change
= FALSE
;
1501 old_guess
[p
] = solve_state
->guess
[p
];
1502 if (solve_state
->guess
[p
] == 0) contains_inconsistency
= TRUE
;
1504 if (solved_iterative
|| no_change
|| contains_inconsistency
) break;
1507 if (contains_inconsistency
) {
1508 *error
= "Puzzle is inconsistent";
1510 free_game(solve_state
);
1514 /* If necessary, try to solve the puzzle with the brute-force solver */
1515 solved_bruteforce
= FALSE
;
1516 if (!solved_iterative
) {
1517 for (p
=0;p
<solve_state
->common
->num_total
;p
++)
1518 if (solve_state
->guess
[p
] != 1 && solve_state
->guess
[p
] != 2 &&
1519 solve_state
->guess
[p
] != 4) count_ambiguous
++;
1521 solve_bruteforce(solve_state
, solve_state
->common
->paths
);
1524 if (!solved_iterative
&& !solved_bruteforce
) {
1525 *error
= "Puzzle is unsolvable";
1527 free_game(solve_state
);
1531 /* printf("Puzzle solved at level %s, iterations %d, ambiguous %d\n", (solved_bruteforce ? "TRICKY" : "NORMAL"), iterative_depth, count_ambiguous); */
1533 move
= snewn(solve_state
->common
->num_total
* 4 +2, char);
1536 for (i
= 0; i
< solve_state
->common
->num_total
; i
++) {
1537 if (solve_state
->guess
[i
] == 1) c
+= sprintf(c
, ";G%d", i
);
1538 if (solve_state
->guess
[i
] == 2) c
+= sprintf(c
, ";V%d", i
);
1539 if (solve_state
->guess
[i
] == 4) c
+= sprintf(c
, ";Z%d", i
);
1542 move
= sresize(move
, c
- move
, char);
1545 free_game(solve_state
);
1549 static int game_can_format_as_text_now(game_params
*params
) {
1553 static char *game_text_format(game_state
*state
) {
1558 ret
= snewn(50 + 6*(state
->common
->params
.w
+2) +
1559 6*(state
->common
->params
.h
+2) +
1560 3*(state
->common
->params
.w
* state
->common
->params
.h
), char);
1562 sprintf(ret
,"G: %d V: %d Z: %d\n\n",state
->common
->num_ghosts
,
1563 state
->common
->num_vampires
, state
->common
->num_zombies
);
1565 for (h
=0;h
<state
->common
->params
.h
+2;h
++) {
1566 for (w
=0;w
<state
->common
->params
.w
+2;w
++) {
1567 c
= state
->common
->grid
[w
+h
*(state
->common
->params
.w
+2)];
1568 xi
= state
->common
->xinfo
[w
+h
*(state
->common
->params
.w
+2)];
1569 r
= grid2range(w
,h
,state
->common
->params
.w
,state
->common
->params
.h
);
1571 sprintf(buf
,"%2d", c
); strcat(ret
,buf
);
1572 } else if (c
== CELL_MIRROR_L
) {
1573 sprintf(buf
," \\"); strcat(ret
,buf
);
1574 } else if (c
== CELL_MIRROR_R
) {
1575 sprintf(buf
," /"); strcat(ret
,buf
);
1576 } else if (xi
>= 0) {
1577 g
= state
->guess
[xi
];
1578 if (g
== 1) { sprintf(buf
," G"); strcat(ret
,buf
); }
1579 else if (g
== 2) { sprintf(buf
," V"); strcat(ret
,buf
); }
1580 else if (g
== 4) { sprintf(buf
," Z"); strcat(ret
,buf
); }
1581 else { sprintf(buf
," ."); strcat(ret
,buf
); }
1583 sprintf(buf
," "); strcat(ret
,buf
);
1586 sprintf(buf
,"\n"); strcat(ret
,buf
);
1593 int hx
, hy
; /* as for solo.c, highlight pos */
1594 int hshow
, hpencil
, hcursor
; /* show state, type, and ?cursor. */
1598 static game_ui
*new_ui(game_state
*state
) {
1599 game_ui
*ui
= snew(game_ui
);
1600 ui
->hx
= ui
->hy
= 0;
1601 ui
->hpencil
= ui
->hshow
= ui
->hcursor
= 0;
1606 static void free_ui(game_ui
*ui
) {
1611 static char *encode_ui(game_ui
*ui
) {
1615 static void decode_ui(game_ui
*ui
, char *encoding
) {
1619 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
, game_state
*newstate
) {
1620 /* See solo.c; if we were pencil-mode highlighting and
1621 * somehow a square has just been properly filled, cancel
1623 if (ui
->hshow
&& ui
->hpencil
&& !ui
->hcursor
) {
1624 int g
= newstate
->guess
[newstate
->common
->xinfo
[ui
->hx
+ ui
->hy
*(newstate
->common
->params
.w
+2)]];
1625 if (g
== 1 || g
== 2 || g
== 4)
1630 struct game_drawstate
{
1631 int tilesize
, started
, solved
;
1635 unsigned char *pencils
;
1637 unsigned char count_errors
[3];
1638 unsigned char *cell_errors
;
1639 unsigned char *hint_errors
;
1641 int hx
, hy
, hshow
, hpencil
; /* as for game_ui. */
1646 #define TILESIZE (ds->tilesize)
1647 #define BORDER (TILESIZE/2)
1649 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1650 int x
, int y
, int button
) {
1655 gx
= ((x
-BORDER
-1) / TILESIZE
);
1656 gy
= ((y
-BORDER
-2) / TILESIZE
) - 1;
1658 if (button
== 'a' || button
== 'A') {
1659 ds
->ascii
= ui
->ascii ? FALSE
: TRUE
;
1663 if (ui
->hshow
== 1 && ui
->hpencil
== 0) {
1664 xi
= state
->common
->xinfo
[ui
->hx
+ ui
->hy
*(state
->common
->params
.w
+2)];
1665 if (xi
>= 0 && !state
->common
->fixed
[xi
]) {
1666 if (button
== 'g' || button
== 'G' || button
== '1') {
1667 if (!ui
->hcursor
) ui
->hshow
= 0;
1668 sprintf(buf
,"G%d",xi
);
1671 if (button
== 'v' || button
== 'V' || button
== '2') {
1672 if (!ui
->hcursor
) ui
->hshow
= 0;
1673 sprintf(buf
,"V%d",xi
);
1676 if (button
== 'z' || button
== 'Z' || button
== '3') {
1677 if (!ui
->hcursor
) ui
->hshow
= 0;
1678 sprintf(buf
,"Z%d",xi
);
1681 if (button
== 'e' || button
== 'E' || button
== CURSOR_SELECT2
||
1682 button
== '0' || button
== '\b' ) {
1683 if (!ui
->hcursor
) ui
->hshow
= 0;
1684 sprintf(buf
,"E%d",xi
);
1690 if (IS_CURSOR_MOVE(button
)) {
1691 if (ui
->hx
== 0 && ui
->hy
== 0) {
1695 else switch (button
) {
1696 case CURSOR_UP
: ui
->hy
-= (ui
->hy
> 1) ?
1 : 0; break;
1697 case CURSOR_DOWN
: ui
->hy
+= (ui
->hy
< ds
->h
) ?
1 : 0; break;
1698 case CURSOR_RIGHT
: ui
->hx
+= (ui
->hx
< ds
->w
) ?
1 : 0; break;
1699 case CURSOR_LEFT
: ui
->hx
-= (ui
->hx
> 1) ?
1 : 0; break;
1701 ui
->hshow
= ui
->hcursor
= 1;
1704 if (ui
->hshow
&& button
== CURSOR_SELECT
) {
1705 ui
->hpencil
= 1 - ui
->hpencil
;
1710 if (ui
->hshow
== 1 && ui
->hpencil
== 1) {
1711 xi
= state
->common
->xinfo
[ui
->hx
+ ui
->hy
*(state
->common
->params
.w
+2)];
1712 if (xi
>= 0 && !state
->common
->fixed
[xi
]) {
1713 if (button
== 'g' || button
== 'G' || button
== '1') {
1714 sprintf(buf
,"g%d",xi
);
1715 ui
->hpencil
= ui
->hshow
= 0;
1718 if (button
== 'v' || button
== 'V' || button
== '2') {
1719 sprintf(buf
,"v%d",xi
);
1720 ui
->hpencil
= ui
->hshow
= 0;
1723 if (button
== 'z' || button
== 'Z' || button
== '3') {
1724 sprintf(buf
,"z%d",xi
);
1725 ui
->hpencil
= ui
->hshow
= 0;
1728 if (button
== 'e' || button
== 'E' || button
== CURSOR_SELECT2
||
1729 button
== '0' || button
== '\b') {
1730 if (!ui
->hcursor
) ui
->hshow
= 0;
1731 sprintf(buf
,"E%d",xi
);
1732 ui
->hpencil
= ui
->hshow
= 0;
1738 if (gx
> 0 && gx
< ds
->w
+1 && gy
> 0 && gy
< ds
->h
+1) {
1739 xi
= state
->common
->xinfo
[gx
+gy
*(state
->common
->params
.w
+2)];
1740 if (xi
>= 0 && !state
->common
->fixed
[xi
]) {
1741 g
= state
->guess
[xi
];
1742 if (ui
->hshow
== 0) {
1743 if (button
== LEFT_BUTTON
) {
1744 ui
->hshow
= 1; ui
->hpencil
= 0; ui
->hcursor
= 0;
1745 ui
->hx
= gx
; ui
->hy
= gy
;
1748 else if (button
== RIGHT_BUTTON
&& g
== 7) {
1749 ui
->hshow
= 1; ui
->hpencil
= 1; ui
->hcursor
= 0;
1750 ui
->hx
= gx
; ui
->hy
= gy
;
1754 else if (ui
->hshow
== 1) {
1755 if (button
== LEFT_BUTTON
) {
1756 if (ui
->hpencil
== 0) {
1757 if (gx
== ui
->hx
&& gy
== ui
->hy
) {
1758 ui
->hshow
= 0; ui
->hpencil
= 0; ui
->hcursor
= 0;
1759 ui
->hx
= 0; ui
->hy
= 0;
1763 ui
->hshow
= 1; ui
->hpencil
= 0; ui
->hcursor
= 0;
1764 ui
->hx
= gx
; ui
->hy
= gy
;
1769 ui
->hshow
= 1; ui
->hpencil
= 0; ui
->hcursor
= 0;
1770 ui
->hx
= gx
; ui
->hy
= gy
;
1774 else if (button
== RIGHT_BUTTON
) {
1775 if (ui
->hpencil
== 0 && g
== 7) {
1776 ui
->hshow
= 1; ui
->hpencil
= 1; ui
->hcursor
= 0;
1777 ui
->hx
= gx
; ui
->hy
= gy
;
1781 if (gx
== ui
->hx
&& gy
== ui
->hy
) {
1782 ui
->hshow
= 0; ui
->hpencil
= 0; ui
->hcursor
= 0;
1783 ui
->hx
= 0; ui
->hy
= 0;
1787 ui
->hshow
= 1; ui
->hpencil
= 1; ui
->hcursor
= 0;
1788 ui
->hx
= gx
; ui
->hy
= gy
;
1800 int check_numbers_draw(game_state
*state
, int *guess
) {
1803 int count_ghosts
, count_vampires
, count_zombies
;
1805 count_ghosts
= count_vampires
= count_zombies
= 0;
1806 for (i
=0;i
<state
->common
->num_total
;i
++) {
1807 if (guess
[i
] == 1) count_ghosts
++;
1808 if (guess
[i
] == 2) count_vampires
++;
1809 if (guess
[i
] == 4) count_zombies
++;
1813 filled
= (count_ghosts
+ count_vampires
+ count_zombies
>=
1814 state
->common
->num_total
);
1816 if (count_ghosts
> state
->common
->num_ghosts
||
1817 (filled
&& count_ghosts
!= state
->common
->num_ghosts
) ) {
1819 state
->count_errors
[0] = TRUE
;
1820 for (x
=1;x
<state
->common
->params
.w
+1;x
++)
1821 for (y
=1;y
<state
->common
->params
.h
+1;y
++) {
1822 xy
= x
+y
*(state
->common
->params
.w
+2);
1823 if (state
->common
->xinfo
[xy
] >= 0 &&
1824 guess
[state
->common
->xinfo
[xy
]] == 1)
1825 state
->cell_errors
[xy
] = TRUE
;
1828 if (count_vampires
> state
->common
->num_vampires
||
1829 (filled
&& count_vampires
!= state
->common
->num_vampires
) ) {
1831 state
->count_errors
[1] = TRUE
;
1832 for (x
=1;x
<state
->common
->params
.w
+1;x
++)
1833 for (y
=1;y
<state
->common
->params
.h
+1;y
++) {
1834 xy
= x
+y
*(state
->common
->params
.w
+2);
1835 if (state
->common
->xinfo
[xy
] >= 0 &&
1836 guess
[state
->common
->xinfo
[xy
]] == 2)
1837 state
->cell_errors
[xy
] = TRUE
;
1840 if (count_zombies
> state
->common
->num_zombies
||
1841 (filled
&& count_zombies
!= state
->common
->num_zombies
) ) {
1843 state
->count_errors
[2] = TRUE
;
1844 for (x
=1;x
<state
->common
->params
.w
+1;x
++)
1845 for (y
=1;y
<state
->common
->params
.h
+1;y
++) {
1846 xy
= x
+y
*(state
->common
->params
.w
+2);
1847 if (state
->common
->xinfo
[xy
] >= 0 &&
1848 guess
[state
->common
->xinfo
[xy
]] == 4)
1849 state
->cell_errors
[xy
] = TRUE
;
1856 int check_path_solution(game_state
*state
, int p
) {
1868 for (i
=0;i
<state
->common
->paths
[p
].length
;i
++) {
1869 if (state
->common
->paths
[p
].p
[i
] == -1) mirror
= TRUE
;
1871 if (state
->guess
[state
->common
->paths
[p
].p
[i
]] == 1 && mirror
)
1873 else if (state
->guess
[state
->common
->paths
[p
].p
[i
]] == 2 && !mirror
)
1875 else if (state
->guess
[state
->common
->paths
[p
].p
[i
]] == 4)
1877 else if (state
->guess
[state
->common
->paths
[p
].p
[i
]] == 7)
1882 if (unfilled
== 0 && count
!= state
->common
->paths
[p
].sightings_start
) {
1884 state
->hint_errors
[state
->common
->paths
[p
].grid_start
] = TRUE
;
1890 for (i
=state
->common
->paths
[p
].length
-1;i
>=0;i
--) {
1891 if (state
->common
->paths
[p
].p
[i
] == -1) mirror
= TRUE
;
1893 if (state
->guess
[state
->common
->paths
[p
].p
[i
]] == 1 && mirror
)
1895 else if (state
->guess
[state
->common
->paths
[p
].p
[i
]] == 2 && !mirror
)
1897 else if (state
->guess
[state
->common
->paths
[p
].p
[i
]] == 4)
1899 else if (state
->guess
[state
->common
->paths
[p
].p
[i
]] == 7)
1904 if (unfilled
== 0 && count
!= state
->common
->paths
[p
].sightings_end
) {
1906 state
->hint_errors
[state
->common
->paths
[p
].grid_end
] = TRUE
;
1910 for (i
=0;i
<state
->common
->paths
[p
].length
;i
++)
1911 state
->cell_errors
[state
->common
->paths
[p
].xy
[i
]] = TRUE
;
1917 static game_state
*execute_move(game_state
*state
, char *move
) {
1923 game_state
*ret
= dup_game(state
);
1932 if (c
== 'G' || c
== 'V' || c
== 'Z' || c
== 'E' ||
1933 c
== 'g' || c
== 'v' || c
== 'z') {
1935 sscanf(move
, "%d%n", &x
, &n
);
1936 if (c
== 'G') ret
->guess
[x
] = 1;
1937 if (c
== 'V') ret
->guess
[x
] = 2;
1938 if (c
== 'Z') ret
->guess
[x
] = 4;
1939 if (c
== 'E') { ret
->guess
[x
] = 7; ret
->pencils
[x
] = 0; }
1940 if (c
== 'g') ret
->pencils
[x
] ^= 1;
1941 if (c
== 'v') ret
->pencils
[x
] ^= 2;
1942 if (c
== 'z') ret
->pencils
[x
] ^= 4;
1945 if (*move
== ';') move
++;
1950 for (i
=0;i
<ret
->common
->wh
;i
++) ret
->cell_errors
[i
] = FALSE
;
1951 for (i
=0;i
<2*ret
->common
->num_paths
;i
++) ret
->hint_errors
[i
] = FALSE
;
1952 for (i
=0;i
<3;i
++) ret
->count_errors
[i
] = FALSE
;
1954 if (!check_numbers_draw(ret
,ret
->guess
)) correct
= FALSE
;
1956 for (p
=0;p
<state
->common
->num_paths
;p
++)
1957 if (!check_path_solution(ret
,p
)) correct
= FALSE
;
1959 for (i
=0;i
<state
->common
->num_total
;i
++)
1960 if (!(ret
->guess
[i
] == 1 || ret
->guess
[i
] == 2 ||
1961 ret
->guess
[i
] == 4)) correct
= FALSE
;
1963 if (correct
&& !solver
) ret
->solved
= TRUE
;
1964 if (solver
) ret
->cheated
= TRUE
;
1969 /* ----------------------------------------------------------------------
1973 #define PREFERRED_TILE_SIZE 64
1975 static void game_compute_size(game_params
*params
, int tilesize
,
1977 *x
= tilesize
+ (2 + params
->w
) * tilesize
;
1978 *y
= tilesize
+ (3 + params
->h
) * tilesize
;
1982 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1983 game_params
*params
, int tilesize
) {
1984 ds
->tilesize
= tilesize
;
1988 #define COLOUR(ret, i, r, g, b) ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
1990 static float *game_colours(frontend
*fe
, int *ncolours
) {
1991 float *ret
= snewn(3 * NCOLOURS
, float);
1993 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1995 ret
[COL_GRID
* 3 + 0] = 0.0F
;
1996 ret
[COL_GRID
* 3 + 1] = 0.0F
;
1997 ret
[COL_GRID
* 3 + 2] = 0.0F
;
1999 ret
[COL_TEXT
* 3 + 0] = 0.0F
;
2000 ret
[COL_TEXT
* 3 + 1] = 0.0F
;
2001 ret
[COL_TEXT
* 3 + 2] = 0.0F
;
2003 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
2004 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
2005 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
2007 ret
[COL_HIGHLIGHT
* 3 + 0] = 0.78F
* ret
[COL_BACKGROUND
* 3 + 0];
2008 ret
[COL_HIGHLIGHT
* 3 + 1] = 0.78F
* ret
[COL_BACKGROUND
* 3 + 1];
2009 ret
[COL_HIGHLIGHT
* 3 + 2] = 0.78F
* ret
[COL_BACKGROUND
* 3 + 2];
2011 ret
[COL_FLASH
* 3 + 0] = 1.0F
;
2012 ret
[COL_FLASH
* 3 + 1] = 1.0F
;
2013 ret
[COL_FLASH
* 3 + 2] = 1.0F
;
2015 ret
[COL_GHOST
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 0.5F
;
2016 ret
[COL_GHOST
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 0];
2017 ret
[COL_GHOST
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 0];
2019 ret
[COL_ZOMBIE
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0] * 0.5F
;
2020 ret
[COL_ZOMBIE
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 0];
2021 ret
[COL_ZOMBIE
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 0] * 0.5F
;
2023 ret
[COL_VAMPIRE
* 3 + 0] = ret
[COL_BACKGROUND
* 3 + 0];
2024 ret
[COL_VAMPIRE
* 3 + 1] = ret
[COL_BACKGROUND
* 3 + 0] * 0.9F
;
2025 ret
[COL_VAMPIRE
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 0] * 0.9F
;
2027 *ncolours
= NCOLOURS
;
2031 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
) {
2033 struct game_drawstate
*ds
= snew(struct game_drawstate
);
2036 ds
->started
= ds
->solved
= FALSE
;
2037 ds
->w
= state
->common
->params
.w
;
2038 ds
->h
= state
->common
->params
.h
;
2041 ds
->count_errors
[0] = FALSE
;
2042 ds
->count_errors
[1] = FALSE
;
2043 ds
->count_errors
[2] = FALSE
;
2045 ds
->monsters
= snewn(state
->common
->num_total
,int);
2046 for (i
=0;i
<(state
->common
->num_total
);i
++)
2047 ds
->monsters
[i
] = 7;
2048 ds
->pencils
= snewn(state
->common
->num_total
,unsigned char);
2049 for (i
=0;i
<state
->common
->num_total
;i
++)
2052 ds
->cell_errors
= snewn(state
->common
->wh
,unsigned char);
2053 for (i
=0;i
<state
->common
->wh
;i
++)
2054 ds
->cell_errors
[i
] = FALSE
;
2055 ds
->hint_errors
= snewn(2*state
->common
->num_paths
,unsigned char);
2056 for (i
=0;i
<2*state
->common
->num_paths
;i
++)
2057 ds
->hint_errors
[i
] = FALSE
;
2059 ds
->hshow
= ds
->hpencil
= ds
->hflash
= 0;
2060 ds
->hx
= ds
->hy
= 0;
2064 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
) {
2065 sfree(ds
->hint_errors
);
2066 sfree(ds
->cell_errors
);
2068 sfree(ds
->monsters
);
2073 static void draw_cell_background(drawing
*dr
, game_drawstate
*ds
,
2074 game_state
*state
, game_ui
*ui
, int x
, int y
) {
2078 dx
= BORDER
+(x
* ds
->tilesize
)+(TILESIZE
/2);
2079 dy
= BORDER
+(y
* ds
->tilesize
)+(TILESIZE
/2)+TILESIZE
;
2081 hon
= (ui
->hshow
&& x
== ui
->hx
&& y
== ui
->hy
);
2082 draw_rect(dr
,dx
-(TILESIZE
/2)+1,dy
-(TILESIZE
/2)+1,TILESIZE
-1,TILESIZE
-1,(hon
&& !ui
->hpencil
) ? COL_HIGHLIGHT
: COL_BACKGROUND
);
2084 if (hon
&& ui
->hpencil
) {
2086 coords
[0] = dx
-(TILESIZE
/2)+1;
2087 coords
[1] = dy
-(TILESIZE
/2)+1;
2088 coords
[2] = coords
[0] + TILESIZE
/2;
2089 coords
[3] = coords
[1];
2090 coords
[4] = coords
[0];
2091 coords
[5] = coords
[1] + TILESIZE
/2;
2092 draw_polygon(dr
, coords
, 3, COL_HIGHLIGHT
, COL_HIGHLIGHT
);
2095 draw_update(dr
,dx
-(TILESIZE
/2)+1,dy
-(TILESIZE
/2)+1,TILESIZE
-1,TILESIZE
-1);
2100 static void draw_circle_or_point(drawing
*dr
, int cx
, int cy
, int radius
,
2104 draw_circle(dr
, cx
, cy
, radius
, colour
, colour
);
2106 draw_rect(dr
, cx
, cy
, 1, 1, colour
);
2109 static void draw_monster(drawing
*dr
, game_drawstate
*ds
, int x
, int y
,
2110 int tilesize
, int hflash
, int monster
)
2112 int black
= (hflash ? COL_FLASH
: COL_TEXT
);
2114 if (monster
== 1) { /* ghost */
2117 clip(dr
,x
-(tilesize
/2)+2,y
-(tilesize
/2)+2,tilesize
-3,tilesize
/2+1);
2118 draw_circle(dr
,x
,y
,2*tilesize
/5, COL_GHOST
,black
);
2122 poly
[i
++] = x
- 2*tilesize
/5;
2124 poly
[i
++] = x
- 2*tilesize
/5;
2125 poly
[i
++] = y
+ 2*tilesize
/5;
2127 for (j
= 0; j
< 3; j
++) {
2128 int total
= (2*tilesize
/5) * 2;
2129 int before
= total
* j
/ 3;
2130 int after
= total
* (j
+1) / 3;
2131 int mid
= (before
+ after
) / 2;
2132 poly
[i
++] = x
- 2*tilesize
/5 + mid
;
2133 poly
[i
++] = y
+ 2*tilesize
/5 - (total
/ 6);
2134 poly
[i
++] = x
- 2*tilesize
/5 + after
;
2135 poly
[i
++] = y
+ 2*tilesize
/5;
2138 poly
[i
++] = x
+ 2*tilesize
/5;
2141 clip(dr
,x
-(tilesize
/2)+2,y
,tilesize
-3,tilesize
-(tilesize
/2)-1);
2142 draw_polygon(dr
, poly
, i
/2, COL_GHOST
, black
);
2145 draw_circle(dr
,x
-tilesize
/6,y
-tilesize
/12,tilesize
/10,
2146 COL_BACKGROUND
,black
);
2147 draw_circle(dr
,x
+tilesize
/6,y
-tilesize
/12,tilesize
/10,
2148 COL_BACKGROUND
,black
);
2150 draw_circle_or_point(dr
,x
-tilesize
/6+1+tilesize
/48,y
-tilesize
/12,
2152 draw_circle_or_point(dr
,x
+tilesize
/6+1+tilesize
/48,y
-tilesize
/12,
2155 } else if (monster
== 2) { /* vampire */
2158 clip(dr
,x
-(tilesize
/2)+2,y
-(tilesize
/2)+2,tilesize
-3,tilesize
/2);
2159 draw_circle(dr
,x
,y
,2*tilesize
/5,black
,black
);
2162 clip(dr
,x
-(tilesize
/2)+2,y
-(tilesize
/2)+2,tilesize
/2+1,tilesize
/2);
2163 draw_circle(dr
,x
-tilesize
/7,y
,2*tilesize
/5-tilesize
/7,
2166 clip(dr
,x
,y
-(tilesize
/2)+2,tilesize
/2+1,tilesize
/2);
2167 draw_circle(dr
,x
+tilesize
/7,y
,2*tilesize
/5-tilesize
/7,
2171 clip(dr
,x
-(tilesize
/2)+2,y
,tilesize
-3,tilesize
/2);
2172 draw_circle(dr
,x
,y
,2*tilesize
/5, COL_VAMPIRE
,black
);
2175 draw_circle(dr
, x
-tilesize
/7, y
-tilesize
/16, tilesize
/16,
2176 COL_BACKGROUND
, black
);
2177 draw_circle(dr
, x
+tilesize
/7, y
-tilesize
/16, tilesize
/16,
2178 COL_BACKGROUND
, black
);
2179 draw_circle_or_point(dr
, x
-tilesize
/7, y
-tilesize
/16, tilesize
/48,
2181 draw_circle_or_point(dr
, x
+tilesize
/7, y
-tilesize
/16, tilesize
/48,
2184 clip(dr
, x
-(tilesize
/2)+2, y
+tilesize
/8, tilesize
-3, tilesize
/4);
2187 poly
[i
++] = x
-3*tilesize
/16;
2188 poly
[i
++] = y
+1*tilesize
/8;
2189 poly
[i
++] = x
-2*tilesize
/16;
2190 poly
[i
++] = y
+7*tilesize
/24;
2191 poly
[i
++] = x
-1*tilesize
/16;
2192 poly
[i
++] = y
+1*tilesize
/8;
2193 draw_polygon(dr
, poly
, i
/2, COL_BACKGROUND
, black
);
2195 poly
[i
++] = x
+3*tilesize
/16;
2196 poly
[i
++] = y
+1*tilesize
/8;
2197 poly
[i
++] = x
+2*tilesize
/16;
2198 poly
[i
++] = y
+7*tilesize
/24;
2199 poly
[i
++] = x
+1*tilesize
/16;
2200 poly
[i
++] = y
+1*tilesize
/8;
2201 draw_polygon(dr
, poly
, i
/2, COL_BACKGROUND
, black
);
2203 draw_circle(dr
, x
, y
-tilesize
/5, 2*tilesize
/5, COL_VAMPIRE
, black
);
2206 } else if (monster
== 4) { /* zombie */
2207 draw_circle(dr
,x
,y
,2*tilesize
/5, COL_ZOMBIE
,black
);
2210 x
-tilesize
/7-tilesize
/16, y
-tilesize
/12-tilesize
/16,
2211 x
-tilesize
/7+tilesize
/16, y
-tilesize
/12+tilesize
/16,
2214 x
-tilesize
/7+tilesize
/16, y
-tilesize
/12-tilesize
/16,
2215 x
-tilesize
/7-tilesize
/16, y
-tilesize
/12+tilesize
/16,
2218 x
+tilesize
/7-tilesize
/16, y
-tilesize
/12-tilesize
/16,
2219 x
+tilesize
/7+tilesize
/16, y
-tilesize
/12+tilesize
/16,
2222 x
+tilesize
/7+tilesize
/16, y
-tilesize
/12-tilesize
/16,
2223 x
+tilesize
/7-tilesize
/16, y
-tilesize
/12+tilesize
/16,
2226 clip(dr
, x
-tilesize
/5, y
+tilesize
/6, 2*tilesize
/5+1, tilesize
/2);
2227 draw_circle(dr
, x
-tilesize
/15, y
+tilesize
/6, tilesize
/12,
2228 COL_BACKGROUND
, black
);
2231 draw_line(dr
, x
-tilesize
/5, y
+tilesize
/6, x
+tilesize
/5, y
+tilesize
/6,
2235 draw_update(dr
,x
-(tilesize
/2)+2,y
-(tilesize
/2)+2,tilesize
-3,tilesize
-3);
2238 static void draw_monster_count(drawing
*dr
, game_drawstate
*ds
,
2239 game_state
*state
, int c
, int hflash
) {
2246 dx
= BORDER
+(ds
->w
+2)*TILESIZE
/2+TILESIZE
/4;
2249 sprintf(buf
,"%d",state
->common
->num_ghosts
);
2254 sprintf(buf
,"%d",state
->common
->num_vampires
);
2258 sprintf(buf
,"%d",state
->common
->num_zombies
);
2265 draw_rect(dr
,dx
-2*TILESIZE
/3,dy
,3*TILESIZE
/2,dh
,COL_BACKGROUND
);
2266 draw_monster(dr
,ds
,dx
-TILESIZE
/3,dh
,2*TILESIZE
/3,hflash
,1<<c
);
2267 draw_text(dr
,dx
,dh
,FONT_VARIABLE
,dy
-1,ALIGN_HLEFT
|ALIGN_VCENTRE
,
2268 (state
->count_errors
[c
] ? COL_ERROR
: hflash ? COL_FLASH
: COL_TEXT
), buf
);
2269 draw_update(dr
,dx
-2*TILESIZE
/3,dy
,3*TILESIZE
/2,dh
);
2272 draw_rect(dr
,dx
-2*TILESIZE
/3,dy
,3*TILESIZE
/2,dh
,COL_BACKGROUND
);
2273 draw_text(dr
,dx
-TILESIZE
/3,dh
,FONT_VARIABLE
,dy
-1,
2274 ALIGN_HCENTRE
|ALIGN_VCENTRE
,
2275 hflash ? COL_FLASH
: COL_TEXT
, bufm
);
2276 draw_text(dr
,dx
,dh
,FONT_VARIABLE
,dy
-1,ALIGN_HLEFT
|ALIGN_VCENTRE
,
2277 (state
->count_errors
[c
] ? COL_ERROR
: hflash ? COL_FLASH
: COL_TEXT
), buf
);
2278 draw_update(dr
,dx
-2*TILESIZE
/3,dy
,3*TILESIZE
/2,dh
);
2284 static void draw_path_hint(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
2285 int i
, int hflash
, int start
) {
2290 p
= start ? state
->common
->paths
[i
].grid_start
: state
->common
->paths
[i
].grid_end
;
2291 range2grid(p
,state
->common
->params
.w
,state
->common
->params
.h
,&x
,&y
);
2292 error
= ds
->hint_errors
[p
];
2294 dx
= BORDER
+(x
* ds
->tilesize
)+(TILESIZE
/2);
2295 dy
= BORDER
+(y
* ds
->tilesize
)+(TILESIZE
/2)+TILESIZE
;
2296 sprintf(buf
,"%d", start ? state
->common
->paths
[i
].sightings_start
: state
->common
->paths
[i
].sightings_end
);
2297 draw_rect(dr
,dx
-(TILESIZE
/2)+2,dy
-(TILESIZE
/2)+2,TILESIZE
-3,TILESIZE
-3,COL_BACKGROUND
);
2298 draw_text(dr
,dx
,dy
,FONT_FIXED
,TILESIZE
/2,ALIGN_HCENTRE
|ALIGN_VCENTRE
, error ? COL_ERROR
: hflash ? COL_FLASH
: COL_TEXT
,buf
);
2299 draw_update(dr
,dx
-(TILESIZE
/2)+2,dy
-(TILESIZE
/2)+2,TILESIZE
-3,TILESIZE
-3);
2304 static void draw_mirror(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
2305 int x
, int y
, int hflash
, int mirror
) {
2306 int dx
,dy
,mx1
,my1
,mx2
,my2
;
2307 dx
= BORDER
+(x
* ds
->tilesize
)+(TILESIZE
/2);
2308 dy
= BORDER
+(y
* ds
->tilesize
)+(TILESIZE
/2)+TILESIZE
;
2310 if (mirror
== CELL_MIRROR_L
) {
2311 mx1
= dx
-(TILESIZE
/4);
2312 my1
= dy
-(TILESIZE
/4);
2313 mx2
= dx
+(TILESIZE
/4);
2314 my2
= dy
+(TILESIZE
/4);
2317 mx1
= dx
-(TILESIZE
/4);
2318 my1
= dy
+(TILESIZE
/4);
2319 mx2
= dx
+(TILESIZE
/4);
2320 my2
= dy
-(TILESIZE
/4);
2322 draw_thick_line(dr
,(float)(TILESIZE
/16),mx1
,my1
,mx2
,my2
,
2323 hflash ? COL_FLASH
: COL_TEXT
);
2324 draw_update(dr
,dx
-(TILESIZE
/2)+1,dy
-(TILESIZE
/2)+1,TILESIZE
-1,TILESIZE
-1);
2329 static void draw_big_monster(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
2330 int x
, int y
, int hflash
, int monster
)
2334 dx
= BORDER
+(x
* ds
->tilesize
)+(TILESIZE
/2);
2335 dy
= BORDER
+(y
* ds
->tilesize
)+(TILESIZE
/2)+TILESIZE
;
2337 if (monster
== 1) sprintf(buf
,"G");
2338 else if (monster
== 2) sprintf(buf
,"V");
2339 else if (monster
== 4) sprintf(buf
,"Z");
2340 else sprintf(buf
," ");
2341 draw_text(dr
,dx
,dy
,FONT_FIXED
,TILESIZE
/2,ALIGN_HCENTRE
|ALIGN_VCENTRE
,
2342 hflash ? COL_FLASH
: COL_TEXT
,buf
);
2343 draw_update(dr
,dx
-(TILESIZE
/2)+2,dy
-(TILESIZE
/2)+2,TILESIZE
-3,
2347 draw_monster(dr
, ds
, dx
, dy
, 3*TILESIZE
/4, hflash
, monster
);
2352 static void draw_pencils(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
2353 int x
, int y
, int pencil
) {
2358 dx
= BORDER
+(x
* ds
->tilesize
)+(TILESIZE
/4);
2359 dy
= BORDER
+(y
* ds
->tilesize
)+(TILESIZE
/4)+TILESIZE
;
2361 for (i
= 0, j
= 1; j
< 8; j
*= 2)
2367 for (py
= 0; py
< 2; py
++)
2368 for (px
= 0; px
< 2; px
++)
2369 if (monsters
[py
*2+px
]) {
2371 draw_monster(dr
, ds
,
2372 dx
+ TILESIZE
/2 * px
, dy
+ TILESIZE
/2 * py
,
2373 TILESIZE
/2, 0, monsters
[py
*2+px
]);
2376 switch (monsters
[py
*2+px
]) {
2377 case 1: sprintf(buf
,"G"); break;
2378 case 2: sprintf(buf
,"V"); break;
2379 case 4: sprintf(buf
,"Z"); break;
2381 draw_text(dr
,dx
+ TILESIZE
/2 * px
,dy
+ TILESIZE
/2 * py
,
2382 FONT_FIXED
,TILESIZE
/4,ALIGN_HCENTRE
|ALIGN_VCENTRE
,
2386 draw_update(dr
,dx
-(TILESIZE
/4)+2,dy
-(TILESIZE
/4)+2,
2387 (TILESIZE
/2)-3,(TILESIZE
/2)-3);
2392 #define FLASH_TIME 0.7F
2394 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
2395 game_state
*state
, int dir
, game_ui
*ui
,
2396 float animtime
, float flashtime
) {
2398 int stale
, xi
, c
, hflash
, hchanged
;
2400 hflash
= (int)(flashtime
* 5 / FLASH_TIME
) % 2;
2402 /* Draw static grid components at startup */
2404 draw_rect(dr
, 0, 0, 2*BORDER
+(ds
->w
+2)*TILESIZE
,
2405 2*BORDER
+(ds
->h
+3)*TILESIZE
, COL_BACKGROUND
);
2406 draw_rect(dr
, BORDER
+TILESIZE
-1, BORDER
+2*TILESIZE
-1,
2407 (ds
->w
)*TILESIZE
+3, (ds
->h
)*TILESIZE
+3, COL_GRID
);
2408 for (i
=0;i
<ds
->w
;i
++)
2409 for (j
=0;j
<ds
->h
;j
++)
2410 draw_rect(dr
, BORDER
+(ds
->tilesize
*(i
+1))+1,
2411 BORDER
+(ds
->tilesize
*(j
+2))+1, ds
->tilesize
-1,
2412 ds
->tilesize
-1, COL_BACKGROUND
);
2413 draw_update(dr
,BORDER
+TILESIZE
-1,BORDER
+2*TILESIZE
-1,
2414 (ds
->w
)*TILESIZE
+3, (ds
->h
)*TILESIZE
+3);
2418 if (ds
->hx
!= ui
->hx
|| ds
->hy
!= ui
->hy
||
2419 ds
->hshow
!= ui
->hshow
|| ds
->hpencil
!= ui
->hpencil
)
2422 /* Draw monster count hints */
2426 if (!ds
->started
) stale
= TRUE
;
2427 if (ds
->hflash
!= hflash
) stale
= TRUE
;
2428 if (ds
->ascii
!= ui
->ascii
) stale
= TRUE
;
2429 if (ds
->count_errors
[i
] != state
->count_errors
[i
]) {
2431 ds
->count_errors
[i
] = state
->count_errors
[i
];
2435 draw_monster_count(dr
, ds
, state
, i
, hflash
);
2439 /* Draw path count hints */
2440 for (i
=0;i
<state
->common
->num_paths
;i
++) {
2444 if (!ds
->started
) stale
= TRUE
;
2445 if (ds
->hflash
!= hflash
) stale
= TRUE
;
2447 p
= state
->common
->paths
[i
].grid_start
;
2448 if (ds
->hint_errors
[p
] != state
->hint_errors
[p
]) {
2450 ds
->hint_errors
[p
] = state
->hint_errors
[p
];
2454 draw_path_hint(dr
, ds
, state
, i
, hflash
, TRUE
);
2459 if (!ds
->started
) stale
= TRUE
;
2460 if (ds
->hflash
!= hflash
) stale
= TRUE
;
2462 p
= state
->common
->paths
[i
].grid_end
;
2463 if (ds
->hint_errors
[p
] != state
->hint_errors
[p
]) {
2465 ds
->hint_errors
[p
] = state
->hint_errors
[p
];
2469 draw_path_hint(dr
, ds
, state
, i
, hflash
, FALSE
);
2474 /* Draw puzzle grid contents */
2475 for (x
= 1; x
< ds
->w
+1; x
++)
2476 for (y
= 1; y
< ds
->h
+1; y
++) {
2478 xy
= x
+y
*(state
->common
->params
.w
+2);
2479 xi
= state
->common
->xinfo
[xy
];
2480 c
= state
->common
->grid
[xy
];
2482 if (!ds
->started
) stale
= TRUE
;
2483 if (ds
->hflash
!= hflash
) stale
= TRUE
;
2484 if (ds
->ascii
!= ui
->ascii
) stale
= TRUE
;
2487 if ((x
== ui
->hx
&& y
== ui
->hy
) ||
2488 (x
== ds
->hx
&& y
== ds
->hy
))
2492 if (xi
>= 0 && (state
->guess
[xi
] != ds
->monsters
[xi
]) ) {
2494 ds
->monsters
[xi
] = state
->guess
[xi
];
2497 if (xi
>= 0 && (state
->pencils
[xi
] != ds
->pencils
[xi
]) ) {
2499 ds
->pencils
[xi
] = state
->pencils
[xi
];
2502 if (state
->cell_errors
[xy
] != ds
->cell_errors
[xy
]) {
2504 ds
->cell_errors
[xy
] = state
->cell_errors
[xy
];
2508 draw_cell_background(dr
, ds
, state
, ui
, x
, y
);
2510 draw_mirror(dr
, ds
, state
, x
, y
, hflash
, c
);
2511 else if (state
->guess
[xi
] == 1 || state
->guess
[xi
] == 2 ||
2512 state
->guess
[xi
] == 4)
2513 draw_big_monster(dr
, ds
, state
, x
, y
, hflash
, state
->guess
[xi
]);
2515 draw_pencils(dr
, ds
, state
, x
, y
, state
->pencils
[xi
]);
2519 ds
->hx
= ui
->hx
; ds
->hy
= ui
->hy
;
2520 ds
->hshow
= ui
->hshow
;
2521 ds
->hpencil
= ui
->hpencil
;
2522 ds
->hflash
= hflash
;
2523 ui
->ascii
= ds
->ascii
;
2528 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
2529 int dir
, game_ui
*ui
) {
2533 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
2534 int dir
, game_ui
*ui
) {
2535 return (!oldstate
->solved
&& newstate
->solved
&& !oldstate
->cheated
&&
2536 !newstate
->cheated
) ? FLASH_TIME
: 0.0F
;
2539 static int game_status(game_state
*state
) {
2540 return state
->solved
;
2543 static int game_timing_state(game_state
*state
, game_ui
*ui
) {
2547 static void game_print_size(game_params
*params
, float *x
, float *y
) {
2550 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
) {
2554 #define thegame undead
2557 const struct game thegame
= {
2558 "Undead", "games.undead", "undead",
2565 TRUE
, game_configure
, custom_params
,
2573 TRUE
, game_can_format_as_text_now
, game_text_format
,
2581 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
2584 game_free_drawstate
,
2589 FALSE
, FALSE
, game_print_size
, game_print
,
2590 FALSE
, /* wants_statusbar */
2591 FALSE
, game_timing_state
,