/*
* Slide puzzle core game logic
* Copyright © 2022-2024 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 .
*
* 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
#include
#include
#include
#include
#include "game.h"
#define B64(x) ((x) & 0xffffffffffffffffull)
/* Rotate val left by n bits. The behaviour is undefined if n is zero. */
static unsigned long long rot_left64(unsigned long long val, int n)
{
return B64( (val << n) | (val >> (64 - n)) );
}
static unsigned long long xoshiro256ss(unsigned long long *s)
{
unsigned long long tmp, ret;
ret = B64(rot_left64(B64(s[1]*5), 7) * 9);
tmp = B64(s[1] << 17);
s[2] ^= s[0];
s[3] ^= s[1];
s[1] ^= s[2];
s[0] ^= s[3];
s[2] ^= tmp;
s[3] = rot_left64(s[3], 45);
return ret;
}
static unsigned long long splitmix64(unsigned long long *state)
{
unsigned long long z;
z = B64(*state += 0x9e3779b97f4a7c15ull);
z = B64((z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ull);
z = B64((z ^ (z >> 27)) * 0x94d049bb133111ebull);
return z ^ (z >> 31);
}
static unsigned long long rng_state[4];
static int rng_is_seeded(void)
{
return rng_state[0] || rng_state[1] || rng_state[2] || rng_state[3];
}
/* Calculate the least power of two greater than val, minus 1. */
static unsigned rng_mask(unsigned val)
{
val |= val >> 1;
val |= val >> 2;
val |= val >> 4;
val |= val >> 8;
if (UINT_MAX >= 65536)
val |= val >> 16;
return val;
}
/* Return a random integer uniformly on the closed interval [0, limit-1] */
static unsigned rng_uniform_int(unsigned max)
{
unsigned mask = rng_mask(max-1);
unsigned long long val;
do {
val = ( xoshiro256ss(rng_state) >> 32 ) & mask;
} while (val >= max);
return val;
}
static void shuffle(unsigned char *tiles, unsigned n)
{
unsigned i, j;
for (i = 1; i < n; i++) {
unsigned char tmp;
j = rng_uniform_int(i+1);
tmp = tiles[i];
tiles[i] = tiles[j];
tiles[j] = tmp;
}
}
void game_reseed(unsigned long long seed)
{
rng_state[0] = splitmix64(&seed);
rng_state[1] = splitmix64(&seed);
rng_state[2] = splitmix64(&seed);
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()) {
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);
/*
* 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;
shuffle(tiles, 25);
memset(board->game, 0, sizeof board->game);
for (i = 0; i < 25; i++) {
assign_tile(board->game, tiles[i], i);
if (tiles[i] == TILE_EMPTY) {
board->game[3] = (1ul<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
}
uint_fast32_t game_do_move(struct board *board, int x, int y)
{
int bx = board->x, by = board->y;
uint_least32_t ret = 0, mask, val[4];
int i, shl, shr;
if ((bx != x) == (by != y))
return 0;
if (bx == x) {
mask = board_mask_v(x, by, y);
shr = 5*(by < y);
shl = 5*(by > y);
} else {
mask = board_mask_h(y, bx, x);
shr = bx < x;
shl = bx > x;
}
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 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;
}