X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/9b4b03d31e30089e9f45f6ea166561c4c0c25a9c..3af70dd4f3397d605fe59bddfd89baf95047ea7d:/netslide.c

diff --git a/netslide.c b/netslide.c
index 11ca2ef..b72706a 100644
--- a/netslide.c
+++ b/netslide.c
@@ -82,8 +82,14 @@ struct game_params {
     float barrier_probability;
 };
 
+struct game_aux_info {
+    int width, height;
+    unsigned char *tiles;
+};
+
 struct game_state {
     int width, height, cx, cy, wrapping, completed;
+    int used_solve, just_used_solve;
     int move_count;
 
     /* position (row or col number, starting at 0) of last move. */
@@ -136,7 +142,9 @@ static struct xyd *new_xyd(int x, int y, int direction)
 }
 
 static void slide_col(game_state *state, int dir, int col);
+static void slide_col_int(int w, int h, unsigned char *tiles, int dir, int col);
 static void slide_row(game_state *state, int dir, int row);
+static void slide_row_int(int w, int h, unsigned char *tiles, int dir, int row);
 
 /* ----------------------------------------------------------------------
  * Manage game parameters.
@@ -198,9 +206,8 @@ static game_params *dup_params(game_params *params)
     return ret;
 }
 
-static game_params *decode_params(char const *string)
+static void decode_params(game_params *ret, char const *string)
 {
-    game_params *ret = default_params();
     char const *p = string;
 
     ret->wrapping = FALSE;
@@ -219,11 +226,9 @@ static game_params *decode_params(char const *string)
     } else {
         ret->height = ret->width;
     }
-
-    return ret;
 }
 
-static char *encode_params(game_params *params)
+static char *encode_params(game_params *params, int full)
 {
     char ret[400];
     int len;
@@ -231,7 +236,7 @@ static char *encode_params(game_params *params)
     len = sprintf(ret, "%dx%d", params->width, params->height);
     if (params->wrapping)
         ret[len++] = 'w';
-    if (params->barrier_probability)
+    if (full && params->barrier_probability)
         len += sprintf(ret+len, "b%g", params->barrier_probability);
     assert(len < lenof(ret));
     ret[len] = '\0';
@@ -305,87 +310,27 @@ static char *validate_params(game_params *params)
 }
 
 /* ----------------------------------------------------------------------
- * Randomly select a new game seed.
+ * Randomly select a new game description.
  */
 
-static char *new_game_seed(game_params *params, random_state *rs)
+static char *new_game_desc(game_params *params, random_state *rs,
+			   game_aux_info **aux)
 {
-    /*
-     * The full description of a Net game is far too large to
-     * encode directly in the seed, so by default we'll have to go
-     * for the simple approach of providing a random-number seed.
-     * 
-     * (This does not restrict me from _later on_ inventing a seed
-     * string syntax which can never be generated by this code -
-     * for example, strings beginning with a letter - allowing me
-     * to type in a precise game, and have new_game detect it and
-     * understand it and do something completely different.)
-     */
-    char buf[40];
-    sprintf(buf, "%lu", random_bits(rs, 32));
-    return dupstr(buf);
-}
+    tree234 *possibilities, *barriertree;
+    int w, h, x, y, cx, cy, nbarriers;
+    unsigned char *tiles, *barriers;
+    char *desc, *p;
 
-static char *validate_seed(game_params *params, char *seed)
-{
-    /*
-     * Since any string at all will suffice to seed the RNG, there
-     * is no validation required.
-     */
-    return NULL;
-}
-
-/* ----------------------------------------------------------------------
- * Construct an initial game state, given a seed and parameters.
- */
-
-static game_state *new_game(game_params *params, char *seed)
-{
-    random_state *rs;
-    game_state *state;
-    tree234 *possibilities, *barriers;
-    int w, h, x, y, nbarriers;
-
-    assert(params->width > 0 && params->height > 0);
-    assert(params->width > 1 || params->height > 1);
-
-    /*
-     * Create a blank game state.
-     */
-    state = snew(game_state);
-    w = state->width = params->width;
-    h = state->height = params->height;
-    state->cx = state->width / 2;
-    state->cy = state->height / 2;
-    state->wrapping = params->wrapping;
-    state->completed = 0;
-    state->move_count = 0;
-    state->last_move_row = -1;
-    state->last_move_col = -1;
-    state->last_move_dir = 0;
-    state->tiles = snewn(state->width * state->height, unsigned char);
-    memset(state->tiles, 0, state->width * state->height);
-    state->barriers = snewn(state->width * state->height, unsigned char);
-    memset(state->barriers, 0, state->width * state->height);
+    w = params->width;
+    h = params->height;
 
-    /*
-     * Set up border barriers if this is a non-wrapping game.
-     */
-    if (!state->wrapping) {
-	for (x = 0; x < state->width; x++) {
-	    barrier(state, x, 0) |= U;
-	    barrier(state, x, state->height-1) |= D;
-	}
-	for (y = 0; y < state->height; y++) {
-	    barrier(state, 0, y) |= L;
-	    barrier(state, state->width-1, y) |= R;
-	}
-    }
+    tiles = snewn(w * h, unsigned char);
+    memset(tiles, 0, w * h);
+    barriers = snewn(w * h, unsigned char);
+    memset(barriers, 0, w * h);
 
-    /*
-     * Seed the internal random number generator.
-     */
-    rs = random_init(seed, strlen(seed));
+    cx = w / 2;
+    cy = h / 2;
 
     /*
      * Construct the unshuffled grid.
@@ -431,14 +376,14 @@ static game_state *new_game(game_params *params, char *seed)
      */
     possibilities = newtree234(xyd_cmp);
 
-    if (state->cx+1 < state->width)
-	add234(possibilities, new_xyd(state->cx, state->cy, R));
-    if (state->cy-1 >= 0)
-	add234(possibilities, new_xyd(state->cx, state->cy, U));
-    if (state->cx-1 >= 0)
-	add234(possibilities, new_xyd(state->cx, state->cy, L));
-    if (state->cy+1 < state->height)
-	add234(possibilities, new_xyd(state->cx, state->cy, D));
+    if (cx+1 < w)
+	add234(possibilities, new_xyd(cx, cy, R));
+    if (cy-1 >= 0)
+	add234(possibilities, new_xyd(cx, cy, U));
+    if (cx-1 >= 0)
+	add234(possibilities, new_xyd(cx, cy, L));
+    if (cy+1 < h)
+	add234(possibilities, new_xyd(cx, cy, D));
 
     while (count234(possibilities) > 0) {
 	int i;
@@ -455,7 +400,7 @@ static game_state *new_game(game_params *params, char *seed)
 	d1 = xyd->direction;
 	sfree(xyd);
 
-	OFFSET(x2, y2, x1, y1, d1, state);
+	OFFSET(x2, y2, x1, y1, d1, params);
 	d2 = F(d1);
 #ifdef DEBUG
 	printf("picked (%d,%d,%c) <-> (%d,%d,%c)\n",
@@ -466,20 +411,20 @@ static game_state *new_game(game_params *params, char *seed)
 	 * Make the connection. (We should be moving to an as yet
 	 * unused tile.)
 	 */
-	tile(state, x1, y1) |= d1;
-	assert(tile(state, x2, y2) == 0);
-	tile(state, x2, y2) |= d2;
+	index(params, tiles, x1, y1) |= d1;
+	assert(index(params, tiles, x2, y2) == 0);
+	index(params, tiles, x2, y2) |= d2;
 
 	/*
 	 * If we have created a T-piece, remove its last
 	 * possibility.
 	 */
-	if (COUNT(tile(state, x1, y1)) == 3) {
+	if (COUNT(index(params, tiles, x1, y1)) == 3) {
 	    struct xyd xyd1, *xydp;
 
 	    xyd1.x = x1;
 	    xyd1.y = y1;
-	    xyd1.direction = 0x0F ^ tile(state, x1, y1);
+	    xyd1.direction = 0x0F ^ index(params, tiles, x1, y1);
 
 	    xydp = find234(possibilities, &xyd1, NULL);
 
@@ -501,7 +446,7 @@ static game_state *new_game(game_params *params, char *seed)
 	    int x3, y3, d3;
 	    struct xyd xyd1, *xydp;
 
-	    OFFSET(x3, y3, x2, y2, d, state);
+	    OFFSET(x3, y3, x2, y2, d, params);
 	    d3 = F(d);
 
 	    xyd1.x = x3;
@@ -530,20 +475,20 @@ static game_state *new_game(game_params *params, char *seed)
 	    if (d == d2)
 		continue;	       /* we've got this one already */
 
-	    if (!state->wrapping) {
+	    if (!params->wrapping) {
 		if (d == U && y2 == 0)
 		    continue;
-		if (d == D && y2 == state->height-1)
+		if (d == D && y2 == h-1)
 		    continue;
 		if (d == L && x2 == 0)
 		    continue;
-		if (d == R && x2 == state->width-1)
+		if (d == R && x2 == w-1)
 		    continue;
 	    }
 
-	    OFFSET(x3, y3, x2, y2, d, state);
+	    OFFSET(x3, y3, x2, y2, d, params);
 
-	    if (tile(state, x3, y3))
+	    if (index(params, tiles, x3, y3))
 		continue;	       /* this would create a loop */
 
 #ifdef DEBUG
@@ -560,20 +505,38 @@ static game_state *new_game(game_params *params, char *seed)
     /*
      * Now compute a list of the possible barrier locations.
      */
-    barriers = newtree234(xyd_cmp);
-    for (y = 0; y < state->height; y++) {
-	for (x = 0; x < state->width; x++) {
-
-	    if (!(tile(state, x, y) & R) &&
-                (state->wrapping || x < state->width-1))
-		add234(barriers, new_xyd(x, y, R));
-	    if (!(tile(state, x, y) & D) &&
-                (state->wrapping || y < state->height-1))
-		add234(barriers, new_xyd(x, y, D));
+    barriertree = newtree234(xyd_cmp);
+    for (y = 0; y < h; y++) {
+	for (x = 0; x < w; x++) {
+
+	    if (!(index(params, tiles, x, y) & R) &&
+                (params->wrapping || x < w-1))
+		add234(barriertree, new_xyd(x, y, R));
+	    if (!(index(params, tiles, x, y) & D) &&
+                (params->wrapping || y < h-1))
+		add234(barriertree, new_xyd(x, y, D));
 	}
     }
 
     /*
+     * Save the unshuffled grid. We do this using a separate
+     * reference-counted structure since it's a large chunk of
+     * memory which we don't want to have to replicate in every
+     * game state while playing.
+     */
+    {
+        game_aux_info *solution;
+
+	solution = snew(game_aux_info);
+	solution->width = w;
+	solution->height = h;
+	solution->tiles = snewn(w * h, unsigned char);
+	memcpy(solution->tiles, tiles, w * h);
+
+	*aux = solution;
+    }
+
+    /*
      * Now shuffle the grid.
      * FIXME - this simply does a set of random moves to shuffle the pieces.
      * A better way would be to number all the pieces, generate a placement
@@ -584,19 +547,19 @@ static game_state *new_game(game_params *params, char *seed)
      */
     {
         int i;
-        int cols = state->width - 1;
-        int rows = state->height - 1;
+        int cols = w - 1;
+        int rows = h - 1;
         for (i = 0; i < cols * rows * 2; i++) {
             /* Choose a direction: 0,1,2,3 = up, right, down, left. */
             int dir = random_upto(rs, 4);
             if (dir % 2 == 0) {
                 int col = random_upto(rs, cols);
-                if (col >= state->cx) col += 1;
-                slide_col(state, 1 - dir, col);
+                if (col >= cx) col += 1;
+                slide_col_int(w, h, tiles, 1 - dir, col);
             } else {
                 int row = random_upto(rs, rows);
-                if (row >= state->cy) row += 1;
-                slide_row(state, 2 - dir, row);
+                if (row >= cy) row += 1;
+                slide_row_int(w, h, tiles, 2 - dir, row);
             }
         }
     }
@@ -604,7 +567,7 @@ static game_state *new_game(game_params *params, char *seed)
     /*
      * And now choose barrier locations. (We carefully do this
      * _after_ shuffling, so that changing the barrier rate in the
-     * params while keeping the game seed the same will give the
+     * params while keeping the random seed the same will give the
      * same shuffled grid and _only_ change the barrier locations.
      * Also the way we choose barrier locations, by repeatedly
      * choosing one possibility from the list until we have enough,
@@ -615,8 +578,8 @@ static game_state *new_game(game_params *params, char *seed)
      * the original 10 plus 10 more, rather than getting 20 new
      * ones and the chance of remembering your first 10.)
      */
-    nbarriers = (int)(params->barrier_probability * count234(barriers));
-    assert(nbarriers >= 0 && nbarriers <= count234(barriers));
+    nbarriers = (int)(params->barrier_probability * count234(barriertree));
+    assert(nbarriers >= 0 && nbarriers <= count234(barriertree));
 
     while (nbarriers > 0) {
 	int i;
@@ -626,8 +589,8 @@ static game_state *new_game(game_params *params, char *seed)
 	/*
 	 * Extract a randomly chosen barrier from the list.
 	 */
-	i = random_upto(rs, count234(barriers));
-	xyd = delpos234(barriers, i);
+	i = random_upto(rs, count234(barriertree));
+	xyd = delpos234(barriertree, i);
 
 	assert(xyd != NULL);
 
@@ -636,11 +599,11 @@ static game_state *new_game(game_params *params, char *seed)
 	d1 = xyd->direction;
 	sfree(xyd);
 
-	OFFSET(x2, y2, x1, y1, d1, state);
+	OFFSET(x2, y2, x1, y1, d1, params);
 	d2 = F(d1);
 
-	barrier(state, x1, y1) |= d1;
-	barrier(state, x2, y2) |= d2;
+	index(params, barriers, x1, y1) |= d1;
+	index(params, barriers, x2, y2) |= d2;
 
 	nbarriers--;
     }
@@ -651,10 +614,153 @@ static game_state *new_game(game_params *params, char *seed)
     {
 	struct xyd *xyd;
 
-	while ( (xyd = delpos234(barriers, 0)) != NULL)
+	while ( (xyd = delpos234(barriertree, 0)) != NULL)
 	    sfree(xyd);
 
-	freetree234(barriers);
+	freetree234(barriertree);
+    }
+
+    /*
+     * Finally, encode the grid into a string game description.
+     * 
+     * My syntax is extremely simple: each square is encoded as a
+     * hex digit in which bit 0 means a connection on the right,
+     * bit 1 means up, bit 2 left and bit 3 down. (i.e. the same
+     * encoding as used internally). Each digit is followed by
+     * optional barrier indicators: `v' means a vertical barrier to
+     * the right of it, and `h' means a horizontal barrier below
+     * it.
+     */
+    desc = snewn(w * h * 3 + 1, char);
+    p = desc;
+    for (y = 0; y < h; y++) {
+        for (x = 0; x < w; x++) {
+            *p++ = "0123456789abcdef"[index(params, tiles, x, y)];
+            if ((params->wrapping || x < w-1) &&
+                (index(params, barriers, x, y) & R))
+                *p++ = 'v';
+            if ((params->wrapping || y < h-1) &&
+                (index(params, barriers, x, y) & D))
+                *p++ = 'h';
+        }
+    }
+    assert(p - desc <= w*h*3);
+    *p = '\0';
+
+    sfree(tiles);
+    sfree(barriers);
+
+    return desc;
+}
+
+static void game_free_aux_info(game_aux_info *aux)
+{
+    sfree(aux->tiles);
+    sfree(aux);
+}
+
+static char *validate_desc(game_params *params, char *desc)
+{
+    int w = params->width, h = params->height;
+    int i;
+
+    for (i = 0; i < w*h; i++) {
+        if (*desc >= '0' && *desc <= '9')
+            /* OK */;
+        else if (*desc >= 'a' && *desc <= 'f')
+            /* OK */;
+        else if (*desc >= 'A' && *desc <= 'F')
+            /* OK */;
+        else if (!*desc)
+            return "Game description shorter than expected";
+        else
+            return "Game description contained unexpected character";
+        desc++;
+        while (*desc == 'h' || *desc == 'v')
+            desc++;
+    }
+    if (*desc)
+        return "Game description longer than expected";
+
+    return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Construct an initial game state, given a description and parameters.
+ */
+
+static game_state *new_game(game_params *params, char *desc)
+{
+    game_state *state;
+    int w, h, x, y;
+
+    assert(params->width > 0 && params->height > 0);
+    assert(params->width > 1 || params->height > 1);
+
+    /*
+     * Create a blank game state.
+     */
+    state = snew(game_state);
+    w = state->width = params->width;
+    h = state->height = params->height;
+    state->cx = state->width / 2;
+    state->cy = state->height / 2;
+    state->wrapping = params->wrapping;
+    state->completed = 0;
+    state->used_solve = state->just_used_solve = FALSE;
+    state->move_count = 0;
+    state->last_move_row = -1;
+    state->last_move_col = -1;
+    state->last_move_dir = 0;
+    state->tiles = snewn(state->width * state->height, unsigned char);
+    memset(state->tiles, 0, state->width * state->height);
+    state->barriers = snewn(state->width * state->height, unsigned char);
+    memset(state->barriers, 0, state->width * state->height);
+
+
+    /*
+     * Parse the game description into the grid.
+     */
+    for (y = 0; y < h; y++) {
+        for (x = 0; x < w; x++) {
+            if (*desc >= '0' && *desc <= '9')
+                tile(state, x, y) = *desc - '0';
+            else if (*desc >= 'a' && *desc <= 'f')
+                tile(state, x, y) = *desc - 'a' + 10;
+            else if (*desc >= 'A' && *desc <= 'F')
+                tile(state, x, y) = *desc - 'A' + 10;
+            if (*desc)
+                desc++;
+            while (*desc == 'h' || *desc == 'v') {
+                int x2, y2, d1, d2;
+                if (*desc == 'v')
+                    d1 = R;
+                else
+                    d1 = D;
+
+                OFFSET(x2, y2, x, y, d1, state);
+                d2 = F(d1);
+
+                barrier(state, x, y) |= d1;
+                barrier(state, x2, y2) |= d2;
+
+                desc++;
+            }
+        }
+    }
+
+    /*
+     * Set up border barriers if this is a non-wrapping game.
+     */
+    if (!state->wrapping) {
+	for (x = 0; x < state->width; x++) {
+	    barrier(state, x, 0) |= U;
+	    barrier(state, x, state->height-1) |= D;
+	}
+	for (y = 0; y < state->height; y++) {
+	    barrier(state, 0, y) |= L;
+	    barrier(state, state->width-1, y) |= R;
+	}
     }
 
     /*
@@ -705,8 +811,6 @@ static game_state *new_game(game_params *params, char *seed)
 	}
     }
 
-    random_free(rs);
-
     return state;
 }
 
@@ -721,6 +825,8 @@ static game_state *dup_game(game_state *state)
     ret->cy = state->cy;
     ret->wrapping = state->wrapping;
     ret->completed = state->completed;
+    ret->used_solve = state->used_solve;
+    ret->just_used_solve = state->just_used_solve;
     ret->move_count = state->move_count;
     ret->last_move_row = state->last_move_row;
     ret->last_move_col = state->last_move_col;
@@ -740,6 +846,26 @@ static void free_game(game_state *state)
     sfree(state);
 }
 
+static game_state *solve_game(game_state *state, game_aux_info *aux,
+			      char **error)
+{
+    game_state *ret;
+
+    if (!aux) {
+	*error = "Solution not known for this puzzle";
+	return NULL;
+    }
+
+    assert(aux->width == state->width);
+    assert(aux->height == state->height);
+    ret = dup_game(state);
+    memcpy(ret->tiles, aux->tiles, ret->width * ret->height);
+    ret->used_solve = ret->just_used_solve = TRUE;
+    ret->completed = ret->move_count = 1;
+
+    return ret;
+}
+
 static char *game_text_format(game_state *state)
 {
     return NULL;
@@ -835,32 +961,42 @@ static void free_ui(game_ui *ui)
  * Process a move.
  */
 
-static void slide_row(game_state *state, int dir, int row)
+static void slide_row_int(int w, int h, unsigned char *tiles, int dir, int row)
 {
-    int x = dir > 0 ? -1 : state->width;
+    int x = dir > 0 ? -1 : w;
     int tx = x + dir;
-    int n = state->width - 1;
-    unsigned char endtile = state->tiles[T(state, tx, row)];
+    int n = w - 1;
+    unsigned char endtile = tiles[row * w + tx];
     do {
         x = tx;
-        tx = (x + dir + state->width) % state->width;
-        state->tiles[T(state, x, row)] = state->tiles[T(state, tx, row)];
+        tx = (x + dir + w) % w;
+        tiles[row * w + x] = tiles[row * w + tx];
     } while (--n > 0);
-    state->tiles[T(state, tx, row)] = endtile;
+    tiles[row * w + tx] = endtile;
 }
 
-static void slide_col(game_state *state, int dir, int col)
+static void slide_col_int(int w, int h, unsigned char *tiles, int dir, int col)
 {
-    int y = dir > 0 ? -1 : state->height;
+    int y = dir > 0 ? -1 : h;
     int ty = y + dir;
-    int n = state->height - 1;
-    unsigned char endtile = state->tiles[T(state, col, ty)];
+    int n = h - 1;
+    unsigned char endtile = tiles[ty * w + col];
     do {
         y = ty;
-        ty = (y + dir + state->height) % state->height;
-        state->tiles[T(state, col, y)] = state->tiles[T(state, col, ty)];
+        ty = (y + dir + h) % h;
+        tiles[y * w + col] = tiles[ty * w + col];
     } while (--n > 0);
-    state->tiles[T(state, col, ty)] = endtile;
+    tiles[ty * w + col] = endtile;
+}
+
+static void slide_row(game_state *state, int dir, int row)
+{
+    slide_row_int(state->width, state->height, state->tiles, dir, row);
+}
+
+static void slide_col(game_state *state, int dir, int col)
+{
+    slide_col_int(state->width, state->height, state->tiles, dir, col);
 }
 
 static game_state *make_move(game_state *state, game_ui *ui,
@@ -903,6 +1039,7 @@ static game_state *make_move(game_state *state, game_ui *ui,
     }
 
     ret = dup_game(state);
+    ret->just_used_solve = FALSE;
 
     if (dx == 0) slide_col(ret, dy, cx);
     else slide_row(ret, dx, cy);
@@ -1472,10 +1609,15 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 	    if (active[i])
 		a++;
 
-	sprintf(statusbuf, "%sMoves: %d Active: %d/%d",
-		(state->completed ? "COMPLETED! " : ""),
-                (state->completed ? state->completed : state->move_count),
-                a, n);
+	if (state->used_solve)
+	    sprintf(statusbuf, "Moves since auto-solve: %d",
+		    state->move_count - state->completed);
+	else
+	    sprintf(statusbuf, "%sMoves: %d",
+		    (state->completed ? "COMPLETED! " : ""),
+		    (state->completed ? state->completed : state->move_count));
+
+	sprintf(statusbuf + strlen(statusbuf), " Active: %d/%d", a, n);
 
 	status_bar(fe, statusbuf);
     }
@@ -1486,6 +1628,13 @@ static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
 static float game_anim_length(game_state *oldstate,
 			      game_state *newstate, int dir)
 {
+    /*
+     * Don't animate an auto-solve move.
+     */
+    if ((dir > 0 && newstate->just_used_solve) ||
+	(dir < 0 && oldstate->just_used_solve))
+	return 0.0F;
+
     return ANIM_TIME;
 }
 
@@ -1496,7 +1645,8 @@ static float game_flash_length(game_state *oldstate,
      * If the game has just been completed, we display a completion
      * flash.
      */
-    if (!oldstate->completed && newstate->completed) {
+    if (!oldstate->completed && newstate->completed &&
+	!oldstate->used_solve && !newstate->used_solve) {
         int size;
         size = 0;
         if (size < newstate->cx+1)
@@ -1532,11 +1682,13 @@ const struct game thegame = {
     dup_params,
     TRUE, game_configure, custom_params,
     validate_params,
-    new_game_seed,
-    validate_seed,
+    new_game_desc,
+    game_free_aux_info,
+    validate_desc,
     new_game,
     dup_game,
     free_game,
+    TRUE, solve_game,
     FALSE, game_text_format,
     new_ui,
     free_ui,