From 301cd8c48591098aedcaa7abaa61e586ab4cdb8c Mon Sep 17 00:00:00 2001 From: simon Date: Sat, 8 Sep 2012 10:48:05 +0000 Subject: [PATCH] New puzzle! Contributed by Steffen Bauer, an implementation of 'Haunted Mirror Maze', a game involving placing ghosts, zombies and vampires in a grid so that the right numbers of them are visible along sight-lines reflected through multiple mirrors. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@9652 cda61777-01e9-0310-a592-d414129be87e --- LICENCE | 4 +- icons/Makefile | 10 +- icons/undead.sav | 14 + puzzles.but | 75 +- undead.R | 18 + undead.c | 2594 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 2708 insertions(+), 7 deletions(-) create mode 100644 icons/undead.sav create mode 100644 undead.R create mode 100644 undead.c diff --git a/LICENCE b/LICENCE index 90f5040..ad8c6f0 100644 --- a/LICENCE +++ b/LICENCE @@ -1,8 +1,8 @@ This software is copyright (c) 2004-2012 Simon Tatham. Portions copyright Richard Boulton, James Harvey, Mike Pinna, Jonas -Kölker, Dariusz Olszewski, Michael Schierl, Lambros Lambrou and -Bernd Schmidt. +Kölker, Dariusz Olszewski, Michael Schierl, Lambros Lambrou, Bernd +Schmidt and Steffen Bauer. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files diff --git a/icons/Makefile b/icons/Makefile index 9901de5..2d4b65b 100644 --- a/icons/Makefile +++ b/icons/Makefile @@ -1,9 +1,10 @@ # Makefile for Puzzles icons. -PUZZLES = blackbox bridges cube dominosa fifteen filling flip galaxies guess \ - inertia keen lightup loopy magnets map mines net netslide pattern \ - pearl pegs range rect samegame signpost singles sixteen slant solo \ - tents towers twiddle unequal untangle +PUZZLES = blackbox bridges cube dominosa fifteen filling flip galaxies \ + guess inertia keen lightup loopy magnets map mines net \ + netslide pattern pearl pegs range rect samegame signpost \ + singles sixteen slant solo tents towers twiddle undead \ + unequal untangle BASE = $(patsubst %,%-base.png,$(PUZZLES)) WEB = $(patsubst %,%-web.png,$(PUZZLES)) @@ -81,6 +82,7 @@ solo-ibase.png : override CROP=481x481 145x145+24+24 tents-ibase.png : override CROP=320x320 165x165+142+0 towers-ibase.png : override CROP=300x300 102x102+151+6 twiddle-ibase.png : override CROP=192x192 102x102+69+21 +undead-ibase.png : override CROP=448x512 192x192+32+96 unequal-ibase.png : override CROP=208x208 104x104+104+104 untangle-ibase.png : override CROP=320x320 164x164+3+116 $(IBASE): %-ibase.png: %-base.png diff --git a/icons/undead.sav b/icons/undead.sav new file mode 100644 index 0000000..3c314dd --- /dev/null +++ b/icons/undead.sav @@ -0,0 +1,14 @@ +SAVEFILE:41:Simon Tatham's Portable Puzzle Collection +VERSION :1:1 +GAME :6:Undead +PARAMS :6:4x4de2 +CPARAMS :6:4x4de2 +DESC :48:5,2,2,aRLgLLaLRL,2,0,1,2,1,1,2,5,0,0,0,2,1,3,1,1 +NSTATES :1:7 +STATEPOS:1:7 +MOVE :2:G0 +MOVE :2:V0 +MOVE :2:G2 +MOVE :2:G3 +MOVE :2:V3 +MOVE :2:Z3 diff --git a/puzzles.but b/puzzles.but index ce0ec3d..a99f3a1 100644 --- a/puzzles.but +++ b/puzzles.but @@ -2971,6 +2971,79 @@ relative to the cursor, i.e. to draw a segment or a cross. These parameters are available from the \q{Custom...} option on the \q{Type} menu. +\C{undead} \i{Undead} + +\cfg{winhelp-topic}{games.undead} + +You are given a grid of squares, some of which contain diagonal +mirrors. Every square which is not a mirror must be filled with one of +three types of undead monster: a ghost, a vampire, or a zombie. + +Vampires can be seen directly, but are invisible when reflected in +mirrors. Ghosts are the opposite way round: they can be seen in +mirrors, but are invisible when looked at directly. Zombies are +visible by any means. + +Around the edge of the grid are written numbers, which indicate how +many monsters can be seen if you look into the grid along a row or +column starting from that position. (The diagonal mirrors are +reflective on both sides.) You are also told the total number of each +type of monster in the grid. + +This puzzle type was invented by David Millar, under the name +\q{Haunted Mirror Maze}. See \k{janko-undead} for more details. + +Undead was contributed to this collection by Steffen Bauer. + +\B{janko-undead} +\W{http://www.janko.at/Raetsel/Spukschloss/index.htm} + +\H{undead-controls} \I{controls, for Undead}Undead controls + +Undead has a similar control system to Solo, Unequal and Keen. + +To play Undead, click the mouse in any empty square and then type a +letter on the keyboard indicating the type of monster: \q{G} for a +ghost, \q{V} for a vampire, or \q{Z} for a zombie. If you make a +mistake, click the mouse in the incorrect square and press Space to +clear it again (or use the Undo feature). + +If you \e{right}-click in a square and then type a letter, the +corresponding monster will be shown in reduced size in that square, as +a \q{pencil mark}. You can have pencil marks for multiple monsters in +the same square. A square containing a full-size monster cannot also +contain pencil marks. + +The game pays no attention to pencil marks, so exactly what you use +them for is up to you: you can use them as reminders that a particular +square needs to be re-examined once you know more about a particular +monster, or you can use them as lists of the possible monster in a +given square, or anything else you feel like. + +To erase a single pencil mark, right-click in the square and type +the same letter again. + +All pencil marks in a square are erased when you left-click and type a +monster letter, or when you left-click and press Space. Right-clicking +and pressing space will also erase pencil marks. + +As for Solo, the cursor keys can be used in conjunction with the digit +keys to place monsters or pencil marks. Use the cursor keys to move a +highlight around the grid, and type a monster letter to enter it in +the highlighted square. Pressing return toggles the highlight into a +mode in which you can enter or remove pencil marks. + +If you prefer plain letters of the alphabet to cute monster pictures, +you can press A to toggle between showing the monsters as monsters or +showing them as letters. + +(All the actions described in \k{common-actions} are also available.) + +\H{undead-parameters} \I{parameters, for Undead}Undead parameters + +These parameters are available from the \q{Custom...} option on the +\q{Type} menu. + \dt \e{Width}, \e{Height} \dd Size of grid in squares. @@ -2985,7 +3058,7 @@ This software is \i{copyright} 2004-2012 Simon Tatham. Portions copyright Richard Boulton, James Harvey, Mike Pinna, Jonas K\u00F6{oe}lker, Dariusz Olszewski, Michael Schierl, Lambros -Lambrou and Bernd Schmidt. +Lambrou, Bernd Schmidt and Steffen Bauer. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files diff --git a/undead.R b/undead.R new file mode 100644 index 0000000..2492d5e --- /dev/null +++ b/undead.R @@ -0,0 +1,18 @@ +# -*- makefile -*- + +undead : [X] GTK COMMON undead undead-icon|no-icon +undead : [G] WINDOWS COMMON undead undead.res|noicon.res + +ALL += undead[COMBINED] + +!begin gtk +GAMES += undead +!end + +!begin >list.c + A(undead) \ +!end + +!begin >wingames.lst +undead.exe:Undead +!end diff --git a/undead.c b/undead.c new file mode 100644 index 0000000..6ce6eaa --- /dev/null +++ b/undead.c @@ -0,0 +1,2594 @@ +/* + * 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 +#include +#include +#include +#include +#include + +#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;icommon->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;icommon->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;icommon->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 && x0 && yw+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;jcommon->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;jcommon->num_total;j++) { + num_monsters = 0; + for (k=0;kcommon->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;pcommon->paths[count].length;p++) { + int m; + m = state->common->paths[count].p[p]; + if (m == -1) continue; + found = FALSE; + for (j=0; jcommon->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;iguess[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;pcommon->paths[counter].length;p++) { + if (state->common->paths[counter].p[p] == -1) mirror = TRUE; + else { + for (i=0;icommon->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;icommon->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;iguess[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;icommon->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;icommon->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=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;icommon->num_total;i++) { + guess[i] = state->guess[i]; + possible[i] = 0; + } + + for (p=0;pcommon->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;iguess[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;icommon->num_total;i++) { + guess[i] = state->guess[i]; + } + count = 0; + for (i=0;iguess[paths[p].mapping[i]] &= + possible[paths[p].mapping[i]]; + sfree(loop.possible); + sfree(loop.guess); + } + } + + for (i=0;icommon->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;icommon->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;pcommon->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;icommon->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;hcommon->params.h+1;h++) + for (w=1;wcommon->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;gcommon->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;gcommon->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;pcommon->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;gcommon->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;wcommon->params.w+1;w++) + for (h=1;hcommon->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;pcommon->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;gcommon->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;pcommon->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;pcommon->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;pcommon->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;ycommon->params.h+1;y++) + for (x=1;xcommon->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;icommon->num_total;i++) { + state->guess[i] = 7; + state->pencils[i] = 0; + state->common->fixed[i] = FALSE; + } + for (i=0;icommon->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;pcommon->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;pcommon->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;pcommon->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;hcommon->params.h+2;h++) { + for (w=0;wcommon->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;icommon->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;xcommon->params.w+1;x++) + for (y=1;ycommon->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;xcommon->params.w+1;x++) + for (y=1;ycommon->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;xcommon->params.w+1;x++) + for (y=1;ycommon->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;icommon->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;icommon->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;icommon->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;pcommon->num_paths;p++) + if (!check_path_solution(ret,p)) correct = FALSE; + + for (i=0;icommon->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;icommon->num_total;i++) + ds->pencils[i] = 0; + + ds->cell_errors = snewn(state->common->wh,unsigned char); + for (i=0;icommon->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<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;iw;i++) + for (j=0;jh;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;icommon->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 */ +}; + -- 2.11.0