/*
+ * Slide puzzle core game logic
+ * Copyright © 2022-2023 Nick Bowler
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <https://www.gnu.org/licenses/>.
+ *
* The RNG implementation is adapted from xoshiro256** and splitmix64
* by David Blackman and Sebastiano Vigna, originally distributed under
* the Creative Commons Zero public domain dedication.
*/
+
#include <config.h>
#include <limits.h>
#include <string.h>
+#include <unistd.h>
#include <time.h>
#include "game.h"
rng_state[3] = splitmix64(&seed);
}
+#define assign_tile(planes, tile, bit) do { \
+ 0[planes] |= (((tile)>>0) & 1ul) << (bit); \
+ 1[planes] |= (((tile)>>1) & 1ul) << (bit); \
+ 2[planes] |= (((tile)>>2) & 1ul) << (bit); \
+} while (0)
+
void game_reset(struct board *board)
{
unsigned char tiles[25];
unsigned i;
- if (!rng_is_seeded())
- game_reseed(time(NULL));
+ if (!rng_is_seeded()) {
+ unsigned long long seed;
+
+ /*
+ * Try to get a reasonable initial seed.
+ *
+ * Reasonable in this context means:
+ *
+ * - roughly even distribution of 1/0 bits, and
+ * - unlikely to generate the same seed twice in succession.
+ */
+ game_begin(board);
+
+ seed = time(NULL);
+ seed += board->time_start;
+ seed += (unsigned long long)getpid() << 16;
+ seed += seed << 32;
+
+ game_reseed(seed);
+ }
for (i = 0; i < 24; i++) {
tiles[i] = (i%6) + 1;
shuffle(tiles, 24);
memset(board->goal, 0, sizeof board->goal);
- for (i = 0; i < 9; i++) {
- uint_fast32_t position = board_position(i/3+1, i%3+1);
-
- if (tiles[i] & 1)
- board->goal[0] |= position >> 6;
- if (tiles[i] & 2)
- board->goal[1] |= position >> 6;
- if (tiles[i] & 4)
- board->goal[2] |= position >> 6;
+ /*
+ * Goal bitmap has 2-tile "gaps" between rows; it doesn't matter what
+ * these are set to and since we have a random permutation it doesn't
+ * matter which of the 24 nonempty tiles we pick for the actual goal.
+ */
+ for (i = 0; i < 13; i++) {
+ assign_tile(board->goal, tiles[i], i);
}
tiles[24] = TILE_EMPTY;
memset(board->game, 0, sizeof board->game);
for (i = 0; i < 25; i++) {
- unsigned x = i/5, y = i%5;
- uint_fast32_t position;
+ assign_tile(board->game, tiles[i], i);
- position = board_position(x, y);
if (tiles[i] == TILE_EMPTY) {
- board->game[0] = 0x1ffffff ^ position;
- board->x = x;
- board->y = y;
- } else {
- if (tiles[i] & 1)
- board->game[1] |= position;
- if (tiles[i] & 2)
- board->game[2] |= position;
- if (tiles[i] & 4)
- board->game[3] |= position;
+ board->game[3] = (1ul<<i);
+ board->x = i%5;
+ board->y = i/5;
+ }
+ }
+
+/* Uncomment to make every game stupidly easy -- winnable in 1 move */
+#if 0
+ /* Force empty space to the border */
+ if (board_position(board->x, board->y) & GOAL_MASK) {
+ switch (rng_uniform_int(4)) {
+ case 0: game_do_move(board, board->x, 0); break;
+ case 1: game_do_move(board, board->x, 4); break;
+ case 2: game_do_move(board, 0, board->y); break;
+ case 3: game_do_move(board, 4, board->y); break;
}
}
+
+ /* Force goal to match the current board */
+ for (i = 0; i < 3; i++) {
+ board->goal[i] = (board->game[i] & GOAL_MASK) >> GOAL_SHIFT;
+ }
+
+ /* Move empty space back to the centre */
+ if (board->x == 0 || board->x == 4) {
+ game_do_move(board, 1+rng_uniform_int(3), board->y);
+ }
+
+ if (board->y == 0 || board->y == 4) {
+ game_do_move(board, board->x, 1+rng_uniform_int(3));
+ }
+#endif
}
-int game_do_move(struct board *board, int x, int y)
+uint_fast32_t game_do_move(struct board *board, int x, int y)
{
int bx = board->x, by = board->y;
- uint_least32_t mask, val[4];
+ uint_least32_t ret = 0, mask, val[4];
int i, shl, shr;
if ((bx != x) == (by != y))
- return -1;
+ return 0;
if (bx == x) {
mask = board_mask_v(x, by, y);
for (i = 0; i < 4; i++) {
board->game[i] ^= (val[i] = board->game[i] & mask);
board->game[i] |= val[i] << shl >> shr;
+ ret |= board->game[i] ^ val[i];
}
board->x = x;
board->y = y;
- return 0;
+
+ return mask & ret;
+}
+
+uint_fast32_t game_check_goal(struct board *board)
+{
+ uint_least32_t *game = board->game;
+ uint_least16_t *goal = board->goal;
+ uint_least32_t mask = 0;
+ int i;
+
+ for (i = 0; i < 3; i++)
+ mask |= game[i] ^ ((0ul+goal[i]) << GOAL_SHIFT);
+ return mask & GOAL_MASK;
+}
+
+int_fast32_t game_finish(struct board *board)
+{
+ int_fast32_t t = game_elapsed(board);
+ int i;
+
+ for (i = 0; i < 4; i++) {
+ board->game[i] &= GOAL_MASK;
+ }
+
+ /*
+ * Setting both x and y hole location to a bogus value will effectively
+ * disable the game since there will be no valid moves.
+ */
+ board->x = board->y = -1;
+
+ return t;
}
projects / rrace.git / blobdiff