git.cworth.org Git - loa/blob - loa-board.c

   1 /*
   2  * Copyright (C) 2008 Carl Worth
   3  *
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 3 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program.  If not, see http://www.gnu.org/licenses/ .
  16  *
  17  * Author: Carl Worth <cworth@cworth.org>
  18  */
  19
  20 #include <stdint.h>
  21 #include <stdlib.h>
  22 #include <assert.h>
  23
  24 #include <glib.h>
  25
  26 #include "loa-board.h"
  27
  28 /* Given an (x,y) position on the board, return the index of the array
  29  * used to count pieces in diagonal rows running from upper-left to
  30  * lower-right, (like a grave accent: à or like a backslash: \).
  31  *
  32  * This is the array to look into when a move occurs with dx and dy of
  33  * the same sign. */
  34 static int
  35 _grave_index (int x, int y)
  36 {
  37     return x - y + LOA_BOARD_SIZE - 1;
  38 }
  39
  40 /* Given an (x,y) position on the board, return the index of the array
  41  * used to count pieces in diagonal rows running from lower-left to
  42  * upper-right, (like an acute accent: á or like a forward slash: /).
  43  *
  44  * This is the array to look into when a move occurs with dx and dy of
  45  * opposite sign, (one positive, one negative). */
  46 static int
  47 _acute_index (int x, int y)
  48 {
  49     return x + y;
  50 }
  51
  52 static void
  53 loa_board_add_piece (loa_board_t *board, int x, int y, loa_cell_t cell)
  54 {
  55     assert (cell == LOA_CELL_BLACK || cell == LOA_CELL_WHITE);
  56     assert (board->cells[x][y] == LOA_CELL_EMPTY);
  57
  58     board->col_pieces[x]++;
  59     board->row_pieces[y]++;
  60     board->diag_grave_pieces[_grave_index (x, y)]++;
  61     board->diag_acute_pieces[_acute_index (x, y)]++;
  62
  63     board->num_pieces[cell]++;
  64
  65     board->cells[x][y] = cell;
  66 }
  67
  68 static loa_cell_t
  69 loa_board_remove_piece (loa_board_t *board, int x, int y)
  70 {
  71     loa_cell_t cell;
  72
  73     cell = board->cells[x][y];
  74
  75     if (cell == LOA_CELL_EMPTY)
  76         return LOA_CELL_EMPTY;
  77
  78     board->col_pieces[x]--;
  79     board->row_pieces[y]--;
  80     board->diag_grave_pieces[_grave_index (x, y)]--;
  81     board->diag_acute_pieces[_acute_index (x, y)]--;
  82
  83     board->num_pieces[cell]--;
  84
  85     board->cells[x][y] = LOA_CELL_EMPTY;
  86
  87     return cell;
  88 }
  89
  90 void
  91 loa_board_init (loa_board_t *board)
  92 {
  93     int i, x, y;
  94
  95     for (x = 0; x < LOA_BOARD_SIZE; x++)
  96         for (y = 0; y < LOA_BOARD_SIZE; y++)
  97             board->cells[x][y] = LOA_CELL_EMPTY;
  98
  99     board->num_pieces[LOA_CELL_BLACK] = 0;
 100     board->num_pieces[LOA_CELL_WHITE] = 0;
 101
 102     for (i = 0; i < LOA_BOARD_SIZE; i++) {
 103         board->row_pieces[i] = 0;
 104         board->col_pieces[i] = 0;
 105     }
 106
 107     for (i = 0; i < LOA_DIAG_ARRAY_SIZE; i++) {
 108         board->diag_grave_pieces[i] = 0;
 109         board->diag_acute_pieces[i] = 0;
 110     }
 111
 112     for (i = 1; i < LOA_BOARD_SIZE - 1; i++) {
 113         loa_board_add_piece (board, i, 0, LOA_CELL_BLACK);
 114         loa_board_add_piece (board, i, LOA_BOARD_SIZE - 1, LOA_CELL_BLACK);
 115         loa_board_add_piece (board, 0, i, LOA_CELL_WHITE);
 116         loa_board_add_piece (board, LOA_BOARD_SIZE - 1, i, LOA_CELL_WHITE);
 117     }
 118
 119     board->player = LOA_PLAYER_BLACK;
 120 }
 121
 122 static int
 123 loa_board_group_size_recursive (loa_board_t *board, int x, int y,
 124                                 loa_cell_t cell,
 125                                 uint64_t *visited)
 126 {
 127     uint64_t bit;
 128
 129     if (x < 0 || y < 0)
 130         return 0;
 131
 132     if (x >= LOA_BOARD_SIZE || y >= LOA_BOARD_SIZE)
 133         return 0;
 134
 135     bit = 1ll << (x * LOA_BOARD_SIZE + y);
 136     if (*visited & bit)
 137         return 0;
 138
 139     *visited |= bit;
 140
 141     if (board->cells[x][y] != cell)
 142         return 0;
 143
 144     return 1 +
 145         loa_board_group_size_recursive (board, x-1, y-1, cell, visited) +
 146         loa_board_group_size_recursive (board, x-1, y  , cell, visited) +
 147         loa_board_group_size_recursive (board, x-1, y+1, cell, visited) +
 148         loa_board_group_size_recursive (board, x  , y-1, cell, visited) +
 149         loa_board_group_size_recursive (board, x  , y  , cell, visited) +
 150         loa_board_group_size_recursive (board, x  , y+1, cell, visited) +
 151         loa_board_group_size_recursive (board, x+1, y-1, cell, visited) +
 152         loa_board_group_size_recursive (board, x+1, y  , cell, visited) +
 153         loa_board_group_size_recursive (board, x+1, y+1, cell, visited);
 154 }
 155
 156 static int
 157 loa_board_group_size (loa_board_t *board, int x, int y)
 158 {
 159     uint64_t visited = 0ll;
 160     loa_cell_t cell = board->cells[x][y];
 161
 162     return loa_board_group_size_recursive (board, x, y, cell, &visited);
 163 }
 164
 165 int
 166 loa_board_is_won (loa_board_t *board, int x, int y)
 167 {
 168     loa_cell_t cell = board->cells[x][y];
 169
 170     if (cell == LOA_CELL_EMPTY)
 171         return 0;
 172
 173     if (loa_board_group_size (board, x, y) == board->num_pieces[cell])
 174         return 1;
 175
 176     return 0;
 177 }
 178
 179 static loa_bool_t
 180 loa_board_move_legal (loa_board_t *board,
 181                       int x1, int y1,
 182                       int x2, int y2,
 183                       char **error)
 184 {
 185     int x, y;
 186     int dx, dy;
 187     int step_x, step_y;
 188
 189     if (x1 < 0 || y1 < 0 || x1 >= LOA_BOARD_SIZE || y1 >= LOA_BOARD_SIZE ||
 190         x2 < 0 || y2 < 0 || x2 >= LOA_BOARD_SIZE || y2 >= LOA_BOARD_SIZE)
 191     {
 192         *error = "Invalid coordinates (not on board)";
 193         return FALSE;
 194     }
 195
 196
 197     if (board->cells[x1][y1] == LOA_CELL_EMPTY) {
 198         *error = "There is no piece there to move";
 199         return FALSE;
 200     }
 201
 202     if (board->cells[x1][y1] != board->player) {
 203         *error = "You cannot move your opponent's piece";
 204         return FALSE;
 205     }
 206
 207     if (board->cells[x2][y2] == board->cells[x1][y1]) {
 208         *error = "You cannot capture your own piece";
 209         return FALSE;
 210     }
 211
 212     dx = x2 - x1;
 213     dy = y2 - y1;
 214
 215     /* Here's the meat of Lines of Action legaility: Does the distance
 216      * moved exactly match the number of pieces (of either color) in
 217      * the row, column, or diagonal of the movement. */
 218     if (dx == 0) {
 219         /* Column */
 220         if (abs (dy) != board->col_pieces[x1]) {
 221             *error = "The move distance does not match the number of pieces in that column";
 222             return FALSE;
 223         }
 224     } else if (dy == 0) {
 225         /* Row */
 226         if (abs (dx) != board->row_pieces[y1]) {
 227             *error = "The move distance does not match the number of pieces in that row";
 228             return FALSE;
 229         }
 230     } else {
 231         if (abs (dx) != abs (dy)) {
 232             *error = "That move is not in a row, column, or diagonal";
 233             return FALSE;
 234         }
 235         /* Diagonal */
 236         if ((dx > 0) == (dy > 0)) {
 237             if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
 238                 *error = "The move distance does not match the number of pieces in that diagonal";
 239                 return FALSE;
 240             }
 241         } else {
 242             if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
 243                 *error = "The move distance does not match the number of pieces in that diagonal";
 244                 return FALSE;
 245             }
 246         }
 247     }
 248
 249     /* Finally, we have to ensure that no opponent pieces are being
 250      * jumped. */
 251     step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
 252     step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
 253     for (x = x1 + step_x, y = y1 + step_y;
 254          x != x2 || y != y2;
 255          x += step_x, y += step_y)
 256     {
 257         if (board->cells[x][y] != LOA_CELL_EMPTY &&
 258             board->cells[x][y] != board->cells[x1][y1])
 259         {
 260             *error = "You cannot jump an opponent's piece";
 261             return FALSE;
 262         }
 263     }
 264
 265     return TRUE;
 266 }
 267
 268 static void
 269 loa_board_next_player (loa_board_t *board)
 270 {
 271     if (board->player == LOA_PLAYER_BLACK)
 272         board->player = LOA_PLAYER_WHITE;
 273     else
 274         board->player = LOA_PLAYER_BLACK;
 275 }
 276
 277 /* XXX: Should check for a legal move for the current player and
 278  * return FALSE in that case, (that is, it should be illegal to pass
 279  * if there's a legal move available). */
 280 int
 281 loa_board_pass (loa_board_t *board)
 282 {
 283     loa_board_next_player (board);
 284
 285     return TRUE;
 286 }
 287
 288 int
 289 loa_board_move (loa_board_t *board,
 290                 int x1, int y1,
 291                 int x2, int y2,
 292                 char **error)
 293 {
 294     loa_cell_t cell;
 295
 296     if (! loa_board_move_legal (board, x1, y1, x2, y2, error))
 297         return FALSE;
 298
 299     cell = loa_board_remove_piece (board, x1, y1);
 300     loa_board_remove_piece (board, x2, y2);
 301     loa_board_add_piece (board, x2, y2, cell);
 302
 303     loa_board_next_player (board);
 304
 305     return TRUE;
 306 }
 307
 308 /* A few different ideas for displaying boards:
 309  *
 310  * 8│ │●│●│●│●│●│●│ |       8| |*|*|*|*|*|*| |
 311  * 7│○│ │ │ │ │ │ │○|       7|o| | | | | | |o|
 312  * 6│○│ │ │ │ │ │ │○|       6|o| | | | | | |o|
 313  * 5│○│ │ │ │ │ │ │○|       5|o| | | | | | |o|
 314  * 4│○│ │ │ │ │ │ │○|       4|o| | | | | | |o|
 315  * 3│○│ │ │ │ │ │ │○|       3|o| | | | | | |o|
 316  * 2│○│ │ │ │ │ │ │○|       2|o| | | | | | |o|
 317  * 1│ │●│●│●│●│●│●│ |       1| |*|*|*|*|*|*| |
 318  *   A B C D E F G H      A B C D E F G H
 319  *
 320  *  ┌───┬───┬───┬───┬───┬───┬───┬───┐   -------------------------------
 321  * 8│   │ ● │ ● │ ● │ ● │ ● │ ● │   │     8|   | * | * | * | * | * | * |   |
 322  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 323  * 7│ ○ │   │   │   │   │   │   │ ○ │     7| o |   |   |   |   |   |   | o |
 324  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 325  * 6│ ○ │   │   │   │   │   │   │ ○ │     6| o |   |   |   |   |   |   | o |
 326  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 327  * 5│ ○ │   │   │   │   │   │   │ ○ │     5| o |   |   |   |   |   |   | o |
 328  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 329  * 4│ ○ │   │   │   │   │   │   │ ○ │     4| o |   |   |   |   |   |   | o |
 330  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 331  * 3│ ○ │   │   │   │   │   │   │ ○ │     3| o |   |   |   |   |   |   | o |
 332  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 333  * 2│ ○ │   │   │   │   │   │   │ ○ │     2| o |   |   |   |   |   |   | o |
 334  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 335  * 1│   │ ● │ ● │ ● │ ● │ ● │ ● │   │     1|   | * | * | * | * | * | * |   |
 336  *  └───┴───┴───┴───┴───┴───┴───┴───┘   -------------------------------
 337  *    A   B   C   D   E   F   G   H        A   B   C   D   E   F   G   H
 338  */
 339 char *
 340 loa_board_to_string (loa_board_t *board)
 341 {
 342     int x, y;
 343     /* In order of BLACK, WHITE, EMPTY */
 344     const char* cell_strings[] = {"●","○"," "};
 345     const char   board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
 346     const char     row_header[] = "│ ";
 347     const char cell_separator[] =    " │ ";
 348     const char     row_footer[] =                                " │";
 349     const char  row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
 350     const char   board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
 351     char *board_string = g_strdup ("");
 352
 353 #define APPEND(str) do {                                        \
 354     char *_new = g_strconcat (board_string, (str), NULL);       \
 355     free (board_string);                                        \
 356     board_string = _new;                                        \
 357 } while (0)
 358
 359 #define APPENDF(format, ...) do {                               \
 360     char *str = g_strdup_printf (format, ## __VA_ARGS__);       \
 361     APPEND (str);                                               \
 362     free (str);                                                 \
 363 } while (0)
 364
 365     APPENDF (" %s\n", board_header);
 366     for (y = 0; y < LOA_BOARD_SIZE; y++) {
 367         APPENDF ("%d%s", LOA_BOARD_SIZE - y, row_header);
 368         for (x = 0; x < LOA_BOARD_SIZE; x++) {
 369             APPENDF ("%s", cell_strings[board->cells[x][y]]);
 370             if (x != LOA_BOARD_SIZE - 1)
 371                 APPENDF ("%s", cell_separator);
 372         }
 373         APPENDF ("%s\n", row_footer);
 374         if (y != LOA_BOARD_SIZE -1)
 375             APPENDF (" %s\n", row_separator);
 376     }
 377     APPENDF (" %s\n", board_footer);
 378
 379     APPENDF ("   ");
 380     for (x = 0; x < LOA_BOARD_SIZE; x++) {
 381         APPENDF ("%c", 'A' + x);
 382         if (x != LOA_BOARD_SIZE - 1)
 383             APPENDF ("   ");
 384     }
 385     APPENDF ("\n");
 386
 387     return board_string;
 388 }