X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/2ac6d24e968232e9040ee0bca5e605b3a75e9c39..1507058f4e2f6d72ffbf3b342d280f8702b1cfb6:/netslide.c

diff --git a/netslide.c b/netslide.c
index f367621..6bac447 100644
--- a/netslide.c
+++ b/netslide.c
@@ -82,9 +82,8 @@ struct game_params {
     float barrier_probability;
 };
 
-struct solved_game_state {
+struct game_aux_info {
     int width, height;
-    int refcount;
     unsigned char *tiles;
 };
 
@@ -101,7 +100,6 @@ struct game_state {
 
     unsigned char *tiles;
     unsigned char *barriers;
-    struct solved_game_state *solution;
 };
 
 #define OFFSET(x2,y2,x1,y1,dir,state) \
@@ -144,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.
@@ -206,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;
@@ -227,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;
@@ -239,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';
@@ -313,94 +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 void game_free_aux_info(game_aux_info *aux)
-{
-    assert(!"Shouldn't happen");
-}
+    w = params->width;
+    h = params->height;
 
-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;
+    tiles = snewn(w * h, unsigned char);
+    memset(tiles, 0, w * h);
+    barriers = snewn(w * h, unsigned char);
+    memset(barriers, 0, w * h);
 
-    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);
-
-    /*
-     * 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;
-	}
-    }
-
-    /*
-     * Seed the internal random number generator.
-     */
-    rs = random_init(seed, strlen(seed));
+    cx = w / 2;
+    cy = h / 2;
 
     /*
      * Construct the unshuffled grid.
@@ -446,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;
@@ -470,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",
@@ -481,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);
 
@@ -516,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;
@@ -545,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
@@ -575,16 +505,16 @@ 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));
 	}
     }
 
@@ -595,16 +525,15 @@ static game_state *new_game(game_params *params, char *seed)
      * game state while playing.
      */
     {
-	struct solved_game_state *solution;
+        game_aux_info *solution;
 
-	solution = snew(struct solved_game_state);
-	solution->width = state->width;
-	solution->height = state->height;
-	solution->refcount = 1;
-	solution->tiles = snewn(state->width * state->height, unsigned char);
-	memcpy(solution->tiles, state->tiles, state->width * state->height);
+	solution = snew(game_aux_info);
+	solution->width = w;
+	solution->height = h;
+	solution->tiles = snewn(w * h, unsigned char);
+	memcpy(solution->tiles, tiles, w * h);
 
-	state->solution = solution;
+	*aux = solution;
     }
 
     /*
@@ -618,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);
             }
         }
     }
@@ -638,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,
@@ -649,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;
@@ -660,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);
 
@@ -670,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--;
     }
@@ -685,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;
+	}
     }
 
     /*
@@ -739,8 +811,6 @@ static game_state *new_game(game_params *params, char *seed)
 	}
     }
 
-    random_free(rs);
-
     return state;
 }
 
@@ -765,19 +835,12 @@ static game_state *dup_game(game_state *state)
     memcpy(ret->tiles, state->tiles, state->width * state->height);
     ret->barriers = snewn(state->width * state->height, unsigned char);
     memcpy(ret->barriers, state->barriers, state->width * state->height);
-    ret->solution = state->solution;
-    if (ret->solution)
-	ret->solution->refcount++;
 
     return ret;
 }
 
 static void free_game(game_state *state)
 {
-    if (state->solution && --state->solution->refcount <= 0) {
-	sfree(state->solution->tiles);
-	sfree(state->solution);
-    }
     sfree(state->tiles);
     sfree(state->barriers);
     sfree(state);
@@ -788,24 +851,17 @@ static game_state *solve_game(game_state *state, game_aux_info *aux,
 {
     game_state *ret;
 
-    if (!state->solution) {
-	/*
-	 * 2005-05-02: This shouldn't happen, at the time of
-	 * writing, because Net is incapable of receiving a puzzle
-	 * description from outside. If in future it becomes so,
-	 * then we will have puzzles for which we don't know the
-	 * solution.
-	 */
+    if (!aux) {
 	*error = "Solution not known for this puzzle";
 	return NULL;
     }
 
-    assert(state->solution->width == state->width);
-    assert(state->solution->height == state->height);
+    assert(aux->width == state->width);
+    assert(aux->height == state->height);
     ret = dup_game(state);
-    memcpy(ret->tiles, state->solution->tiles, ret->width * ret->height);
+    memcpy(ret->tiles, aux->tiles, ret->width * ret->height);
     ret->used_solve = ret->just_used_solve = TRUE;
-    ret->completed = ret->move_count;
+    ret->completed = ret->move_count = 1;
 
     return ret;
 }
@@ -905,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,
@@ -940,6 +1006,8 @@ static game_state *make_move(game_state *state, game_ui *ui,
     int n, dx, dy;
     game_state *ret;
 
+    button &= ~MOD_MASK;
+
     if (button != LEFT_BUTTON && button != RIGHT_BUTTON)
         return NULL;
 
@@ -1616,9 +1684,9 @@ const struct game thegame = {
     dup_params,
     TRUE, game_configure, custom_params,
     validate_params,
-    new_game_seed,
+    new_game_desc,
     game_free_aux_info,
-    validate_seed,
+    validate_desc,
     new_game,
     dup_game,
     free_game,