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