From: Simon Tatham <anakin@pobox.com>
Date: Wed, 24 Feb 2016 19:14:31 +0000 (+0000)
Subject: Tracks: use the new findloop for loop detection.
X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=sgt-puzzles.git;a=commitdiff_plain;h=01844d39c6c92d5ce417519ef2bdced6346f2549;hp=a2380d277a50b02d9575017559d95d562986488a

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.
---

diff --git a/tracks.R b/tracks.R
index 1535944..f88dfb0 100644
--- 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
 
diff --git a/tracks.c b/tracks.c
index cecfe7c..d633a9c 100644
--- a/tracks.c
+++ b/tracks.c
@@ -1490,11 +1490,10 @@ static void debug_state(game_state *state, const char *what) {
     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,22 +1502,47 @@ static void dsf_update_completion(game_state *state, int *loopclass,
     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)
 {
     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 @@ static int check_completion(game_state *state, int mark)
 
     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)) {