--- /dev/null
+/*
+ * undead: Implementation of Haunted Mirror Mazes
+ *
+ * http://www.janko.at/Raetsel/Spukschloss/index.htm
+ *
+ * Puzzle definition is the total number of each monster type, the
+ * grid definition, and the list of sightings (clockwise, starting
+ * from top left corner)
+ *
+ * Example: (Janko puzzle No. 1,
+ * http://www.janko.at/Raetsel/Spukschloss/001.a.htm )
+ *
+ * Ghosts: 0 Vampires: 2 Zombies: 6
+ *
+ * 2 1 1 1
+ * 1 \ \ . / 2
+ * 0 \ . / . 2
+ * 0 / . / . 2
+ * 3 . . . \ 2
+ * 3 3 2 2
+ *
+ * would be encoded into:
+ * 4x4:0,2,6,LLaRLaRaRaRdL,2,1,1,1,2,2,2,2,2,2,3,3,3,0,0,1
+ *
+ * Additionally, the game description can contain monsters fixed at a
+ * certain grid position. The internal generator does not (yet) use
+ * this feature, but this is needed to enter puzzles like Janko No.
+ * 14, which is encoded as:
+ * 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
+ *
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+
+enum {
+ COL_BACKGROUND,
+ COL_GRID,
+ COL_TEXT,
+ COL_ERROR,
+ COL_HIGHLIGHT,
+ COL_FLASH,
+ COL_GHOST,
+ COL_ZOMBIE,
+ COL_VAMPIRE,
+ NCOLOURS
+};
+
+#define DIFFLIST(A) \
+ A(EASY,Easy,e) \
+ A(NORMAL,Normal,n) \
+ A(TRICKY,Tricky,t)
+#define ENUM(upper,title,lower) DIFF_ ## upper,
+#define TITLE(upper,title,lower) #title,
+#define ENCODE(upper,title,lower) #lower
+#define CONFIG(upper,title,lower) ":" #title
+enum { DIFFLIST(ENUM) DIFFCOUNT };
+static char const *const undead_diffnames[] = { DIFFLIST(TITLE) "(count)" };
+static char const undead_diffchars[] = DIFFLIST(ENCODE);
+#define DIFFCONFIG DIFFLIST(CONFIG)
+
+struct game_params {
+ int w; /* Grid width */
+ int h; /* Grid height */
+ int diff; /* Puzzle difficulty */
+};
+
+static const struct game_params undead_presets[] = {
+ { 4, 4, DIFF_EASY },
+ { 4, 4, DIFF_NORMAL },
+ { 4, 4, DIFF_TRICKY },
+ { 5, 5, DIFF_EASY },
+ { 5, 5, DIFF_NORMAL },
+ { 5, 5, DIFF_TRICKY },
+ { 7, 7, DIFF_EASY },
+ { 7, 7, DIFF_NORMAL }
+};
+
+#define DEFAULT_PRESET 1
+
+static game_params *default_params(void) {
+ game_params *ret = snew(game_params);
+
+ *ret = undead_presets[DEFAULT_PRESET];
+ return ret;
+}
+
+static int game_fetch_preset(int i, char **name, game_params **params) {
+ game_params *ret;
+ char buf[64];
+
+ if (i < 0 || i >= lenof(undead_presets)) return FALSE;
+
+ ret = default_params();
+ *ret = undead_presets[i]; /* struct copy */
+ *params = ret;
+
+ sprintf(buf, "%dx%d %s",
+ undead_presets[i].w, undead_presets[i].h,
+ undead_diffnames[undead_presets[i].diff]);
+ *name = dupstr(buf);
+
+ return TRUE;
+}
+
+static void free_params(game_params *params) {
+ sfree(params);
+}
+
+static game_params *dup_params(game_params *params) {
+ game_params *ret = snew(game_params);
+ *ret = *params; /* structure copy */
+ return ret;
+}
+
+static void decode_params(game_params *params, char const *string) {
+ params->w = params->h = atoi(string);
+
+ while (*string && isdigit((unsigned char) *string)) ++string;
+ if (*string == 'x') {
+ string++;
+ params->h = atoi(string);
+ while (*string && isdigit((unsigned char)*string)) string++;
+ }
+
+ params->diff = DIFF_NORMAL;
+ if (*string == 'd') {
+ int i;
+ string++;
+ for (i = 0; i < DIFFCOUNT; i++)
+ if (*string == undead_diffchars[i])
+ params->diff = i;
+ if (*string) string++;
+ }
+
+ return;
+}
+
+static char *encode_params(game_params *params, int full) {
+ char buf[256];
+ sprintf(buf, "%dx%d", params->w, params->h);
+ if (full)
+ sprintf(buf + strlen(buf), "d%c", undead_diffchars[params->diff]);
+ return dupstr(buf);
+}
+
+static config_item *game_configure(game_params *params) {
+ config_item *ret;
+ char buf[64];
+
+ ret = snewn(4, config_item);
+
+ ret[0].name = "Width";
+ ret[0].type = C_STRING;
+ sprintf(buf, "%d", params->w);
+ ret[0].sval = dupstr(buf);
+ ret[0].ival = 0;
+
+ ret[1].name = "Height";
+ ret[1].type = C_STRING;
+ sprintf(buf, "%d", params->h);
+ ret[1].sval = dupstr(buf);
+ ret[1].ival = 0;
+
+ ret[2].name = "Difficulty";
+ ret[2].type = C_CHOICES;
+ ret[2].sval = DIFFCONFIG;
+ ret[2].ival = params->diff;
+
+ ret[3].name = NULL;
+ ret[3].type = C_END;
+ ret[3].sval = NULL;
+ ret[3].ival = 0;
+
+ return ret;
+}
+
+static game_params *custom_params(config_item *cfg) {
+ game_params *ret = snew(game_params);
+
+ ret->w = atoi(cfg[0].sval);
+ ret->h = atoi(cfg[1].sval);
+ ret->diff = cfg[2].ival;
+ return ret;
+}
+
+static char *validate_params(game_params *params, int full) {
+ if ((params->w * params->h ) > 54) return "Grid is too big";
+ if (params->w < 3) return "Width must be at least 3";
+ if (params->h < 3) return "Height must be at least 3";
+ if (params->diff >= DIFFCOUNT) return "Unknown difficulty rating";
+ return NULL;
+}
+
+/* --------------------------------------------------------------- */
+/* Game state allocation, deallocation. */
+
+struct path {
+ int length;
+ int *p;
+ int grid_start;
+ int grid_end;
+ int num_monsters;
+ int *mapping;
+ int sightings_start;
+ int sightings_end;
+ int *xy;
+};
+
+struct game_common {
+ int refcount;
+ struct game_params params;
+ int wh;
+ int num_ghosts,num_vampires,num_zombies,num_total;
+ int num_paths;
+ struct path *paths;
+ int *grid;
+ int *xinfo;
+ int *fixed;
+ int solved;
+};
+
+struct game_state {
+ struct game_common *common;
+ int *guess;
+ unsigned char *pencils;
+ unsigned char *cell_errors;
+ unsigned char *hint_errors;
+ unsigned char count_errors[3];
+ int solved;
+ int cheated;
+};
+
+static game_state *new_state(game_params *params) {
+ int i;
+ game_state *state = snew(game_state);
+ state->common = snew(struct game_common);
+
+ state->common->refcount = 1;
+ state->common->params.w = params->w;
+ state->common->params.h = params->h;
+ state->common->params.diff = params->diff;
+
+ state->common->wh = (state->common->params.w +2) * (state->common->params.h +2);
+
+ state->common->num_ghosts = 0;
+ state->common->num_vampires = 0;
+ state->common->num_zombies = 0;
+ state->common->num_total = 0;
+
+ state->common->grid = snewn(state->common->wh, int);
+ state->common->xinfo = snewn(state->common->wh, int);
+ state->common->fixed = NULL;
+ state->common->solved = FALSE;
+
+ state->common->num_paths =
+ state->common->params.w + state->common->params.h;
+ state->common->paths = snewn(state->common->num_paths, struct path);
+
+ for (i=0;i<state->common->num_paths;i++) {
+ state->common->paths[i].length = 0;
+ state->common->paths[i].grid_start = -1;
+ state->common->paths[i].grid_end = -1;
+ state->common->paths[i].num_monsters = 0;
+ state->common->paths[i].sightings_start = 0;
+ state->common->paths[i].sightings_end = 0;
+ state->common->paths[i].p = snewn(state->common->wh,int);
+ state->common->paths[i].xy = snewn(state->common->wh,int);
+ state->common->paths[i].mapping = snewn(state->common->wh,int);
+ }
+
+ state->guess = NULL;
+ state->pencils = NULL;
+
+ state->cell_errors = snewn(state->common->wh, unsigned char);
+ for (i=0;i<state->common->wh;i++)
+ state->cell_errors[i] = FALSE;
+ state->hint_errors = snewn(2*state->common->num_paths, unsigned char);
+ for (i=0;i<2*state->common->num_paths;i++)
+ state->hint_errors[i] = FALSE;
+ for (i=0;i<3;i++)
+ state->count_errors[i] = FALSE;
+
+ state->solved = FALSE;
+ state->cheated = FALSE;
+
+ return state;
+}
+
+static game_state *dup_game(game_state *state) {
+ game_state *ret = snew(game_state);
+
+ ret->common = state->common;
+ ret->common->refcount++;
+
+ if (state->guess != NULL) {
+ ret->guess = snewn(ret->common->num_total,int);
+ memcpy(ret->guess, state->guess, ret->common->num_total*sizeof(int));
+ }
+ else ret->guess = NULL;
+
+ if (state->pencils != NULL) {
+ ret->pencils = snewn(ret->common->num_total,unsigned char);
+ memcpy(ret->pencils, state->pencils,
+ ret->common->num_total*sizeof(unsigned char));
+ }
+ else ret->pencils = NULL;
+
+ if (state->cell_errors != NULL) {
+ ret->cell_errors = snewn(ret->common->wh,unsigned char);
+ memcpy(ret->cell_errors, state->cell_errors,
+ ret->common->wh*sizeof(unsigned char));
+ }
+ else ret->cell_errors = NULL;
+
+ if (state->hint_errors != NULL) {
+ ret->hint_errors = snewn(2*ret->common->num_paths,unsigned char);
+ memcpy(ret->hint_errors, state->hint_errors,
+ 2*ret->common->num_paths*sizeof(unsigned char));
+ }
+ else ret->hint_errors = NULL;
+
+ ret->count_errors[0] = state->count_errors[0];
+ ret->count_errors[1] = state->count_errors[1];
+ ret->count_errors[2] = state->count_errors[2];
+
+ ret->solved = state->solved;
+ ret->cheated = state->cheated;
+
+ return ret;
+}
+
+static void free_game(game_state *state) {
+ int i;
+
+ state->common->refcount--;
+ if (state->common->refcount == 0) {
+ for (i=0;i<state->common->num_paths;i++) {
+ sfree(state->common->paths[i].mapping);
+ sfree(state->common->paths[i].xy);
+ sfree(state->common->paths[i].p);
+ }
+ sfree(state->common->paths);
+ sfree(state->common->xinfo);
+ sfree(state->common->grid);
+ if (state->common->fixed != NULL) sfree(state->common->fixed);
+ sfree(state->common);
+ }
+ if (state->hint_errors != NULL) sfree(state->hint_errors);
+ if (state->cell_errors != NULL) sfree(state->cell_errors);
+ if (state->pencils != NULL) sfree(state->pencils);
+ if (state->guess != NULL) sfree(state->guess);
+ sfree(state);
+
+ return;
+}
+
+/* --------------------------------------------------------------- */
+/* Puzzle generator */
+
+/* cell states */
+enum {
+ CELL_EMPTY,
+ CELL_MIRROR_L,
+ CELL_MIRROR_R,
+ CELL_GHOST,
+ CELL_VAMPIRE,
+ CELL_ZOMBIE,
+ CELL_UNDEF
+};
+
+/* grid walk directions */
+enum {
+ DIRECTION_NONE,
+ DIRECTION_UP,
+ DIRECTION_RIGHT,
+ DIRECTION_LEFT,
+ DIRECTION_DOWN
+};
+
+int range2grid(int rangeno, int width, int height, int *x, int *y) {
+
+ if (rangeno < 0) {
+ *x = 0; *y = 0; return DIRECTION_NONE;
+ }
+ if (rangeno < width) {
+ *x = rangeno+1; *y = 0; return DIRECTION_DOWN;
+ }
+ rangeno = rangeno - width;
+ if (rangeno < height) {
+ *x = width+1; *y = rangeno+1; return DIRECTION_LEFT;
+ }
+ rangeno = rangeno - height;
+ if (rangeno < width) {
+ *x = width-rangeno; *y = height+1; return DIRECTION_UP;
+ }
+ rangeno = rangeno - width;
+ if (rangeno < height) {
+ *x = 0; *y = height-rangeno; return DIRECTION_RIGHT;
+ }
+ *x = 0; *y = 0;
+ return DIRECTION_NONE;
+}
+
+int grid2range(int x, int y, int w, int h) {
+ if (x>0 && x<w+1 && y>0 && y<h+1) return -1;
+ if (x<0 || x>w+1 || y<0 || y>h+1) return -1;
+ if ((x == 0 || x==w+1) && (y==0 || y==h+1)) return -1;
+ if (y==0) return x-1;
+ if (x==(w+1)) return y-1+w;
+ if (y==(h+1)) return 2*w + h - x;
+ return 2*(w+h) - y;
+}
+
+void make_paths(game_state *state) {
+ int i;
+ int count = 0;
+
+ for (i=0;i<2*(state->common->params.w + state->common->params.h);i++) {
+ int x,y,dir;
+ int j,k,num_monsters;
+ int found;
+ int c,p;
+ found = FALSE;
+ /* Check whether inverse path is already in list */
+ for (j=0;j<count;j++) {
+ if (i == state->common->paths[j].grid_end) {
+ found = TRUE;
+ break;
+ }
+ }
+ if (found) continue;
+
+ /* We found a new path through the mirror maze */
+ state->common->paths[count].grid_start = i;
+ dir = range2grid(i, state->common->params.w,
+ state->common->params.h,&x,&y);
+ state->common->paths[count].sightings_start =
+ state->common->grid[x+y*(state->common->params.w +2)];
+ while (TRUE) {
+ int c,r;
+
+ if (dir == DIRECTION_DOWN) y++;
+ else if (dir == DIRECTION_LEFT) x--;
+ else if (dir == DIRECTION_UP) y--;
+ else if (dir == DIRECTION_RIGHT) x++;
+
+ r = grid2range(x, y, state->common->params.w,
+ state->common->params.h);
+ if (r != -1) {
+ state->common->paths[count].grid_end = r;
+ state->common->paths[count].sightings_end =
+ state->common->grid[x+y*(state->common->params.w +2)];
+ break;
+ }
+
+ c = state->common->grid[x+y*(state->common->params.w+2)];
+ state->common->paths[count].xy[state->common->paths[count].length] =
+ x+y*(state->common->params.w+2);
+ if (c == CELL_MIRROR_L) {
+ state->common->paths[count].p[state->common->paths[count].length] = -1;
+ if (dir == DIRECTION_DOWN) dir = DIRECTION_RIGHT;
+ else if (dir == DIRECTION_LEFT) dir = DIRECTION_UP;
+ else if (dir == DIRECTION_UP) dir = DIRECTION_LEFT;
+ else if (dir == DIRECTION_RIGHT) dir = DIRECTION_DOWN;
+ }
+ else if (c == CELL_MIRROR_R) {
+ state->common->paths[count].p[state->common->paths[count].length] = -1;
+ if (dir == DIRECTION_DOWN) dir = DIRECTION_LEFT;
+ else if (dir == DIRECTION_LEFT) dir = DIRECTION_DOWN;
+ else if (dir == DIRECTION_UP) dir = DIRECTION_RIGHT;
+ else if (dir == DIRECTION_RIGHT) dir = DIRECTION_UP;
+ }
+ else {
+ state->common->paths[count].p[state->common->paths[count].length] =
+ state->common->xinfo[x+y*(state->common->params.w+2)];
+ }
+ state->common->paths[count].length++;
+ }
+ /* Count unique monster entries in each path */
+ state->common->paths[count].num_monsters = 0;
+ for (j=0;j<state->common->num_total;j++) {
+ num_monsters = 0;
+ for (k=0;k<state->common->paths[count].length;k++)
+ if (state->common->paths[count].p[k] == j)
+ num_monsters++;
+ if (num_monsters > 0)
+ state->common->paths[count].num_monsters++;
+ }
+
+ /* Generate mapping vector */
+ c = 0;
+ for (p=0;p<state->common->paths[count].length;p++) {
+ int m;
+ m = state->common->paths[count].p[p];
+ if (m == -1) continue;
+ found = FALSE;
+ for (j=0; j<c; j++)
+ if (state->common->paths[count].mapping[j] == m) found = TRUE;
+ if (!found) state->common->paths[count].mapping[c++] = m;
+ }
+ count++;
+ }
+ return;
+}
+
+struct guess {
+ int length;
+ int *guess;
+ int *possible;
+};
+
+int next_list(struct guess *g, int pos) {
+
+ if (pos == 0) {
+ if ((g->guess[pos] == 1 && g->possible[pos] == 1) ||
+ (g->guess[pos] == 2 && (g->possible[pos] == 3 ||
+ g->possible[pos] == 2)) ||
+ g->guess[pos] == 4)
+ return FALSE;
+ if (g->guess[pos] == 1 && (g->possible[pos] == 3 ||
+ g->possible[pos] == 7)) {
+ g->guess[pos] = 2; return TRUE;
+ }
+ if (g->guess[pos] == 1 && g->possible[pos] == 5) {
+ g->guess[pos] = 4; return TRUE;
+ }
+ if (g->guess[pos] == 2 && (g->possible[pos] == 6 || g->possible[pos] == 7)) {
+ g->guess[pos] = 4; return TRUE;
+ }
+ }
+
+ if (g->guess[pos] == 1) {
+ if (g->possible[pos] == 1) {
+ return next_list(g,pos-1);
+ }
+ if (g->possible[pos] == 3 || g->possible[pos] == 7) {
+ g->guess[pos] = 2; return TRUE;
+ }
+ if (g->possible[pos] == 5) {
+ g->guess[pos] = 4; return TRUE;
+ }
+ }
+
+ if (g->guess[pos] == 2) {
+ if (g->possible[pos] == 2) {
+ return next_list(g,pos-1);
+ }
+ if (g->possible[pos] == 3) {
+ g->guess[pos] = 1; return next_list(g,pos-1);
+ }
+ if (g->possible[pos] == 6 || g->possible[pos] == 7) {
+ g->guess[pos] = 4; return TRUE;
+ }
+ }
+
+ if (g->guess[pos] == 4) {
+ if (g->possible[pos] == 5 || g->possible[pos] == 7) {
+ g->guess[pos] = 1; return next_list(g,pos-1);
+ }
+ if (g->possible[pos] == 6) {
+ g->guess[pos] = 2; return next_list(g,pos-1);
+ }
+ if (g->possible[pos] == 4) {
+ return next_list(g,pos-1);
+ }
+ }
+ return FALSE;
+}
+
+void get_unique(game_state *state, int counter, random_state *rs) {
+
+ int p,i,c,count_uniques;
+ struct guess path_guess;
+
+ struct entry {
+ struct entry *link;
+ int *guess;
+ int start_view;
+ int end_view;
+ };
+
+ struct {
+ struct entry *head;
+ struct entry *node;
+ } views, single_views, loop_views, test_views;
+
+ struct entry test_entry;
+
+ path_guess.length = state->common->paths[counter].num_monsters;
+ path_guess.guess = snewn(path_guess.length,int);
+ path_guess.possible = snewn(path_guess.length,int);
+ for (i=0;i<path_guess.length;i++)
+ path_guess.guess[i] = path_guess.possible[i] = 0;
+
+ for (p=0;p<path_guess.length;p++) {
+ path_guess.possible[p] =
+ state->guess[state->common->paths[counter].mapping[p]];
+ switch (path_guess.possible[p]) {
+ case 1: path_guess.guess[p] = 1; break;
+ case 2: path_guess.guess[p] = 2; break;
+ case 3: path_guess.guess[p] = 1; break;
+ case 4: path_guess.guess[p] = 4; break;
+ case 5: path_guess.guess[p] = 1; break;
+ case 6: path_guess.guess[p] = 2; break;
+ case 7: path_guess.guess[p] = 1; break;
+ }
+ }
+
+ views.head = NULL;
+ views.node = NULL;
+
+ do {
+ int mirror;
+
+ views.node = snewn(1,struct entry);
+ views.node->link = views.head;
+ views.node->guess = snewn(path_guess.length,int);
+ views.head = views.node;
+ views.node->start_view = 0;
+ views.node->end_view = 0;
+ memcpy(views.node->guess, path_guess.guess,
+ path_guess.length*sizeof(int));
+
+ mirror = FALSE;
+ for (p=0;p<state->common->paths[counter].length;p++) {
+ if (state->common->paths[counter].p[p] == -1) mirror = TRUE;
+ else {
+ for (i=0;i<path_guess.length;i++) {
+ if (state->common->paths[counter].p[p] ==
+ state->common->paths[counter].mapping[i]) {
+ if (path_guess.guess[i] == 1 && mirror == TRUE)
+ views.node->start_view++;
+ if (path_guess.guess[i] == 2 && mirror == FALSE)
+ views.node->start_view++;
+ if (path_guess.guess[i] == 4)
+ views.node->start_view++;
+ break;
+ }
+ }
+ }
+ }
+ mirror = FALSE;
+ for (p=state->common->paths[counter].length-1;p>=0;p--) {
+ if (state->common->paths[counter].p[p] == -1) mirror = TRUE;
+ else {
+ for (i=0;i<path_guess.length;i++) {
+ if (state->common->paths[counter].p[p] ==
+ state->common->paths[counter].mapping[i]) {
+ if (path_guess.guess[i] == 1 && mirror == TRUE)
+ views.node->end_view++;
+ if (path_guess.guess[i] == 2 && mirror == FALSE)
+ views.node->end_view++;
+ if (path_guess.guess[i] == 4)
+ views.node->end_view++;
+ break;
+ }
+ }
+ }
+ }
+ } while (next_list(&path_guess, path_guess.length-1));
+
+ /* extract single entries from view list */
+
+ test_views.head = views.head;
+ test_views.node = views.node;
+
+ test_entry.guess = snewn(path_guess.length,int);
+
+ single_views.head = NULL;
+ single_views.node = NULL;
+
+ count_uniques = 0;
+ while (test_views.head != NULL) {
+ test_views.node = test_views.head;
+ test_views.head = test_views.head->link;
+ c = 0;
+ loop_views.head = views.head;
+ loop_views.node = views.node;
+ while (loop_views.head != NULL) {
+ loop_views.node = loop_views.head;
+ loop_views.head = loop_views.head->link;
+ if (test_views.node->start_view == loop_views.node->start_view &&
+ test_views.node->end_view == loop_views.node->end_view)
+ c++;
+ }
+ if (c == 1) {
+ single_views.node = snewn(1,struct entry);
+ single_views.node->link = single_views.head;
+ single_views.node->guess = snewn(path_guess.length,int);
+ single_views.head = single_views.node;
+ single_views.node->start_view = test_views.node->start_view;
+ single_views.node->end_view = test_views.node->end_view;
+ memcpy(single_views.node->guess, test_views.node->guess,
+ path_guess.length*sizeof(int));
+ count_uniques++;
+ }
+ }
+
+ if (count_uniques > 0) {
+ test_entry.start_view = 0;
+ test_entry.end_view = 0;
+ /* Choose one unique guess per random */
+ /* While we are busy with looping through single_views, we
+ * conveniently free the linked list single_view */
+ c = random_upto(rs,count_uniques);
+ while(single_views.head != NULL) {
+ single_views.node = single_views.head;
+ single_views.head = single_views.head->link;
+ if (c-- == 0) {
+ memcpy(test_entry.guess, single_views.node->guess,
+ path_guess.length*sizeof(int));
+ test_entry.start_view = single_views.node->start_view;
+ test_entry.end_view = single_views.node->end_view;
+ }
+ sfree(single_views.node->guess);
+ sfree(single_views.node);
+ }
+
+ /* Modify state_guess according to path_guess.mapping */
+ for (i=0;i<path_guess.length;i++)
+ state->guess[state->common->paths[counter].mapping[i]] =
+ test_entry.guess[i];
+ }
+
+ sfree(test_entry.guess);
+
+ while (views.head != NULL) {
+ views.node = views.head;
+ views.head = views.head->link;
+ sfree(views.node->guess);
+ sfree(views.node);
+ }
+
+ sfree(path_guess.possible);
+ sfree(path_guess.guess);
+
+ return;
+}
+
+int count_monsters(game_state *state,
+ int *cGhost, int *cVampire, int *cZombie) {
+ int cNone;
+ int i;
+
+ *cGhost = *cVampire = *cZombie = cNone = 0;
+
+ for (i=0;i<state->common->num_total;i++) {
+ if (state->guess[i] == 1) (*cGhost)++;
+ else if (state->guess[i] == 2) (*cVampire)++;
+ else if (state->guess[i] == 4) (*cZombie)++;
+ else cNone++;
+ }
+
+ return cNone;
+}
+
+int check_numbers(game_state *state, int *guess) {
+ int valid;
+ int i;
+ int count_ghosts, count_vampires, count_zombies;
+
+ count_ghosts = count_vampires = count_zombies = 0;
+ for (i=0;i<state->common->num_total;i++) {
+ if (guess[i] == 1) count_ghosts++;
+ if (guess[i] == 2) count_vampires++;
+ if (guess[i] == 4) count_zombies++;
+ }
+
+ valid = TRUE;
+
+ if (count_ghosts > state->common->num_ghosts) valid = FALSE;
+ if (count_vampires > state->common->num_vampires) valid = FALSE;
+ if (count_zombies > state->common->num_zombies) valid = FALSE;
+
+ return valid;
+}
+
+int check_solution(int *g, struct path path) {
+ int i;
+ int mirror;
+ int count;
+
+ count = 0;
+ mirror = FALSE;
+ for (i=0;i<path.length;i++) {
+ if (path.p[i] == -1) mirror = TRUE;
+ else {
+ if (g[path.p[i]] == 1 && mirror) count++;
+ else if (g[path.p[i]] == 2 && !mirror) count++;
+ else if (g[path.p[i]] == 4) count++;
+ }
+ }
+ if (count != path.sightings_start) return FALSE;
+
+ count = 0;
+ mirror = FALSE;
+ for (i=path.length-1;i>=0;i--) {
+ if (path.p[i] == -1) mirror = TRUE;
+ else {
+ if (g[path.p[i]] == 1 && mirror) count++;
+ else if (g[path.p[i]] == 2 && !mirror) count++;
+ else if (g[path.p[i]] == 4) count++;
+ }
+ }
+ if (count != path.sightings_end) return FALSE;
+
+ return TRUE;
+}
+
+int solve_iterative(game_state *state, struct path *paths) {
+ int solved;
+ int p,i,j,count;
+
+ int *guess;
+ int *possible;
+
+ struct guess loop;
+
+ solved = TRUE;
+ loop.length = state->common->num_total;
+ guess = snewn(state->common->num_total,int);
+ possible = snewn(state->common->num_total,int);
+
+ for (i=0;i<state->common->num_total;i++) {
+ guess[i] = state->guess[i];
+ possible[i] = 0;
+ }
+
+ for (p=0;p<state->common->num_paths;p++) {
+ if (paths[p].num_monsters > 0) {
+ loop.length = paths[p].num_monsters;
+ loop.guess = snewn(paths[p].num_monsters,int);
+ loop.possible = snewn(paths[p].num_monsters,int);
+
+ for (i=0;i<paths[p].num_monsters;i++) {
+ switch (state->guess[paths[p].mapping[i]]) {
+ case 1: loop.guess[i] = 1; break;
+ case 2: loop.guess[i] = 2; break;
+ case 3: loop.guess[i] = 1; break;
+ case 4: loop.guess[i] = 4; break;
+ case 5: loop.guess[i] = 1; break;
+ case 6: loop.guess[i] = 2; break;
+ case 7: loop.guess[i] = 1; break;
+ }
+ loop.possible[i] = state->guess[paths[p].mapping[i]];
+ possible[paths[p].mapping[i]] = 0;
+ }
+
+ while(TRUE) {
+ for (i=0;i<state->common->num_total;i++) {
+ guess[i] = state->guess[i];
+ }
+ count = 0;
+ for (i=0;i<paths[p].num_monsters;i++)
+ guess[paths[p].mapping[i]] = loop.guess[count++];
+ if (check_numbers(state,guess) &&
+ check_solution(guess,paths[p]))
+ for (j=0;j<paths[p].num_monsters;j++)
+ possible[paths[p].mapping[j]] |= loop.guess[j];
+ if (!next_list(&loop,loop.length-1)) break;
+ }
+ for (i=0;i<paths[p].num_monsters;i++)
+ state->guess[paths[p].mapping[i]] &=
+ possible[paths[p].mapping[i]];
+ sfree(loop.possible);
+ sfree(loop.guess);
+ }
+ }
+
+ for (i=0;i<state->common->num_total;i++) {
+ if (state->guess[i] == 3 || state->guess[i] == 5 ||
+ state->guess[i] == 6 || state->guess[i] == 7) {
+ solved = FALSE; break;
+ }
+ }
+
+ sfree(possible);
+ sfree(guess);
+
+ return solved;
+}
+
+int solve_bruteforce(game_state *state, struct path *paths) {
+ int solved, correct;
+ int number_solutions;
+ int p,i;
+
+ struct guess loop;
+
+ loop.guess = snewn(state->common->num_total,int);
+ loop.possible = snewn(state->common->num_total,int);
+
+ for (i=0;i<state->common->num_total;i++) {
+ loop.possible[i] = state->guess[i];
+ switch (state->guess[i]) {
+ case 1: loop.guess[i] = 1; break;
+ case 2: loop.guess[i] = 2; break;
+ case 3: loop.guess[i] = 1; break;
+ case 4: loop.guess[i] = 4; break;
+ case 5: loop.guess[i] = 1; break;
+ case 6: loop.guess[i] = 2; break;
+ case 7: loop.guess[i] = 1; break;
+ }
+ }
+
+ solved = FALSE;
+ number_solutions = 0;
+
+ while (TRUE) {
+
+ correct = TRUE;
+ if (!check_numbers(state,loop.guess)) correct = FALSE;
+ else
+ for (p=0;p<state->common->num_paths;p++)
+ if (!check_solution(loop.guess,paths[p])) {
+ correct = FALSE; break;
+ }
+ if (correct) {
+ number_solutions++;
+ solved = TRUE;
+ if(number_solutions > 1) {
+ solved = FALSE;
+ break;
+ }
+ for (i=0;i<state->common->num_total;i++)
+ state->guess[i] = loop.guess[i];
+ }
+ if (!next_list(&loop,state->common->num_total -1)) {
+ break;
+ }
+ }
+
+ sfree(loop.possible);
+ sfree(loop.guess);
+
+ return solved;
+}
+
+int path_cmp(const void *a, const void *b) {
+ const struct path *pa = (const struct path *)a;
+ const struct path *pb = (const struct path *)b;
+ return pa->num_monsters - pb->num_monsters;
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive) {
+ int i,count,c,w,h,r,p,g;
+ game_state *new;
+
+ /* Variables for puzzle generation algorithm */
+ int filling;
+ int max_length;
+ int count_ghosts, count_vampires, count_zombies;
+ int abort;
+ float ratio;
+
+ /* Variables for solver algorithm */
+ int solved_iterative, solved_bruteforce, contains_inconsistency,
+ count_ambiguous;
+ int iterative_depth;
+ int *old_guess;
+
+ /* Variables for game description generation */
+ int x,y;
+ char *e;
+ char *desc;
+
+ i = 0;
+ while (TRUE) {
+ new = new_state(params);
+ abort = FALSE;
+
+ /* Fill grid with random mirrors and (later to be populated)
+ * empty monster cells */
+ count = 0;
+ for (h=1;h<new->common->params.h+1;h++)
+ for (w=1;w<new->common->params.w+1;w++) {
+ c = random_upto(rs,5);
+ if (c >= 2) {
+ new->common->grid[w+h*(new->common->params.w+2)] = CELL_EMPTY;
+ new->common->xinfo[w+h*(new->common->params.w+2)] = count++;
+ }
+ else if (c == 0) {
+ new->common->grid[w+h*(new->common->params.w+2)] =
+ CELL_MIRROR_L;
+ new->common->xinfo[w+h*(new->common->params.w+2)] = -1;
+ }
+ else {
+ new->common->grid[w+h*(new->common->params.w+2)] =
+ CELL_MIRROR_R;
+ new->common->xinfo[w+h*(new->common->params.w+2)] = -1;
+ }
+ }
+ new->common->num_total = count; /* Total number of monsters in maze */
+
+ /* Puzzle is boring if it has too few monster cells. Discard
+ * grid, make new grid */
+ if (new->common->num_total <= 4) {
+ free_game(new);
+ continue;
+ }
+
+ /* Monsters / Mirrors ratio should be balanced */
+ ratio = (float)new->common->num_total /
+ (float)(new->common->params.w * new->common->params.h);
+ if (ratio < 0.48 || ratio > 0.78) {
+ free_game(new);
+ continue;
+ }
+
+ /* Assign clue identifiers */
+ for (r=0;r<2*(new->common->params.w+new->common->params.h);r++) {
+ int x,y,gridno;
+ gridno = range2grid(r,new->common->params.w,new->common->params.h,
+ &x,&y);
+ new->common->grid[x+y*(new->common->params.w +2)] = gridno;
+ new->common->xinfo[x+y*(new->common->params.w +2)] = 0;
+ }
+ /* The four corners don't matter at all for the game. Set them
+ * all to zero, just to have a nice data structure */
+ new->common->grid[0] = 0;
+ new->common->xinfo[0] = 0;
+ new->common->grid[new->common->params.w+1] = 0;
+ new->common->xinfo[new->common->params.w+1] = 0;
+ new->common->grid[new->common->params.w+1 + (new->common->params.h+1)*(new->common->params.w+2)] = 0;
+ new->common->xinfo[new->common->params.w+1 + (new->common->params.h+1)*(new->common->params.w+2)] = 0;
+ new->common->grid[(new->common->params.h+1)*(new->common->params.w+2)] = 0;
+ new->common->xinfo[(new->common->params.h+1)*(new->common->params.w+2)] = 0;
+
+ /* Initialize solution vector */
+ new->guess = snewn(new->common->num_total,int);
+ for (g=0;g<new->common->num_total;g++) new->guess[g] = 7;
+
+ /* Initialize fixed flag from common. Not needed for the
+ * puzzle generator; initialize it for having clean code */
+ new->common->fixed = snewn(new->common->num_total,int);
+ for (g=0;g<new->common->num_total;g++)
+ new->common->fixed[g] = FALSE;
+
+ /* paths generation */
+ make_paths(new);
+
+ /* Grid is invalid if max. path length > threshold. Discard
+ * grid, make new one */
+ switch (new->common->params.diff) {
+ case DIFF_EASY: max_length = min(new->common->params.w,new->common->params.h) + 1; break;
+ case DIFF_NORMAL: max_length = (max(new->common->params.w,new->common->params.h) * 3) / 2; break;
+ case DIFF_TRICKY: max_length = 9; break;
+ default: max_length = 9; break;
+ }
+
+ for (p=0;p<new->common->num_paths;p++) {
+ if (new->common->paths[p].num_monsters > max_length) {
+ abort = TRUE;
+ }
+ }
+ if (abort) {
+ free_game(new);
+ continue;
+ }
+
+ qsort(new->common->paths, new->common->num_paths,
+ sizeof(struct path), path_cmp);
+
+ /* Grid monster initialization */
+ /* For easy puzzles, we try to fill nearly the whole grid
+ with unique solution paths (up to 2) For more difficult
+ puzzles, we fill only roughly half the grid, and choose
+ random monsters for the rest For hard puzzles, we fill
+ even less paths with unique solutions */
+
+ switch (new->common->params.diff) {
+ case DIFF_EASY: filling = 2; break;
+ case DIFF_NORMAL: filling = min( (new->common->params.w+new->common->params.h) , (new->common->num_total)/2 ); break;
+ case DIFF_TRICKY: filling = max( (new->common->params.w+new->common->params.h) , (new->common->num_total)/2 ); break;
+ default: filling = 0; break;
+ }
+
+ count = 0;
+ while ( (count_monsters(new, &count_ghosts, &count_vampires,
+ &count_zombies)) > filling) {
+ if ((count) >= new->common->num_paths) break;
+ if (new->common->paths[count].num_monsters == 0) {
+ count++;
+ continue;
+ }
+ get_unique(new,count,rs);
+ count++;
+ }
+
+ /* Fill any remaining ambiguous entries with random monsters */
+ for(g=0;g<new->common->num_total;g++) {
+ if (new->guess[g] == 7) {
+ r = random_upto(rs,3);
+ new->guess[g] = (r == 0) ? 1 : ( (r == 1) ? 2 : 4 );
+ }
+ }
+
+ /* Determine all hints */
+ count_monsters(new, &new->common->num_ghosts,
+ &new->common->num_vampires, &new->common->num_zombies);
+
+ /* Puzzle is trivial if it has only one type of monster. Discard. */
+ if ((new->common->num_ghosts == 0 && new->common->num_vampires == 0) ||
+ (new->common->num_ghosts == 0 && new->common->num_zombies == 0) ||
+ (new->common->num_vampires == 0 && new->common->num_zombies == 0)) {
+ free_game(new);
+ continue;
+ }
+
+ /* Discard puzzle if difficulty Tricky, and it has only 1
+ * member of any monster type */
+ if (new->common->params.diff == DIFF_TRICKY &&
+ (new->common->num_ghosts <= 1 ||
+ new->common->num_vampires <= 1 || new->common->num_zombies <= 1)) {
+ free_game(new);
+ continue;
+ }
+
+ for (w=1;w<new->common->params.w+1;w++)
+ for (h=1;h<new->common->params.h+1;h++) {
+ c = new->common->xinfo[w+h*(new->common->params.w+2)];
+ if (c >= 0) {
+ if (new->guess[c] == 1) new->common->grid[w+h*(new->common->params.w+2)] = CELL_GHOST;
+ if (new->guess[c] == 2) new->common->grid[w+h*(new->common->params.w+2)] = CELL_VAMPIRE;
+ if (new->guess[c] == 4) new->common->grid[w+h*(new->common->params.w+2)] = CELL_ZOMBIE;
+ }
+ }
+
+ /* Prepare path information needed by the solver (containing all hints) */
+ for (p=0;p<new->common->num_paths;p++) {
+ int mirror,x,y;
+
+ new->common->paths[p].sightings_start = 0;
+ new->common->paths[p].sightings_end = 0;
+
+ mirror = FALSE;
+ for (g=0;g<new->common->paths[p].length;g++) {
+
+ if (new->common->paths[p].p[g] == -1) mirror = TRUE;
+ else {
+ if (new->guess[new->common->paths[p].p[g]] == 1 && mirror == TRUE) (new->common->paths[p].sightings_start)++;
+ else if (new->guess[new->common->paths[p].p[g]] == 2 && mirror == FALSE) (new->common->paths[p].sightings_start)++;
+ else if (new->guess[new->common->paths[p].p[g]] == 4) (new->common->paths[p].sightings_start)++;
+ }
+ }
+
+ mirror = FALSE;
+ for (g=new->common->paths[p].length-1;g>=0;g--) {
+ if (new->common->paths[p].p[g] == -1) mirror = TRUE;
+ else {
+ if (new->guess[new->common->paths[p].p[g]] == 1 && mirror == TRUE) (new->common->paths[p].sightings_end)++;
+ else if (new->guess[new->common->paths[p].p[g]] == 2 && mirror == FALSE) (new->common->paths[p].sightings_end)++;
+ else if (new->guess[new->common->paths[p].p[g]] == 4) (new->common->paths[p].sightings_end)++;
+ }
+ }
+
+ range2grid(new->common->paths[p].grid_start,
+ new->common->params.w,new->common->params.h,&x,&y);
+ new->common->grid[x+y*(new->common->params.w +2)] =
+ new->common->paths[p].sightings_start;
+ range2grid(new->common->paths[p].grid_end,
+ new->common->params.w,new->common->params.h,&x,&y);
+ new->common->grid[x+y*(new->common->params.w +2)] =
+ new->common->paths[p].sightings_end;
+ }
+
+ /* Try to solve the puzzle with the iterative solver */
+ old_guess = snewn(new->common->num_total,int);
+ for (p=0;p<new->common->num_total;p++) {
+ new->guess[p] = 7;
+ old_guess[p] = 7;
+ }
+ iterative_depth = 0;
+ solved_iterative = FALSE;
+ contains_inconsistency = FALSE;
+ count_ambiguous = 0;
+
+ while (TRUE) {
+ int no_change;
+ no_change = TRUE;
+ solved_iterative = solve_iterative(new,new->common->paths);
+ iterative_depth++;
+ for (p=0;p<new->common->num_total;p++) {
+ if (new->guess[p] != old_guess[p]) no_change = FALSE;
+ old_guess[p] = new->guess[p];
+ if (new->guess[p] == 0) contains_inconsistency = TRUE;
+ }
+ if (solved_iterative || no_change) break;
+ }
+
+ /* If necessary, try to solve the puzzle with the brute-force solver */
+ solved_bruteforce = FALSE;
+ if (new->common->params.diff != DIFF_EASY &&
+ !solved_iterative && !contains_inconsistency) {
+ for (p=0;p<new->common->num_total;p++)
+ if (new->guess[p] != 1 && new->guess[p] != 2 &&
+ new->guess[p] != 4) count_ambiguous++;
+
+ solved_bruteforce = solve_bruteforce(new, new->common->paths);
+ }
+
+ /* Determine puzzle difficulty level */
+ if (new->common->params.diff == DIFF_EASY && solved_iterative &&
+ iterative_depth <= 3 && !contains_inconsistency) {
+/* printf("Puzzle level: EASY Level %d Ratio %f Ambiguous %d (Found after %i tries)\n",iterative_depth, ratio, count_ambiguous, i); */
+ break;
+ }
+
+ if (new->common->params.diff == DIFF_NORMAL &&
+ ((solved_iterative && iterative_depth > 3) ||
+ (solved_bruteforce && count_ambiguous < 4)) &&
+ !contains_inconsistency) {
+/* printf("Puzzle level: NORMAL Level %d Ratio %f Ambiguous %d (Found after %d tries)\n", iterative_depth, ratio, count_ambiguous, i); */
+ break;
+ }
+ if (new->common->params.diff == DIFF_TRICKY &&
+ solved_bruteforce && iterative_depth > 0 &&
+ count_ambiguous >= 4 && !contains_inconsistency) {
+/* printf("Puzzle level: TRICKY Level %d Ratio %f Ambiguous %d (Found after %d tries)\n", iterative_depth, ratio, count_ambiguous, i); */
+ break;
+ }
+
+ /* If puzzle is not solvable or does not satisfy the desired
+ * difficulty level, free memory and start from scratch */
+ sfree(old_guess);
+ free_game(new);
+ i++;
+ }
+
+ /* We have a valid puzzle! */
+
+ desc = snewn(10 + new->common->wh +
+ 6*(new->common->params.w + new->common->params.h), char);
+ e = desc;
+
+ /* Encode monster counts */
+ e += sprintf(e, "%d,", new->common->num_ghosts);
+ e += sprintf(e, "%d,", new->common->num_vampires);
+ e += sprintf(e, "%d,", new->common->num_zombies);
+
+ /* Encode grid */
+ count = 0;
+ for (y=1;y<new->common->params.h+1;y++)
+ for (x=1;x<new->common->params.w+1;x++) {
+ c = new->common->grid[x+y*(new->common->params.w+2)];
+ if (count > 25) {
+ *e++ = 'z';
+ count -= 26;
+ }
+ if (c != CELL_MIRROR_L && c != CELL_MIRROR_R) {
+ count++;
+ }
+ else if (c == CELL_MIRROR_L) {
+ if (count > 0) *e++ = (count-1 + 'a');
+ *e++ = 'L';
+ count = 0;
+ }
+ else {
+ if (count > 0) *e++ = (count-1 + 'a');
+ *e++ = 'R';
+ count = 0;
+ }
+ }
+ if (count > 0) *e++ = (count-1 + 'a');
+
+ /* Encode hints */
+ for (p=0;p<2*(new->common->params.w + new->common->params.h);p++) {
+ range2grid(p,new->common->params.w,new->common->params.h,&x,&y);
+ e += sprintf(e, ",%d", new->common->grid[x+y*(new->common->params.w+2)]);
+ }
+
+ *e++ = '\0';
+ desc = sresize(desc, e - desc, char);
+
+ sfree(old_guess);
+ free_game(new);
+
+ return desc;
+}
+
+void num2grid(int num, int width, int height, int *x, int *y) {
+ *x = 1+(num%width);
+ *y = 1+(num/width);
+ return;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc) {
+ int i;
+ int n;
+ int count;
+
+ game_state *state = new_state(params);
+
+ state->common->num_ghosts = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ desc++;
+ state->common->num_vampires = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ desc++;
+ state->common->num_zombies = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ desc++;
+
+ state->common->num_total = state->common->num_ghosts + state->common->num_vampires + state->common->num_zombies;
+
+ state->guess = snewn(state->common->num_total,int);
+ state->pencils = snewn(state->common->num_total,unsigned char);
+ state->common->fixed = snewn(state->common->num_total,int);
+ for (i=0;i<state->common->num_total;i++) {
+ state->guess[i] = 7;
+ state->pencils[i] = 0;
+ state->common->fixed[i] = FALSE;
+ }
+ for (i=0;i<state->common->wh;i++)
+ state->cell_errors[i] = FALSE;
+ for (i=0;i<2*state->common->num_paths;i++)
+ state->hint_errors[i] = FALSE;
+ for (i=0;i<3;i++)
+ state->count_errors[i] = FALSE;
+
+ count = 0;
+ n = 0;
+ while (*desc != ',') {
+ int c;
+ int x,y;
+
+ if (*desc == 'L') {
+ num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
+ state->common->grid[x+y*(state->common->params.w +2)] = CELL_MIRROR_L;
+ state->common->xinfo[x+y*(state->common->params.w+2)] = -1;
+ n++;
+ }
+ else if (*desc == 'R') {
+ num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
+ state->common->grid[x+y*(state->common->params.w +2)] = CELL_MIRROR_R;
+ state->common->xinfo[x+y*(state->common->params.w+2)] = -1;
+ n++;
+ }
+ else if (*desc == 'G') {
+ num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
+ state->common->grid[x+y*(state->common->params.w +2)] = CELL_GHOST;
+ state->common->xinfo[x+y*(state->common->params.w+2)] = count;
+ state->guess[count] = 1;
+ state->common->fixed[count++] = TRUE;
+ n++;
+ }
+ else if (*desc == 'V') {
+ num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
+ state->common->grid[x+y*(state->common->params.w +2)] = CELL_VAMPIRE;
+ state->common->xinfo[x+y*(state->common->params.w+2)] = count;
+ state->guess[count] = 2;
+ state->common->fixed[count++] = TRUE;
+ n++;
+ }
+ else if (*desc == 'Z') {
+ num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
+ state->common->grid[x+y*(state->common->params.w +2)] = CELL_ZOMBIE;
+ state->common->xinfo[x+y*(state->common->params.w+2)] = count;
+ state->guess[count] = 4;
+ state->common->fixed[count++] = TRUE;
+ n++;
+ }
+ else {
+ c = *desc - ('a' -1);
+ while (c-- > 0) {
+ num2grid(n,state->common->params.w,state->common->params.h,&x,&y);
+ state->common->grid[x+y*(state->common->params.w +2)] = CELL_EMPTY;
+ state->common->xinfo[x+y*(state->common->params.w+2)] = count;
+ state->guess[count] = 7;
+ state->common->fixed[count++] = FALSE;
+ n++;
+ }
+ }
+ desc++;
+ }
+ desc++;
+
+ for (i=0;i<2*(state->common->params.w + state->common->params.h);i++) {
+ int x,y;
+ int sights;
+
+ sights = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ desc++;
+
+
+ range2grid(i,state->common->params.w,state->common->params.h,&x,&y);
+ state->common->grid[x+y*(state->common->params.w +2)] = sights;
+ state->common->xinfo[x+y*(state->common->params.w +2)] = -2;
+ }
+
+ state->common->grid[0] = 0;
+ state->common->xinfo[0] = -2;
+ state->common->grid[state->common->params.w+1] = 0;
+ state->common->xinfo[state->common->params.w+1] = -2;
+ state->common->grid[state->common->params.w+1 + (state->common->params.h+1)*(state->common->params.w+2)] = 0;
+ state->common->xinfo[state->common->params.w+1 + (state->common->params.h+1)*(state->common->params.w+2)] = -2;
+ state->common->grid[(state->common->params.h+1)*(state->common->params.w+2)] = 0;
+ state->common->xinfo[(state->common->params.h+1)*(state->common->params.w+2)] = -2;
+
+ make_paths(state);
+ qsort(state->common->paths, state->common->num_paths, sizeof(struct path), path_cmp);
+
+ return state;
+}
+
+static char *validate_desc(game_params *params, char *desc) {
+ int i;
+ int w = params->w, h = params->h;
+ int wh = w*h;
+ int area;
+ int monsters;
+ int monster_count;
+ char *desc_s = desc;
+
+ for (i=0;i<3;i++) {
+ if (!*desc) return "Faulty game description";
+ while (*desc && isdigit((unsigned char)*desc)) { desc++; }
+ if (*desc != ',') return "Invalid character in number list";
+ desc++;
+ }
+ desc = desc_s;
+
+ area = monsters = monster_count = 0;
+ for (i=0;i<3;i++) {
+ monster_count += atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ desc++;
+ }
+ while (*desc && *desc != ',') {
+ if (*desc >= 'a' && *desc <= 'z') {
+ area += *desc - 'a' +1; monsters += *desc - 'a' +1;
+ } else if (*desc == 'G' || *desc == 'V' || *desc == 'Z') {
+ area++; monsters++;
+ } else if (*desc == 'L' || *desc == 'R') {
+ area++;
+ } else
+ return "Invalid character in grid specification";
+ desc++;
+ }
+ if (area < wh) return "Not enough data to fill grid";
+ else if (area > wh) return "Too much data to fill grid";
+ if (monsters != monster_count)
+ return "Monster numbers do not match grid spaces";
+
+ for (i = 0; i < 2*(w+h); i++) {
+ if (!*desc) return "Not enough numbers given after grid specification";
+ else if (*desc != ',') return "Invalid character in number list";
+ desc++;
+ while (*desc && isdigit((unsigned char)*desc)) { desc++; }
+ }
+
+ if (*desc) return "Unexpected additional data at end of game description";
+
+ return NULL;
+}
+
+static char *solve_game(game_state *state_start, game_state *currstate, char *aux, char **error) {
+ int p;
+ int *old_guess;
+ int iterative_depth;
+ int solved_iterative, solved_bruteforce, contains_inconsistency,
+ count_ambiguous;
+
+ int i;
+ char *move, *c;
+
+ game_state *solve_state = dup_game(currstate);
+
+ old_guess = snewn(solve_state->common->num_total,int);
+ for (p=0;p<solve_state->common->num_total;p++) {
+ if (solve_state->common->fixed[p]) {
+ old_guess[p] = solve_state->guess[p] = state_start->guess[p];
+ }
+ else {
+ old_guess[p] = solve_state->guess[p] = 7;
+ }
+ }
+ iterative_depth = 0;
+ solved_iterative = FALSE;
+ contains_inconsistency = FALSE;
+ count_ambiguous = 0;
+
+ /* Try to solve the puzzle with the iterative solver */
+ while (TRUE) {
+ int no_change;
+ no_change = TRUE;
+ solved_iterative =
+ solve_iterative(solve_state,solve_state->common->paths);
+ iterative_depth++;
+ for (p=0;p<solve_state->common->num_total;p++) {
+ if (solve_state->guess[p] != old_guess[p]) no_change = FALSE;
+ old_guess[p] = solve_state->guess[p];
+ if (solve_state->guess[p] == 0) contains_inconsistency = TRUE;
+ }
+ if (solved_iterative || no_change || contains_inconsistency) break;
+ }
+
+ if (contains_inconsistency) {
+ *error = "Puzzle is inconsistent";
+ sfree(old_guess);
+ free_game(solve_state);
+ return NULL;
+ }
+
+ /* If necessary, try to solve the puzzle with the brute-force solver */
+ solved_bruteforce = FALSE;
+ if (!solved_iterative) {
+ for (p=0;p<solve_state->common->num_total;p++)
+ if (solve_state->guess[p] != 1 && solve_state->guess[p] != 2 &&
+ solve_state->guess[p] != 4) count_ambiguous++;
+ solved_bruteforce =
+ solve_bruteforce(solve_state, solve_state->common->paths);
+ }
+
+ if (!solved_iterative && !solved_bruteforce) {
+ *error = "Puzzle is unsolvable";
+ sfree(old_guess);
+ free_game(solve_state);
+ return NULL;
+ }
+
+/* printf("Puzzle solved at level %s, iterations %d, ambiguous %d\n", (solved_bruteforce ? "TRICKY" : "NORMAL"), iterative_depth, count_ambiguous); */
+
+ move = snewn(solve_state->common->num_total * 4 +2, char);
+ c = move;
+ *c++='S';
+ for (i = 0; i < solve_state->common->num_total; i++) {
+ if (solve_state->guess[i] == 1) c += sprintf(c, ";G%d", i);
+ if (solve_state->guess[i] == 2) c += sprintf(c, ";V%d", i);
+ if (solve_state->guess[i] == 4) c += sprintf(c, ";Z%d", i);
+ }
+ *c++ = '\0';
+ move = sresize(move, c - move, char);
+
+ sfree(old_guess);
+ free_game(solve_state);
+ return move;
+}
+
+static int game_can_format_as_text_now(game_params *params) {
+ return TRUE;
+}
+
+static char *game_text_format(game_state *state) {
+ int w,h,c,r,xi,g;
+ char *ret;
+ char buf[120];
+
+ ret = snewn(50 + 6*(state->common->params.w +2) +
+ 6*(state->common->params.h+2) +
+ 3*(state->common->params.w * state->common->params.h), char);
+
+ sprintf(ret,"G: %d V: %d Z: %d\n\n",state->common->num_ghosts,
+ state->common->num_vampires, state->common->num_zombies);
+
+ for (h=0;h<state->common->params.h+2;h++) {
+ for (w=0;w<state->common->params.w+2;w++) {
+ c = state->common->grid[w+h*(state->common->params.w+2)];
+ xi = state->common->xinfo[w+h*(state->common->params.w+2)];
+ r = grid2range(w,h,state->common->params.w,state->common->params.h);
+ if (r != -1) {
+ sprintf(buf,"%2d", c); strcat(ret,buf);
+ } else if (c == CELL_MIRROR_L) {
+ sprintf(buf," \\"); strcat(ret,buf);
+ } else if (c == CELL_MIRROR_R) {
+ sprintf(buf," /"); strcat(ret,buf);
+ } else if (xi >= 0) {
+ g = state->guess[xi];
+ if (g == 1) { sprintf(buf," G"); strcat(ret,buf); }
+ else if (g == 2) { sprintf(buf," V"); strcat(ret,buf); }
+ else if (g == 4) { sprintf(buf," Z"); strcat(ret,buf); }
+ else { sprintf(buf," ."); strcat(ret,buf); }
+ } else {
+ sprintf(buf," "); strcat(ret,buf);
+ }
+ }
+ sprintf(buf,"\n"); strcat(ret,buf);
+ }
+
+ return ret;
+}
+
+struct game_ui {
+ int hx, hy; /* as for solo.c, highlight pos */
+ int hshow, hpencil, hcursor; /* show state, type, and ?cursor. */
+ int ascii;
+};
+
+static game_ui *new_ui(game_state *state) {
+ game_ui *ui = snew(game_ui);
+ ui->hx = ui->hy = 0;
+ ui->hpencil = ui->hshow = ui->hcursor = 0;
+ ui->ascii = FALSE;
+ return ui;
+}
+
+static void free_ui(game_ui *ui) {
+ sfree(ui);
+ return;
+}
+
+static char *encode_ui(game_ui *ui) {
+ return NULL;
+}
+
+static void decode_ui(game_ui *ui, char *encoding) {
+ return;
+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate, game_state *newstate) {
+ /* See solo.c; if we were pencil-mode highlighting and
+ * somehow a square has just been properly filled, cancel
+ * pencil mode. */
+ if (ui->hshow && ui->hpencil && !ui->hcursor) {
+ int g = newstate->guess[newstate->common->xinfo[ui->hx + ui->hy*(newstate->common->params.w+2)]];
+ if (g == 1 || g == 2 || g == 4)
+ ui->hshow = 0;
+ }
+}
+
+struct game_drawstate {
+ int tilesize, started, solved;
+ int w, h;
+
+ int *monsters;
+ unsigned char *pencils;
+
+ unsigned char count_errors[3];
+ unsigned char *cell_errors;
+ unsigned char *hint_errors;
+
+ int hx, hy, hshow, hpencil; /* as for game_ui. */
+ int hflash;
+ int ascii;
+};
+
+#define TILESIZE (ds->tilesize)
+#define BORDER (TILESIZE/2)
+
+static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button) {
+ int gx,gy;
+ int g,xi;
+ char buf[80];
+
+ gx = ((x-BORDER-1) / TILESIZE );
+ gy = ((y-BORDER-2) / TILESIZE ) - 1;
+
+ if (button == 'a' || button == 'A') {
+ ds->ascii = ui->ascii ? FALSE : TRUE;
+ return "";
+ }
+
+ if (ui->hshow == 1 && ui->hpencil == 0) {
+ xi = state->common->xinfo[ui->hx + ui->hy*(state->common->params.w+2)];
+ if (xi >= 0 && !state->common->fixed[xi]) {
+ if (button == 'g' || button == 'G' || button == '1') {
+ if (!ui->hcursor) ui->hshow = 0;
+ sprintf(buf,"G%d",xi);
+ return dupstr(buf);
+ }
+ if (button == 'v' || button == 'V' || button == '2') {
+ if (!ui->hcursor) ui->hshow = 0;
+ sprintf(buf,"V%d",xi);
+ return dupstr(buf);
+ }
+ if (button == 'z' || button == 'Z' || button == '3') {
+ if (!ui->hcursor) ui->hshow = 0;
+ sprintf(buf,"Z%d",xi);
+ return dupstr(buf);
+ }
+ if (button == 'e' || button == 'E' || button == CURSOR_SELECT2 ||
+ button == '0' || button == '\b' ) {
+ if (!ui->hcursor) ui->hshow = 0;
+ sprintf(buf,"E%d",xi);
+ return dupstr(buf);
+ }
+ }
+ }
+
+ if (IS_CURSOR_MOVE(button)) {
+ if (ui->hx == 0 && ui->hy == 0) {
+ ui->hx = 1;
+ ui->hy = 1;
+ }
+ else switch (button) {
+ case CURSOR_UP: ui->hy -= (ui->hy > 1) ? 1 : 0; break;
+ case CURSOR_DOWN: ui->hy += (ui->hy < ds->h) ? 1 : 0; break;
+ case CURSOR_RIGHT: ui->hx += (ui->hx < ds->w) ? 1 : 0; break;
+ case CURSOR_LEFT: ui->hx -= (ui->hx > 1) ? 1 : 0; break;
+ }
+ ui->hshow = ui->hcursor = 1;
+ return "";
+ }
+ if (ui->hshow && button == CURSOR_SELECT) {
+ ui->hpencil = 1 - ui->hpencil;
+ ui->hcursor = 1;
+ return "";
+ }
+
+ if (ui->hshow == 1 && ui->hpencil == 1) {
+ xi = state->common->xinfo[ui->hx + ui->hy*(state->common->params.w+2)];
+ if (xi >= 0 && !state->common->fixed[xi]) {
+ if (button == 'g' || button == 'G' || button == '1') {
+ sprintf(buf,"g%d",xi);
+ ui->hpencil = ui->hshow = 0;
+ return dupstr(buf);
+ }
+ if (button == 'v' || button == 'V' || button == '2') {
+ sprintf(buf,"v%d",xi);
+ ui->hpencil = ui->hshow = 0;
+ return dupstr(buf);
+ }
+ if (button == 'z' || button == 'Z' || button == '3') {
+ sprintf(buf,"z%d",xi);
+ ui->hpencil = ui->hshow = 0;
+ return dupstr(buf);
+ }
+ if (button == 'e' || button == 'E' || button == CURSOR_SELECT2 ||
+ button == '0' || button == '\b') {
+ if (!ui->hcursor) ui->hshow = 0;
+ sprintf(buf,"E%d",xi);
+ ui->hpencil = ui->hshow = 0;
+ return dupstr(buf);
+ }
+ }
+ }
+
+ if (gx > 0 && gx < ds->w+1 && gy > 0 && gy < ds->h+1) {
+ xi = state->common->xinfo[gx+gy*(state->common->params.w+2)];
+ if (xi >= 0 && !state->common->fixed[xi]) {
+ g = state->guess[xi];
+ if (ui->hshow == 0) {
+ if (button == LEFT_BUTTON) {
+ ui->hshow = 1; ui->hpencil = 0; ui->hcursor = 0;
+ ui->hx = gx; ui->hy = gy;
+ return "";
+ }
+ else if (button == RIGHT_BUTTON && g == 7) {
+ ui->hshow = 1; ui->hpencil = 1; ui->hcursor = 0;
+ ui->hx = gx; ui->hy = gy;
+ return "";
+ }
+ }
+ else if (ui->hshow == 1) {
+ if (button == LEFT_BUTTON) {
+ if (ui->hpencil == 0) {
+ if (gx == ui->hx && gy == ui->hy) {
+ ui->hshow = 0; ui->hpencil = 0; ui->hcursor = 0;
+ ui->hx = 0; ui->hy = 0;
+ return "";
+ }
+ else {
+ ui->hshow = 1; ui->hpencil = 0; ui->hcursor = 0;
+ ui->hx = gx; ui->hy = gy;
+ return "";
+ }
+ }
+ else {
+ ui->hshow = 1; ui->hpencil = 0; ui->hcursor = 0;
+ ui->hx = gx; ui->hy = gy;
+ return "";
+ }
+ }
+ else if (button == RIGHT_BUTTON) {
+ if (ui->hpencil == 0 && g == 7) {
+ ui->hshow = 1; ui->hpencil = 1; ui->hcursor = 0;
+ ui->hx = gx; ui->hy = gy;
+ return "";
+ }
+ else {
+ if (gx == ui->hx && gy == ui->hy) {
+ ui->hshow = 0; ui->hpencil = 0; ui->hcursor = 0;
+ ui->hx = 0; ui->hy = 0;
+ return "";
+ }
+ else if (g == 7) {
+ ui->hshow = 1; ui->hpencil = 1; ui->hcursor = 0;
+ ui->hx = gx; ui->hy = gy;
+ return "";
+ }
+ }
+ }
+ }
+ }
+ }
+
+ return NULL;
+}
+
+int check_numbers_draw(game_state *state, int *guess) {
+ int valid, filled;
+ int i,x,y,xy;
+ int count_ghosts, count_vampires, count_zombies;
+
+ count_ghosts = count_vampires = count_zombies = 0;
+ for (i=0;i<state->common->num_total;i++) {
+ if (guess[i] == 1) count_ghosts++;
+ if (guess[i] == 2) count_vampires++;
+ if (guess[i] == 4) count_zombies++;
+ }
+
+ valid = TRUE;
+ filled = (count_ghosts + count_vampires + count_zombies >=
+ state->common->num_total);
+
+ if (count_ghosts > state->common->num_ghosts ||
+ (filled && count_ghosts != state->common->num_ghosts) ) {
+ valid = FALSE;
+ state->count_errors[0] = TRUE;
+ for (x=1;x<state->common->params.w+1;x++)
+ for (y=1;y<state->common->params.h+1;y++) {
+ xy = x+y*(state->common->params.w+2);
+ if (state->common->xinfo[xy] >= 0 &&
+ guess[state->common->xinfo[xy]] == 1)
+ state->cell_errors[xy] = TRUE;
+ }
+ }
+ if (count_vampires > state->common->num_vampires ||
+ (filled && count_vampires != state->common->num_vampires) ) {
+ valid = FALSE;
+ state->count_errors[1] = TRUE;
+ for (x=1;x<state->common->params.w+1;x++)
+ for (y=1;y<state->common->params.h+1;y++) {
+ xy = x+y*(state->common->params.w+2);
+ if (state->common->xinfo[xy] >= 0 &&
+ guess[state->common->xinfo[xy]] == 2)
+ state->cell_errors[xy] = TRUE;
+ }
+ }
+ if (count_zombies > state->common->num_zombies ||
+ (filled && count_zombies != state->common->num_zombies) ) {
+ valid = FALSE;
+ state->count_errors[2] = TRUE;
+ for (x=1;x<state->common->params.w+1;x++)
+ for (y=1;y<state->common->params.h+1;y++) {
+ xy = x+y*(state->common->params.w+2);
+ if (state->common->xinfo[xy] >= 0 &&
+ guess[state->common->xinfo[xy]] == 4)
+ state->cell_errors[xy] = TRUE;
+ }
+ }
+
+ return valid;
+}
+
+int check_path_solution(game_state *state, int p) {
+ int i;
+ int mirror;
+ int count;
+ int correct;
+ int unfilled;
+
+ count = 0;
+ mirror = FALSE;
+ correct = TRUE;
+
+ unfilled = 0;
+ for (i=0;i<state->common->paths[p].length;i++) {
+ if (state->common->paths[p].p[i] == -1) mirror = TRUE;
+ else {
+ if (state->guess[state->common->paths[p].p[i]] == 1 && mirror)
+ count++;
+ else if (state->guess[state->common->paths[p].p[i]] == 2 && !mirror)
+ count++;
+ else if (state->guess[state->common->paths[p].p[i]] == 4)
+ count++;
+ else if (state->guess[state->common->paths[p].p[i]] == 7)
+ unfilled++;
+ }
+ }
+
+ if (unfilled == 0 && count != state->common->paths[p].sightings_start) {
+ correct = FALSE;
+ state->hint_errors[state->common->paths[p].grid_start] = TRUE;
+ }
+
+ count = 0;
+ mirror = FALSE;
+ unfilled = 0;
+ for (i=state->common->paths[p].length-1;i>=0;i--) {
+ if (state->common->paths[p].p[i] == -1) mirror = TRUE;
+ else {
+ if (state->guess[state->common->paths[p].p[i]] == 1 && mirror)
+ count++;
+ else if (state->guess[state->common->paths[p].p[i]] == 2 && !mirror)
+ count++;
+ else if (state->guess[state->common->paths[p].p[i]] == 4)
+ count++;
+ else if (state->guess[state->common->paths[p].p[i]] == 7)
+ unfilled++;
+ }
+ }
+
+ if (unfilled == 0 && count != state->common->paths[p].sightings_end) {
+ correct = FALSE;
+ state->hint_errors[state->common->paths[p].grid_end] = TRUE;
+ }
+
+ if (!correct) {
+ for (i=0;i<state->common->paths[p].length;i++)
+ state->cell_errors[state->common->paths[p].xy[i]] = TRUE;
+ }
+
+ return correct;
+}
+
+static game_state *execute_move(game_state *state, char *move) {
+ int x,n,p,i;
+ char c;
+ int correct;
+ int solver;
+
+ game_state *ret = dup_game(state);
+ solver = FALSE;
+
+ while (*move) {
+ c = *move;
+ if (c == 'S') {
+ move++;
+ solver = TRUE;
+ }
+ if (c == 'G' || c == 'V' || c == 'Z' || c == 'E' ||
+ c == 'g' || c == 'v' || c == 'z') {
+ move++;
+ sscanf(move, "%d%n", &x, &n);
+ if (c == 'G') ret->guess[x] = 1;
+ if (c == 'V') ret->guess[x] = 2;
+ if (c == 'Z') ret->guess[x] = 4;
+ if (c == 'E') { ret->guess[x] = 7; ret->pencils[x] = 0; }
+ if (c == 'g') ret->pencils[x] ^= 1;
+ if (c == 'v') ret->pencils[x] ^= 2;
+ if (c == 'z') ret->pencils[x] ^= 4;
+ move += n;
+ }
+ if (*move == ';') move++;
+ }
+
+ correct = TRUE;
+
+ for (i=0;i<ret->common->wh;i++) ret->cell_errors[i] = FALSE;
+ for (i=0;i<2*ret->common->num_paths;i++) ret->hint_errors[i] = FALSE;
+ for (i=0;i<3;i++) ret->count_errors[i] = FALSE;
+
+ if (!check_numbers_draw(ret,ret->guess)) correct = FALSE;
+
+ for (p=0;p<state->common->num_paths;p++)
+ if (!check_path_solution(ret,p)) correct = FALSE;
+
+ for (i=0;i<state->common->num_total;i++)
+ if (!(ret->guess[i] == 1 || ret->guess[i] == 2 ||
+ ret->guess[i] == 4)) correct = FALSE;
+
+ if (correct && !solver) ret->solved = TRUE;
+ if (solver) ret->cheated = TRUE;
+
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+#define PREFERRED_TILE_SIZE 64
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y) {
+ *x = tilesize + (2 + params->w) * tilesize;
+ *y = tilesize + (3 + params->h) * tilesize;
+ return;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize) {
+ ds->tilesize = tilesize;
+ return;
+}
+
+#define COLOUR(ret, i, r, g, b) ((ret[3*(i)+0] = (r)), (ret[3*(i)+1] = (g)), (ret[3*(i)+2] = (b)))
+
+static float *game_colours(frontend *fe, int *ncolours) {
+ float *ret = snewn(3 * NCOLOURS, float);
+
+ frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+
+ ret[COL_GRID * 3 + 0] = 0.0F;
+ ret[COL_GRID * 3 + 1] = 0.0F;
+ ret[COL_GRID * 3 + 2] = 0.0F;
+
+ ret[COL_TEXT * 3 + 0] = 0.0F;
+ ret[COL_TEXT * 3 + 1] = 0.0F;
+ ret[COL_TEXT * 3 + 2] = 0.0F;
+
+ ret[COL_ERROR * 3 + 0] = 1.0F;
+ ret[COL_ERROR * 3 + 1] = 0.0F;
+ ret[COL_ERROR * 3 + 2] = 0.0F;
+
+ ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2];
+
+ ret[COL_FLASH * 3 + 0] = 1.0F;
+ ret[COL_FLASH * 3 + 1] = 1.0F;
+ ret[COL_FLASH * 3 + 2] = 1.0F;
+
+ ret[COL_GHOST * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
+ ret[COL_GHOST * 3 + 1] = ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_GHOST * 3 + 2] = ret[COL_BACKGROUND * 3 + 0];
+
+ ret[COL_ZOMBIE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
+ ret[COL_ZOMBIE * 3 + 1] = ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_ZOMBIE * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.5F;
+
+ ret[COL_VAMPIRE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_VAMPIRE * 3 + 1] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
+ ret[COL_VAMPIRE * 3 + 2] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) {
+ int i;
+ struct game_drawstate *ds = snew(struct game_drawstate);
+
+ ds->tilesize = 0;
+ ds->started = ds->solved = FALSE;
+ ds->w = state->common->params.w;
+ ds->h = state->common->params.h;
+ ds->ascii = FALSE;
+
+ ds->count_errors[0] = FALSE;
+ ds->count_errors[1] = FALSE;
+ ds->count_errors[2] = FALSE;
+
+ ds->monsters = snewn(state->common->num_total,int);
+ for (i=0;i<(state->common->num_total);i++)
+ ds->monsters[i] = 7;
+ ds->pencils = snewn(state->common->num_total,unsigned char);
+ for (i=0;i<state->common->num_total;i++)
+ ds->pencils[i] = 0;
+
+ ds->cell_errors = snewn(state->common->wh,unsigned char);
+ for (i=0;i<state->common->wh;i++)
+ ds->cell_errors[i] = FALSE;
+ ds->hint_errors = snewn(2*state->common->num_paths,unsigned char);
+ for (i=0;i<2*state->common->num_paths;i++)
+ ds->hint_errors[i] = FALSE;
+
+ ds->hshow = ds->hpencil = ds->hflash = 0;
+ ds->hx = ds->hy = 0;
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds) {
+ sfree(ds->hint_errors);
+ sfree(ds->cell_errors);
+ sfree(ds->pencils);
+ sfree(ds->monsters);
+ sfree(ds);
+ return;
+}
+
+static void draw_cell_background(drawing *dr, game_drawstate *ds,
+ game_state *state, game_ui *ui, int x, int y) {
+
+ int hon;
+ int dx,dy;
+ dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
+ dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
+
+ hon = (ui->hshow && x == ui->hx && y == ui->hy);
+ draw_rect(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1,(hon && !ui->hpencil) ? COL_HIGHLIGHT : COL_BACKGROUND);
+
+ if (hon && ui->hpencil) {
+ int coords[6];
+ coords[0] = dx-(TILESIZE/2)+1;
+ coords[1] = dy-(TILESIZE/2)+1;
+ coords[2] = coords[0] + TILESIZE/2;
+ coords[3] = coords[1];
+ coords[4] = coords[0];
+ coords[5] = coords[1] + TILESIZE/2;
+ draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
+ }
+
+ draw_update(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1);
+
+ return;
+}
+
+static void draw_circle_or_point(drawing *dr, int cx, int cy, int radius,
+ int colour)
+{
+ if (radius > 0)
+ draw_circle(dr, cx, cy, radius, colour, colour);
+ else
+ draw_rect(dr, cx, cy, 1, 1, colour);
+}
+
+static void draw_monster(drawing *dr, game_drawstate *ds, int x, int y,
+ int tilesize, int hflash, int monster)
+{
+ int black = (hflash ? COL_FLASH : COL_TEXT);
+
+ if (monster == 1) { /* ghost */
+ int poly[80], i, j;
+
+ clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize/2+1);
+ draw_circle(dr,x,y,2*tilesize/5, COL_GHOST,black);
+ unclip(dr);
+
+ i = 0;
+ poly[i++] = x - 2*tilesize/5;
+ poly[i++] = y-2;
+ poly[i++] = x - 2*tilesize/5;
+ poly[i++] = y + 2*tilesize/5;
+
+ for (j = 0; j < 3; j++) {
+ int total = (2*tilesize/5) * 2;
+ int before = total * j / 3;
+ int after = total * (j+1) / 3;
+ int mid = (before + after) / 2;
+ poly[i++] = x - 2*tilesize/5 + mid;
+ poly[i++] = y + 2*tilesize/5 - (total / 6);
+ poly[i++] = x - 2*tilesize/5 + after;
+ poly[i++] = y + 2*tilesize/5;
+ }
+
+ poly[i++] = x + 2*tilesize/5;
+ poly[i++] = y-2;
+
+ clip(dr,x-(tilesize/2)+2,y,tilesize-3,tilesize-(tilesize/2)-1);
+ draw_polygon(dr, poly, i/2, COL_GHOST, black);
+ unclip(dr);
+
+ draw_circle(dr,x-tilesize/6,y-tilesize/12,tilesize/10,
+ COL_BACKGROUND,black);
+ draw_circle(dr,x+tilesize/6,y-tilesize/12,tilesize/10,
+ COL_BACKGROUND,black);
+
+ draw_circle_or_point(dr,x-tilesize/6+1+tilesize/48,y-tilesize/12,
+ tilesize/48,black);
+ draw_circle_or_point(dr,x+tilesize/6+1+tilesize/48,y-tilesize/12,
+ tilesize/48,black);
+
+ } else if (monster == 2) { /* vampire */
+ int poly[80], i;
+
+ clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize/2);
+ draw_circle(dr,x,y,2*tilesize/5,black,black);
+ unclip(dr);
+
+ clip(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize/2+1,tilesize/2);
+ draw_circle(dr,x-tilesize/7,y,2*tilesize/5-tilesize/7,
+ COL_VAMPIRE,black);
+ unclip(dr);
+ clip(dr,x,y-(tilesize/2)+2,tilesize/2+1,tilesize/2);
+ draw_circle(dr,x+tilesize/7,y,2*tilesize/5-tilesize/7,
+ COL_VAMPIRE,black);
+ unclip(dr);
+
+ clip(dr,x-(tilesize/2)+2,y,tilesize-3,tilesize/2);
+ draw_circle(dr,x,y,2*tilesize/5, COL_VAMPIRE,black);
+ unclip(dr);
+
+ draw_circle(dr, x-tilesize/7, y-tilesize/16, tilesize/16,
+ COL_BACKGROUND, black);
+ draw_circle(dr, x+tilesize/7, y-tilesize/16, tilesize/16,
+ COL_BACKGROUND, black);
+ draw_circle_or_point(dr, x-tilesize/7, y-tilesize/16, tilesize/48,
+ black);
+ draw_circle_or_point(dr, x+tilesize/7, y-tilesize/16, tilesize/48,
+ black);
+
+ clip(dr, x-(tilesize/2)+2, y+tilesize/8, tilesize-3, tilesize/4);
+
+ i = 0;
+ poly[i++] = x-3*tilesize/16;
+ poly[i++] = y+1*tilesize/8;
+ poly[i++] = x-2*tilesize/16;
+ poly[i++] = y+7*tilesize/24;
+ poly[i++] = x-1*tilesize/16;
+ poly[i++] = y+1*tilesize/8;
+ draw_polygon(dr, poly, i/2, COL_BACKGROUND, black);
+ i = 0;
+ poly[i++] = x+3*tilesize/16;
+ poly[i++] = y+1*tilesize/8;
+ poly[i++] = x+2*tilesize/16;
+ poly[i++] = y+7*tilesize/24;
+ poly[i++] = x+1*tilesize/16;
+ poly[i++] = y+1*tilesize/8;
+ draw_polygon(dr, poly, i/2, COL_BACKGROUND, black);
+
+ draw_circle(dr, x, y-tilesize/5, 2*tilesize/5, COL_VAMPIRE, black);
+ unclip(dr);
+
+ } else if (monster == 4) { /* zombie */
+ draw_circle(dr,x,y,2*tilesize/5, COL_ZOMBIE,black);
+
+ draw_line(dr,
+ x-tilesize/7-tilesize/16, y-tilesize/12-tilesize/16,
+ x-tilesize/7+tilesize/16, y-tilesize/12+tilesize/16,
+ black);
+ draw_line(dr,
+ x-tilesize/7+tilesize/16, y-tilesize/12-tilesize/16,
+ x-tilesize/7-tilesize/16, y-tilesize/12+tilesize/16,
+ black);
+ draw_line(dr,
+ x+tilesize/7-tilesize/16, y-tilesize/12-tilesize/16,
+ x+tilesize/7+tilesize/16, y-tilesize/12+tilesize/16,
+ black);
+ draw_line(dr,
+ x+tilesize/7+tilesize/16, y-tilesize/12-tilesize/16,
+ x+tilesize/7-tilesize/16, y-tilesize/12+tilesize/16,
+ black);
+
+ clip(dr, x-tilesize/5, y+tilesize/6, 2*tilesize/5+1, tilesize/2);
+ draw_circle(dr, x-tilesize/15, y+tilesize/6, tilesize/12,
+ COL_BACKGROUND, black);
+ unclip(dr);
+
+ draw_line(dr, x-tilesize/5, y+tilesize/6, x+tilesize/5, y+tilesize/6,
+ black);
+ }
+
+ draw_update(dr,x-(tilesize/2)+2,y-(tilesize/2)+2,tilesize-3,tilesize-3);
+}
+
+static void draw_monster_count(drawing *dr, game_drawstate *ds,
+ game_state *state, int c, int hflash) {
+ int dx,dy,dh;
+ char buf[8];
+ char bufm[8];
+
+ dy = TILESIZE/2;
+ dh = TILESIZE;
+ dx = BORDER+(ds->w+2)*TILESIZE/2+TILESIZE/4;
+ switch (c) {
+ case 0:
+ sprintf(buf,"%d",state->common->num_ghosts);
+ sprintf(bufm,"G");
+ dx -= 3*TILESIZE/2;
+ break;
+ case 1:
+ sprintf(buf,"%d",state->common->num_vampires);
+ sprintf(bufm,"V");
+ break;
+ case 2:
+ sprintf(buf,"%d",state->common->num_zombies);
+ sprintf(bufm,"Z");
+ dx += 3*TILESIZE/2;
+ break;
+ }
+
+ if (!ds->ascii) {
+ draw_rect(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh,COL_BACKGROUND);
+ draw_monster(dr,ds,dx-TILESIZE/3,dh,2*TILESIZE/3,hflash,1<<c);
+ draw_text(dr,dx,dh,FONT_VARIABLE,dy-1,ALIGN_HLEFT|ALIGN_VCENTRE,
+ (state->count_errors[c] ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT), buf);
+ draw_update(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh);
+ }
+ else {
+ draw_rect(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh,COL_BACKGROUND);
+ draw_text(dr,dx-TILESIZE/3,dh,FONT_VARIABLE,dy-1,
+ ALIGN_HCENTRE|ALIGN_VCENTRE,
+ hflash ? COL_FLASH : COL_TEXT, bufm);
+ draw_text(dr,dx,dh,FONT_VARIABLE,dy-1,ALIGN_HLEFT|ALIGN_VCENTRE,
+ (state->count_errors[c] ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT), buf);
+ draw_update(dr,dx-2*TILESIZE/3,dy,3*TILESIZE/2,dh);
+ }
+
+ return;
+}
+
+static void draw_path_hint(drawing *dr, game_drawstate *ds, game_state *state,
+ int i, int hflash, int start) {
+ int dx,dy,x,y;
+ int p,error;
+ char buf[80];
+
+ p = start ? state->common->paths[i].grid_start : state->common->paths[i].grid_end;
+ range2grid(p,state->common->params.w,state->common->params.h,&x,&y);
+ error = ds->hint_errors[p];
+
+ dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
+ dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
+ sprintf(buf,"%d", start ? state->common->paths[i].sightings_start : state->common->paths[i].sightings_end);
+ draw_rect(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,TILESIZE-3,COL_BACKGROUND);
+ draw_text(dr,dx,dy,FONT_FIXED,TILESIZE/2,ALIGN_HCENTRE|ALIGN_VCENTRE, error ? COL_ERROR : hflash ? COL_FLASH : COL_TEXT,buf);
+ draw_update(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,TILESIZE-3);
+
+ return;
+}
+
+static void draw_mirror(drawing *dr, game_drawstate *ds, game_state *state,
+ int x, int y, int hflash, int mirror) {
+ int dx,dy,mx1,my1,mx2,my2;
+ dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
+ dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
+
+ if (mirror == CELL_MIRROR_L) {
+ mx1 = dx-(TILESIZE/4);
+ my1 = dy-(TILESIZE/4);
+ mx2 = dx+(TILESIZE/4);
+ my2 = dy+(TILESIZE/4);
+ }
+ else {
+ mx1 = dx-(TILESIZE/4);
+ my1 = dy+(TILESIZE/4);
+ mx2 = dx+(TILESIZE/4);
+ my2 = dy-(TILESIZE/4);
+ }
+ draw_thick_line(dr,(float)(TILESIZE/16),mx1,my1,mx2,my2,
+ hflash ? COL_FLASH : COL_TEXT);
+ draw_update(dr,dx-(TILESIZE/2)+1,dy-(TILESIZE/2)+1,TILESIZE-1,TILESIZE-1);
+
+ return;
+}
+
+static void draw_big_monster(drawing *dr, game_drawstate *ds, game_state *state,
+ int x, int y, int hflash, int monster)
+{
+ int dx,dy;
+ char buf[10];
+ dx = BORDER+(x* ds->tilesize)+(TILESIZE/2);
+ dy = BORDER+(y* ds->tilesize)+(TILESIZE/2)+TILESIZE;
+ if (ds->ascii) {
+ if (monster == 1) sprintf(buf,"G");
+ else if (monster == 2) sprintf(buf,"V");
+ else if (monster == 4) sprintf(buf,"Z");
+ else sprintf(buf," ");
+ draw_text(dr,dx,dy,FONT_FIXED,TILESIZE/2,ALIGN_HCENTRE|ALIGN_VCENTRE,
+ hflash ? COL_FLASH : COL_TEXT,buf);
+ draw_update(dr,dx-(TILESIZE/2)+2,dy-(TILESIZE/2)+2,TILESIZE-3,
+ TILESIZE-3);
+ }
+ else {
+ draw_monster(dr, ds, dx, dy, 3*TILESIZE/4, hflash, monster);
+ }
+ return;
+}
+
+static void draw_pencils(drawing *dr, game_drawstate *ds, game_state *state,
+ int x, int y, int pencil) {
+ int dx, dy;
+ int monsters[4];
+ int i, j, px, py;
+ char buf[10];
+ dx = BORDER+(x* ds->tilesize)+(TILESIZE/4);
+ dy = BORDER+(y* ds->tilesize)+(TILESIZE/4)+TILESIZE;
+
+ for (i = 0, j = 1; j < 8; j *= 2)
+ if (pencil & j)
+ monsters[i++] = j;
+ while (i < 4)
+ monsters[i++] = 0;
+
+ for (py = 0; py < 2; py++)
+ for (px = 0; px < 2; px++)
+ if (monsters[py*2+px]) {
+ if (!ds->ascii) {
+ draw_monster(dr, ds,
+ dx + TILESIZE/2 * px, dy + TILESIZE/2 * py,
+ TILESIZE/2, 0, monsters[py*2+px]);
+ }
+ else {
+ switch (monsters[py*2+px]) {
+ case 1: sprintf(buf,"G"); break;
+ case 2: sprintf(buf,"V"); break;
+ case 4: sprintf(buf,"Z"); break;
+ }
+ draw_text(dr,dx + TILESIZE/2 * px,dy + TILESIZE/2 * py,
+ FONT_FIXED,TILESIZE/4,ALIGN_HCENTRE|ALIGN_VCENTRE,
+ COL_TEXT,buf);
+ }
+ }
+ draw_update(dr,dx-(TILESIZE/4)+2,dy-(TILESIZE/4)+2,
+ (TILESIZE/2)-3,(TILESIZE/2)-3);
+
+ return;
+}
+
+#define FLASH_TIME 0.7F
+
+static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
+ game_state *state, int dir, game_ui *ui,
+ float animtime, float flashtime) {
+ int i,j,x,y,xy;
+ int stale, xi, c, hflash, hchanged;
+
+ hflash = (int)(flashtime * 5 / FLASH_TIME) % 2;
+
+ /* Draw static grid components at startup */
+ if (!ds->started) {
+ draw_rect(dr, 0, 0, 2*BORDER+(ds->w+2)*TILESIZE,
+ 2*BORDER+(ds->h+3)*TILESIZE, COL_BACKGROUND);
+ draw_rect(dr, BORDER+TILESIZE-1, BORDER+2*TILESIZE-1,
+ (ds->w)*TILESIZE +3, (ds->h)*TILESIZE +3, COL_GRID);
+ for (i=0;i<ds->w;i++)
+ for (j=0;j<ds->h;j++)
+ draw_rect(dr, BORDER+(ds->tilesize*(i+1))+1,
+ BORDER+(ds->tilesize*(j+2))+1, ds->tilesize-1,
+ ds->tilesize-1, COL_BACKGROUND);
+ draw_update(dr,BORDER+TILESIZE-1,BORDER+2*TILESIZE-1,
+ (ds->w)*TILESIZE+3, (ds->h)*TILESIZE+3);
+ }
+
+ hchanged = FALSE;
+ if (ds->hx != ui->hx || ds->hy != ui->hy ||
+ ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
+ hchanged = TRUE;
+
+ /* Draw monster count hints */
+
+ for (i=0;i<3;i++) {
+ stale = FALSE;
+ if (!ds->started) stale = TRUE;
+ if (ds->hflash != hflash) stale = TRUE;
+ if (ds->ascii != ui->ascii) stale = TRUE;
+ if (ds->count_errors[i] != state->count_errors[i]) {
+ stale = TRUE;
+ ds->count_errors[i] = state->count_errors[i];
+ }
+
+ if (stale) {
+ draw_monster_count(dr, ds, state, i, hflash);
+ }
+ }
+
+ /* Draw path count hints */
+ for (i=0;i<state->common->num_paths;i++) {
+ int p;
+ stale = FALSE;
+
+ if (!ds->started) stale = TRUE;
+ if (ds->hflash != hflash) stale = TRUE;
+
+ p = state->common->paths[i].grid_start;
+ if (ds->hint_errors[p] != state->hint_errors[p]) {
+ stale = TRUE;
+ ds->hint_errors[p] = state->hint_errors[p];
+ }
+
+ if (stale) {
+ draw_path_hint(dr, ds, state, i, hflash, TRUE);
+ }
+
+ stale = FALSE;
+
+ if (!ds->started) stale = TRUE;
+ if (ds->hflash != hflash) stale = TRUE;
+
+ p = state->common->paths[i].grid_end;
+ if (ds->hint_errors[p] != state->hint_errors[p]) {
+ stale = TRUE;
+ ds->hint_errors[p] = state->hint_errors[p];
+ }
+
+ if (stale) {
+ draw_path_hint(dr, ds, state, i, hflash, FALSE);
+ }
+
+ }
+
+ /* Draw puzzle grid contents */
+ for (x = 1; x < ds->w+1; x++)
+ for (y = 1; y < ds->h+1; y++) {
+ stale = FALSE;
+ xy = x+y*(state->common->params.w+2);
+ xi = state->common->xinfo[xy];
+ c = state->common->grid[xy];
+
+ if (!ds->started) stale = TRUE;
+ if (ds->hflash != hflash) stale = TRUE;
+ if (ds->ascii != ui->ascii) stale = TRUE;
+
+ if (hchanged) {
+ if ((x == ui->hx && y == ui->hy) ||
+ (x == ds->hx && y == ds->hy))
+ stale = TRUE;
+ }
+
+ if (xi >= 0 && (state->guess[xi] != ds->monsters[xi]) ) {
+ stale = TRUE;
+ ds->monsters[xi] = state->guess[xi];
+ }
+
+ if (xi >= 0 && (state->pencils[xi] != ds->pencils[xi]) ) {
+ stale = TRUE;
+ ds->pencils[xi] = state->pencils[xi];
+ }
+
+ if (state->cell_errors[xy] != ds->cell_errors[xy]) {
+ stale = TRUE;
+ ds->cell_errors[xy] = state->cell_errors[xy];
+ }
+
+ if (stale) {
+ draw_cell_background(dr, ds, state, ui, x, y);
+ if (xi < 0)
+ draw_mirror(dr, ds, state, x, y, hflash, c);
+ else if (state->guess[xi] == 1 || state->guess[xi] == 2 ||
+ state->guess[xi] == 4)
+ draw_big_monster(dr, ds, state, x, y, hflash, state->guess[xi]);
+ else
+ draw_pencils(dr, ds, state, x, y, state->pencils[xi]);
+ }
+ }
+
+ ds->hx = ui->hx; ds->hy = ui->hy;
+ ds->hshow = ui->hshow;
+ ds->hpencil = ui->hpencil;
+ ds->hflash = hflash;
+ ui->ascii = ds->ascii;
+ ds->started = TRUE;
+ return;
+}
+
+static float game_anim_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui) {
+ return 0.0F;
+}
+
+static float game_flash_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui) {
+ return (!oldstate->solved && newstate->solved && !oldstate->cheated &&
+ !newstate->cheated) ? FLASH_TIME : 0.0F;
+}
+
+static int game_status(game_state *state) {
+ return state->solved;
+}
+
+static int game_timing_state(game_state *state, game_ui *ui) {
+ return TRUE;
+}
+
+static void game_print_size(game_params *params, float *x, float *y) {
+}
+
+static void game_print(drawing *dr, game_state *state, int tilesize) {
+}
+
+#ifdef COMBINED
+#define thegame undead
+#endif
+
+const struct game thegame = {
+ "Undead", "games.undead", "undead",
+ default_params,
+ game_fetch_preset,
+ decode_params,
+ encode_params,
+ free_params,
+ dup_params,
+ TRUE, game_configure, custom_params,
+ validate_params,
+ new_game_desc,
+ validate_desc,
+ new_game,
+ dup_game,
+ free_game,
+ TRUE, solve_game,
+ TRUE, game_can_format_as_text_now, game_text_format,
+ new_ui,
+ free_ui,
+ encode_ui,
+ decode_ui,
+ game_changed_state,
+ interpret_move,
+ execute_move,
+ PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
+ game_colours,
+ game_new_drawstate,
+ game_free_drawstate,
+ game_redraw,
+ game_anim_length,
+ game_flash_length,
+ game_status,
+ FALSE, FALSE, game_print_size, game_print,
+ FALSE, /* wants_statusbar */
+ FALSE, game_timing_state,
+ 0, /* flags */
+};
+
~mdw / sgt / puzzles / commitdiff