2 * Slide puzzle core game logic
3 * Copyright © 2022-2023 Nick Bowler
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <https://www.gnu.org/licenses/>.
18 * The RNG implementation is adapted from xoshiro256** and splitmix64
19 * by David Blackman and Sebastiano Vigna, originally distributed under
20 * the Creative Commons Zero public domain dedication.
30 #define B64(x) ((x) & 0xffffffffffffffff)
32 /* Rotate val left by n bits. The behaviour is undefined if n is zero. */
33 static unsigned long long rot_left64(unsigned long long val, int n)
35 return B64( (val << n) | (val >> (64 - n)) );
38 static unsigned long long xoshiro256ss(unsigned long long *s)
40 unsigned long long tmp, ret;
42 ret = B64(rot_left64(B64(s[1]*5), 7) * 9);
43 tmp = B64(s[1] << 17);
50 s[3] = rot_left64(s[3], 45);
55 static unsigned long long splitmix64(unsigned long long *state)
59 z = B64(*state += 0x9e3779b97f4a7c15);
60 z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9);
61 z = B64((z ^ (z >> 27)) * 0x94d049bb133111eb);
66 static unsigned long long rng_state[4];
68 static int rng_is_seeded(void)
70 return rng_state[0] || rng_state[1] || rng_state[2] || rng_state[3];
73 /* Calculate the least power of two greater than val, minus 1. */
74 static unsigned rng_mask(unsigned val)
81 if (UINT_MAX >= 65536)
87 /* Return a random integer uniformly on the closed interval [0, limit-1] */
88 static unsigned rng_uniform_int(unsigned max)
90 unsigned mask = rng_mask(max-1);
91 unsigned long long val;
94 val = ( xoshiro256ss(rng_state) >> 32 ) & mask;
100 static void shuffle(unsigned char *tiles, unsigned n)
104 for (i = 1; i < n; i++) {
107 j = rng_uniform_int(i+1);
114 void game_reseed(unsigned long long seed)
116 rng_state[0] = splitmix64(&seed);
117 rng_state[1] = splitmix64(&seed);
118 rng_state[2] = splitmix64(&seed);
119 rng_state[3] = splitmix64(&seed);
122 #define assign_tile(planes, tile, bit) do { \
123 0[planes] |= (((tile)>>0) & 1ul) << (bit); \
124 1[planes] |= (((tile)>>1) & 1ul) << (bit); \
125 2[planes] |= (((tile)>>2) & 1ul) << (bit); \
128 void game_reset(struct board *board)
130 unsigned char tiles[25];
133 if (!rng_is_seeded()) {
134 unsigned long long seed;
137 * Try to get a reasonable initial seed.
139 * Reasonable in this context means:
141 * - roughly even distribution of 1/0 bits, and
142 * - unlikely to generate the same seed twice in succession.
147 seed += board->time_start;
148 seed += (unsigned long long)getpid() << 16;
154 for (i = 0; i < 24; i++) {
155 tiles[i] = (i%6) + 1;
159 memset(board->goal, 0, sizeof board->goal);
162 * Goal bitmap has 2-tile "gaps" between rows; it doesn't matter what
163 * these are set to and since we have a random permutation it doesn't
164 * matter which of the 24 nonempty tiles we pick for the actual goal.
166 for (i = 0; i < 13; i++) {
167 assign_tile(board->goal, tiles[i], i);
170 tiles[24] = TILE_EMPTY;
172 memset(board->game, 0, sizeof board->game);
174 for (i = 0; i < 25; i++) {
175 assign_tile(board->game, tiles[i], i);
177 if (tiles[i] == TILE_EMPTY) {
178 board->game[3] = (1ul<<i);
184 /* Uncomment to make every game stupidly easy -- winnable in 1 move */
186 /* Force empty space to the border */
187 if (board_position(board->x, board->y) & GOAL_MASK) {
188 switch (rng_uniform_int(4)) {
189 case 0: game_do_move(board, board->x, 0); break;
190 case 1: game_do_move(board, board->x, 4); break;
191 case 2: game_do_move(board, 0, board->y); break;
192 case 3: game_do_move(board, 4, board->y); break;
196 /* Force goal to match the current board */
197 for (i = 0; i < 3; i++) {
198 board->goal[i] = (board->game[i] & GOAL_MASK) >> GOAL_SHIFT;
201 /* Move empty space back to the centre */
202 if (board->x == 0 || board->x == 4) {
203 game_do_move(board, 1+rng_uniform_int(3), board->y);
206 if (board->y == 0 || board->y == 4) {
207 game_do_move(board, board->x, 1+rng_uniform_int(3));
212 uint_fast32_t game_do_move(struct board *board, int x, int y)
214 int bx = board->x, by = board->y;
215 uint_least32_t ret = 0, mask, val[4];
218 if ((bx != x) == (by != y))
222 mask = board_mask_v(x, by, y);
226 mask = board_mask_h(y, bx, x);
231 for (i = 0; i < 4; i++) {
232 board->game[i] ^= (val[i] = board->game[i] & mask);
233 board->game[i] |= val[i] << shl >> shr;
234 ret |= board->game[i] ^ val[i];
243 uint_fast32_t game_check_goal(struct board *board)
245 uint_least32_t *game = board->game;
246 uint_least16_t *goal = board->goal;
247 uint_least32_t mask = 0;
250 for (i = 0; i < 3; i++)
251 mask |= game[i] ^ ((0ul+goal[i]) << GOAL_SHIFT);
252 return mask & GOAL_MASK;
255 int_fast32_t game_finish(struct board *board)
257 int_fast32_t t = game_elapsed(board);
260 for (i = 0; i < 4; i++) {
261 board->game[i] &= GOAL_MASK;
265 * Setting both x and y hole location to a bogus value will effectively
266 * disable the game since there will be no valid moves.
268 board->x = board->y = -1;