2 * untangle.c: Game about planar graphs. You are given a graph
3 * represented by points and straight lines, with some lines
4 * crossing; your task is to drag the points into a configuration
5 * where none of the lines cross.
7 * Cloned from a Flash game called `Planarity', by John Tantalo.
8 * <http://home.cwru.edu/~jnt5/Planarity> at the time of writing
9 * this. The Flash game had a fixed set of levels; my added value,
10 * as usual, is automatic generation of random games to order.
16 * - Docs and checklist etc
17 * - Any way we can speed up redraws on GTK? Uck.
30 #define CIRCLE_RADIUS 6
31 #define DRAG_THRESHOLD (CIRCLE_RADIUS * 2)
32 #define PREFERRED_TILESIZE 64
34 #define FLASH_TIME 0.13F
35 #define ANIM_TIME 0.13F
36 #define SOLVEANIM_TIME 0.50F
48 typedef struct point {
50 * Points are stored using rational coordinates, with the same
51 * denominator for both coordinates.
58 * This structure is implicitly associated with a particular
59 * point set, so all it has to do is to store two point
60 * indices. It is required to store them in the order (lower,
61 * higher), i.e. a < b always.
67 int n; /* number of points */
71 int refcount; /* for deallocation */
72 tree234 *edges; /* stores `edge' structures */
77 int w, h; /* extent of coordinate system only */
80 int completed, cheated, just_solved;
83 static int edgecmpC(const void *av, const void *bv)
85 const edge *a = (const edge *)av;
86 const edge *b = (const edge *)bv;
99 static int edgecmp(void *av, void *bv) { return edgecmpC(av, bv); }
101 static game_params *default_params(void)
103 game_params *ret = snew(game_params);
110 static int game_fetch_preset(int i, char **name, game_params **params)
117 case 0: n = 6; break;
118 case 1: n = 10; break;
119 case 2: n = 15; break;
120 case 3: n = 20; break;
121 case 4: n = 25; break;
122 default: return FALSE;
125 sprintf(buf, "%d points", n);
128 *params = ret = snew(game_params);
134 static void free_params(game_params *params)
139 static game_params *dup_params(game_params *params)
141 game_params *ret = snew(game_params);
142 *ret = *params; /* structure copy */
146 static void decode_params(game_params *params, char const *string)
148 params->n = atoi(string);
151 static char *encode_params(game_params *params, int full)
155 sprintf(buf, "%d", params->n);
160 static config_item *game_configure(game_params *params)
165 ret = snewn(3, config_item);
167 ret[0].name = "Number of points";
168 ret[0].type = C_STRING;
169 sprintf(buf, "%d", params->n);
170 ret[0].sval = dupstr(buf);
181 static game_params *custom_params(config_item *cfg)
183 game_params *ret = snew(game_params);
185 ret->n = atoi(cfg[0].sval);
190 static char *validate_params(game_params *params, int full)
193 return "Number of points must be at least four";
198 * Determine whether the line segments between a1 and a2, and
199 * between b1 and b2, intersect. We count it as an intersection if
200 * any of the endpoints lies _on_ the other line.
202 static int cross(point a1, point a2, point b1, point b2)
204 int b1x, b1y, b2x, b2y, px, py, d1, d2, d3;
207 * The condition for crossing is that b1 and b2 are on opposite
208 * sides of the line a1-a2, and vice versa. We determine this
209 * by taking the dot product of b1-a1 with a vector
210 * perpendicular to a2-a1, and similarly with b2-a1, and seeing
211 * if they have different signs.
215 * Construct the vector b1-a1. We don't have to worry too much
216 * about the denominator, because we're only going to check the
217 * sign of this vector; we just need to get the numerator
220 b1x = b1.x * a1.d - a1.x * b1.d;
221 b1y = b1.y * a1.d - a1.y * b1.d;
222 /* Now construct b2-a1, and a vector perpendicular to a2-a1,
223 * in the same way. */
224 b2x = b2.x * a1.d - a1.x * b2.d;
225 b2y = b2.y * a1.d - a1.y * b2.d;
226 px = a1.y * a2.d - a2.y * a1.d;
227 py = a2.x * a1.d - a1.x * a2.d;
228 /* Take the dot products. */
229 d1 = b1x * px + b1y * py;
230 d2 = b2x * px + b2y * py;
231 /* If they have the same non-zero sign, the lines do not cross. */
232 if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0))
236 * If the dot products are both exactly zero, then the two line
237 * segments are collinear. At this point the intersection
238 * condition becomes whether or not they overlap within their
241 if (d1 == 0 && d2 == 0) {
242 /* Construct the vector a2-a1. */
243 px = a2.x * a1.d - a1.x * a2.d;
244 py = a2.y * a1.d - a1.y * a2.d;
245 /* Determine the dot products of b1-a1 and b2-a1 with this. */
246 d1 = b1x * px + b1y * py;
247 d2 = b2x * px + b2y * py;
248 /* If they're both strictly negative, the lines do not cross. */
249 if (d1 < 0 && d2 < 0)
251 /* Otherwise, take the dot product of a2-a1 with itself. If
252 * the other two dot products both exceed this, the lines do
254 d3 = px * px + py * py;
255 if (d1 > d3 && d2 > d3)
260 * We've eliminated the only important special case, and we
261 * have determined that b1 and b2 are on opposite sides of the
262 * line a1-a2. Now do the same thing the other way round and
265 b1x = a1.x * b1.d - b1.x * a1.d;
266 b1y = a1.y * b1.d - b1.y * a1.d;
267 b2x = a2.x * b1.d - b1.x * a2.d;
268 b2y = a2.y * b1.d - b1.y * a2.d;
269 px = b1.y * b2.d - b2.y * b1.d;
270 py = b2.x * b1.d - b1.x * b2.d;
271 d1 = b1x * px + b1y * py;
272 d2 = b2x * px + b2y * py;
273 if ((d1 > 0 && d2 > 0) || (d1 < 0 && d2 < 0))
277 * The lines must cross.
282 static unsigned long squarert(unsigned long n) {
283 unsigned long d, a, b, di;
287 b = 1L << 30; /* largest available power of 4 */
302 * Our solutions are arranged on a square grid big enough that n
303 * points occupy about 1/POINTDENSITY of the grid.
305 #define POINTDENSITY 3
307 #define COORDLIMIT(n) squarert((n) * POINTDENSITY)
309 static void addedge(tree234 *edges, int a, int b)
311 edge *e = snew(edge);
321 static int isedge(tree234 *edges, int a, int b)
330 return find234(edges, &e, NULL) != NULL;
333 typedef struct vertex {
338 static int vertcmpC(const void *av, const void *bv)
340 const vertex *a = (vertex *)av;
341 const vertex *b = (vertex *)bv;
343 if (a->param < b->param)
345 else if (a->param > b->param)
347 else if (a->vindex < b->vindex)
349 else if (a->vindex > b->vindex)
353 static int vertcmp(void *av, void *bv) { return vertcmpC(av, bv); }
356 * Construct point coordinates for n points arranged in a circle,
357 * within the bounding box (0,0) to (w,w).
359 static void make_circle(point *pts, int n, int w)
364 * First, decide on a denominator. Although in principle it
365 * would be nice to set this really high so as to finely
366 * distinguish all the points on the circle, I'm going to set
367 * it at a fixed size to prevent integer overflow problems.
369 d = PREFERRED_TILESIZE;
372 * Leave a little space outside the circle.
380 for (i = 0; i < n; i++) {
381 double angle = i * 2 * PI / n;
382 double x = r * sin(angle), y = - r * cos(angle);
383 pts[i].x = (int)(c + x + 0.5);
384 pts[i].y = (int)(c + y + 0.5);
389 static char *new_game_desc(game_params *params, random_state *rs,
390 char **aux, int interactive)
393 int w, h, i, j, k, m;
396 tree234 *edges, *vertices;
398 vertex *v, *vs, *vlist;
401 w = h = COORDLIMIT(n);
404 * Choose n points from this grid.
406 pts = snewn(n, point);
407 tmp = snewn(w*h, int);
408 for (i = 0; i < w*h; i++)
410 shuffle(tmp, w*h, sizeof(*tmp), rs);
411 for (i = 0; i < n; i++) {
412 pts[i].x = tmp[i] % w;
413 pts[i].y = tmp[i] / w;
419 * Now start adding edges between the points.
421 * At all times, we attempt to add an edge to the lowest-degree
422 * vertex we currently have, and we try the other vertices as
423 * candidate second endpoints in order of distance from this
424 * one. We stop as soon as we find an edge which
426 * (a) does not increase any vertex's degree beyond MAXDEGREE
427 * (b) does not cross any existing edges
428 * (c) does not intersect any actual point.
430 vs = snewn(n, vertex);
431 vertices = newtree234(vertcmp);
432 for (i = 0; i < n; i++) {
434 v->param = 0; /* in this tree, param is the degree */
438 edges = newtree234(edgecmp);
439 vlist = snewn(n, vertex);
443 for (i = 0; i < n; i++) {
444 v = index234(vertices, i);
447 if (v->param >= MAXDEGREE)
448 break; /* nothing left to add! */
451 * Sort the other vertices into order of their distance
452 * from this one. Don't bother looking below i, because
453 * we've already tried those edges the other way round.
454 * Also here we rule out target vertices with too high
455 * a degree, and (of course) ones to which we already
459 for (k = i+1; k < n; k++) {
460 vertex *kv = index234(vertices, k);
464 if (kv->param >= MAXDEGREE || isedge(edges, ki, j))
467 vlist[m].vindex = ki;
468 dx = pts[ki].x - pts[j].x;
469 dy = pts[ki].y - pts[j].y;
470 vlist[m].param = dx*dx + dy*dy;
474 qsort(vlist, m, sizeof(*vlist), vertcmpC);
476 for (k = 0; k < m; k++) {
478 int ki = vlist[k].vindex;
481 * Check to see whether this edge intersects any
482 * existing edge or point.
484 for (p = 0; p < n; p++)
485 if (p != ki && p != j && cross(pts[ki], pts[j],
490 for (p = 0; (e = index234(edges, p)) != NULL; p++)
491 if (e->a != ki && e->a != j &&
492 e->b != ki && e->b != j &&
493 cross(pts[ki], pts[j], pts[e->a], pts[e->b]))
499 * We're done! Add this edge, modify the degrees of
500 * the two vertices involved, and break.
502 addedge(edges, j, ki);
504 del234(vertices, vs+j);
506 add234(vertices, vs+j);
507 del234(vertices, vs+ki);
509 add234(vertices, vs+ki);
518 break; /* we're done. */
522 * That's our graph. Now shuffle the points, making sure that
523 * they come out with at least one crossed line when arranged
524 * in a circle (so that the puzzle isn't immediately solved!).
527 for (i = 0; i < n; i++)
529 pts2 = snewn(n, point);
530 make_circle(pts2, n, w);
532 shuffle(tmp, n, sizeof(*tmp), rs);
533 for (i = 0; (e = index234(edges, i)) != NULL; i++) {
534 for (j = i+1; (e2 = index234(edges, j)) != NULL; j++) {
535 if (e2->a == e->a || e2->a == e->b ||
536 e2->b == e->a || e2->b == e->b)
538 if (cross(pts2[tmp[e2->a]], pts2[tmp[e2->b]],
539 pts2[tmp[e->a]], pts2[tmp[e->b]]))
546 break; /* we've found a crossing */
550 * We're done. Now encode the graph in a string format. Let's
551 * use a comma-separated list of dash-separated vertex number
552 * pairs, numbered from zero. We'll sort the list to prevent
565 for (i = 0; (e = index234(edges, i)) != NULL; i++) {
567 ea[i].a = min(tmp[e->a], tmp[e->b]);
568 ea[i].b = max(tmp[e->a], tmp[e->b]);
569 retlen += 1 + sprintf(buf, "%d-%d", ea[i].a, ea[i].b);
572 qsort(ea, m, sizeof(*ea), edgecmpC);
574 ret = snewn(retlen, char);
578 for (i = 0; i < m; i++) {
579 k += sprintf(ret + k, "%s%d-%d", sep, ea[i].a, ea[i].b);
588 * Encode the solution we started with as an aux_info string.
595 auxlen = 2; /* leading 'S' and trailing '\0' */
596 for (i = 0; i < n; i++) {
604 pts2[j].x += pts2[j].d / 2;
605 pts2[j].y += pts2[j].d / 2;
606 auxlen += sprintf(buf, ";P%d:%d,%d/%d", i,
607 pts2[j].x, pts2[j].y, pts2[j].d);
610 auxstr = snewn(auxlen, char);
612 for (i = 0; i < n; i++)
613 k += sprintf(auxstr+k, ";P%d:%d,%d/%d", i,
614 pts2[i].x, pts2[i].y, pts2[i].d);
622 freetree234(vertices);
624 while ((e = delpos234(edges, 0)) != NULL)
632 static char *validate_desc(game_params *params, char *desc)
638 if (a < 0 || a >= params->n)
639 return "Number out of range in game description";
640 while (*desc && isdigit((unsigned char)*desc)) desc++;
642 return "Expected '-' after number in game description";
643 desc++; /* eat dash */
645 if (b < 0 || b >= params->n)
646 return "Number out of range in game description";
647 while (*desc && isdigit((unsigned char)*desc)) desc++;
650 return "Expected ',' after number in game description";
651 desc++; /* eat comma */
658 static game_state *new_game(midend_data *me, game_params *params, char *desc)
661 game_state *state = snew(game_state);
664 state->params = *params;
665 state->w = state->h = COORDLIMIT(n);
666 state->pts = snewn(n, point);
667 make_circle(state->pts, n, state->w);
668 state->graph = snew(struct graph);
669 state->graph->refcount = 1;
670 state->graph->edges = newtree234(edgecmp);
671 state->completed = state->cheated = state->just_solved = FALSE;
675 assert(a >= 0 && a < params->n);
676 while (*desc && isdigit((unsigned char)*desc)) desc++;
677 assert(*desc == '-');
678 desc++; /* eat dash */
680 assert(b >= 0 && b < params->n);
681 while (*desc && isdigit((unsigned char)*desc)) desc++;
683 assert(*desc == ',');
684 desc++; /* eat comma */
686 addedge(state->graph->edges, a, b);
692 static game_state *dup_game(game_state *state)
694 int n = state->params.n;
695 game_state *ret = snew(game_state);
697 ret->params = state->params;
700 ret->pts = snewn(n, point);
701 memcpy(ret->pts, state->pts, n * sizeof(point));
702 ret->graph = state->graph;
703 ret->graph->refcount++;
704 ret->completed = state->completed;
705 ret->cheated = state->cheated;
706 ret->just_solved = state->just_solved;
711 static void free_game(game_state *state)
713 if (--state->graph->refcount <= 0) {
715 while ((e = delpos234(state->graph->edges, 0)) != NULL)
717 freetree234(state->graph->edges);
724 static char *solve_game(game_state *state, game_state *currstate,
725 char *aux, char **error)
728 *error = "Solution not known for this puzzle";
735 static char *game_text_format(game_state *state)
741 int dragpoint; /* point being dragged; -1 if none */
742 point newpoint; /* where it's been dragged to so far */
743 int just_dragged; /* reset in game_changed_state */
744 int just_moved; /* _set_ in game_changed_state */
748 static game_ui *new_ui(game_state *state)
750 game_ui *ui = snew(game_ui);
752 ui->just_moved = ui->just_dragged = FALSE;
756 static void free_ui(game_ui *ui)
761 static char *encode_ui(game_ui *ui)
766 static void decode_ui(game_ui *ui, char *encoding)
770 static void game_changed_state(game_ui *ui, game_state *oldstate,
771 game_state *newstate)
774 ui->just_moved = ui->just_dragged;
775 ui->just_dragged = FALSE;
778 struct game_drawstate {
782 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
783 int x, int y, int button)
785 int n = state->params.n;
787 if (button == LEFT_BUTTON) {
791 * Begin drag. We drag the vertex _nearest_ to the pointer,
792 * just in case one is nearly on top of another and we want
793 * to drag the latter. However, we drag nothing at all if
794 * the nearest vertex is outside DRAG_THRESHOLD.
799 for (i = 0; i < n; i++) {
800 int px = state->pts[i].x * ds->tilesize / state->pts[i].d;
801 int py = state->pts[i].y * ds->tilesize / state->pts[i].d;
804 int d = dx*dx + dy*dy;
806 if (best == -1 || bestd > d) {
812 if (bestd <= DRAG_THRESHOLD * DRAG_THRESHOLD) {
813 ui->dragpoint = best;
816 ui->newpoint.d = ds->tilesize;
820 } else if (button == LEFT_DRAG && ui->dragpoint >= 0) {
823 ui->newpoint.d = ds->tilesize;
825 } else if (button == LEFT_RELEASE && ui->dragpoint >= 0) {
826 int p = ui->dragpoint;
829 ui->dragpoint = -1; /* terminate drag, no matter what */
832 * First, see if we're within range. The user can cancel a
833 * drag by dragging the point right off the window.
835 if (ui->newpoint.x < 0 || ui->newpoint.x >= state->w*ui->newpoint.d ||
836 ui->newpoint.y < 0 || ui->newpoint.y >= state->h*ui->newpoint.d)
840 * We aren't cancelling the drag. Construct a move string
841 * indicating where this point is going to.
843 sprintf(buf, "P%d:%d,%d/%d", p,
844 ui->newpoint.x, ui->newpoint.y, ui->newpoint.d);
845 ui->just_dragged = TRUE;
852 static game_state *execute_move(game_state *state, char *move)
854 int n = state->params.n;
856 game_state *ret = dup_game(state);
858 ret->just_solved = FALSE;
863 if (*move == ';') move++;
864 ret->cheated = ret->just_solved = TRUE;
867 sscanf(move+1, "%d:%d,%d/%d%n", &p, &x, &y, &d, &k) == 4 &&
868 p >= 0 && p < n && d > 0) {
874 if (*move == ';') move++;
882 * Check correctness: for every pair of edges, see whether they
885 if (!ret->completed) {
889 for (i = 0; (e = index234(ret->graph->edges, i)) != NULL; i++) {
890 for (j = i+1; (e2 = index234(ret->graph->edges, j)) != NULL; j++) {
891 if (e2->a == e->a || e2->a == e->b ||
892 e2->b == e->a || e2->b == e->b)
894 if (cross(ret->pts[e2->a], ret->pts[e2->b],
895 ret->pts[e->a], ret->pts[e->b]))
903 * e == NULL if we've gone through all the edge pairs
904 * without finding a crossing.
906 ret->completed = (e == NULL);
912 /* ----------------------------------------------------------------------
916 static void game_compute_size(game_params *params, int tilesize,
919 *x = *y = COORDLIMIT(params->n) * tilesize;
922 static void game_set_size(game_drawstate *ds, game_params *params,
925 ds->tilesize = tilesize;
928 static float *game_colours(frontend *fe, game_state *state, int *ncolours)
930 float *ret = snewn(3 * NCOLOURS, float);
932 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
934 ret[COL_LINE * 3 + 0] = 0.0F;
935 ret[COL_LINE * 3 + 1] = 0.0F;
936 ret[COL_LINE * 3 + 2] = 0.0F;
938 ret[COL_OUTLINE * 3 + 0] = 0.0F;
939 ret[COL_OUTLINE * 3 + 1] = 0.0F;
940 ret[COL_OUTLINE * 3 + 2] = 0.0F;
942 ret[COL_POINT * 3 + 0] = 0.0F;
943 ret[COL_POINT * 3 + 1] = 0.0F;
944 ret[COL_POINT * 3 + 2] = 1.0F;
946 ret[COL_DRAGPOINT * 3 + 0] = 1.0F;
947 ret[COL_DRAGPOINT * 3 + 1] = 1.0F;
948 ret[COL_DRAGPOINT * 3 + 2] = 1.0F;
950 ret[COL_NEIGHBOUR * 3 + 0] = 1.0F;
951 ret[COL_NEIGHBOUR * 3 + 1] = 0.0F;
952 ret[COL_NEIGHBOUR * 3 + 2] = 0.0F;
954 *ncolours = NCOLOURS;
958 static game_drawstate *game_new_drawstate(game_state *state)
960 struct game_drawstate *ds = snew(struct game_drawstate);
967 static void game_free_drawstate(game_drawstate *ds)
972 static point mix(point a, point b, float distance)
977 ret.x = a.x * b.d + distance * (b.x * a.d - a.x * b.d);
978 ret.y = a.y * b.d + distance * (b.y * a.d - a.y * b.d);
983 static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
984 game_state *state, int dir, game_ui *ui,
985 float animtime, float flashtime)
993 * There's no terribly sensible way to do partial redraws of
994 * this game, so I'm going to have to resort to redrawing the
995 * whole thing every time.
998 bg = (flashtime != 0 ? COL_DRAGPOINT : COL_BACKGROUND);
999 game_compute_size(&state->params, ds->tilesize, &w, &h);
1000 draw_rect(fe, 0, 0, w, h, bg);
1006 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
1010 p1 = state->pts[e->a];
1011 p2 = state->pts[e->b];
1012 if (ui->dragpoint == e->a)
1014 else if (ui->dragpoint == e->b)
1018 p1 = mix(oldstate->pts[e->a], p1, animtime / ui->anim_length);
1019 p2 = mix(oldstate->pts[e->b], p2, animtime / ui->anim_length);
1022 x1 = p1.x * ds->tilesize / p1.d;
1023 y1 = p1.y * ds->tilesize / p1.d;
1024 x2 = p2.x * ds->tilesize / p2.d;
1025 y2 = p2.y * ds->tilesize / p2.d;
1027 draw_line(fe, x1, y1, x2, y2, COL_LINE);
1033 * When dragging, we should not only vary the colours, but
1034 * leave the point being dragged until last.
1036 for (j = 0; j < 3; j++) {
1037 int thisc = (j == 0 ? COL_POINT :
1038 j == 1 ? COL_NEIGHBOUR : COL_DRAGPOINT);
1039 for (i = 0; i < state->params.n; i++) {
1041 point p = state->pts[i];
1043 if (ui->dragpoint == i) {
1046 } else if (ui->dragpoint >= 0 &&
1047 isedge(state->graph->edges, ui->dragpoint, i)) {
1054 p = mix(oldstate->pts[i], p, animtime / ui->anim_length);
1057 x = p.x * ds->tilesize / p.d;
1058 y = p.y * ds->tilesize / p.d;
1060 #ifdef VERTEX_NUMBERS
1061 draw_circle(fe, x, y, DRAG_THRESHOLD, bg, bg);
1064 sprintf(buf, "%d", i);
1065 draw_text(fe, x, y, FONT_VARIABLE, DRAG_THRESHOLD*3/2,
1066 ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf);
1069 draw_circle(fe, x, y, CIRCLE_RADIUS, c, COL_OUTLINE);
1075 draw_update(fe, 0, 0, w, h);
1078 static float game_anim_length(game_state *oldstate, game_state *newstate,
1079 int dir, game_ui *ui)
1083 if ((dir < 0 ? oldstate : newstate)->just_solved)
1084 ui->anim_length = SOLVEANIM_TIME;
1086 ui->anim_length = ANIM_TIME;
1087 return ui->anim_length;
1090 static float game_flash_length(game_state *oldstate, game_state *newstate,
1091 int dir, game_ui *ui)
1093 if (!oldstate->completed && newstate->completed &&
1094 !oldstate->cheated && !newstate->cheated)
1099 static int game_wants_statusbar(void)
1104 static int game_timing_state(game_state *state, game_ui *ui)
1110 #define thegame untangle
1113 const struct game thegame = {
1114 "Untangle", "games.untangle",
1121 TRUE, game_configure, custom_params,
1129 FALSE, game_text_format,
1137 PREFERRED_TILESIZE, game_compute_size, game_set_size,
1140 game_free_drawstate,
1144 game_wants_statusbar,
1145 FALSE, game_timing_state,
1146 SOLVE_ANIMATES, /* mouse_priorities */