#include // ------------------------------------------------------------------- // Helpers #define NUM_SHIFT 4 #define NUM_INC (0x1<> NUM_SHIFT) #define THE_COORDS(x,y) ((x)+(y)*board_size) // ------------------------------------------------------------------- // Game management void reset_state(const uint8_t new_board_size) { if (new_board_size == 6) { 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