8ea6f99d36bb45ad758011bee975ef57faf3c86a
[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 <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 }