};
struct game_state {
- grid *game_grid;
+ grid *game_grid; /* ref-counted (internally) */
/* Put -1 in a face that doesn't get a clue */
signed char *clues;
SOLVERLIST(SOLVER_FN_DECL)
static int (*(solver_fns[]))(solver_state *) = { SOLVERLIST(SOLVER_FN) };
static int const solver_diffs[] = { SOLVERLIST(SOLVER_DIFF) };
-const int NUM_SOLVERS = sizeof(solver_diffs)/sizeof(*solver_diffs);
+static const int NUM_SOLVERS = sizeof(solver_diffs)/sizeof(*solver_diffs);
struct game_params {
int w, h;
int diff;
int type;
-
- /* Grid generation is expensive, so keep a (ref-counted) reference to the
- * grid for these parameters, and only generate when required. */
- grid *game_grid;
};
/* line_drawstate is the same as line_state, but with the extra ERROR
/* ------- List of grid generators ------- */
#define GRIDLIST(A) \
- A(Squares,grid_new_square,3,3) \
- A(Triangular,grid_new_triangular,3,3) \
- A(Honeycomb,grid_new_honeycomb,3,3) \
- A(Snub-Square,grid_new_snubsquare,3,3) \
- A(Cairo,grid_new_cairo,3,4) \
- A(Great-Hexagonal,grid_new_greathexagonal,3,3) \
- A(Octagonal,grid_new_octagonal,3,3) \
- A(Kites,grid_new_kites,3,3) \
- A(Floret,grid_new_floret,1,2) \
- A(Dodecagonal,grid_new_dodecagonal,2,2) \
- A(Great-Dodecagonal,grid_new_greatdodecagonal,2,2)
-
-#define GRID_NAME(title,fn,amin,omin) #title,
-#define GRID_CONFIG(title,fn,amin,omin) ":" #title
-#define GRID_FN(title,fn,amin,omin) &fn,
-#define GRID_SIZES(title,fn,amin,omin) \
+ A(Squares,GRID_SQUARE,3,3) \
+ A(Triangular,GRID_TRIANGULAR,3,3) \
+ A(Honeycomb,GRID_HONEYCOMB,3,3) \
+ A(Snub-Square,GRID_SNUBSQUARE,3,3) \
+ A(Cairo,GRID_CAIRO,3,4) \
+ A(Great-Hexagonal,GRID_GREATHEXAGONAL,3,3) \
+ A(Octagonal,GRID_OCTAGONAL,3,3) \
+ A(Kites,GRID_KITE,3,3) \
+ A(Floret,GRID_FLORET,1,2) \
+ A(Dodecagonal,GRID_DODECAGONAL,2,2) \
+ A(Great-Dodecagonal,GRID_GREATDODECAGONAL,2,2) \
+ A(Penrose (kite/dart),GRID_PENROSE_P2,3,3) \
+ A(Penrose (rhombs),GRID_PENROSE_P3,3,3)
+
+#define GRID_NAME(title,type,amin,omin) #title,
+#define GRID_CONFIG(title,type,amin,omin) ":" #title
+#define GRID_TYPE(title,type,amin,omin) type,
+#define GRID_SIZES(title,type,amin,omin) \
{amin, omin, \
"Width and height for this grid type must both be at least " #amin, \
"At least one of width and height for this grid type must be at least " #omin,},
static char const *const gridnames[] = { GRIDLIST(GRID_NAME) };
#define GRID_CONFIGS GRIDLIST(GRID_CONFIG)
-static grid * (*(grid_fns[]))(int w, int h) = { GRIDLIST(GRID_FN) };
-#define NUM_GRID_TYPES (sizeof(grid_fns) / sizeof(grid_fns[0]))
+static grid_type grid_types[] = { GRIDLIST(GRID_TYPE) };
+#define NUM_GRID_TYPES (sizeof(grid_types) / sizeof(grid_types[0]))
static const struct {
int amin, omin;
char *aerr, *oerr;
/* Generates a (dynamically allocated) new grid, according to the
* type and size requested in params. Does nothing if the grid is already
- * generated. The allocated grid is owned by the params object, and will be
- * freed in free_params(). */
-static void params_generate_grid(game_params *params)
+ * generated. */
+static grid *loopy_generate_grid(game_params *params, char *grid_desc)
{
- if (!params->game_grid) {
- params->game_grid = grid_fns[params->type](params->w, params->h);
- }
+ return grid_new(grid_types[params->type], params->w, params->h, grid_desc);
}
/* ----------------------------------------------------------------------
ret->diff = DIFF_EASY;
ret->type = 0;
- ret->game_grid = NULL;
-
return ret;
}
game_params *ret = snew(game_params);
*ret = *params; /* structure copy */
- if (ret->game_grid) {
- ret->game_grid->refcount++;
- }
return ret;
}
static const game_params presets[] = {
#ifdef SMALL_SCREEN
- { 7, 7, DIFF_EASY, 0, NULL },
- { 7, 7, DIFF_NORMAL, 0, NULL },
- { 7, 7, DIFF_HARD, 0, NULL },
- { 7, 7, DIFF_HARD, 1, NULL },
- { 7, 7, DIFF_HARD, 2, NULL },
- { 5, 5, DIFF_HARD, 3, NULL },
- { 7, 7, DIFF_HARD, 4, NULL },
- { 5, 4, DIFF_HARD, 5, NULL },
- { 5, 5, DIFF_HARD, 6, NULL },
- { 5, 5, DIFF_HARD, 7, NULL },
- { 3, 3, DIFF_HARD, 8, NULL },
- { 3, 3, DIFF_HARD, 9, NULL },
- { 3, 3, DIFF_HARD, 10, NULL },
+ { 7, 7, DIFF_EASY, 0 },
+ { 7, 7, DIFF_NORMAL, 0 },
+ { 7, 7, DIFF_HARD, 0 },
+ { 7, 7, DIFF_HARD, 1 },
+ { 7, 7, DIFF_HARD, 2 },
+ { 5, 5, DIFF_HARD, 3 },
+ { 7, 7, DIFF_HARD, 4 },
+ { 5, 4, DIFF_HARD, 5 },
+ { 5, 5, DIFF_HARD, 6 },
+ { 5, 5, DIFF_HARD, 7 },
+ { 3, 3, DIFF_HARD, 8 },
+ { 3, 3, DIFF_HARD, 9 },
+ { 3, 3, DIFF_HARD, 10 },
+ { 6, 6, DIFF_HARD, 11 },
+ { 6, 6, DIFF_HARD, 12 },
#else
- { 7, 7, DIFF_EASY, 0, NULL },
- { 10, 10, DIFF_EASY, 0, NULL },
- { 7, 7, DIFF_NORMAL, 0, NULL },
- { 10, 10, DIFF_NORMAL, 0, NULL },
- { 7, 7, DIFF_HARD, 0, NULL },
- { 10, 10, DIFF_HARD, 0, NULL },
- { 10, 10, DIFF_HARD, 1, NULL },
- { 12, 10, DIFF_HARD, 2, NULL },
- { 7, 7, DIFF_HARD, 3, NULL },
- { 9, 9, DIFF_HARD, 4, NULL },
- { 5, 4, DIFF_HARD, 5, NULL },
- { 7, 7, DIFF_HARD, 6, NULL },
- { 5, 5, DIFF_HARD, 7, NULL },
- { 5, 5, DIFF_HARD, 8, NULL },
- { 5, 4, DIFF_HARD, 9, NULL },
- { 5, 4, DIFF_HARD, 10, NULL },
+ { 7, 7, DIFF_EASY, 0 },
+ { 10, 10, DIFF_EASY, 0 },
+ { 7, 7, DIFF_NORMAL, 0 },
+ { 10, 10, DIFF_NORMAL, 0 },
+ { 7, 7, DIFF_HARD, 0 },
+ { 10, 10, DIFF_HARD, 0 },
+ { 10, 10, DIFF_HARD, 1 },
+ { 12, 10, DIFF_HARD, 2 },
+ { 7, 7, DIFF_HARD, 3 },
+ { 9, 9, DIFF_HARD, 4 },
+ { 5, 4, DIFF_HARD, 5 },
+ { 7, 7, DIFF_HARD, 6 },
+ { 5, 5, DIFF_HARD, 7 },
+ { 5, 5, DIFF_HARD, 8 },
+ { 5, 4, DIFF_HARD, 9 },
+ { 5, 4, DIFF_HARD, 10 },
+ { 10, 10, DIFF_HARD, 11 },
+ { 10, 10, DIFF_HARD, 12 }
#endif
};
static void free_params(game_params *params)
{
- if (params->game_grid) {
- grid_free(params->game_grid);
- }
sfree(params);
}
static void decode_params(game_params *params, char const *string)
{
- if (params->game_grid) {
- grid_free(params->game_grid);
- params->game_grid = NULL;
- }
params->h = params->w = atoi(string);
params->diff = DIFF_EASY;
while (*string && isdigit((unsigned char)*string)) string++;
ret->type = cfg[2].ival;
ret->diff = cfg[3].ival;
- ret->game_grid = NULL;
return ret;
}
return retval;
}
+#define GRID_DESC_SEP '_'
+
+/* Splits up a (optional) grid_desc from the game desc. Returns the
+ * grid_desc (which needs freeing) and updates the desc pointer to
+ * start of real desc, or returns NULL if no desc. */
+static char *extract_grid_desc(char **desc)
+{
+ char *sep = strchr(*desc, GRID_DESC_SEP), *gd;
+ int gd_len;
+
+ if (!sep) return NULL;
+
+ gd_len = sep - (*desc);
+ gd = snewn(gd_len+1, char);
+ memcpy(gd, *desc, gd_len);
+ gd[gd_len] = '\0';
+
+ *desc = sep+1;
+
+ return gd;
+}
+
/* We require that the params pass the test in validate_params and that the
* description fills the entire game area */
static char *validate_desc(game_params *params, char *desc)
{
int count = 0;
grid *g;
- params_generate_grid(params);
- g = params->game_grid;
+ char *grid_desc, *ret;
+
+ /* It's pretty inefficient to do this just for validation. All we need to
+ * know is the precise number of faces. */
+ grid_desc = extract_grid_desc(&desc);
+ ret = grid_validate_desc(grid_types[params->type], params->w, params->h, grid_desc);
+ if (ret) return ret;
+
+ g = loopy_generate_grid(params, grid_desc);
+ if (grid_desc) sfree(grid_desc);
for (; *desc; ++desc) {
if ((*desc >= '0' && *desc <= '9') || (*desc >= 'A' && *desc <= 'Z')) {
if (count > g->num_faces)
return "Description too long for board size";
+ grid_free(g);
+
return NULL;
}
static void game_compute_size(game_params *params, int tilesize,
int *x, int *y)
{
- grid *g;
int grid_width, grid_height, rendered_width, rendered_height;
+ int g_tilesize;
+
+ grid_compute_size(grid_types[params->type], params->w, params->h,
+ &g_tilesize, &grid_width, &grid_height);
- params_generate_grid(params);
- g = params->game_grid;
- grid_width = g->highest_x - g->lowest_x;
- grid_height = g->highest_y - g->lowest_y;
/* multiply first to minimise rounding error on integer division */
- rendered_width = grid_width * tilesize / g->tilesize;
- rendered_height = grid_height * tilesize / g->tilesize;
+ rendered_width = grid_width * tilesize / g_tilesize;
+ rendered_height = grid_height * tilesize / g_tilesize;
*x = rendered_width + 2 * BORDER(tilesize) + 1;
*y = rendered_height + 2 * BORDER(tilesize) + 1;
}
ret[COL_FOREGROUND * 3 + 1] = 0.0F;
ret[COL_FOREGROUND * 3 + 2] = 0.0F;
- ret[COL_LINEUNKNOWN * 3 + 0] = 0.8F;
- ret[COL_LINEUNKNOWN * 3 + 1] = 0.8F;
+ /*
+ * We want COL_LINEUNKNOWN to be a yellow which is a bit darker
+ * than the background. (I previously set it to 0.8,0.8,0, but
+ * found that this went badly with the 0.8,0.8,0.8 favoured as a
+ * background by the Java frontend.)
+ */
+ ret[COL_LINEUNKNOWN * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] * 0.9F;
+ ret[COL_LINEUNKNOWN * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] * 0.9F;
ret[COL_LINEUNKNOWN * 3 + 2] = 0.0F;
ret[COL_HIGHLIGHT * 3 + 0] = 1.0F;
static void game_free_drawstate(drawing *dr, game_drawstate *ds)
{
+ sfree(ds->textx);
+ sfree(ds->texty);
sfree(ds->clue_error);
sfree(ds->clue_satisfied);
sfree(ds->lines);
char **aux, int interactive)
{
/* solution and description both use run-length encoding in obvious ways */
- char *retval;
+ char *retval, *game_desc, *grid_desc;
grid *g;
game_state *state = snew(game_state);
game_state *state_new;
- int count = 0;
- params_generate_grid(params);
- state->game_grid = g = params->game_grid;
- g->refcount++;
+
+ grid_desc = grid_new_desc(grid_types[params->type], params->w, params->h, rs);
+ state->game_grid = g = loopy_generate_grid(params, grid_desc);
+
state->clues = snewn(g->num_faces, signed char);
state->lines = snewn(g->num_edges, char);
state->line_errors = snewn(g->num_edges, unsigned char);
* preventing games smaller than 4x4 seems to stop this happening */
do {
add_full_clues(state, rs);
- if (++count%100 == 0) printf("tried %d times to make a unique board\n", count);
} while (!game_has_unique_soln(state, params->diff));
state_new = remove_clues(state, rs, params->diff);
goto newboard_please;
}
- retval = state_to_text(state);
+ game_desc = state_to_text(state);
free_game(state);
+ if (grid_desc) {
+ retval = snewn(strlen(grid_desc) + 1 + strlen(game_desc) + 1, char);
+ sprintf(retval, "%s%c%s", grid_desc, (int)GRID_DESC_SEP, game_desc);
+ sfree(grid_desc);
+ sfree(game_desc);
+ } else {
+ retval = game_desc;
+ }
+
assert(!validate_desc(params, retval));
return retval;
game_state *state = snew(game_state);
int empties_to_make = 0;
int n,n2;
- const char *dp = desc;
+ const char *dp;
+ char *grid_desc;
grid *g;
int num_faces, num_edges;
- params_generate_grid(params);
- state->game_grid = g = params->game_grid;
- g->refcount++;
+ grid_desc = extract_grid_desc(&desc);
+ state->game_grid = g = loopy_generate_grid(params, grid_desc);
+ if (grid_desc) sfree(grid_desc);
+
+ dp = desc;
+
num_faces = g->num_faces;
num_edges = g->num_edges;
if (state->clues[i] < 0)
continue;
+ /*
+ * This code checks whether the numeric clue on a face is so
+ * large as to permit all its remaining LINE_UNKNOWNs to be
+ * filled in as LINE_YES, or alternatively so small as to
+ * permit them all to be filled in as LINE_NO.
+ */
+
if (state->clues[i] < current_yes) {
sstate->solver_status = SOLVER_MISTAKE;
return DIFF_EASY;
sstate->face_solved[i] = TRUE;
continue;
}
+
+ if (f->order - state->clues[i] == current_no + 1 &&
+ f->order - current_yes - current_no > 2) {
+ /*
+ * One small refinement to the above: we also look for any
+ * adjacent pair of LINE_UNKNOWNs around the face with
+ * some LINE_YES incident on it from elsewhere. If we find
+ * one, then we know that pair of LINE_UNKNOWNs can't
+ * _both_ be LINE_YES, and hence that pushes us one line
+ * closer to being able to determine all the rest.
+ */
+ int j, k, e1, e2, e, d;
+
+ for (j = 0; j < f->order; j++) {
+ e1 = f->edges[j] - g->edges;
+ e2 = f->edges[j+1 < f->order ? j+1 : 0] - g->edges;
+
+ if (g->edges[e1].dot1 == g->edges[e2].dot1 ||
+ g->edges[e1].dot1 == g->edges[e2].dot2) {
+ d = g->edges[e1].dot1 - g->dots;
+ } else {
+ assert(g->edges[e1].dot2 == g->edges[e2].dot1 ||
+ g->edges[e1].dot2 == g->edges[e2].dot2);
+ d = g->edges[e1].dot2 - g->dots;
+ }
+
+ if (state->lines[e1] == LINE_UNKNOWN &&
+ state->lines[e2] == LINE_UNKNOWN) {
+ for (k = 0; k < g->dots[d].order; k++) {
+ int e = g->dots[d].edges[k] - g->edges;
+ if (state->lines[e] == LINE_YES)
+ goto found; /* multi-level break */
+ }
+ }
+ }
+ continue;
+
+ found:
+ /*
+ * If we get here, we've found such a pair of edges, and
+ * they're e1 and e2.
+ */
+ for (j = 0; j < f->order; j++) {
+ e = f->edges[j] - g->edges;
+ if (state->lines[e] == LINE_UNKNOWN && e != e1 && e != e2) {
+ int r = solver_set_line(sstate, e, LINE_YES);
+ assert(r);
+ diff = min(diff, DIFF_EASY);
+ }
+ }
+ }
}
check_caches(sstate);
/* Returns (into x,y) position of centre of face for rendering the text clue.
*/
static void face_text_pos(const game_drawstate *ds, const grid *g,
- const grid_face *f, int *xret, int *yret)
+ grid_face *f, int *xret, int *yret)
{
- int x, y, x0, y0, x1, y1, xbest, ybest, i, shift;
- long bestdist;
int faceindex = f - g->faces;
/*
}
/*
- * Otherwise, try to find the point in the polygon with the
- * maximum distance to any edge or corner.
- *
- * Start by working out the face's bounding box, in grid
- * coordinates.
+ * Otherwise, use the incentre computed by grid.c and convert it
+ * to screen coordinates.
*/
- x0 = x1 = f->dots[0]->x;
- y0 = y1 = f->dots[0]->y;
- for (i = 1; i < f->order; i++) {
- if (x0 > f->dots[i]->x) x0 = f->dots[i]->x;
- if (x1 < f->dots[i]->x) x1 = f->dots[i]->x;
- if (y0 > f->dots[i]->y) y0 = f->dots[i]->y;
- if (y1 < f->dots[i]->y) y1 = f->dots[i]->y;
- }
-
- /*
- * If the grid is at excessive resolution, decide on a scaling
- * factor to bring it within reasonable bounds so we don't have to
- * think too hard or suffer integer overflow.
- */
- shift = 0;
- while (x1 - x0 > 128 || y1 - y0 > 128) {
- shift++;
- x0 >>= 1;
- x1 >>= 1;
- y0 >>= 1;
- y1 >>= 1;
- }
-
- /*
- * Now iterate over every point in that bounding box.
- */
- xbest = ybest = -1;
- bestdist = -1;
- for (y = y0; y <= y1; y++) {
- for (x = x0; x <= x1; x++) {
- /*
- * First, disqualify the point if it's not inside the
- * polygon, which we work out by counting the edges to the
- * right of the point. (For tiebreaking purposes when
- * edges start or end on our y-coordinate or go right
- * through it, we consider our point to be offset by a
- * small _positive_ epsilon in both the x- and
- * y-direction.)
- */
- int in = 0;
- for (i = 0; i < f->order; i++) {
- int xs = f->edges[i]->dot1->x >> shift;
- int xe = f->edges[i]->dot2->x >> shift;
- int ys = f->edges[i]->dot1->y >> shift;
- int ye = f->edges[i]->dot2->y >> shift;
- if ((y >= ys && y < ye) || (y >= ye && y < ys)) {
- /*
- * The line goes past our y-position. Now we need
- * to know if its x-coordinate when it does so is
- * to our right.
- *
- * The x-coordinate in question is mathematically
- * (y - ys) * (xe - xs) / (ye - ys), and we want
- * to know whether (x - xs) >= that. Of course we
- * avoid the division, so we can work in integers;
- * to do this we must multiply both sides of the
- * inequality by ye - ys, which means we must
- * first check that's not negative.
- */
- int num = xe - xs, denom = ye - ys;
- if (denom < 0) {
- num = -num;
- denom = -denom;
- }
- if ((x - xs) * denom >= (y - ys) * num)
- in ^= 1;
- }
- }
-
- if (in) {
- long mindist = LONG_MAX;
-
- /*
- * This point is inside the polygon, so now we check
- * its minimum distance to every edge and corner.
- * First the corners ...
- */
- for (i = 0; i < f->order; i++) {
- int xp = f->dots[i]->x >> shift;
- int yp = f->dots[i]->y >> shift;
- int dx = x - xp, dy = y - yp;
- long dist = (long)dx*dx + (long)dy*dy;
- if (mindist > dist)
- mindist = dist;
- }
-
- /*
- * ... and now also check the perpendicular distance
- * to every edge, if the perpendicular lies between
- * the edge's endpoints.
- */
- for (i = 0; i < f->order; i++) {
- int xs = f->edges[i]->dot1->x >> shift;
- int xe = f->edges[i]->dot2->x >> shift;
- int ys = f->edges[i]->dot1->y >> shift;
- int ye = f->edges[i]->dot2->y >> shift;
-
- /*
- * If s and e are our endpoints, and p our
- * candidate circle centre, the foot of a
- * perpendicular from p to the line se lies
- * between s and e if and only if (p-s).(e-s) lies
- * strictly between 0 and (e-s).(e-s).
- */
- int edx = xe - xs, edy = ye - ys;
- int pdx = x - xs, pdy = y - ys;
- long pde = (long)pdx * edx + (long)pdy * edy;
- long ede = (long)edx * edx + (long)edy * edy;
- if (0 < pde && pde < ede) {
- /*
- * Yes, the nearest point on this edge is
- * closer than either endpoint, so we must
- * take it into account by measuring the
- * perpendicular distance to the edge and
- * checking its square against mindist.
- */
-
- long pdre = (long)pdx * edy - (long)pdy * edx;
- long sqlen = pdre * pdre / ede;
-
- if (mindist > sqlen)
- mindist = sqlen;
- }
- }
-
- /*
- * Right. Now we know the biggest circle around this
- * point, so we can check it against bestdist.
- */
- if (bestdist < mindist) {
- bestdist = mindist;
- xbest = x;
- ybest = y;
- }
- }
- }
- }
-
- assert(bestdist >= 0);
-
- /* convert to screen coordinates */
- grid_to_screen(ds, g, xbest << shift, ybest << shift,
+ grid_find_incentre(f);
+ grid_to_screen(ds, g, f->ix, f->iy,
&ds->textx[faceindex], &ds->texty[faceindex]);
*xret = ds->textx[faceindex];
grid *g = state->game_grid;
grid_edge *e = g->edges + i;
int x1, x2, y1, y2;
- int xmin, ymin, xmax, ymax;
int line_colour;
if (state->line_errors[i])
grid_to_screen(ds, g, e->dot1->x, e->dot1->y, &x1, &y1);
grid_to_screen(ds, g, e->dot2->x, e->dot2->y, &x2, &y2);
- xmin = min(x1, x2);
- xmax = max(x1, x2);
- ymin = min(y1, y2);
- ymax = max(y1, y2);
-
if (line_colour == COL_FAINT) {
static int draw_faint_lines = -1;
if (draw_faint_lines < 0) {
draw_rect(dr, x, y, w, h, COL_BACKGROUND);
for (i = 0; i < g->num_faces; i++) {
- face_text_bbox(ds, g, &g->faces[i], &bx, &by, &bw, &bh);
- if (boxes_intersect(x, y, w, h, bx, by, bw, bh))
- game_redraw_clue(dr, ds, state, i);
+ if (state->clues[i] >= 0) {
+ face_text_bbox(ds, g, &g->faces[i], &bx, &by, &bw, &bh);
+ if (boxes_intersect(x, y, w, h, bx, by, bw, bh))
+ game_redraw_clue(dr, ds, state, i);
+ }
}
for (phase = 0; phase < NPHASES; phase++) {
for (i = 0; i < g->num_edges; i++) {
}
#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */
~mdw / sgt / puzzles / blobdiff