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 <stdio.h>
  21 #include <stdint.h>
  22 #include <stdlib.h>
  23 #include <assert.h>
  24 #include <string.h>
  25 #include <ctype.h>
  26
  27 #include <glib.h>
  28
  29 #include "loa-board.h"
  30
  31 static loa_bool_t
  32 loa_move_is_valid (const loa_move_t *move)
  33 {
  34     return (move->x1 >= 0 && move->x1 < LOA_BOARD_SIZE &&
  35             move->y1 >= 0 && move->y1 < LOA_BOARD_SIZE &&
  36             move->x2 >= 0 && move->x2 < LOA_BOARD_SIZE &&
  37             move->y2 >= 0 && move->y2 < LOA_BOARD_SIZE);
  38 }
  39
  40 const char *
  41 loa_move_to_string (const loa_move_t *move)
  42 {
  43 #define LOA_MOVE_STRING_SIZE 6
  44     static char move_string[LOA_MOVE_STRING_SIZE];
  45
  46     if (! loa_move_is_valid (move)) {
  47         strcpy (move_string, "***");
  48         return move_string;
  49     }
  50
  51     snprintf (move_string, LOA_MOVE_STRING_SIZE,
  52               "%c%d%c%c%d",
  53               'a' + move->x1, LOA_BOARD_SIZE - move->y1,
  54               move->is_capture ? 'x' : '-',
  55               'a' + move->x2, LOA_BOARD_SIZE - move->y2);
  56
  57     return move_string;
  58 }
  59
  60 loa_bool_t
  61 loa_move_init_from_string (loa_move_t *move, const char *string)
  62 {
  63     char xc1, xc2, sep;
  64     int x1, y1, x2, y2;
  65     int matched;
  66
  67     /* Avoid returning uninitialized data on error. */
  68     move->x1 = 0;
  69     move->y1 = 0;
  70     move->x2 = 0;
  71     move->y2 = 0;
  72     move->is_capture = 0;
  73
  74     matched = sscanf (string, "%c%d%c%c%d", &xc1, &y1, &sep, &xc2, &y2);
  75     if (matched != 5)
  76         return FALSE;
  77
  78     x1 = tolower (xc1) - 'a';
  79     x2 = tolower (xc2) - 'a';
  80     y1 = LOA_BOARD_SIZE - y1;
  81     y2 = LOA_BOARD_SIZE - y2;
  82
  83     if (x1 < 0 || x1 >= LOA_BOARD_SIZE ||
  84         y1 < 0 || y1 >= LOA_BOARD_SIZE ||
  85         x2 < 0 || x2 >= LOA_BOARD_SIZE ||
  86         y2 < 0 || y2 >= LOA_BOARD_SIZE)
  87     {
  88         return FALSE;
  89     }
  90
  91     if (sep != '-' && sep != 'x' && sep != 'X')
  92         return FALSE;
  93
  94     move->x1 = x1;
  95     move->y1 = y1;
  96     move->x2 = x2;
  97     move->y2 = y2;
  98
  99     if (sep == 'x' || sep == 'X')
 100         move->is_capture = TRUE;
 101     else
 102         move->is_capture = FALSE;
 103
 104     return TRUE;
 105 }
 106
 107 /* Given an (x,y) position on the board, return the index of the array
 108  * used to count pieces in diagonal rows running from upper-left to
 109  * lower-right, (like a grave accent: à or like a backslash: \).
 110  *
 111  * This is the array to look into when a move occurs with dx and dy of
 112  * the same sign. */
 113 static int
 114 _grave_index (int x, int y)
 115 {
 116     return x - y + LOA_BOARD_SIZE - 1;
 117 }
 118
 119 /* Given an (x,y) position on the board, return the index of the array
 120  * used to count pieces in diagonal rows running from lower-left to
 121  * upper-right, (like an acute accent: á or like a forward slash: /).
 122  *
 123  * This is the array to look into when a move occurs with dx and dy of
 124  * opposite sign, (one positive, one negative). */
 125 static int
 126 _acute_index (int x, int y)
 127 {
 128     return x + y;
 129 }
 130
 131 static void
 132 loa_board_add_piece (loa_board_t *board, int x, int y, loa_cell_t cell)
 133 {
 134     assert (cell == LOA_CELL_BLACK || cell == LOA_CELL_WHITE);
 135     assert (board->cells[x][y] == LOA_CELL_EMPTY);
 136
 137     board->col_pieces[x]++;
 138     board->row_pieces[y]++;
 139     board->diag_grave_pieces[_grave_index (x, y)]++;
 140     board->diag_acute_pieces[_acute_index (x, y)]++;
 141
 142     board->num_pieces[cell]++;
 143
 144     board->cells[x][y] = cell;
 145 }
 146
 147 static loa_cell_t
 148 loa_board_remove_piece (loa_board_t *board, int x, int y)
 149 {
 150     loa_cell_t cell;
 151
 152     cell = board->cells[x][y];
 153
 154     if (cell == LOA_CELL_EMPTY)
 155         return LOA_CELL_EMPTY;
 156
 157     board->col_pieces[x]--;
 158     board->row_pieces[y]--;
 159     board->diag_grave_pieces[_grave_index (x, y)]--;
 160     board->diag_acute_pieces[_acute_index (x, y)]--;
 161
 162     board->num_pieces[cell]--;
 163
 164     board->cells[x][y] = LOA_CELL_EMPTY;
 165
 166     return cell;
 167 }
 168
 169 void
 170 loa_board_init (loa_board_t *board)
 171 {
 172     board->moves = NULL;
 173     board->moves_size = 0;
 174
 175     loa_board_reset (board);
 176 }
 177
 178 void
 179 loa_board_fini (loa_board_t *board)
 180 {
 181     if (board->moves)
 182         free (board->moves);
 183 }
 184
 185 void
 186 loa_board_reset (loa_board_t *board)
 187 {
 188     int i, x, y;
 189
 190     for (x = 0; x < LOA_BOARD_SIZE; x++)
 191         for (y = 0; y < LOA_BOARD_SIZE; y++)
 192             board->cells[x][y] = LOA_CELL_EMPTY;
 193
 194     board->num_pieces[LOA_CELL_BLACK] = 0;
 195     board->num_pieces[LOA_CELL_WHITE] = 0;
 196
 197     for (i = 0; i < LOA_BOARD_SIZE; i++) {
 198         board->row_pieces[i] = 0;
 199         board->col_pieces[i] = 0;
 200     }
 201
 202     for (i = 0; i < LOA_DIAG_ARRAY_SIZE; i++) {
 203         board->diag_grave_pieces[i] = 0;
 204         board->diag_acute_pieces[i] = 0;
 205     }
 206
 207     for (i = 1; i < LOA_BOARD_SIZE - 1; i++) {
 208         loa_board_add_piece (board, i, 0, LOA_CELL_BLACK);
 209         loa_board_add_piece (board, i, LOA_BOARD_SIZE - 1, LOA_CELL_BLACK);
 210         loa_board_add_piece (board, 0, i, LOA_CELL_WHITE);
 211         loa_board_add_piece (board, LOA_BOARD_SIZE - 1, i, LOA_CELL_WHITE);
 212     }
 213
 214     /* Leave board->moves and board->moves_size as allocated */
 215     board->num_moves = 0;
 216
 217     board->player = LOA_PLAYER_BLACK;
 218 }
 219
 220 static int
 221 loa_board_group_size_recursive (loa_board_t *board, int x, int y,
 222                                 loa_cell_t cell,
 223                                 uint64_t *visited)
 224 {
 225     uint64_t bit;
 226
 227     if (x < 0 || y < 0)
 228         return 0;
 229
 230     if (x >= LOA_BOARD_SIZE || y >= LOA_BOARD_SIZE)
 231         return 0;
 232
 233     bit = 1ll << (x * LOA_BOARD_SIZE + y);
 234     if (*visited & bit)
 235         return 0;
 236
 237     *visited |= bit;
 238
 239     if (board->cells[x][y] != cell)
 240         return 0;
 241
 242     return 1 +
 243         loa_board_group_size_recursive (board, x-1, y-1, cell, visited) +
 244         loa_board_group_size_recursive (board, x-1, y  , cell, visited) +
 245         loa_board_group_size_recursive (board, x-1, y+1, cell, visited) +
 246         loa_board_group_size_recursive (board, x  , y-1, cell, visited) +
 247         loa_board_group_size_recursive (board, x  , y  , cell, visited) +
 248         loa_board_group_size_recursive (board, x  , y+1, cell, visited) +
 249         loa_board_group_size_recursive (board, x+1, y-1, cell, visited) +
 250         loa_board_group_size_recursive (board, x+1, y  , cell, visited) +
 251         loa_board_group_size_recursive (board, x+1, y+1, cell, visited);
 252 }
 253
 254 static int
 255 loa_board_group_size (loa_board_t *board, int x, int y)
 256 {
 257     uint64_t visited = 0ll;
 258     loa_cell_t cell = board->cells[x][y];
 259
 260     return loa_board_group_size_recursive (board, x, y, cell, &visited);
 261 }
 262
 263 int
 264 loa_board_is_won (loa_board_t *board, int x, int y)
 265 {
 266     loa_cell_t cell = board->cells[x][y];
 267
 268     if (cell == LOA_CELL_EMPTY)
 269         return 0;
 270
 271     if (loa_board_group_size (board, x, y) == board->num_pieces[cell])
 272         return 1;
 273
 274     return 0;
 275 }
 276
 277 static loa_bool_t
 278 loa_board_move_legal (loa_board_t        *board,
 279                       const loa_move_t   *move,
 280                       char              **error)
 281 {
 282     int x, y;
 283     int x1, y1, x2, y2;
 284     int dx, dy;
 285     int step_x, step_y;
 286
 287     if (! loa_move_is_valid (move))
 288     {
 289         *error = "Invalid coordinates (not on board)";
 290         return FALSE;
 291     }
 292
 293     x1 = move->x1;
 294     y1 = move->y1;
 295     x2 = move->x2;
 296     y2 = move->y2;
 297
 298     if (board->cells[x1][y1] == LOA_CELL_EMPTY) {
 299         *error = "There is no piece there to move";
 300         return FALSE;
 301     }
 302
 303     if (board->cells[x1][y1] != board->player) {
 304         *error = "You cannot move your opponent's piece";
 305         return FALSE;
 306     }
 307
 308     if (board->cells[x2][y2] == board->cells[x1][y1]) {
 309         *error = "You cannot capture your own piece";
 310         return FALSE;
 311     }
 312
 313     dx = x2 - x1;
 314     dy = y2 - y1;
 315
 316     /* Here's the meat of Lines of Action legaility: Does the distance
 317      * moved exactly match the number of pieces (of either color) in
 318      * the row, column, or diagonal of the movement. */
 319     if (dx == 0) {
 320         /* Column */
 321         if (abs (dy) != board->col_pieces[x1]) {
 322             *error = "The move distance does not match the number of pieces in that column";
 323             return FALSE;
 324         }
 325     } else if (dy == 0) {
 326         /* Row */
 327         if (abs (dx) != board->row_pieces[y1]) {
 328             *error = "The move distance does not match the number of pieces in that row";
 329             return FALSE;
 330         }
 331     } else {
 332         if (abs (dx) != abs (dy)) {
 333             *error = "That move is not in a row, column, or diagonal";
 334             return FALSE;
 335         }
 336         /* Diagonal */
 337         if ((dx > 0) == (dy > 0)) {
 338             if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
 339                 *error = "The move distance does not match the number of pieces in that diagonal";
 340                 return FALSE;
 341             }
 342         } else {
 343             if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
 344                 *error = "The move distance does not match the number of pieces in that diagonal";
 345                 return FALSE;
 346             }
 347         }
 348     }
 349
 350     /* Finally, we have to ensure that no opponent pieces are being
 351      * jumped. */
 352     step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
 353     step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
 354     for (x = x1 + step_x, y = y1 + step_y;
 355          x != x2 || y != y2;
 356          x += step_x, y += step_y)
 357     {
 358         if (board->cells[x][y] != LOA_CELL_EMPTY &&
 359             board->cells[x][y] != board->cells[x1][y1])
 360         {
 361             *error = "You cannot jump an opponent's piece";
 362             return FALSE;
 363         }
 364     }
 365
 366     return TRUE;
 367 }
 368
 369 static void
 370 loa_board_next_player (loa_board_t *board)
 371 {
 372     if (board->player == LOA_PLAYER_BLACK)
 373         board->player = LOA_PLAYER_WHITE;
 374     else
 375         board->player = LOA_PLAYER_BLACK;
 376 }
 377
 378 /* XXX: Should check for a legal move for the current player and
 379  * return FALSE in that case, (that is, it should be illegal to pass
 380  * if there's a legal move available). */
 381 int
 382 loa_board_pass (loa_board_t *board)
 383 {
 384     loa_board_next_player (board);
 385
 386     return TRUE;
 387 }
 388
 389 /* Once the move is validated and executed, append it to the moves
 390  * array that stores the move history. */
 391 static void
 392 loa_board_add_move_to_history (loa_board_t      *board,
 393                                const loa_move_t *move)
 394 {
 395     board->num_moves++;
 396
 397     if (board->num_moves > board->moves_size) {
 398         if (board->moves_size)
 399             board->moves_size *= 2;
 400         else
 401             board->moves_size = 20;
 402
 403         board->moves = realloc (board->moves,
 404                                 board->moves_size * sizeof (loa_move_t));
 405         if (board->moves == NULL) {
 406             fprintf (stderr, "Out of memory.\n");
 407             exit (1);
 408         }
 409     }
 410
 411     board->moves[board->num_moves - 1] = *move;
 412 }
 413
 414 int
 415 loa_board_move (loa_board_t *board,
 416                 int x1, int y1,
 417                 int x2, int y2,
 418                 char **error)
 419 {
 420     loa_cell_t cell;
 421     loa_move_t move;
 422
 423     move.x1 = x1;
 424     move.y1 = y1;
 425     move.x2 = x2;
 426     move.y2 = y2;
 427
 428     if (! loa_board_move_legal (board, &move, error))
 429         return FALSE;
 430
 431     cell = loa_board_remove_piece (board, x1, y1);
 432     assert (cell == board->player);
 433
 434     cell = loa_board_remove_piece (board, x2, y2);
 435     if (cell == LOA_CELL_EMPTY) {
 436         move.is_capture = FALSE;
 437     } else {
 438         assert (cell != board->player);
 439         move.is_capture = TRUE;
 440     }
 441
 442     loa_board_add_piece (board, x2, y2, board->player);
 443
 444     loa_board_add_move_to_history (board, &move);
 445
 446     loa_board_next_player (board);
 447
 448     return TRUE;
 449 }
 450
 451 /* A few different ideas for displaying boards:
 452  *
 453  * 8│ │●│●│●│●│●│●│ |       8| |*|*|*|*|*|*| |
 454  * 7│○│ │ │ │ │ │ │○|       7|o| | | | | | |o|
 455  * 6│○│ │ │ │ │ │ │○|       6|o| | | | | | |o|
 456  * 5│○│ │ │ │ │ │ │○|       5|o| | | | | | |o|
 457  * 4│○│ │ │ │ │ │ │○|       4|o| | | | | | |o|
 458  * 3│○│ │ │ │ │ │ │○|       3|o| | | | | | |o|
 459  * 2│○│ │ │ │ │ │ │○|       2|o| | | | | | |o|
 460  * 1│ │●│●│●│●│●│●│ |       1| |*|*|*|*|*|*| |
 461  *   A B C D E F G H      A B C D E F G H
 462  *
 463  *  ┌───┬───┬───┬───┬───┬───┬───┬───┐   -------------------------------
 464  * 8│   │ ● │ ● │ ● │ ● │ ● │ ● │   │     8|   | * | * | * | * | * | * |   |
 465  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 466  * 7│ ○ │   │   │   │   │   │   │ ○ │     7| o |   |   |   |   |   |   | o |
 467  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 468  * 6│ ○ │   │   │   │   │   │   │ ○ │     6| o |   |   |   |   |   |   | o |
 469  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 470  * 5│ ○ │   │   │   │   │   │   │ ○ │     5| o |   |   |   |   |   |   | o |
 471  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 472  * 4│ ○ │   │   │   │   │   │   │ ○ │     4| o |   |   |   |   |   |   | o |
 473  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 474  * 3│ ○ │   │   │   │   │   │   │ ○ │     3| o |   |   |   |   |   |   | o |
 475  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 476  * 2│ ○ │   │   │   │   │   │   │ ○ │     2| o |   |   |   |   |   |   | o |
 477  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
 478  * 1│   │ ● │ ● │ ● │ ● │ ● │ ● │   │     1|   | * | * | * | * | * | * |   |
 479  *  └───┴───┴───┴───┴───┴───┴───┴───┘   -------------------------------
 480  *    A   B   C   D   E   F   G   H        A   B   C   D   E   F   G   H
 481  */
 482 char *
 483 loa_board_to_string (loa_board_t *board)
 484 {
 485     int x, y;
 486     /* In order of BLACK, WHITE, EMPTY */
 487     const char* cell_strings[] = {"●","○"," "};
 488     const char   board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
 489     const char     row_header[] = "│ ";
 490     const char cell_separator[] =    " │ ";
 491     const char     row_footer[] =                                " │";
 492     const char  row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
 493     const char   board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
 494     char *board_string = g_strdup ("");
 495
 496 #define APPEND(str) do {                                        \
 497     char *_new = g_strconcat (board_string, (str), NULL);       \
 498     free (board_string);                                        \
 499     board_string = _new;                                        \
 500 } while (0)
 501
 502 #define APPENDF(format, ...) do {                               \
 503     char *str = g_strdup_printf (format, ## __VA_ARGS__);       \
 504     APPEND (str);                                               \
 505     free (str);                                                 \
 506 } while (0)
 507
 508     APPENDF (" %s\n", board_header);
 509     for (y = 0; y < LOA_BOARD_SIZE; y++) {
 510         APPENDF ("%d%s", LOA_BOARD_SIZE - y, row_header);
 511         for (x = 0; x < LOA_BOARD_SIZE; x++) {
 512             APPENDF ("%s", cell_strings[board->cells[x][y]]);
 513             if (x != LOA_BOARD_SIZE - 1)
 514                 APPENDF ("%s", cell_separator);
 515         }
 516         APPENDF ("%s\n", row_footer);
 517         if (y != LOA_BOARD_SIZE -1)
 518             APPENDF (" %s\n", row_separator);
 519     }
 520     APPENDF (" %s\n", board_footer);
 521
 522     APPENDF ("   ");
 523     for (x = 0; x < LOA_BOARD_SIZE; x++) {
 524         APPENDF ("%c", 'A' + x);
 525         if (x != LOA_BOARD_SIZE - 1)
 526             APPENDF ("   ");
 527     }
 528     APPENDF ("\n");
 529
 530     return board_string;
 531 }