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;
83 board->score[DVONN_PLAYER_BLACK] = 0;
84 board->score[DVONN_PLAYER_WHITE] = 0;
88 dvonn_board_cell_occupied (dvonn_board_t *board,
91 if (x < 0 || x >= DVONN_BOARD_X_SIZE ||
92 y < 0 || y >= DVONN_BOARD_Y_SIZE)
97 if (board->cells[x][y].type == DVONN_CELL_INVALID ||
98 board->cells[x][y].type == DVONN_CELL_EMPTY)
107 dvonn_board_cell_owned_by (dvonn_board_t *board,
109 dvonn_player_t player)
111 if (! dvonn_board_cell_occupied (board, x, y))
114 /* Cast here to avoid compiler warning about mixing enum types in
116 return board->cells[x][y].type == (dvonn_cell_type_t) player;
120 dvonn_board_cell_surrounded (dvonn_board_t *board,
126 dvonn_board_cell_occupied (board, x - 1, y) +
127 dvonn_board_cell_occupied (board, x + 1, y) +
128 dvonn_board_cell_occupied (board, x, y - 1) +
129 dvonn_board_cell_occupied (board, x, y + 1) +
130 dvonn_board_cell_occupied (board, x + 1, y - 1) +
131 dvonn_board_cell_occupied (board, x - 1, y + 1);
133 return (surround_count == 6);
137 dvonn_board_move_legal (dvonn_board_t *board,
144 if (x1 < 0 || x1 >= DVONN_BOARD_X_SIZE ||
145 y1 < 0 || y1 >= DVONN_BOARD_Y_SIZE ||
146 x2 < 0 || x2 >= DVONN_BOARD_X_SIZE ||
147 y2 < 0 || y2 >= DVONN_BOARD_Y_SIZE)
149 *error = "Invalid coordinates (not on board)";
153 if (board->cells[x1][y1].type == DVONN_CELL_INVALID ||
154 board->cells[x2][y2].type == DVONN_CELL_INVALID)
156 *error = "Not a valid board space";
160 if (board->cells[x1][y1].type == DVONN_CELL_EMPTY) {
161 *error = "There are no pieces there to move";
165 if (dvonn_board_cell_surrounded (board, x1, y1)) {
166 *error = "You cannot move a piece that is surrounded";
170 if (! dvonn_board_cell_owned_by (board, x1, y1, board->player)) {
171 *error = "You cannot move your opponent's stack";
175 if (board->cells[x2][y2].type == DVONN_CELL_EMPTY) {
176 *error = "You cannot move to an empty space";
180 /* Move must be in a straight line, which in our array is
181 * horizontal, vertical, or one of the diagonals. */
183 distance = abs (y2 - y1);
185 distance = abs (x2 - x1);
186 else if ((x2 - x1) == - (y2 - y1))
187 distance = abs (x2 - x1);
189 *error = "Move is not in a straight line";
193 if (distance != board->cells[x1][y1].height) {
194 *error = "Move distance is not the same as stack height";
202 dvonn_board_player_has_legal_move (dvonn_board_t *board)
207 for (x = 0; x < DVONN_BOARD_X_SIZE; x++) {
208 for (y = 0; y < DVONN_BOARD_X_SIZE; y++) {
209 if (! dvonn_board_cell_occupied (board, x, y))
211 if (! (board->cells[x][y].type == (dvonn_cell_type_t) board->player))
213 height = board->cells[x][y].height;
214 if (dvonn_board_move_legal (board, x, y,
215 x + height, y, &error))
217 if (dvonn_board_move_legal (board, x, y,
218 x - height, y, &error))
220 if (dvonn_board_move_legal (board, x, y,
221 x, y + height, &error))
223 if (dvonn_board_move_legal (board, x, y,
224 x, y - height, &error))
226 if (dvonn_board_move_legal (board, x, y,
227 x + height, y - height, &error))
229 if (dvonn_board_move_legal (board, x, y,
230 x - height, y + height, &error))
239 dvonn_board_next_player (dvonn_board_t *board)
241 if (board->player == DVONN_PLAYER_BLACK)
242 board->player = DVONN_PLAYER_WHITE;
244 board->player = DVONN_PLAYER_BLACK;
246 /* Only look for legal moves during the movement phase. */
247 if (board->phase != DVONN_PHASE_MOVEMENT)
250 if (! dvonn_board_player_has_legal_move (board)) {
251 if (board->player == DVONN_PLAYER_BLACK)
252 board->player = DVONN_PLAYER_WHITE;
254 board->player = DVONN_PLAYER_BLACK;
256 if (! dvonn_board_player_has_legal_move (board))
261 board->phase = DVONN_PHASE_GAME_OVER;
263 /* Compute final score. */
264 for (x = 0; x < DVONN_BOARD_X_SIZE; x++) {
265 for (y = 0; y < DVONN_BOARD_Y_SIZE; y++) {
266 if (dvonn_board_cell_occupied (board, x, y))
268 cell = &board->cells[x][y];
269 if (cell->type == DVONN_CELL_RED)
271 board->score[cell->type] += cell->height;
282 dvonn_board_place (dvonn_board_t *board,
286 if (board->phase != DVONN_PHASE_PLACEMENT) {
287 *error = "Cannot place outside of placement phase";
291 if (board->cells[x][y].type != DVONN_CELL_EMPTY) {
292 *error = "Cannot place on an occupied space";
296 if (board->moves < 3) {
297 board->cells[x][y].type = DVONN_CELL_RED;
298 board->cells[x][y].contains_red = TRUE;
299 } else if (board->moves % 2) {
300 board->cells[x][y].type = DVONN_CELL_BLACK;
302 board->cells[x][y].type = DVONN_CELL_WHITE;
305 board->cells[x][y].height = 1;
309 dvonn_board_next_player (board);
311 if (board->moves == 49) {
312 board->phase = DVONN_PHASE_MOVEMENT;
314 board->player = DVONN_PLAYER_WHITE;
321 fill_living(dvonn_board_t *board,
322 int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE],
325 if (dvonn_board_cell_occupied (board, x, y) && ! living[x][y])
329 fill_living (board, living, x - 1, y);
330 fill_living (board, living, x + 1, y);
331 fill_living (board, living, x, y - 1);
332 fill_living (board, living, x, y + 1);
333 fill_living (board, living, x + 1, y - 1);
334 fill_living (board, living, x - 1, y + 1);
339 eliminate_disconnected_stacks (dvonn_board_t *board)
342 int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE];
344 for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
345 for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
348 for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
349 for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
350 if (board->cells[x][y].contains_red)
351 fill_living (board, living, x, y);
353 for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
354 for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
355 if (dvonn_board_cell_occupied (board, x, y) &&
358 board->cells[x][y].type = DVONN_CELL_EMPTY;
359 board->cells[x][y].height = 0;
364 dvonn_board_move (dvonn_board_t *board,
369 if (board->phase != DVONN_PHASE_MOVEMENT) {
370 *error = "Cannot move outside of placement phase";
374 if (! dvonn_board_move_legal (board, x1, y1, x2, y2, error))
377 board->cells[x2][y2].height += board->cells[x1][y1].height;
378 board->cells[x2][y2].type = board->cells[x1][y1].type;
379 board->cells[x2][y2].contains_red |= board->cells[x1][y1].contains_red;
381 board->cells[x1][y1].type = DVONN_CELL_EMPTY;
382 board->cells[x1][y1].height = 0;
383 board->cells[x1][y1].contains_red = FALSE;
385 eliminate_disconnected_stacks (board);
387 dvonn_board_next_player (board);