6bb010fccd39e58b07309776d0d6ad7bd7828b2d
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
53 typedef struct point
{
55 * Points are stored using rational coordinates, with the same
56 * denominator for both coordinates.
63 * This structure is implicitly associated with a particular
64 * point set, so all it has to do is to store two point
65 * indices. It is required to store them in the order (lower,
66 * higher), i.e. a < b always.
72 int n
; /* number of points */
76 int refcount
; /* for deallocation */
77 tree234
*edges
; /* stores `edge' structures */
82 int w
, h
; /* extent of coordinate system only */
85 int *crosses
; /* mark edges which are crossed */
88 int completed
, cheated
, just_solved
;
91 static int edgecmpC(const void *av
, const void *bv
)
93 const edge
*a
= (const edge
*)av
;
94 const edge
*b
= (const edge
*)bv
;
100 else if (a
->b
< b
->b
)
102 else if (a
->b
> b
->b
)
107 static int edgecmp(void *av
, void *bv
) { return edgecmpC(av
, bv
); }
109 static game_params
*default_params(void)
111 game_params
*ret
= snew(game_params
);
118 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
125 case 0: n
= 6; break;
126 case 1: n
= 10; break;
127 case 2: n
= 15; break;
128 case 3: n
= 20; break;
129 case 4: n
= 25; break;
130 default: return FALSE
;
133 sprintf(buf
, "%d points", n
);
136 *params
= ret
= snew(game_params
);
142 static void free_params(game_params
*params
)
147 static game_params
*dup_params(game_params
*params
)
149 game_params
*ret
= snew(game_params
);
150 *ret
= *params
; /* structure copy */
154 static void decode_params(game_params
*params
, char const *string
)
156 params
->n
= atoi(string
);
159 static char *encode_params(game_params
*params
, int full
)
163 sprintf(buf
, "%d", params
->n
);
168 static config_item
*game_configure(game_params
*params
)
173 ret
= snewn(3, config_item
);
175 ret
[0].name
= "Number of points";
176 ret
[0].type
= C_STRING
;
177 sprintf(buf
, "%d", params
->n
);
178 ret
[0].sval
= dupstr(buf
);
189 static game_params
*custom_params(config_item
*cfg
)
191 game_params
*ret
= snew(game_params
);
193 ret
->n
= atoi(cfg
[0].sval
);
198 static char *validate_params(game_params
*params
, int full
)
201 return "Number of points must be at least four";
206 * Determine whether the line segments between a1 and a2, and
207 * between b1 and b2, intersect. We count it as an intersection if
208 * any of the endpoints lies _on_ the other line.
210 static int cross(point a1
, point a2
, point b1
, point b2
)
212 long b1x
, b1y
, b2x
, b2y
, px
, py
, d1
, d2
, d3
;
215 * The condition for crossing is that b1 and b2 are on opposite
216 * sides of the line a1-a2, and vice versa. We determine this
217 * by taking the dot product of b1-a1 with a vector
218 * perpendicular to a2-a1, and similarly with b2-a1, and seeing
219 * if they have different signs.
223 * Construct the vector b1-a1. We don't have to worry too much
224 * about the denominator, because we're only going to check the
225 * sign of this vector; we just need to get the numerator
228 b1x
= b1
.x
* a1
.d
- a1
.x
* b1
.d
;
229 b1y
= b1
.y
* a1
.d
- a1
.y
* b1
.d
;
230 /* Now construct b2-a1, and a vector perpendicular to a2-a1,
231 * in the same way. */
232 b2x
= b2
.x
* a1
.d
- a1
.x
* b2
.d
;
233 b2y
= b2
.y
* a1
.d
- a1
.y
* b2
.d
;
234 px
= a1
.y
* a2
.d
- a2
.y
* a1
.d
;
235 py
= a2
.x
* a1
.d
- a1
.x
* a2
.d
;
236 /* Take the dot products. */
237 d1
= b1x
* px
+ b1y
* py
;
238 d2
= b2x
* px
+ b2y
* py
;
239 /* If they have the same non-zero sign, the lines do not cross. */
240 if ((d1
> 0 && d2
> 0) || (d1
< 0 && d2
< 0))
244 * If the dot products are both exactly zero, then the two line
245 * segments are collinear. At this point the intersection
246 * condition becomes whether or not they overlap within their
249 if (d1
== 0 && d2
== 0) {
250 /* Construct the vector a2-a1. */
251 px
= a2
.x
* a1
.d
- a1
.x
* a2
.d
;
252 py
= a2
.y
* a1
.d
- a1
.y
* a2
.d
;
253 /* Determine the dot products of b1-a1 and b2-a1 with this. */
254 d1
= b1x
* px
+ b1y
* py
;
255 d2
= b2x
* px
+ b2y
* py
;
256 /* If they're both strictly negative, the lines do not cross. */
257 if (d1
< 0 && d2
< 0)
259 /* Otherwise, take the dot product of a2-a1 with itself. If
260 * the other two dot products both exceed this, the lines do
262 d3
= px
* px
+ py
* py
;
263 if (d1
> d3
&& d2
> d3
)
268 * We've eliminated the only important special case, and we
269 * have determined that b1 and b2 are on opposite sides of the
270 * line a1-a2. Now do the same thing the other way round and
273 b1x
= a1
.x
* b1
.d
- b1
.x
* a1
.d
;
274 b1y
= a1
.y
* b1
.d
- b1
.y
* a1
.d
;
275 b2x
= a2
.x
* b1
.d
- b1
.x
* a2
.d
;
276 b2y
= a2
.y
* b1
.d
- b1
.y
* a2
.d
;
277 px
= b1
.y
* b2
.d
- b2
.y
* b1
.d
;
278 py
= b2
.x
* b1
.d
- b1
.x
* b2
.d
;
279 d1
= b1x
* px
+ b1y
* py
;
280 d2
= b2x
* px
+ b2y
* py
;
281 if ((d1
> 0 && d2
> 0) || (d1
< 0 && d2
< 0))
285 * The lines must cross.
290 static unsigned long squarert(unsigned long n
) {
291 unsigned long d
, a
, b
, di
;
295 b
= 1L << 30; /* largest available power of 4 */
310 * Our solutions are arranged on a square grid big enough that n
311 * points occupy about 1/POINTDENSITY of the grid.
313 #define POINTDENSITY 3
315 #define COORDLIMIT(n) squarert((n) * POINTDENSITY)
317 static void addedge(tree234
*edges
, int a
, int b
)
319 edge
*e
= snew(edge
);
329 static int isedge(tree234
*edges
, int a
, int b
)
338 return find234(edges
, &e
, NULL
) != NULL
;
341 typedef struct vertex
{
346 static int vertcmpC(const void *av
, const void *bv
)
348 const vertex
*a
= (vertex
*)av
;
349 const vertex
*b
= (vertex
*)bv
;
351 if (a
->param
< b
->param
)
353 else if (a
->param
> b
->param
)
355 else if (a
->vindex
< b
->vindex
)
357 else if (a
->vindex
> b
->vindex
)
361 static int vertcmp(void *av
, void *bv
) { return vertcmpC(av
, bv
); }
364 * Construct point coordinates for n points arranged in a circle,
365 * within the bounding box (0,0) to (w,w).
367 static void make_circle(point
*pts
, int n
, int w
)
372 * First, decide on a denominator. Although in principle it
373 * would be nice to set this really high so as to finely
374 * distinguish all the points on the circle, I'm going to set
375 * it at a fixed size to prevent integer overflow problems.
377 d
= PREFERRED_TILESIZE
;
380 * Leave a little space outside the circle.
388 for (i
= 0; i
< n
; i
++) {
389 double angle
= i
* 2 * PI
/ n
;
390 double x
= r
* sin(angle
), y
= - r
* cos(angle
);
391 pts
[i
].x
= (long)(c
+ x
+ 0.5);
392 pts
[i
].y
= (long)(c
+ y
+ 0.5);
397 static char *new_game_desc(game_params
*params
, random_state
*rs
,
398 char **aux
, int interactive
)
400 int n
= params
->n
, i
;
404 tree234
*edges
, *vertices
;
406 vertex
*v
, *vs
, *vlist
;
409 w
= h
= COORDLIMIT(n
);
412 * Choose n points from this grid.
414 pts
= snewn(n
, point
);
415 tmp
= snewn(w
*h
, long);
416 for (i
= 0; i
< w
*h
; i
++)
418 shuffle(tmp
, w
*h
, sizeof(*tmp
), rs
);
419 for (i
= 0; i
< n
; i
++) {
420 pts
[i
].x
= tmp
[i
] % w
;
421 pts
[i
].y
= tmp
[i
] / w
;
427 * Now start adding edges between the points.
429 * At all times, we attempt to add an edge to the lowest-degree
430 * vertex we currently have, and we try the other vertices as
431 * candidate second endpoints in order of distance from this
432 * one. We stop as soon as we find an edge which
434 * (a) does not increase any vertex's degree beyond MAXDEGREE
435 * (b) does not cross any existing edges
436 * (c) does not intersect any actual point.
438 vs
= snewn(n
, vertex
);
439 vertices
= newtree234(vertcmp
);
440 for (i
= 0; i
< n
; i
++) {
442 v
->param
= 0; /* in this tree, param is the degree */
446 edges
= newtree234(edgecmp
);
447 vlist
= snewn(n
, vertex
);
451 for (i
= 0; i
< n
; i
++) {
452 v
= index234(vertices
, i
);
455 if (v
->param
>= MAXDEGREE
)
456 break; /* nothing left to add! */
459 * Sort the other vertices into order of their distance
460 * from this one. Don't bother looking below i, because
461 * we've already tried those edges the other way round.
462 * Also here we rule out target vertices with too high
463 * a degree, and (of course) ones to which we already
467 for (k
= i
+1; k
< n
; k
++) {
468 vertex
*kv
= index234(vertices
, k
);
472 if (kv
->param
>= MAXDEGREE
|| isedge(edges
, ki
, j
))
475 vlist
[m
].vindex
= ki
;
476 dx
= pts
[ki
].x
- pts
[j
].x
;
477 dy
= pts
[ki
].y
- pts
[j
].y
;
478 vlist
[m
].param
= dx
*dx
+ dy
*dy
;
482 qsort(vlist
, m
, sizeof(*vlist
), vertcmpC
);
484 for (k
= 0; k
< m
; k
++) {
486 int ki
= vlist
[k
].vindex
;
489 * Check to see whether this edge intersects any
490 * existing edge or point.
492 for (p
= 0; p
< n
; p
++)
493 if (p
!= ki
&& p
!= j
&& cross(pts
[ki
], pts
[j
],
498 for (p
= 0; (e
= index234(edges
, p
)) != NULL
; p
++)
499 if (e
->a
!= ki
&& e
->a
!= j
&&
500 e
->b
!= ki
&& e
->b
!= j
&&
501 cross(pts
[ki
], pts
[j
], pts
[e
->a
], pts
[e
->b
]))
507 * We're done! Add this edge, modify the degrees of
508 * the two vertices involved, and break.
510 addedge(edges
, j
, ki
);
512 del234(vertices
, vs
+j
);
514 add234(vertices
, vs
+j
);
515 del234(vertices
, vs
+ki
);
517 add234(vertices
, vs
+ki
);
526 break; /* we're done. */
530 * That's our graph. Now shuffle the points, making sure that
531 * they come out with at least one crossed line when arranged
532 * in a circle (so that the puzzle isn't immediately solved!).
534 tmp
= snewn(n
, long);
535 for (i
= 0; i
< n
; i
++)
537 pts2
= snewn(n
, point
);
538 make_circle(pts2
, n
, w
);
540 shuffle(tmp
, n
, sizeof(*tmp
), rs
);
541 for (i
= 0; (e
= index234(edges
, i
)) != NULL
; i
++) {
542 for (j
= i
+1; (e2
= index234(edges
, j
)) != NULL
; j
++) {
543 if (e2
->a
== e
->a
|| e2
->a
== e
->b
||
544 e2
->b
== e
->a
|| e2
->b
== e
->b
)
546 if (cross(pts2
[tmp
[e2
->a
]], pts2
[tmp
[e2
->b
]],
547 pts2
[tmp
[e
->a
]], pts2
[tmp
[e
->b
]]))
554 break; /* we've found a crossing */
558 * We're done. Now encode the graph in a string format. Let's
559 * use a comma-separated list of dash-separated vertex number
560 * pairs, numbered from zero. We'll sort the list to prevent
573 for (i
= 0; (e
= index234(edges
, i
)) != NULL
; i
++) {
575 ea
[i
].a
= min(tmp
[e
->a
], tmp
[e
->b
]);
576 ea
[i
].b
= max(tmp
[e
->a
], tmp
[e
->b
]);
577 retlen
+= 1 + sprintf(buf
, "%d-%d", ea
[i
].a
, ea
[i
].b
);
580 qsort(ea
, m
, sizeof(*ea
), edgecmpC
);
582 ret
= snewn(retlen
, char);
586 for (i
= 0; i
< m
; i
++) {
587 k
+= sprintf(ret
+ k
, "%s%d-%d", sep
, ea
[i
].a
, ea
[i
].b
);
596 * Encode the solution we started with as an aux_info string.
603 auxlen
= 2; /* leading 'S' and trailing '\0' */
604 for (i
= 0; i
< n
; i
++) {
612 pts2
[j
].x
+= pts2
[j
].d
/ 2;
613 pts2
[j
].y
+= pts2
[j
].d
/ 2;
614 auxlen
+= sprintf(buf
, ";P%d:%ld,%ld/%ld", i
,
615 pts2
[j
].x
, pts2
[j
].y
, pts2
[j
].d
);
618 auxstr
= snewn(auxlen
, char);
620 for (i
= 0; i
< n
; i
++)
621 k
+= sprintf(auxstr
+k
, ";P%d:%ld,%ld/%ld", i
,
622 pts2
[i
].x
, pts2
[i
].y
, pts2
[i
].d
);
630 freetree234(vertices
);
632 while ((e
= delpos234(edges
, 0)) != NULL
)
640 static char *validate_desc(game_params
*params
, char *desc
)
646 if (a
< 0 || a
>= params
->n
)
647 return "Number out of range in game description";
648 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
650 return "Expected '-' after number in game description";
651 desc
++; /* eat dash */
653 if (b
< 0 || b
>= params
->n
)
654 return "Number out of range in game description";
655 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
658 return "Expected ',' after number in game description";
659 desc
++; /* eat comma */
666 static void mark_crossings(game_state
*state
)
672 #ifdef SHOW_CROSSINGS
673 for (i
= 0; (e
= index234(state
->graph
->edges
, i
)) != NULL
; i
++)
674 state
->crosses
[i
] = FALSE
;
678 * Check correctness: for every pair of edges, see whether they
681 for (i
= 0; (e
= index234(state
->graph
->edges
, i
)) != NULL
; i
++) {
682 for (j
= i
+1; (e2
= index234(state
->graph
->edges
, j
)) != NULL
; j
++) {
683 if (e2
->a
== e
->a
|| e2
->a
== e
->b
||
684 e2
->b
== e
->a
|| e2
->b
== e
->b
)
686 if (cross(state
->pts
[e2
->a
], state
->pts
[e2
->b
],
687 state
->pts
[e
->a
], state
->pts
[e
->b
])) {
689 #ifdef SHOW_CROSSINGS
690 state
->crosses
[i
] = state
->crosses
[j
] = TRUE
;
692 goto done
; /* multi-level break - sorry */
699 * e == NULL if we've gone through all the edge pairs
700 * without finding a crossing.
702 #ifndef SHOW_CROSSINGS
706 state
->completed
= TRUE
;
709 static game_state
*new_game(midend_data
*me
, game_params
*params
, char *desc
)
712 game_state
*state
= snew(game_state
);
715 state
->params
= *params
;
716 state
->w
= state
->h
= COORDLIMIT(n
);
717 state
->pts
= snewn(n
, point
);
718 make_circle(state
->pts
, n
, state
->w
);
719 state
->graph
= snew(struct graph
);
720 state
->graph
->refcount
= 1;
721 state
->graph
->edges
= newtree234(edgecmp
);
722 state
->cheated
= state
->just_solved
= FALSE
;
726 assert(a
>= 0 && a
< params
->n
);
727 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
728 assert(*desc
== '-');
729 desc
++; /* eat dash */
731 assert(b
>= 0 && b
< params
->n
);
732 while (*desc
&& isdigit((unsigned char)*desc
)) desc
++;
734 assert(*desc
== ',');
735 desc
++; /* eat comma */
737 addedge(state
->graph
->edges
, a
, b
);
740 #ifdef SHOW_CROSSINGS
741 state
->crosses
= snewn(count234(state
->graph
->edges
), int);
743 mark_crossings(state
); /* sets up `crosses' and `completed' */
748 static game_state
*dup_game(game_state
*state
)
750 int n
= state
->params
.n
;
751 game_state
*ret
= snew(game_state
);
753 ret
->params
= state
->params
;
756 ret
->pts
= snewn(n
, point
);
757 memcpy(ret
->pts
, state
->pts
, n
* sizeof(point
));
758 ret
->graph
= state
->graph
;
759 ret
->graph
->refcount
++;
760 ret
->completed
= state
->completed
;
761 ret
->cheated
= state
->cheated
;
762 ret
->just_solved
= state
->just_solved
;
763 #ifdef SHOW_CROSSINGS
764 ret
->crosses
= snewn(count234(ret
->graph
->edges
), int);
765 memcpy(ret
->crosses
, state
->crosses
,
766 count234(ret
->graph
->edges
) * sizeof(int));
772 static void free_game(game_state
*state
)
774 if (--state
->graph
->refcount
<= 0) {
776 while ((e
= delpos234(state
->graph
->edges
, 0)) != NULL
)
778 freetree234(state
->graph
->edges
);
785 static char *solve_game(game_state
*state
, game_state
*currstate
,
786 char *aux
, char **error
)
788 int n
= state
->params
.n
;
797 *error
= "Solution not known for this puzzle";
802 * Decode the aux_info to get the original point positions.
804 pts
= snewn(n
, point
);
806 for (i
= 0; i
< n
; i
++) {
809 int ret
= sscanf(aux
, ";P%d:%ld,%ld/%ld%n", &p
, &x
, &y
, &d
, &k
);
810 if (ret
!= 4 || p
!= i
) {
811 *error
= "Internal error: aux_info badly formatted";
822 * Now go through eight possible symmetries of the point set.
823 * For each one, work out the sum of the Euclidean distances
824 * between the points' current positions and their new ones.
826 * We're squaring distances here, which means we're at risk of
827 * integer overflow. Fortunately, there's no real need to be
828 * massively careful about rounding errors, since this is a
829 * non-essential bit of the code; so I'll just work in floats
835 for (i
= 0; i
< 8; i
++) {
838 matrix
[0] = matrix
[1] = matrix
[2] = matrix
[3] = 0;
839 matrix
[i
& 1] = (i
& 2) ?
+1 : -1;
840 matrix
[3-(i
&1)] = (i
& 4) ?
+1 : -1;
843 for (j
= 0; j
< n
; j
++) {
844 float px
= (float)pts
[j
].x
/ pts
[j
].d
;
845 float py
= (float)pts
[j
].y
/ pts
[j
].d
;
846 float sx
= (float)currstate
->pts
[j
].x
/ currstate
->pts
[j
].d
;
847 float sy
= (float)currstate
->pts
[j
].y
/ currstate
->pts
[j
].d
;
848 float cx
= (float)currstate
->w
/ 2;
849 float cy
= (float)currstate
->h
/ 2;
850 float ox
, oy
, dx
, dy
;
855 ox
= matrix
[0] * px
+ matrix
[1] * py
;
856 oy
= matrix
[2] * px
+ matrix
[3] * py
;
867 if (besti
< 0 || bestd
> d
) {
876 * Now we know which symmetry is closest to the points' current
879 matrix
[0] = matrix
[1] = matrix
[2] = matrix
[3] = 0;
880 matrix
[besti
& 1] = (besti
& 2) ?
+1 : -1;
881 matrix
[3-(besti
&1)] = (besti
& 4) ?
+1 : -1;
884 ret
= snewn(retsize
, char);
889 for (i
= 0; i
< n
; i
++) {
890 float px
= (float)pts
[i
].x
/ pts
[i
].d
;
891 float py
= (float)pts
[i
].y
/ pts
[i
].d
;
892 float cx
= (float)currstate
->w
/ 2;
893 float cy
= (float)currstate
->h
/ 2;
900 ox
= matrix
[0] * px
+ matrix
[1] * py
;
901 oy
= matrix
[2] * px
+ matrix
[3] * py
;
907 * Use a fixed denominator of 2, because we know the
908 * original points were on an integer grid offset by 1/2.
916 extra
= sprintf(buf
, ";P%d:%ld,%ld/%ld", i
,
917 pts
[i
].x
, pts
[i
].y
, pts
[i
].d
);
918 if (retlen
+ extra
>= retsize
) {
919 retsize
= retlen
+ extra
+ 256;
920 ret
= sresize(ret
, retsize
, char);
922 strcpy(ret
+ retlen
, buf
);
931 static char *game_text_format(game_state
*state
)
937 int dragpoint
; /* point being dragged; -1 if none */
938 point newpoint
; /* where it's been dragged to so far */
939 int just_dragged
; /* reset in game_changed_state */
940 int just_moved
; /* _set_ in game_changed_state */
944 static game_ui
*new_ui(game_state
*state
)
946 game_ui
*ui
= snew(game_ui
);
948 ui
->just_moved
= ui
->just_dragged
= FALSE
;
952 static void free_ui(game_ui
*ui
)
957 static char *encode_ui(game_ui
*ui
)
962 static void decode_ui(game_ui
*ui
, char *encoding
)
966 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
967 game_state
*newstate
)
970 ui
->just_moved
= ui
->just_dragged
;
971 ui
->just_dragged
= FALSE
;
974 struct game_drawstate
{
978 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
979 int x
, int y
, int button
)
981 int n
= state
->params
.n
;
983 if (button
== LEFT_BUTTON
) {
988 * Begin drag. We drag the vertex _nearest_ to the pointer,
989 * just in case one is nearly on top of another and we want
990 * to drag the latter. However, we drag nothing at all if
991 * the nearest vertex is outside DRAG_THRESHOLD.
996 for (i
= 0; i
< n
; i
++) {
997 long px
= state
->pts
[i
].x
* ds
->tilesize
/ state
->pts
[i
].d
;
998 long py
= state
->pts
[i
].y
* ds
->tilesize
/ state
->pts
[i
].d
;
1001 long d
= dx
*dx
+ dy
*dy
;
1003 if (best
== -1 || bestd
> d
) {
1009 if (bestd
<= DRAG_THRESHOLD
* DRAG_THRESHOLD
) {
1010 ui
->dragpoint
= best
;
1013 ui
->newpoint
.d
= ds
->tilesize
;
1017 } else if (button
== LEFT_DRAG
&& ui
->dragpoint
>= 0) {
1020 ui
->newpoint
.d
= ds
->tilesize
;
1022 } else if (button
== LEFT_RELEASE
&& ui
->dragpoint
>= 0) {
1023 int p
= ui
->dragpoint
;
1026 ui
->dragpoint
= -1; /* terminate drag, no matter what */
1029 * First, see if we're within range. The user can cancel a
1030 * drag by dragging the point right off the window.
1032 if (ui
->newpoint
.x
< 0 ||
1033 ui
->newpoint
.x
>= (long)state
->w
*ui
->newpoint
.d
||
1034 ui
->newpoint
.y
< 0 ||
1035 ui
->newpoint
.y
>= (long)state
->h
*ui
->newpoint
.d
)
1039 * We aren't cancelling the drag. Construct a move string
1040 * indicating where this point is going to.
1042 sprintf(buf
, "P%d:%ld,%ld/%ld", p
,
1043 ui
->newpoint
.x
, ui
->newpoint
.y
, ui
->newpoint
.d
);
1044 ui
->just_dragged
= TRUE
;
1051 static game_state
*execute_move(game_state
*state
, char *move
)
1053 int n
= state
->params
.n
;
1056 game_state
*ret
= dup_game(state
);
1058 ret
->just_solved
= FALSE
;
1063 if (*move
== ';') move
++;
1064 ret
->cheated
= ret
->just_solved
= TRUE
;
1067 sscanf(move
+1, "%d:%ld,%ld/%ld%n", &p
, &x
, &y
, &d
, &k
) == 4 &&
1068 p
>= 0 && p
< n
&& d
> 0) {
1074 if (*move
== ';') move
++;
1081 mark_crossings(ret
);
1086 /* ----------------------------------------------------------------------
1090 static void game_compute_size(game_params
*params
, int tilesize
,
1093 *x
= *y
= COORDLIMIT(params
->n
) * tilesize
;
1096 static void game_set_size(game_drawstate
*ds
, game_params
*params
,
1099 ds
->tilesize
= tilesize
;
1102 static float *game_colours(frontend
*fe
, game_state
*state
, int *ncolours
)
1104 float *ret
= snewn(3 * NCOLOURS
, float);
1106 frontend_default_colour(fe
, &ret
[COL_BACKGROUND
* 3]);
1108 ret
[COL_LINE
* 3 + 0] = 0.0F
;
1109 ret
[COL_LINE
* 3 + 1] = 0.0F
;
1110 ret
[COL_LINE
* 3 + 2] = 0.0F
;
1112 #ifdef SHOW_CROSSINGS
1113 ret
[COL_CROSSEDLINE
* 3 + 0] = 1.0F
;
1114 ret
[COL_CROSSEDLINE
* 3 + 1] = 0.0F
;
1115 ret
[COL_CROSSEDLINE
* 3 + 2] = 0.0F
;
1118 ret
[COL_OUTLINE
* 3 + 0] = 0.0F
;
1119 ret
[COL_OUTLINE
* 3 + 1] = 0.0F
;
1120 ret
[COL_OUTLINE
* 3 + 2] = 0.0F
;
1122 ret
[COL_POINT
* 3 + 0] = 0.0F
;
1123 ret
[COL_POINT
* 3 + 1] = 0.0F
;
1124 ret
[COL_POINT
* 3 + 2] = 1.0F
;
1126 ret
[COL_DRAGPOINT
* 3 + 0] = 1.0F
;
1127 ret
[COL_DRAGPOINT
* 3 + 1] = 1.0F
;
1128 ret
[COL_DRAGPOINT
* 3 + 2] = 1.0F
;
1130 ret
[COL_NEIGHBOUR
* 3 + 0] = 1.0F
;
1131 ret
[COL_NEIGHBOUR
* 3 + 1] = 0.0F
;
1132 ret
[COL_NEIGHBOUR
* 3 + 2] = 0.0F
;
1134 ret
[COL_FLASH1
* 3 + 0] = 0.5F
;
1135 ret
[COL_FLASH1
* 3 + 1] = 0.5F
;
1136 ret
[COL_FLASH1
* 3 + 2] = 0.5F
;
1138 ret
[COL_FLASH2
* 3 + 0] = 1.0F
;
1139 ret
[COL_FLASH2
* 3 + 1] = 1.0F
;
1140 ret
[COL_FLASH2
* 3 + 2] = 1.0F
;
1142 *ncolours
= NCOLOURS
;
1146 static game_drawstate
*game_new_drawstate(game_state
*state
)
1148 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1155 static void game_free_drawstate(game_drawstate
*ds
)
1160 static point
mix(point a
, point b
, float distance
)
1165 ret
.x
= a
.x
* b
.d
+ distance
* (b
.x
* a
.d
- a
.x
* b
.d
);
1166 ret
.y
= a
.y
* b
.d
+ distance
* (b
.y
* a
.d
- a
.y
* b
.d
);
1171 static void game_redraw(frontend
*fe
, game_drawstate
*ds
, game_state
*oldstate
,
1172 game_state
*state
, int dir
, game_ui
*ui
,
1173 float animtime
, float flashtime
)
1181 * There's no terribly sensible way to do partial redraws of
1182 * this game, so I'm going to have to resort to redrawing the
1183 * whole thing every time.
1187 bg
= COL_BACKGROUND
;
1188 else if ((int)(flashtime
* 4 / FLASH_TIME
) % 2 == 0)
1193 game_compute_size(&state
->params
, ds
->tilesize
, &w
, &h
);
1194 draw_rect(fe
, 0, 0, w
, h
, bg
);
1200 for (i
= 0; (e
= index234(state
->graph
->edges
, i
)) != NULL
; i
++) {
1202 long x1
, y1
, x2
, y2
;
1204 p1
= state
->pts
[e
->a
];
1205 p2
= state
->pts
[e
->b
];
1206 if (ui
->dragpoint
== e
->a
)
1208 else if (ui
->dragpoint
== e
->b
)
1212 p1
= mix(oldstate
->pts
[e
->a
], p1
, animtime
/ ui
->anim_length
);
1213 p2
= mix(oldstate
->pts
[e
->b
], p2
, animtime
/ ui
->anim_length
);
1216 x1
= p1
.x
* ds
->tilesize
/ p1
.d
;
1217 y1
= p1
.y
* ds
->tilesize
/ p1
.d
;
1218 x2
= p2
.x
* ds
->tilesize
/ p2
.d
;
1219 y2
= p2
.y
* ds
->tilesize
/ p2
.d
;
1221 draw_line(fe
, x1
, y1
, x2
, y2
,
1222 #ifdef SHOW_CROSSINGS
1223 (oldstate?oldstate
:state
)->crosses
[i
] ?
1232 * When dragging, we should not only vary the colours, but
1233 * leave the point being dragged until last.
1235 for (j
= 0; j
< 3; j
++) {
1236 int thisc
= (j
== 0 ? COL_POINT
:
1237 j
== 1 ? COL_NEIGHBOUR
: COL_DRAGPOINT
);
1238 for (i
= 0; i
< state
->params
.n
; i
++) {
1241 point p
= state
->pts
[i
];
1243 if (ui
->dragpoint
== i
) {
1246 } else if (ui
->dragpoint
>= 0 &&
1247 isedge(state
->graph
->edges
, ui
->dragpoint
, i
)) {
1254 p
= mix(oldstate
->pts
[i
], p
, animtime
/ ui
->anim_length
);
1257 x
= p
.x
* ds
->tilesize
/ p
.d
;
1258 y
= p
.y
* ds
->tilesize
/ p
.d
;
1260 #ifdef VERTEX_NUMBERS
1261 draw_circle(fe
, x
, y
, DRAG_THRESHOLD
, bg
, bg
);
1264 sprintf(buf
, "%d", i
);
1265 draw_text(fe
, x
, y
, FONT_VARIABLE
, DRAG_THRESHOLD
*3/2,
1266 ALIGN_VCENTRE
|ALIGN_HCENTRE
, c
, buf
);
1269 draw_circle(fe
, x
, y
, CIRCLE_RADIUS
, c
, COL_OUTLINE
);
1275 draw_update(fe
, 0, 0, w
, h
);
1278 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1279 int dir
, game_ui
*ui
)
1283 if ((dir
< 0 ? oldstate
: newstate
)->just_solved
)
1284 ui
->anim_length
= SOLVEANIM_TIME
;
1286 ui
->anim_length
= ANIM_TIME
;
1287 return ui
->anim_length
;
1290 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1291 int dir
, game_ui
*ui
)
1293 if (!oldstate
->completed
&& newstate
->completed
&&
1294 !oldstate
->cheated
&& !newstate
->cheated
)
1299 static int game_wants_statusbar(void)
1304 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1310 #define thegame untangle
1313 const struct game thegame
= {
1314 "Untangle", "games.untangle",
1321 TRUE
, game_configure
, custom_params
,
1329 FALSE
, game_text_format
,
1337 PREFERRED_TILESIZE
, game_compute_size
, game_set_size
,
1340 game_free_drawstate
,
1344 game_wants_statusbar
,
1345 FALSE
, game_timing_state
,
1346 SOLVE_ANIMATES
, /* mouse_priorities */