#define DRAG_THRESHOLD (CIRCLE_RADIUS * 2)
#define PREFERRED_TILESIZE 64
-#define FLASH_TIME 0.13F
+#define FLASH_TIME 0.30F
#define ANIM_TIME 0.13F
#define SOLVEANIM_TIME 0.50F
enum {
COL_BACKGROUND,
COL_LINE,
+#ifdef SHOW_CROSSINGS
+ COL_CROSSEDLINE,
+#endif
COL_OUTLINE,
COL_POINT,
COL_DRAGPOINT,
COL_NEIGHBOUR,
+ COL_FLASH1,
+ COL_FLASH2,
NCOLOURS
};
* Points are stored using rational coordinates, with the same
* denominator for both coordinates.
*/
- int x, y, d;
+ long x, y, d;
} point;
typedef struct edge {
game_params params;
int w, h; /* extent of coordinate system only */
point *pts;
+#ifdef SHOW_CROSSINGS
+ int *crosses; /* mark edges which are crossed */
+#endif
struct graph *graph;
int completed, cheated, just_solved;
};
*/
static int cross(point a1, point a2, point b1, point b2)
{
- int b1x, b1y, b2x, b2y, px, py, d1, d2, d3;
+ long b1x, b1y, b2x, b2y, px, py, d1, d2, d3;
/*
* The condition for crossing is that b1 and b2 are on opposite
d = n;
a = 0;
- b = 1 << 30; /* largest available power of 4 */
+ b = 1L << 30; /* largest available power of 4 */
do {
a >>= 1;
di = 2*a + b;
*/
static void make_circle(point *pts, int n, int w)
{
- int d, r, c, i;
+ long d, r, c, i;
/*
* First, decide on a denominator. Although in principle it
for (i = 0; i < n; i++) {
double angle = i * 2 * PI / n;
double x = r * sin(angle), y = - r * cos(angle);
- pts[i].x = (int)(c + x + 0.5);
- pts[i].y = (int)(c + y + 0.5);
+ pts[i].x = (long)(c + x + 0.5);
+ pts[i].y = (long)(c + y + 0.5);
pts[i].d = d;
}
}
static char *new_game_desc(game_params *params, random_state *rs,
char **aux, int interactive)
{
- int n = params->n;
- int w, h, i, j, k, m;
+ int n = params->n, i;
+ long w, h, j, k, m;
point *pts, *pts2;
- int *tmp;
+ long *tmp;
tree234 *edges, *vertices;
edge *e, *e2;
vertex *v, *vs, *vlist;
* Choose n points from this grid.
*/
pts = snewn(n, point);
- tmp = snewn(w*h, int);
+ tmp = snewn(w*h, long);
for (i = 0; i < w*h; i++)
tmp[i] = i;
shuffle(tmp, w*h, sizeof(*tmp), rs);
* they come out with at least one crossed line when arranged
* in a circle (so that the puzzle isn't immediately solved!).
*/
- tmp = snewn(n, int);
+ tmp = snewn(n, long);
for (i = 0; i < n; i++)
tmp[i] = i;
pts2 = snewn(n, point);
}
pts2[j].x += pts2[j].d / 2;
pts2[j].y += pts2[j].d / 2;
- auxlen += sprintf(buf, ";P%d:%d,%d/%d", i,
+ auxlen += sprintf(buf, ";P%d:%ld,%ld/%ld", i,
pts2[j].x, pts2[j].y, pts2[j].d);
}
k = 0;
auxstr = snewn(auxlen, char);
auxstr[k++] = 'S';
for (i = 0; i < n; i++)
- k += sprintf(auxstr+k, ";P%d:%d,%d/%d", i,
+ k += sprintf(auxstr+k, ";P%d:%ld,%ld/%ld", i,
pts2[i].x, pts2[i].y, pts2[i].d);
assert(k < auxlen);
*aux = auxstr;
return NULL;
}
+static void mark_crossings(game_state *state)
+{
+ int ok = TRUE;
+ int i, j;
+ edge *e, *e2;
+
+#ifdef SHOW_CROSSINGS
+ for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++)
+ state->crosses[i] = FALSE;
+#endif
+
+ /*
+ * Check correctness: for every pair of edges, see whether they
+ * cross.
+ */
+ for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
+ for (j = i+1; (e2 = index234(state->graph->edges, j)) != NULL; j++) {
+ if (e2->a == e->a || e2->a == e->b ||
+ e2->b == e->a || e2->b == e->b)
+ continue;
+ if (cross(state->pts[e2->a], state->pts[e2->b],
+ state->pts[e->a], state->pts[e->b])) {
+ ok = FALSE;
+#ifdef SHOW_CROSSINGS
+ state->crosses[i] = state->crosses[j] = TRUE;
+#else
+ goto done; /* multi-level break - sorry */
+#endif
+ }
+ }
+ }
+
+ /*
+ * e == NULL if we've gone through all the edge pairs
+ * without finding a crossing.
+ */
+#ifndef SHOW_CROSSINGS
+ done:
+#endif
+ if (ok)
+ state->completed = TRUE;
+}
+
static game_state *new_game(midend_data *me, game_params *params, char *desc)
{
int n = params->n;
state->graph = snew(struct graph);
state->graph->refcount = 1;
state->graph->edges = newtree234(edgecmp);
- state->completed = state->cheated = state->just_solved = FALSE;
+ state->cheated = state->just_solved = FALSE;
while (*desc) {
a = atoi(desc);
addedge(state->graph->edges, a, b);
}
+#ifdef SHOW_CROSSINGS
+ state->crosses = snewn(count234(state->graph->edges), int);
+#endif
+ mark_crossings(state); /* sets up `crosses' and `completed' */
+
return state;
}
ret->completed = state->completed;
ret->cheated = state->cheated;
ret->just_solved = state->just_solved;
+#ifdef SHOW_CROSSINGS
+ ret->crosses = snewn(count234(ret->graph->edges), int);
+ memcpy(ret->crosses, state->crosses,
+ count234(ret->graph->edges) * sizeof(int));
+#endif
return ret;
}
static char *solve_game(game_state *state, game_state *currstate,
char *aux, char **error)
{
+ int n = state->params.n;
+ int matrix[4];
+ point *pts;
+ int i, j, besti;
+ float bestd;
+ char buf[80], *ret;
+ int retlen, retsize;
+
if (!aux) {
*error = "Solution not known for this puzzle";
return NULL;
}
- return dupstr(aux);
+ /*
+ * Decode the aux_info to get the original point positions.
+ */
+ pts = snewn(n, point);
+ aux++; /* eat 'S' */
+ for (i = 0; i < n; i++) {
+ int p, k;
+ long x, y, d;
+ int ret = sscanf(aux, ";P%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k);
+ if (ret != 4 || p != i) {
+ *error = "Internal error: aux_info badly formatted";
+ sfree(pts);
+ return NULL;
+ }
+ pts[i].x = x;
+ pts[i].y = y;
+ pts[i].d = d;
+ aux += k;
+ }
+
+ /*
+ * Now go through eight possible symmetries of the point set.
+ * For each one, work out the sum of the Euclidean distances
+ * between the points' current positions and their new ones.
+ *
+ * We're squaring distances here, which means we're at risk of
+ * integer overflow. Fortunately, there's no real need to be
+ * massively careful about rounding errors, since this is a
+ * non-essential bit of the code; so I'll just work in floats
+ * internally.
+ */
+ besti = -1;
+ bestd = 0.0F;
+
+ for (i = 0; i < 8; i++) {
+ float d;
+
+ matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
+ matrix[i & 1] = (i & 2) ? +1 : -1;
+ matrix[3-(i&1)] = (i & 4) ? +1 : -1;
+
+ d = 0.0F;
+ for (j = 0; j < n; j++) {
+ float px = (float)pts[j].x / pts[j].d;
+ float py = (float)pts[j].y / pts[j].d;
+ float sx = (float)currstate->pts[j].x / currstate->pts[j].d;
+ float sy = (float)currstate->pts[j].y / currstate->pts[j].d;
+ float cx = (float)currstate->w / 2;
+ float cy = (float)currstate->h / 2;
+ float ox, oy, dx, dy;
+
+ px -= cx;
+ py -= cy;
+
+ ox = matrix[0] * px + matrix[1] * py;
+ oy = matrix[2] * px + matrix[3] * py;
+
+ ox += cx;
+ oy += cy;
+
+ dx = ox - sx;
+ dy = oy - sy;
+
+ d += dx*dx + dy*dy;
+ }
+
+ if (besti < 0 || bestd > d) {
+ besti = i;
+ bestd = d;
+ }
+ }
+
+ assert(besti >= 0);
+
+ /*
+ * Now we know which symmetry is closest to the points' current
+ * positions. Use it.
+ */
+ matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
+ matrix[besti & 1] = (besti & 2) ? +1 : -1;
+ matrix[3-(besti&1)] = (besti & 4) ? +1 : -1;
+
+ retsize = 256;
+ ret = snewn(retsize, char);
+ retlen = 0;
+ ret[retlen++] = 'S';
+ ret[retlen] = '\0';
+
+ for (i = 0; i < n; i++) {
+ float px = (float)pts[i].x / pts[i].d;
+ float py = (float)pts[i].y / pts[i].d;
+ float cx = (float)currstate->w / 2;
+ float cy = (float)currstate->h / 2;
+ float ox, oy;
+ int extra;
+
+ px -= cx;
+ py -= cy;
+
+ ox = matrix[0] * px + matrix[1] * py;
+ oy = matrix[2] * px + matrix[3] * py;
+
+ ox += cx;
+ oy += cy;
+
+ /*
+ * Use a fixed denominator of 2, because we know the
+ * original points were on an integer grid offset by 1/2.
+ */
+ pts[i].d = 2;
+ ox *= pts[i].d;
+ oy *= pts[i].d;
+ pts[i].x = ox + 0.5;
+ pts[i].y = oy + 0.5;
+
+ extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i,
+ pts[i].x, pts[i].y, pts[i].d);
+ if (retlen + extra >= retsize) {
+ retsize = retlen + extra + 256;
+ ret = sresize(ret, retsize, char);
+ }
+ strcpy(ret + retlen, buf);
+ retlen += extra;
+ }
+
+ sfree(pts);
+
+ return ret;
}
static char *game_text_format(game_state *state)
}
struct game_drawstate {
- int tilesize;
+ long tilesize;
};
static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
int n = state->params.n;
if (button == LEFT_BUTTON) {
- int i, best, bestd;
+ int i, best;
+ long bestd;
/*
* Begin drag. We drag the vertex _nearest_ to the pointer,
bestd = 0;
for (i = 0; i < n; i++) {
- int px = state->pts[i].x * ds->tilesize / state->pts[i].d;
- int py = state->pts[i].y * ds->tilesize / state->pts[i].d;
- int dx = px - x;
- int dy = py - y;
- int d = dx*dx + dy*dy;
+ long px = state->pts[i].x * ds->tilesize / state->pts[i].d;
+ long py = state->pts[i].y * ds->tilesize / state->pts[i].d;
+ long dx = px - x;
+ long dy = py - y;
+ long d = dx*dx + dy*dy;
if (best == -1 || bestd > d) {
best = i;
* First, see if we're within range. The user can cancel a
* drag by dragging the point right off the window.
*/
- if (ui->newpoint.x < 0 || ui->newpoint.x >= state->w*ui->newpoint.d ||
- ui->newpoint.y < 0 || ui->newpoint.y >= state->h*ui->newpoint.d)
+ if (ui->newpoint.x < 0 ||
+ ui->newpoint.x >= (long)state->w*ui->newpoint.d ||
+ ui->newpoint.y < 0 ||
+ ui->newpoint.y >= (long)state->h*ui->newpoint.d)
return "";
/*
* We aren't cancelling the drag. Construct a move string
* indicating where this point is going to.
*/
- sprintf(buf, "P%d:%d,%d/%d", p,
+ sprintf(buf, "P%d:%ld,%ld/%ld", p,
ui->newpoint.x, ui->newpoint.y, ui->newpoint.d);
ui->just_dragged = TRUE;
return dupstr(buf);
static game_state *execute_move(game_state *state, char *move)
{
int n = state->params.n;
- int p, x, y, d, k;
+ int p, k;
+ long x, y, d;
game_state *ret = dup_game(state);
ret->just_solved = FALSE;
ret->cheated = ret->just_solved = TRUE;
}
if (*move == 'P' &&
- sscanf(move+1, "%d:%d,%d/%d%n", &p, &x, &y, &d, &k) == 4 &&
+ sscanf(move+1, "%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k) == 4 &&
p >= 0 && p < n && d > 0) {
ret->pts[p].x = x;
ret->pts[p].y = y;
}
}
- /*
- * Check correctness: for every pair of edges, see whether they
- * cross.
- */
- if (!ret->completed) {
- int i, j;
- edge *e, *e2;
-
- for (i = 0; (e = index234(ret->graph->edges, i)) != NULL; i++) {
- for (j = i+1; (e2 = index234(ret->graph->edges, j)) != NULL; j++) {
- if (e2->a == e->a || e2->a == e->b ||
- e2->b == e->a || e2->b == e->b)
- continue;
- if (cross(ret->pts[e2->a], ret->pts[e2->b],
- ret->pts[e->a], ret->pts[e->b]))
- break;
- }
- if (e2)
- break;
- }
-
- /*
- * e == NULL if we've gone through all the edge pairs
- * without finding a crossing.
- */
- ret->completed = (e == NULL);
- }
+ mark_crossings(ret);
return ret;
}
ret[COL_LINE * 3 + 1] = 0.0F;
ret[COL_LINE * 3 + 2] = 0.0F;
+#ifdef SHOW_CROSSINGS
+ ret[COL_CROSSEDLINE * 3 + 0] = 1.0F;
+ ret[COL_CROSSEDLINE * 3 + 1] = 0.0F;
+ ret[COL_CROSSEDLINE * 3 + 2] = 0.0F;
+#endif
+
ret[COL_OUTLINE * 3 + 0] = 0.0F;
ret[COL_OUTLINE * 3 + 1] = 0.0F;
ret[COL_OUTLINE * 3 + 2] = 0.0F;
ret[COL_NEIGHBOUR * 3 + 1] = 0.0F;
ret[COL_NEIGHBOUR * 3 + 2] = 0.0F;
+ ret[COL_FLASH1 * 3 + 0] = 0.5F;
+ ret[COL_FLASH1 * 3 + 1] = 0.5F;
+ ret[COL_FLASH1 * 3 + 2] = 0.5F;
+
+ ret[COL_FLASH2 * 3 + 0] = 1.0F;
+ ret[COL_FLASH2 * 3 + 1] = 1.0F;
+ ret[COL_FLASH2 * 3 + 2] = 1.0F;
+
*ncolours = NCOLOURS;
return ret;
}
* whole thing every time.
*/
- bg = (flashtime != 0 ? COL_DRAGPOINT : COL_BACKGROUND);
+ if (flashtime == 0)
+ bg = COL_BACKGROUND;
+ else if ((int)(flashtime * 4 / FLASH_TIME) % 2 == 0)
+ bg = COL_FLASH1;
+ else
+ bg = COL_FLASH2;
+
game_compute_size(&state->params, ds->tilesize, &w, &h);
draw_rect(fe, 0, 0, w, h, bg);
for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
point p1, p2;
- int x1, y1, x2, y2;
+ long x1, y1, x2, y2;
p1 = state->pts[e->a];
p2 = state->pts[e->b];
x2 = p2.x * ds->tilesize / p2.d;
y2 = p2.y * ds->tilesize / p2.d;
- draw_line(fe, x1, y1, x2, y2, COL_LINE);
+ draw_line(fe, x1, y1, x2, y2,
+#ifdef SHOW_CROSSINGS
+ (oldstate?oldstate:state)->crosses[i] ?
+ COL_CROSSEDLINE :
+#endif
+ COL_LINE);
}
/*
int thisc = (j == 0 ? COL_POINT :
j == 1 ? COL_NEIGHBOUR : COL_DRAGPOINT);
for (i = 0; i < state->params.n; i++) {
- int x, y, c;
+ long x, y;
+ int c;
point p = state->pts[i];
if (ui->dragpoint == i) {
~ian / sgt-puzzles.git / blobdiff