From fd22e4cf3198c1e63cf26dd5fdce588a1e969ac1 Mon Sep 17 00:00:00 2001 From: tslil Date: Mon, 28 Dec 2020 20:56:46 -0500 Subject: Started on PTN stuff --- include/enums.h | 5 + include/ptn.c | 86 +++++++++++++++++ include/ptn.h | 13 +++ include/state.c | 274 +++++++++++++++++++++++++++++++++++++++++++++++++++++ include/state.h | 24 +++++ include/tak.c | 288 -------------------------------------------------------- include/tak.h | 32 ------- 7 files changed, 402 insertions(+), 320 deletions(-) create mode 100644 include/enums.h create mode 100644 include/ptn.c create mode 100644 include/ptn.h create mode 100644 include/state.c create mode 100644 include/state.h delete mode 100644 include/tak.c delete mode 100644 include/tak.h (limited to 'include') diff --git a/include/enums.h b/include/enums.h new file mode 100644 index 0000000..1df2a4b --- /dev/null +++ b/include/enums.h @@ -0,0 +1,5 @@ +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 }; diff --git a/include/ptn.c b/include/ptn.c new file mode 100644 index 0000000..58648b9 --- /dev/null +++ b/include/ptn.c @@ -0,0 +1,86 @@ +#include "ptn.h" + +#define ASSERT_NONEMPTY { if (ptn == 0 || *ptn == 0) return PTN_INVALID; } +#define ASSERT_MORE { if (*ptn == 0) return PTN_INVALID; } + +enum PTN_PARSE_RESULT +parse_place(const uint8_t board_size, char *ptn, + uint8_t *location, enum STONE_VARIANT *stone) { + + ASSERT_NONEMPTY; + + *stone = STONE_FLAT; + switch (*ptn) { + case 'C' : { ptn++; *stone = STONE_CAPSTONE; break; }; + case 'S' : { ptn++; *stone = STONE_STANDING; break; }; + case 'F' : { ptn++; break; }; + } + + ASSERT_MORE; + + if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; + *location = *ptn - 'a'; + + ptn++; ASSERT_MORE; + + if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; + *location += board_size * (*ptn - '1'); + + if (*(++ptn) > 0) return PTN_INVALID; + + return PTN_VALID; +} + +enum PTN_PARSE_RESULT +parse_move(const uint8_t board_size, char *ptn, + uint8_t *location, enum MOVE_DIRECTION *direction, + uint8_t *steps, uint8_t drops[5]) { + + ASSERT_NONEMPTY; + + uint8_t picked_up = 0; + + if ( (*ptn >= '1') && (*ptn <= '0' + board_size)) { + picked_up = *ptn - '0'; + ptn++; ASSERT_MORE; + } + + if ( (*ptn < 'a') || (*ptn > '`' + board_size) ) return PTN_INVALID; + *location = *ptn - 'a'; + + ptn++; ASSERT_MORE; + + if ( (*ptn < '1') || (*ptn > board_size + '0') ) return PTN_INVALID; + *location += board_size * (*ptn - '1'); + + ptn++; ASSERT_MORE; + + switch (*ptn) { + case '+': { *direction = M_UP; break; } + case '-': { *direction = M_DOWN; break; } + case '<': { *direction = M_LEFT; break; } + case '>': { *direction = M_RIGHT; break; } + default: return PTN_INVALID; + } + + ptn++; ASSERT_MORE; + + *steps = 0; + uint8_t total = 0; + while (*ptn) { + if ( (*ptn < '1') || (*ptn > '0' + board_size) ) { + return PTN_INVALID; + } + // TODO: Correct? + if ( (*steps >= board_size) && *ptn) return PTN_INVALID; + + drops[*steps] = *ptn - '0'; + total += drops[*steps]; + *steps += 1; + ptn++; + } + + if ( (picked_up > 0) && (total != picked_up) ) return PTN_INVALID; + + return PTN_VALID; +} diff --git a/include/ptn.h b/include/ptn.h new file mode 100644 index 0000000..715a7d0 --- /dev/null +++ b/include/ptn.h @@ -0,0 +1,13 @@ +#include +#include "enums.h" + +enum PTN_PARSE_RESULT { PTN_VALID, PTN_INVALID }; + +enum PTN_PARSE_RESULT +parse_place(const uint8_t board_size, char *ptn, + uint8_t *location, enum STONE_VARIANT *stone); + +enum PTN_PARSE_RESULT +parse_move(const uint8_t board_size, char *ptn, + uint8_t *location, enum MOVE_DIRECTION *direction, + uint8_t *steps, uint8_t drops[5]); diff --git a/include/state.c b/include/state.c new file mode 100644 index 0000000..1505881 --- /dev/null +++ b/include/state.c @@ -0,0 +1,274 @@ +#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_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 +#include "enums.h" + +static uint8_t board_size = 5; + +typedef uint16_t colour_stack_t; +typedef uint8_t data_t; + +static colour_stack_t colours[36]; +static data_t celldat[36]; +static uint8_t white_flats, black_flats, white_caps, black_caps, turn; + +void reset_game(void); + +enum ACTION_RESULT +try_place(const int8_t location, const enum COLOUR colour, + const enum STONE_VARIANT stone); + +enum ACTION_RESULT +try_move(const int8_t location, const enum MOVE_DIRECTION direction, + const uint8_t steps, const uint8_t drops[5]); + +enum WIN_RESULT +check_win(const enum COLOUR colour); diff --git a/include/tak.c b/include/tak.c deleted file mode 100644 index d772b5d..0000000 --- a/include/tak.c +++ /dev/null @@ -1,288 +0,0 @@ -#include "tak.h" - -// ------------------------------------------------------------------- -// Helpers - -#define NUM_SHIFT 4 -#define NUM_INC (0x1<> NUM_SHIFT) - -#define THE_COORDS(x,y) ((x)+(y)*board_size) - -// ------------------------------------------------------------------- -// Game management - -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; - - reset_game(); - return 0; -} - -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; - - turn = 0; - - for (uint8_t k = 0; k < board_size * board_size; k++ ) { - celldat[k] = 0; - } -} - -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 (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 - -static uint8_t board_size = 5; - -typedef uint16_t colour_stack_t; -typedef uint8_t data_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 }; - -static colour_stack_t *colours = 0; -static data_t *celldat = 0; -static uint8_t white_flats, black_flats, white_caps, black_caps, turn; - -uint8_t init_game(void); -void reset_game(void); -void free_game(void); - -enum ACTION_RESULT -try_place(const int8_t location, const enum COLOUR colour, - const enum STONE_VARIANT stone); - -enum ACTION_RESULT -try_move(const int8_t location, const enum MOVE_DIRECTION direction, - const uint8_t steps, const uint8_t * const drops); - -enum WIN_RESULT -check_win(const enum COLOUR colour); -- cgit v1.2.3