for (y = 0; y < DVONN_BOARD_Y_SIZE; y++) {
board->cells[x][y].type = DVONN_CELL_EMPTY;
board->cells[x][y].height = 0;
+ board->cells[x][y].contains_red = FALSE;
}
}
board->phase = DVONN_PHASE_PLACEMENT;
board->player = DVONN_PLAYER_WHITE;
board->moves = 0;
+ board->score[DVONN_PLAYER_BLACK] = 0;
+ board->score[DVONN_PLAYER_WHITE] = 0;
+}
+
+dvonn_bool_t
+dvonn_board_cell_occupied (dvonn_board_t *board,
+ int x, int y)
+{
+ if (x < 0 || x >= DVONN_BOARD_X_SIZE ||
+ y < 0 || y >= DVONN_BOARD_Y_SIZE)
+ {
+ return FALSE;
+ }
+
+ if (board->cells[x][y].type == DVONN_CELL_INVALID ||
+ board->cells[x][y].type == DVONN_CELL_EMPTY)
+ {
+ return FALSE;
+ }
+
+ return TRUE;
+}
+
+dvonn_bool_t
+dvonn_board_cell_owned_by (dvonn_board_t *board,
+ int x, int y,
+ dvonn_player_t player)
+{
+ if (! dvonn_board_cell_occupied (board, x, y))
+ return FALSE;
+
+ /* Cast here to avoid compiler warning about mixing enum types in
+ * a comparison. */
+ return board->cells[x][y].type == (dvonn_cell_type_t) player;
+}
+
+dvonn_bool_t
+dvonn_board_cell_surrounded (dvonn_board_t *board,
+ int x, int y)
+{
+ int surround_count;
+
+ surround_count =
+ dvonn_board_cell_occupied (board, x - 1, y) +
+ dvonn_board_cell_occupied (board, x + 1, y) +
+ dvonn_board_cell_occupied (board, x, y - 1) +
+ dvonn_board_cell_occupied (board, x, y + 1) +
+ dvonn_board_cell_occupied (board, x + 1, y - 1) +
+ dvonn_board_cell_occupied (board, x - 1, y + 1);
+
+ return (surround_count == 6);
}
static dvonn_bool_t
int x2, int y2,
char **error)
{
+ int distance;
+
if (x1 < 0 || x1 >= DVONN_BOARD_X_SIZE ||
y1 < 0 || y1 >= DVONN_BOARD_Y_SIZE ||
x2 < 0 || x2 >= DVONN_BOARD_X_SIZE ||
return FALSE;
}
- if (board->cells[x1][y1].type == DVONN_CELL_INVALID) {
+ if (board->cells[x1][y1].type == DVONN_CELL_INVALID ||
+ board->cells[x2][y2].type == DVONN_CELL_INVALID)
+ {
*error = "Not a valid board space";
return FALSE;
}
if (board->cells[x1][y1].type == DVONN_CELL_EMPTY) {
- *error = "There is no piece there to move";
+ *error = "There are no pieces there to move";
return FALSE;
}
- if (board->cells[x1][y1].type != board->player) {
- *error = "You cannot move your opponent's piece";
+ if (dvonn_board_cell_surrounded (board, x1, y1)) {
+ *error = "You cannot move a piece that is surrounded";
return FALSE;
}
- /* XXX: Need to code up DVONN-legal move calculation here. */
+ if (! dvonn_board_cell_owned_by (board, x1, y1, board->player)) {
+ *error = "You cannot move your opponent's stack";
+ return FALSE;
+ }
+
+ if (board->cells[x2][y2].type == DVONN_CELL_EMPTY) {
+ *error = "You cannot move to an empty space";
+ return FALSE;
+ }
+
+ /* Move must be in a straight line, which in our array is
+ * horizontal, vertical, or one of the diagonals. */
+ if (x2 == x1)
+ distance = abs (y2 - y1);
+ else if (y2 == y1)
+ distance = abs (x2 - x1);
+ else if ((x2 - x1) == - (y2 - y1))
+ distance = abs (x2 - x1);
+ else {
+ *error = "Move is not in a straight line";
+ return FALSE;
+ }
+
+ if (distance != board->cells[x1][y1].height) {
+ *error = "Move distance is not the same as stack height";
+ return FALSE;
+ }
return TRUE;
}
-static void
+static dvonn_bool_t
+dvonn_board_player_has_legal_move (dvonn_board_t *board)
+{
+ int x, y, height;
+ char *error;
+
+ for (x = 0; x < DVONN_BOARD_X_SIZE; x++) {
+ for (y = 0; y < DVONN_BOARD_X_SIZE; y++) {
+ if (! dvonn_board_cell_occupied (board, x, y))
+ continue;
+ if (! (board->cells[x][y].type == (dvonn_cell_type_t) board->player))
+ continue;
+ height = board->cells[x][y].height;
+ if (dvonn_board_move_legal (board, x, y,
+ x + height, y, &error))
+ return TRUE;
+ if (dvonn_board_move_legal (board, x, y,
+ x - height, y, &error))
+ return TRUE;
+ if (dvonn_board_move_legal (board, x, y,
+ x, y + height, &error))
+ return TRUE;
+ if (dvonn_board_move_legal (board, x, y,
+ x, y - height, &error))
+ return TRUE;
+ if (dvonn_board_move_legal (board, x, y,
+ x + height, y - height, &error))
+ return TRUE;
+ if (dvonn_board_move_legal (board, x, y,
+ x - height, y + height, &error))
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+
+
+static dvonn_phase_t
dvonn_board_next_player (dvonn_board_t *board)
{
if (board->player == DVONN_PLAYER_BLACK)
board->player = DVONN_PLAYER_WHITE;
else
board->player = DVONN_PLAYER_BLACK;
+
+ /* Only look for legal moves during the movement phase. */
+ if (board->phase != DVONN_PHASE_MOVEMENT)
+ return board->phase;
+
+ if (! dvonn_board_player_has_legal_move (board)) {
+ if (board->player == DVONN_PLAYER_BLACK)
+ board->player = DVONN_PLAYER_WHITE;
+ else
+ board->player = DVONN_PLAYER_BLACK;
+
+ if (! dvonn_board_player_has_legal_move (board))
+ {
+ int x, y;
+ dvonn_cell_t *cell;
+
+ board->phase = DVONN_PHASE_GAME_OVER;
+
+ /* Compute final score. */
+ for (x = 0; x < DVONN_BOARD_X_SIZE; x++) {
+ for (y = 0; y < DVONN_BOARD_Y_SIZE; y++) {
+ if (dvonn_board_cell_occupied (board, x, y))
+ {
+ cell = &board->cells[x][y];
+ if (cell->type == DVONN_CELL_RED)
+ continue;
+ board->score[cell->type] += cell->height;
+ }
+ }
+ }
+ }
+ }
+
+ return board->phase;
}
int
return FALSE;
}
- if (board->moves < 3)
+ if (board->moves < 3) {
board->cells[x][y].type = DVONN_CELL_RED;
- else if (board->moves % 2)
+ board->cells[x][y].contains_red = TRUE;
+ } else if (board->moves % 2) {
board->cells[x][y].type = DVONN_CELL_BLACK;
- else
+ } else {
board->cells[x][y].type = DVONN_CELL_WHITE;
+ }
+
+ board->cells[x][y].height = 1;
board->moves++;
+ dvonn_board_next_player (board);
+
if (board->moves == 49) {
board->phase = DVONN_PHASE_MOVEMENT;
board->moves = 0;
+ board->player = DVONN_PLAYER_WHITE;
}
return TRUE;
}
+static void
+fill_living(dvonn_board_t *board,
+ int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE],
+ int x, int y)
+{
+ if (dvonn_board_cell_occupied (board, x, y) && ! living[x][y])
+ {
+ living[x][y] = 1;
+
+ fill_living (board, living, x - 1, y);
+ fill_living (board, living, x + 1, y);
+ fill_living (board, living, x, y - 1);
+ fill_living (board, living, x, y + 1);
+ fill_living (board, living, x + 1, y - 1);
+ fill_living (board, living, x - 1, y + 1);
+ }
+}
+
+static void
+eliminate_disconnected_stacks (dvonn_board_t *board)
+{
+ int x, y;
+ int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE];
+
+ for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
+ for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
+ living[x][y] = 0;
+
+ for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
+ for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
+ if (board->cells[x][y].contains_red)
+ fill_living (board, living, x, y);
+
+ for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
+ for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
+ if (dvonn_board_cell_occupied (board, x, y) &&
+ ! living[x][y])
+ {
+ board->cells[x][y].type = DVONN_CELL_EMPTY;
+ board->cells[x][y].height = 0;
+ }
+}
+
int
dvonn_board_move (dvonn_board_t *board,
int x1, int y1,
if (! dvonn_board_move_legal (board, x1, y1, x2, y2, error))
return FALSE;
- /* XXX: Need to execute the move here. */
+ board->cells[x2][y2].height += board->cells[x1][y1].height;
+ board->cells[x2][y2].type = board->cells[x1][y1].type;
+ board->cells[x2][y2].contains_red |= board->cells[x1][y1].contains_red;
+
+ board->cells[x1][y1].type = DVONN_CELL_EMPTY;
+ board->cells[x1][y1].height = 0;
+ board->cells[x1][y1].contains_red = FALSE;
+
+ eliminate_disconnected_stacks (board);
dvonn_board_next_player (board);
projects / dvonn / blobdiff