From 7e33d9d0482f397390bea2f2ce17562ac2bb736d Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Tue, 19 Feb 2008 11:26:23 -0800 Subject: [PATCH] Add initial lg-loa program (Lines of Action) --- .gitignore | 1 + Makefile | 2 +- lg-loa.c | 647 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 649 insertions(+), 1 deletion(-) create mode 100644 lg-loa.c diff --git a/.gitignore b/.gitignore index 17ea798..c4cc277 100644 --- a/.gitignore +++ b/.gitignore @@ -1,6 +1,7 @@ *~ *.o lg-echo +lg-loa lg-set lg-test Makefile.dep diff --git a/Makefile b/Makefile index d74c04b..14f17ef 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,4 @@ -ALL=lg-echo lg-test lg-set +ALL=lg-echo lg-test lg-set lg-loa MYCFLAGS=-Wall `pkg-config --cflags loudmouth-1.0` MYLDFLAGS=`pkg-config --libs loudmouth-1.0` diff --git a/lg-loa.c b/lg-loa.c new file mode 100644 index 0000000..61e6351 --- /dev/null +++ b/lg-loa.c @@ -0,0 +1,647 @@ +/* + * Copyright (C) 2008 Carl Worth + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see http://www.gnu.org/licenses/ . + * + * Author: Carl Worth + */ + +#include "loudgame.h" + +#include +#include +#include + +#include +#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; + +typedef struct _loa_game { + loudgame_t lg; + board_t board; + player_t current; +} 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; +} + +static loa_bool_t +loa_game_move (loa_game_t *game, const char * peer, + int x1, int y1, int x2, int y2) +{ + 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)."); + 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; +} + +static void +loa_game_handle_show (loa_game_t *game, + const char *peer) +{ + LmMessage *reply; + LmMessageNode *html, *body, *span; + gboolean result; + GError *error = NULL; + char *board_string; + char *line, *newline; + + reply = lm_message_new (peer, LM_MESSAGE_TYPE_MESSAGE); + html = lm_message_node_add_child (reply->node, "html", ""); + lm_message_node_set_attribute (html, + "xmlns", + "http://jabber.org/protocol/xhtml-im"); + body = lm_message_node_add_child (html, "body", ""); + lm_message_node_set_attribute (body, + "xmlns", + "http://www.w3.org/1999/xhtml"); + + if (game->current == 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); + + line = board_string; + while (1) { + newline = strchr (line, '\n'); + if (newline) + *newline = '\0'; + lm_message_node_add_child (body, "br", ""); + span = lm_message_node_add_child (body, "span", line); + lm_message_node_set_attribute (span, "style", + "font-family: Monospace;"); + if (! newline) + break; + line = newline + 1; + } + + free (board_string); + + result = lm_connection_send (game->lg.connection, reply, &error); + lm_message_unref (reply); + + if (! result) { + g_error ("lm_connection_send failed: %s\n", + error->message); + loudgame_quit (&game->lg, 1); + } +} + +static void +loa_game_handle_move (loa_game_t *game, + const char *peer, + const char *move) +{ + char xc1, xc2; + int x1, y1, x2, y2; + int matched; + + matched = sscanf (move, " %c %d %c %d ", &xc1, &y1, &xc2, &y2); + if (matched != 4) { + loudgame_sendf (&game->lg, peer, + "Error: The 'move' command requires a move of the form 'b1d3'"); + 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)) + return; + + loudgame_broadcastf (&game->lg, "%c%d%c%d", + 'a' + x1, BOARD_SIZE - y1, + 'a' + x2, BOARD_SIZE - y2); + + if (board_is_won (&game->board, x2, y2)) + loudgame_broadcastf (&game->lg, "%s wins", peer); +} + +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); +} + +static void +loa_game_handle_help (loa_game_t *game, const char *peer) +{ + loudgame_sendf (&game->lg, peer, + "I'm a bot that allows you to play the game Lines of Action.\n" + "Here are some commands I understand:\n" + "\tshow \t\tShow the current board\n" + "\tmove aNbN\tMove a piece, (eg. 'move b1d3')\n" + "\tpass \t\tSkip a turn (only legal if no moves are possible)\n" + "\tnew \t\tBegin a new game\n" + "\thelp \t\tThis help message\n" + "\trules \t\tA description of the Lines of Action rules\n" + "\n" + "Lines of Action was invented by Claude Soucie and first made popular\n" + "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n" + "\n" + "If you are new to Lines of Action, type 'rules' now to learn the rules.\n"); +} + +static void +loa_game_handle_rules (loa_game_t *game, const char *peer) +{ + loudgame_sendf (&game->lg, peer, + "Lines of Action can be played with a standard (English) checkers set,\n" + "that is an 8x8 board and 12 markers each of contrasting colors ('black' and\n" + "'white'). The initial placement has 6 each of the black pieces on the top\n" + "and bottom rows, and 6 each of the white pieces on the left and right columns\n" + "leaving the four corner spaces empty. Play begins with the black player and\n" + "then alternates.\n" + "\n" + "On each move a piece is moved in a straight line in any of eight directions,\n" + "(similar to a queen's move in chess), but must be moved exactly the same\n" + "number of spaces as there are pieces (of either color) in the row, column,\n" + "or diagonal of the move. A piece may jump over pieces of its own color, but\n" + "may not jump a piece of the opposite color. The final square of the move can\n" + "be either empty or can contain a piece of the opposing color, in which case\n" + "that piece is removed from the game.\n" + "\n" + "If a player has no possible move, then that player must pass, (but if the\n" + "player has a possible move, then the player cannot pass).\n" + "\n" + "The goal of the game is to connect all of your remaining pieces into\n" + "a single, connected group. Pieces that are diagonally adjacent are\n" + "considered connected.\n" + "\n" + "If a move simultaneously creates a winning condition for both players, this\n" + "is considered a win for the player making the move.\n" + "\n" + "Notes on this implementation:\n" + "\n" + "This implementation enforces the move rules described above, but will\n" + "allow any person to make moves, (that is, you can control both\n" + "colors). Think of it as being somewhat like a physical board where\n" + "any person could move the pieces at any time, but generally two people\n" + "will take turns and others will politely watch.\n" + "\n" + "Also, the game won't currently show you the board again after a\n" + "player makes a move, so you'll need to keep typing 'show' to see\n" + "updates. Yes, this is a bug, and yes it will be fixed soon.\n" + "\n" + "Lines of Action was invented by Claude Soucie and first made popular\n" + "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n"); +} + +static void +loa_game_handle_new (loa_game_t *game, const char *peer) +{ + loudgame_broadcastf (&game->lg, "%s has started a new game", peer); + loa_game_new_game (game); +} + +static void +loa_game_handle_message (loudgame_t *lg, + const char *peer, + const char *message) +{ + loa_game_t *game = (loa_game_t *) lg; + + if (strcmp (message, "show") == 0) + loa_game_handle_show (game, peer); + else if (strncmp (message, "move", 4) == 0) + loa_game_handle_move (game, peer, message + 4); + else if (strcmp (message, "pass") == 0) + loa_game_handle_pass (game, peer); + else if (strcmp (message, "new") == 0) + loa_game_handle_new (game, peer); + else if (strcmp (message, "help") == 0) + loa_game_handle_help (game, peer); + else if (strcmp (message, "rules") == 0) + loa_game_handle_rules (game, peer); + else + loudgame_sendf (lg, peer, "Unknown command: '%s'. Use 'help' to get a list of valid commands.", message); +} + +static int +loa_game_init (loa_game_t *game, int argc, char *argv[]) +{ + int err; + + err = loudgame_init (&game->lg, argc, argv); + if (err) + return err; + + loa_game_new_game (game); + + return 0; +} + +int +main (int argc, char **argv) +{ + loa_game_t game; + int err; + + err = loa_game_init (&game, argc, argv); + if (err) + return err; + + game.lg.handle_message = loa_game_handle_message; + + err = loudgame_run (&game.lg); + if (err) + return err; + + return 0; +} -- 2.43.0