| 1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
| 2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * |
| 3 | * http://www.gnu.org/software/gnugo/ for more information. * |
| 4 | * * |
| 5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * |
| 6 | * 2008 and 2009 by the Free Software Foundation. * |
| 7 | * * |
| 8 | * This program is free software; you can redistribute it and/or * |
| 9 | * modify it under the terms of the GNU General Public License as * |
| 10 | * published by the Free Software Foundation - version 3 or * |
| 11 | * (at your option) any later version. * |
| 12 | * * |
| 13 | * This program is distributed in the hope that it will be useful, * |
| 14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * |
| 15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * |
| 16 | * GNU General Public License in file COPYING for more details. * |
| 17 | * * |
| 18 | * You should have received a copy of the GNU General Public * |
| 19 | * License along with this program; if not, write to the Free * |
| 20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * |
| 21 | * Boston, MA 02111, USA. * |
| 22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ |
| 23 | |
| 24 | #include "gnugo.h" |
| 25 | |
| 26 | #include <stdio.h> |
| 27 | #include <string.h> |
| 28 | #include <math.h> |
| 29 | |
| 30 | #include "liberty.h" |
| 31 | #include "gg_utils.h" |
| 32 | |
| 33 | /* Forward declarations */ |
| 34 | static int goal_dist(int pos, signed char goal[BOARDMAX]); |
| 35 | static int compare_angles(const void *a, const void *b); |
| 36 | static void show_surround_map(signed char mf[BOARDMAX], |
| 37 | signed char mn[BOARDMAX]); |
| 38 | |
| 39 | /* Globals */ |
| 40 | static int gg; /* stores the gravity center of the goal */ |
| 41 | |
| 42 | |
| 43 | /* Returns true if a dragon is enclosed within the convex hull of |
| 44 | * its hostile neighbor dragons. This is an indication that the dragon is |
| 45 | * in danger. Stones on the second and first lines are not tested. |
| 46 | * |
| 47 | * Normally NULL will be passed to the parameter apos. It can be |
| 48 | * an empty board location. If apos is non NULL it is marked and |
| 49 | * added to the the hull. Thus we can ask if adding a single stone |
| 50 | * to the board surrounds the dragon. |
| 51 | * |
| 52 | * A CORNER is a vertex of the polygon which comprises this convex |
| 53 | * hull. The algorithm proceeds by first finding the sequence of |
| 54 | * corners on the left side of the polyhedron, then the sequence |
| 55 | * of corners on the right side. |
| 56 | * |
| 57 | * The hull is marked in the array mn with the number 1. A slight |
| 58 | * expansion is marked with the number 2. Return code is SURROUNDED if |
| 59 | * the friendly dragon lies within the area marked 1, |
| 60 | * WEAKLY_SURROUNDED if it lies in the slightly larger area marked 1 |
| 61 | * and 2, and 0 otherwise. |
| 62 | * |
| 63 | * The notion of weak surroundedness seems to be much less indicative |
| 64 | * of a dragon's immanent danger than surroundedness. |
| 65 | * |
| 66 | * An exception: if the larger area contains any stone of a different |
| 67 | * friendly dragon (which is not DEAD) the return code is 0, unless |
| 68 | * that allied dragon is ENTIRELY contained within the hull. |
| 69 | * |
| 70 | * Another exception: an ikken tobi (one space jump) is generally not |
| 71 | * a connection but in practice may be almost as good. If there is an |
| 72 | * ikken tobi out of the hull, then the dragon is not surrounded. |
| 73 | * |
| 74 | * If the parameter showboard is 1, the figure is drawn. If showboard |
| 75 | * is 2, the figure is only drawn if the region is surrounded. |
| 76 | * |
| 77 | * If (apos) is NULL, the result is saved in the surround_data cache. |
| 78 | * The assumption is that the function will only be called once |
| 79 | * with (apos) null, during make_dragons; thereafter the surroundedness |
| 80 | * will be accessed using the function is_surrounded(). |
| 81 | * |
| 82 | * If *surround_size is not a NULL pointer, then surround_size |
| 83 | * returns the size of the surroundings. |
| 84 | */ |
| 85 | |
| 86 | int |
| 87 | compute_surroundings(int pos, int apos, int showboard, int *surround_size) |
| 88 | { |
| 89 | int i, j; |
| 90 | int m, n; |
| 91 | int k; |
| 92 | int dpos; |
| 93 | int surrounded; |
| 94 | |
| 95 | int left_corner[MAX_BOARD]; |
| 96 | int right_corner[MAX_BOARD]; |
| 97 | int corner[BOARDMAX]; |
| 98 | int left_corners = 0, right_corners = 0; |
| 99 | int corners = 0; |
| 100 | int top_row, bottom_row; |
| 101 | int color = board[pos]; |
| 102 | int other = OTHER_COLOR(color); |
| 103 | int gi = 0; |
| 104 | int gj = 0; |
| 105 | int stones = 0; |
| 106 | int found_some; |
| 107 | |
| 108 | signed char mf[BOARDMAX]; /* friendly dragon */ |
| 109 | signed char mn[BOARDMAX]; /* neighbor dragons */ |
| 110 | int sd[BOARDMAX]; /* distances to the goal */ |
| 111 | |
| 112 | if (DRAGON2(pos).hostile_neighbors == 0) |
| 113 | return(0); |
| 114 | |
| 115 | memset(mf, 0, sizeof(mf)); |
| 116 | memset(mn, 0, sizeof(mn)); |
| 117 | memset(sd, 0, sizeof(sd)); |
| 118 | |
| 119 | mark_dragon(pos, mf, 1); |
| 120 | |
| 121 | /* mark hostile neighbors */ |
| 122 | |
| 123 | for (k = 0; k < DRAGON2(pos).neighbors; k++) { |
| 124 | int nd = DRAGON(DRAGON2(pos).adjacent[k]).origin; |
| 125 | |
| 126 | if (board[nd] != color) { |
| 127 | if (0) |
| 128 | gprintf("neighbor: %1m\n", nd); |
| 129 | mark_dragon(nd, mn, 1); |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | /* descend markings from stones lying on the 2nd and third lines */ |
| 134 | |
| 135 | for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) |
| 136 | if (ON_BOARD(dpos) && mn[dpos]) { |
| 137 | for (k = 0; k < 4; k++) { |
| 138 | int d = delta[k]; |
| 139 | if (!ON_BOARD(dpos + d)) |
| 140 | continue; |
| 141 | if (!ON_BOARD(dpos + 2*d)) { |
| 142 | if (board[dpos + d] == EMPTY) |
| 143 | mn[dpos + d] = 1; |
| 144 | } |
| 145 | else if (!ON_BOARD(dpos + 3*d)) { |
| 146 | if (board[dpos + d] == EMPTY |
| 147 | && board[dpos + 2*d] == EMPTY) |
| 148 | mn[dpos + 2*d] = 1; |
| 149 | } |
| 150 | } |
| 151 | } |
| 152 | |
| 153 | /* compute minimum distances to the goal */ |
| 154 | |
| 155 | for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) |
| 156 | if (ON_BOARD(dpos) && mn[dpos]) |
| 157 | sd[dpos] = goal_dist(dpos, mf); |
| 158 | |
| 159 | /* revise markings */ |
| 160 | |
| 161 | do { |
| 162 | found_some = 0; |
| 163 | for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) |
| 164 | if (ON_BOARD(dpos) && mn[dpos] && sd[dpos] > 8) { |
| 165 | /* discard markings if we can find 2 stones |
| 166 | * that verify : |
| 167 | * - it is closer to the goal than we are |
| 168 | * - it is closer to us than the goal is |
| 169 | * - they are closer to each other than we are to the goal |
| 170 | */ |
| 171 | for (i = BOARDMIN; i < BOARDMAX; i++) |
| 172 | if (ON_BOARD(i) && mn[i] && i != dpos |
| 173 | && sd[i] < sd[dpos] |
| 174 | && square_dist(i, dpos) < sd[dpos]) { |
| 175 | for (j = i + 1; j < BOARDMAX; j++) |
| 176 | if (ON_BOARD(j) && mn[j] && j != dpos |
| 177 | && sd[j] < sd[dpos] |
| 178 | && square_dist(j, dpos) < sd[dpos] |
| 179 | && square_dist(i, j) < sd[dpos]) { |
| 180 | mn[dpos] = 0; |
| 181 | found_some = 1; |
| 182 | break; |
| 183 | } |
| 184 | if (mn[dpos] == 0) |
| 185 | break; |
| 186 | } |
| 187 | } |
| 188 | } while (found_some); |
| 189 | |
| 190 | /* prepare corner array */ |
| 191 | |
| 192 | for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) |
| 193 | if (ON_BOARD(dpos) && mn[dpos]) |
| 194 | corner[corners++] = dpos; |
| 195 | |
| 196 | /* compute gravity center of the goal */ |
| 197 | |
| 198 | for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) |
| 199 | if (ON_BOARD(dpos) && mf[dpos]) { |
| 200 | gi += I(dpos); |
| 201 | gj += J(dpos); |
| 202 | stones++; |
| 203 | } |
| 204 | gi /= stones; |
| 205 | gj /= stones; |
| 206 | gg = POS(gi, gj); |
| 207 | |
| 208 | /* sort the corner array */ |
| 209 | |
| 210 | gg_sort(corner, corners, sizeof(int), compare_angles); |
| 211 | |
| 212 | /* if apos is not NO_MOVE, mark it. */ |
| 213 | |
| 214 | if (apos != NO_MOVE) { |
| 215 | ASSERT_ON_BOARD1(apos); |
| 216 | mn[apos] = 1; |
| 217 | } |
| 218 | |
| 219 | if (showboard == 1) { |
| 220 | show_surround_map(mf, mn); |
| 221 | } |
| 222 | |
| 223 | /* find top row of surrounding polyhedron */ |
| 224 | |
| 225 | top_row = -1; |
| 226 | for (m = 0; m < board_size; m++) { |
| 227 | if (top_row != -1) |
| 228 | break; |
| 229 | for (n = 0; n < board_size; n++) |
| 230 | if (mn[POS(m, n)]) { |
| 231 | left_corner[0] = POS(m, n); |
| 232 | top_row = m; |
| 233 | break; |
| 234 | } |
| 235 | } |
| 236 | |
| 237 | /* find bottom row */ |
| 238 | |
| 239 | bottom_row = -1; |
| 240 | for (m = board_size - 1; m >= 0; m--) { |
| 241 | if (bottom_row != -1) |
| 242 | break; |
| 243 | for (n = 0; n < board_size; n++) |
| 244 | if (mn[POS(m, n)]) { |
| 245 | bottom_row = m; |
| 246 | break; |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | /* find the corners on the left side */ |
| 251 | |
| 252 | for (left_corners = 1; I(left_corner[left_corners-1]) < bottom_row; |
| 253 | left_corners++) { |
| 254 | int best_found = 0; |
| 255 | float best_slope = 0.; |
| 256 | int m = I(left_corner[left_corners-1]); |
| 257 | int n = J(left_corner[left_corners-1]); |
| 258 | |
| 259 | for (i = m + 1; i <= bottom_row; i++) |
| 260 | for (j = 0; j < board_size; j++) |
| 261 | if (mn[POS(i, j)]) { |
| 262 | float slope = ((float) (j - n))/((float) (i - m)); |
| 263 | if (0) |
| 264 | gprintf("(left) at %m, last %m, slope=%f\n", i, j, m, n, slope); |
| 265 | |
| 266 | if (!best_found || slope < best_slope) { |
| 267 | best_found = POS(i, j); |
| 268 | best_slope = slope; |
| 269 | } |
| 270 | } |
| 271 | ASSERT_ON_BOARD1(best_found); |
| 272 | left_corner[left_corners] = best_found; |
| 273 | } |
| 274 | |
| 275 | for (n = board_size-1; n >= 0; n--) |
| 276 | if (mn[POS(top_row, n)]) { |
| 277 | right_corner[0] = POS(top_row, n); |
| 278 | break; |
| 279 | } |
| 280 | |
| 281 | /* find the corners on the right side */ |
| 282 | |
| 283 | for (right_corners = 1; I(right_corner[right_corners-1]) < bottom_row; |
| 284 | right_corners++) { |
| 285 | int best_found = 0; |
| 286 | float best_slope = 0.; |
| 287 | int m = I(right_corner[right_corners-1]); |
| 288 | int n = J(right_corner[right_corners-1]); |
| 289 | |
| 290 | for (i = m + 1; i <= bottom_row; i++) { |
| 291 | for (j = board_size - 1; j >= 0; j--) { |
| 292 | if (mn[POS(i, j)]) { |
| 293 | float slope = ((float) (j - n))/((float) (i - m)); |
| 294 | if (0) |
| 295 | gprintf("(right) at %m, last %m, slope=%f\n", i, j, m, n, slope); |
| 296 | if (!best_found || slope > best_slope) { |
| 297 | best_found = POS(i, j); |
| 298 | best_slope = slope; |
| 299 | } |
| 300 | } |
| 301 | } |
| 302 | } |
| 303 | ASSERT_ON_BOARD1(best_found); |
| 304 | right_corner[right_corners] = best_found; |
| 305 | } |
| 306 | |
| 307 | if (0) { |
| 308 | for (k = 0; k < left_corners; k++) |
| 309 | gprintf("left corner %d: %1m\n", k, left_corner[k]); |
| 310 | |
| 311 | for (k = 0; k < right_corners; k++) |
| 312 | gprintf("right corner %d: %1m\n", k, right_corner[k]); |
| 313 | } |
| 314 | |
| 315 | /* Now mark the interior of the convex hull */ |
| 316 | |
| 317 | for (n = J(left_corner[0]); n <= J(right_corner[0]); n++) |
| 318 | mn[POS(top_row, n)] = 1; |
| 319 | |
| 320 | for (n = J(left_corner[left_corners-1]); |
| 321 | n <= J(right_corner[right_corners-1]); n++) |
| 322 | mn[POS(bottom_row, n)] = 1; |
| 323 | |
| 324 | for (m = top_row+1; m < bottom_row; m++) { |
| 325 | int left_boundary = -1, right_boundary = -1; |
| 326 | for (k = 1; k < left_corners; k++) { |
| 327 | if (I(left_corner[k]) > m) { |
| 328 | float ti = I(left_corner[k-1]); |
| 329 | float tj = J(left_corner[k-1]); |
| 330 | float bi = I(left_corner[k]); |
| 331 | float bj = J(left_corner[k]); |
| 332 | |
| 333 | if (0) |
| 334 | gprintf("(left) %d: %1m %1m\n", |
| 335 | m, left_corner[k-1], left_corner[k]); |
| 336 | /* left edge in this row is on segment (ti,tj) -> (bi, bj) */ |
| 337 | |
| 338 | /* FIXME: Rewrite this to avoid floating point arithmetic */ |
| 339 | left_boundary = ceil(tj + (m - ti) * (bj - tj) / (bi - ti)); |
| 340 | break; |
| 341 | } |
| 342 | } |
| 343 | |
| 344 | for (k = 1; k < right_corners; k++) { |
| 345 | if (I(right_corner[k]) > m) { |
| 346 | float ti = I(right_corner[k-1]); |
| 347 | float tj = J(right_corner[k-1]); |
| 348 | float bi = I(right_corner[k]); |
| 349 | float bj = J(right_corner[k]); |
| 350 | |
| 351 | if (0) |
| 352 | gprintf("(right) %d: %1m %1m\n", |
| 353 | m, right_corner[k-1], right_corner[k]); |
| 354 | |
| 355 | /* FIXME: Rewrite this to avoid floating point arithmetic */ |
| 356 | right_boundary = floor(tj + (m - ti) * (bj - tj) / (bi - ti)); |
| 357 | break; |
| 358 | } |
| 359 | } |
| 360 | |
| 361 | for (n = left_boundary; n <= right_boundary; n++) |
| 362 | mn[POS(m, n)] = 1; |
| 363 | } |
| 364 | |
| 365 | /* mark the expanded region */ |
| 366 | |
| 367 | for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) |
| 368 | if (ON_BOARD(dpos) && mn[dpos] == 1) |
| 369 | for (k = 0; k < 4; k++) |
| 370 | if (ON_BOARD(dpos + delta[k]) && !mn[dpos + delta[k]]) |
| 371 | mn[dpos + delta[k]] = 2; |
| 372 | |
| 373 | /* Mark allied dragons that intersect the (unexpanded) hull. |
| 374 | * These must all lie entirely within the hull for the |
| 375 | * dragon to be considered surrounded. |
| 376 | * |
| 377 | * Only neighbor dragons are considered since dragons that |
| 378 | * are not neighbors are less likely to be helpful. |
| 379 | */ |
| 380 | |
| 381 | for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) { |
| 382 | int mpos; |
| 383 | if (ON_BOARD(dpos) |
| 384 | && mn[dpos] == 1 |
| 385 | && board[dpos] == color |
| 386 | && are_neighbor_dragons(pos, dpos) |
| 387 | && !mf[dpos]) { |
| 388 | |
| 389 | for (mpos = BOARDMIN; mpos < BOARDMAX; mpos++) |
| 390 | if (ON_BOARD(mpos) && is_same_dragon(mpos, dpos)) |
| 391 | mf[mpos] = 2; |
| 392 | } |
| 393 | /* A special case |
| 394 | * |
| 395 | * . X X . |
| 396 | * X O . X |
| 397 | * X . O O |
| 398 | * . O . . |
| 399 | * |
| 400 | * The O stone hasn't been amalgamated and the surround computations |
| 401 | * might think this single stone dragon is surrounded, which in turn |
| 402 | * can generate overvaluation of moves around this stone. |
| 403 | * Consequently, we allow inclusion of the stones at kosumi distance |
| 404 | * in the mf (friendly) array. |
| 405 | */ |
| 406 | if (ON_BOARD(dpos) |
| 407 | && mn[dpos] == 2 |
| 408 | && board[dpos] == color |
| 409 | && are_neighbor_dragons(pos, dpos) |
| 410 | && !mf[dpos]) { |
| 411 | for (k = 4; k < 8; k++) |
| 412 | if (ON_BOARD(dpos + delta[k]) && board[dpos + delta[k]] == color |
| 413 | && mn[dpos + delta[k]] == 1 |
| 414 | && board[dpos + delta[k-4]] == EMPTY |
| 415 | && board[dpos + delta[(k-3)%4]] == EMPTY) { |
| 416 | for (mpos = BOARDMIN; mpos < BOARDMAX; mpos++) |
| 417 | if (ON_BOARD(mpos) && is_same_dragon(mpos, dpos)) |
| 418 | mf[mpos] = 2; |
| 419 | } |
| 420 | } |
| 421 | } |
| 422 | |
| 423 | /* determine the surround status of the dragon */ |
| 424 | |
| 425 | surrounded = SURROUNDED; |
| 426 | |
| 427 | /* Compute the maximum surround status awarded |
| 428 | * If distances between enclosing stones are large, reduce to |
| 429 | * WEAKLY_SURROUNDED. If (really) too large, then reduce to 0 |
| 430 | * FIXME: constants chosen completely ad hoc. Possibly better tunings |
| 431 | * can be found. |
| 432 | */ |
| 433 | |
| 434 | for (k = 0; k < corners - 1; k++) { |
| 435 | if (is_edge_vertex(corner[k]) |
| 436 | && is_edge_vertex(corner[k+1])) |
| 437 | continue; |
| 438 | if (square_dist(corner[k], corner[k+1]) > 60) { |
| 439 | surrounded = 0; |
| 440 | break; |
| 441 | } |
| 442 | else if (square_dist(corner[k], corner[k+1]) > 27) |
| 443 | surrounded = WEAKLY_SURROUNDED; |
| 444 | } |
| 445 | if (surrounded |
| 446 | && (!is_edge_vertex(corner[0]) |
| 447 | || !is_edge_vertex(corner[corners-1]))) { |
| 448 | if (square_dist(corner[0], corner[corners-1]) > 60) |
| 449 | surrounded = 0; |
| 450 | else if (square_dist(corner[0], corner[corners-1]) > 27) |
| 451 | surrounded = WEAKLY_SURROUNDED; |
| 452 | } |
| 453 | |
| 454 | if (surrounded) |
| 455 | for (dpos = BOARDMIN; dpos < BOARDMAX; dpos++) |
| 456 | if (mf[dpos]) { |
| 457 | if (mn[dpos] == 0) { |
| 458 | surrounded = 0; |
| 459 | break; |
| 460 | } |
| 461 | else if (mn[dpos] == 2) |
| 462 | surrounded = WEAKLY_SURROUNDED; |
| 463 | } |
| 464 | |
| 465 | /* revise the status for single stone dragons. */ |
| 466 | |
| 467 | if (stones == 1 |
| 468 | && surrounded == WEAKLY_SURROUNDED |
| 469 | && mn[pos] == 2) |
| 470 | surrounded = 0; |
| 471 | |
| 472 | /* revise the status if an ikken tobi jumps out. */ |
| 473 | |
| 474 | if (surrounded) { |
| 475 | for (dpos = BOARDMIN; dpos < BOARDMAX && surrounded; dpos++) { |
| 476 | if (!ON_BOARD(dpos) || !mf[dpos]) |
| 477 | continue; |
| 478 | |
| 479 | for (k = 0; k < 4; k++) { |
| 480 | int up = delta[k]; |
| 481 | int right = delta[(k + 1) % 4]; |
| 482 | if (board[dpos + up] == EMPTY |
| 483 | && board[dpos + 2*up] == color |
| 484 | && mn[dpos + 2*up] != 1 |
| 485 | && ON_BOARD(dpos + up + right) |
| 486 | && board[dpos + up + right] != other |
| 487 | && ON_BOARD(dpos + up - right) |
| 488 | && board[dpos + up - right] != other) { |
| 489 | surrounded = 0; |
| 490 | break; |
| 491 | } |
| 492 | } |
| 493 | } |
| 494 | } |
| 495 | |
| 496 | if (showboard == 1 || (showboard == 2 && surrounded)) { |
| 497 | show_surround_map(mf, mn); |
| 498 | } |
| 499 | |
| 500 | if (!apos && surrounded && surround_pointer < MAX_SURROUND) { |
| 501 | memcpy(surroundings[surround_pointer].surround_map, mn, sizeof(mn)); |
| 502 | surroundings[surround_pointer].dragon_number = dragon[pos].id; |
| 503 | surround_pointer++; |
| 504 | } |
| 505 | |
| 506 | if (surround_size) { |
| 507 | int pos; |
| 508 | |
| 509 | *surround_size = 0; |
| 510 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) |
| 511 | if (ON_BOARD(pos) && mn[pos] == 1) |
| 512 | (*surround_size)++; |
| 513 | } |
| 514 | |
| 515 | return surrounded; |
| 516 | } |
| 517 | |
| 518 | |
| 519 | /* Computes the minimum distance to the goal |
| 520 | */ |
| 521 | |
| 522 | static int |
| 523 | goal_dist(int pos, signed char goal[BOARDMAX]) |
| 524 | { |
| 525 | int dist = 10000; |
| 526 | int ii; |
| 527 | |
| 528 | for (ii = BOARDMIN; ii < BOARDMAX; ii++) |
| 529 | if (ON_BOARD(ii) && goal[ii]) |
| 530 | dist = gg_min(dist, square_dist(ii, pos)); |
| 531 | |
| 532 | return dist; |
| 533 | } |
| 534 | |
| 535 | /* Compares angles. Chosen convention: |
| 536 | * - SOUTH is "lowest" |
| 537 | * - ascending order is done clock-wise (WEST, NORTH, EAST) |
| 538 | */ |
| 539 | static int |
| 540 | compare_angles(const void *a, const void *b) |
| 541 | { |
| 542 | int aa = *((const int *)a); |
| 543 | int bb = *((const int *)b); |
| 544 | |
| 545 | int di_a = I(aa) - I(gg); |
| 546 | int dj_a = J(aa) - J(gg); |
| 547 | int di_b = I(bb) - I(gg); |
| 548 | int dj_b = J(bb) - J(gg); |
| 549 | |
| 550 | float sin_a, sin_b; |
| 551 | |
| 552 | if (aa == gg) |
| 553 | return 1; |
| 554 | if (bb == gg) |
| 555 | return -1; |
| 556 | |
| 557 | if (dj_a == 0) { |
| 558 | if (di_a > 0) { |
| 559 | if (dj_b != 0 || di_b <= 0) |
| 560 | return -1; |
| 561 | return 0; |
| 562 | } |
| 563 | else { |
| 564 | if (dj_b > 0) |
| 565 | return -1; |
| 566 | else if (dj_b < 0 || di_b > 0) |
| 567 | return 1; |
| 568 | else |
| 569 | return 0; |
| 570 | } |
| 571 | } |
| 572 | |
| 573 | sin_a = (float)di_a / sqrt(di_a*di_a + dj_a*dj_a); |
| 574 | sin_b = (float)di_b / sqrt(di_b*di_b + dj_b*dj_b); |
| 575 | |
| 576 | if (dj_a > 0) { |
| 577 | if (dj_b <= 0) |
| 578 | return 1; |
| 579 | if (sin_a > sin_b) |
| 580 | return 1; |
| 581 | else if (sin_a < sin_b) |
| 582 | return -1; |
| 583 | else |
| 584 | return 0; |
| 585 | } |
| 586 | else { /* if (dj_a < 0) */ |
| 587 | if (dj_b > 0) |
| 588 | return -1; |
| 589 | if (sin_a < sin_b) |
| 590 | return 1; |
| 591 | else if (sin_a > sin_b) |
| 592 | return -1; |
| 593 | else |
| 594 | return 0; |
| 595 | } |
| 596 | } |
| 597 | |
| 598 | |
| 599 | static void |
| 600 | show_surround_map(signed char mf[BOARDMAX], signed char mn[BOARDMAX]) |
| 601 | { |
| 602 | int m, n; |
| 603 | |
| 604 | start_draw_board(); |
| 605 | for (m = 0; m < board_size; m++) |
| 606 | for (n = 0; n < board_size; n++) { |
| 607 | int col, c; |
| 608 | |
| 609 | if (mf[POS(m, n)]) { |
| 610 | if (mn[POS(m, n)] == 1) |
| 611 | col = GG_COLOR_RED; |
| 612 | else if (mn[POS(m, n)] == 2) |
| 613 | col = GG_COLOR_YELLOW; |
| 614 | else |
| 615 | col = GG_COLOR_GREEN; |
| 616 | } |
| 617 | else if (mn[POS(m, n)] == 1) |
| 618 | col = GG_COLOR_BLUE; |
| 619 | else if (mn[POS(m, n)] == 2) |
| 620 | col = GG_COLOR_CYAN; |
| 621 | else |
| 622 | col = GG_COLOR_BLACK; |
| 623 | if (board[POS(m, n)] == BLACK) |
| 624 | c = 'X'; |
| 625 | else if (board[POS(m, n)] == WHITE) |
| 626 | c = 'O'; |
| 627 | else if (mn[POS(m, n)]) |
| 628 | c = '*'; |
| 629 | else |
| 630 | c = '.'; |
| 631 | draw_color_char(m, n, c, col); |
| 632 | } |
| 633 | end_draw_board(); |
| 634 | } |
| 635 | |
| 636 | |
| 637 | |
| 638 | int |
| 639 | is_surrounded(int dr) |
| 640 | { |
| 641 | return(DRAGON2(dr).surround_status); |
| 642 | } |
| 643 | |
| 644 | /* Returns true if (dragon) is not surrounded, but (move) surrounds it. |
| 645 | */ |
| 646 | |
| 647 | int |
| 648 | does_surround(int move, int dr) |
| 649 | { |
| 650 | if (DRAGON2(dr).surround_status) |
| 651 | return 0; |
| 652 | return compute_surroundings(dr, move, 0, NULL); |
| 653 | } |
| 654 | |
| 655 | |
| 656 | /* Should be run once per genmove, before make_dragons. */ |
| 657 | |
| 658 | void |
| 659 | reset_surround_data(void) |
| 660 | { |
| 661 | surround_pointer = 0; |
| 662 | } |
| 663 | |
| 664 | |
| 665 | /* Returns 1 (respectively 2) if pos is in the convex hull |
| 666 | * (respectively expanded hull boundary) of the surrounding |
| 667 | * dragons. Returns -1 if the dragon is not found. |
| 668 | */ |
| 669 | int |
| 670 | surround_map(int dr, int pos) |
| 671 | { |
| 672 | int k; |
| 673 | |
| 674 | for (k = 0; k < surround_pointer; k++) |
| 675 | if (surroundings[k].dragon_number == dragon[dr].id) |
| 676 | return surroundings[k].surround_map[pos]; |
| 677 | return -1; |
| 678 | } |
| 679 | |
| 680 | |
| 681 | |
| 682 | |
| 683 | |
| 684 | /* |
| 685 | * Local Variables: |
| 686 | * tab-width: 8 |
| 687 | * c-basic-offset: 2 |
| 688 | * End: |
| 689 | */ |