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.30F
35 #define ANIM_TIME 0.13F
36 #define SOLVEANIM_TIME 0.50F
50 typedef struct point
{
52 * Points are stored using rational coordinates, with the same
53 * denominator for both coordinates.
60 * This structure is implicitly associated with a particular
61 * point set, so all it has to do is to store two point
62 * indices. It is required to store them in the order (lower,
63 * higher), i.e. a < b always.
69 int n
; /* number of points */
73 int refcount
; /* for deallocation */
74 tree234
*edges
; /* stores `edge' structures */
79 int w
, h
; /* extent of coordinate system only */
82 int completed
, cheated
, just_solved
;
85 static int edgecmpC(const void *av
, const void *bv
)
87 const edge
*a
= (const edge
*)av
;
88 const edge
*b
= (const edge
*)bv
;
101 static int edgecmp(void *av
, void *bv
) { return edgecmpC(av
, bv
); }
103 static game_params
*default_params(void)
105 game_params
*ret
= snew(game_params
);
112 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
119 case 0: n
= 6; break;
120 case 1: n
= 10; break;
121 case 2: n
= 15; break;
122 case 3: n
= 20; break;
123 case 4: n
= 25; break;
124 default: return FALSE
;
127 sprintf(buf
, "%d points", n
);
130 *params
= ret
= snew(game_params
);
136 static void free_params(game_params
*params
)
141 static game_params
*dup_params(game_params
*params
)
143 game_params
*ret
= snew(game_params
);
144 *ret
= *params
; /* structure copy */
148 static void decode_params(game_params
*params
, char const *string
)
150 params
->n
= atoi(string
);
153 static char *encode_params(game_params
*params
, int full
)
157 sprintf(buf
, "%d", params
->n
);
162 static config_item
*game_configure(game_params
*params
)
167 ret
= snewn(3, config_item
);
169 ret
[0].name
= "Number of points";
170 ret
[0].type
= C_STRING
;
171 sprintf(buf
, "%d", params
->n
);
172 ret
[0].sval
= dupstr(buf
);
183 static game_params
*custom_params(config_item
*cfg
)
185 game_params
*ret
= snew(game_params
);
187 ret
->n
= atoi(cfg
[0].sval
);
192 static char *validate_params(game_params
*params
, int full
)
195 return "Number of points must be at least four";
200 * Determine whether the line segments between a1 and a2, and
201 * between b1 and b2, intersect. We count it as an intersection if
202 * any of the endpoints lies _on_ the other line.
204 static int cross(point a1
, point a2
, point b1
, point b2
)
206 long b1x
, b1y
, b2x
, b2y
, px
, py
, d1
, d2
, d3
;
209 * The condition for crossing is that b1 and b2 are on opposite
210 * sides of the line a1-a2, and vice versa. We determine this
211 * by taking the dot product of b1-a1 with a vector
212 * perpendicular to a2-a1, and similarly with b2-a1, and seeing
213 * if they have different signs.
217 * Construct the vector b1-a1. We don't have to worry too much
218 * about the denominator, because we're only going to check the
219 * sign of this vector; we just need to get the numerator
222 b1x
= b1
.x
* a1
.d
- a1
.x
* b1
.d
;
223 b1y
= b1
.y
* a1
.d
- a1
.y
* b1
.d
;
224 /* Now construct b2-a1, and a vector perpendicular to a2-a1,
225 * in the same way. */
226 b2x
= b2
.x
* a1
.d
- a1
.x
* b2
.d
;
227 b2y
= b2
.y
* a1
.d
- a1
.y
* b2
.d
;
228 px
= a1
.y
* a2
.d
- a2
.y
* a1
.d
;
229 py
= a2
.x
* a1
.d
- a1
.x
* a2
.d
;
230 /* Take the dot products. */
231 d1
= b1x
* px
+ b1y
* py
;
232 d2
= b2x
* px
+ b2y
* py
;
233 /* If they have the same non-zero sign, the lines do not cross. */
234 if ((d1
> 0 && d2
> 0) || (d1
< 0 && d2
< 0))
238 * If the dot products are both exactly zero, then the two line
239 * segments are collinear. At this point the intersection
240 * condition becomes whether or not they overlap within their
243 if (d1
== 0 && d2
== 0) {
244 /* Construct the vector a2-a1. */
245 px
= a2
.x
* a1
.d
- a1
.x
* a2
.d
;
246 py
= a2
.y
* a1
.d
- a1
.y
* a2
.d
;
247 /* Determine the dot products of b1-a1 and b2-a1 with this. */
248 d1
= b1x
* px
+ b1y
* py
;
249 d2
= b2x
* px
+ b2y
* py
;
250 /* If they're both strictly negative, the lines do not cross. */
251 if (d1
< 0 && d2
< 0)
253 /* Otherwise, take the dot product of a2-a1 with itself. If
254 * the other two dot products both exceed this, the lines do
256 d3
= px
* px
+ py
* py
;
257 if (d1
> d3
&& d2
> d3
)
262 * We've eliminated the only important special case, and we
263 * have determined that b1 and b2 are on opposite sides of the
264 * line a1-a2. Now do the same thing the other way round and
267 b1x
= a1
.x
* b1
.d
- b1
.x
* a1
.d
;
268 b1y
= a1
.y
* b1
.d
- b1
.y
* a1
.d
;
269 b2x
= a2
.x
* b1
.d
- b1
.x
* a2
.d
;
270 b2y
= a2
.y
* b1
.d
- b1
.y
* a2
.d
;
271 px
= b1
.y
* b2
.d
- b2
.y
* b1
.d
;
272 py
= b2
.x
* b1
.d
- b1
.x
* b2
.d
;
273 d1
= b1x
* px
+ b1y
* py
;
274 d2
= b2x
* px
+ b2y
* py
;
275 if ((d1
> 0 && d2
> 0) || (d1
< 0 && d2
< 0))
279 * The lines must cross.
284 static unsigned long squarert(unsigned long n
) {
285 unsigned long d
, a
, b
, di
;
289 b
= 1L << 30; /* largest available power of 4 */
304 * Our solutions are arranged on a square grid big enough that n
305 * points occupy about 1/POINTDENSITY of the grid.
307 #define POINTDENSITY 3
309 #define COORDLIMIT(n) squarert((n) * POINTDENSITY)
311 static void addedge(tree234
*edges
, int a
, int b
)
313 edge
*e
= snew(edge
);
323 static int isedge(tree234
*edges
, int a
, int b
)
332 return find234(edges
, &e
, NULL
) != NULL
;
335 typedef struct vertex
{
340 static int vertcmpC(const void *av
, const void *bv
)
342 const vertex
*a
= (vertex
*)av
;
343 const vertex
*b
= (vertex
*)bv
;
345 if (a
->param
< b
->param
)
347 else if (a
->param
> b
->param
)
349 else if (a
->vindex
< b
->vindex
)
351 else if (a
->vindex
> b
->vindex
)
355 static int vertcmp(void *av
, void *bv
) { return vertcmpC(av
, bv
); }
358 * Construct point coordinates for n points arranged in a circle,
359 * within the bounding box (0,0) to (w,w).
361 static void make_circle(point
*pts
, int n
, int w
)
366 * First, decide on a denominator. Although in principle it
367 * would be nice to set this really high so as to finely
368 * distinguish all the points on the circle, I'm going to set
369 * it at a fixed size to prevent integer overflow problems.
371 d
= PREFERRED_TILESIZE
;
374 * Leave a little space outside the circle.
382 for (i
= 0; i
< n
; i
++) {
383 double angle
= i
* 2 * PI
/ n
;
384 double x
= r
* sin(angle
), y
= - r
* cos(angle
);
385 pts
[i
].x
= (long)(c
+ x
+ 0.5);
386 pts
[i
].y
= (long)(c
+ y
+ 0.5);
391 static char *new_game_desc(game_params
*params
, random_state
*rs
,
392 char **aux
, int interactive
)
394 int n
= params
->n
, i
;
398 tree234
*edges
, *vertices
;
400 vertex
*v
, *vs
, *vlist
;
403 w
= h
= COORDLIMIT(n
);
406 * Choose n points from this grid.
408 pts
= snewn(n
, point
);
409 tmp
= snewn(w
*h
, long);
410 for (i
= 0; i
< w
*h
; i
++)
412 shuffle(tmp
, w
*h
, sizeof(*tmp
), rs
);
413 for (i
= 0; i
< n
; i
++) {
414 pts
[i
].x
= tmp
[i
] % w
;
415 pts
[i
].y
= tmp
[i
] / w
;
421 * Now start adding edges between the points.
423 * At all times, we attempt to add an edge to the lowest-degree
424 * vertex we currently have, and we try the other vertices as
425 * candidate second endpoints in order of distance from this
426 * one. We stop as soon as we find an edge which
428 * (a) does not increase any vertex's degree beyond MAXDEGREE
429 * (b) does not cross any existing edges
430 * (c) does not intersect any actual point.
432 vs
= snewn(n
, vertex
);
433 vertices
= newtree234(vertcmp
);
434 for (i
= 0; i
< n
; i
++) {
436 v
->param
= 0; /* in this tree, param is the degree */
440 edges
= newtree234(edgecmp
);
441 vlist
= snewn(n
, vertex
);
445 for (i
= 0; i
< n
; i
++) {
446 v
= index234(vertices
, i
);
449 if (v
->param
>= MAXDEGREE
)
450 break; /* nothing left to add! */
453 * Sort the other vertices into order of their distance
454 * from this one. Don't bother looking below i, because
455 * we've already tried those edges the other way round.
456 * Also here we rule out target vertices with too high
457 * a degree, and (of course) ones to which we already
461 for (k
= i
+1; k
< n
; k
++) {
462 vertex
*kv
= index234(vertices
, k
);
466 if (kv
->param
>= MAXDEGREE
|| isedge(edges
, ki
, j
))
469 vlist
[m
].vindex
= ki
;
470 dx
= pts
[ki
].x
- pts
[j
].x
;
471 dy
= pts
[ki
].y
- pts
[j
].y
;
472 vlist
[m
].param
= dx
*dx
+ dy
*dy
;
476 qsort(vlist
, m
, sizeof(*vlist
), vertcmpC
);
478 for (k
= 0; k
< m
; k
++) {
480 int ki
= vlist
[k
].vindex
;
483 * Check to see whether this edge intersects any
484 * existing edge or point.
486 for (p
= 0; p
< n
; p
++)
487 if (p
!= ki
&& p
!= j
&& cross(pts
[ki
], pts
[j
],
492 for (p
= 0; (e
= index234(edges
, p
)) != NULL
; p
++)
493 if (e
->a
!= ki
&& e
->a
!= j
&&
494 e
->b
!= ki
&& e
->b
!= j
&&
495 cross(pts
[ki
], pts
[j
], pts
[e
->a
], pts
[e
->b
]))
501 * We're done! Add this edge, modify the degrees of
502 * the two vertices involved, and break.
504 addedge(edges
, j
, ki
);
506 del234(vertices
, vs
+j
);
508 add234(vertices
, vs
+j
);
509 del234(vertices
, vs
+ki
);
511 add234(vertices
, vs
+ki
);
520 break; /* we're done. */
524 * That's our graph. Now shuffle the points, making sure that
525 * they come out with at least one crossed line when arranged
526 * in a circle (so that the puzzle isn't immediately solved!).
528 tmp
= snewn(n
, long);
529 for (i
= 0; i
< n
; i
++)
531 pts2
= snewn(n
, point
);
532 make_circle(pts2
, n
, w
);
534 shuffle(tmp
, n
, sizeof(*tmp
), rs
);
535 for (i
= 0; (e
= index234(edges
, i
)) != NULL
; i
++) {
536 for (j
= i
+1; (e2
= index234(edges
, j
)) != NULL
; j
++) {
537 if (e2
->a
== e
->a
|| e2
->a
== e
->b
||
538 e2
->b
== e
->a
|| e2
->b
== e
->b
)
540 if (cross(pts2
[tmp
[e2
->a
]], pts2
[tmp
[e2
->b
]],
541 pts2
[tmp
[e
->a
]], pts2
[tmp
[e
->b
]]))
548 break; /* we've found a crossing */
552 * We're done. Now encode the graph in a string format. Let's
553 * use a comma-separated list of dash-separated vertex number
554 * pairs, numbered from zero. We'll sort the list to prevent
567 for (i
= 0; (e
= index234(edges
, i
)) != NULL
; i
++) {
569 ea
[i
].a
= min(tmp
[e
->a
], tmp
[e
->b
]);
570 ea
[i
].b
= max(tmp
[e
->a
], tmp
[e
->b
]);
571 retlen
+= 1 + sprintf(buf
, "%d-%d", ea
[i
].a
, ea
[i
].b
);
574 qsort(ea
, m
, sizeof(*ea
), edgecmpC
);
576 ret
= snewn(retlen
, char);
580 for (i
= 0; i
< m
; i
++) {
581 k
+= sprintf(ret
+ k
, "%s%d-%d", sep
, ea
[i
].a
, ea
[i
].b
);
590 * Encode the solution we started with as an aux_info string.
597 auxlen
= 2; /* leading 'S' and trailing '\0' */
598 for (i
= 0; i
< n
; i
++) {
606 pts2
[j
].x
+= pts2
[j
].d
/ 2;
607 pts2
[j
].y
+= pts2
[j
].d
/ 2;
608 auxlen
+= sprintf(buf
, ";P%d:%ld,%ld/%ld", i
,
609 pts2
[j
].x
, pts2
[j
].y
, pts2
[j
].d
);
612 auxstr
= snewn(auxlen
, char);
614 for (i
= 0; i
< n
; i
++)
615 k
+= sprintf(auxstr
+k
, ";P%d:%ld,%ld/%ld", i
,
616 pts2
[i
].x
, pts2
[i
].y
, pts2
[i
].d
);
624 freetree234(vertices
);
626 while ((e
= delpos234(edges
, 0)) != NULL
)
634 static char *validate_desc(game_params
*params
, char *desc
)
640 if (a
< 0 || a
>= params
->n
)
641 return "Number out of range in game description";
642 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
644 return "Expected '-' after number in game description";
645 desc
++; /* eat dash */
647 if (b
< 0 || b
>= params
->n
)
648 return "Number out of range in game description";
649 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
652 return "Expected ',' after number in game description";
653 desc
++; /* eat comma */
660 static game_state
*new_game(midend_data
*me
, game_params
*params
, char *desc
)
663 game_state
*state
= snew(game_state
);
666 state
->params
= *params
;
667 state
->w
= state
->h
= COORDLIMIT(n
);
668 state
->pts
= snewn(n
, point
);
669 make_circle(state
->pts
, n
, state
->w
);
670 state
->graph
= snew(struct graph
);
671 state
->graph
->refcount
= 1;
672 state
->graph
->edges
= newtree234(edgecmp
);
673 state
->completed
= state
->cheated
= state
->just_solved
= FALSE
;
677 assert(a
>= 0 && a
< params
->n
);
678 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
679 assert(*desc
== '-');
680 desc
++; /* eat dash */
682 assert(b
>= 0 && b
< params
->n
);
683 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
685 assert(*desc
== ',');
686 desc
++; /* eat comma */
688 addedge(state
->graph
->edges
, a
, b
);
694 static game_state
*dup_game(game_state
*state
)
696 int n
= state
->params
.n
;
697 game_state
*ret
= snew(game_state
);
699 ret
->params
= state
->params
;
702 ret
->pts
= snewn(n
, point
);
703 memcpy(ret
->pts
, state
->pts
, n
* sizeof(point
));
704 ret
->graph
= state
->graph
;
705 ret
->graph
->refcount
++;
706 ret
->completed
= state
->completed
;
707 ret
->cheated
= state
->cheated
;
708 ret
->just_solved
= state
->just_solved
;
713 static void free_game(game_state
*state
)
715 if (--state
->graph
->refcount
<= 0) {
717 while ((e
= delpos234(state
->graph
->edges
, 0)) != NULL
)
719 freetree234(state
->graph
->edges
);
726 static char *solve_game(game_state
*state
, game_state
*currstate
,
727 char *aux
, char **error
)
729 int n
= state
->params
.n
;
738 *error
= "Solution not known for this puzzle";
743 * Decode the aux_info to get the original point positions.
745 pts
= snewn(n
, point
);
747 for (i
= 0; i
< n
; i
++) {
750 int ret
= sscanf(aux
, ";P%d:%ld,%ld/%ld%n", &p
, &x
, &y
, &d
, &k
);
751 if (ret
!= 4 || p
!= i
) {
752 *error
= "Internal error: aux_info badly formatted";
763 * Now go through eight possible symmetries of the point set.
764 * For each one, work out the sum of the Euclidean distances
765 * between the points' current positions and their new ones.
767 * We're squaring distances here, which means we're at risk of
768 * integer overflow. Fortunately, there's no real need to be
769 * massively careful about rounding errors, since this is a
770 * non-essential bit of the code; so I'll just work in floats
776 for (i
= 0; i
< 8; i
++) {
779 matrix
[0] = matrix
[1] = matrix
[2] = matrix
[3] = 0;
780 matrix
[i
& 1] = (i
& 2) ?
+1 : -1;
781 matrix
[3-(i
&1)] = (i
& 4) ?
+1 : -1;
784 for (j
= 0; j
< n
; j
++) {
785 float px
= (float)pts
[j
].x
/ pts
[j
].d
;
786 float py
= (float)pts
[j
].y
/ pts
[j
].d
;
787 float sx
= (float)currstate
->pts
[j
].x
/ currstate
->pts
[j
].d
;
788 float sy
= (float)currstate
->pts
[j
].y
/ currstate
->pts
[j
].d
;
789 float cx
= (float)currstate
->w
/ 2;
790 float cy
= (float)currstate
->h
/ 2;
791 float ox
, oy
, dx
, dy
;
796 ox
= matrix
[0] * px
+ matrix
[1] * py
;
797 oy
= matrix
[2] * px
+ matrix
[3] * py
;
808 if (besti
< 0 || bestd
> d
) {
817 * Now we know which symmetry is closest to the points' current
820 matrix
[0] = matrix
[1] = matrix
[2] = matrix
[3] = 0;
821 matrix
[besti
& 1] = (besti
& 2) ?
+1 : -1;
822 matrix
[3-(besti
&1)] = (besti
& 4) ?
+1 : -1;
825 ret
= snewn(retsize
, char);
830 for (i
= 0; i
< n
; i
++) {
831 float px
= (float)pts
[i
].x
/ pts
[i
].d
;
832 float py
= (float)pts
[i
].y
/ pts
[i
].d
;
833 float cx
= (float)currstate
->w
/ 2;
834 float cy
= (float)currstate
->h
/ 2;
841 ox
= matrix
[0] * px
+ matrix
[1] * py
;
842 oy
= matrix
[2] * px
+ matrix
[3] * py
;
848 * Use a fixed denominator of 2, because we know the
849 * original points were on an integer grid offset by 1/2.
857 extra
= sprintf(buf
, ";P%d:%ld,%ld/%ld", i
,
858 pts
[i
].x
, pts
[i
].y
, pts
[i
].d
);
859 if (retlen
+ extra
>= retsize
) {
860 retsize
= retlen
+ extra
+ 256;
861 ret
= sresize(ret
, retsize
, char);
863 strcpy(ret
+ retlen
, buf
);
872 static char *game_text_format(game_state
*state
)
878 int dragpoint
; /* point being dragged; -1 if none */
879 point newpoint
; /* where it's been dragged to so far */
880 int just_dragged
; /* reset in game_changed_state */
881 int just_moved
; /* _set_ in game_changed_state */
885 static game_ui
*new_ui(game_state
*state
)
887 game_ui
*ui
= snew(game_ui
);
889 ui
->just_moved
= ui
->just_dragged
= FALSE
;
893 static void free_ui(game_ui
*ui
)
898 static char *encode_ui(game_ui
*ui
)
903 static void decode_ui(game_ui
*ui
, char *encoding
)
907 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
908 game_state
*newstate
)
911 ui
->just_moved
= ui
->just_dragged
;
912 ui
->just_dragged
= FALSE
;
915 struct game_drawstate
{
919 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
920 int x
, int y
, int button
)
922 int n
= state
->params
.n
;
924 if (button
== LEFT_BUTTON
) {
929 * Begin drag. We drag the vertex _nearest_ to the pointer,
930 * just in case one is nearly on top of another and we want
931 * to drag the latter. However, we drag nothing at all if
932 * the nearest vertex is outside DRAG_THRESHOLD.
937 for (i
= 0; i
< n
; i
++) {
938 long px
= state
->pts
[i
].x
* ds
->tilesize
/ state
->pts
[i
].d
;
939 long py
= state
->pts
[i
].y
* ds
->tilesize
/ state
->pts
[i
].d
;
942 long d
= dx
*dx
+ dy
*dy
;
944 if (best
== -1 || bestd
> d
) {
950 if (bestd
<= DRAG_THRESHOLD
* DRAG_THRESHOLD
) {
951 ui
->dragpoint
= best
;
954 ui
->newpoint
.d
= ds
->tilesize
;
958 } else if (button
== LEFT_DRAG
&& ui
->dragpoint
>= 0) {
961 ui
->newpoint
.d
= ds
->tilesize
;
963 } else if (button
== LEFT_RELEASE
&& ui
->dragpoint
>= 0) {
964 int p
= ui
->dragpoint
;
967 ui
->dragpoint
= -1; /* terminate drag, no matter what */
970 * First, see if we're within range. The user can cancel a
971 * drag by dragging the point right off the window.
973 if (ui
->newpoint
.x
< 0 ||
974 ui
->newpoint
.x
>= (long)state
->w
*ui
->newpoint
.d
||
975 ui
->newpoint
.y
< 0 ||
976 ui
->newpoint
.y
>= (long)state
->h
*ui
->newpoint
.d
)
980 * We aren't cancelling the drag. Construct a move string
981 * indicating where this point is going to.
983 sprintf(buf
, "P%d:%ld,%ld/%ld", p
,
984 ui
->newpoint
.x
, ui
->newpoint
.y
, ui
->newpoint
.d
);
985 ui
->just_dragged
= TRUE
;
992 static game_state
*execute_move(game_state
*state
, char *move
)
994 int n
= state
->params
.n
;
997 game_state
*ret
= dup_game(state
);
999 ret
->just_solved
= FALSE
;
1004 if (*move
== ';') move
++;
1005 ret
->cheated
= ret
->just_solved
= TRUE
;
1008 sscanf(move
+1, "%d:%ld,%ld/%ld%n", &p
, &x
, &y
, &d
, &k
) == 4 &&
1009 p
>= 0 && p
< n
&& d
> 0) {
1015 if (*move
== ';') move
++;
1023 * Check correctness: for every pair of edges, see whether they
1026 if (!ret
->completed
) {
1030 for (i
= 0; (e
= index234(ret
->graph
->edges
, i
)) != NULL
; i
++) {
1031 for (j
= i
+1; (e2
= index234(ret
->graph
->edges
, j
)) != NULL
; j
++) {
1032 if (e2
->a
== e
->a
|| e2
->a
== e
->b
||
1033 e2
->b
== e
->a
|| e2
->b
== e
->b
)
1035 if (cross(ret
->pts
[e2
->a
], ret
->pts
[e2
->b
],
1036 ret
->pts
[e
->a
], ret
->pts
[e
->b
]))
1044 * e == NULL if we've gone through all the edge pairs
1045 * without finding a crossing.
1047 ret
->completed
= (e
== NULL
);
1053 /* ----------------------------------------------------------------------
1057 static void game_compute_size(game_params
*params
, int tilesize
,
1060 *x
= *y
= COORDLIMIT(params
->n
) * tilesize
;
1063 static void game_set_size(game_drawstate
*ds
, game_params
*params
,
1066 ds
->tilesize
= tilesize
;
1069 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
1071 float *ret
= snewn(3 * NCOLOURS
, float);
1073 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1075 ret
[COL_LINE
* 3 + 0] = 0.0F
;
1076 ret
[COL_LINE
* 3 + 1] = 0.0F
;
1077 ret
[COL_LINE
* 3 + 2] = 0.0F
;
1079 ret
[COL_OUTLINE
* 3 + 0] = 0.0F
;
1080 ret
[COL_OUTLINE
* 3 + 1] = 0.0F
;
1081 ret
[COL_OUTLINE
* 3 + 2] = 0.0F
;
1083 ret
[COL_POINT
* 3 + 0] = 0.0F
;
1084 ret
[COL_POINT
* 3 + 1] = 0.0F
;
1085 ret
[COL_POINT
* 3 + 2] = 1.0F
;
1087 ret
[COL_DRAGPOINT
* 3 + 0] = 1.0F
;
1088 ret
[COL_DRAGPOINT
* 3 + 1] = 1.0F
;
1089 ret
[COL_DRAGPOINT
* 3 + 2] = 1.0F
;
1091 ret
[COL_NEIGHBOUR
* 3 + 0] = 1.0F
;
1092 ret
[COL_NEIGHBOUR
* 3 + 1] = 0.0F
;
1093 ret
[COL_NEIGHBOUR
* 3 + 2] = 0.0F
;
1095 ret
[COL_FLASH1
* 3 + 0] = 0.5F
;
1096 ret
[COL_FLASH1
* 3 + 1] = 0.5F
;
1097 ret
[COL_FLASH1
* 3 + 2] = 0.5F
;
1099 ret
[COL_FLASH2
* 3 + 0] = 1.0F
;
1100 ret
[COL_FLASH2
* 3 + 1] = 1.0F
;
1101 ret
[COL_FLASH2
* 3 + 2] = 1.0F
;
1103 *ncolours
= NCOLOURS
;
1107 static game_drawstate
*game_new_drawstate(game_state
*state
)
1109 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1116 static void game_free_drawstate(game_drawstate
*ds
)
1121 static point
mix(point a
, point b
, float distance
)
1126 ret
.x
= a
.x
* b
.d
+ distance
* (b
.x
* a
.d
- a
.x
* b
.d
);
1127 ret
.y
= a
.y
* b
.d
+ distance
* (b
.y
* a
.d
- a
.y
* b
.d
);
1132 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
1133 game_state
*state
, int dir
, game_ui
*ui
,
1134 float animtime
, float flashtime
)
1142 * There's no terribly sensible way to do partial redraws of
1143 * this game, so I'm going to have to resort to redrawing the
1144 * whole thing every time.
1148 bg
= COL_BACKGROUND
;
1149 else if ((int)(flashtime
* 4 / FLASH_TIME
) % 2 == 0)
1154 game_compute_size(&state
->params
, ds
->tilesize
, &w
, &h
);
1155 draw_rect(fe
, 0, 0, w
, h
, bg
);
1161 for (i
= 0; (e
= index234(state
->graph
->edges
, i
)) != NULL
; i
++) {
1163 long x1
, y1
, x2
, y2
;
1165 p1
= state
->pts
[e
->a
];
1166 p2
= state
->pts
[e
->b
];
1167 if (ui
->dragpoint
== e
->a
)
1169 else if (ui
->dragpoint
== e
->b
)
1173 p1
= mix(oldstate
->pts
[e
->a
], p1
, animtime
/ ui
->anim_length
);
1174 p2
= mix(oldstate
->pts
[e
->b
], p2
, animtime
/ ui
->anim_length
);
1177 x1
= p1
.x
* ds
->tilesize
/ p1
.d
;
1178 y1
= p1
.y
* ds
->tilesize
/ p1
.d
;
1179 x2
= p2
.x
* ds
->tilesize
/ p2
.d
;
1180 y2
= p2
.y
* ds
->tilesize
/ p2
.d
;
1182 draw_line(fe
, x1
, y1
, x2
, y2
, COL_LINE
);
1188 * When dragging, we should not only vary the colours, but
1189 * leave the point being dragged until last.
1191 for (j
= 0; j
< 3; j
++) {
1192 int thisc
= (j
== 0 ? COL_POINT
:
1193 j
== 1 ? COL_NEIGHBOUR
: COL_DRAGPOINT
);
1194 for (i
= 0; i
< state
->params
.n
; i
++) {
1197 point p
= state
->pts
[i
];
1199 if (ui
->dragpoint
== i
) {
1202 } else if (ui
->dragpoint
>= 0 &&
1203 isedge(state
->graph
->edges
, ui
->dragpoint
, i
)) {
1210 p
= mix(oldstate
->pts
[i
], p
, animtime
/ ui
->anim_length
);
1213 x
= p
.x
* ds
->tilesize
/ p
.d
;
1214 y
= p
.y
* ds
->tilesize
/ p
.d
;
1216 #ifdef VERTEX_NUMBERS
1217 draw_circle(fe
, x
, y
, DRAG_THRESHOLD
, bg
, bg
);
1220 sprintf(buf
, "%d", i
);
1221 draw_text(fe
, x
, y
, FONT_VARIABLE
, DRAG_THRESHOLD
*3/2,
1222 ALIGN_VCENTRE
|ALIGN_HCENTRE
, c
, buf
);
1225 draw_circle(fe
, x
, y
, CIRCLE_RADIUS
, c
, COL_OUTLINE
);
1231 draw_update(fe
, 0, 0, w
, h
);
1234 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1235 int dir
, game_ui
*ui
)
1239 if ((dir
< 0 ? oldstate
: newstate
)->just_solved
)
1240 ui
->anim_length
= SOLVEANIM_TIME
;
1242 ui
->anim_length
= ANIM_TIME
;
1243 return ui
->anim_length
;
1246 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1247 int dir
, game_ui
*ui
)
1249 if (!oldstate
->completed
&& newstate
->completed
&&
1250 !oldstate
->cheated
&& !newstate
->cheated
)
1255 static int game_wants_statusbar(void)
1260 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1266 #define thegame untangle
1269 const struct game thegame
= {
1270 "Untangle", "games.untangle",
1277 TRUE
, game_configure
, custom_params
,
1285 FALSE
, game_text_format
,
1293 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
1296 game_free_drawstate
,
1300 game_wants_statusbar
,
1301 FALSE
, game_timing_state
,
1302 SOLVE_ANIMATES
, /* mouse_priorities */