path: root/include/state.c

#include <state.h>

// -------------------------------------------------------------------
// Helpers

#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)

#define THE_COORDS(x,y) ((x)+(y)*board_size)

// -------------------------------------------------------------------
// Game management

void reset_game() {
  if (board_size == 6) {
    white_flats = 30; black_flats = 30;
  } else {
    board_size = 5;
    white_flats = 21; black_flats = 21;
  }
  white_caps = 1; black_caps = 1;

  turn = 0;

  for (uint8_t k = 0; k < board_size * board_size; k++ ) {
    celldat[k] = 0;
  }
}

// -------------------------------------------------------------------
// 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 (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 drops[5]) {
  // Can't do this
  if (steps == 0 || steps > 5) 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;
}