Commit | Line | Data |
---|---|---|
7eeb782e AT |
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 | */ |