X-Git-Url: https://git.cworth.org/git?p=dvonn;a=blobdiff_plain;f=dvonn-board.c;h=c78905ee3910b521ae851dd49a9fa265ce9970e9;hp=f80277531ee7a8ee9bf71ba616a2e8c2ca69ea45;hb=HEAD;hpb=2c8c385d00f60fad7a4b74b0b66516fbce62c50f

diff --git a/dvonn-board.c b/dvonn-board.c
index f802775..c78905e 100644
--- a/dvonn-board.c
+++ b/dvonn-board.c
@@ -63,6 +63,7 @@ dvonn_board_init (dvonn_board_t *board)
 	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;
 	}
     }
 
@@ -79,6 +80,57 @@ dvonn_board_init (dvonn_board_t *board)
     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
@@ -87,6 +139,8 @@ dvonn_board_move_legal (dvonn_board_t *board,
 			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 ||
@@ -96,33 +150,132 @@ dvonn_board_move_legal (dvonn_board_t *board,
 	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 (dvonn_board_cell_surrounded (board, x1, y1)) {
+	*error = "You cannot move a piece that is surrounded";
+	return FALSE;
+    }
+
+    if (! dvonn_board_cell_owned_by (board, x1, y1, board->player)) {
+	*error = "You cannot move your opponent's stack";
 	return FALSE;
     }
 
-    if (board->cells[x1][y1].type != board->player) {
-	*error = "You cannot move your opponent's piece";
+    if (board->cells[x2][y2].type == DVONN_CELL_EMPTY) {
+	*error = "You cannot move to an empty space";
 	return FALSE;
     }
 
-    /* XXX: Need to code up DVONN-legal move calculation here. */
+    /* 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
@@ -140,25 +293,73 @@ dvonn_board_place (dvonn_board_t *board,
 	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,
@@ -175,9 +376,13 @@ dvonn_board_move (dvonn_board_t *board,
 
     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);