shithub: puzzles

Download patch

ref: 01844d39c6c92d5ce417519ef2bdced6346f2549
parent: a2380d277a50b02d9575017559d95d562986488a
author: Simon Tatham <anakin@pobox.com>
date: Wed Feb 24 14:14:31 EST 2016 

Tracks: use the new findloop for loop detection.

Tracks's previous loop detector was very basic, and only bothered to
highlight one loop, even if the player managed to create more than one
at a time. Now we highlight all of them.



--- a/tracks.R
+++ b/tracks.R
@@ -1,6 +1,6 @@
 # -*- makefile -*-
 
-TRACKS_EXTRA = dsf
+TRACKS_EXTRA = dsf findloop
 
 tracks  : [X] GTK COMMON tracks TRACKS_EXTRA tracks-icon|no-icon
 
--- a/tracks.c
+++ b/tracks.c
@@ -1490,11 +1490,10 @@
     sfree(sstring);
 }
 
-static void dsf_update_completion(game_state *state, int *loopclass,
-                                  int ax, int ay, char dir,
-                                  int *dsf)
+static void dsf_update_completion(game_state *state, int ax, int ay,
+                                  char dir, int *dsf)
 {
-    int w = state->p.w, ai = ay*w+ax, bx, by, bi, ac, bc;
+    int w = state->p.w, ai = ay*w+ax, bx, by, bi;
 
     if (!(S_E_DIRS(state, ax, ay, E_TRACK) & dir)) return;
     bx = ax + DX(dir);
@@ -1503,15 +1502,38 @@
     if (!INGRID(state, bx, by)) return;
     bi = by*w+bx;
 
-    ac = dsf_canonify(dsf, ai);
-    bc = dsf_canonify(dsf, bi);
+    dsf_merge(dsf, ai, bi);
+}
 
-    if (ac == bc) {
-        /* loop detected */
-        *loopclass = ac;
-    } else {
-        dsf_merge(dsf, ai, bi);
+struct tracks_neighbour_ctx {
+    game_state *state;
+    int i, n, neighbours[4];
+};
+static int tracks_neighbour(int vertex, void *vctx)
+{
+    struct tracks_neighbour_ctx *ctx = (struct tracks_neighbour_ctx *)vctx;
+    if (vertex >= 0) {
+        game_state *state = ctx->state;
+        int w = state->p.w, x = vertex % w, y = vertex / w;
+        int dirs = S_E_DIRS(state, x, y, E_TRACK);
+        int j;
+
+        ctx->i = ctx->n = 0;
+
+        for (j = 0; j < 4; j++) {
+            int dir = 1<<j;
+            if (dirs & dir) {
+                int nx = x + DX(dir), ny = y + DY(dir);
+                if (INGRID(state, nx, ny))
+                    ctx->neighbours[ctx->n++] = ny * w + nx;
+            }
+        }
     }
+
+    if (ctx->i < ctx->n)
+        return ctx->neighbours[ctx->i++];
+    else
+        return -1;
 }
 
 static int check_completion(game_state *state, int mark)
@@ -1518,7 +1540,9 @@
 {
     int w = state->p.w, h = state->p.h, x, y, i, target, ret = TRUE;
     int ntrack, nnotrack, ntrackcomplete;
-    int *dsf, loopclass, pathclass;
+    int *dsf, pathclass;
+    struct findloopstate *fls;
+    struct tracks_neighbour_ctx ctx;
 
     if (mark) {
         for (i = 0; i < w+h; i++) {
@@ -1585,28 +1609,35 @@
 
     dsf = snewn(w*h, int);
     dsf_init(dsf, w*h);
-    loopclass = -1;
 
     for (x = 0; x < w; x++) {
         for (y = 0; y < h; y++) {
-            dsf_update_completion(state, &loopclass, x, y, R, dsf);
-            dsf_update_completion(state, &loopclass, x, y, D, dsf);
+            dsf_update_completion(state, x, y, R, dsf);
+            dsf_update_completion(state, x, y, D, dsf);
         }
     }
-    if (loopclass != -1) {
+
+    fls = findloop_new_state(w*h);
+    ctx.state = state;
+    if (findloop_run(fls, w*h, tracks_neighbour, &ctx)) {
         debug(("loop detected, not complete"));
         ret = FALSE; /* no loop allowed */
         if (mark) {
             for (x = 0; x < w; x++) {
                 for (y = 0; y < h; y++) {
-                    /* TODO this will only highlight the first loop found */
-                    if (dsf_canonify(dsf, y*w + x) == loopclass) {
-                        state->sflags[y*w+x] |= S_ERROR;
-                    }
+                    int u, v;
+
+                    u = y*w + x;
+                    for (v = tracks_neighbour(u, &ctx); v >= 0;
+                         v = tracks_neighbour(-1, &ctx))
+                        if (findloop_is_loop_edge(fls, u, v))
+                            state->sflags[y*w+x] |= S_ERROR;
                 }
             }
         }
     }
+    findloop_free_state(fls);
+
     if (mark) {
         pathclass = dsf_canonify(dsf, state->numbers->row_s*w);
         if (pathclass == dsf_canonify(dsf, (h-1)*w + state->numbers->col_s)) {