git.cworth.org Git - dvonn/blob - dvonn-board.c

   1 /*
   2  * Copyright (C) 2009 Carl Worth
   3  *
   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.
   8  *
   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.
  13  *
  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/ .
  16  *
  17  * Author: Carl Worth <cworth@cworth.org>
  18  */
  19
  20 #include <stdint.h>
  21 #include <stdlib.h>
  22 #include <assert.h>
  23
  24 #include <glib.h>
  25
  26 #include "dvonn-board.h"
  27
  28 /* Just a diagram to help start thinking about data structures:
  29  *
  30  * Played/drawn as:
  31  *
  32  *   1 ○ ○ ○ ○ ○ ○ ○ ○ ○
  33  *  2 ○ ● ● ○ ○ ○ ○ ○ ○ ○
  34  * 3 ○ ● ○ ● ○ ○ ○ ○ ○ ○ ○
  35  *  4 ○ ● ● ○ ○ ○ ○ ○ ○ ○ K
  36  *   5 ○ ○ ○ ○ ○ ○ ○ ○ ○ J
  37  *      A B C D E F G H I
  38  *
  39  * Stored as:
  40  *
  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
  47  *
  48  * With connections as:
  49  *
  50  *         C2  D2
  51  *          | /
  52  *  B3 <-> C3 <-> D3
  53  *        / |
  54  *      B2 C4
  55  */
  56
  57 void
  58 dvonn_board_init (dvonn_board_t *board)
  59 {
  60     int x, y;
  61
  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;
  67         }
  68     }
  69
  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;
  74             board->cells
  75                 [DVONN_BOARD_X_SIZE-1-x]
  76                 [DVONN_BOARD_Y_SIZE-1-y].type = DVONN_CELL_INVALID;
  77         }
  78     }
  79
  80     board->phase = DVONN_PHASE_PLACEMENT;
  81     board->player = DVONN_PLAYER_WHITE;
  82     board->moves = 0;
  83     board->score[DVONN_PLAYER_BLACK] = 0;
  84     board->score[DVONN_PLAYER_WHITE] = 0;
  85 }
  86
  87 dvonn_bool_t
  88 dvonn_board_cell_occupied (dvonn_board_t *board,
  89                            int x, int y)
  90 {
  91     if (x < 0 || x >= DVONN_BOARD_X_SIZE ||
  92         y < 0 || y >= DVONN_BOARD_Y_SIZE)
  93     {
  94         return FALSE;
  95     }
  96
  97     if (board->cells[x][y].type == DVONN_CELL_INVALID ||
  98         board->cells[x][y].type == DVONN_CELL_EMPTY)
  99     {
 100         return FALSE;
 101     }
 102
 103     return TRUE;
 104 }
 105
 106 dvonn_bool_t
 107 dvonn_board_cell_owned_by (dvonn_board_t *board,
 108                            int x, int y,
 109                            dvonn_player_t player)
 110 {
 111     if (! dvonn_board_cell_occupied (board, x, y))
 112         return FALSE;
 113
 114     /* Cast here to avoid compiler warning about mixing enum types in
 115      * a comparison. */
 116     return board->cells[x][y].type == (dvonn_cell_type_t) player;
 117 }
 118
 119 dvonn_bool_t
 120 dvonn_board_cell_surrounded (dvonn_board_t *board,
 121                              int x, int y)
 122 {
 123     int surround_count;
 124
 125     surround_count =
 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);
 132
 133     return (surround_count == 6);
 134 }
 135
 136 static dvonn_bool_t
 137 dvonn_board_move_legal (dvonn_board_t *board,
 138                         int x1, int y1,
 139                         int x2, int y2,
 140                         char **error)
 141 {
 142     int distance;
 143
 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)
 148     {
 149         *error = "Invalid coordinates (not on board)";
 150         return FALSE;
 151     }
 152
 153     if (board->cells[x1][y1].type == DVONN_CELL_INVALID ||
 154         board->cells[x2][y2].type == DVONN_CELL_INVALID)
 155     {
 156         *error = "Not a valid board space";
 157         return FALSE;
 158     }
 159
 160     if (board->cells[x1][y1].type == DVONN_CELL_EMPTY) {
 161         *error = "There are no pieces there to move";
 162         return FALSE;
 163     }
 164
 165     if (dvonn_board_cell_surrounded (board, x1, y1)) {
 166         *error = "You cannot move a piece that is surrounded";
 167         return FALSE;
 168     }
 169
 170     if (! dvonn_board_cell_owned_by (board, x1, y1, board->player)) {
 171         *error = "You cannot move your opponent's stack";
 172         return FALSE;
 173     }
 174
 175     if (board->cells[x2][y2].type == DVONN_CELL_EMPTY) {
 176         *error = "You cannot move to an empty space";
 177         return FALSE;
 178     }
 179
 180     /* Move must be in a straight line, which in our array is
 181      * horizontal, vertical, or one of the diagonals. */
 182     if (x2 == x1)
 183         distance = abs (y2 - y1);
 184     else if (y2 == y1)
 185         distance = abs (x2 - x1);
 186     else if ((x2 - x1) == - (y2 - y1))
 187         distance = abs (x2 - x1);
 188     else {
 189         *error = "Move is not in a straight line";
 190         return FALSE;
 191     }
 192
 193     if (distance != board->cells[x1][y1].height) {
 194         *error = "Move distance is not the same as stack height";
 195         return FALSE;
 196     }
 197
 198     return TRUE;
 199 }
 200
 201 static dvonn_bool_t
 202 dvonn_board_player_has_legal_move (dvonn_board_t *board)
 203 {
 204     int x, y, height;
 205     char *error;
 206
 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))
 210                 continue;
 211             if (! (board->cells[x][y].type == (dvonn_cell_type_t) board->player))
 212                 continue;
 213             height = board->cells[x][y].height;
 214             if (dvonn_board_move_legal (board, x, y,
 215                                         x + height, y, &error))
 216                 return TRUE;
 217             if (dvonn_board_move_legal (board, x, y,
 218                                         x - height, y, &error))
 219                 return TRUE;
 220             if (dvonn_board_move_legal (board, x, y,
 221                                         x, y + height, &error))
 222                 return TRUE;
 223             if (dvonn_board_move_legal (board, x, y,
 224                                         x, y - height, &error))
 225                 return TRUE;
 226             if (dvonn_board_move_legal (board, x, y,
 227                                         x + height, y - height, &error))
 228                 return TRUE;
 229             if (dvonn_board_move_legal (board, x, y,
 230                                         x - height, y + height, &error))
 231                 return TRUE;
 232         }
 233     }
 234     return FALSE;
 235 }
 236
 237
 238 static dvonn_phase_t
 239 dvonn_board_next_player (dvonn_board_t *board)
 240 {
 241     if (board->player == DVONN_PLAYER_BLACK)
 242         board->player = DVONN_PLAYER_WHITE;
 243     else
 244         board->player = DVONN_PLAYER_BLACK;
 245
 246     /* Only look for legal moves during the movement phase. */
 247     if (board->phase != DVONN_PHASE_MOVEMENT)
 248         return board->phase;
 249
 250     if (! dvonn_board_player_has_legal_move (board)) {
 251         if (board->player == DVONN_PLAYER_BLACK)
 252             board->player = DVONN_PLAYER_WHITE;
 253         else
 254             board->player = DVONN_PLAYER_BLACK;
 255
 256         if (! dvonn_board_player_has_legal_move (board))
 257         {
 258             int x, y;
 259             dvonn_cell_t *cell;
 260
 261             board->phase = DVONN_PHASE_GAME_OVER;
 262
 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))
 267                     {
 268                         cell = &board->cells[x][y];
 269                         if (cell->type == DVONN_CELL_RED)
 270                             continue;
 271                         board->score[cell->type] += cell->height;
 272                     }
 273                 }
 274             }
 275         }
 276     }
 277
 278     return board->phase;
 279 }
 280
 281 int
 282 dvonn_board_place (dvonn_board_t *board,
 283                    int x, int y,
 284                    char **error)
 285 {
 286     if (board->phase != DVONN_PHASE_PLACEMENT) {
 287         *error = "Cannot place outside of placement phase";
 288         return FALSE;
 289     }
 290
 291     if (board->cells[x][y].type != DVONN_CELL_EMPTY) {
 292         *error = "Cannot place on an occupied space";
 293         return FALSE;
 294     }
 295
 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;
 301     } else {
 302         board->cells[x][y].type = DVONN_CELL_WHITE;
 303     }
 304
 305     board->cells[x][y].height = 1;
 306
 307     board->moves++;
 308
 309     dvonn_board_next_player (board);
 310
 311     if (board->moves == 49) {
 312         board->phase = DVONN_PHASE_MOVEMENT;
 313         board->moves = 0;
 314         board->player = DVONN_PLAYER_WHITE;
 315     }
 316
 317     return TRUE;
 318 }
 319
 320 static void
 321 fill_living(dvonn_board_t *board,
 322             int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE],
 323             int x, int y)
 324 {
 325     if (dvonn_board_cell_occupied (board, x, y) && ! living[x][y])
 326     {
 327         living[x][y] = 1;
 328
 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);
 335     }
 336 }
 337
 338 static void
 339 eliminate_disconnected_stacks (dvonn_board_t *board)
 340 {
 341     int x, y;
 342     int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE];
 343
 344     for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
 345         for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
 346             living[x][y] = 0;
 347
 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);
 352
 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) &&
 356                 ! living[x][y])
 357             {
 358                 board->cells[x][y].type = DVONN_CELL_EMPTY;
 359                 board->cells[x][y].height = 0;
 360             }
 361 }
 362
 363 int
 364 dvonn_board_move (dvonn_board_t *board,
 365                   int x1, int y1,
 366                   int x2, int y2,
 367                   char **error)
 368 {
 369     if (board->phase != DVONN_PHASE_MOVEMENT) {
 370         *error = "Cannot move outside of placement phase";
 371         return FALSE;
 372     }
 373
 374     if (! dvonn_board_move_legal (board, x1, y1, x2, y2, error))
 375         return FALSE;
 376
 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;
 380
 381     board->cells[x1][y1].type = DVONN_CELL_EMPTY;
 382     board->cells[x1][y1].height = 0;
 383     board->cells[x1][y1].contains_red = FALSE;
 384
 385     eliminate_disconnected_stacks (board);
 386
 387     dvonn_board_next_player (board);
 388
 389     return TRUE;
 390 }