apps/plugins/goban/board.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Copyright (C) 2007-2009 Joshua Simmons <mud at majidejima dot com>
  11  *
  12  * This program is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU General Public License
  14  * as published by the Free Software Foundation; either version 2
  15  * of the License, or (at your option) any later version.
  16  *
  17  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  18  * KIND, either express or implied.
  19  *
  20  ****************************************************************************/
  21
  22 #include "goban.h"
  23 #include "board.h"
  24 #include "display.h"
  25 #include "types.h"
  26 #include "game.h"
  27 #include "util.h"
  28
  29 #include "plugin.h"
  30
  31 unsigned int board_width = MAX_BOARD_SIZE;
  32 unsigned int board_height = MAX_BOARD_SIZE;
  33
  34 /* Board has 'invalid' markers around each border */
  35 unsigned char board_data[(MAX_BOARD_SIZE + 2) * (MAX_BOARD_SIZE + 2)];
  36 int white_captures = 0;
  37 int black_captures = 0;
  38
  39 uint8_t board_marks[(MAX_BOARD_SIZE + 2) * (MAX_BOARD_SIZE + 2)];
  40 uint8_t current_mark = 255;
  41
  42 /* there can't be any changes off of the board, so no need to add the
  43    borders */
  44 uint8_t board_changes[MAX_BOARD_SIZE * MAX_BOARD_SIZE];
  45
  46 unsigned short ko_pos = INVALID_POS;
  47
  48 /* forward declarations */
  49 static void setup_marks (void);
  50 static void make_mark (unsigned short pos);
  51 static int get_liberties_helper (unsigned short pos, unsigned char orig_color);
  52 static int flood_fill_helper (unsigned short pos, unsigned char orig_color,
  53                               unsigned char color);
  54
  55
  56 /* these aren't "board marks" in the marks on the SGF sense, they are used
  57    internally to mark already visited points and the like (such as when
  58    doing liberty counting for groups)
  59
  60    We avoid having to clear the entire array every time by storing the
  61    "current_mark" number and defining marked as "== current_mark".  We
  62    still need to clear the whole array once per "cycle" though, or we'd get
  63    false positives sometimes
  64    */
  65 static void
  66 setup_marks (void)
  67 {
  68     unsigned int x, y;
  69
  70     current_mark++;
  71
  72     if (current_mark == 0)
  73     {
  74         current_mark++;
  75
  76         for (y = 0; y < board_height; ++y)
  77         {
  78             for (x = 0; x < board_width; ++x)
  79             {
  80                 board_marks[POS (x, y)] = 0;
  81             }
  82         }
  83     }
  84 }
  85
  86 static void
  87 make_mark (unsigned short pos)
  88 {
  89     board_marks[pos] = current_mark;
  90 }
  91
  92 static bool
  93 is_marked (unsigned short pos)
  94 {
  95     return board_marks[pos] == current_mark;
  96 }
  97
  98 void
  99 clear_board (void)
 100 {
 101     unsigned int x, y;
 102
 103     /* for the borders */
 104     rb->memset(board_data, INVALID, sizeof(board_data));
 105
 106     /* now make the actual board part */
 107     for (y = 0; y < board_height; ++y)
 108     {
 109         for (x = 0; x < board_width; ++x)
 110         {
 111             board_data[POS (x, y)] = EMPTY;
 112         }
 113     }
 114
 115     white_captures = 0;
 116     black_captures = 0;
 117
 118     ko_pos = INVALID_POS;
 119 }
 120
 121 bool
 122 set_size_board (int width, int height)
 123 {
 124     if (width < MIN_BOARD_SIZE || width > MAX_BOARD_SIZE ||
 125         height < MIN_BOARD_SIZE || height > MAX_BOARD_SIZE)
 126     {
 127         return false;
 128     }
 129     else
 130     {
 131         board_width = width;
 132         board_height = height;
 133         setup_display ();
 134         return true;
 135     }
 136 }
 137
 138 unsigned char
 139 get_point_board (unsigned short pos)
 140 {
 141     return board_data[pos];
 142 }
 143
 144 void
 145 set_point_board (unsigned short pos, unsigned char color)
 146 {
 147     board_data[pos] = color;
 148 }
 149
 150 bool
 151 on_board (unsigned short pos)
 152 {
 153     if (pos < POS (0, 0) ||
 154         pos > POS (board_width - 1, board_height - 1) ||
 155         get_point_board (pos) == INVALID)
 156     {
 157         return false;
 158     }
 159     else
 160     {
 161         return true;
 162     }
 163 }
 164
 165 int
 166 get_liberties_board (unsigned short pos)
 167 {
 168     if (!on_board (pos) || get_point_board (pos) == EMPTY)
 169     {
 170         return -1;
 171     }
 172
 173     setup_marks ();
 174
 175     int ret_val = 0;
 176     unsigned char orig_color = get_point_board (pos);
 177
 178     empty_stack (&parse_stack);
 179     push_pos_stack (&parse_stack, pos);
 180
 181     /* Since we only ever test for liberties in order to determine
 182        captures and the like, there's no reason to count any liberties
 183        higher than 2 (we sometimes need to know if something has 1 liberty
 184        for dealing with ko) */
 185     while (pop_pos_stack (&parse_stack, &pos) && ret_val < 2)
 186     {
 187         ret_val += get_liberties_helper (NORTH (pos), orig_color);
 188         ret_val += get_liberties_helper (SOUTH (pos), orig_color);
 189         ret_val += get_liberties_helper (EAST (pos), orig_color);
 190         ret_val += get_liberties_helper (WEST (pos), orig_color);
 191     }
 192
 193     /* if there's more than two liberties, the stack isn't empty, so empty
 194        it */
 195     empty_stack (&parse_stack);
 196
 197     return ret_val;
 198 }
 199
 200 static int
 201 get_liberties_helper (unsigned short pos, unsigned char orig_color)
 202 {
 203     if (on_board (pos) &&
 204         get_point_board (pos) != OTHER (orig_color) && !is_marked (pos))
 205     {
 206         make_mark (pos);
 207
 208         if (get_point_board (pos) == EMPTY)
 209         {
 210             return 1;
 211         }
 212         else
 213         {
 214             push_pos_stack (&parse_stack, pos);
 215         }
 216     }
 217
 218     return 0;
 219 }
 220
 221
 222 int
 223 flood_fill_board (unsigned short pos, unsigned char color)
 224 {
 225     if (!on_board (pos) || get_point_board (pos) == color)
 226     {
 227         return 0;
 228     }
 229
 230     empty_stack (&parse_stack);
 231
 232     int ret_val = 0;
 233
 234     unsigned char orig_color = get_point_board (pos);
 235
 236     set_point_board (pos, color);
 237     ++ret_val;
 238     push_pos_stack (&parse_stack, pos);
 239
 240     while (pop_pos_stack (&parse_stack, &pos))
 241     {
 242         ret_val += flood_fill_helper (NORTH (pos), orig_color, color);
 243         ret_val += flood_fill_helper (SOUTH (pos), orig_color, color);
 244         ret_val += flood_fill_helper (EAST (pos), orig_color, color);
 245         ret_val += flood_fill_helper (WEST (pos), orig_color, color);
 246     }
 247
 248     return ret_val;
 249 }
 250
 251
 252 static int
 253 flood_fill_helper (unsigned short pos, unsigned char orig_color,
 254                    unsigned char color)
 255 {
 256     if (on_board (pos) && get_point_board (pos) == orig_color)
 257     {
 258         set_point_board (pos, color);
 259         push_pos_stack (&parse_stack, pos);
 260         return 1;
 261     }
 262
 263     return 0;
 264 }
 265
 266 bool
 267 legal_move_board (unsigned short pos, unsigned char color, bool allow_suicide)
 268 {
 269     /* you can always pass */
 270     if (pos == PASS_POS)
 271     {
 272         return true;
 273     }
 274
 275     if (!on_board (pos) || (color != BLACK && color != WHITE))
 276     {
 277         return false;
 278     }
 279
 280     if (pos == ko_pos && color == current_player)
 281     {
 282         return false;
 283     }
 284
 285     if (get_point_board (pos) != EMPTY)
 286     {
 287         return false;
 288     }
 289
 290     /* don't need to save the current state, because it's always empty
 291        since we tested for that above */
 292     set_point_board (pos, color);
 293
 294     /* if we have liberties, it can't be illegal */
 295     if (get_liberties_board (pos) > 0 ||
 296         /* if we can capture something, it can't be illegal */
 297         (get_point_board (NORTH (pos)) == OTHER (color) &&
 298          !get_liberties_board (NORTH (pos))) ||
 299         (get_point_board (SOUTH (pos)) == OTHER (color) &&
 300          !get_liberties_board (SOUTH (pos))) ||
 301         (get_point_board (EAST (pos)) == OTHER (color) &&
 302          !get_liberties_board (EAST (pos))) ||
 303         (get_point_board (WEST (pos)) == OTHER (color) &&
 304          !get_liberties_board (WEST (pos))) ||
 305         /* if we're allowed to suicide, only multi-stone suicide is legal
 306            (no ruleset allows single-stone suicide that I know of) */
 307         (allow_suicide && (get_point_board (NORTH (pos)) == color ||
 308                            get_point_board (SOUTH (pos)) == color ||
 309                            get_point_board (EAST (pos)) == color ||
 310                            get_point_board (WEST (pos)) == color)))
 311     {
 312         /* undo our previous set */
 313         set_point_board (pos, EMPTY);
 314         return true;
 315     }
 316     else
 317     {
 318         /* undo our previous set */
 319         set_point_board (pos, EMPTY);
 320         return false;
 321     }
 322 }
 323
 324
 325 unsigned short
 326 WRAP (unsigned short pos)
 327 {
 328     int x, y;
 329     if (on_board (pos))
 330     {
 331         return pos;
 332     }
 333     else
 334     {
 335         x = I (pos);
 336         y = J (pos);
 337
 338         if (x < 0)
 339         {
 340             x = board_width - 1;
 341         }
 342         else if ((unsigned int) x >= board_width)
 343         {
 344             x = 0;
 345         }
 346
 347         if (y < 0)
 348         {
 349             y = board_height - 1;
 350         }
 351         else if ((unsigned int) y >= board_height)
 352         {
 353             y = 0;
 354         }
 355         return POS (x, y);
 356     }
 357 }