Changed representation, implemented most basic things for tak.h

1 files changed, 268 insertions, 39 deletions

diff --git a/include/tak.c b/include/tak.c
index a4c053b..d772b5d 100644
--- a/include/tak.c
+++ b/include/tak.c
@@ -1,59 +1,288 @@
 #include "tak.h"
 
-// Be sure not to set higher bits in colour than LSB
-void set_stone(board_t board, bit_board_t *capstand,
-               const uint8_t location,
-               const uint8_t colour,
-               const enum STONE_VARIANT stone) {
+// -------------------------------------------------------------------
+// Helpers
 
-  board[location] = (STONE_IS_CAPSTAND(stone) ? CELL_MASK_CAPSTAND : 0x0000)
-    | CELL_COUNT_INC | colour;
-  if (stone == STONE_CAPSTONE) BITBOARD_SET(*capstand, location);
-}
+#define NUM_SHIFT  4
+#define NUM_INC    (0x1<<NUM_SHIFT) // 0b00010000
+#define NUM_MASK   (0xF<<NUM_SHIFT) // 0b11110000
+#define STONE_MASK 0b00000011
+#define DFS_MASK   0b00001100
+#define USED_MASK  0b11110011
+
+#define STONE_AT(l) (celldat[(l)] & STONE_MASK)
+#define COUNT_AT(l) (celldat[(l)] >> NUM_SHIFT)
 
-// This can overflow, checks are elsewhere
-void push_cells_stack(board_t board, bit_board_t *capstand,
-                      const uint8_t location, const uint8_t count,
-                      const uint8_t colours,
-                      const enum STONE_VARIANT top_stone) {
+#define THE_COORDS(x,y) ((x)+(y)*board_size)
 
-  if (top_stone == STONE_CAPSTONE) BITBOARD_RST(*capstand, location);
+// -------------------------------------------------------------------
+// Game management
 
-  const cell_t cell = board[location];
-  const uint8_t new_count = CELL_GET_COUNT(cell) + count;
-  const uint8_t new_stack = (CELL_GET_STACK(cell) << count) | colours;
+uint8_t init_game() {
+  colours = calloc(board_size * board_size, sizeof(colour_stack_t));
+  if (colours == NULL) return -1;
+  celldat = calloc(board_size * board_size, sizeof(data_t));
+  if (celldat == NULL) return -1;
 
-  board[location] = (STONE_IS_CAPSTAND(top_stone) ? CELL_MASK_CAPSTAND : 0x0000)
-    | ((new_count > 0xA) ? 0xA : new_count)
-    | (new_stack & CELL_MASK_STACK);
+  reset_game();
+  return 0;
 }
 
-// Calling this with count = 0 is destructive
-void drop_cells_stack(board_t board, bit_board_t *capstand,
-                     const uint8_t location, const uint8_t count) {
+void reset_game() {
+  if (board_size == 6) {
+    white_flats = 30; black_flats = 30;
+  } else {
+    white_flats = 21; black_flats = 21;
+  }
+  white_caps = 1; black_caps = 1;
 
-  // NOTE: We always clear the bitboard and capstand flags as it's not
-  // possible that those stones are underneath anything.
+  turn = 0;
 
-  BITBOARD_RST(*capstand, location);
-  const uint8_t cur_count = CELL_GET_COUNT(board[location]);
-  if (count >= cur_count) {
-    board[location] = CELL_EMPTY_VALUE;
-  } else {
-    board[location] = ((cur_count - count) << CELL_COUNT_SHIFT)
-      | (CELL_GET_STACK(board[location]) >> count);
+  for (uint8_t k = 0; k < board_size * board_size; k++ ) {
+    celldat[k] = 0;
   }
 }
 
-enum ACTION_RESULT try_place_stone(board_t board, bit_board_t *capstand,
-                                   const uint8_t location, const uint8_t colour,
-                                   const enum STONE_VARIANT stone)
+void free_game() {
+  free(colours);
+  free(celldat);
+}
+
+// -------------------------------------------------------------------
+// Place stone
+
+enum ACTION_RESULT
+try_place(const int8_t location, const enum COLOUR colour,
+          const enum STONE_VARIANT stone)
 {
   // Can't place on an occupied square
-  if (CELL_IS_EMPTY(board[location])) {
-    set_stone(board, capstand, location, colour, stone);
-    return A_OK;
+  if (COUNT_AT(location)) {
+    return A_ILLEGAL;
   } else {
+    switch (stone) {
+      case STONE_STANDING: ;
+      case STONE_FLAT: {
+        if (colour == C_BLACK) {
+          if (black_flats) black_flats--;
+          else return A_ILLEGAL;
+        } else {
+          if (white_flats) white_flats--;
+          else return A_ILLEGAL;
+        }
+        break;
+      }
+      case STONE_CAPSTONE: {
+        if (colour == C_BLACK) {
+          if (black_caps) black_caps--;
+          else return A_ILLEGAL;
+        } else {
+          if (white_caps) white_caps--;
+          else return A_ILLEGAL;
+        }
+        break;
+      }
+    }
+
+    colours[location] = colour;
+    celldat[location] = NUM_INC | stone;
+    return A_OK;
+  }
+}
+
+// -------------------------------------------------------------------
+// Move stack
+
+void
+push_stones(const int8_t location, const uint8_t count, const uint8_t new_colours,
+            const enum STONE_VARIANT top_stone) {
+  colours[location]  = (colours[location] << count) | new_colours;
+  celldat[location]  = ((celldat[location] + ((count << NUM_SHIFT))) & NUM_MASK) | top_stone;
+}
+
+void
+drop_stones(const int8_t location, const uint8_t count) {
+  // Calling this with count = 0 is destructive
+  colours[location] >>= count;
+  const uint8_t dec_count = celldat[location] + (((~count) << NUM_SHIFT));
+  celldat[location] = dec_count & NUM_MASK;
+}
+
+enum ACTION_RESULT
+try_move(const int8_t location, const enum MOVE_DIRECTION direction,
+         const uint8_t steps, const uint8_t * const drops) {
+  // Can't do this
+  if (steps == 0) return A_ILLEGAL;
+
+  int8_t delta;
+  // Is the desired direction and count on the board?
+  switch (direction) {
+    case M_UP:    {
+      delta = +board_size;
+      if (location + delta * steps > board_size * board_size) return A_ILLEGAL;
+      else break;
+    };
+    case M_DOWN:  {
+      delta = -board_size;
+      if (location + delta * steps < 0) return A_ILLEGAL;
+      else break;
+    };
+    case M_RIGHT: {
+      delta = +1;
+      if (location + delta * steps > board_size * board_size) return A_ILLEGAL;
+      else break;
+    };
+    case M_LEFT:  {
+      delta = -1;
+      if (location + delta * steps < 0) return A_ILLEGAL;
+      else break;
+    };
+  };
+
+  // For every square in the direction
+  uint8_t total = 0;
+  for (uint8_t k = 0; k < steps; k++) {
+    // Can't drop 0 anywhere because we're past the first square
+    if (drops[k] == 0)
+      return A_ILLEGAL;
+    // Can't drop more than BOARD_SIZE stones in a square
+    if (drops[k] > board_size)
+      return A_ILLEGAL;
+    // Check for overflows
+    if (COUNT_AT(location+(k+1)*delta) + drops[k] > 0x0F)
+      return A_OVERFLOW;
+    // Check for capstone
+    if (STONE_AT(location+(k+1)*delta) == STONE_CAPSTONE)
+      return A_ILLEGAL;
+    // Check for wall
+    if ( (STONE_AT(location+(k+1)*delta) == STONE_STANDING)
+         // If not last drop, or not dropping just one, or not a cap
+         && ( (k+1 < steps)
+              || (drops[k] != 1)
+              || (STONE_AT(location) != STONE_CAPSTONE) )
+         )
+      return A_ILLEGAL;
+    total += drops[k];
+  }
+
+  // Can't ask to move more than BOARD_SIZE or stones available
+  if ( (total > board_size) || (total > COUNT_AT(location)) )
     return A_ILLEGAL;
+
+  // Nothing illegal, do it
+  uint8_t j = total;
+  for (uint8_t k = 0; k < steps; k++) {
+    j -= drops[k];
+    push_stones(location+(k+1)*delta,
+                drops[k],
+                (colours[location] >> j) & (0xFFFF >> (16 - drops[k])),
+                (k == steps - 1) ? STONE_AT(location) : STONE_FLAT);
+  }
+
+  drop_stones(location, COUNT_AT(location)-total);
+
+  return A_OK;
+}
+
+// -------------------------------------------------------------------
+// Win conditions
+
+uint8_t
+board_full(void) {
+  for (uint8_t k; k < board_size*board_size; k++) {
+    if (COUNT_AT(k) == 0) return 0;
+  }
+  return 1;
+}
+
+// direction == 0 --> left-to-right, otherwise --> top-to-bottom
+uint8_t
+dfs_road(uint8_t dfs_stack[board_size*board_size], uint8_t dfs_pntr,
+         const enum COLOUR colour, const uint8_t direction) {
+  while (dfs_pntr > 0) {
+    const uint8_t cur = dfs_stack[--dfs_pntr];
+    // Made it to the other side?
+    if (direction) {
+      if (cur >= board_size * (board_size - 1))
+        return 1;
+    } else {
+      if (cur % board_size == 0)
+        return 1;
+    }
+    // Add neighbours of appropriate colour
+    if ( (cur + 1 < board_size * board_size)
+         && ((colours[cur+1] & 1) == colour)
+         && ((celldat[cur+1] & DFS_MASK) == 0) ) {
+      dfs_stack[dfs_pntr++] = cur + 1;
+      celldat[cur+1] |= DFS_MASK;
+    }
+    if ( (cur >= 1)
+         && ((colours[cur-1] & 1) == colour)
+         && ((celldat[cur-1] & DFS_MASK) == 0) ) {
+      dfs_stack[dfs_pntr++] = cur - 1;
+      celldat[cur-1] |= DFS_MASK;
+    }
+    if ( (cur + board_size < board_size * board_size)
+         && ((colours[cur+board_size] & 1) == colour)
+         && ((celldat[cur+board_size] & DFS_MASK) == 0) ) {
+      dfs_stack[dfs_pntr++] = cur + board_size;
+      celldat[cur+board_size] |= DFS_MASK;
+    }
+    if ( (cur >= board_size)
+         && ((colours[cur-board_size] & 1) == colour)
+         && ((celldat[cur-board_size] & DFS_MASK) == 0) ) {
+      dfs_stack[dfs_pntr++] = cur - board_size;
+      celldat[cur-board_size] |= DFS_MASK;
+    }
   }
+  return 0;
+}
+
+enum WIN_RESULT
+check_win(const enum COLOUR colour) {
+  // Do we do a flat count?
+  if (black_flats == 0 || white_flats == 0 || board_full()) {
+      int8_t total = 0;
+      for (uint8_t k = 0; k < board_size * board_size; k++) {
+        if (STONE_AT(k) == STONE_FLAT) {
+          total += ((colours[k] & 1) == C_BLACK) ? +1 : -1 ;
+        }
+      }
+      if (total > 0) return W_FLAT_BLACK;
+      else return W_FLAT_WHITE;
+  }
+
+  // Road?
+  uint8_t dfs_stack[board_size * board_size];
+  uint8_t dfs_pntr = 0;
+
+  // Prime the depth-first-search stack with all boundary cells of
+  // colour COLOUR, we're using the two left-over bits in data_t to
+  // track whether we've seen it. Reset those before anything.
+
+  for (uint8_t k=0; k<board_size*board_size; k++) {
+    celldat[k] &= USED_MASK;
+  }
+
+  enum WIN_RESULT res = (colour == C_BLACK) ?
+    W_ROAD_BLACK : W_ROAD_WHITE;
+
+  // First left-to-right
+  for (uint8_t y=0; y<board_size; y++) {
+    if ( (colours[THE_COORDS(0, y)] & 1) == colour) {
+      dfs_stack[dfs_pntr++] = THE_COORDS(0, y);
+      celldat[THE_COORDS(0, y)] |= DFS_MASK;
+    }
+  }
+  if (dfs_road(dfs_stack, dfs_pntr, colour, 0)) return res;
+
+  // Then top-to-bottom
+  for (uint8_t x=1; x+1<board_size; x++) {
+    if ( (colours[THE_COORDS(x, 0)] & 1) == colour) {
+      dfs_stack[dfs_pntr++] = THE_COORDS(x, 0);
+      celldat[THE_COORDS(x, 0)] |= DFS_MASK;
+    }
+  }
+  if (dfs_road(dfs_stack, dfs_pntr, colour, 1)) return res;
+
+  return W_NONE;
 }