tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
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.
6 *
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.
11 */
12
13/*
14 * TODO:
15 *
16 * - This puzzle, perhaps uniquely among the collection, could use
17 * support for non-aspect-ratio-preserving resizes. This would
18 * require some sort of fairly large redesign, unfortunately (since
19 * it would invalidate the basic assumption that puzzles' size
20 * requirements are adequately expressed by a single scalar tile
21 * size), and probably complicate the rest of the puzzles' API as a
22 * result. So I'm not sure I really want to do it.
23 */
24
25#include <stdio.h>
26#include <stdlib.h>
27#include <string.h>
28#include <assert.h>
29#include <ctype.h>
30#include <limits.h>
31#ifdef NO_TGMATH_H
32# include <math.h>
33#else
34# include <tgmath.h>
35#endif
36#if HAVE_STDINT_H
37# include <stdint.h>
38#endif
39
40#include "puzzles.h"
41#include "tree234.h"
42
43#ifndef CIRCLE_RADIUS
44# define CIRCLE_RADIUS 6
45#endif
46
47#ifndef DRAG_THRESHOLD
48# define DRAG_THRESHOLD (CIRCLE_RADIUS * 2)
49#endif
50
51#define PREFERRED_TILESIZE 64
52
53#define FLASH_TIME 0.30F
54#define ANIM_TIME 0.13F
55#define SOLVEANIM_TIME 0.50F
56
57enum {
58 COL_SYSBACKGROUND,
59 COL_BACKGROUND,
60 COL_LINE,
61 COL_CROSSEDLINE,
62 COL_OUTLINE,
63 COL_POINT,
64 COL_DRAGPOINT,
65 COL_CURSORPOINT,
66 COL_NEIGHBOUR,
67 COL_FLASH1,
68 COL_FLASH2,
69 NCOLOURS
70};
71
72enum {
73 PREF_SNAP_TO_GRID,
74 PREF_SHOW_CROSSED_EDGES,
75 PREF_VERTEX_STYLE,
76 N_PREF_ITEMS
77};
78
79typedef struct point {
80 /*
81 * Points are stored using rational coordinates, with the same
82 * denominator for both coordinates.
83 */
84 long x, y, d;
85} point;
86
87typedef struct edge {
88 /*
89 * This structure is implicitly associated with a particular
90 * point set, so all it has to do is to store two point
91 * indices. It is required to store them in the order (lower,
92 * higher), i.e. a < b always.
93 */
94 int a, b;
95} edge;
96
97struct game_params {
98 int n; /* number of points */
99};
100
101struct graph {
102 int refcount; /* for deallocation */
103 tree234 *edges; /* stores `edge' structures */
104};
105
106struct game_state {
107 game_params params;
108 int w, h; /* extent of coordinate system only */
109 point *pts;
110 struct graph *graph;
111#ifndef EDITOR
112 int *crosses; /* mark edges which are crossed */
113 bool completed, cheated, just_solved;
114#endif
115};
116
117static int edgecmpC(const void *av, const void *bv)
118{
119 const edge *a = (const edge *)av;
120 const edge *b = (const edge *)bv;
121
122 if (a->a < b->a)
123 return -1;
124 else if (a->a > b->a)
125 return +1;
126 else if (a->b < b->b)
127 return -1;
128 else if (a->b > b->b)
129 return +1;
130 return 0;
131}
132
133static int edgecmp(void *av, void *bv) { return edgecmpC(av, bv); }
134
135static game_params *default_params(void)
136{
137 game_params *ret = snew(game_params);
138
139 ret->n = 10;
140
141 return ret;
142}
143
144static bool game_fetch_preset(int i, char **name, game_params **params)
145{
146 game_params *ret;
147 int n;
148 char buf[80];
149
150 switch (i) {
151 case 0: n = 6; break;
152 case 1: n = 10; break;
153 case 2: n = 15; break;
154 case 3: n = 20; break;
155 case 4: n = 25; break;
156 default: return false;
157 }
158
159 sprintf(buf, "%d points", n);
160 *name = dupstr(buf);
161
162 *params = ret = snew(game_params);
163 ret->n = n;
164
165 return true;
166}
167
168static void free_params(game_params *params)
169{
170 sfree(params);
171}
172
173static game_params *dup_params(const game_params *params)
174{
175 game_params *ret = snew(game_params);
176 *ret = *params; /* structure copy */
177 return ret;
178}
179
180static void decode_params(game_params *params, char const *string)
181{
182 params->n = atoi(string);
183}
184
185static char *encode_params(const game_params *params, bool full)
186{
187 char buf[80];
188
189 sprintf(buf, "%d", params->n);
190
191 return dupstr(buf);
192}
193
194static config_item *game_configure(const game_params *params)
195{
196 config_item *ret;
197 char buf[80];
198
199 ret = snewn(3, config_item);
200
201 ret[0].name = "Number of points";
202 ret[0].type = C_STRING;
203 sprintf(buf, "%d", params->n);
204 ret[0].u.string.sval = dupstr(buf);
205
206 ret[1].name = NULL;
207 ret[1].type = C_END;
208
209 return ret;
210}
211
212static game_params *custom_params(const config_item *cfg)
213{
214 game_params *ret = snew(game_params);
215
216 ret->n = atoi(cfg[0].u.string.sval);
217
218 return ret;
219}
220
221static const char *validate_params(const game_params *params, bool full)
222{
223#ifndef EDITOR
224 if (params->n < 4)
225 return "Number of points must be at least four";
226#else
227 if (params->n < 1)
228 return "Number of points must be at least one";
229#endif
230 if (params->n > INT_MAX / 3)
231 return "Number of points must not be unreasonably large";
232 return NULL;
233}
234
235#ifndef EDITOR
236/* ----------------------------------------------------------------------
237 * Small number of 64-bit integer arithmetic operations, to prevent
238 * integer overflow at the very core of cross().
239 */
240
241#if !HAVE_STDINT_H
242/* For prehistoric C implementations, do this the hard way */
243
244typedef struct {
245 long hi;
246 unsigned long lo;
247} int64;
248
249#define greater64(i,j) ( (i).hi>(j).hi || ((i).hi==(j).hi && (i).lo>(j).lo))
250#define sign64(i) ((i).hi < 0 ? -1 : (i).hi==0 && (i).lo==0 ? 0 : +1)
251
252static int64 mulu32to64(unsigned long x, unsigned long y)
253{
254 unsigned long a, b, c, d, t;
255 int64 ret;
256
257 a = (x & 0xFFFF) * (y & 0xFFFF);
258 b = (x & 0xFFFF) * (y >> 16);
259 c = (x >> 16) * (y & 0xFFFF);
260 d = (x >> 16) * (y >> 16);
261
262 ret.lo = a;
263 ret.hi = d + (b >> 16) + (c >> 16);
264 t = (b & 0xFFFF) << 16;
265 ret.lo += t;
266 if (ret.lo < t)
267 ret.hi++;
268 t = (c & 0xFFFF) << 16;
269 ret.lo += t;
270 if (ret.lo < t)
271 ret.hi++;
272
273#ifdef DIAGNOSTIC_VIA_LONGLONG
274 assert(((unsigned long long)ret.hi << 32) + ret.lo ==
275 (unsigned long long)x * y);
276#endif
277
278 return ret;
279}
280
281static int64 mul32to64(long x, long y)
282{
283 int sign = +1;
284 int64 ret;
285#ifdef DIAGNOSTIC_VIA_LONGLONG
286 long long realret = (long long)x * y;
287#endif
288
289 if (x < 0)
290 x = -x, sign = -sign;
291 if (y < 0)
292 y = -y, sign = -sign;
293
294 ret = mulu32to64(x, y);
295
296 if (sign < 0) {
297 ret.hi = -ret.hi;
298 ret.lo = -ret.lo;
299 if (ret.lo)
300 ret.hi--;
301 }
302
303#ifdef DIAGNOSTIC_VIA_LONGLONG
304 assert(((unsigned long long)ret.hi << 32) + ret.lo == realret);
305#endif
306
307 return ret;
308}
309
310static int64 dotprod64(long a, long b, long p, long q)
311{
312 int64 ab, pq;
313
314 ab = mul32to64(a, b);
315 pq = mul32to64(p, q);
316 ab.hi += pq.hi;
317 ab.lo += pq.lo;
318 if (ab.lo < pq.lo)
319 ab.hi++;
320 return ab;
321}
322
323#else /* HAVE_STDINT_H */
324
325typedef int64_t int64;
326#define greater64(i,j) ((i) > (j))
327#define sign64(i) ((i) < 0 ? -1 : (i)==0 ? 0 : +1)
328#define mulu32to64(x,y) ((int64_t)(unsigned long)(x) * (unsigned long)(y))
329#define mul32to64(x,y) ((int64_t)(long)(x) * (long)(y))
330
331static int64 dotprod64(long a, long b, long p, long q)
332{
333 return (int64)a * b + (int64)p * q;
334}
335
336#endif /* HAVE_STDINT_H */
337
338/*
339 * Determine whether the line segments between a1 and a2, and
340 * between b1 and b2, intersect. We count it as an intersection if
341 * any of the endpoints lies _on_ the other line.
342 */
343static bool cross(point a1, point a2, point b1, point b2)
344{
345 long b1x, b1y, b2x, b2y, px, py;
346 int64 d1, d2, d3;
347
348 /*
349 * The condition for crossing is that b1 and b2 are on opposite
350 * sides of the line a1-a2, and vice versa. We determine this
351 * by taking the dot product of b1-a1 with a vector
352 * perpendicular to a2-a1, and similarly with b2-a1, and seeing
353 * if they have different signs.
354 */
355
356 /*
357 * Construct the vector b1-a1. We don't have to worry too much
358 * about the denominator, because we're only going to check the
359 * sign of this vector; we just need to get the numerator
360 * right.
361 */
362 b1x = b1.x * a1.d - a1.x * b1.d;
363 b1y = b1.y * a1.d - a1.y * b1.d;
364 /* Now construct b2-a1, and a vector perpendicular to a2-a1,
365 * in the same way. */
366 b2x = b2.x * a1.d - a1.x * b2.d;
367 b2y = b2.y * a1.d - a1.y * b2.d;
368 px = a1.y * a2.d - a2.y * a1.d;
369 py = a2.x * a1.d - a1.x * a2.d;
370 /* Take the dot products. Here we resort to 64-bit arithmetic. */
371 d1 = dotprod64(b1x, px, b1y, py);
372 d2 = dotprod64(b2x, px, b2y, py);
373 /* If they have the same non-zero sign, the lines do not cross. */
374 if ((sign64(d1) > 0 && sign64(d2) > 0) ||
375 (sign64(d1) < 0 && sign64(d2) < 0))
376 return false;
377
378 /*
379 * If the dot products are both exactly zero, then the two line
380 * segments are collinear. At this point the intersection
381 * condition becomes whether or not they overlap within their
382 * line.
383 */
384 if (sign64(d1) == 0 && sign64(d2) == 0) {
385 /* Construct the vector a2-a1. */
386 px = a2.x * a1.d - a1.x * a2.d;
387 py = a2.y * a1.d - a1.y * a2.d;
388 /* Determine the dot products of b1-a1 and b2-a1 with this. */
389 d1 = dotprod64(b1x, px, b1y, py);
390 d2 = dotprod64(b2x, px, b2y, py);
391 /* If they're both strictly negative, the lines do not cross. */
392 if (sign64(d1) < 0 && sign64(d2) < 0)
393 return false;
394 /* Otherwise, take the dot product of a2-a1 with itself. If
395 * the other two dot products both exceed this, the lines do
396 * not cross. */
397 d3 = dotprod64(px, px, py, py);
398 if (greater64(d1, d3) && greater64(d2, d3))
399 return false;
400 }
401
402 /*
403 * We've eliminated the only important special case, and we
404 * have determined that b1 and b2 are on opposite sides of the
405 * line a1-a2. Now do the same thing the other way round and
406 * we're done.
407 */
408 b1x = a1.x * b1.d - b1.x * a1.d;
409 b1y = a1.y * b1.d - b1.y * a1.d;
410 b2x = a2.x * b1.d - b1.x * a2.d;
411 b2y = a2.y * b1.d - b1.y * a2.d;
412 px = b1.y * b2.d - b2.y * b1.d;
413 py = b2.x * b1.d - b1.x * b2.d;
414 d1 = dotprod64(b1x, px, b1y, py);
415 d2 = dotprod64(b2x, px, b2y, py);
416 if ((sign64(d1) > 0 && sign64(d2) > 0) ||
417 (sign64(d1) < 0 && sign64(d2) < 0))
418 return false;
419
420 /*
421 * The lines must cross.
422 */
423 return true;
424}
425
426#endif /* EDITOR */
427
428static unsigned long squarert(unsigned long n) {
429 unsigned long d, a, b, di;
430
431 d = n;
432 a = 0;
433 b = 1L << 30; /* largest available power of 4 */
434 do {
435 a >>= 1;
436 di = 2*a + b;
437 if (di <= d) {
438 d -= di;
439 a += b;
440 }
441 b >>= 2;
442 } while (b);
443
444 return a;
445}
446
447/*
448 * Our solutions are arranged on a square grid big enough that n
449 * points occupy about 1/POINTDENSITY of the grid.
450 */
451#define POINTDENSITY 3
452#define MAXDEGREE 4
453#define COORDLIMIT(n) squarert((n) * POINTDENSITY)
454
455static void addedge(tree234 *edges, int a, int b)
456{
457 edge *e = snew(edge);
458
459 assert(a != b);
460
461 e->a = min(a, b);
462 e->b = max(a, b);
463
464 if (add234(edges, e) != e)
465 /* Duplicate edge. */
466 sfree(e);
467}
468
469#ifdef EDITOR
470static void deledge(tree234 *edges, int a, int b)
471{
472 edge e, *found;
473
474 assert(a != b);
475
476 e.a = min(a, b);
477 e.b = max(a, b);
478
479 found = del234(edges, &e);
480 sfree(found);
481}
482#endif
483
484static bool isedge(tree234 *edges, int a, int b)
485{
486 edge e;
487
488 assert(a != b);
489
490 e.a = min(a, b);
491 e.b = max(a, b);
492
493 return find234(edges, &e, NULL) != NULL;
494}
495
496typedef struct vertex {
497 int param;
498 int vindex;
499} vertex;
500
501#ifndef EDITOR
502static int vertcmpC(const void *av, const void *bv)
503{
504 const vertex *a = (const vertex *)av;
505 const vertex *b = (const vertex *)bv;
506
507 if (a->param < b->param)
508 return -1;
509 else if (a->param > b->param)
510 return +1;
511 else if (a->vindex < b->vindex)
512 return -1;
513 else if (a->vindex > b->vindex)
514 return +1;
515 return 0;
516}
517static int vertcmp(void *av, void *bv) { return vertcmpC(av, bv); }
518#endif
519
520/*
521 * Construct point coordinates for n points arranged in a circle,
522 * within the bounding box (0,0) to (w,w).
523 */
524static void make_circle(point *pts, int n, int w)
525{
526 long d, r, c, i;
527
528 /*
529 * First, decide on a denominator. Although in principle it
530 * would be nice to set this really high so as to finely
531 * distinguish all the points on the circle, I'm going to set
532 * it at a fixed size to prevent integer overflow problems.
533 */
534 d = PREFERRED_TILESIZE;
535
536 /*
537 * Leave a little space outside the circle.
538 */
539 c = d * w / 2;
540 r = d * w * 3 / 7;
541
542 /*
543 * Place the points.
544 */
545 for (i = 0; i < n; i++) {
546 double angle = i * 2 * PI / n;
547 double x = r * sin(angle), y = - r * cos(angle);
548 pts[i].x = (long)(c + x + 0.5);
549 pts[i].y = (long)(c + y + 0.5);
550 pts[i].d = d;
551 }
552}
553
554/*
555 * Encode a graph in Untangle's game id: a comma-separated list of
556 * dash-separated vertex number pairs, numbered from zero.
557 *
558 * If params != NULL, then the number of vertices is prefixed to the
559 * front to make a full Untangle game id. Otherwise, we return just
560 * the game description part.
561 *
562 * If mapping != NULL, then it is expected to be a mapping from the
563 * graph's original vertex numbers to output vertex numbers.
564 */
565static char *encode_graph(const game_params *params, tree234 *edges,
566 const long *mapping)
567{
568 const char *sep;
569 char buf[80];
570 int i, k, m, retlen;
571 edge *e, *ea;
572 char *ret;
573
574 retlen = 0;
575 if (params)
576 retlen += sprintf(buf, "%d:", params->n);
577
578 m = count234(edges);
579 ea = snewn(m, edge);
580 for (i = 0; (e = index234(edges, i)) != NULL; i++) {
581 int ma, mb;
582 assert(i < m);
583 if (mapping) {
584 ma = mapping[e->a];
585 mb = mapping[e->b];
586 } else {
587 ma = e->a;
588 mb = e->b;
589 }
590 ea[i].a = min(ma, mb);
591 ea[i].b = max(ma, mb);
592 if (i > 0)
593 retlen++; /* comma separator after the previous edge */
594 retlen += sprintf(buf, "%d-%d", ea[i].a, ea[i].b);
595 }
596 assert(i == m);
597 /* Re-sort to prevent side channels, if mapping was used */
598 qsort(ea, m, sizeof(*ea), edgecmpC);
599
600 ret = snewn(retlen + 1, char);
601 sep = "";
602 k = 0;
603 if (params)
604 k += sprintf(ret + k, "%d:", params->n);
605
606 for (i = 0; i < m; i++) {
607 k += sprintf(ret + k, "%s%d-%d", sep, ea[i].a, ea[i].b);
608 sep = ",";
609 }
610 assert(k == retlen);
611
612 sfree(ea);
613
614 return ret;
615}
616
617static char *new_game_desc(const game_params *params, random_state *rs,
618 char **aux, bool interactive)
619{
620#ifndef EDITOR
621 int n = params->n, i;
622 long w, h, j, k, m;
623 point *pts, *pts2;
624 long *tmp;
625 tree234 *edges, *vertices;
626 edge *e, *e2;
627 vertex *v, *vs, *vlist;
628 char *ret;
629
630 w = h = COORDLIMIT(n);
631
632 /*
633 * Choose n points from this grid.
634 */
635 pts = snewn(n, point);
636 tmp = snewn(w*h, long);
637 for (i = 0; i < w*h; i++)
638 tmp[i] = i;
639 shuffle(tmp, w*h, sizeof(*tmp), rs);
640 for (i = 0; i < n; i++) {
641 pts[i].x = tmp[i] % w;
642 pts[i].y = tmp[i] / w;
643 pts[i].d = 1;
644 }
645 sfree(tmp);
646
647 /*
648 * Now start adding edges between the points.
649 *
650 * At all times, we attempt to add an edge to the lowest-degree
651 * vertex we currently have, and we try the other vertices as
652 * candidate second endpoints in order of distance from this
653 * one. We stop as soon as we find an edge which
654 *
655 * (a) does not increase any vertex's degree beyond MAXDEGREE
656 * (b) does not cross any existing edges
657 * (c) does not intersect any actual point.
658 */
659 vs = snewn(n, vertex);
660 vertices = newtree234(vertcmp);
661 for (i = 0; i < n; i++) {
662 v = vs + i;
663 v->param = 0; /* in this tree, param is the degree */
664 v->vindex = i;
665 add234(vertices, v);
666 }
667 edges = newtree234(edgecmp);
668 vlist = snewn(n, vertex);
669 while (1) {
670 bool added = false;
671
672 for (i = 0; i < n; i++) {
673 v = index234(vertices, i);
674 j = v->vindex;
675
676 if (v->param >= MAXDEGREE)
677 break; /* nothing left to add! */
678
679 /*
680 * Sort the other vertices into order of their distance
681 * from this one. Don't bother looking below i, because
682 * we've already tried those edges the other way round.
683 * Also here we rule out target vertices with too high
684 * a degree, and (of course) ones to which we already
685 * have an edge.
686 */
687 m = 0;
688 for (k = i+1; k < n; k++) {
689 vertex *kv = index234(vertices, k);
690 int ki = kv->vindex;
691 int dx, dy;
692
693 if (kv->param >= MAXDEGREE || isedge(edges, ki, j))
694 continue;
695
696 vlist[m].vindex = ki;
697 dx = pts[ki].x - pts[j].x;
698 dy = pts[ki].y - pts[j].y;
699 vlist[m].param = dx*dx + dy*dy;
700 m++;
701 }
702
703 qsort(vlist, m, sizeof(*vlist), vertcmpC);
704
705 for (k = 0; k < m; k++) {
706 int p;
707 int ki = vlist[k].vindex;
708
709 /*
710 * Check to see whether this edge intersects any
711 * existing edge or point.
712 */
713 for (p = 0; p < n; p++)
714 if (p != ki && p != j && cross(pts[ki], pts[j],
715 pts[p], pts[p]))
716 break;
717 if (p < n)
718 continue;
719 for (p = 0; (e = index234(edges, p)) != NULL; p++)
720 if (e->a != ki && e->a != j &&
721 e->b != ki && e->b != j &&
722 cross(pts[ki], pts[j], pts[e->a], pts[e->b]))
723 break;
724 if (e)
725 continue;
726
727 /*
728 * We're done! Add this edge, modify the degrees of
729 * the two vertices involved, and break.
730 */
731 addedge(edges, j, ki);
732 added = true;
733 del234(vertices, vs+j);
734 vs[j].param++;
735 add234(vertices, vs+j);
736 del234(vertices, vs+ki);
737 vs[ki].param++;
738 add234(vertices, vs+ki);
739 break;
740 }
741
742 if (k < m)
743 break;
744 }
745
746 if (!added)
747 break; /* we're done. */
748 }
749
750 /*
751 * That's our graph. Now shuffle the points, making sure that
752 * they come out with at least one crossed line when arranged
753 * in a circle (so that the puzzle isn't immediately solved!).
754 */
755 tmp = snewn(n, long);
756 for (i = 0; i < n; i++)
757 tmp[i] = i;
758 pts2 = snewn(n, point);
759 make_circle(pts2, n, w);
760 while (1) {
761 shuffle(tmp, n, sizeof(*tmp), rs);
762 for (i = 0; (e = index234(edges, i)) != NULL; i++) {
763 for (j = i+1; (e2 = index234(edges, j)) != NULL; j++) {
764 if (e2->a == e->a || e2->a == e->b ||
765 e2->b == e->a || e2->b == e->b)
766 continue;
767 if (cross(pts2[tmp[e2->a]], pts2[tmp[e2->b]],
768 pts2[tmp[e->a]], pts2[tmp[e->b]]))
769 break;
770 }
771 if (e2)
772 break;
773 }
774 if (e)
775 break; /* we've found a crossing */
776 }
777
778 /*
779 * We're done. Encode the output graph as a string.
780 */
781 ret = encode_graph(NULL, edges, tmp);
782
783 /*
784 * Encode the solution we started with as an aux_info string.
785 */
786 {
787 char buf[80];
788 char *auxstr;
789 int auxlen;
790
791 auxlen = 2; /* leading 'S' and trailing '\0' */
792 for (i = 0; i < n; i++) {
793 j = tmp[i];
794 pts2[j] = pts[i];
795 if (pts2[j].d & 1) {
796 pts2[j].x *= 2;
797 pts2[j].y *= 2;
798 pts2[j].d *= 2;
799 }
800 pts2[j].x += pts2[j].d / 2;
801 pts2[j].y += pts2[j].d / 2;
802 auxlen += sprintf(buf, ";P%d:%ld,%ld/%ld", i,
803 pts2[j].x, pts2[j].y, pts2[j].d);
804 }
805 k = 0;
806 auxstr = snewn(auxlen, char);
807 auxstr[k++] = 'S';
808 for (i = 0; i < n; i++)
809 k += sprintf(auxstr+k, ";P%d:%ld,%ld/%ld", i,
810 pts2[i].x, pts2[i].y, pts2[i].d);
811 assert(k < auxlen);
812 *aux = auxstr;
813 }
814 sfree(pts2);
815
816 sfree(tmp);
817 sfree(vlist);
818 freetree234(vertices);
819 sfree(vs);
820 while ((e = delpos234(edges, 0)) != NULL)
821 sfree(e);
822 freetree234(edges);
823 sfree(pts);
824
825 return ret;
826#else
827 return dupstr("");
828#endif
829}
830
831static const char *validate_desc(const game_params *params, const char *desc)
832{
833 int a, b;
834
835 while (*desc) {
836 a = atoi(desc);
837 if (a < 0 || a >= params->n)
838 return "Number out of range in game description";
839 while (*desc && isdigit((unsigned char)*desc)) desc++;
840 if (*desc != '-')
841 return "Expected '-' after number in game description";
842 desc++; /* eat dash */
843 b = atoi(desc);
844 if (b < 0 || b >= params->n)
845 return "Number out of range in game description";
846 while (*desc && isdigit((unsigned char)*desc)) desc++;
847 if (*desc) {
848 if (*desc != ',')
849 return "Expected ',' after number in game description";
850 desc++; /* eat comma */
851 }
852 if (a == b)
853 return "Node linked to itself in game description";
854 }
855
856 return NULL;
857}
858
859#ifndef EDITOR
860static void mark_crossings(game_state *state)
861{
862 bool ok = true;
863 int i, j;
864 edge *e, *e2;
865
866 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++)
867 state->crosses[i] = false;
868
869 /*
870 * Check correctness: for every pair of edges, see whether they
871 * cross.
872 */
873 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
874 for (j = i+1; (e2 = index234(state->graph->edges, j)) != NULL; j++) {
875 if (e2->a == e->a || e2->a == e->b ||
876 e2->b == e->a || e2->b == e->b)
877 continue;
878 if (cross(state->pts[e2->a], state->pts[e2->b],
879 state->pts[e->a], state->pts[e->b])) {
880 ok = false;
881 state->crosses[i] = state->crosses[j] = true;
882 }
883 }
884 }
885
886 /*
887 * e == NULL if we've gone through all the edge pairs
888 * without finding a crossing.
889 */
890 if (ok)
891 state->completed = true;
892}
893#endif
894
895static game_state *new_game(midend *me, const game_params *params,
896 const char *desc)
897{
898 int n = params->n;
899 game_state *state = snew(game_state);
900 int a, b;
901
902 state->params = *params;
903 state->w = state->h = COORDLIMIT(n);
904 state->pts = snewn(n, point);
905 make_circle(state->pts, n, state->w);
906 state->graph = snew(struct graph);
907 state->graph->refcount = 1;
908 state->graph->edges = newtree234(edgecmp);
909#ifndef EDITOR
910 state->completed = state->cheated = state->just_solved = false;
911#endif
912
913 while (*desc) {
914 a = atoi(desc);
915 assert(a >= 0 && a < params->n);
916 while (*desc && isdigit((unsigned char)*desc)) desc++;
917 assert(*desc == '-');
918 desc++; /* eat dash */
919 b = atoi(desc);
920 assert(b >= 0 && b < params->n);
921 while (*desc && isdigit((unsigned char)*desc)) desc++;
922 if (*desc) {
923 assert(*desc == ',');
924 desc++; /* eat comma */
925 }
926 addedge(state->graph->edges, a, b);
927 }
928
929#ifndef EDITOR
930 state->crosses = snewn(count234(state->graph->edges), int);
931 mark_crossings(state); /* sets up `crosses' and `completed' */
932#endif
933
934 return state;
935}
936
937static game_state *dup_game(const game_state *state)
938{
939 int n = state->params.n;
940 game_state *ret = snew(game_state);
941
942 ret->params = state->params;
943 ret->w = state->w;
944 ret->h = state->h;
945 ret->pts = snewn(n, point);
946 memcpy(ret->pts, state->pts, n * sizeof(point));
947#ifndef EDITOR
948 ret->graph = state->graph;
949 ret->graph->refcount++;
950 ret->completed = state->completed;
951 ret->cheated = state->cheated;
952 ret->just_solved = state->just_solved;
953 ret->crosses = snewn(count234(ret->graph->edges), int);
954 memcpy(ret->crosses, state->crosses,
955 count234(ret->graph->edges) * sizeof(int));
956#else
957 /* For the graph editor, we must clone the whole graph */
958 ret->graph = snew(struct graph);
959 ret->graph->refcount = 1;
960 ret->graph->edges = newtree234(edgecmp);
961 {
962 int i;
963 struct edge *edge;
964 for (i = 0; (edge = index234(state->graph->edges, i)) != NULL; i++) {
965 addedge(ret->graph->edges, edge->a, edge->b);
966 }
967 }
968#endif
969
970 return ret;
971}
972
973static void free_game(game_state *state)
974{
975 if (--state->graph->refcount <= 0) {
976 edge *e;
977 while ((e = delpos234(state->graph->edges, 0)) != NULL)
978 sfree(e);
979 freetree234(state->graph->edges);
980 sfree(state->graph);
981 }
982#ifndef EDITOR
983 sfree(state->crosses);
984#endif
985 sfree(state->pts);
986 sfree(state);
987}
988
989#ifndef EDITOR
990static char *solve_game(const game_state *state, const game_state *currstate,
991 const char *aux, const char **error)
992{
993 int n = state->params.n;
994 int matrix[4];
995 point *pts;
996 int i, j, besti;
997 float bestd;
998 char buf[80], *ret;
999 int retlen, retsize;
1000
1001 if (!aux) {
1002 *error = "Solution not known for this puzzle";
1003 return NULL;
1004 }
1005
1006 /*
1007 * Decode the aux_info to get the original point positions.
1008 */
1009 pts = snewn(n, point);
1010 aux++; /* eat 'S' */
1011 for (i = 0; i < n; i++) {
1012 int p, k;
1013 long x, y, d;
1014 int ret = sscanf(aux, ";P%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k);
1015 if (ret != 4 || p != i) {
1016 *error = "Internal error: aux_info badly formatted";
1017 sfree(pts);
1018 return NULL;
1019 }
1020 pts[i].x = x;
1021 pts[i].y = y;
1022 pts[i].d = d;
1023 aux += k;
1024 }
1025
1026 /*
1027 * Now go through eight possible symmetries of the point set.
1028 * For each one, work out the sum of the Euclidean distances
1029 * between the points' current positions and their new ones.
1030 *
1031 * We're squaring distances here, which means we're at risk of
1032 * integer overflow. Fortunately, there's no real need to be
1033 * massively careful about rounding errors, since this is a
1034 * non-essential bit of the code; so I'll just work in floats
1035 * internally.
1036 */
1037 besti = -1;
1038 bestd = 0.0F;
1039
1040 for (i = 0; i < 8; i++) {
1041 float d;
1042
1043 matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
1044 matrix[i & 1] = (i & 2) ? +1 : -1;
1045 matrix[3-(i&1)] = (i & 4) ? +1 : -1;
1046
1047 d = 0.0F;
1048 for (j = 0; j < n; j++) {
1049 float px = (float)pts[j].x / pts[j].d;
1050 float py = (float)pts[j].y / pts[j].d;
1051 float sx = (float)currstate->pts[j].x / currstate->pts[j].d;
1052 float sy = (float)currstate->pts[j].y / currstate->pts[j].d;
1053 float cx = (float)currstate->w / 2;
1054 float cy = (float)currstate->h / 2;
1055 float ox, oy, dx, dy;
1056
1057 px -= cx;
1058 py -= cy;
1059
1060 ox = matrix[0] * px + matrix[1] * py;
1061 oy = matrix[2] * px + matrix[3] * py;
1062
1063 ox += cx;
1064 oy += cy;
1065
1066 dx = ox - sx;
1067 dy = oy - sy;
1068
1069 d += dx*dx + dy*dy;
1070 }
1071
1072 if (besti < 0 || bestd > d) {
1073 besti = i;
1074 bestd = d;
1075 }
1076 }
1077
1078 assert(besti >= 0);
1079
1080 /*
1081 * Now we know which symmetry is closest to the points' current
1082 * positions. Use it.
1083 */
1084 matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0;
1085 matrix[besti & 1] = (besti & 2) ? +1 : -1;
1086 matrix[3-(besti&1)] = (besti & 4) ? +1 : -1;
1087
1088 retsize = 256;
1089 ret = snewn(retsize, char);
1090 retlen = 0;
1091 ret[retlen++] = 'S';
1092 ret[retlen] = '\0';
1093
1094 for (i = 0; i < n; i++) {
1095 float px = (float)pts[i].x / pts[i].d;
1096 float py = (float)pts[i].y / pts[i].d;
1097 float cx = (float)currstate->w / 2;
1098 float cy = (float)currstate->h / 2;
1099 float ox, oy;
1100 int extra;
1101
1102 px -= cx;
1103 py -= cy;
1104
1105 ox = matrix[0] * px + matrix[1] * py;
1106 oy = matrix[2] * px + matrix[3] * py;
1107
1108 ox += cx;
1109 oy += cy;
1110
1111 /*
1112 * Use a fixed denominator of 2, because we know the
1113 * original points were on an integer grid offset by 1/2.
1114 */
1115 pts[i].d = 2;
1116 ox *= pts[i].d;
1117 oy *= pts[i].d;
1118 pts[i].x = (long)(ox + 0.5F);
1119 pts[i].y = (long)(oy + 0.5F);
1120
1121 extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i,
1122 pts[i].x, pts[i].y, pts[i].d);
1123 if (retlen + extra >= retsize) {
1124 retsize = retlen + extra + 256;
1125 ret = sresize(ret, retsize, char);
1126 }
1127 strcpy(ret + retlen, buf);
1128 retlen += extra;
1129 }
1130
1131 sfree(pts);
1132
1133 return ret;
1134}
1135#endif /* EDITOR */
1136
1137#ifdef EDITOR
1138static bool game_can_format_as_text_now(const game_params *params)
1139{
1140 return true;
1141}
1142
1143static char *game_text_format(const game_state *state)
1144{
1145 return encode_graph(&state->params, state->graph->edges, NULL);
1146}
1147#endif /* EDITOR */
1148
1149typedef enum DragType { DRAG_MOVE_POINT, DRAG_TOGGLE_EDGE } DragType;
1150
1151struct game_ui {
1152 /* Invariant: at most one of {dragpoint, cursorpoint} may be valid
1153 * at any time. */
1154 int dragpoint; /* point being dragged; -1 if none */
1155 int cursorpoint; /* point being highlighted, but
1156 * not dragged by the cursor,
1157 * again -1 if none */
1158
1159 point newpoint; /* where it's been dragged to so far */
1160 bool just_dragged; /* reset in game_changed_state */
1161 bool just_moved; /* _set_ in game_changed_state */
1162 float anim_length;
1163
1164 DragType dragtype;
1165
1166 /*
1167 * User preference option to snap dragged points to a coarse-ish
1168 * grid. Requested by a user who otherwise found themself spending
1169 * too much time struggling to get lines nicely horizontal or
1170 * vertical.
1171 */
1172 bool snap_to_grid;
1173
1174 /*
1175 * User preference option to highlight graph edges involved in a
1176 * crossing.
1177 */
1178 bool show_crossed_edges;
1179
1180 /*
1181 * User preference option to show vertices as numbers instead of
1182 * circular blobs, so you can easily tell them apart.
1183 */
1184 bool vertex_numbers;
1185};
1186
1187static game_ui *new_ui(const game_state *state)
1188{
1189 game_ui *ui = snew(game_ui);
1190 ui->dragpoint = -1;
1191 ui->cursorpoint = -1;
1192 ui->just_moved = ui->just_dragged = false;
1193 ui->snap_to_grid = false;
1194 ui->show_crossed_edges = false;
1195 ui->vertex_numbers = false;
1196 return ui;
1197}
1198
1199static config_item *get_prefs(game_ui *ui)
1200{
1201 config_item *cfg;
1202
1203 cfg = snewn(N_PREF_ITEMS+1, config_item);
1204
1205 cfg[PREF_SNAP_TO_GRID].name = "Snap points to a grid";
1206 cfg[PREF_SNAP_TO_GRID].kw = "snap-to-grid";
1207 cfg[PREF_SNAP_TO_GRID].type = C_BOOLEAN;
1208 cfg[PREF_SNAP_TO_GRID].u.boolean.bval = ui->snap_to_grid;
1209
1210 cfg[PREF_SHOW_CROSSED_EDGES].name = "Show edges that cross another edge";
1211 cfg[PREF_SHOW_CROSSED_EDGES].kw = "show-crossed-edges";
1212 cfg[PREF_SHOW_CROSSED_EDGES].type = C_BOOLEAN;
1213 cfg[PREF_SHOW_CROSSED_EDGES].u.boolean.bval = ui->show_crossed_edges;
1214
1215 cfg[PREF_VERTEX_STYLE].name = "Display style for vertices";
1216 cfg[PREF_VERTEX_STYLE].kw = "vertex-style";
1217 cfg[PREF_VERTEX_STYLE].type = C_CHOICES;
1218 cfg[PREF_VERTEX_STYLE].u.choices.choicenames = ":Circles:Numbers";
1219 cfg[PREF_VERTEX_STYLE].u.choices.choicekws = ":circle:number";
1220 cfg[PREF_VERTEX_STYLE].u.choices.selected = ui->vertex_numbers;
1221
1222 cfg[N_PREF_ITEMS].name = NULL;
1223 cfg[N_PREF_ITEMS].type = C_END;
1224
1225 return cfg;
1226}
1227
1228static void set_prefs(game_ui *ui, const config_item *cfg)
1229{
1230 ui->snap_to_grid = cfg[PREF_SNAP_TO_GRID].u.boolean.bval;
1231 ui->show_crossed_edges = cfg[PREF_SHOW_CROSSED_EDGES].u.boolean.bval;
1232 ui->vertex_numbers = cfg[PREF_VERTEX_STYLE].u.choices.selected;
1233}
1234
1235static void free_ui(game_ui *ui)
1236{
1237 sfree(ui);
1238}
1239
1240static void game_changed_state(game_ui *ui, const game_state *oldstate,
1241 const game_state *newstate)
1242{
1243 ui->dragpoint = -1;
1244 ui->just_moved = ui->just_dragged;
1245 ui->just_dragged = false;
1246}
1247
1248struct game_drawstate {
1249 long tilesize;
1250 int bg, dragpoint, cursorpoint;
1251 long *x, *y;
1252};
1253
1254static void place_dragged_point(const game_state *state, game_ui *ui,
1255 const game_drawstate *ds, int x, int y)
1256{
1257 if (ui->snap_to_grid) {
1258 /*
1259 * We snap points to a grid that has n-1 vertices on each
1260 * side. This should be large enough to permit a straight-
1261 * line drawing of any n-vertex planar graph, and moreover,
1262 * any specific planar embedding of that graph.
1263 *
1264 * Source: David Eppstein's book 'Forbidden Configurations in
1265 * Discrete Geometry' mentions (section 16.3, page 182) that
1266 * the point configuration he describes as GRID(n-1,n-1) -
1267 * that is, the vertices of a square grid with n-1 vertices on
1268 * each side - is universal for n-vertex planar graphs. In
1269 * other words (from definitions earlier in the chapter), if a
1270 * graph G admits any drawing in the plane at all, then it can
1271 * be drawn with straight lines, and with all vertices being
1272 * vertices of that grid.
1273 *
1274 * That fact by itself only says that _some_ planar embedding
1275 * of G can be drawn in this grid. We'd prefer that _all_
1276 * embeddings of G can be so drawn, because 'snap to grid' is
1277 * supposed to be a UI affordance, not an extra puzzle
1278 * challenge, so we don't want to constrain the player's
1279 * choice of planar embedding.
1280 *
1281 * But it doesn't make a difference. Proof: given a specific
1282 * planar embedding of G, triangulate it, by adding extra
1283 * edges to every face of degree > 3. When this process
1284 * terminates with every face a triangle, we have a new graph
1285 * G' such that no edge can be added without it ceasing to be
1286 * planar. Standard theorems say that a maximal planar graph
1287 * is 3-connected, and that a 3-connected planar graph has a
1288 * _unique_ embedding. So any drawing of G' in the plane can
1289 * be converted into a drawing of G in the desired embedding,
1290 * by simply removing all the extra edges that we added to
1291 * turn G into G'. And G' is still an n-vertex planar graph,
1292 * hence it can be drawn in GRID(n-1,n-1). []
1293 */
1294 int d = state->params.n - 1;
1295
1296 /* Calculate position in terms of the snapping grid. */
1297 x = d * x / (state->w * ds->tilesize);
1298 y = d * y / (state->h * ds->tilesize);
1299 /* Convert to standard co-ordinates, applying a half-square offset. */
1300 ui->newpoint.x = (x * 2 + 1) * state->w;
1301 ui->newpoint.y = (y * 2 + 1) * state->h;
1302 ui->newpoint.d = d * 2;
1303 } else {
1304 ui->newpoint.x = x;
1305 ui->newpoint.y = y;
1306 ui->newpoint.d = ds->tilesize;
1307 }
1308}
1309
1310static float normsq(point pt) {
1311 return (pt.x * pt.x + pt.y * pt.y) / (pt.d * pt.d);
1312}
1313
1314/*
1315 * Find a vertex within DRAG_THRESHOLD of the pointer, or return -1 if
1316 * no such point exists. In case of more than one, we return the one
1317 * _nearest_ to the pointer, so that if two points are very close it's
1318 * still possible to drag a specific one of them.
1319 */
1320static int point_under_mouse(const game_state *state,
1321 const game_drawstate *ds, int x, int y)
1322{
1323 int n = state->params.n;
1324 int i, best;
1325 long bestd;
1326
1327 best = -1;
1328 bestd = 0;
1329
1330 for (i = 0; i < n; i++) {
1331 long px = state->pts[i].x * ds->tilesize / state->pts[i].d;
1332 long py = state->pts[i].y * ds->tilesize / state->pts[i].d;
1333 long dx = px - x;
1334 long dy = py - y;
1335 long d = dx*dx + dy*dy;
1336
1337 if (best == -1 || bestd > d) {
1338 best = i;
1339 bestd = d;
1340 }
1341 }
1342
1343 if (bestd <= DRAG_THRESHOLD * DRAG_THRESHOLD)
1344 return best;
1345
1346 return -1;
1347}
1348
1349static char *interpret_move(const game_state *state, game_ui *ui,
1350 const game_drawstate *ds,
1351 int x, int y, int button)
1352{
1353 int n = state->params.n;
1354
1355 if (IS_MOUSE_DOWN(button)) {
1356 int p = point_under_mouse(state, ds, x, y);
1357 if (p >= 0) {
1358 ui->dragtype = DRAG_MOVE_POINT;
1359#ifdef EDITOR
1360 if (button == RIGHT_BUTTON)
1361 ui->dragtype = DRAG_TOGGLE_EDGE;
1362#endif
1363
1364 ui->dragpoint = p;
1365 ui->cursorpoint = -1; /* eliminate the cursor point, if any */
1366 if (ui->dragtype == DRAG_MOVE_POINT)
1367 place_dragged_point(state, ui, ds, x, y);
1368 return MOVE_UI_UPDATE;
1369 }
1370 return MOVE_NO_EFFECT;
1371 } else if (IS_MOUSE_DRAG(button) && ui->dragpoint >= 0 &&
1372 ui->dragtype == DRAG_MOVE_POINT) {
1373 place_dragged_point(state, ui, ds, x, y);
1374 return MOVE_UI_UPDATE;
1375 } else if (IS_MOUSE_RELEASE(button) && ui->dragpoint >= 0 &&
1376 ui->dragtype == DRAG_MOVE_POINT) {
1377 int p = ui->dragpoint;
1378 char buf[80];
1379
1380 ui->dragpoint = -1; /* terminate drag, no matter what */
1381 ui->cursorpoint = -1; /* also eliminate the cursor point */
1382
1383 /*
1384 * First, see if we're within range. The user can cancel a
1385 * drag by dragging the point right off the window.
1386 */
1387 if (ui->newpoint.x < 0 ||
1388 ui->newpoint.x >= (long)state->w*ui->newpoint.d ||
1389 ui->newpoint.y < 0 ||
1390 ui->newpoint.y >= (long)state->h*ui->newpoint.d)
1391 return MOVE_UI_UPDATE;
1392
1393 /*
1394 * We aren't cancelling the drag. Construct a move string
1395 * indicating where this point is going to.
1396 */
1397 sprintf(buf, "P%d:%ld,%ld/%ld", p,
1398 ui->newpoint.x, ui->newpoint.y, ui->newpoint.d);
1399 ui->just_dragged = true;
1400 return dupstr(buf);
1401#ifdef EDITOR
1402 } else if (IS_MOUSE_DRAG(button) && ui->dragpoint >= 0 &&
1403 ui->dragtype == DRAG_TOGGLE_EDGE) {
1404 ui->cursorpoint = point_under_mouse(state, ds, x, y);
1405 return MOVE_UI_UPDATE;
1406 } else if (IS_MOUSE_RELEASE(button) && ui->dragpoint >= 0 &&
1407 ui->dragtype == DRAG_TOGGLE_EDGE) {
1408 int p = ui->dragpoint;
1409 int q = point_under_mouse(state, ds, x, y);
1410 char buf[80];
1411
1412 ui->dragpoint = -1; /* terminate drag, no matter what */
1413 ui->cursorpoint = -1; /* also eliminate the cursor point */
1414
1415 if (q < 0 || p == q)
1416 return MOVE_UI_UPDATE;
1417
1418 sprintf(buf, "E%c%d,%d",
1419 isedge(state->graph->edges, p, q) ? 'D' : 'A',
1420 p, q);
1421 return dupstr(buf);
1422#endif /* EDITOR */
1423 } else if (IS_MOUSE_DRAG(button)) {
1424 return MOVE_NO_EFFECT;
1425 } else if (IS_MOUSE_RELEASE(button)) {
1426 assert(ui->dragpoint == -1);
1427 return MOVE_NO_EFFECT;
1428 }
1429 else if(IS_CURSOR_MOVE(button)) {
1430 if(ui->dragpoint < 0) {
1431 /*
1432 * We're selecting a point with the cursor keys.
1433 *
1434 * If no point is currently highlighted, we assume the "0"
1435 * point is highlighted to begin. Then, we search all the
1436 * points and find the nearest one (by Euclidean distance)
1437 * in the quadrant corresponding to the cursor key
1438 * direction. A point is in the right quadrant if and only
1439 * if the azimuth angle to that point from the cursor
1440 * point is within a [-45 deg, +45 deg] interval from the
1441 * direction vector of the cursor key.
1442 *
1443 * An important corner case here is if another point is in
1444 * the exact same location as the currently highlighted
1445 * point (which is a possibility with the "snap to grid"
1446 * preference). In this case, we do not consider the other
1447 * point as a candidate point, so as to prevent the cursor
1448 * from being "stuck" on any point. The player can still
1449 * select the overlapped point by dragging the highlighted
1450 * point away and then navigating back.
1451 */
1452 int i, best = -1;
1453 float bestd = 0;
1454
1455 if(ui->cursorpoint < 0) {
1456 ui->cursorpoint = 0;
1457 }
1458
1459 point cur = state->pts[ui->cursorpoint];
1460
1461 for (i = 0; i < n; i++) {
1462 point delta;
1463 float distsq;
1464 point p = state->pts[i];
1465 int right_direction = false;
1466
1467 if(i == ui->cursorpoint)
1468 continue;
1469
1470 /* Compute the vector p - cur. Check that it lies in
1471 * the correct quadrant. */
1472 delta.x = p.x * cur.d - cur.x * p.d;
1473 delta.y = p.y * cur.d - cur.y * p.d;
1474 delta.d = cur.d * p.d;
1475
1476 if(delta.x == 0 && delta.y == 0)
1477 continue; /* overlaps cursor point - skip */
1478
1479 switch(button) {
1480 case CURSOR_UP:
1481 right_direction = (delta.y <= -delta.x) && (delta.y <= delta.x);
1482 break;
1483 case CURSOR_DOWN:
1484 right_direction = (delta.y >= -delta.x) && (delta.y >= delta.x);
1485 break;
1486 case CURSOR_LEFT:
1487 right_direction = (delta.y >= delta.x) && (delta.y <= -delta.x);
1488 break;
1489 case CURSOR_RIGHT:
1490 right_direction = (delta.y <= delta.x) && (delta.y >= -delta.x);
1491 break;
1492 }
1493
1494 if(!right_direction)
1495 continue;
1496
1497 /* Compute squared Euclidean distance */
1498 distsq = normsq(delta);
1499
1500 if (best == -1 || distsq < bestd) {
1501 best = i;
1502 bestd = distsq;
1503 }
1504 }
1505
1506 if(best >= 0) {
1507 ui->cursorpoint = best;
1508 return MOVE_UI_UPDATE;
1509 }
1510 }
1511 else if(ui->dragpoint >= 0) {
1512 /* Dragging a point with the cursor keys. */
1513 int movement_increment = ds->tilesize / 2;
1514 int dx = 0, dy = 0;
1515
1516 switch(button) {
1517 case CURSOR_UP:
1518 dy = -movement_increment;
1519 break;
1520 case CURSOR_DOWN:
1521 dy = movement_increment;
1522 break;
1523 case CURSOR_LEFT:
1524 dx = -movement_increment;
1525 break;
1526 case CURSOR_RIGHT:
1527 dx = movement_increment;
1528 break;
1529 default:
1530 break;
1531 }
1532
1533 /* This code has a slightly inconvenient interaction with
1534 * the snap to grid feature: if the point being dragged
1535 * originates on a non-grid point which is in the bottom
1536 * half or right half (or both) of a grid cell (a 75%
1537 * probability), then dragging point right (if it
1538 * originates from the right half) or down (if it
1539 * originates from the bottom half) will cause the point
1540 * to move one more grid cell than intended in that
1541 * direction. I (F. Wei) it wasn't worth handling this
1542 * corner case - if anyone feels inclined, please feel
1543 * free to do so. */
1544 place_dragged_point(state, ui, ds,
1545 ui->newpoint.x * ds->tilesize / ui->newpoint.d + dx,
1546 ui->newpoint.y * ds->tilesize / ui->newpoint.d + dy);
1547 return MOVE_UI_UPDATE;
1548 }
1549 } else if(button == CURSOR_SELECT) {
1550 if(ui->dragpoint < 0 && ui->cursorpoint >= 0) {
1551 /* begin drag */
1552 ui->dragtype = DRAG_MOVE_POINT;
1553 ui->dragpoint = ui->cursorpoint;
1554 ui->cursorpoint = -1;
1555 ui->newpoint.x = state->pts[ui->dragpoint].x * ds->tilesize / state->pts[ui->dragpoint].d;
1556 ui->newpoint.y = state->pts[ui->dragpoint].y * ds->tilesize / state->pts[ui->dragpoint].d;
1557 ui->newpoint.d = ds->tilesize;
1558 return MOVE_UI_UPDATE;
1559 }
1560 else if(ui->dragpoint >= 0) {
1561 /* end drag */
1562 int p = ui->dragpoint;
1563 char buf[80];
1564
1565 ui->cursorpoint = ui->dragpoint;
1566 ui->dragpoint = -1; /* terminate drag, no matter what */
1567
1568 /*
1569 * First, see if we're within range. The user can cancel a
1570 * drag by dragging the point right off the window.
1571 */
1572 if (ui->newpoint.x < 0 ||
1573 ui->newpoint.x >= (long)state->w*ui->newpoint.d ||
1574 ui->newpoint.y < 0 ||
1575 ui->newpoint.y >= (long)state->h*ui->newpoint.d)
1576 return MOVE_UI_UPDATE;
1577
1578 /*
1579 * We aren't cancelling the drag. Construct a move string
1580 * indicating where this point is going to.
1581 */
1582 sprintf(buf, "P%d:%ld,%ld/%ld", p,
1583 ui->newpoint.x, ui->newpoint.y, ui->newpoint.d);
1584 ui->just_dragged = true;
1585 return dupstr(buf);
1586 }
1587 else if(ui->cursorpoint < 0) {
1588 ui->cursorpoint = 0;
1589 return MOVE_UI_UPDATE;
1590 }
1591 } else if(STRIP_BUTTON_MODIFIERS(button) == CURSOR_SELECT2 ||
1592 STRIP_BUTTON_MODIFIERS(button) == '\t') {
1593 /* Use spacebar or tab to cycle through the points. Shift
1594 * reverses cycle direction. */
1595 if(ui->dragpoint >= 0)
1596 return MOVE_NO_EFFECT;
1597 if(ui->cursorpoint < 0) {
1598 ui->cursorpoint = 0;
1599 return MOVE_UI_UPDATE;
1600 }
1601 assert(ui->cursorpoint >= 0);
1602
1603 /* cursorpoint is valid - increment it */
1604 int direction = (button & MOD_SHFT) ? -1 : 1;
1605 ui->cursorpoint = (ui->cursorpoint + direction + state->params.n) % state->params.n;
1606 return MOVE_UI_UPDATE;
1607 }
1608
1609 return MOVE_UNUSED;
1610}
1611
1612static game_state *execute_move(const game_state *state, const char *move)
1613{
1614 int n = state->params.n;
1615 int p, k;
1616 long x, y, d;
1617 game_state *ret = dup_game(state);
1618
1619#ifndef EDITOR
1620 ret->just_solved = false;
1621#endif
1622
1623#ifdef EDITOR
1624 if (*move == 'E') {
1625 bool add;
1626 int a, b;
1627
1628 move++;
1629 if (*move == 'A')
1630 add = true;
1631 else if (*move == 'D')
1632 add = false;
1633 else {
1634 free_game(ret);
1635 return NULL;
1636 }
1637
1638 move++;
1639 a = atoi(move);
1640 while (*move && isdigit((unsigned char)*move))
1641 move++;
1642
1643 if (*move != ',') {
1644 free_game(ret);
1645 return NULL;
1646 }
1647 move++;
1648
1649 b = atoi(move);
1650
1651 if (a >= 0 && a < n && b >= 0 && b < n && a != b) {
1652 if (add)
1653 addedge(ret->graph->edges, a, b);
1654 else
1655 deledge(ret->graph->edges, a, b);
1656 return ret;
1657 } else {
1658 free_game(ret);
1659 return NULL;
1660 }
1661 }
1662#endif
1663
1664 while (*move) {
1665#ifndef EDITOR
1666 if (*move == 'S') {
1667 move++;
1668 if (*move == ';') move++;
1669 ret->cheated = ret->just_solved = true;
1670 }
1671#endif
1672 if (*move == 'P' &&
1673 sscanf(move+1, "%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k) == 4 &&
1674 p >= 0 && p < n && d > 0) {
1675 ret->pts[p].x = x;
1676 ret->pts[p].y = y;
1677 ret->pts[p].d = d;
1678
1679 move += k+1;
1680 if (*move == ';') move++;
1681 } else {
1682 free_game(ret);
1683 return NULL;
1684 }
1685 }
1686
1687#ifndef EDITOR
1688 mark_crossings(ret);
1689#endif
1690
1691 return ret;
1692}
1693
1694/* ----------------------------------------------------------------------
1695 * Drawing routines.
1696 */
1697
1698static void game_compute_size(const game_params *params, int tilesize,
1699 const game_ui *ui, int *x, int *y)
1700{
1701 *x = *y = COORDLIMIT(params->n) * tilesize;
1702}
1703
1704static void game_set_size(drawing *dr, game_drawstate *ds,
1705 const game_params *params, int tilesize)
1706{
1707 ds->tilesize = tilesize;
1708}
1709
1710static float *game_colours(frontend *fe, int *ncolours)
1711{
1712 float *ret = snewn(3 * NCOLOURS, float);
1713
1714 /*
1715 * COL_BACKGROUND is what we use as the normal background colour.
1716 * Unusually, though, it isn't colour #0: COL_SYSBACKGROUND, a bit
1717 * darker, takes that place. This means that if the user resizes
1718 * an Untangle window so as to change its aspect ratio, the
1719 * still-square playable area will be distinguished from the dead
1720 * space around it.
1721 */
1722 game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_SYSBACKGROUND);
1723
1724 ret[COL_LINE * 3 + 0] = 0.0F;
1725 ret[COL_LINE * 3 + 1] = 0.0F;
1726 ret[COL_LINE * 3 + 2] = 0.0F;
1727
1728 ret[COL_CROSSEDLINE * 3 + 0] = 1.0F;
1729 ret[COL_CROSSEDLINE * 3 + 1] = 0.0F;
1730 ret[COL_CROSSEDLINE * 3 + 2] = 0.0F;
1731
1732 ret[COL_OUTLINE * 3 + 0] = 0.0F;
1733 ret[COL_OUTLINE * 3 + 1] = 0.0F;
1734 ret[COL_OUTLINE * 3 + 2] = 0.0F;
1735
1736 ret[COL_POINT * 3 + 0] = 0.0F;
1737 ret[COL_POINT * 3 + 1] = 0.0F;
1738 ret[COL_POINT * 3 + 2] = 1.0F;
1739
1740 ret[COL_DRAGPOINT * 3 + 0] = 1.0F;
1741 ret[COL_DRAGPOINT * 3 + 1] = 1.0F;
1742 ret[COL_DRAGPOINT * 3 + 2] = 1.0F;
1743
1744 ret[COL_CURSORPOINT * 3 + 0] = 0.5F;
1745 ret[COL_CURSORPOINT * 3 + 1] = 0.5F;
1746 ret[COL_CURSORPOINT * 3 + 2] = 0.5F;
1747
1748 ret[COL_NEIGHBOUR * 3 + 0] = 1.0F;
1749 ret[COL_NEIGHBOUR * 3 + 1] = 0.0F;
1750 ret[COL_NEIGHBOUR * 3 + 2] = 0.0F;
1751
1752 ret[COL_FLASH1 * 3 + 0] = 0.5F;
1753 ret[COL_FLASH1 * 3 + 1] = 0.5F;
1754 ret[COL_FLASH1 * 3 + 2] = 0.5F;
1755
1756 ret[COL_FLASH2 * 3 + 0] = 1.0F;
1757 ret[COL_FLASH2 * 3 + 1] = 1.0F;
1758 ret[COL_FLASH2 * 3 + 2] = 1.0F;
1759
1760 *ncolours = NCOLOURS;
1761 return ret;
1762}
1763
1764static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1765{
1766 struct game_drawstate *ds = snew(struct game_drawstate);
1767 int i;
1768
1769 ds->tilesize = 0;
1770 ds->x = snewn(state->params.n, long);
1771 ds->y = snewn(state->params.n, long);
1772 for (i = 0; i < state->params.n; i++)
1773 ds->x[i] = ds->y[i] = -1;
1774 ds->bg = -1;
1775 ds->dragpoint = -1;
1776 ds->cursorpoint = -1;
1777
1778 return ds;
1779}
1780
1781static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1782{
1783 sfree(ds->y);
1784 sfree(ds->x);
1785 sfree(ds);
1786}
1787
1788static point mix(point a, point b, float distance)
1789{
1790 point ret;
1791
1792 ret.d = a.d * b.d;
1793 ret.x = (long)(a.x * b.d + distance * (b.x * a.d - a.x * b.d));
1794 ret.y = (long)(a.y * b.d + distance * (b.y * a.d - a.y * b.d));
1795
1796 return ret;
1797}
1798
1799static void game_redraw(drawing *dr, game_drawstate *ds,
1800 const game_state *oldstate, const game_state *state,
1801 int dir, const game_ui *ui,
1802 float animtime, float flashtime)
1803{
1804 int w, h;
1805 edge *e;
1806 int i, j;
1807 int bg;
1808 bool points_moved;
1809#ifdef EDITOR
1810 bool edges_changed;
1811#endif
1812
1813 /*
1814 * There's no terribly sensible way to do partial redraws of
1815 * this game, so I'm going to have to resort to redrawing the
1816 * whole thing every time.
1817 */
1818
1819 if (flashtime == 0)
1820 bg = COL_BACKGROUND;
1821 else if ((int)(flashtime * 4 / FLASH_TIME) % 2 == 0)
1822 bg = COL_FLASH1;
1823 else
1824 bg = COL_FLASH2;
1825
1826 /*
1827 * To prevent excessive spinning on redraw during a completion
1828 * flash, we first check to see if _either_ the flash
1829 * background colour has changed _or_ at least one point has
1830 * moved _or_ a drag has begun or ended, and abandon the redraw
1831 * if neither is the case.
1832 *
1833 * Also in this loop we work out the coordinates of all the
1834 * points for this redraw.
1835 */
1836 points_moved = false;
1837 for (i = 0; i < state->params.n; i++) {
1838 point p = state->pts[i];
1839 long x, y;
1840
1841 if (ui->dragpoint == i && ui->dragtype == DRAG_MOVE_POINT)
1842 p = ui->newpoint;
1843
1844 if (oldstate)
1845 p = mix(oldstate->pts[i], p, animtime / ui->anim_length);
1846
1847 x = p.x * ds->tilesize / p.d;
1848 y = p.y * ds->tilesize / p.d;
1849
1850 if (ds->x[i] != x || ds->y[i] != y)
1851 points_moved = true;
1852
1853 ds->x[i] = x;
1854 ds->y[i] = y;
1855 }
1856
1857#ifdef EDITOR
1858 edges_changed = false;
1859 if (oldstate) {
1860 for (i = 0;; i++) {
1861 edge *eold = index234(oldstate->graph->edges, i);
1862 edge *enew = index234(state->graph->edges, i);
1863 if (!eold && !enew)
1864 break;
1865 if (!eold || !enew) {
1866 edges_changed = true;
1867 break;
1868 }
1869 if (eold->a != enew->a || eold->b != enew->b) {
1870 edges_changed = true;
1871 break;
1872 }
1873 }
1874 }
1875#endif
1876
1877 if (ds->bg == bg &&
1878 ds->dragpoint == ui->dragpoint &&
1879 ds->cursorpoint == ui->cursorpoint &&
1880#ifdef EDITOR
1881 !edges_changed &&
1882#endif
1883 !points_moved)
1884 return; /* nothing to do */
1885
1886 ds->dragpoint = ui->dragpoint;
1887 ds->cursorpoint = ui->cursorpoint;
1888 ds->bg = bg;
1889
1890 game_compute_size(&state->params, ds->tilesize, ui, &w, &h);
1891 draw_rect(dr, 0, 0, w, h, bg);
1892
1893 /*
1894 * Draw the edges.
1895 */
1896
1897 for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) {
1898#ifndef EDITOR
1899 int colour = ui->show_crossed_edges &&
1900 (oldstate?oldstate:state)->crosses[i] ?
1901 COL_CROSSEDLINE : COL_LINE;
1902#else
1903 int colour = COL_LINE;
1904#endif
1905
1906 draw_line(dr, ds->x[e->a], ds->y[e->a], ds->x[e->b], ds->y[e->b],
1907 colour);
1908 }
1909
1910 /*
1911 * Draw the points.
1912 *
1913 * When dragging, we vary the point colours to highlight the drag
1914 * point and neighbour points. The draw order is defined so that
1915 * the most relevant points (i.e., the dragged point and cursor
1916 * point) are drawn last, so they appear on top of other points.
1917 */
1918 static const int draw_order[] = {
1919 COL_POINT,
1920 COL_NEIGHBOUR,
1921 COL_CURSORPOINT,
1922 COL_DRAGPOINT
1923 };
1924
1925 for (j = 0; j < 4; j++) {
1926 int thisc = draw_order[j];
1927 for (i = 0; i < state->params.n; i++) {
1928 int c;
1929
1930 if (ui->dragpoint == i) {
1931 c = COL_DRAGPOINT;
1932 } else if(ui->cursorpoint == i) {
1933 c = COL_CURSORPOINT;
1934 } else if (ui->dragpoint >= 0 &&
1935 isedge(state->graph->edges, ui->dragpoint, i)) {
1936 c = COL_NEIGHBOUR;
1937 } else {
1938 c = COL_POINT;
1939 }
1940
1941 if (c == thisc) {
1942 if (ui->vertex_numbers) {
1943 char buf[80];
1944 draw_circle(dr, ds->x[i], ds->y[i], DRAG_THRESHOLD, bg, bg);
1945 sprintf(buf, "%d", i);
1946 draw_text(dr, ds->x[i], ds->y[i], FONT_VARIABLE,
1947 DRAG_THRESHOLD*3/2,
1948 ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf);
1949 } else {
1950 draw_circle(dr, ds->x[i], ds->y[i], CIRCLE_RADIUS,
1951 c, COL_OUTLINE);
1952 }
1953 }
1954 }
1955 }
1956
1957 draw_update(dr, 0, 0, w, h);
1958}
1959
1960static float game_anim_length(const game_state *oldstate,
1961 const game_state *newstate, int dir, game_ui *ui)
1962{
1963 if (ui->just_moved)
1964 return 0.0F;
1965#ifndef EDITOR
1966 if ((dir < 0 ? oldstate : newstate)->just_solved)
1967 ui->anim_length = SOLVEANIM_TIME;
1968 else
1969 ui->anim_length = ANIM_TIME;
1970#else
1971 ui->anim_length = ANIM_TIME;
1972#endif
1973 return ui->anim_length;
1974}
1975
1976static float game_flash_length(const game_state *oldstate,
1977 const game_state *newstate, int dir, game_ui *ui)
1978{
1979#ifndef EDITOR
1980 if (!oldstate->completed && newstate->completed &&
1981 !oldstate->cheated && !newstate->cheated)
1982 return FLASH_TIME;
1983#endif
1984 return 0.0F;
1985}
1986
1987static void game_get_cursor_location(const game_ui *ui,
1988 const game_drawstate *ds,
1989 const game_state *state,
1990 const game_params *params,
1991 int *x, int *y, int *w, int *h)
1992{
1993 point pt;
1994 if (ui->dragpoint >= 0 && ui->dragtype == DRAG_MOVE_POINT)
1995 pt = ui->newpoint;
1996 else if(ui->cursorpoint >= 0)
1997 pt = state->pts[ui->cursorpoint];
1998 else
1999 return;
2000
2001 int cx = ds->tilesize * pt.x / pt.d;
2002 int cy = ds->tilesize * pt.y / pt.d;
2003
2004 *x = cx - CIRCLE_RADIUS;
2005 *y = cy - CIRCLE_RADIUS;
2006 *w = *h = 2 * CIRCLE_RADIUS + 1;
2007}
2008
2009static int game_status(const game_state *state)
2010{
2011#ifdef EDITOR
2012 return 0;
2013#else
2014 return state->completed ? +1 : 0;
2015#endif
2016}
2017
2018#ifdef COMBINED
2019#define thegame untangle
2020#endif
2021
2022const struct game thegame = {
2023 "Untangle", "games.untangle", "untangle",
2024 default_params,
2025 game_fetch_preset, NULL,
2026 decode_params,
2027 encode_params,
2028 free_params,
2029 dup_params,
2030 true, game_configure, custom_params,
2031 validate_params,
2032 new_game_desc,
2033 validate_desc,
2034 new_game,
2035 dup_game,
2036 free_game,
2037#ifndef EDITOR
2038 true, solve_game,
2039 false, NULL, NULL, /* can_format_as_text_now, text_format */
2040#else
2041 false, NULL,
2042 true, game_can_format_as_text_now, game_text_format,
2043#endif
2044 get_prefs, set_prefs,
2045 new_ui,
2046 free_ui,
2047 NULL, /* encode_ui */
2048 NULL, /* decode_ui */
2049 NULL, /* game_request_keys */
2050 game_changed_state,
2051 NULL, /* current_key_label */
2052 interpret_move,
2053 execute_move,
2054 PREFERRED_TILESIZE, game_compute_size, game_set_size,
2055 game_colours,
2056 game_new_drawstate,
2057 game_free_drawstate,
2058 game_redraw,
2059 game_anim_length,
2060 game_flash_length,
2061 game_get_cursor_location,
2062 game_status,
2063 false, false, NULL, NULL, /* print_size, print */
2064 false, /* wants_statusbar */
2065 false, NULL, /* timing_state */
2066 SOLVE_ANIMATES, /* flags */
2067};