src/game.h

   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
  19 #ifndef RRACE_GAME_H_
  20 #define RRACE_GAME_H_
  21
  22 #include <inttypes.h>
  23 #include <xtime.h>
  24
  25 enum {
  26         TILE_EMPTY,
  27         TILE_RED,
  28         TILE_ORANGE,
  29         TILE_YELLOW,
  30         TILE_GREEN,
  31         TILE_BLUE,
  32         TILE_WHITE,
  33         TILE_MAX
  34 };
  35
  36 #define GOAL_SHIFT 6
  37 #define GOAL_MASK 0x739c0ul
  38 #define GAME_MASK 0x1fffffful
  39
  40 struct board {
  41         /*
  42          * Bit planes representing the current game area.
  43          *
  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
  47          * is position (4, 4).
  48          *
  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.
  55          */
  56         uint_least32_t game[4];
  57
  58         /*
  59          * Bit planes representing the goal area.
  60          *
  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.
  63          *
  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.
  67          */
  68         uint_least16_t goal[3];
  69
  70         /* (x, y) position of the current empty space. */
  71         uint_least8_t x, y;
  72
  73         xtime_t time_start;
  74 };
  75
  76 /* Return the board bitmap with all bits in column x set */
  77 static inline uint_fast32_t board_column(int x)
  78 {
  79         return 0x108421ul << x;
  80 }
  81
  82 /* Return the board bitmap with all bits in row y set */
  83 static inline uint_fast32_t board_row(int y)
  84 {
  85         return 0x1ful << 5*y;
  86 }
  87
  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)
  90 {
  91         return 1ul << x << 5*y;
  92 }
  93
  94 /*
  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).
  97  */
  98 static inline uint_fast32_t board_mask_h(int y, int x0, int x1)
  99 {
 100         uint_fast32_t row = board_row(y);
 101
 102         if (x0 < x1)
 103                 return (row << x0) & (row >> (4-x1));
 104         return (row << x1) & (row >> (4-x0));
 105 }
 106
 107 /*
 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).
 110  */
 111 static inline uint_fast32_t board_mask_v(int x, int y0, int y1)
 112 {
 113         uint_fast32_t col = board_column(x);
 114
 115         if (y0 < y1)
 116                 return (col << 5*y0) & (col >> 5*(4-y1));
 117         return (col << 5*y1) & (col >> 5*(4-y0));
 118 }
 119
 120 /*
 121  * Return the board bitmap setting locations on or above row y.
 122  */
 123 static inline uint_fast32_t board_above(int y)
 124 {
 125         return ( 0x20ul << 5*y ) - 1;
 126 }
 127
 128 /*
 129  * Return the board bitmap setting locations on or below row y.
 130  */
 131 static inline uint_fast32_t board_below(int y)
 132 {
 133         return ~( 1ul << 5*y ) + 1;
 134 }
 135
 136 /*
 137  * Return the board bitmap setting locations on or left of column x.
 138  */
 139 static inline uint_fast32_t board_left(int x)
 140 {
 141         uint_fast32_t val = board_column(x);
 142
 143         return val | (val - 0x108421);
 144 }
 145
 146 /*
 147  * Return the board bitmap setting locations on or right of column x.
 148  */
 149 static inline uint_fast32_t board_right(int x)
 150 {
 151         uint_fast32_t val = board_column(x);
 152
 153         return ~val + 0x108421;
 154 }
 155
 156 /*
 157  * Return the board bitmap setting the rectangle of locations that are:
 158  *
 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.
 163  *
 164  * It must be the case that x2 >= x1 and y2 >= y1.
 165  */
 166 static inline uint_fast32_t board_rect(int x1, int y1, int x2, int y2)
 167 {
 168         return (board_left(x2-x1) << x1) & (board_above(y2-y1) << 5*y1);
 169 }
 170
 171 /*
 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).
 176  */
 177 #define board_tile(planes, bit) (((0[planes]<<0) >> (bit)) & 1) \
 178                               | (((1[planes]<<1) >> (bit)) & 2) \
 179                               | (((2[planes]<<2) >> (bit)) & 4)
 180
 181 /*
 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
 184  * is now (x, y).
 185  *
 186  * Returns the board bitmap indicating which positions changed.  A return
 187  * value of 0 therefore indicates an invalid move.
 188  */
 189 uint_fast32_t game_do_move(struct board *board, int x, int y);
 190
 191 /*
 192  * Returns the board bitmap setting game locations that differ from the goal.
 193  * A return value of 0 therefore indicates a winning position.
 194  */
 195 uint_fast32_t game_check_goal(struct board *board);
 196
 197 /*
 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.
 200  */
 201 void game_reseed(unsigned long long seed);
 202
 203 /*
 204  * Shuffle the game and goal tiles to produce a new game state.
 205  */
 206 void game_reset(struct board *board);
 207
 208 /*
 209  * Reset the game start time.
 210  */
 211 void game_begin(struct board *board);
 212
 213 /*
 214  * Return the total elapsed time (in ms) since the last call to game_begin.
 215  */
 216 int_fast32_t game_elapsed(struct board *board);
 217
 218 /*
 219  * Disable new moves and clear all tile bits other than the 9 goal tiles.
 220  * Returns the total elapsed time (in ms).
 221  */
 222 int_fast32_t game_finish(struct board *board);
 223
 224 #endif