2 * Copyright (C) 2009 Carl Worth
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.
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.
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/ .
17 * Author: Carl Worth <cworth@cworth.org>
26 #include "dvonn-board.h"
28 /* Just a diagram to help start thinking about data structures:
33 * 2 ○ ● ● ○ ○ ○ ○ ○ ○ ○
34 * 3 ○ ● ○ ● ○ ○ ○ ○ ○ ○ ○
35 * 4 ○ ● ● ○ ○ ○ ○ ○ ○ ○ K
36 * 5 ○ ○ ○ ○ ○ ○ ○ ○ ○ J
41 * 1 x x ○ ○ ○ ○ ○ ○ ○ ○ ○
42 * 2 x ○ ● ● ○ ○ ○ ○ ○ ○ ○
43 * 3 ○ ● ○ ● ○ ○ ○ ○ ○ ○ ○
44 * 4 ○ ● ● ○ ○ ○ ○ ○ ○ ○ x
45 * 5 ○ ○ ○ ○ ○ ○ ○ ○ ○ x x
46 * A B C D E F G H I J K
48 * With connections as:
58 dvonn_board_init (dvonn_board_t *board)
62 for (x = 0; x < DVONN_BOARD_X_SIZE; x++) {
63 for (y = 0; y < DVONN_BOARD_Y_SIZE; y++) {
64 board->cells[x][y].type = DVONN_CELL_EMPTY;
65 board->cells[x][y].height = 0;
66 board->cells[x][y].contains_red = FALSE;
70 /* Cut out the unplayable "corners" of the board. */
71 for (x = 0; x < DVONN_BOARD_Y_SIZE / 2; x++) {
72 for (y = 0; y < (DVONN_BOARD_Y_SIZE / 2) - x; y++) {
73 board->cells[x][y].type = DVONN_CELL_INVALID;
75 [DVONN_BOARD_X_SIZE-1-x]
76 [DVONN_BOARD_Y_SIZE-1-y].type = DVONN_CELL_INVALID;
80 board->phase = DVONN_PHASE_PLACEMENT;
81 board->player = DVONN_PLAYER_WHITE;
86 dvonn_board_cell_occupied (dvonn_board_t *board,
89 if (x < 0 || x >= DVONN_BOARD_X_SIZE ||
90 y < 0 || y >= DVONN_BOARD_Y_SIZE)
95 if (board->cells[x][y].type == DVONN_CELL_INVALID ||
96 board->cells[x][y].type == DVONN_CELL_EMPTY)
105 dvonn_board_cell_owned_by (dvonn_board_t *board,
107 dvonn_player_t player)
109 if (! dvonn_board_cell_occupied (board, x, y))
112 /* Cast here to avoid compiler warning about mixing enum types in
114 return board->cells[x][y].type == (dvonn_cell_type_t) player;
118 dvonn_board_cell_surrounded (dvonn_board_t *board,
124 dvonn_board_cell_occupied (board, x - 1, y) +
125 dvonn_board_cell_occupied (board, x + 1, y) +
126 dvonn_board_cell_occupied (board, x, y - 1) +
127 dvonn_board_cell_occupied (board, x, y + 1) +
128 dvonn_board_cell_occupied (board, x + 1, y - 1) +
129 dvonn_board_cell_occupied (board, x - 1, y + 1);
131 return (surround_count == 6);
135 dvonn_board_move_legal (dvonn_board_t *board,
142 if (x1 < 0 || x1 >= DVONN_BOARD_X_SIZE ||
143 y1 < 0 || y1 >= DVONN_BOARD_Y_SIZE ||
144 x2 < 0 || x2 >= DVONN_BOARD_X_SIZE ||
145 y2 < 0 || y2 >= DVONN_BOARD_Y_SIZE)
147 *error = "Invalid coordinates (not on board)";
151 if (board->cells[x1][y1].type == DVONN_CELL_INVALID ||
152 board->cells[x2][y2].type == DVONN_CELL_INVALID)
154 *error = "Not a valid board space";
158 if (board->cells[x1][y1].type == DVONN_CELL_EMPTY) {
159 *error = "There are no pieces there to move";
163 if (dvonn_board_cell_surrounded (board, x1, y1)) {
164 *error = "You cannot move a piece that is surrounded";
168 if (! dvonn_board_cell_owned_by (board, x1, y1, board->player)) {
169 *error = "You cannot move your opponent's stack";
173 if (board->cells[x2][y2].type == DVONN_CELL_EMPTY) {
174 *error = "You cannot move to an empty space";
178 /* Move must be in a straight line, which in our array is
179 * horizontal, vertical, or one of the diagonals. */
181 distance = abs (y2 - y1);
183 distance = abs (x2 - x1);
184 else if ((x2 - x1) == - (y2 - y1))
185 distance = abs (x2 - x1);
187 *error = "Move is not in a straight line";
191 if (distance != board->cells[x1][y1].height) {
192 *error = "Move distance is not the same as stack height";
200 dvonn_board_next_player (dvonn_board_t *board)
202 if (board->player == DVONN_PLAYER_BLACK)
203 board->player = DVONN_PLAYER_WHITE;
205 board->player = DVONN_PLAYER_BLACK;
209 dvonn_board_pass (dvonn_board_t *board)
211 /* XXX: Should check here and only allow a pass if there are
214 dvonn_board_next_player (board);
220 dvonn_board_place (dvonn_board_t *board,
224 if (board->phase != DVONN_PHASE_PLACEMENT) {
225 *error = "Cannot place outside of placement phase";
229 if (board->cells[x][y].type != DVONN_CELL_EMPTY) {
230 *error = "Cannot place on an occupied space";
234 if (board->moves < 3) {
235 board->cells[x][y].type = DVONN_CELL_RED;
236 board->cells[x][y].contains_red = TRUE;
237 } else if (board->moves % 2) {
238 board->cells[x][y].type = DVONN_CELL_BLACK;
240 board->cells[x][y].type = DVONN_CELL_WHITE;
243 board->cells[x][y].height = 1;
247 dvonn_board_next_player (board);
249 if (board->moves == 49) {
250 board->phase = DVONN_PHASE_MOVEMENT;
252 board->player = DVONN_PLAYER_WHITE;
259 fill_living(dvonn_board_t *board,
260 int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE],
263 if (dvonn_board_cell_occupied (board, x, y) && ! living[x][y])
267 fill_living (board, living, x - 1, y);
268 fill_living (board, living, x + 1, y);
269 fill_living (board, living, x, y - 1);
270 fill_living (board, living, x, y + 1);
271 fill_living (board, living, x + 1, y - 1);
272 fill_living (board, living, x - 1, y + 1);
277 eliminate_disconnected_stacks (dvonn_board_t *board)
280 int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE];
282 for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
283 for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
286 for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
287 for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
288 if (board->cells[x][y].contains_red)
289 fill_living (board, living, x, y);
291 for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
292 for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
293 if (dvonn_board_cell_occupied (board, x, y) &&
296 board->cells[x][y].type = DVONN_CELL_EMPTY;
297 board->cells[x][y].height = 0;
302 dvonn_board_move (dvonn_board_t *board,
307 if (board->phase != DVONN_PHASE_MOVEMENT) {
308 *error = "Cannot move outside of placement phase";
312 if (! dvonn_board_move_legal (board, x1, y1, x2, y2, error))
315 board->cells[x2][y2].height += board->cells[x1][y1].height;
316 board->cells[x2][y2].type = board->cells[x1][y1].type;
317 board->cells[x2][y2].contains_red |= board->cells[x1][y1].contains_red;
319 board->cells[x1][y1].type = DVONN_CELL_EMPTY;
320 board->cells[x1][y1].height = 0;
321 board->cells[x1][y1].contains_red = FALSE;
323 eliminate_disconnected_stacks (board);
325 dvonn_board_next_player (board);