X-Git-Url: https://git.cworth.org/git?p=loudgame;a=blobdiff_plain;f=loa-board.c;fp=loa-board.c;h=5eb9cc5ab4984b87a8b050e06a8b20c2ada3b0c3;hp=0000000000000000000000000000000000000000;hb=53f4e9ba973bb1f15f41ba8fdd46ce592eafd9a2;hpb=39b7f117f31404e4cc936b28b6a7d0fc2cc0141e

diff --git a/loa-board.c b/loa-board.c
new file mode 100644
index 0000000..5eb9cc5
--- /dev/null
+++ b/loa-board.c
@@ -0,0 +1,386 @@
+/*
+ * 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 <cworth@cworth.org>
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include <glib.h>
+
+#include "loa-board.h"
+
+/* 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 + LOA_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 void
+loa_board_add_piece (loa_board_t *board, int x, int y, loa_cell_t cell)
+{
+    assert (cell == LOA_CELL_BLACK || cell == LOA_CELL_WHITE);
+    assert (board->cells[x][y] == LOA_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 loa_cell_t
+loa_board_remove_piece (loa_board_t *board, int x, int y)
+{
+    loa_cell_t cell;
+
+    cell = board->cells[x][y];
+
+    if (cell == LOA_CELL_EMPTY)
+	return LOA_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] = LOA_CELL_EMPTY;
+
+    return cell;
+}
+
+void
+loa_board_init (loa_board_t *board)
+{
+    int i, x, y;
+
+    for (x = 0; x < LOA_BOARD_SIZE; x++)
+	for (y = 0; y < LOA_BOARD_SIZE; y++)
+	    board->cells[x][y] = LOA_CELL_EMPTY;
+
+    board->num_pieces[LOA_CELL_BLACK] = 0;
+    board->num_pieces[LOA_CELL_WHITE] = 0;
+
+    for (i = 0; i < LOA_BOARD_SIZE; i++) {
+	board->row_pieces[i] = 0;
+	board->col_pieces[i] = 0;
+    }
+
+    for (i = 0; i < LOA_DIAG_ARRAY_SIZE; i++) {
+	board->diag_grave_pieces[i] = 0;
+	board->diag_acute_pieces[i] = 0;
+    }
+
+    for (i = 1; i < LOA_BOARD_SIZE - 1; i++) {
+	loa_board_add_piece (board, i, 0, LOA_CELL_BLACK);
+	loa_board_add_piece (board, i, LOA_BOARD_SIZE - 1, LOA_CELL_BLACK);
+	loa_board_add_piece (board, 0, i, LOA_CELL_WHITE);
+	loa_board_add_piece (board, LOA_BOARD_SIZE - 1, i, LOA_CELL_WHITE);
+    }
+
+    board->player = LOA_PLAYER_BLACK;
+}
+
+static int
+loa_board_group_size_recursive (loa_board_t *board, int x, int y,
+				loa_cell_t cell,
+				uint64_t *visited)
+{
+    uint64_t bit;
+
+    if (x < 0 || y < 0)
+	return 0;
+
+    if (x >= LOA_BOARD_SIZE || y >= LOA_BOARD_SIZE)
+	return 0;
+
+    bit = 1ll << (x * LOA_BOARD_SIZE + y);
+    if (*visited & bit)
+	return 0;
+
+    *visited |= bit;
+
+    if (board->cells[x][y] != cell)
+	return 0;
+
+    return 1 +
+	loa_board_group_size_recursive (board, x-1, y-1, cell, visited) +
+	loa_board_group_size_recursive (board, x-1, y  , cell, visited) +
+	loa_board_group_size_recursive (board, x-1, y+1, cell, visited) +
+	loa_board_group_size_recursive (board, x  , y-1, cell, visited) +
+	loa_board_group_size_recursive (board, x  , y  , cell, visited) +
+	loa_board_group_size_recursive (board, x  , y+1, cell, visited) +
+	loa_board_group_size_recursive (board, x+1, y-1, cell, visited) +
+	loa_board_group_size_recursive (board, x+1, y  , cell, visited) +
+	loa_board_group_size_recursive (board, x+1, y+1, cell, visited);
+}
+
+static int
+loa_board_group_size (loa_board_t *board, int x, int y)
+{
+    uint64_t visited = 0ll;
+    loa_cell_t cell = board->cells[x][y];
+
+    return loa_board_group_size_recursive (board, x, y, cell, &visited);
+}
+
+int
+loa_board_is_won (loa_board_t *board, int x, int y)
+{
+    loa_cell_t cell = board->cells[x][y];
+
+    if (cell == LOA_CELL_EMPTY)
+	return 0;
+
+    if (loa_board_group_size (board, x, y) == board->num_pieces[cell])
+	return 1;
+
+    return 0;
+}
+
+static loa_bool_t
+loa_board_move_legal (loa_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 (x1 < 0 || y1 < 0 || x1 >= LOA_BOARD_SIZE || y1 >= LOA_BOARD_SIZE) {
+	*error = "Invalid coordinates (not on board)";
+	return FALSE;
+    }
+
+
+    if (board->cells[x1][y1] == LOA_CELL_EMPTY) {
+	*error = "There is no piece there to move";
+	return FALSE;
+    }
+
+    if (board->cells[x1][y1] != board->player) {
+	*error = "You cannot move your opponent's piece";
+	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] != LOA_CELL_EMPTY &&
+	    board->cells[x][y] != board->cells[x1][y1])
+	{
+	    *error = "You cannot jump an opponent's piece";
+	    return FALSE;
+	}
+    }
+
+    return TRUE;
+}
+
+static void
+loa_board_next_player (loa_board_t *board)
+{
+    if (board->player == LOA_PLAYER_BLACK)
+	board->player = LOA_PLAYER_WHITE;
+    else
+	board->player = LOA_PLAYER_BLACK;
+}
+
+/* XXX: Should check for a legal move for the current player and
+ * return FALSE in that case, (that is, it should be illegal to pass
+ * if there's a legal move available). */
+int
+loa_board_pass (loa_board_t *board)
+{
+    loa_board_next_player (board);
+
+    return TRUE;
+}
+
+int
+loa_board_move (loa_board_t *board,
+		int x1, int y1,
+		int x2, int y2,
+		char **error)
+{
+    loa_cell_t cell;
+
+    if (! loa_board_move_legal (board, x1, y1, x2, y2, error))
+	return FALSE;
+
+    cell = loa_board_remove_piece (board, x1, y1);
+    loa_board_remove_piece (board, x2, y2);
+    loa_board_add_piece (board, x2, y2, cell);
+
+    loa_board_next_player (board);
+
+    return TRUE;
+}
+
+/* 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
+ */
+char *
+loa_board_to_string (loa_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 < LOA_BOARD_SIZE; y++) {
+	APPENDF ("%d%s", LOA_BOARD_SIZE - y, row_header);
+	for (x = 0; x < LOA_BOARD_SIZE; x++) {
+	    APPENDF ("%s", cell_strings[board->cells[x][y]]);
+	    if (x != LOA_BOARD_SIZE - 1)
+		APPENDF ("%s", cell_separator);
+	}
+	APPENDF ("%s\n", row_footer);
+	if (y != LOA_BOARD_SIZE -1)
+	    APPENDF (" %s\n", row_separator);
+    }
+    APPENDF (" %s\n", board_footer);
+
+    APPENDF ("   ");
+    for (x = 0; x < LOA_BOARD_SIZE; x++) {
+	APPENDF ("%c", 'A' + x);
+	if (x != LOA_BOARD_SIZE - 1)
+	    APPENDF ("   ");
+    }
+    APPENDF ("\n");
+
+    return board_string;
+}