git.cworth.org Git - loudgame/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         *error = "Invalid coordinates (not on board)";
 191         return FALSE;
 192     }
 193
 194
 195     if (board->cells[x1][y1] == LOA_CELL_EMPTY) {
 196         *error = "There is no piece there to move";
 197         return FALSE;
 198     }
 199
 200     if (board->cells[x1][y1] != board->player) {
 201         *error = "You cannot move your opponent's piece";
 202         return FALSE;
 203     }
 204
 205     if (board->cells[x2][y2] == board->cells[x1][y1]) {
 206         *error = "You cannot capture your own piece";
 207         return FALSE;
 208     }
 209
 210     dx = x2 - x1;
 211     dy = y2 - y1;
 212
 213     /* Here's the meat of Lines of Action legaility: Does the distance
 214      * moved exactly match the number of pieces (of either color) in
 215      * the row, column, or diagonal of the movement. */
 216     if (dx == 0) {
 217         /* Column */
 218         if (abs (dy) != board->col_pieces[x1]) {
 219             *error = "The move distance does not match the number of pieces in that column";
 220             return FALSE;
 221         }
 222     } else if (dy == 0) {
 223         /* Row */
 224         if (abs (dx) != board->row_pieces[y1]) {
 225             *error = "The move distance does not match the number of pieces in that row";
 226             return FALSE;
 227         }
 228     } else {
 229         if (abs (dx) != abs (dy)) {
 230             *error = "That move is not in a row, column, or diagonal";
 231             return FALSE;
 232         }
 233         /* Diagonal */
 234         if ((dx > 0) == (dy > 0)) {
 235             if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
 236                 *error = "The move distance does not match the number of pieces in that diagonal";
 237                 return FALSE;
 238             }
 239         } else {
 240             if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
 241                 *error = "The move distance does not match the number of pieces in that diagonal";
 242                 return FALSE;
 243             }
 244         }
 245     }
 246
 247     /* Finally, we have to ensure that no opponent pieces are being
 248      * jumped. */
 249     step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
 250     step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
 251     for (x = x1 + step_x, y = y1 + step_y;
 252          x != x2 || y != y2;
 253          x += step_x, y += step_y)
 254     {
 255         if (board->cells[x][y] != LOA_CELL_EMPTY &&
 256             board->cells[x][y] != board->cells[x1][y1])
 257         {
 258             *error = "You cannot jump an opponent's piece";
 259             return FALSE;
 260         }
 261     }
 262
 263     return TRUE;
 264 }
 265
 266 static void
 267 loa_board_next_player (loa_board_t *board)
 268 {
 269     if (board->player == LOA_PLAYER_BLACK)
 270         board->player = LOA_PLAYER_WHITE;
 271     else
 272         board->player = LOA_PLAYER_BLACK;
 273 }
 274
 275 /* XXX: Should check for a legal move for the current player and
 276  * return FALSE in that case, (that is, it should be illegal to pass
 277  * if there's a legal move available). */
 278 int
 279 loa_board_pass (loa_board_t *board)
 280 {
 281     loa_board_next_player (board);
 282
 283     return TRUE;
 284 }
 285
 286 int
 287 loa_board_move (loa_board_t *board,
 288                 int x1, int y1,
 289                 int x2, int y2,
 290                 char **error)
 291 {
 292     loa_cell_t cell;
 293
 294     if (! loa_board_move_legal (board, x1, y1, x2, y2, error))
 295         return FALSE;
 296
 297     cell = loa_board_remove_piece (board, x1, y1);
 298     loa_board_remove_piece (board, x2, y2);
 299     loa_board_add_piece (board, x2, y2, cell);
 300
 301     loa_board_next_player (board);
 302
 303     return TRUE;
 304 }
 305
 306 /* A few different ideas for displaying boards:
 307  *
 308  * 8│ │●│●│●│●│●│●│ |       8| |*|*|*|*|*|*| |
 309  * 7│○│ │ │ │ │ │ │○|       7|o| | | | | | |o|
 310  * 6│○│ │ │ │ │ │ │○|       6|o| | | | | | |o|
 311  * 5│○│ │ │ │ │ │ │○|       5|o| | | | | | |o|
 312  * 4│○│ │ │ │ │ │ │○|       4|o| | | | | | |o|
 313  * 3│○│ │ │ │ │ │ │○|       3|o| | | | | | |o|
 314  * 2│○│ │ │ │ │ │ │○|       2|o| | | | | | |o|
 315  * 1│ │●│●│●│●│●│●│ |       1| |*|*|*|*|*|*| |
 316  *   A B C D E F G H      A B C D E F G H
 317  *
 318  *  ┌───┬───┬───┬───┬───┬───┬───┬───┐   -------------------------------
 319  * 8│   │ ● │ ● │ ● │ ● │ ● │ ● │   │     8|   | * | * | * | * | * | * |   |
 320  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 321  * 7│ ○ │   │   │   │   │   │   │ ○ │     7| o |   |   |   |   |   |   | o |
 322  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 323  * 6│ ○ │   │   │   │   │   │   │ ○ │     6| o |   |   |   |   |   |   | o |
 324  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 325  * 5│ ○ │   │   │   │   │   │   │ ○ │     5| o |   |   |   |   |   |   | o |
 326  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 327  * 4│ ○ │   │   │   │   │   │   │ ○ │     4| o |   |   |   |   |   |   | o |
 328  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 329  * 3│ ○ │   │   │   │   │   │   │ ○ │     3| o |   |   |   |   |   |   | o |
 330  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 331  * 2│ ○ │   │   │   │   │   │   │ ○ │     2| o |   |   |   |   |   |   | o |
 332  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 333  * 1│   │ ● │ ● │ ● │ ● │ ● │ ● │   │     1|   | * | * | * | * | * | * |   |
 334  *  └───┴───┴───┴───┴───┴───┴───┴───┘   -------------------------------
 335  *    A   B   C   D   E   F   G   H        A   B   C   D   E   F   G   H
 336  */
 337 char *
 338 loa_board_to_string (loa_board_t *board)
 339 {
 340     int x, y;
 341     /* In order of BLACK, WHITE, EMPTY */
 342     const char* cell_strings[] = {"●","○"," "};
 343     const char   board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
 344     const char     row_header[] = "│ ";
 345     const char cell_separator[] =    " │ ";
 346     const char     row_footer[] =                                " │";
 347     const char  row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
 348     const char   board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
 349     char *board_string = g_strdup ("");
 350
 351 #define APPEND(str) do {                                        \
 352     char *_new = g_strconcat (board_string, (str), NULL);       \
 353     free (board_string);                                        \
 354     board_string = _new;                                        \
 355 } while (0)
 356
 357 #define APPENDF(format, ...) do {                               \
 358     char *str = g_strdup_printf (format, ## __VA_ARGS__);       \
 359     APPEND (str);                                               \
 360     free (str);                                                 \
 361 } while (0)
 362
 363     APPENDF (" %s\n", board_header);
 364     for (y = 0; y < LOA_BOARD_SIZE; y++) {
 365         APPENDF ("%d%s", LOA_BOARD_SIZE - y, row_header);
 366         for (x = 0; x < LOA_BOARD_SIZE; x++) {
 367             APPENDF ("%s", cell_strings[board->cells[x][y]]);
 368             if (x != LOA_BOARD_SIZE - 1)
 369                 APPENDF ("%s", cell_separator);
 370         }
 371         APPENDF ("%s\n", row_footer);
 372         if (y != LOA_BOARD_SIZE -1)
 373             APPENDF (" %s\n", row_separator);
 374     }
 375     APPENDF (" %s\n", board_footer);
 376
 377     APPENDF ("   ");
 378     for (x = 0; x < LOA_BOARD_SIZE; x++) {
 379         APPENDF ("%c", 'A' + x);
 380         if (x != LOA_BOARD_SIZE - 1)
 381             APPENDF ("   ");
 382     }
 383     APPENDF ("\n");
 384
 385     return board_string;
 386 }