src/game.c

   1 /*
   2  * Slide puzzle core game logic
   3  * Copyright © 2022 Nick Bowler
   4  *
   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.
   9  *
  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.
  14  *
  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/>.
  17  *
  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.
  21  */
  22
  23 #include <config.h>
  24 #include <limits.h>
  25 #include <string.h>
  26 #include <time.h>
  27 #include <gethrxtime.h>
  28 #include "game.h"
  29
  30 #define B64(x) ((x) & 0xffffffffffffffff)
  31
  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)
  34 {
  35         return B64( (val << n) | (val >> (64 - n)) );
  36 }
  37
  38 static unsigned long long xoshiro256ss(unsigned long long *s)
  39 {
  40         unsigned long long tmp, ret;
  41
  42         ret = B64(rot_left64(B64(s[1]*5), 7) * 9);
  43         tmp = B64(s[1] << 17);
  44
  45         s[2] ^= s[0];
  46         s[3] ^= s[1];
  47         s[1] ^= s[2];
  48         s[0] ^= s[3];
  49         s[2] ^= tmp;
  50         s[3] = rot_left64(s[3], 45);
  51
  52         return ret;
  53 }
  54
  55 static unsigned long long splitmix64(unsigned long long *state)
  56 {
  57         unsigned long long z;
  58
  59         z = B64(*state += 0x9e3779b97f4a7c15);
  60         z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9);
  61         z = B64((z ^ (z >> 27)) * 0x94d049bb133111eb);
  62
  63         return z ^ (z >> 31);
  64 }
  65
  66 static unsigned long long rng_state[4];
  67
  68 static int rng_is_seeded(void)
  69 {
  70         return rng_state[0] || rng_state[1] || rng_state[2] || rng_state[3];
  71 }
  72
  73 /* Calculate the least power of two greater than val, minus 1. */
  74 static unsigned rng_mask(unsigned val)
  75 {
  76         val |= val >> 1;
  77         val |= val >> 2;
  78         val |= val >> 4;
  79         val |= val >> 8;
  80
  81         if (UINT_MAX >= 65536)
  82                 val |= val >> 16;
  83
  84         return val;
  85 }
  86
  87 /* Return a random integer uniformly on the closed interval [0, limit-1] */
  88 static unsigned rng_uniform_int(unsigned max)
  89 {
  90         unsigned mask = rng_mask(max-1);
  91         unsigned long long val;
  92
  93         do {
  94                 val = ( xoshiro256ss(rng_state) >> 32 ) & mask;
  95         } while (val >= max);
  96
  97         return val;
  98 }
  99
 100 static void shuffle(unsigned char *tiles, unsigned n)
 101 {
 102         unsigned i, j;
 103
 104         for (i = 1; i < n; i++) {
 105                 unsigned char tmp;
 106
 107                 j = rng_uniform_int(i+1);
 108                 tmp = tiles[i];
 109                 tiles[i] = tiles[j];
 110                 tiles[j] = tmp;
 111         }
 112 }
 113
 114 void game_reseed(unsigned long long seed)
 115 {
 116         rng_state[0] = splitmix64(&seed);
 117         rng_state[1] = splitmix64(&seed);
 118         rng_state[2] = splitmix64(&seed);
 119         rng_state[3] = splitmix64(&seed);
 120 }
 121
 122 void game_reset(struct board *board)
 123 {
 124         unsigned char tiles[25];
 125         unsigned i;
 126
 127         if (!rng_is_seeded()) {
 128                 unsigned long long seed;
 129
 130                 seed = time(NULL);
 131                 seed += gethrxtime();
 132                 seed += seed << 32;
 133
 134                 game_reseed(seed);
 135         }
 136
 137         for (i = 0; i < 24; i++) {
 138                 tiles[i] = (i%6) + 1;
 139         }
 140
 141         shuffle(tiles, 24);
 142         memset(board->goal, 0, sizeof board->goal);
 143
 144         for (i = 0; i < 9; i++) {
 145                 uint_fast32_t position = board_position(i/3+1, i%3+1) >> 6;
 146
 147                 if (tiles[i] & 1) board->goal[0] |= position;
 148                 if (tiles[i] & 2) board->goal[1] |= position;
 149                 if (tiles[i] & 4) board->goal[2] |= position;
 150         }
 151
 152         tiles[24] = TILE_EMPTY;
 153         shuffle(tiles, 25);
 154
 155         memset(board->game, 0, sizeof board->game);
 156         for (i = 0; i < 25; i++) {
 157                 unsigned x = i/5, y = i%5;
 158                 uint_fast32_t position;
 159
 160                 position = board_position(x, y);
 161                 if (tiles[i] != TILE_EMPTY) {
 162                         if (tiles[i] & 1) board->game[0] |= position;
 163                         if (tiles[i] & 2) board->game[1] |= position;
 164                         if (tiles[i] & 4) board->game[2] |= position;
 165                 } else {
 166                         board->game[3] = ~position;
 167                         board->x = x;
 168                         board->y = y;
 169                 }
 170         }
 171
 172 /* Uncomment to make every game stupidly easy -- winnable in 1 move */
 173 #if 0
 174         /* Force empty space to the border */
 175         if (board_position(board->x, board->y) & GOAL_MASK) {
 176                 switch (rng_uniform_int(4)) {
 177                 case 0: game_do_move(board, board->x, 0); break;
 178                 case 1: game_do_move(board, board->x, 4); break;
 179                 case 2: game_do_move(board, 0, board->y); break;
 180                 case 3: game_do_move(board, 4, board->y); break;
 181                 }
 182         }
 183
 184         /* Force goal to match the current board */
 185         for (i = 0; i < 3; i++) {
 186                 board->goal[i] = (board->game[i] & GOAL_MASK) >> GOAL_SHIFT;
 187         }
 188
 189         /* Move empty space back to the centre */
 190         if (board->x == 0 || board->x == 4) {
 191                 game_do_move(board, 1+rng_uniform_int(3), board->y);
 192         }
 193
 194         if (board->y == 0 || board->y == 4) {
 195                 game_do_move(board, board->x, 1+rng_uniform_int(3));
 196         }
 197 #endif
 198 }
 199
 200 uint_fast32_t game_do_move(struct board *board, int x, int y)
 201 {
 202         int bx = board->x, by = board->y;
 203         uint_least32_t ret = 0, mask, val[4];
 204         int i, shl, shr;
 205
 206         if ((bx != x) == (by != y))
 207                 return 0;
 208
 209         if (bx == x) {
 210                 mask = board_mask_v(x, by, y);
 211                 shr = 5*(by < y);
 212                 shl = 5*(by > y);
 213         } else {
 214                 mask = board_mask_h(y, bx, x);
 215                 shr = bx < x;
 216                 shl = bx > x;
 217         }
 218
 219         for (i = 0; i < 4; i++) {
 220                 board->game[i] ^= (val[i] = board->game[i] & mask);
 221                 board->game[i] |= val[i] << shl >> shr;
 222                 ret |= board->game[i] ^ val[i];
 223         }
 224
 225         board->x = x;
 226         board->y = y;
 227
 228         return mask & ret;
 229 }
 230
 231 uint_fast32_t game_check_goal(struct board *board)
 232 {
 233         uint_least32_t *game = board->game;
 234         uint_least16_t *goal = board->goal;
 235         uint_least32_t mask = 0;
 236         int i;
 237
 238         for (i = 0; i < 3; i++)
 239                 mask |= game[i] ^ ((0ul+goal[i]) << GOAL_SHIFT);
 240         return mask & GOAL_MASK;
 241 }
 242
 243 void game_begin(struct board *board)
 244 {
 245         board->time_start = gethrxtime();
 246 }
 247
 248 int_fast32_t game_elapsed(struct board *board)
 249 {
 250         return (gethrxtime() - board->time_start) / 1000000;
 251 }
 252
 253 int_fast32_t game_finish(struct board *board)
 254 {
 255         int_fast32_t t = game_elapsed(board);
 256         int i;
 257
 258         for (i = 0; i < 4; i++) {
 259                 board->game[i] &= GOAL_MASK;
 260         }
 261
 262         /*
 263          * Setting both x and y hole location to a bogus value will effectively
 264          * disable the game since there will be no valid moves.
 265          */
 266         board->x = board->y = -1;
 267
 268         return t;
 269 }