From f706a6a0546400cb6a1925f25dc010ffce2afd49 Mon Sep 17 00:00:00 2001 From: tslil Date: Sun, 27 Dec 2020 23:21:44 -0500 Subject: Changed representation, implemented most basic things for tak.h --- include/tak.c | 307 ++++++++++++++++++++++++++++++++++++++++++++++++++-------- include/tak.h | 66 +++++-------- 2 files changed, 290 insertions(+), 83 deletions(-) (limited to 'include') 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) -// 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 #include -/* 16 bits arranged as follows: +static uint8_t board_size = 5; - MSB : capstone or standing stone - 14-11: number of stones in the cell, 0x0-0xA valid, 0xF means empty - 0-10 : stack, LSB is top +typedef uint16_t colour_stack_t; +typedef uint8_t data_t; -*/ -typedef uint16_t cell_t; +enum COLOUR { C_WHITE, C_BLACK }; +enum STONE_VARIANT { STONE_FLAT, STONE_STANDING, STONE_CAPSTONE }; +enum MOVE_DIRECTION { M_UP, M_DOWN, M_LEFT, M_RIGHT }; +enum ACTION_RESULT { A_OK, A_ILLEGAL, A_OVERFLOW }; +enum WIN_RESULT { W_NONE, W_ROAD_WHITE, W_ROAD_BLACK, W_FLAT_WHITE, W_FLAT_BLACK }; -#define CELL_EMPTY_VALUE 0b0111100000000000 -#define CELL_MASK_CAPSTAND 0b1000000000000000 -#define CELL_MASK_COUNT CELL_EMPTY_VALUE -#define CELL_MASK_STACK 0b0000011111111111 -#define CELL_MASK_NOTSTACK 0b1111100000000000 +static colour_stack_t *colours = 0; +static data_t *celldat = 0; +static uint8_t white_flats, black_flats, white_caps, black_caps, turn; -#define CELL_COUNT_MAX 0b0101000000000000 -#define CELL_COUNT_INC 0b0000100000000000 -#define CELL_COUNT_SHIFT 11 +uint8_t init_game(void); +void reset_game(void); +void free_game(void); -#define CELL_IS_EMPTY(x) ((x) == CELL_EMPTY_VALUE) -#define CELL_IS_CAPSTAND(x) ((x) & CELL_MASK_CAPSTAND) -#define CELL_TOP_IS_BLACK(x) ((x) & 1) -#define CELL_TOP_IS_WHITE(x) (~(CELL_TOP_IS_BLACK(x))) +enum ACTION_RESULT +try_place(const int8_t location, const enum COLOUR colour, + const enum STONE_VARIANT stone); -#define CELL_SET_TOP_BLACK(x) ((x) |= 0x0001) -#define CELL_SET_TOP_WHITE(x) ((x) &= 0xFFFE) -#define CELL_SET_CAPSTAND(x) ((x) |= CELL_MASK_CAPSTAND) +enum ACTION_RESULT +try_move(const int8_t location, const enum MOVE_DIRECTION direction, + const uint8_t steps, const uint8_t * const drops); -#define CELL_GET_COUNT(x) ((uint8_t)(((x) & CELL_MASK_COUNT) >> CELL_COUNT_SHIFT)) -#define CELL_GET_STACK(x) ((x) & CELL_MASK_STACK) -#define CELL_GET_NOTSTACK(x) ((x) & CELL_MASK_NOTSTACK) - -enum ACTION_RESULT { A_OK, A_ILLEGAL, A_OVERFLOW }; - -typedef cell_t* board_t; -typedef uint64_t bit_board_t; // 8x8 board is exactly 8 bytes :) - -#define BITBOARD_SET(bb,location) ((bb) |= 1ULL << (location)) -#define BITBOARD_RST(bb,location) ((bb) &= ~(1ULL << (location))) - -enum STONE_VARIANT { STONE_FLAT, STONE_STANDING, STONE_CAPSTONE }; -#define STONE_IS_CAPSTAND(s) ((s == STONE_CAPSTONE) || (s == STONE_STANDING)) - -// Taking actions -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); - -// enum ACTION_RESULT move_stack(board_t *board, bit_board *capstand, uint8_t source, uint); - -// Querying things +enum WIN_RESULT +check_win(const enum COLOUR colour); -- cgit v1.3.1