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 long 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
= (long)(c
+ x
+ 0.5);
384 pts
[i
].y
= (long)(c
+ y
+ 0.5);
389 static char *new_game_desc(game_params
*params
, random_state
*rs
,
390 char **aux
, int interactive
)
392 int n
= params
->n
, i
;
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
, long);
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!).
526 tmp
= snewn(n
, long);
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:%ld,%ld/%ld", 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:%ld,%ld/%ld", 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
) {
792 * Begin drag. We drag the vertex _nearest_ to the pointer,
793 * just in case one is nearly on top of another and we want
794 * to drag the latter. However, we drag nothing at all if
795 * the nearest vertex is outside DRAG_THRESHOLD.
800 for (i
= 0; i
< n
; i
++) {
801 long px
= state
->pts
[i
].x
* ds
->tilesize
/ state
->pts
[i
].d
;
802 long py
= state
->pts
[i
].y
* ds
->tilesize
/ state
->pts
[i
].d
;
805 long d
= dx
*dx
+ dy
*dy
;
807 if (best
== -1 || bestd
> d
) {
813 if (bestd
<= DRAG_THRESHOLD
* DRAG_THRESHOLD
) {
814 ui
->dragpoint
= best
;
817 ui
->newpoint
.d
= ds
->tilesize
;
821 } else if (button
== LEFT_DRAG
&& ui
->dragpoint
>= 0) {
824 ui
->newpoint
.d
= ds
->tilesize
;
826 } else if (button
== LEFT_RELEASE
&& ui
->dragpoint
>= 0) {
827 int p
= ui
->dragpoint
;
830 ui
->dragpoint
= -1; /* terminate drag, no matter what */
833 * First, see if we're within range. The user can cancel a
834 * drag by dragging the point right off the window.
836 if (ui
->newpoint
.x
< 0 ||
837 ui
->newpoint
.x
>= (long)state
->w
*ui
->newpoint
.d
||
838 ui
->newpoint
.y
< 0 ||
839 ui
->newpoint
.y
>= (long)state
->h
*ui
->newpoint
.d
)
843 * We aren't cancelling the drag. Construct a move string
844 * indicating where this point is going to.
846 sprintf(buf
, "P%d:%ld,%ld/%ld", p
,
847 ui
->newpoint
.x
, ui
->newpoint
.y
, ui
->newpoint
.d
);
848 ui
->just_dragged
= TRUE
;
855 static game_state
*execute_move(game_state
*state
, char *move
)
857 int n
= state
->params
.n
;
860 game_state
*ret
= dup_game(state
);
862 ret
->just_solved
= FALSE
;
867 if (*move
== ';') move
++;
868 ret
->cheated
= ret
->just_solved
= TRUE
;
871 sscanf(move
+1, "%d:%ld,%ld/%ld%n", &p
, &x
, &y
, &d
, &k
) == 4 &&
872 p
>= 0 && p
< n
&& d
> 0) {
878 if (*move
== ';') move
++;
886 * Check correctness: for every pair of edges, see whether they
889 if (!ret
->completed
) {
893 for (i
= 0; (e
= index234(ret
->graph
->edges
, i
)) != NULL
; i
++) {
894 for (j
= i
+1; (e2
= index234(ret
->graph
->edges
, j
)) != NULL
; j
++) {
895 if (e2
->a
== e
->a
|| e2
->a
== e
->b
||
896 e2
->b
== e
->a
|| e2
->b
== e
->b
)
898 if (cross(ret
->pts
[e2
->a
], ret
->pts
[e2
->b
],
899 ret
->pts
[e
->a
], ret
->pts
[e
->b
]))
907 * e == NULL if we've gone through all the edge pairs
908 * without finding a crossing.
910 ret
->completed
= (e
== NULL
);
916 /* ----------------------------------------------------------------------
920 static void game_compute_size(game_params
*params
, int tilesize
,
923 *x
= *y
= COORDLIMIT(params
->n
) * tilesize
;
926 static void game_set_size(game_drawstate
*ds
, game_params
*params
,
929 ds
->tilesize
= tilesize
;
932 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
934 float *ret
= snewn(3 * NCOLOURS
, float);
936 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
938 ret
[COL_LINE
* 3 + 0] = 0.0F
;
939 ret
[COL_LINE
* 3 + 1] = 0.0F
;
940 ret
[COL_LINE
* 3 + 2] = 0.0F
;
942 ret
[COL_OUTLINE
* 3 + 0] = 0.0F
;
943 ret
[COL_OUTLINE
* 3 + 1] = 0.0F
;
944 ret
[COL_OUTLINE
* 3 + 2] = 0.0F
;
946 ret
[COL_POINT
* 3 + 0] = 0.0F
;
947 ret
[COL_POINT
* 3 + 1] = 0.0F
;
948 ret
[COL_POINT
* 3 + 2] = 1.0F
;
950 ret
[COL_DRAGPOINT
* 3 + 0] = 1.0F
;
951 ret
[COL_DRAGPOINT
* 3 + 1] = 1.0F
;
952 ret
[COL_DRAGPOINT
* 3 + 2] = 1.0F
;
954 ret
[COL_NEIGHBOUR
* 3 + 0] = 1.0F
;
955 ret
[COL_NEIGHBOUR
* 3 + 1] = 0.0F
;
956 ret
[COL_NEIGHBOUR
* 3 + 2] = 0.0F
;
958 *ncolours
= NCOLOURS
;
962 static game_drawstate
*game_new_drawstate(game_state
*state
)
964 struct game_drawstate
*ds
= snew(struct game_drawstate
);
971 static void game_free_drawstate(game_drawstate
*ds
)
976 static point
mix(point a
, point b
, float distance
)
981 ret
.x
= a
.x
* b
.d
+ distance
* (b
.x
* a
.d
- a
.x
* b
.d
);
982 ret
.y
= a
.y
* b
.d
+ distance
* (b
.y
* a
.d
- a
.y
* b
.d
);
987 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
988 game_state
*state
, int dir
, game_ui
*ui
,
989 float animtime
, float flashtime
)
997 * There's no terribly sensible way to do partial redraws of
998 * this game, so I'm going to have to resort to redrawing the
999 * whole thing every time.
1002 bg
= (flashtime
!= 0 ? COL_DRAGPOINT
: COL_BACKGROUND
);
1003 game_compute_size(&state
->params
, ds
->tilesize
, &w
, &h
);
1004 draw_rect(fe
, 0, 0, w
, h
, bg
);
1010 for (i
= 0; (e
= index234(state
->graph
->edges
, i
)) != NULL
; i
++) {
1012 long x1
, y1
, x2
, y2
;
1014 p1
= state
->pts
[e
->a
];
1015 p2
= state
->pts
[e
->b
];
1016 if (ui
->dragpoint
== e
->a
)
1018 else if (ui
->dragpoint
== e
->b
)
1022 p1
= mix(oldstate
->pts
[e
->a
], p1
, animtime
/ ui
->anim_length
);
1023 p2
= mix(oldstate
->pts
[e
->b
], p2
, animtime
/ ui
->anim_length
);
1026 x1
= p1
.x
* ds
->tilesize
/ p1
.d
;
1027 y1
= p1
.y
* ds
->tilesize
/ p1
.d
;
1028 x2
= p2
.x
* ds
->tilesize
/ p2
.d
;
1029 y2
= p2
.y
* ds
->tilesize
/ p2
.d
;
1031 draw_line(fe
, x1
, y1
, x2
, y2
, COL_LINE
);
1037 * When dragging, we should not only vary the colours, but
1038 * leave the point being dragged until last.
1040 for (j
= 0; j
< 3; j
++) {
1041 int thisc
= (j
== 0 ? COL_POINT
:
1042 j
== 1 ? COL_NEIGHBOUR
: COL_DRAGPOINT
);
1043 for (i
= 0; i
< state
->params
.n
; i
++) {
1046 point p
= state
->pts
[i
];
1048 if (ui
->dragpoint
== i
) {
1051 } else if (ui
->dragpoint
>= 0 &&
1052 isedge(state
->graph
->edges
, ui
->dragpoint
, i
)) {
1059 p
= mix(oldstate
->pts
[i
], p
, animtime
/ ui
->anim_length
);
1062 x
= p
.x
* ds
->tilesize
/ p
.d
;
1063 y
= p
.y
* ds
->tilesize
/ p
.d
;
1065 #ifdef VERTEX_NUMBERS
1066 draw_circle(fe
, x
, y
, DRAG_THRESHOLD
, bg
, bg
);
1069 sprintf(buf
, "%d", i
);
1070 draw_text(fe
, x
, y
, FONT_VARIABLE
, DRAG_THRESHOLD
*3/2,
1071 ALIGN_VCENTRE
|ALIGN_HCENTRE
, c
, buf
);
1074 draw_circle(fe
, x
, y
, CIRCLE_RADIUS
, c
, COL_OUTLINE
);
1080 draw_update(fe
, 0, 0, w
, h
);
1083 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1084 int dir
, game_ui
*ui
)
1088 if ((dir
< 0 ? oldstate
: newstate
)->just_solved
)
1089 ui
->anim_length
= SOLVEANIM_TIME
;
1091 ui
->anim_length
= ANIM_TIME
;
1092 return ui
->anim_length
;
1095 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1096 int dir
, game_ui
*ui
)
1098 if (!oldstate
->completed
&& newstate
->completed
&&
1099 !oldstate
->cheated
&& !newstate
->cheated
)
1104 static int game_wants_statusbar(void)
1109 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1115 #define thegame untangle
1118 const struct game thegame
= {
1119 "Untangle", "games.untangle",
1126 TRUE
, game_configure
, custom_params
,
1134 FALSE
, game_text_format
,
1142 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
1145 game_free_drawstate
,
1149 game_wants_statusbar
,
1150 FALSE
, game_timing_state
,
1151 SOLVE_ANIMATES
, /* mouse_priorities */