X-Git-Url: https://git.cworth.org/git?p=loudgame;a=blobdiff_plain;f=lg-loa.c;h=5a4d819de4543cfd24037aa648f8cda96b30e6e2;hp=f6a8f4c182e10811b093ed1bf5651fe09779463f;hb=HEAD;hpb=76ee71f47307291d8d2457204fc7c44b93729bb9 diff --git a/lg-loa.c b/lg-loa.c index f6a8f4c..5a4d819 100644 --- a/lg-loa.c +++ b/lg-loa.c @@ -27,401 +27,30 @@ #include #include -typedef int loa_bool_t; - -#ifndef FALSE -#define FALSE 0 -#endif -#ifndef TRUE -#define TRUE 1 -#endif - -typedef enum { - PLAYER_BLACK, - PLAYER_WHITE -} player_t; - -typedef enum { - CELL_BLACK = PLAYER_BLACK, - CELL_WHITE = PLAYER_WHITE, - CELL_EMPTY -} cell_t; - -/* The implementation of board_group_size depends on the square of - * BOARD_SIZE being less than or equal to 64. */ -#define BOARD_SIZE 8 -#define DIAG_ARRAY_SIZE (2 * BOARD_SIZE - 1) - -typedef struct { - cell_t cells[BOARD_SIZE][BOARD_SIZE]; - - /* Number of black and white pieces */ - int num_pieces[2]; - - /* Number of pieces (of either color) in each row, column, and - * diagonal. */ - int row_pieces[BOARD_SIZE]; - int col_pieces[BOARD_SIZE]; - int diag_grave_pieces[DIAG_ARRAY_SIZE]; - int diag_acute_pieces[DIAG_ARRAY_SIZE]; -} board_t; +#include "loa-board.h" typedef struct _loa_game { loudgame_t lg; - board_t board; - player_t current; + loa_board_t board; } loa_game_t; -static int -board_group_size_recursive (board_t *board, int x, int y, - cell_t cell, - uint64_t *visited) -{ - uint64_t bit; - - if (x < 0 || y < 0) - return 0; - - if (x >= BOARD_SIZE || y >= BOARD_SIZE) - return 0; - - bit = 1ll << (x * BOARD_SIZE + y); - if (*visited & bit) - return 0; - - *visited |= bit; - - if (board->cells[x][y] != cell) - return 0; - - return 1 + - board_group_size_recursive (board, x-1, y-1, cell, visited) + - board_group_size_recursive (board, x-1, y , cell, visited) + - board_group_size_recursive (board, x-1, y+1, cell, visited) + - board_group_size_recursive (board, x , y-1, cell, visited) + - board_group_size_recursive (board, x , y , cell, visited) + - board_group_size_recursive (board, x , y+1, cell, visited) + - board_group_size_recursive (board, x+1, y-1, cell, visited) + - board_group_size_recursive (board, x+1, y , cell, visited) + - board_group_size_recursive (board, x+1, y+1, cell, visited); -} - -static int -board_group_size (board_t *board, int x, int y) -{ - uint64_t visited = 0ll; - cell_t cell = board->cells[x][y]; - - return board_group_size_recursive (board, x, y, cell, &visited); -} - -static int -board_is_won (board_t *board, int x, int y) -{ - cell_t cell = board->cells[x][y]; - - if (cell == CELL_EMPTY) - return 0; - - if (board_group_size (board, x, y) == board->num_pieces[cell]) - return 1; - - return 0; -} - -/* Given an (x,y) position on the board, return the index of the array - * used to count pieces in diagonal rows running from upper-left to - * lower-right, (like a grave accent: à or like a backslash: \). - * - * This is the array to look into when a move occurs with dx and dy of - * the same sign. */ -static int -_grave_index (int x, int y) -{ - return x - y + BOARD_SIZE - 1; -} - -/* Given an (x,y) position on the board, return the index of the array - * used to count pieces in diagonal rows running from lower-left to - * upper-right, (like an acute accent: á or like a forward slash: /). - * - * This is the array to look into when a move occurs with dx and dy of - * opposite sign, (one positive, one negative). */ -static int -_acute_index (int x, int y) -{ - return x + y; -} - -static loa_bool_t -board_move_legal (board_t *board, int x1, int y1, int x2, int y2, char **error) -{ - int x, y; - int dx, dy; - int step_x, step_y; - - if (board->cells[x1][y1] == CELL_EMPTY) { - *error = "There is no piece there to move"; - return FALSE; - } - - if (board->cells[x2][y2] == board->cells[x1][y1]) { - *error = "You cannot capture your own piece"; - return FALSE; - } - - dx = x2 - x1; - dy = y2 - y1; - - /* Here's the meat of Lines of Action legaility: Does the distance - * moved exactly match the number of pieces (of either color) in - * the row, column, or diagonal of the movement. */ - if (dx == 0) { - /* Column */ - if (abs (dy) != board->col_pieces[x1]) { - *error = "The move distance does not match the number of pieces in that column"; - return FALSE; - } - } else if (dy == 0) { - /* Row */ - if (abs (dx) != board->row_pieces[y1]) { - *error = "The move distance does not match the number of pieces in that row"; - return FALSE; - } - } else { - if (abs (dx) != abs (dy)) { - *error = "That move is not in a row, column, or diagonal"; - return FALSE; - } - /* Diagonal */ - if ((dx > 0) == (dy > 0)) { - if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) { - *error = "The move distance does not match the number of pieces in that diagonal"; - return FALSE; - } - } else { - if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) { - *error = "The move distance does not match the number of pieces in that diagonal"; - return FALSE; - } - } - } - - /* Finally, we have to ensure that no opponent pieces are being - * jumped. */ - step_x = dx ? ((dx < 0) ? -1 : +1) : 0; - step_y = dy ? ((dy < 0) ? -1 : +1) : 0; - for (x = x1 + step_x, y = y1 + step_y; - x != x2 || y != y2; - x += step_x, y += step_y) - { - if (board->cells[x][y] != CELL_EMPTY && - board->cells[x][y] != board->cells[x1][y1]) - { - *error = "You cannot jump an opponent's piece"; - return FALSE; - } - } - - return TRUE; -} - -static void -board_add_piece (board_t *board, int x, int y, cell_t cell) -{ - assert (cell == CELL_BLACK || cell == CELL_WHITE); - assert (board->cells[x][y] == CELL_EMPTY); - - board->col_pieces[x]++; - board->row_pieces[y]++; - board->diag_grave_pieces[_grave_index (x, y)]++; - board->diag_acute_pieces[_acute_index (x, y)]++; - - board->num_pieces[cell]++; - - board->cells[x][y] = cell; -} - -static cell_t -board_remove_piece (board_t *board, int x, int y) -{ - cell_t cell; - - cell = board->cells[x][y]; - - if (cell == CELL_EMPTY) - return CELL_EMPTY; - - board->col_pieces[x]--; - board->row_pieces[y]--; - board->diag_grave_pieces[_grave_index (x, y)]--; - board->diag_acute_pieces[_acute_index (x, y)]--; - - board->num_pieces[cell]--; - - board->cells[x][y] = CELL_EMPTY; - - return cell; -} - -static void -board_init (board_t *board) -{ - int i, x, y; - - for (x = 0; x < BOARD_SIZE; x++) - for (y = 0; y < BOARD_SIZE; y++) - board->cells[x][y] = CELL_EMPTY; - - board->num_pieces[CELL_BLACK] = 0; - board->num_pieces[CELL_WHITE] = 0; - - for (i = 0; i < BOARD_SIZE; i++) { - board->row_pieces[i] = 0; - board->col_pieces[i] = 0; - } - - for (i = 0; i < DIAG_ARRAY_SIZE; i++) { - board->diag_grave_pieces[i] = 0; - board->diag_acute_pieces[i] = 0; - } - - for (i = 1; i < BOARD_SIZE - 1; i++) { - board_add_piece (board, i, 0, CELL_BLACK); - board_add_piece (board, i, BOARD_SIZE - 1, CELL_BLACK); - board_add_piece (board, 0, i, CELL_WHITE); - board_add_piece (board, BOARD_SIZE - 1, i, CELL_WHITE); - } -} - -/* A few different ideas for displaying boards: - * - * 8│ │●│●│●│●│●│●│ | 8| |*|*|*|*|*|*| | - * 7│○│ │ │ │ │ │ │○| 7|o| | | | | | |o| - * 6│○│ │ │ │ │ │ │○| 6|o| | | | | | |o| - * 5│○│ │ │ │ │ │ │○| 5|o| | | | | | |o| - * 4│○│ │ │ │ │ │ │○| 4|o| | | | | | |o| - * 3│○│ │ │ │ │ │ │○| 3|o| | | | | | |o| - * 2│○│ │ │ │ │ │ │○| 2|o| | | | | | |o| - * 1│ │●│●│●│●│●│●│ | 1| |*|*|*|*|*|*| | - * A B C D E F G H A B C D E F G H - * - * ┌───┬───┬───┬───┬───┬───┬───┬───┐ ------------------------------- - * 8│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 8| | * | * | * | * | * | * | | - * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---| - * 7│ ○ │ │ │ │ │ │ │ ○ │ 7| o | | | | | | | o | - * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---| - * 6│ ○ │ │ │ │ │ │ │ ○ │ 6| o | | | | | | | o | - * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---| - * 5│ ○ │ │ │ │ │ │ │ ○ │ 5| o | | | | | | | o | - * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---| - * 4│ ○ │ │ │ │ │ │ │ ○ │ 4| o | | | | | | | o | - * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---| - * 3│ ○ │ │ │ │ │ │ │ ○ │ 3| o | | | | | | | o | - * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---| - * 2│ ○ │ │ │ │ │ │ │ ○ │ 2| o | | | | | | | o | - * ├───┼───┼───┼───┼───┼───┼───┼───┤ |---+---+---+---+---+---+---+---| - * 1│ │ ● │ ● │ ● │ ● │ ● │ ● │ │ 1| | * | * | * | * | * | * | | - * └───┴───┴───┴───┴───┴───┴───┴───┘ ------------------------------- - * A B C D E F G H A B C D E F G H - */ -static char * -board_to_string (board_t *board) -{ - int x, y; - /* In order of BLACK, WHITE, EMPTY */ - const char* cell_strings[] = {"●","○"," "}; - const char board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐"; - const char row_header[] = "│ "; - const char cell_separator[] = " │ "; - const char row_footer[] = " │"; - const char row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤"; - const char board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘"; - char *board_string = g_strdup (""); - -#define APPEND(str) do { \ - char *_new = g_strconcat (board_string, (str), NULL); \ - free (board_string); \ - board_string = _new; \ -} while (0) - -#define APPENDF(format, ...) do { \ - char *str = g_strdup_printf (format, ## __VA_ARGS__); \ - APPEND (str); \ - free (str); \ -} while (0) - - APPENDF (" %s\n", board_header); - for (y = 0; y < BOARD_SIZE; y++) { - APPENDF ("%d%s", BOARD_SIZE - y, row_header); - for (x = 0; x < BOARD_SIZE; x++) { - APPENDF ("%s", cell_strings[board->cells[x][y]]); - if (x != BOARD_SIZE - 1) - APPENDF ("%s", cell_separator); - } - APPENDF ("%s\n", row_footer); - if (y != BOARD_SIZE -1) - APPENDF (" %s\n", row_separator); - } - APPENDF (" %s\n", board_footer); - - APPENDF (" "); - for (x = 0; x < BOARD_SIZE; x++) { - APPENDF ("%c", 'A' + x); - if (x != BOARD_SIZE - 1) - APPENDF (" "); - } - APPENDF ("\n"); - - return board_string; -} - static void loa_game_new_game (loa_game_t *game) { - board_init (&game->board); - game->current = PLAYER_BLACK; -} - -static void -loa_game_next_player (loa_game_t *game) -{ - if (game->current == PLAYER_BLACK) - game->current = PLAYER_WHITE; - else - game->current = PLAYER_BLACK; + loa_board_reset (&game->board); } static loa_bool_t -loa_game_move (loa_game_t *game, const char * peer, - int x1, int y1, int x2, int y2) +loa_game_move (loa_game_t *game, const char * peer, loa_move_t *move) { - board_t *board = &game->board; - cell_t cell; char *error; - if (x1 < 0 || y1 < 0 || x1 >= BOARD_SIZE || y1 >= BOARD_SIZE) { - loudgame_sendf (&game->lg, peer, "Invalid coordinates (not on board)."); + if (! loa_board_move (&game->board, move, &error)) { + loudgame_sendf (&game->lg, peer, "Illegal move: %s: %s", + loa_move_to_string (move), error); return FALSE; } - if (board->cells[x1][y1] != game->current) { - loudgame_sendf (&game->lg, peer, "Cell at (%d,%d) does not belong to current player.", - x1, y1); - return FALSE; - } - - if (! board_move_legal (&game->board, x1, y1, x2, y2, &error)) { - loudgame_sendf (&game->lg, peer, "Illegal move: %s."); - return FALSE; - } - - cell = board_remove_piece (board, x1, y1); - board_remove_piece (board, x2, y2); - board_add_piece (board, x2, y2, cell); - - loa_game_next_player (game); - return TRUE; } @@ -446,12 +75,12 @@ loa_game_handle_show (loa_game_t *game, "xmlns", "http://www.w3.org/1999/xhtml"); - if (game->current == PLAYER_BLACK) + if (game->board.player == LOA_PLAYER_BLACK) lm_message_node_add_child (body, "span", "Black to move:"); else lm_message_node_add_child (body, "span", "White to move:"); - board_string = board_to_string (&game->board); + board_string = loa_board_to_string (&game->board); line = board_string; while (1) { @@ -482,41 +111,46 @@ loa_game_handle_show (loa_game_t *game, static void loa_game_handle_move (loa_game_t *game, const char *peer, - const char *move) + const char *move_string) { - char xc1, xc2; - int x1, y1, x2, y2; - int matched; + loa_move_t move; - matched = sscanf (move, " %c %d %c %d ", &xc1, &y1, &xc2, &y2); - if (matched != 4) { + if (! loa_move_init_from_string (&move, move_string)) { loudgame_sendf (&game->lg, peer, - "Error: The 'move' command requires a move of the form 'b1d3'"); + "Error: The 'move' command requires a move of the form 'b1-d3'"); return; } - x1 = tolower (xc1) - 'a'; - x2 = tolower (xc2) - 'a'; - /* We use an upper-left origin internally. */ - y1 = BOARD_SIZE - y1; - y2 = BOARD_SIZE - y2; - if (! loa_game_move (game, peer, x1, y1, x2, y2)) + if (! loa_game_move (game, peer, &move)) return; - loudgame_broadcastf (&game->lg, "%c%d%c%d", - 'a' + x1, BOARD_SIZE - y1, - 'a' + x2, BOARD_SIZE - y2); + loudgame_broadcastf (&game->lg, "%s", loa_move_to_string (&move)); - if (board_is_won (&game->board, x2, y2)) + if (loa_board_is_won (&game->board, move.x2, move.y2)) loudgame_broadcastf (&game->lg, "%s wins", peer); } +static void +loa_game_handle_history (loa_game_t *game, + const char *peer) +{ + int i; + + for (i = 0; i < game->board.num_moves; i++) + loudgame_sendf (&game->lg, peer, "%s", + loa_move_to_string (&game->board.moves[i])); +} + static void loa_game_handle_pass (loa_game_t *game, const char *peer) { loudgame_broadcastf (&game->lg, "%s passes", peer); - loa_game_next_player (game); + if (loa_board_pass (&game->board)) + return; + + loudgame_sendf (&game->lg, peer, + "Error: You cannot pass since you have a legal move available"); } static void @@ -529,9 +163,10 @@ loa_game_handle_help (loa_game_t *game, const char *peer) "\n" "And some game-specific commands:\n" "\tshow \t\tShow the current board\n" - "\tmove aNbN\tMove a piece, (eg. 'move b1d3')\n" + "\tmove aNbN\tMove a piece, (eg. 'move b1-d3')\n" "\tpass \t\tSkip a turn (only legal if no moves are possible)\n" "\tnew \t\tBegin a new game\n" + "\thistory \t\tShow the move history of the game\n" "\thelp \t\tThis help message\n" "\trules \t\tA description of the Lines of Action rules\n" "\n" @@ -608,6 +243,8 @@ loa_game_handle_message (loudgame_t *lg, loa_game_handle_pass (game, peer); else if (strcmp (message, "new") == 0) loa_game_handle_new (game, peer); + else if (strcmp (message, "history") == 0) + loa_game_handle_history (game, peer); else if (strcmp (message, "help") == 0) loa_game_handle_help (game, peer); else if (strcmp (message, "rules") == 0) @@ -625,6 +262,8 @@ loa_game_init (loa_game_t *game, int argc, char *argv[]) if (err) return err; + loa_board_init (&game->board); + loa_game_new_game (game); return 0;