Add support for a 'history' command
[loudgame] / 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 }