/*
* TODO:
- *
- * - Docs and checklist etc
- * - Any way we can speed up redraws on GTK? Uck.
+ *
+ * - This puzzle, perhaps uniquely among the collection, could use
+ * support for non-aspect-ratio-preserving resizes. This would
+ * require some sort of fairly large redesign, unfortunately (since
+ * it would invalidate the basic assumption that puzzles' size
+ * requirements are adequately expressed by a single scalar tile
+ * size), and probably complicate the rest of the puzzles' API as a
+ * result. So I'm not sure I really want to do it.
+ *
+ * - It would be nice if we could somehow auto-detect a real `long
+ * long' type on the host platform and use it in place of my
+ * hand-hacked int64s. It'd be faster and more reliable.
*/
#include <stdio.h>
#define SOLVEANIM_TIME 0.50F
enum {
+ COL_SYSBACKGROUND,
COL_BACKGROUND,
COL_LINE,
#ifdef SHOW_CROSSINGS
sfree(params);
}
-static game_params *dup_params(game_params *params)
+static game_params *dup_params(const game_params *params)
{
game_params *ret = snew(game_params);
*ret = *params; /* structure copy */
params->n = atoi(string);
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
{
char buf[80];
return dupstr(buf);
}
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[80];
return ret;
}
-static game_params *custom_params(config_item *cfg)
+static game_params *custom_params(const config_item *cfg)
{
game_params *ret = snew(game_params);
return ret;
}
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
{
if (params->n < 4)
return "Number of points must be at least four";
return NULL;
}
+/* ----------------------------------------------------------------------
+ * Small number of 64-bit integer arithmetic operations, to prevent
+ * integer overflow at the very core of cross().
+ */
+
+typedef struct {
+ long hi;
+ unsigned long lo;
+} int64;
+
+#define greater64(i,j) ( (i).hi>(j).hi || ((i).hi==(j).hi && (i).lo>(j).lo))
+#define sign64(i) ((i).hi < 0 ? -1 : (i).hi==0 && (i).lo==0 ? 0 : +1)
+
+static int64 mulu32to64(unsigned long x, unsigned long y)
+{
+ unsigned long a, b, c, d, t;
+ int64 ret;
+
+ a = (x & 0xFFFF) * (y & 0xFFFF);
+ b = (x & 0xFFFF) * (y >> 16);
+ c = (x >> 16) * (y & 0xFFFF);
+ d = (x >> 16) * (y >> 16);
+
+ ret.lo = a;
+ ret.hi = d + (b >> 16) + (c >> 16);
+ t = (b & 0xFFFF) << 16;
+ ret.lo += t;
+ if (ret.lo < t)
+ ret.hi++;
+ t = (c & 0xFFFF) << 16;
+ ret.lo += t;
+ if (ret.lo < t)
+ ret.hi++;
+
+#ifdef DIAGNOSTIC_VIA_LONGLONG
+ assert(((unsigned long long)ret.hi << 32) + ret.lo ==
+ (unsigned long long)x * y);
+#endif
+
+ return ret;
+}
+
+static int64 mul32to64(long x, long y)
+{
+ int sign = +1;
+ int64 ret;
+#ifdef DIAGNOSTIC_VIA_LONGLONG
+ long long realret = (long long)x * y;
+#endif
+
+ if (x < 0)
+ x = -x, sign = -sign;
+ if (y < 0)
+ y = -y, sign = -sign;
+
+ ret = mulu32to64(x, y);
+
+ if (sign < 0) {
+ ret.hi = -ret.hi;
+ ret.lo = -ret.lo;
+ if (ret.lo)
+ ret.hi--;
+ }
+
+#ifdef DIAGNOSTIC_VIA_LONGLONG
+ assert(((unsigned long long)ret.hi << 32) + ret.lo == realret);
+#endif
+
+ return ret;
+}
+
+static int64 dotprod64(long a, long b, long p, long q)
+{
+ int64 ab, pq;
+
+ ab = mul32to64(a, b);
+ pq = mul32to64(p, q);
+ ab.hi += pq.hi;
+ ab.lo += pq.lo;
+ if (ab.lo < pq.lo)
+ ab.hi++;
+ return ab;
+}
+
/*
* Determine whether the line segments between a1 and a2, and
* between b1 and b2, intersect. We count it as an intersection if
*/
static int cross(point a1, point a2, point b1, point b2)
{
- long b1x, b1y, b2x, b2y, px, py, d1, d2, d3;
+ long b1x, b1y, b2x, b2y, px, py;
+ int64 d1, d2, d3;
/*
* The condition for crossing is that b1 and b2 are on opposite
b2y = b2.y * a1.d - a1.y * b2.d;
px = a1.y * a2.d - a2.y * a1.d;
py = a2.x * a1.d - a1.x * a2.d;
- /* Take the dot products. */
- d1 = b1x * px + b1y * py;
- d2 = b2x * px + b2y * py;
+ /* Take the dot products. Here we resort to 64-bit arithmetic. */
+ d1 = dotprod64(b1x, px, b1y, py);
+ d2 = dotprod64(b2x, px, b2y, py);
/* If they have the same non-zero sign, the lines do not cross. */
- if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0))
+ if ((sign64(d1) > 0 && sign64(d2) > 0) ||
+ (sign64(d1) < 0 && sign64(d2) < 0))
return FALSE;
/*
* condition becomes whether or not they overlap within their
* line.
*/
- if (d1 == 0 && d2 == 0) {
+ if (sign64(d1) == 0 && sign64(d2) == 0) {
/* Construct the vector a2-a1. */
px = a2.x * a1.d - a1.x * a2.d;
py = a2.y * a1.d - a1.y * a2.d;
/* Determine the dot products of b1-a1 and b2-a1 with this. */
- d1 = b1x * px + b1y * py;
- d2 = b2x * px + b2y * py;
+ d1 = dotprod64(b1x, px, b1y, py);
+ d2 = dotprod64(b2x, px, b2y, py);
/* If they're both strictly negative, the lines do not cross. */
- if (d1 < 0 && d2 < 0)
+ if (sign64(d1) < 0 && sign64(d2) < 0)
return FALSE;
/* Otherwise, take the dot product of a2-a1 with itself. If
* the other two dot products both exceed this, the lines do
* not cross. */
- d3 = px * px + py * py;
- if (d1 > d3 && d2 > d3)
+ d3 = dotprod64(px, px, py, py);
+ if (greater64(d1, d3) && greater64(d2, d3))
return FALSE;
}
b2y = a2.y * b1.d - b1.y * a2.d;
px = b1.y * b2.d - b2.y * b1.d;
py = b2.x * b1.d - b1.x * b2.d;
- d1 = b1x * px + b1y * py;
- d2 = b2x * px + b2y * py;
- if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0))
+ d1 = dotprod64(b1x, px, b1y, py);
+ d2 = dotprod64(b2x, px, b2y, py);
+ if ((sign64(d1) > 0 && sign64(d2) > 0) ||
+ (sign64(d1) < 0 && sign64(d2) < 0))
return FALSE;
/*
}
}
-static char *new_game_desc(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params, random_state *rs,
char **aux, int interactive)
{
int n = params->n, i;
return ret;
}
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
{
int a, b;
state->completed = TRUE;
}
-static game_state *new_game(midend_data *me, game_params *params, char *desc)
+static game_state *new_game(midend *me, const game_params *params,
+ const char *desc)
{
int n = params->n;
game_state *state = snew(game_state);
state->graph = snew(struct graph);
state->graph->refcount = 1;
state->graph->edges = newtree234(edgecmp);
- state->cheated = state->just_solved = FALSE;
+ state->completed = state->cheated = state->just_solved = FALSE;
while (*desc) {
a = atoi(desc);
#ifdef SHOW_CROSSINGS
state->crosses = snewn(count234(state->graph->edges), int);
-#endif
mark_crossings(state); /* sets up `crosses' and `completed' */
+#endif
return state;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
int n = state->params.n;
game_state *ret = snew(game_state);
sfree(state);
}
-static char *solve_game(game_state *state, game_state *currstate,
- char *aux, char **error)
+static char *solve_game(const game_state *state, const game_state *currstate,
+ const char *aux, char **error)
{
int n = state->params.n;
int matrix[4];
pts[i].d = 2;
ox *= pts[i].d;
oy *= pts[i].d;
- pts[i].x = ox + 0.5;
- pts[i].y = oy + 0.5;
+ pts[i].x = (long)(ox + 0.5F);
+ pts[i].y = (long)(oy + 0.5F);
extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i,
pts[i].x, pts[i].y, pts[i].d);
return ret;
}
-static char *game_text_format(game_state *state)
+static int game_can_format_as_text_now(const game_params *params)
+{
+ return TRUE;
+}
+
+static char *game_text_format(const game_state *state)
{
return NULL;
}
float anim_length;
};
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
game_ui *ui = snew(game_ui);
ui->dragpoint = -1;
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
}
-static void game_changed_state(game_ui *ui, game_state *oldstate,
- game_state *newstate)
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+ const game_state *newstate)
{
ui->dragpoint = -1;
ui->just_moved = ui->just_dragged;
struct game_drawstate {
long tilesize;
+ int bg, dragpoint;
+ long *x, *y;
};
-static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
- int x, int y, int button)
+static char *interpret_move(const game_state *state, game_ui *ui,
+ const game_drawstate *ds,
+ int x, int y, int button)
{
int n = state->params.n;
- if (button == LEFT_BUTTON) {
+ if (IS_MOUSE_DOWN(button)) {
int i, best;
long bestd;
return "";
}
- } else if (button == LEFT_DRAG && ui->dragpoint >= 0) {
+ } else if (IS_MOUSE_DRAG(button) && ui->dragpoint >= 0) {
ui->newpoint.x = x;
ui->newpoint.y = y;
ui->newpoint.d = ds->tilesize;
return "";
- } else if (button == LEFT_RELEASE && ui->dragpoint >= 0) {
+ } else if (IS_MOUSE_RELEASE(button) && ui->dragpoint >= 0) {
int p = ui->dragpoint;
char buf[80];
return NULL;
}
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
{
int n = state->params.n;
int p, k;
* Drawing routines.
*/
-static void game_compute_size(game_params *params, int tilesize,
- int *x, int *y)
+static void game_compute_size(const game_params *params, int tilesize,
+ int *x, int *y)
{
*x = *y = COORDLIMIT(params->n) * tilesize;
}
-static void game_set_size(game_drawstate *ds, game_params *params,
- int tilesize)
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ const game_params *params, int tilesize)
{
ds->tilesize = tilesize;
}
-static float *game_colours(frontend *fe, game_state *state, int *ncolours)
+static float *game_colours(frontend *fe, int *ncolours)
{
float *ret = snewn(3 * NCOLOURS, float);
- frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+ /*
+ * COL_BACKGROUND is what we use as the normal background colour.
+ * Unusually, though, it isn't colour #0: COL_SYSBACKGROUND, a bit
+ * darker, takes that place. This means that if the user resizes
+ * an Untangle window so as to change its aspect ratio, the
+ * still-square playable area will be distinguished from the dead
+ * space around it.
+ */
+ game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_SYSBACKGROUND);
ret[COL_LINE * 3 + 0] = 0.0F;
ret[COL_LINE * 3 + 1] = 0.0F;
return ret;
}
-static game_drawstate *game_new_drawstate(game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
struct game_drawstate *ds = snew(struct game_drawstate);
+ int i;
ds->tilesize = 0;
+ ds->x = snewn(state->params.n, long);
+ ds->y = snewn(state->params.n, long);
+ for (i = 0; i < state->params.n; i++)
+ ds->x[i] = ds->y[i] = -1;
+ ds->bg = -1;
+ ds->dragpoint = -1;
return ds;
}
-static void game_free_drawstate(game_drawstate *ds)
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
{
+ sfree(ds->y);
+ sfree(ds->x);
sfree(ds);
}
point ret;
ret.d = a.d * b.d;
- ret.x = a.x * b.d + distance * (b.x * a.d - a.x * b.d);
- ret.y = a.y * b.d + distance * (b.y * a.d - a.y * b.d);
+ ret.x = (long)(a.x * b.d + distance * (b.x * a.d - a.x * b.d));
+ ret.y = (long)(a.y * b.d + distance * (b.y * a.d - a.y * b.d));
return ret;
}
-static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
- float animtime, float flashtime)
+static void game_redraw(drawing *dr, game_drawstate *ds,
+ const game_state *oldstate, const game_state *state,
+ int dir, const game_ui *ui,
+ float animtime, float flashtime)
{
int w, h;
edge *e;
int i, j;
- int bg;
+ int bg, points_moved;
/*
* There's no terribly sensible way to do partial redraws of
else
bg = COL_FLASH2;
+ /*
+ * To prevent excessive spinning on redraw during a completion
+ * flash, we first check to see if _either_ the flash
+ * background colour has changed _or_ at least one point has
+ * moved _or_ a drag has begun or ended, and abandon the redraw
+ * if neither is the case.
+ *
+ * Also in this loop we work out the coordinates of all the
+ * points for this redraw.
+ */
+ points_moved = FALSE;
+ for (i = 0; i < state->params.n; i++) {
+ point p = state->pts[i];
+ long x, y;
+
+ if (ui->dragpoint == i)
+ p = ui->newpoint;
+
+ if (oldstate)
+ p = mix(oldstate->pts[i], p, animtime / ui->anim_length);
+
+ x = p.x * ds->tilesize / p.d;
+ y = p.y * ds->tilesize / p.d;
+
+ if (ds->x[i] != x || ds->y[i] != y)
+ points_moved = TRUE;
+
+ ds->x[i] = x;
+ ds->y[i] = y;
+ }
+
+ if (ds->bg == bg && ds->dragpoint == ui->dragpoint && !points_moved)
+ return; /* nothing to do */
+
+ ds->dragpoint = ui->dragpoint;
+ ds->bg = bg;
+
game_compute_size(&state->params, ds->tilesize, &w, &h);
- draw_rect(fe, 0, 0, w, h, bg);
+ draw_rect(dr, 0, 0, w, h, bg);
/*
* Draw the edges.
*/
for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
- point p1, p2;
- long x1, y1, x2, y2;
-
- p1 = state->pts[e->a];
- p2 = state->pts[e->b];
- if (ui->dragpoint == e->a)
- p1 = ui->newpoint;
- else if (ui->dragpoint == e->b)
- p2 = ui->newpoint;
-
- if (oldstate) {
- p1 = mix(oldstate->pts[e->a], p1, animtime / ui->anim_length);
- p2 = mix(oldstate->pts[e->b], p2, animtime / ui->anim_length);
- }
-
- x1 = p1.x * ds->tilesize / p1.d;
- y1 = p1.y * ds->tilesize / p1.d;
- x2 = p2.x * ds->tilesize / p2.d;
- y2 = p2.y * ds->tilesize / p2.d;
-
- draw_line(fe, x1, y1, x2, y2,
+ draw_line(dr, ds->x[e->a], ds->y[e->a], ds->x[e->b], ds->y[e->b],
#ifdef SHOW_CROSSINGS
(oldstate?oldstate:state)->crosses[i] ?
COL_CROSSEDLINE :
int thisc = (j == 0 ? COL_POINT :
j == 1 ? COL_NEIGHBOUR : COL_DRAGPOINT);
for (i = 0; i < state->params.n; i++) {
- long x, y;
int c;
- point p = state->pts[i];
if (ui->dragpoint == i) {
- p = ui->newpoint;
c = COL_DRAGPOINT;
} else if (ui->dragpoint >= 0 &&
isedge(state->graph->edges, ui->dragpoint, i)) {
c = COL_POINT;
}
- if (oldstate)
- p = mix(oldstate->pts[i], p, animtime / ui->anim_length);
-
if (c == thisc) {
- x = p.x * ds->tilesize / p.d;
- y = p.y * ds->tilesize / p.d;
-
#ifdef VERTEX_NUMBERS
- draw_circle(fe, x, y, DRAG_THRESHOLD, bg, bg);
+ draw_circle(dr, ds->x[i], ds->y[i], DRAG_THRESHOLD, bg, bg);
{
char buf[80];
sprintf(buf, "%d", i);
- draw_text(fe, x, y, FONT_VARIABLE, DRAG_THRESHOLD*3/2,
+ draw_text(dr, ds->x[i], ds->y[i], FONT_VARIABLE,
+ DRAG_THRESHOLD*3/2,
ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf);
}
#else
- draw_circle(fe, x, y, CIRCLE_RADIUS, c, COL_OUTLINE);
+ draw_circle(dr, ds->x[i], ds->y[i], CIRCLE_RADIUS,
+ c, COL_OUTLINE);
#endif
}
}
}
- draw_update(fe, 0, 0, w, h);
+ draw_update(dr, 0, 0, w, h);
}
-static float game_anim_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+static float game_anim_length(const game_state *oldstate,
+ const game_state *newstate, int dir, game_ui *ui)
{
if (ui->just_moved)
return 0.0F;
return ui->anim_length;
}
-static float game_flash_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+static float game_flash_length(const game_state *oldstate,
+ const game_state *newstate, int dir, game_ui *ui)
{
if (!oldstate->completed && newstate->completed &&
!oldstate->cheated && !newstate->cheated)
return 0.0F;
}
-static int game_wants_statusbar(void)
+static int game_status(const game_state *state)
{
- return FALSE;
+ return state->completed ? +1 : 0;
}
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_timing_state(const game_state *state, game_ui *ui)
{
return TRUE;
}
+static void game_print_size(const game_params *params, float *x, float *y)
+{
+}
+
+static void game_print(drawing *dr, const game_state *state, int tilesize)
+{
+}
+
#ifdef COMBINED
#define thegame untangle
#endif
const struct game thegame = {
- "Untangle", "games.untangle",
+ "Untangle", "games.untangle", "untangle",
default_params,
game_fetch_preset,
decode_params,
dup_game,
free_game,
TRUE, solve_game,
- FALSE, game_text_format,
+ FALSE, game_can_format_as_text_now, game_text_format,
new_ui,
free_ui,
encode_ui,
game_redraw,
game_anim_length,
game_flash_length,
- game_wants_statusbar,
+ game_status,
+ FALSE, FALSE, game_print_size, game_print,
+ FALSE, /* wants_statusbar */
FALSE, game_timing_state,
- SOLVE_ANIMATES, /* mouse_priorities */
+ SOLVE_ANIMATES, /* flags */
};
~ian / sgt-puzzles.git / blobdiff