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 }
  84
  85 dvonn_bool_t
  86 dvonn_board_cell_occupied (dvonn_board_t *board,
  87                            int x, int y)
  88 {
  89     if (x < 0 || x >= DVONN_BOARD_X_SIZE ||
  90         y < 0 || y >= DVONN_BOARD_Y_SIZE)
  91     {
  92         return FALSE;
  93     }
  94
  95     if (board->cells[x][y].type == DVONN_CELL_INVALID ||
  96         board->cells[x][y].type == DVONN_CELL_EMPTY)
  97     {
  98         return FALSE;
  99     }
 100
 101     return TRUE;
 102 }
 103
 104 dvonn_bool_t
 105 dvonn_board_cell_owned_by (dvonn_board_t *board,
 106                            int x, int y,
 107                            dvonn_player_t player)
 108 {
 109     if (! dvonn_board_cell_occupied (board, x, y))
 110         return FALSE;
 111
 112     /* Cast here to avoid compiler warning about mixing enum types in
 113      * a comparison. */
 114     return board->cells[x][y].type == (dvonn_cell_type_t) player;
 115 }
 116
 117 dvonn_bool_t
 118 dvonn_board_cell_surrounded (dvonn_board_t *board,
 119                              int x, int y)
 120 {
 121     int surround_count;
 122
 123     surround_count =
 124         dvonn_board_cell_occupied (board, x - 1, y) +
 125         dvonn_board_cell_occupied (board, x + 1, y) +
 126         dvonn_board_cell_occupied (board, x, y - 1) +
 127         dvonn_board_cell_occupied (board, x, y + 1) +
 128         dvonn_board_cell_occupied (board, x + 1, y - 1) +
 129         dvonn_board_cell_occupied (board, x - 1, y + 1);
 130
 131     return (surround_count == 6);
 132 }
 133
 134 static dvonn_bool_t
 135 dvonn_board_move_legal (dvonn_board_t *board,
 136                         int x1, int y1,
 137                         int x2, int y2,
 138                         char **error)
 139 {
 140     int distance;
 141
 142     if (x1 < 0 || x1 >= DVONN_BOARD_X_SIZE ||
 143         y1 < 0 || y1 >= DVONN_BOARD_Y_SIZE ||
 144         x2 < 0 || x2 >= DVONN_BOARD_X_SIZE ||
 145         y2 < 0 || y2 >= DVONN_BOARD_Y_SIZE)
 146     {
 147         *error = "Invalid coordinates (not on board)";
 148         return FALSE;
 149     }
 150
 151     if (board->cells[x1][y1].type == DVONN_CELL_INVALID ||
 152         board->cells[x2][y2].type == DVONN_CELL_INVALID)
 153     {
 154         *error = "Not a valid board space";
 155         return FALSE;
 156     }
 157
 158     if (board->cells[x1][y1].type == DVONN_CELL_EMPTY) {
 159         *error = "There are no pieces there to move";
 160         return FALSE;
 161     }
 162
 163     if (dvonn_board_cell_surrounded (board, x1, y1)) {
 164         *error = "You cannot move a piece that is surrounded";
 165         return FALSE;
 166     }
 167
 168     if (! dvonn_board_cell_owned_by (board, x1, y1, board->player)) {
 169         *error = "You cannot move your opponent's stack";
 170         return FALSE;
 171     }
 172
 173     if (board->cells[x2][y2].type == DVONN_CELL_EMPTY) {
 174         *error = "You cannot move to an empty space";
 175         return FALSE;
 176     }
 177
 178     /* Move must be in a straight line, which in our array is
 179      * horizontal, vertical, or one of the diagonals. */
 180     if (x2 == x1)
 181         distance = abs (y2 - y1);
 182     else if (y2 == y1)
 183         distance = abs (x2 - x1);
 184     else if ((x2 - x1) == - (y2 - y1))
 185         distance = abs (x2 - x1);
 186     else {
 187         *error = "Move is not in a straight line";
 188         return FALSE;
 189     }
 190
 191     if (distance != board->cells[x1][y1].height) {
 192         *error = "Move distance is not the same as stack height";
 193         return FALSE;
 194     }
 195
 196     return TRUE;
 197 }
 198
 199 static void
 200 dvonn_board_next_player (dvonn_board_t *board)
 201 {
 202     if (board->player == DVONN_PLAYER_BLACK)
 203         board->player = DVONN_PLAYER_WHITE;
 204     else
 205         board->player = DVONN_PLAYER_BLACK;
 206 }
 207
 208 int
 209 dvonn_board_pass (dvonn_board_t *board)
 210 {
 211     /* XXX: Should check here and only allow a pass if there are
 212      * no legal moves. */
 213
 214     dvonn_board_next_player (board);
 215
 216     return TRUE;
 217 }
 218
 219 int
 220 dvonn_board_place (dvonn_board_t *board,
 221                    int x, int y,
 222                    char **error)
 223 {
 224     if (board->phase != DVONN_PHASE_PLACEMENT) {
 225         *error = "Cannot place outside of placement phase";
 226         return FALSE;
 227     }
 228
 229     if (board->cells[x][y].type != DVONN_CELL_EMPTY) {
 230         *error = "Cannot place on an occupied space";
 231         return FALSE;
 232     }
 233
 234     if (board->moves < 3) {
 235         board->cells[x][y].type = DVONN_CELL_RED;
 236         board->cells[x][y].contains_red = TRUE;
 237     } else if (board->moves % 2) {
 238         board->cells[x][y].type = DVONN_CELL_BLACK;
 239     } else {
 240         board->cells[x][y].type = DVONN_CELL_WHITE;
 241     }
 242
 243     board->cells[x][y].height = 1;
 244
 245     board->moves++;
 246
 247     dvonn_board_next_player (board);
 248
 249     if (board->moves == 49) {
 250         board->phase = DVONN_PHASE_MOVEMENT;
 251         board->moves = 0;
 252         board->player = DVONN_PLAYER_WHITE;
 253     }
 254
 255     return TRUE;
 256 }
 257
 258 static void
 259 fill_living(dvonn_board_t *board,
 260             int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE],
 261             int x, int y)
 262 {
 263     if (dvonn_board_cell_occupied (board, x, y) && ! living[x][y])
 264     {
 265         living[x][y] = 1;
 266
 267         fill_living (board, living, x - 1, y);
 268         fill_living (board, living, x + 1, y);
 269         fill_living (board, living, x, y - 1);
 270         fill_living (board, living, x, y + 1);
 271         fill_living (board, living, x + 1, y - 1);
 272         fill_living (board, living, x - 1, y + 1);
 273     }
 274 }
 275
 276 static void
 277 eliminate_disconnected_stacks (dvonn_board_t *board)
 278 {
 279     int x, y;
 280     int living[DVONN_BOARD_X_SIZE][DVONN_BOARD_Y_SIZE];
 281
 282     for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
 283         for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
 284             living[x][y] = 0;
 285
 286     for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
 287         for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
 288             if (board->cells[x][y].contains_red)
 289                 fill_living (board, living, x, y);
 290
 291     for (x = 0; x < DVONN_BOARD_X_SIZE; x++)
 292         for (y = 0; y < DVONN_BOARD_Y_SIZE; y++)
 293             if (dvonn_board_cell_occupied (board, x, y) &&
 294                 ! living[x][y])
 295             {
 296                 board->cells[x][y].type = DVONN_CELL_EMPTY;
 297                 board->cells[x][y].height = 0;
 298             }
 299 }
 300
 301 int
 302 dvonn_board_move (dvonn_board_t *board,
 303                   int x1, int y1,
 304                   int x2, int y2,
 305                   char **error)
 306 {
 307     if (board->phase != DVONN_PHASE_MOVEMENT) {
 308         *error = "Cannot move outside of placement phase";
 309         return FALSE;
 310     }
 311
 312     if (! dvonn_board_move_legal (board, x1, y1, x2, y2, error))
 313         return FALSE;
 314
 315     board->cells[x2][y2].height += board->cells[x1][y1].height;
 316     board->cells[x2][y2].type = board->cells[x1][y1].type;
 317     board->cells[x2][y2].contains_red |= board->cells[x1][y1].contains_red;
 318
 319     board->cells[x1][y1].type = DVONN_CELL_EMPTY;
 320     board->cells[x1][y1].height = 0;
 321     board->cells[x1][y1].contains_red = FALSE;
 322
 323     eliminate_disconnected_stacks (board);
 324
 325     dvonn_board_next_player (board);
 326
 327     return TRUE;
 328 }