diff options
author | Franklin Wei <git@fwei.tk> | 2017-04-29 18:21:56 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2017-04-29 18:24:42 -0400 |
commit | 881746789a489fad85aae8317555f73dbe261556 (patch) | |
tree | cec2946362c4698c8db3c10f3242ef546c2c22dd /apps/plugins/puzzles/src/untangle.c | |
parent | 03dd4b92be7dcd5c8ab06da3810887060e06abd5 (diff) | |
download | rockbox-881746789a489fad85aae8317555f73dbe261556.tar.gz rockbox-881746789a489fad85aae8317555f73dbe261556.zip |
puzzles: refactor and resync with upstream
This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.
Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804
Diffstat (limited to 'apps/plugins/puzzles/src/untangle.c')
-rw-r--r-- | apps/plugins/puzzles/src/untangle.c | 1637 |
1 files changed, 1637 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/untangle.c b/apps/plugins/puzzles/src/untangle.c new file mode 100644 index 0000000000..47e839e875 --- /dev/null +++ b/apps/plugins/puzzles/src/untangle.c | |||
@@ -0,0 +1,1637 @@ | |||
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 | * - It would be nice if we could somehow auto-detect a real `long | ||
25 | * long' type on the host platform and use it in place of my | ||
26 | * hand-hacked int64s. It'd be faster and more reliable. | ||
27 | */ | ||
28 | |||
29 | #include <stdio.h> | ||
30 | #include <stdlib.h> | ||
31 | #include <string.h> | ||
32 | #include <assert.h> | ||
33 | #include <ctype.h> | ||
34 | #include <math.h> | ||
35 | |||
36 | #include "puzzles.h" | ||
37 | #include "tree234.h" | ||
38 | |||
39 | #define CIRCLE_RADIUS 6 | ||
40 | #define DRAG_THRESHOLD (CIRCLE_RADIUS * 2) | ||
41 | #define PREFERRED_TILESIZE 64 | ||
42 | #define CURSOR_GRANULARITY 5 | ||
43 | |||
44 | #define FLASH_TIME 0.30F | ||
45 | #define ANIM_TIME 0.13F | ||
46 | #define SOLVEANIM_TIME 0.50F | ||
47 | |||
48 | enum { | ||
49 | COL_SYSBACKGROUND, | ||
50 | COL_BACKGROUND, | ||
51 | COL_LINE, | ||
52 | #ifdef SHOW_CROSSINGS | ||
53 | COL_CROSSEDLINE, | ||
54 | #endif | ||
55 | COL_OUTLINE, | ||
56 | COL_POINT, | ||
57 | COL_DRAGPOINT, | ||
58 | COL_CURSORPOINT, | ||
59 | COL_NEIGHBOUR, | ||
60 | COL_FLASH1, | ||
61 | COL_FLASH2, | ||
62 | NCOLOURS | ||
63 | }; | ||
64 | |||
65 | typedef struct point { | ||
66 | /* | ||
67 | * Points are stored using rational coordinates, with the same | ||
68 | * denominator for both coordinates. | ||
69 | */ | ||
70 | long x, y, d; | ||
71 | } point; | ||
72 | |||
73 | typedef struct edge { | ||
74 | /* | ||
75 | * This structure is implicitly associated with a particular | ||
76 | * point set, so all it has to do is to store two point | ||
77 | * indices. It is required to store them in the order (lower, | ||
78 | * higher), i.e. a < b always. | ||
79 | */ | ||
80 | int a, b; | ||
81 | } edge; | ||
82 | |||
83 | struct game_params { | ||
84 | int n; /* number of points */ | ||
85 | }; | ||
86 | |||
87 | struct graph { | ||
88 | int refcount; /* for deallocation */ | ||
89 | tree234 *edges; /* stores `edge' structures */ | ||
90 | }; | ||
91 | |||
92 | struct game_state { | ||
93 | game_params params; | ||
94 | int w, h; /* extent of coordinate system only */ | ||
95 | point *pts; | ||
96 | #ifdef SHOW_CROSSINGS | ||
97 | int *crosses; /* mark edges which are crossed */ | ||
98 | #endif | ||
99 | struct graph *graph; | ||
100 | int completed, cheated, just_solved; | ||
101 | }; | ||
102 | |||
103 | static int edgecmpC(const void *av, const void *bv) | ||
104 | { | ||
105 | const edge *a = (const edge *)av; | ||
106 | const edge *b = (const edge *)bv; | ||
107 | |||
108 | if (a->a < b->a) | ||
109 | return -1; | ||
110 | else if (a->a > b->a) | ||
111 | return +1; | ||
112 | else if (a->b < b->b) | ||
113 | return -1; | ||
114 | else if (a->b > b->b) | ||
115 | return +1; | ||
116 | return 0; | ||
117 | } | ||
118 | |||
119 | static int edgecmp(void *av, void *bv) { return edgecmpC(av, bv); } | ||
120 | |||
121 | static game_params *default_params(void) | ||
122 | { | ||
123 | game_params *ret = snew(game_params); | ||
124 | |||
125 | ret->n = 10; | ||
126 | |||
127 | return ret; | ||
128 | } | ||
129 | |||
130 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
131 | { | ||
132 | game_params *ret; | ||
133 | int n; | ||
134 | char buf[80]; | ||
135 | |||
136 | switch (i) { | ||
137 | case 0: n = 6; break; | ||
138 | case 1: n = 10; break; | ||
139 | case 2: n = 15; break; | ||
140 | case 3: n = 20; break; | ||
141 | case 4: n = 25; break; | ||
142 | default: return FALSE; | ||
143 | } | ||
144 | |||
145 | sprintf(buf, "%d points", n); | ||
146 | *name = dupstr(buf); | ||
147 | |||
148 | *params = ret = snew(game_params); | ||
149 | ret->n = n; | ||
150 | |||
151 | return TRUE; | ||
152 | } | ||
153 | |||
154 | static void free_params(game_params *params) | ||
155 | { | ||
156 | sfree(params); | ||
157 | } | ||
158 | |||
159 | static game_params *dup_params(const game_params *params) | ||
160 | { | ||
161 | game_params *ret = snew(game_params); | ||
162 | *ret = *params; /* structure copy */ | ||
163 | return ret; | ||
164 | } | ||
165 | |||
166 | static void decode_params(game_params *params, char const *string) | ||
167 | { | ||
168 | params->n = atoi(string); | ||
169 | } | ||
170 | |||
171 | static char *encode_params(const game_params *params, int full) | ||
172 | { | ||
173 | char buf[80]; | ||
174 | |||
175 | sprintf(buf, "%d", params->n); | ||
176 | |||
177 | return dupstr(buf); | ||
178 | } | ||
179 | |||
180 | static config_item *game_configure(const game_params *params) | ||
181 | { | ||
182 | config_item *ret; | ||
183 | char buf[80]; | ||
184 | |||
185 | ret = snewn(3, config_item); | ||
186 | |||
187 | ret[0].name = "Number of points"; | ||
188 | ret[0].type = C_STRING; | ||
189 | sprintf(buf, "%d", params->n); | ||
190 | ret[0].sval = dupstr(buf); | ||
191 | ret[0].ival = 0; | ||
192 | |||
193 | ret[1].name = NULL; | ||
194 | ret[1].type = C_END; | ||
195 | ret[1].sval = NULL; | ||
196 | ret[1].ival = 0; | ||
197 | |||
198 | return ret; | ||
199 | } | ||
200 | |||
201 | static game_params *custom_params(const config_item *cfg) | ||
202 | { | ||
203 | game_params *ret = snew(game_params); | ||
204 | |||
205 | ret->n = atoi(cfg[0].sval); | ||
206 | |||
207 | return ret; | ||
208 | } | ||
209 | |||
210 | static char *validate_params(const game_params *params, int full) | ||
211 | { | ||
212 | if (params->n < 4) | ||
213 | return "Number of points must be at least four"; | ||
214 | return NULL; | ||
215 | } | ||
216 | |||
217 | /* ---------------------------------------------------------------------- | ||
218 | * Small number of 64-bit integer arithmetic operations, to prevent | ||
219 | * integer overflow at the very core of cross(). | ||
220 | */ | ||
221 | |||
222 | typedef struct { | ||
223 | long hi; | ||
224 | unsigned long lo; | ||
225 | } int64; | ||
226 | |||
227 | #define greater64(i,j) ( (i).hi>(j).hi || ((i).hi==(j).hi && (i).lo>(j).lo)) | ||
228 | #define sign64(i) ((i).hi < 0 ? -1 : (i).hi==0 && (i).lo==0 ? 0 : +1) | ||
229 | |||
230 | static int64 mulu32to64(unsigned long x, unsigned long y) | ||
231 | { | ||
232 | unsigned long a, b, c, d, t; | ||
233 | int64 ret; | ||
234 | |||
235 | a = (x & 0xFFFF) * (y & 0xFFFF); | ||
236 | b = (x & 0xFFFF) * (y >> 16); | ||
237 | c = (x >> 16) * (y & 0xFFFF); | ||
238 | d = (x >> 16) * (y >> 16); | ||
239 | |||
240 | ret.lo = a; | ||
241 | ret.hi = d + (b >> 16) + (c >> 16); | ||
242 | t = (b & 0xFFFF) << 16; | ||
243 | ret.lo += t; | ||
244 | if (ret.lo < t) | ||
245 | ret.hi++; | ||
246 | t = (c & 0xFFFF) << 16; | ||
247 | ret.lo += t; | ||
248 | if (ret.lo < t) | ||
249 | ret.hi++; | ||
250 | |||
251 | #ifdef DIAGNOSTIC_VIA_LONGLONG | ||
252 | assert(((unsigned long long)ret.hi << 32) + ret.lo == | ||
253 | (unsigned long long)x * y); | ||
254 | #endif | ||
255 | |||
256 | return ret; | ||
257 | } | ||
258 | |||
259 | static int64 mul32to64(long x, long y) | ||
260 | { | ||
261 | int sign = +1; | ||
262 | int64 ret; | ||
263 | #ifdef DIAGNOSTIC_VIA_LONGLONG | ||
264 | long long realret = (long long)x * y; | ||
265 | #endif | ||
266 | |||
267 | if (x < 0) | ||
268 | x = -x, sign = -sign; | ||
269 | if (y < 0) | ||
270 | y = -y, sign = -sign; | ||
271 | |||
272 | ret = mulu32to64(x, y); | ||
273 | |||
274 | if (sign < 0) { | ||
275 | ret.hi = -ret.hi; | ||
276 | ret.lo = -ret.lo; | ||
277 | if (ret.lo) | ||
278 | ret.hi--; | ||
279 | } | ||
280 | |||
281 | #ifdef DIAGNOSTIC_VIA_LONGLONG | ||
282 | assert(((unsigned long long)ret.hi << 32) + ret.lo == realret); | ||
283 | #endif | ||
284 | |||
285 | return ret; | ||
286 | } | ||
287 | |||
288 | static int64 dotprod64(long a, long b, long p, long q) | ||
289 | { | ||
290 | int64 ab, pq; | ||
291 | |||
292 | ab = mul32to64(a, b); | ||
293 | pq = mul32to64(p, q); | ||
294 | ab.hi += pq.hi; | ||
295 | ab.lo += pq.lo; | ||
296 | if (ab.lo < pq.lo) | ||
297 | ab.hi++; | ||
298 | return ab; | ||
299 | } | ||
300 | |||
301 | /* | ||
302 | * Determine whether the line segments between a1 and a2, and | ||
303 | * between b1 and b2, intersect. We count it as an intersection if | ||
304 | * any of the endpoints lies _on_ the other line. | ||
305 | */ | ||
306 | static int cross(point a1, point a2, point b1, point b2) | ||
307 | { | ||
308 | long b1x, b1y, b2x, b2y, px, py; | ||
309 | int64 d1, d2, d3; | ||
310 | |||
311 | /* | ||
312 | * The condition for crossing is that b1 and b2 are on opposite | ||
313 | * sides of the line a1-a2, and vice versa. We determine this | ||
314 | * by taking the dot product of b1-a1 with a vector | ||
315 | * perpendicular to a2-a1, and similarly with b2-a1, and seeing | ||
316 | * if they have different signs. | ||
317 | */ | ||
318 | |||
319 | /* | ||
320 | * Construct the vector b1-a1. We don't have to worry too much | ||
321 | * about the denominator, because we're only going to check the | ||
322 | * sign of this vector; we just need to get the numerator | ||
323 | * right. | ||
324 | */ | ||
325 | b1x = b1.x * a1.d - a1.x * b1.d; | ||
326 | b1y = b1.y * a1.d - a1.y * b1.d; | ||
327 | /* Now construct b2-a1, and a vector perpendicular to a2-a1, | ||
328 | * in the same way. */ | ||
329 | b2x = b2.x * a1.d - a1.x * b2.d; | ||
330 | b2y = b2.y * a1.d - a1.y * b2.d; | ||
331 | px = a1.y * a2.d - a2.y * a1.d; | ||
332 | py = a2.x * a1.d - a1.x * a2.d; | ||
333 | /* Take the dot products. Here we resort to 64-bit arithmetic. */ | ||
334 | d1 = dotprod64(b1x, px, b1y, py); | ||
335 | d2 = dotprod64(b2x, px, b2y, py); | ||
336 | /* If they have the same non-zero sign, the lines do not cross. */ | ||
337 | if ((sign64(d1) > 0 && sign64(d2) > 0) || | ||
338 | (sign64(d1) < 0 && sign64(d2) < 0)) | ||
339 | return FALSE; | ||
340 | |||
341 | /* | ||
342 | * If the dot products are both exactly zero, then the two line | ||
343 | * segments are collinear. At this point the intersection | ||
344 | * condition becomes whether or not they overlap within their | ||
345 | * line. | ||
346 | */ | ||
347 | if (sign64(d1) == 0 && sign64(d2) == 0) { | ||
348 | /* Construct the vector a2-a1. */ | ||
349 | px = a2.x * a1.d - a1.x * a2.d; | ||
350 | py = a2.y * a1.d - a1.y * a2.d; | ||
351 | /* Determine the dot products of b1-a1 and b2-a1 with this. */ | ||
352 | d1 = dotprod64(b1x, px, b1y, py); | ||
353 | d2 = dotprod64(b2x, px, b2y, py); | ||
354 | /* If they're both strictly negative, the lines do not cross. */ | ||
355 | if (sign64(d1) < 0 && sign64(d2) < 0) | ||
356 | return FALSE; | ||
357 | /* Otherwise, take the dot product of a2-a1 with itself. If | ||
358 | * the other two dot products both exceed this, the lines do | ||
359 | * not cross. */ | ||
360 | d3 = dotprod64(px, px, py, py); | ||
361 | if (greater64(d1, d3) && greater64(d2, d3)) | ||
362 | return FALSE; | ||
363 | } | ||
364 | |||
365 | /* | ||
366 | * We've eliminated the only important special case, and we | ||
367 | * have determined that b1 and b2 are on opposite sides of the | ||
368 | * line a1-a2. Now do the same thing the other way round and | ||
369 | * we're done. | ||
370 | */ | ||
371 | b1x = a1.x * b1.d - b1.x * a1.d; | ||
372 | b1y = a1.y * b1.d - b1.y * a1.d; | ||
373 | b2x = a2.x * b1.d - b1.x * a2.d; | ||
374 | b2y = a2.y * b1.d - b1.y * a2.d; | ||
375 | px = b1.y * b2.d - b2.y * b1.d; | ||
376 | py = b2.x * b1.d - b1.x * b2.d; | ||
377 | d1 = dotprod64(b1x, px, b1y, py); | ||
378 | d2 = dotprod64(b2x, px, b2y, py); | ||
379 | if ((sign64(d1) > 0 && sign64(d2) > 0) || | ||
380 | (sign64(d1) < 0 && sign64(d2) < 0)) | ||
381 | return FALSE; | ||
382 | |||
383 | /* | ||
384 | * The lines must cross. | ||
385 | */ | ||
386 | return TRUE; | ||
387 | } | ||
388 | |||
389 | static unsigned long squarert(unsigned long n) { | ||
390 | unsigned long d, a, b, di; | ||
391 | |||
392 | d = n; | ||
393 | a = 0; | ||
394 | b = 1L << 30; /* largest available power of 4 */ | ||
395 | do { | ||
396 | a >>= 1; | ||
397 | di = 2*a + b; | ||
398 | if (di <= d) { | ||
399 | d -= di; | ||
400 | a += b; | ||
401 | } | ||
402 | b >>= 2; | ||
403 | } while (b); | ||
404 | |||
405 | return a; | ||
406 | } | ||
407 | |||
408 | /* | ||
409 | * Our solutions are arranged on a square grid big enough that n | ||
410 | * points occupy about 1/POINTDENSITY of the grid. | ||
411 | */ | ||
412 | #define POINTDENSITY 3 | ||
413 | #define MAXDEGREE 4 | ||
414 | #define COORDLIMIT(n) squarert((n) * POINTDENSITY) | ||
415 | |||
416 | static void addedge(tree234 *edges, int a, int b) | ||
417 | { | ||
418 | edge *e = snew(edge); | ||
419 | |||
420 | assert(a != b); | ||
421 | |||
422 | e->a = min(a, b); | ||
423 | e->b = max(a, b); | ||
424 | |||
425 | add234(edges, e); | ||
426 | } | ||
427 | |||
428 | static int isedge(tree234 *edges, int a, int b) | ||
429 | { | ||
430 | edge e; | ||
431 | |||
432 | assert(a != b); | ||
433 | |||
434 | e.a = min(a, b); | ||
435 | e.b = max(a, b); | ||
436 | |||
437 | return find234(edges, &e, NULL) != NULL; | ||
438 | } | ||
439 | |||
440 | typedef struct vertex { | ||
441 | int param; | ||
442 | int vindex; | ||
443 | } vertex; | ||
444 | |||
445 | static int vertcmpC(const void *av, const void *bv) | ||
446 | { | ||
447 | const vertex *a = (vertex *)av; | ||
448 | const vertex *b = (vertex *)bv; | ||
449 | |||
450 | if (a->param < b->param) | ||
451 | return -1; | ||
452 | else if (a->param > b->param) | ||
453 | return +1; | ||
454 | else if (a->vindex < b->vindex) | ||
455 | return -1; | ||
456 | else if (a->vindex > b->vindex) | ||
457 | return +1; | ||
458 | return 0; | ||
459 | } | ||
460 | static int vertcmp(void *av, void *bv) { return vertcmpC(av, bv); } | ||
461 | |||
462 | /* | ||
463 | * Construct point coordinates for n points arranged in a circle, | ||
464 | * within the bounding box (0,0) to (w,w). | ||
465 | */ | ||
466 | static void make_circle(point *pts, int n, int w) | ||
467 | { | ||
468 | long d, r, c, i; | ||
469 | |||
470 | /* | ||
471 | * First, decide on a denominator. Although in principle it | ||
472 | * would be nice to set this really high so as to finely | ||
473 | * distinguish all the points on the circle, I'm going to set | ||
474 | * it at a fixed size to prevent integer overflow problems. | ||
475 | */ | ||
476 | d = PREFERRED_TILESIZE; | ||
477 | |||
478 | /* | ||
479 | * Leave a little space outside the circle. | ||
480 | */ | ||
481 | c = d * w / 2; | ||
482 | r = d * w * 3 / 7; | ||
483 | |||
484 | /* | ||
485 | * Place the points. | ||
486 | */ | ||
487 | for (i = 0; i < n; i++) { | ||
488 | double angle = i * 2 * PI / n; | ||
489 | double x = r * sin(angle), y = - r * cos(angle); | ||
490 | pts[i].x = (long)(c + x + 0.5); | ||
491 | pts[i].y = (long)(c + y + 0.5); | ||
492 | pts[i].d = d; | ||
493 | } | ||
494 | } | ||
495 | |||
496 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
497 | char **aux, int interactive) | ||
498 | { | ||
499 | int n = params->n, i; | ||
500 | long w, h, j, k, m; | ||
501 | point *pts, *pts2; | ||
502 | long *tmp; | ||
503 | tree234 *edges, *vertices; | ||
504 | edge *e, *e2; | ||
505 | vertex *v, *vs, *vlist; | ||
506 | char *ret; | ||
507 | |||
508 | w = h = COORDLIMIT(n); | ||
509 | |||
510 | /* | ||
511 | * Choose n points from this grid. | ||
512 | */ | ||
513 | pts = snewn(n, point); | ||
514 | tmp = snewn(w*h, long); | ||
515 | for (i = 0; i < w*h; i++) | ||
516 | tmp[i] = i; | ||
517 | shuffle(tmp, w*h, sizeof(*tmp), rs); | ||
518 | for (i = 0; i < n; i++) { | ||
519 | pts[i].x = tmp[i] % w; | ||
520 | pts[i].y = tmp[i] / w; | ||
521 | pts[i].d = 1; | ||
522 | } | ||
523 | sfree(tmp); | ||
524 | |||
525 | /* | ||
526 | * Now start adding edges between the points. | ||
527 | * | ||
528 | * At all times, we attempt to add an edge to the lowest-degree | ||
529 | * vertex we currently have, and we try the other vertices as | ||
530 | * candidate second endpoints in order of distance from this | ||
531 | * one. We stop as soon as we find an edge which | ||
532 | * | ||
533 | * (a) does not increase any vertex's degree beyond MAXDEGREE | ||
534 | * (b) does not cross any existing edges | ||
535 | * (c) does not intersect any actual point. | ||
536 | */ | ||
537 | vs = snewn(n, vertex); | ||
538 | vertices = newtree234(vertcmp); | ||
539 | for (i = 0; i < n; i++) { | ||
540 | v = vs + i; | ||
541 | v->param = 0; /* in this tree, param is the degree */ | ||
542 | v->vindex = i; | ||
543 | add234(vertices, v); | ||
544 | } | ||
545 | edges = newtree234(edgecmp); | ||
546 | vlist = snewn(n, vertex); | ||
547 | while (1) { | ||
548 | int added = FALSE; | ||
549 | |||
550 | for (i = 0; i < n; i++) { | ||
551 | v = index234(vertices, i); | ||
552 | j = v->vindex; | ||
553 | |||
554 | if (v->param >= MAXDEGREE) | ||
555 | break; /* nothing left to add! */ | ||
556 | |||
557 | /* | ||
558 | * Sort the other vertices into order of their distance | ||
559 | * from this one. Don't bother looking below i, because | ||
560 | * we've already tried those edges the other way round. | ||
561 | * Also here we rule out target vertices with too high | ||
562 | * a degree, and (of course) ones to which we already | ||
563 | * have an edge. | ||
564 | */ | ||
565 | m = 0; | ||
566 | for (k = i+1; k < n; k++) { | ||
567 | vertex *kv = index234(vertices, k); | ||
568 | int ki = kv->vindex; | ||
569 | int dx, dy; | ||
570 | |||
571 | if (kv->param >= MAXDEGREE || isedge(edges, ki, j)) | ||
572 | continue; | ||
573 | |||
574 | vlist[m].vindex = ki; | ||
575 | dx = pts[ki].x - pts[j].x; | ||
576 | dy = pts[ki].y - pts[j].y; | ||
577 | vlist[m].param = dx*dx + dy*dy; | ||
578 | m++; | ||
579 | } | ||
580 | |||
581 | qsort(vlist, m, sizeof(*vlist), vertcmpC); | ||
582 | |||
583 | for (k = 0; k < m; k++) { | ||
584 | int p; | ||
585 | int ki = vlist[k].vindex; | ||
586 | |||
587 | /* | ||
588 | * Check to see whether this edge intersects any | ||
589 | * existing edge or point. | ||
590 | */ | ||
591 | for (p = 0; p < n; p++) | ||
592 | if (p != ki && p != j && cross(pts[ki], pts[j], | ||
593 | pts[p], pts[p])) | ||
594 | break; | ||
595 | if (p < n) | ||
596 | continue; | ||
597 | for (p = 0; (e = index234(edges, p)) != NULL; p++) | ||
598 | if (e->a != ki && e->a != j && | ||
599 | e->b != ki && e->b != j && | ||
600 | cross(pts[ki], pts[j], pts[e->a], pts[e->b])) | ||
601 | break; | ||
602 | if (e) | ||
603 | continue; | ||
604 | |||
605 | /* | ||
606 | * We're done! Add this edge, modify the degrees of | ||
607 | * the two vertices involved, and break. | ||
608 | */ | ||
609 | addedge(edges, j, ki); | ||
610 | added = TRUE; | ||
611 | del234(vertices, vs+j); | ||
612 | vs[j].param++; | ||
613 | add234(vertices, vs+j); | ||
614 | del234(vertices, vs+ki); | ||
615 | vs[ki].param++; | ||
616 | add234(vertices, vs+ki); | ||
617 | break; | ||
618 | } | ||
619 | |||
620 | if (k < m) | ||
621 | break; | ||
622 | } | ||
623 | |||
624 | if (!added) | ||
625 | break; /* we're done. */ | ||
626 | } | ||
627 | |||
628 | /* | ||
629 | * That's our graph. Now shuffle the points, making sure that | ||
630 | * they come out with at least one crossed line when arranged | ||
631 | * in a circle (so that the puzzle isn't immediately solved!). | ||
632 | */ | ||
633 | tmp = snewn(n, long); | ||
634 | for (i = 0; i < n; i++) | ||
635 | tmp[i] = i; | ||
636 | pts2 = snewn(n, point); | ||
637 | make_circle(pts2, n, w); | ||
638 | while (1) { | ||
639 | shuffle(tmp, n, sizeof(*tmp), rs); | ||
640 | for (i = 0; (e = index234(edges, i)) != NULL; i++) { | ||
641 | for (j = i+1; (e2 = index234(edges, j)) != NULL; j++) { | ||
642 | if (e2->a == e->a || e2->a == e->b || | ||
643 | e2->b == e->a || e2->b == e->b) | ||
644 | continue; | ||
645 | if (cross(pts2[tmp[e2->a]], pts2[tmp[e2->b]], | ||
646 | pts2[tmp[e->a]], pts2[tmp[e->b]])) | ||
647 | break; | ||
648 | } | ||
649 | if (e2) | ||
650 | break; | ||
651 | } | ||
652 | if (e) | ||
653 | break; /* we've found a crossing */ | ||
654 | } | ||
655 | |||
656 | /* | ||
657 | * We're done. Now encode the graph in a string format. Let's | ||
658 | * use a comma-separated list of dash-separated vertex number | ||
659 | * pairs, numbered from zero. We'll sort the list to prevent | ||
660 | * side channels. | ||
661 | */ | ||
662 | ret = NULL; | ||
663 | { | ||
664 | char *sep; | ||
665 | char buf[80]; | ||
666 | int retlen; | ||
667 | edge *ea; | ||
668 | |||
669 | retlen = 0; | ||
670 | m = count234(edges); | ||
671 | ea = snewn(m, edge); | ||
672 | for (i = 0; (e = index234(edges, i)) != NULL; i++) { | ||
673 | assert(i < m); | ||
674 | ea[i].a = min(tmp[e->a], tmp[e->b]); | ||
675 | ea[i].b = max(tmp[e->a], tmp[e->b]); | ||
676 | retlen += 1 + sprintf(buf, "%d-%d", ea[i].a, ea[i].b); | ||
677 | } | ||
678 | assert(i == m); | ||
679 | qsort(ea, m, sizeof(*ea), edgecmpC); | ||
680 | |||
681 | ret = snewn(retlen, char); | ||
682 | sep = ""; | ||
683 | k = 0; | ||
684 | |||
685 | for (i = 0; i < m; i++) { | ||
686 | k += sprintf(ret + k, "%s%d-%d", sep, ea[i].a, ea[i].b); | ||
687 | sep = ","; | ||
688 | } | ||
689 | assert(k < retlen); | ||
690 | |||
691 | sfree(ea); | ||
692 | } | ||
693 | |||
694 | /* | ||
695 | * Encode the solution we started with as an aux_info string. | ||
696 | */ | ||
697 | { | ||
698 | char buf[80]; | ||
699 | char *auxstr; | ||
700 | int auxlen; | ||
701 | |||
702 | auxlen = 2; /* leading 'S' and trailing '\0' */ | ||
703 | for (i = 0; i < n; i++) { | ||
704 | j = tmp[i]; | ||
705 | pts2[j] = pts[i]; | ||
706 | if (pts2[j].d & 1) { | ||
707 | pts2[j].x *= 2; | ||
708 | pts2[j].y *= 2; | ||
709 | pts2[j].d *= 2; | ||
710 | } | ||
711 | pts2[j].x += pts2[j].d / 2; | ||
712 | pts2[j].y += pts2[j].d / 2; | ||
713 | auxlen += sprintf(buf, ";P%d:%ld,%ld/%ld", i, | ||
714 | pts2[j].x, pts2[j].y, pts2[j].d); | ||
715 | } | ||
716 | k = 0; | ||
717 | auxstr = snewn(auxlen, char); | ||
718 | auxstr[k++] = 'S'; | ||
719 | for (i = 0; i < n; i++) | ||
720 | k += sprintf(auxstr+k, ";P%d:%ld,%ld/%ld", i, | ||
721 | pts2[i].x, pts2[i].y, pts2[i].d); | ||
722 | assert(k < auxlen); | ||
723 | *aux = auxstr; | ||
724 | } | ||
725 | sfree(pts2); | ||
726 | |||
727 | sfree(tmp); | ||
728 | sfree(vlist); | ||
729 | freetree234(vertices); | ||
730 | sfree(vs); | ||
731 | while ((e = delpos234(edges, 0)) != NULL) | ||
732 | sfree(e); | ||
733 | freetree234(edges); | ||
734 | sfree(pts); | ||
735 | |||
736 | return ret; | ||
737 | } | ||
738 | |||
739 | static char *validate_desc(const game_params *params, const char *desc) | ||
740 | { | ||
741 | int a, b; | ||
742 | |||
743 | while (*desc) { | ||
744 | a = atoi(desc); | ||
745 | if (a < 0 || a >= params->n) | ||
746 | return "Number out of range in game description"; | ||
747 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
748 | if (*desc != '-') | ||
749 | return "Expected '-' after number in game description"; | ||
750 | desc++; /* eat dash */ | ||
751 | b = atoi(desc); | ||
752 | if (b < 0 || b >= params->n) | ||
753 | return "Number out of range in game description"; | ||
754 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
755 | if (*desc) { | ||
756 | if (*desc != ',') | ||
757 | return "Expected ',' after number in game description"; | ||
758 | desc++; /* eat comma */ | ||
759 | } | ||
760 | } | ||
761 | |||
762 | return NULL; | ||
763 | } | ||
764 | |||
765 | static void mark_crossings(game_state *state) | ||
766 | { | ||
767 | int ok = TRUE; | ||
768 | int i, j; | ||
769 | edge *e, *e2; | ||
770 | |||
771 | #ifdef SHOW_CROSSINGS | ||
772 | for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) | ||
773 | state->crosses[i] = FALSE; | ||
774 | #endif | ||
775 | |||
776 | /* | ||
777 | * Check correctness: for every pair of edges, see whether they | ||
778 | * cross. | ||
779 | */ | ||
780 | for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) { | ||
781 | for (j = i+1; (e2 = index234(state->graph->edges, j)) != NULL; j++) { | ||
782 | if (e2->a == e->a || e2->a == e->b || | ||
783 | e2->b == e->a || e2->b == e->b) | ||
784 | continue; | ||
785 | if (cross(state->pts[e2->a], state->pts[e2->b], | ||
786 | state->pts[e->a], state->pts[e->b])) { | ||
787 | ok = FALSE; | ||
788 | #ifdef SHOW_CROSSINGS | ||
789 | state->crosses[i] = state->crosses[j] = TRUE; | ||
790 | #else | ||
791 | goto done; /* multi-level break - sorry */ | ||
792 | #endif | ||
793 | } | ||
794 | } | ||
795 | } | ||
796 | |||
797 | /* | ||
798 | * e == NULL if we've gone through all the edge pairs | ||
799 | * without finding a crossing. | ||
800 | */ | ||
801 | #ifndef SHOW_CROSSINGS | ||
802 | done: | ||
803 | #endif | ||
804 | if (ok) | ||
805 | state->completed = TRUE; | ||
806 | } | ||
807 | |||
808 | static game_state *new_game(midend *me, const game_params *params, | ||
809 | const char *desc) | ||
810 | { | ||
811 | int n = params->n; | ||
812 | game_state *state = snew(game_state); | ||
813 | int a, b; | ||
814 | |||
815 | state->params = *params; | ||
816 | state->w = state->h = COORDLIMIT(n); | ||
817 | state->pts = snewn(n, point); | ||
818 | make_circle(state->pts, n, state->w); | ||
819 | state->graph = snew(struct graph); | ||
820 | state->graph->refcount = 1; | ||
821 | state->graph->edges = newtree234(edgecmp); | ||
822 | state->completed = state->cheated = state->just_solved = FALSE; | ||
823 | |||
824 | while (*desc) { | ||
825 | a = atoi(desc); | ||
826 | assert(a >= 0 && a < params->n); | ||
827 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
828 | assert(*desc == '-'); | ||
829 | desc++; /* eat dash */ | ||
830 | b = atoi(desc); | ||
831 | assert(b >= 0 && b < params->n); | ||
832 | while (*desc && isdigit((unsigned char)*desc)) desc++; | ||
833 | if (*desc) { | ||
834 | assert(*desc == ','); | ||
835 | desc++; /* eat comma */ | ||
836 | } | ||
837 | addedge(state->graph->edges, a, b); | ||
838 | } | ||
839 | |||
840 | #ifdef SHOW_CROSSINGS | ||
841 | state->crosses = snewn(count234(state->graph->edges), int); | ||
842 | mark_crossings(state); /* sets up `crosses' and `completed' */ | ||
843 | #endif | ||
844 | |||
845 | return state; | ||
846 | } | ||
847 | |||
848 | static game_state *dup_game(const game_state *state) | ||
849 | { | ||
850 | int n = state->params.n; | ||
851 | game_state *ret = snew(game_state); | ||
852 | |||
853 | ret->params = state->params; | ||
854 | ret->w = state->w; | ||
855 | ret->h = state->h; | ||
856 | ret->pts = snewn(n, point); | ||
857 | memcpy(ret->pts, state->pts, n * sizeof(point)); | ||
858 | ret->graph = state->graph; | ||
859 | ret->graph->refcount++; | ||
860 | ret->completed = state->completed; | ||
861 | ret->cheated = state->cheated; | ||
862 | ret->just_solved = state->just_solved; | ||
863 | #ifdef SHOW_CROSSINGS | ||
864 | ret->crosses = snewn(count234(ret->graph->edges), int); | ||
865 | memcpy(ret->crosses, state->crosses, | ||
866 | count234(ret->graph->edges) * sizeof(int)); | ||
867 | #endif | ||
868 | |||
869 | return ret; | ||
870 | } | ||
871 | |||
872 | static void free_game(game_state *state) | ||
873 | { | ||
874 | if (--state->graph->refcount <= 0) { | ||
875 | edge *e; | ||
876 | while ((e = delpos234(state->graph->edges, 0)) != NULL) | ||
877 | sfree(e); | ||
878 | freetree234(state->graph->edges); | ||
879 | sfree(state->graph); | ||
880 | } | ||
881 | sfree(state->pts); | ||
882 | sfree(state); | ||
883 | } | ||
884 | |||
885 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
886 | const char *aux, char **error) | ||
887 | { | ||
888 | int n = state->params.n; | ||
889 | int matrix[4]; | ||
890 | point *pts; | ||
891 | int i, j, besti; | ||
892 | float bestd; | ||
893 | char buf[80], *ret; | ||
894 | int retlen, retsize; | ||
895 | |||
896 | if (!aux) { | ||
897 | *error = "Solution not known for this puzzle"; | ||
898 | return NULL; | ||
899 | } | ||
900 | |||
901 | /* | ||
902 | * Decode the aux_info to get the original point positions. | ||
903 | */ | ||
904 | pts = snewn(n, point); | ||
905 | aux++; /* eat 'S' */ | ||
906 | for (i = 0; i < n; i++) { | ||
907 | int p, k; | ||
908 | long x, y, d; | ||
909 | int ret = sscanf(aux, ";P%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k); | ||
910 | if (ret != 4 || p != i) { | ||
911 | *error = "Internal error: aux_info badly formatted"; | ||
912 | sfree(pts); | ||
913 | return NULL; | ||
914 | } | ||
915 | pts[i].x = x; | ||
916 | pts[i].y = y; | ||
917 | pts[i].d = d; | ||
918 | aux += k; | ||
919 | } | ||
920 | |||
921 | /* | ||
922 | * Now go through eight possible symmetries of the point set. | ||
923 | * For each one, work out the sum of the Euclidean distances | ||
924 | * between the points' current positions and their new ones. | ||
925 | * | ||
926 | * We're squaring distances here, which means we're at risk of | ||
927 | * integer overflow. Fortunately, there's no real need to be | ||
928 | * massively careful about rounding errors, since this is a | ||
929 | * non-essential bit of the code; so I'll just work in floats | ||
930 | * internally. | ||
931 | */ | ||
932 | besti = -1; | ||
933 | bestd = 0.0F; | ||
934 | |||
935 | for (i = 0; i < 8; i++) { | ||
936 | float d; | ||
937 | |||
938 | matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0; | ||
939 | matrix[i & 1] = (i & 2) ? +1 : -1; | ||
940 | matrix[3-(i&1)] = (i & 4) ? +1 : -1; | ||
941 | |||
942 | d = 0.0F; | ||
943 | for (j = 0; j < n; j++) { | ||
944 | float px = (float)pts[j].x / pts[j].d; | ||
945 | float py = (float)pts[j].y / pts[j].d; | ||
946 | float sx = (float)currstate->pts[j].x / currstate->pts[j].d; | ||
947 | float sy = (float)currstate->pts[j].y / currstate->pts[j].d; | ||
948 | float cx = (float)currstate->w / 2; | ||
949 | float cy = (float)currstate->h / 2; | ||
950 | float ox, oy, dx, dy; | ||
951 | |||
952 | px -= cx; | ||
953 | py -= cy; | ||
954 | |||
955 | ox = matrix[0] * px + matrix[1] * py; | ||
956 | oy = matrix[2] * px + matrix[3] * py; | ||
957 | |||
958 | ox += cx; | ||
959 | oy += cy; | ||
960 | |||
961 | dx = ox - sx; | ||
962 | dy = oy - sy; | ||
963 | |||
964 | d += dx*dx + dy*dy; | ||
965 | } | ||
966 | |||
967 | if (besti < 0 || bestd > d) { | ||
968 | besti = i; | ||
969 | bestd = d; | ||
970 | } | ||
971 | } | ||
972 | |||
973 | assert(besti >= 0); | ||
974 | |||
975 | /* | ||
976 | * Now we know which symmetry is closest to the points' current | ||
977 | * positions. Use it. | ||
978 | */ | ||
979 | matrix[0] = matrix[1] = matrix[2] = matrix[3] = 0; | ||
980 | matrix[besti & 1] = (besti & 2) ? +1 : -1; | ||
981 | matrix[3-(besti&1)] = (besti & 4) ? +1 : -1; | ||
982 | |||
983 | retsize = 256; | ||
984 | ret = snewn(retsize, char); | ||
985 | retlen = 0; | ||
986 | ret[retlen++] = 'S'; | ||
987 | ret[retlen] = '\0'; | ||
988 | |||
989 | for (i = 0; i < n; i++) { | ||
990 | float px = (float)pts[i].x / pts[i].d; | ||
991 | float py = (float)pts[i].y / pts[i].d; | ||
992 | float cx = (float)currstate->w / 2; | ||
993 | float cy = (float)currstate->h / 2; | ||
994 | float ox, oy; | ||
995 | int extra; | ||
996 | |||
997 | px -= cx; | ||
998 | py -= cy; | ||
999 | |||
1000 | ox = matrix[0] * px + matrix[1] * py; | ||
1001 | oy = matrix[2] * px + matrix[3] * py; | ||
1002 | |||
1003 | ox += cx; | ||
1004 | oy += cy; | ||
1005 | |||
1006 | /* | ||
1007 | * Use a fixed denominator of 2, because we know the | ||
1008 | * original points were on an integer grid offset by 1/2. | ||
1009 | */ | ||
1010 | pts[i].d = 2; | ||
1011 | ox *= pts[i].d; | ||
1012 | oy *= pts[i].d; | ||
1013 | pts[i].x = (long)(ox + 0.5F); | ||
1014 | pts[i].y = (long)(oy + 0.5F); | ||
1015 | |||
1016 | extra = sprintf(buf, ";P%d:%ld,%ld/%ld", i, | ||
1017 | pts[i].x, pts[i].y, pts[i].d); | ||
1018 | if (retlen + extra >= retsize) { | ||
1019 | retsize = retlen + extra + 256; | ||
1020 | ret = sresize(ret, retsize, char); | ||
1021 | } | ||
1022 | strcpy(ret + retlen, buf); | ||
1023 | retlen += extra; | ||
1024 | } | ||
1025 | |||
1026 | sfree(pts); | ||
1027 | |||
1028 | return ret; | ||
1029 | } | ||
1030 | |||
1031 | static int game_can_format_as_text_now(const game_params *params) | ||
1032 | { | ||
1033 | return TRUE; | ||
1034 | } | ||
1035 | |||
1036 | static char *game_text_format(const game_state *state) | ||
1037 | { | ||
1038 | return NULL; | ||
1039 | } | ||
1040 | |||
1041 | struct game_ui { | ||
1042 | int dragpoint; /* point being dragged; -1 if none */ | ||
1043 | |||
1044 | int cursorpoint; /* point being highlighted, but | ||
1045 | * not dragged by the cursor, | ||
1046 | * again -1 if none */ | ||
1047 | |||
1048 | point newpoint; /* where it's been dragged to so far */ | ||
1049 | int just_dragged; /* reset in game_changed_state */ | ||
1050 | int just_moved; /* _set_ in game_changed_state */ | ||
1051 | float anim_length; | ||
1052 | }; | ||
1053 | |||
1054 | static game_ui *new_ui(const game_state *state) | ||
1055 | { | ||
1056 | game_ui *ui = snew(game_ui); | ||
1057 | ui->dragpoint = -1; | ||
1058 | ui->cursorpoint = -1; | ||
1059 | ui->just_moved = ui->just_dragged = FALSE; | ||
1060 | return ui; | ||
1061 | } | ||
1062 | |||
1063 | static void free_ui(game_ui *ui) | ||
1064 | { | ||
1065 | sfree(ui); | ||
1066 | } | ||
1067 | |||
1068 | static char *encode_ui(const game_ui *ui) | ||
1069 | { | ||
1070 | return NULL; | ||
1071 | } | ||
1072 | |||
1073 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1074 | { | ||
1075 | } | ||
1076 | |||
1077 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1078 | const game_state *newstate) | ||
1079 | { | ||
1080 | ui->dragpoint = -1; | ||
1081 | ui->just_moved = ui->just_dragged; | ||
1082 | ui->just_dragged = FALSE; | ||
1083 | } | ||
1084 | |||
1085 | struct game_drawstate { | ||
1086 | long tilesize; | ||
1087 | int bg, dragpoint, cursorpoint; | ||
1088 | long *x, *y; | ||
1089 | }; | ||
1090 | |||
1091 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1092 | const game_drawstate *ds, | ||
1093 | int x, int y, int button) | ||
1094 | { | ||
1095 | int n = state->params.n; | ||
1096 | |||
1097 | if (IS_MOUSE_DOWN(button)) { | ||
1098 | int i, best; | ||
1099 | long bestd; | ||
1100 | |||
1101 | /* | ||
1102 | * Begin drag. We drag the vertex _nearest_ to the pointer, | ||
1103 | * just in case one is nearly on top of another and we want | ||
1104 | * to drag the latter. However, we drag nothing at all if | ||
1105 | * the nearest vertex is outside DRAG_THRESHOLD. | ||
1106 | */ | ||
1107 | best = -1; | ||
1108 | bestd = 0; | ||
1109 | |||
1110 | for (i = 0; i < n; i++) { | ||
1111 | long px = state->pts[i].x * ds->tilesize / state->pts[i].d; | ||
1112 | long py = state->pts[i].y * ds->tilesize / state->pts[i].d; | ||
1113 | long dx = px - x; | ||
1114 | long dy = py - y; | ||
1115 | long d = dx*dx + dy*dy; | ||
1116 | |||
1117 | if (best == -1 || bestd > d) { | ||
1118 | best = i; | ||
1119 | bestd = d; | ||
1120 | } | ||
1121 | } | ||
1122 | |||
1123 | if (bestd <= DRAG_THRESHOLD * DRAG_THRESHOLD) { | ||
1124 | ui->dragpoint = best; | ||
1125 | ui->newpoint.x = x; | ||
1126 | ui->newpoint.y = y; | ||
1127 | ui->newpoint.d = ds->tilesize; | ||
1128 | return ""; | ||
1129 | } | ||
1130 | |||
1131 | } else if (IS_MOUSE_DRAG(button) && ui->dragpoint >= 0) { | ||
1132 | ui->newpoint.x = x; | ||
1133 | ui->newpoint.y = y; | ||
1134 | ui->newpoint.d = ds->tilesize; | ||
1135 | return ""; | ||
1136 | } else if (IS_MOUSE_RELEASE(button) && ui->dragpoint >= 0) { | ||
1137 | int p = ui->dragpoint; | ||
1138 | char buf[80]; | ||
1139 | |||
1140 | ui->dragpoint = -1; /* terminate drag, no matter what */ | ||
1141 | |||
1142 | /* | ||
1143 | * First, see if we're within range. The user can cancel a | ||
1144 | * drag by dragging the point right off the window. | ||
1145 | */ | ||
1146 | if (ui->newpoint.x < 0 || | ||
1147 | ui->newpoint.x >= (long)state->w*ui->newpoint.d || | ||
1148 | ui->newpoint.y < 0 || | ||
1149 | ui->newpoint.y >= (long)state->h*ui->newpoint.d) | ||
1150 | return ""; | ||
1151 | |||
1152 | /* | ||
1153 | * We aren't cancelling the drag. Construct a move string | ||
1154 | * indicating where this point is going to. | ||
1155 | */ | ||
1156 | sprintf(buf, "P%d:%ld,%ld/%ld", p, | ||
1157 | ui->newpoint.x, ui->newpoint.y, ui->newpoint.d); | ||
1158 | ui->just_dragged = TRUE; | ||
1159 | return dupstr(buf); | ||
1160 | } | ||
1161 | else if(IS_CURSOR_MOVE(button)) | ||
1162 | { | ||
1163 | if(ui->dragpoint < 0) | ||
1164 | { | ||
1165 | /* We're selecting a point here. */ | ||
1166 | /* Search all the points and find the closest one (2-D) in | ||
1167 | * the given direction. */ | ||
1168 | int i, best; | ||
1169 | long bestd; | ||
1170 | |||
1171 | if(ui->cursorpoint < 0) | ||
1172 | { | ||
1173 | ui->cursorpoint = 0; | ||
1174 | } | ||
1175 | |||
1176 | /* | ||
1177 | * Begin drag. We drag the vertex _nearest_ to the pointer, | ||
1178 | * just in case one is nearly on top of another and we want | ||
1179 | * to drag the latter. However, we drag nothing at all if | ||
1180 | * the nearest vertex is outside DRAG_THRESHOLD. | ||
1181 | */ | ||
1182 | best = -1; | ||
1183 | bestd = 0; | ||
1184 | |||
1185 | for (i = 0; i < n; i++) { | ||
1186 | if(i == ui->cursorpoint) | ||
1187 | continue; | ||
1188 | |||
1189 | long px = state->pts[i].x * ds->tilesize / state->pts[i].d; | ||
1190 | long py = state->pts[i].y * ds->tilesize / state->pts[i].d; | ||
1191 | long dx = px - state->pts[ui->cursorpoint].x * ds->tilesize / state->pts[ui->cursorpoint].d; | ||
1192 | long dy = py - state->pts[ui->cursorpoint].y * ds->tilesize / state->pts[ui->cursorpoint].d; | ||
1193 | long d = dx*dx + dy*dy; | ||
1194 | |||
1195 | /* Figure out if this point falls into a 90 degree | ||
1196 | * range extending from the current point */ | ||
1197 | |||
1198 | float angle = atan2(-dy, dx); /* negate y to adjust for raster coordinates */ | ||
1199 | |||
1200 | /* offset to [0..2*PI] */ | ||
1201 | if(angle < 0) | ||
1202 | angle += 2*PI; | ||
1203 | |||
1204 | int right_direction = FALSE; | ||
1205 | |||
1206 | if((button == CURSOR_UP && (1*PI/4 <= angle && angle <= 3*PI/4)) || | ||
1207 | (button == CURSOR_LEFT && (3*PI/4 <= angle && angle <= 5*PI/4)) || | ||
1208 | (button == CURSOR_DOWN && (5*PI/4 <= angle && angle <= 7*PI/4)) || | ||
1209 | (button == CURSOR_RIGHT && (angle >= 7*PI/4 || angle <= 1*PI/4))) | ||
1210 | right_direction = TRUE; | ||
1211 | |||
1212 | if ((best == -1 || bestd > d) && right_direction) { | ||
1213 | best = i; | ||
1214 | bestd = d; | ||
1215 | } | ||
1216 | } | ||
1217 | |||
1218 | if(best >= 0) | ||
1219 | { | ||
1220 | ui->cursorpoint = best; | ||
1221 | return ""; | ||
1222 | } | ||
1223 | } | ||
1224 | else if(ui->dragpoint >= 0) | ||
1225 | { | ||
1226 | /* dragging */ | ||
1227 | switch(button) | ||
1228 | { | ||
1229 | case CURSOR_UP: | ||
1230 | ui->newpoint.y -= ds->tilesize / CURSOR_GRANULARITY; | ||
1231 | return ""; | ||
1232 | case CURSOR_DOWN: | ||
1233 | ui->newpoint.y += ds->tilesize / CURSOR_GRANULARITY; | ||
1234 | return ""; | ||
1235 | case CURSOR_LEFT: | ||
1236 | ui->newpoint.x -= ds->tilesize / CURSOR_GRANULARITY; | ||
1237 | return ""; | ||
1238 | case CURSOR_RIGHT: | ||
1239 | ui->newpoint.x += ds->tilesize / CURSOR_GRANULARITY; | ||
1240 | return ""; | ||
1241 | default: | ||
1242 | break; | ||
1243 | } | ||
1244 | } | ||
1245 | } | ||
1246 | else if(IS_CURSOR_SELECT(button)) | ||
1247 | { | ||
1248 | if(ui->dragpoint < 0 && ui->cursorpoint >= 0) | ||
1249 | { | ||
1250 | /* begin drag */ | ||
1251 | ui->dragpoint = ui->cursorpoint; | ||
1252 | ui->cursorpoint = -1; | ||
1253 | ui->newpoint.x = state->pts[ui->dragpoint].x * ds->tilesize / state->pts[ui->dragpoint].d; | ||
1254 | ui->newpoint.y = state->pts[ui->dragpoint].y * ds->tilesize / state->pts[ui->dragpoint].d; | ||
1255 | ui->newpoint.d = ds->tilesize; | ||
1256 | return ""; | ||
1257 | } | ||
1258 | else if(ui->dragpoint >= 0) | ||
1259 | { | ||
1260 | /* end drag */ | ||
1261 | int p = ui->dragpoint; | ||
1262 | char buf[80]; | ||
1263 | |||
1264 | ui->cursorpoint = ui->dragpoint; | ||
1265 | ui->dragpoint = -1; /* terminate drag, no matter what */ | ||
1266 | |||
1267 | /* | ||
1268 | * First, see if we're within range. The user can cancel a | ||
1269 | * drag by dragging the point right off the window. | ||
1270 | */ | ||
1271 | if (ui->newpoint.x < 0 || | ||
1272 | ui->newpoint.x >= (long)state->w*ui->newpoint.d || | ||
1273 | ui->newpoint.y < 0 || | ||
1274 | ui->newpoint.y >= (long)state->h*ui->newpoint.d) | ||
1275 | return ""; | ||
1276 | |||
1277 | /* | ||
1278 | * We aren't cancelling the drag. Construct a move string | ||
1279 | * indicating where this point is going to. | ||
1280 | */ | ||
1281 | sprintf(buf, "P%d:%ld,%ld/%ld", p, | ||
1282 | ui->newpoint.x, ui->newpoint.y, ui->newpoint.d); | ||
1283 | ui->just_dragged = TRUE; | ||
1284 | return dupstr(buf); | ||
1285 | } | ||
1286 | else if(ui->cursorpoint < 0) | ||
1287 | ui->cursorpoint = 0; | ||
1288 | } | ||
1289 | |||
1290 | return NULL; | ||
1291 | } | ||
1292 | |||
1293 | static game_state *execute_move(const game_state *state, const char *move) | ||
1294 | { | ||
1295 | int n = state->params.n; | ||
1296 | int p, k; | ||
1297 | long x, y, d; | ||
1298 | game_state *ret = dup_game(state); | ||
1299 | |||
1300 | ret->just_solved = FALSE; | ||
1301 | |||
1302 | while (*move) { | ||
1303 | if (*move == 'S') { | ||
1304 | move++; | ||
1305 | if (*move == ';') move++; | ||
1306 | ret->cheated = ret->just_solved = TRUE; | ||
1307 | } | ||
1308 | if (*move == 'P' && | ||
1309 | sscanf(move+1, "%d:%ld,%ld/%ld%n", &p, &x, &y, &d, &k) == 4 && | ||
1310 | p >= 0 && p < n && d > 0) { | ||
1311 | ret->pts[p].x = x; | ||
1312 | ret->pts[p].y = y; | ||
1313 | ret->pts[p].d = d; | ||
1314 | |||
1315 | move += k+1; | ||
1316 | if (*move == ';') move++; | ||
1317 | } else { | ||
1318 | free_game(ret); | ||
1319 | return NULL; | ||
1320 | } | ||
1321 | } | ||
1322 | |||
1323 | mark_crossings(ret); | ||
1324 | |||
1325 | return ret; | ||
1326 | } | ||
1327 | |||
1328 | /* ---------------------------------------------------------------------- | ||
1329 | * Drawing routines. | ||
1330 | */ | ||
1331 | |||
1332 | static void game_compute_size(const game_params *params, int tilesize, | ||
1333 | int *x, int *y) | ||
1334 | { | ||
1335 | *x = *y = COORDLIMIT(params->n) * tilesize; | ||
1336 | } | ||
1337 | |||
1338 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1339 | const game_params *params, int tilesize) | ||
1340 | { | ||
1341 | ds->tilesize = tilesize; | ||
1342 | } | ||
1343 | |||
1344 | static float *game_colours(frontend *fe, int *ncolours) | ||
1345 | { | ||
1346 | float *ret = snewn(3 * NCOLOURS, float); | ||
1347 | |||
1348 | /* | ||
1349 | * COL_BACKGROUND is what we use as the normal background colour. | ||
1350 | * Unusually, though, it isn't colour #0: COL_SYSBACKGROUND, a bit | ||
1351 | * darker, takes that place. This means that if the user resizes | ||
1352 | * an Untangle window so as to change its aspect ratio, the | ||
1353 | * still-square playable area will be distinguished from the dead | ||
1354 | * space around it. | ||
1355 | */ | ||
1356 | game_mkhighlight(fe, ret, COL_BACKGROUND, -1, COL_SYSBACKGROUND); | ||
1357 | |||
1358 | ret[COL_LINE * 3 + 0] = 0.0F; | ||
1359 | ret[COL_LINE * 3 + 1] = 0.0F; | ||
1360 | ret[COL_LINE * 3 + 2] = 0.0F; | ||
1361 | |||
1362 | #ifdef SHOW_CROSSINGS | ||
1363 | ret[COL_CROSSEDLINE * 3 + 0] = 1.0F; | ||
1364 | ret[COL_CROSSEDLINE * 3 + 1] = 0.0F; | ||
1365 | ret[COL_CROSSEDLINE * 3 + 2] = 0.0F; | ||
1366 | #endif | ||
1367 | |||
1368 | ret[COL_OUTLINE * 3 + 0] = 0.0F; | ||
1369 | ret[COL_OUTLINE * 3 + 1] = 0.0F; | ||
1370 | ret[COL_OUTLINE * 3 + 2] = 0.0F; | ||
1371 | |||
1372 | ret[COL_POINT * 3 + 0] = 0.0F; | ||
1373 | ret[COL_POINT * 3 + 1] = 0.0F; | ||
1374 | ret[COL_POINT * 3 + 2] = 1.0F; | ||
1375 | |||
1376 | ret[COL_DRAGPOINT * 3 + 0] = 1.0F; | ||
1377 | ret[COL_DRAGPOINT * 3 + 1] = 1.0F; | ||
1378 | ret[COL_DRAGPOINT * 3 + 2] = 1.0F; | ||
1379 | |||
1380 | ret[COL_CURSORPOINT * 3 + 0] = 0.5F; | ||
1381 | ret[COL_CURSORPOINT * 3 + 1] = 0.5F; | ||
1382 | ret[COL_CURSORPOINT * 3 + 2] = 0.5F; | ||
1383 | |||
1384 | ret[COL_NEIGHBOUR * 3 + 0] = 1.0F; | ||
1385 | ret[COL_NEIGHBOUR * 3 + 1] = 0.0F; | ||
1386 | ret[COL_NEIGHBOUR * 3 + 2] = 0.0F; | ||
1387 | |||
1388 | ret[COL_FLASH1 * 3 + 0] = 0.5F; | ||
1389 | ret[COL_FLASH1 * 3 + 1] = 0.5F; | ||
1390 | ret[COL_FLASH1 * 3 + 2] = 0.5F; | ||
1391 | |||
1392 | ret[COL_FLASH2 * 3 + 0] = 1.0F; | ||
1393 | ret[COL_FLASH2 * 3 + 1] = 1.0F; | ||
1394 | ret[COL_FLASH2 * 3 + 2] = 1.0F; | ||
1395 | |||
1396 | *ncolours = NCOLOURS; | ||
1397 | return ret; | ||
1398 | } | ||
1399 | |||
1400 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1401 | { | ||
1402 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1403 | int i; | ||
1404 | |||
1405 | ds->tilesize = 0; | ||
1406 | ds->x = snewn(state->params.n, long); | ||
1407 | ds->y = snewn(state->params.n, long); | ||
1408 | for (i = 0; i < state->params.n; i++) | ||
1409 | ds->x[i] = ds->y[i] = -1; | ||
1410 | ds->bg = -1; | ||
1411 | ds->dragpoint = -1; | ||
1412 | ds->cursorpoint = -1; | ||
1413 | |||
1414 | return ds; | ||
1415 | } | ||
1416 | |||
1417 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1418 | { | ||
1419 | sfree(ds->y); | ||
1420 | sfree(ds->x); | ||
1421 | sfree(ds); | ||
1422 | } | ||
1423 | |||
1424 | static point mix(point a, point b, float distance) | ||
1425 | { | ||
1426 | point ret; | ||
1427 | |||
1428 | ret.d = a.d * b.d; | ||
1429 | ret.x = (long)(a.x * b.d + distance * (b.x * a.d - a.x * b.d)); | ||
1430 | ret.y = (long)(a.y * b.d + distance * (b.y * a.d - a.y * b.d)); | ||
1431 | |||
1432 | return ret; | ||
1433 | } | ||
1434 | |||
1435 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1436 | const game_state *oldstate, const game_state *state, | ||
1437 | int dir, const game_ui *ui, | ||
1438 | float animtime, float flashtime) | ||
1439 | { | ||
1440 | int w, h; | ||
1441 | edge *e; | ||
1442 | int i, j; | ||
1443 | int bg, points_moved; | ||
1444 | |||
1445 | /* | ||
1446 | * There's no terribly sensible way to do partial redraws of | ||
1447 | * this game, so I'm going to have to resort to redrawing the | ||
1448 | * whole thing every time. | ||
1449 | */ | ||
1450 | |||
1451 | if (flashtime == 0) | ||
1452 | bg = COL_BACKGROUND; | ||
1453 | else if ((int)(flashtime * 4 / FLASH_TIME) % 2 == 0) | ||
1454 | bg = COL_FLASH1; | ||
1455 | else | ||
1456 | bg = COL_FLASH2; | ||
1457 | |||
1458 | /* | ||
1459 | * To prevent excessive spinning on redraw during a completion | ||
1460 | * flash, we first check to see if _either_ the flash | ||
1461 | * background colour has changed _or_ at least one point has | ||
1462 | * moved _or_ a drag has begun or ended, and abandon the redraw | ||
1463 | * if neither is the case. | ||
1464 | * | ||
1465 | * Also in this loop we work out the coordinates of all the | ||
1466 | * points for this redraw. | ||
1467 | */ | ||
1468 | points_moved = FALSE; | ||
1469 | for (i = 0; i < state->params.n; i++) { | ||
1470 | point p = state->pts[i]; | ||
1471 | long x, y; | ||
1472 | |||
1473 | if (ui->dragpoint == i) | ||
1474 | p = ui->newpoint; | ||
1475 | |||
1476 | if (oldstate) | ||
1477 | p = mix(oldstate->pts[i], p, animtime / ui->anim_length); | ||
1478 | |||
1479 | x = p.x * ds->tilesize / p.d; | ||
1480 | y = p.y * ds->tilesize / p.d; | ||
1481 | |||
1482 | if (ds->x[i] != x || ds->y[i] != y) | ||
1483 | points_moved = TRUE; | ||
1484 | |||
1485 | ds->x[i] = x; | ||
1486 | ds->y[i] = y; | ||
1487 | } | ||
1488 | |||
1489 | if (ds->bg == bg && ds->dragpoint == ui->dragpoint && ds->cursorpoint == ui->cursorpoint && !points_moved) | ||
1490 | return; /* nothing to do */ | ||
1491 | |||
1492 | ds->dragpoint = ui->dragpoint; | ||
1493 | ds->bg = bg; | ||
1494 | |||
1495 | game_compute_size(&state->params, ds->tilesize, &w, &h); | ||
1496 | |||
1497 | clip(dr, 0, 0, w, h); | ||
1498 | draw_rect(dr, 0, 0, w, h, bg); | ||
1499 | |||
1500 | /* | ||
1501 | * Draw the edges. | ||
1502 | */ | ||
1503 | |||
1504 | for (i = 0; (e = index234(state->graph->edges, i)) != NULL; i++) { | ||
1505 | draw_line(dr, ds->x[e->a], ds->y[e->a], ds->x[e->b], ds->y[e->b], | ||
1506 | #ifdef SHOW_CROSSINGS | ||
1507 | (oldstate?oldstate:state)->crosses[i] ? | ||
1508 | COL_CROSSEDLINE : | ||
1509 | #endif | ||
1510 | COL_LINE); | ||
1511 | } | ||
1512 | |||
1513 | /* | ||
1514 | * Draw the points. | ||
1515 | * | ||
1516 | * When dragging, we should not only vary the colours, but | ||
1517 | * leave the point being dragged until last. | ||
1518 | */ | ||
1519 | for (j = 0; j < 4; j++) { | ||
1520 | int thisc = (j == 0 ? COL_POINT : | ||
1521 | (j == 1 ? COL_NEIGHBOUR : | ||
1522 | j == 2 ? COL_CURSORPOINT : COL_DRAGPOINT)); | ||
1523 | for (i = 0; i < state->params.n; i++) { | ||
1524 | int c; | ||
1525 | |||
1526 | if (ui->dragpoint == i) { | ||
1527 | c = COL_DRAGPOINT; | ||
1528 | } else if(ui->cursorpoint == i) { | ||
1529 | c = COL_CURSORPOINT; | ||
1530 | } else if (ui->dragpoint >= 0 && | ||
1531 | isedge(state->graph->edges, ui->dragpoint, i)) { | ||
1532 | c = COL_NEIGHBOUR; | ||
1533 | } else { | ||
1534 | c = COL_POINT; | ||
1535 | } | ||
1536 | |||
1537 | if (c == thisc) { | ||
1538 | #ifdef VERTEX_NUMBERS | ||
1539 | draw_circle(dr, ds->x[i], ds->y[i], DRAG_THRESHOLD, bg, bg); | ||
1540 | { | ||
1541 | char buf[80]; | ||
1542 | sprintf(buf, "%d", i); | ||
1543 | draw_text(dr, ds->x[i], ds->y[i], FONT_VARIABLE, | ||
1544 | DRAG_THRESHOLD*3/2, | ||
1545 | ALIGN_VCENTRE|ALIGN_HCENTRE, c, buf); | ||
1546 | } | ||
1547 | #else | ||
1548 | draw_circle(dr, ds->x[i], ds->y[i], CIRCLE_RADIUS, | ||
1549 | c, COL_OUTLINE); | ||
1550 | #endif | ||
1551 | } | ||
1552 | } | ||
1553 | } | ||
1554 | |||
1555 | draw_update(dr, 0, 0, w, h); | ||
1556 | } | ||
1557 | |||
1558 | static float game_anim_length(const game_state *oldstate, | ||
1559 | const game_state *newstate, int dir, game_ui *ui) | ||
1560 | { | ||
1561 | if (ui->just_moved) | ||
1562 | return 0.0F; | ||
1563 | if ((dir < 0 ? oldstate : newstate)->just_solved) | ||
1564 | ui->anim_length = SOLVEANIM_TIME; | ||
1565 | else | ||
1566 | ui->anim_length = ANIM_TIME; | ||
1567 | return ui->anim_length; | ||
1568 | } | ||
1569 | |||
1570 | static float game_flash_length(const game_state *oldstate, | ||
1571 | const game_state *newstate, int dir, game_ui *ui) | ||
1572 | { | ||
1573 | if (!oldstate->completed && newstate->completed && | ||
1574 | !oldstate->cheated && !newstate->cheated) | ||
1575 | return FLASH_TIME; | ||
1576 | return 0.0F; | ||
1577 | } | ||
1578 | |||
1579 | static int game_status(const game_state *state) | ||
1580 | { | ||
1581 | return state->completed ? +1 : 0; | ||
1582 | } | ||
1583 | |||
1584 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1585 | { | ||
1586 | return TRUE; | ||
1587 | } | ||
1588 | |||
1589 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1590 | { | ||
1591 | } | ||
1592 | |||
1593 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1594 | { | ||
1595 | } | ||
1596 | |||
1597 | #ifdef COMBINED | ||
1598 | #define thegame untangle | ||
1599 | #endif | ||
1600 | |||
1601 | const struct game thegame = { | ||
1602 | "Untangle", "games.untangle", "untangle", | ||
1603 | default_params, | ||
1604 | game_fetch_preset, NULL, | ||
1605 | decode_params, | ||
1606 | encode_params, | ||
1607 | free_params, | ||
1608 | dup_params, | ||
1609 | TRUE, game_configure, custom_params, | ||
1610 | validate_params, | ||
1611 | new_game_desc, | ||
1612 | validate_desc, | ||
1613 | new_game, | ||
1614 | dup_game, | ||
1615 | free_game, | ||
1616 | TRUE, solve_game, | ||
1617 | FALSE, game_can_format_as_text_now, game_text_format, | ||
1618 | new_ui, | ||
1619 | free_ui, | ||
1620 | encode_ui, | ||
1621 | decode_ui, | ||
1622 | game_changed_state, | ||
1623 | interpret_move, | ||
1624 | execute_move, | ||
1625 | PREFERRED_TILESIZE, game_compute_size, game_set_size, | ||
1626 | game_colours, | ||
1627 | game_new_drawstate, | ||
1628 | game_free_drawstate, | ||
1629 | game_redraw, | ||
1630 | game_anim_length, | ||
1631 | game_flash_length, | ||
1632 | game_status, | ||
1633 | FALSE, FALSE, game_print_size, game_print, | ||
1634 | FALSE, /* wants_statusbar */ | ||
1635 | FALSE, game_timing_state, | ||
1636 | SOLVE_ANIMATES, /* flags */ | ||
1637 | }; | ||