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/>.
37 #define GOAL_MASK 0x739c0ul
38 #define GAME_MASK 0x1fffffful
42 * Bit planes representing the current game area.
44 * The 5x5 game board is represented by these four 25-bit values.
45 * The bits are arranged in row-major order so, for example, bit 0
46 * corresponds to position (0,0), bit 4 is position (4,0) and bit 25
49 * game[0] - least significant bit of the tile's colour.
50 * game[1] - tile colour.
51 * game[2] - most significant bit of the tile's colour.
52 * game[3] - No internal meaning. The game_reset function will clear
53 * the bit at the empty position and set all others, and
54 * game_do_move will adjust it.
56 uint_least32_t game[4];
59 * Bit planes representing the goal area.
61 * These are encoded identically to the game area, except the values
62 * are shifted right by 6 as only bits 6 through 18 are relevant.
64 * goal[0] - least significant bit of the tile's colour.
65 * goal[2] - tile colour.
66 * goal[3] - most significant bit of the tile's colour.
68 uint_least16_t goal[3];
70 /* (x, y) position of the current empty space. */
76 /* Return the board bitmap with all bits in column x set */
77 static inline uint_fast32_t board_column(int x)
79 return 0x108421ul << x;
82 /* Return the board bitmap with all bits in row y set */
83 static inline uint_fast32_t board_row(int y)
88 /* Return the board bitmap with the bit at position (x, y) set. */
89 static inline uint_fast32_t board_position(int x, int y)
91 return 1ul << x << 5*y;
95 * Return the board bitmap with set bits indicating tile locations
96 * that change with the hole at (x0, y) and the play at (x1, y).
98 static inline uint_fast32_t board_mask_h(int y, int x0, int x1)
100 uint_fast32_t row = board_row(y);
103 return (row << x0) & (row >> (4-x1));
104 return (row << x1) & (row >> (4-x0));
108 * Return the board bitmap with set bits indicating tile locations
109 * that change with the hole at (x, y0) and the play at (x, y1).
111 static inline uint_fast32_t board_mask_v(int x, int y0, int y1)
113 uint_fast32_t col = board_column(x);
116 return (col << 5*y0) & (col >> 5*(4-y1));
117 return (col << 5*y1) & (col >> 5*(4-y0));
121 * Return the board bitmap setting locations on or above row y.
123 static inline uint_fast32_t board_above(int y)
125 return ( 0x20ul << 5*y ) - 1;
129 * Return the board bitmap setting locations on or below row y.
131 static inline uint_fast32_t board_below(int y)
133 return ~( 1ul << 5*y ) + 1;
137 * Return the board bitmap setting locations on or left of column x.
139 static inline uint_fast32_t board_left(int x)
141 uint_fast32_t val = board_column(x);
143 return val | (val - 0x108421);
147 * Return the board bitmap setting locations on or right of column x.
149 static inline uint_fast32_t board_right(int x)
151 uint_fast32_t val = board_column(x);
153 return ~val + 0x108421;
157 * Return the board bitmap setting the rectangle of locations that are:
159 * - on or right of column x1, and
160 * - on or left of column x2, and
161 * - on or below row y1, and
162 * - on or above row y2.
164 * It must be the case that x2 >= x1 and y2 >= y1.
166 static inline uint_fast32_t board_rect(int x1, int y1, int x2, int y2)
168 return (board_left(x2-x1) << x1) & (board_above(y2-y1) << 5*y1);
172 * Extract the tile colour from a specific position of one of the
173 * arrays of tile bitmaps. The position is a bit index. So for
174 * example, game the tile at a given (x, y) position can be extracted
175 * by board_tile(board.game, 5*y+x).
177 #define board_tile(planes, bit) (((0[planes]<<0) >> (bit)) & 1) \
178 | (((1[planes]<<1) >> (bit)) & 2) \
179 | (((2[planes]<<2) >> (bit)) & 4)
182 * Move the bits in the game bitmaps according to a move at position (x, y),
183 * and update the location of the empty position which, if the move was valid
186 * Returns the board bitmap indicating which positions changed. A return
187 * value of 0 therefore indicates an invalid move.
189 uint_fast32_t game_do_move(struct board *board, int x, int y);
192 * Returns the board bitmap setting game locations that differ from the goal.
193 * A return value of 0 therefore indicates a winning position.
195 uint_fast32_t game_check_goal(struct board *board);
198 * Initialize the game RNG such that the next call to game_reset will produce a
199 * new board that is entirely dependent on the given seed value.
201 void game_reseed(unsigned long long seed);
204 * Shuffle the game and goal tiles to produce a new game state.
206 void game_reset(struct board *board);
209 * Reset the game start time.
211 void game_begin(struct board *board);
214 * Return the total elapsed time (in ms) since the last call to game_begin.
216 int_fast32_t game_elapsed(struct board *board);
219 * Disable new moves and clear all tile bits other than the 9 goal tiles.
220 * Returns the total elapsed time (in ms).
222 int_fast32_t game_finish(struct board *board);
225 * Constructs a new set of game bitmaps into buf, with tiles in the
226 * objective area replaced by the goal tile colours, and returns buf.
228 static inline uint_least32_t *
229 game_overlay_goal(struct board *board, uint_least32_t *buf)
233 for (i = 0; i < 3; i++) {
234 buf[i] = (unsigned long)board->goal[i] << GOAL_SHIFT;
235 buf[i] = (buf[i] & GOAL_MASK) | (board->game[i] & ~GOAL_MASK);