X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=net.c;h=349b13dfb216edfde678f50cf8d701c4ead2e91e;hb=fc6cc8fb2b9cbc97ccd6a74c8953cc1920013141;hp=fa48a869cb4fd78568d150e837f494f47323c04a;hpb=251b21c41813055d9c416378508b1ee038bc3dac;p=sgt-puzzles.git

diff --git a/net.c b/net.c
index fa48a86..349b13d 100644
--- a/net.c
+++ b/net.c
@@ -41,6 +41,11 @@
 #define D 0x08
 #define LOCKED 0x10
 #define ACTIVE 0x20
+#define RLOOP (R << 6)
+#define ULOOP (U << 6)
+#define LLOOP (L << 6)
+#define DLOOP (D << 6)
+#define LOOP(dir) ((dir) << 6)
 
 /* Rotations: Anticlockwise, Clockwise, Flip, general rotate */
 #define A(x) ( (((x) & 0x07) << 1) | (((x) & 0x08) >> 3) )
@@ -85,6 +90,7 @@ enum {
     COL_ENDPOINT,
     COL_POWERED,
     COL_BARRIER,
+    COL_LOOP,
     NCOLOURS
 };
 
@@ -1126,6 +1132,10 @@ static void perturb(int w, int h, unsigned char *tiles, int wrapping,
     sfree(perimeter);
 }
 
+static int *compute_loops_inner(int w, int h, int wrapping,
+                                const unsigned char *tiles,
+                                const unsigned char *barriers);
+
 static char *new_game_desc(const game_params *params, random_state *rs,
 			   char **aux, int interactive)
 {
@@ -1424,10 +1434,21 @@ static char *new_game_desc(const game_params *params, random_state *rs,
      * connectedness. However, that would take more effort, and
      * it's easier to simply make sure every grid is _obviously_
      * not solved.)
+     *
+     * We also require that our shuffle produces no loops in the
+     * initial grid state, because it's a bit rude to light up a 'HEY,
+     * YOU DID SOMETHING WRONG!' indicator when the user hasn't even
+     * had a chance to do _anything_ yet. This also is possible just
+     * by retrying the whole shuffle on failure, because it's clear
+     * that at least one non-solved shuffle with no loops must exist.
+     * (Proof: take the _solved_ state of the puzzle, and rotate one
+     * endpoint.)
      */
     while (1) {
-        int mismatches;
+        int mismatches, prev_loopsquares, this_loopsquares, i;
+        int *loops;
 
+      shuffle:
         for (y = 0; y < h; y++) {
             for (x = 0; x < w; x++) {
                 int orig = index(params, tiles, x, y);
@@ -1436,6 +1457,35 @@ static char *new_game_desc(const game_params *params, random_state *rs,
             }
         }
 
+        /*
+         * Check for loops, and try to fix them by reshuffling just
+         * the squares involved.
+         */
+        prev_loopsquares = w*h+1;
+        while (1) {
+            loops = compute_loops_inner(w, h, params->wrapping, tiles, NULL);
+            this_loopsquares = 0;
+            for (i = 0; i < w*h; i++) {
+                if (loops[i]) {
+                    int orig = tiles[i];
+                    int rot = random_upto(rs, 4);
+                    tiles[i] = ROT(orig, rot);
+                    this_loopsquares++;
+                }
+            }
+            sfree(loops);
+            if (this_loopsquares > prev_loopsquares) {
+                /*
+                 * We're increasing rather than reducing the number of
+                 * loops. Give up and go back to the full shuffle.
+                 */
+                goto shuffle;
+            }
+            if (this_loopsquares == 0)
+                break;
+            prev_loopsquares = this_loopsquares;
+        }
+
         mismatches = 0;
         /*
          * I can't even be bothered to check for mismatches across
@@ -1452,8 +1502,11 @@ static char *new_game_desc(const game_params *params, random_state *rs,
                 mismatches++;
         }
 
-        if (mismatches > 0)
-            break;
+        if (mismatches == 0)
+            continue;
+
+        /* OK. */
+        break;
     }
 
     /*
@@ -1856,6 +1909,87 @@ static unsigned char *compute_active(const game_state *state, int cx, int cy)
     return active;
 }
 
+struct net_neighbour_ctx {
+    int w, h;
+    const unsigned char *tiles, *barriers;
+    int i, n, neighbours[4];
+};
+static int net_neighbour(int vertex, void *vctx)
+{
+    struct net_neighbour_ctx *ctx = (struct net_neighbour_ctx *)vctx;
+
+    if (vertex >= 0) {
+        int x = vertex % ctx->w, y = vertex / ctx->w;
+        int tile, dir, x1, y1, v1;
+
+        ctx->i = ctx->n = 0;
+
+        tile = ctx->tiles[vertex];
+        if (ctx->barriers)
+            tile &= ~ctx->barriers[vertex];
+
+        for (dir = 1; dir < 0x10; dir <<= 1) {
+            if (!(tile & dir))
+                continue;
+            OFFSETWH(x1, y1, x, y, dir, ctx->w, ctx->h);
+            v1 = y1 * ctx->w + x1;
+            if (ctx->tiles[v1] & F(dir))
+                ctx->neighbours[ctx->n++] = v1;
+        }
+    }
+
+    if (ctx->i < ctx->n)
+        return ctx->neighbours[ctx->i++];
+    else
+        return -1;
+}
+
+static int *compute_loops_inner(int w, int h, int wrapping,
+                                const unsigned char *tiles,
+                                const unsigned char *barriers)
+{
+    struct net_neighbour_ctx ctx;
+    struct findloopstate *fls;
+    int *loops;
+    int x, y;
+
+    fls = findloop_new_state(w*h);
+    ctx.w = w;
+    ctx.h = h;
+    ctx.tiles = tiles;
+    ctx.barriers = barriers;
+    findloop_run(fls, w*h, net_neighbour, &ctx);
+
+    loops = snewn(w*h, int);
+
+    for (y = 0; y < h; y++) {
+        for (x = 0; x < w; x++) {
+            int x1, y1, dir;
+            int flags = 0;
+
+            for (dir = 1; dir < 0x10; dir <<= 1) {
+                if ((tiles[y*w+x] & dir) &&
+                    !(barriers && (barriers[y*w+x] & dir))) {
+                    OFFSETWH(x1, y1, x, y, dir, w, h);
+                    if ((tiles[y1*w+x1] & F(dir)) &&
+                        findloop_is_loop_edge(fls, y*w+x, y1*w+x1))
+                        flags |= LOOP(dir);
+                }
+            }
+            loops[y*w+x] = flags;
+        }
+    }
+
+    findloop_free_state(fls);
+    return loops;
+}
+
+static int *compute_loops(const game_state *state)
+{
+    return compute_loops_inner(state->width, state->height, state->wrapping,
+                               state->tiles, state->barriers);
+}
+
 struct game_ui {
     int org_x, org_y; /* origin */
     int cx, cy;       /* source tile (game coordinates) */
@@ -1916,7 +2050,7 @@ struct game_drawstate {
     int width, height;
     int org_x, org_y;
     int tilesize;
-    unsigned char *visible;
+    int *visible;
 };
 
 /* ----------------------------------------------------------------------
@@ -2290,14 +2424,16 @@ static game_state *execute_move(const game_state *from, const char *move)
 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
 {
     game_drawstate *ds = snew(game_drawstate);
+    int i;
 
     ds->started = FALSE;
     ds->width = state->width;
     ds->height = state->height;
     ds->org_x = ds->org_y = -1;
-    ds->visible = snewn(state->width * state->height, unsigned char);
+    ds->visible = snewn(state->width * state->height, int);
     ds->tilesize = 0;                  /* undecided yet */
-    memset(ds->visible, 0xFF, state->width * state->height);
+    for (i = 0; i < state->width * state->height; i++)
+        ds->visible[i] = -1;
 
     return ds;
 }
@@ -2355,6 +2491,13 @@ static float *game_colours(frontend *fe, int *ncolours)
     ret[COL_BARRIER * 3 + 1] = 0.0F;
     ret[COL_BARRIER * 3 + 2] = 0.0F;
 
+    /*
+     * Highlighted loops are red as well.
+     */
+    ret[COL_LOOP * 3 + 0] = 1.0F;
+    ret[COL_LOOP * 3 + 1] = 0.0F;
+    ret[COL_LOOP * 3 + 2] = 0.0F;
+
     /*
      * Unpowered endpoints are blue.
      */
@@ -2527,9 +2670,14 @@ static void draw_tile(drawing *dr, const game_state *state, game_drawstate *ds,
             ey = (TILE_SIZE - TILE_BORDER - 1.0F) / 2.0F * Y(dir);
             MATMUL(tx, ty, matrix, ex, ey);
             draw_line(dr, bx+(int)cx, by+(int)cy,
-		      bx+(int)(cx+tx), by+(int)(cy+ty), col);
+		      bx+(int)(cx+tx), by+(int)(cy+ty),
+                      (tile & LOOP(dir)) ? COL_LOOP : col);
         }
     }
+    /* If we've drawn any loop-highlighted arms, make sure the centre
+     * point is loop-coloured rather than a later arm overwriting it. */
+    if (tile & (RLOOP | ULOOP | LLOOP | DLOOP))
+        draw_rect(dr, bx+(int)cx, by+(int)cy, 1, 1, COL_LOOP);
 
     /*
      * Draw the box in the middle. We do this in blue if the tile
@@ -2598,7 +2746,9 @@ static void draw_tile(drawing *dr, const game_state *state, game_drawstate *ds,
              */
             draw_rect_coords(dr, px-vx, py-vy, px+lx+vx, py+ly+vy, COL_WIRE);
             draw_rect_coords(dr, px, py, px+lx, py+ly,
-                             (tile & ACTIVE) ? COL_POWERED : COL_WIRE);
+                             ((tile & LOOP(dir)) ? COL_LOOP :
+                              (tile & ACTIVE) ? COL_POWERED :
+                              COL_WIRE));
         } else {
             /*
              * The other tile extends into our border, but isn't
@@ -2672,6 +2822,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds,
 {
     int x, y, tx, ty, frame, last_rotate_dir, moved_origin = FALSE;
     unsigned char *active;
+    int *loops;
     float angle = 0.0;
 
     /*
@@ -2765,11 +2916,13 @@ static void game_redraw(drawing *dr, game_drawstate *ds,
      * Draw any tile which differs from the way it was last drawn.
      */
     active = compute_active(state, ui->cx, ui->cy);
+    loops = compute_loops(state);
 
     for (x = 0; x < ds->width; x++)
         for (y = 0; y < ds->height; y++) {
-            unsigned char c = tile(state, GX(x), GY(y)) |
-                              index(state, active, GX(x), GY(y));
+            int c = tile(state, GX(x), GY(y)) |
+                index(state, active, GX(x), GY(y)) |
+                index(state, loops, GX(x), GY(y));
             int is_src = GX(x) == ui->cx && GY(y) == ui->cy;
             int is_anim = GX(x) == tx && GY(y) == ty;
             int is_cursor = ui->cur_visible &&
@@ -2796,12 +2949,12 @@ static void game_redraw(drawing *dr, game_drawstate *ds,
 
             if (moved_origin ||
                 index(state, ds->visible, x, y) != c ||
-                index(state, ds->visible, x, y) == 0xFF ||
+                index(state, ds->visible, x, y) == -1 ||
                 is_src || is_anim || is_cursor) {
                 draw_tile(dr, state, ds, x, y, c,
                           is_src, (is_anim ? angle : 0.0F), is_cursor);
                 if (is_src || is_anim || is_cursor)
-                    index(state, ds->visible, x, y) = 0xFF;
+                    index(state, ds->visible, x, y) = -1;
                 else
                     index(state, ds->visible, x, y) = c;
             }
@@ -2830,6 +2983,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds,
     }
 
     sfree(active);
+    sfree(loops);
 }
 
 static float game_anim_length(const game_state *oldstate,