diff options
Diffstat (limited to 'include/tak.c')
| -rw-r--r-- | include/tak.c | 486 |
1 files changed, 485 insertions, 1 deletions
diff --git a/include/tak.c b/include/tak.c index 1c47aeb..6059794 100644 --- a/include/tak.c +++ b/include/tak.c @@ -1,12 +1,496 @@ #include "tak.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) + +// ------------------------------------------------------------------- +// General state stuff + +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; + current_colour = C_BLACK; + + for (uint8_t k = 0; k < board_size * board_size; k++ ) { + celldat[k] = 0; + } +} + +void +next_turn(void) { + turn++; + if (turn == 2) { + current_colour = C_WHITE; + } else { + if (current_colour == C_BLACK) current_colour = C_WHITE; + else current_colour = C_BLACK; + } +} + +// ------------------------------------------------------------------- +// Place stone + +enum E_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 + +static 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; +} + +static 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 E_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 >> (0x10 - drops[k])), + (k == steps - 1) ? STONE_AT(location) : STONE_FLAT); + } + + drop_stones(location, total); + + return A_OK; +} + +// ------------------------------------------------------------------- +// Win conditions + +static 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 +static 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; +} + +static enum E_RESULT +check_road_colour(const enum COLOUR colour) { + 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. + + const enum E_RESULT winner = + (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 winner; + + // 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 winner; + + return W_NONE; +} + +enum E_RESULT +check_win(void) { + // 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 if (total < 0) { + return W_FLAT_WHITE; + } else { + return W_DRAW; + } + } + + // Road? + + // We're using the two left-over bits in data_t to track whether + // we've seen it. Reset those before anything. No need to do it + // between checks, however, as pieces are black XOR white. + + for (uint8_t k=0; k<board_size*board_size; k++) { + celldat[k] &= USED_MASK; + } + + enum E_RESULT rb, rw; + rb = check_road_colour(C_BLACK); + rw = check_road_colour(C_WHITE); + + if (rb == W_ROAD_BLACK) { + if (rw == W_ROAD_WHITE) { + return W_DRAGON; + } else { + return W_ROAD_BLACK; + } + } else { + return rw; + } +} + +// ------------------------------------------------------------------- +// PTN place parser + +#define ASSERT_NONEMPTY { if (ptn == 0 || *ptn == 0) return PTN_INVALID; } +#define ASSERT_MORE { if (*ptn == 0) return PTN_INVALID; } + +enum E_RESULT +parse_place(const uint8_t board_size, char *ptn, + uint8_t *out_location, enum STONE_VARIANT *out_stone) { + + if (board_size < 5 || board_size > 6) return PTN_INVALID; + + ASSERT_NONEMPTY; + + *out_stone = STONE_FLAT; + switch (*ptn) { + case 'C' : { ptn++; *out_stone = STONE_CAPSTONE; break; }; + case 'S' : { ptn++; *out_stone = STONE_STANDING; break; }; + case 'F' : { ptn++; break; }; + } + + ASSERT_MORE; + + if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; + *out_location = *ptn - 'a'; + + ptn++; ASSERT_MORE; + + if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; + *out_location += board_size * (*ptn - '1'); + + if (*(++ptn) > 0) return PTN_INVALID; + + return PTN_VALID; +} + +// ------------------------------------------------------------------- +// PTN move parser + +enum E_RESULT +parse_move(const uint8_t board_size, char *ptn, + uint8_t *out_location, enum MOVE_DIRECTION *out_direction, + uint8_t *out_steps, uint8_t out_drops[5]) { + + if (board_size < 5 || board_size > 6) return PTN_INVALID; + + ASSERT_NONEMPTY; + + uint8_t picked_up = 1; + + if ( (*ptn >= '1') && (*ptn <= '0' + board_size)) { + picked_up = *ptn - '0'; + ptn++; ASSERT_MORE; + } + + if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; + *out_location = *ptn - 'a'; + + ptn++; ASSERT_MORE; + + if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; + *out_location += board_size * (*ptn - '1'); + + ptn++; ASSERT_MORE; + + switch (*ptn) { + case '+': { *out_direction = M_UP; break; } + case '-': { *out_direction = M_DOWN; break; } + case '<': { *out_direction = M_LEFT; break; } + case '>': { *out_direction = M_RIGHT; break; } + default: return PTN_INVALID; + } + + ptn++; + // Handle the case '[1]<column><row><direction>' as + // '1<column><row><direction>1' for convenience + if (*ptn == 0) { + if (picked_up == 1) { + *out_steps = 1; + out_drops[0] = 1; + } else { + return PTN_INVALID; + } + } + + *out_steps = 0; + uint8_t total = 0; + while (*ptn) { + if ( (*ptn < '1') || (*ptn > '0' + board_size) ) { + return PTN_INVALID; + } + + if ( (*out_steps + 1 >= board_size) && *ptn) return PTN_INVALID; + + out_drops[*out_steps] = *ptn - '0'; + total += out_drops[*out_steps]; + *out_steps += 1; + ptn++; + } + + if ( total != picked_up ) return PTN_INVALID; + + return PTN_VALID; +} + +// ------------------------------------------------------------------- +// Generate PTN for place + +void +generate_place(const uint8_t board_size, const uint8_t in_location, + const enum STONE_VARIANT in_stone, char out_ptn[4]) { + switch (in_stone) { + case STONE_FLAT: { break; } + case STONE_STANDING: { *out_ptn = 'S'; out_ptn++; break; } + case STONE_CAPSTONE: { *out_ptn = 'C'; out_ptn++; break; } + } + *out_ptn = 'a' + (in_location % board_size); out_ptn++; + *out_ptn = '1' + (in_location / board_size); out_ptn++; + *out_ptn = 0; +} + +// ------------------------------------------------------------------- +// Generate PTN for move + +void +generate_move(const uint8_t board_size, const uint8_t in_location, + const enum MOVE_DIRECTION in_direction, + const uint8_t in_steps, const uint8_t in_drops[5], + char out_ptn[10]) { + uint8_t total = 0; + for (uint8_t k = 0; k<in_steps; k++) total+=in_drops[k]; + if (total > 1) { + *out_ptn = '0' + total; out_ptn++; + } + + *out_ptn = 'a' + (in_location % board_size); out_ptn++; + *out_ptn = '1' + (in_location / board_size); out_ptn++; + + switch (in_direction) { + case M_UP: { *out_ptn = '+'; break; } + case M_DOWN: { *out_ptn = '-'; break; } + case M_LEFT: { *out_ptn = '<'; break; } + case M_RIGHT: { *out_ptn = '>'; break; } + }; out_ptn++; + + + for (uint8_t k = 0; (total > 1) && (k < in_steps); k++) { + *out_ptn = '0' + in_drops[k]; out_ptn++; + } + + *out_ptn = 0; +} + +// ------------------------------------------------------------------- +// Driver + +static uint8_t +is_not_placement(char *ptn) { + if (ptn == 0) return 0; + for (;;ptn++) { + switch (*ptn) { + case '+': + case '-': + case '>': + case '<': return 1; + case 0: return 0; + } + } +} + enum E_RESULT do_ptn(char *ptn) { enum E_RESULT res; uint8_t location; - if (likely_move(ptn)) { + if (is_not_placement(ptn)) { uint8_t steps, drops[5]; enum MOVE_DIRECTION direction; res = parse_move(board_size, ptn, &location, |