Implement automatic pass (when there is no legal move) and end-of-game

[dvonn] / dvonn-board.c

diff --git a/dvonn-board.c b/dvonn-board.c
index 4aaac54aadc19bcb65f3a5f360c967206e417e51..c78905ee3910b521ae851dd49a9fa265ce9970e9 100644 (file)
--- a/dvonn-board.c
+++ b/dvonn-board.c
@@ -80,6 +80,8 @@ 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
@@ -101,6 +103,19 @@ dvonn_board_cell_occupied (dvonn_board_t *board,
     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)
@@ -152,7 +167,7 @@ dvonn_board_move_legal (dvonn_board_t *board,
        return FALSE;
     }
 
-    if (board->cells[x1][y1].type != board->player) {
+    if (! dvonn_board_cell_owned_by (board, x1, y1, board->player)) {
        *error = "You cannot move your opponent's stack";
        return FALSE;
     }
@@ -183,24 +198,84 @@ dvonn_board_move_legal (dvonn_board_t *board,
     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;
-}
-
-int
-dvonn_board_pass (dvonn_board_t *board)
-{
-    /* XXX: Should check here and only allow a pass if there are
-     * no legal moves. */
 
-    dvonn_board_next_player (board);
+    /* 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 TRUE;
+    return board->phase;
 }
 
 int
@@ -231,14 +306,60 @@ dvonn_board_place (dvonn_board_t *board,
 
     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,
@@ -261,6 +382,8 @@ dvonn_board_move (dvonn_board_t *board,
     board->cells[x1][y1].height = 0;
     board->cells[x1][y1].contains_red = FALSE;
 
+    eliminate_disconnected_stacks (board);
+
     dvonn_board_next_player (board);
 
     return TRUE;