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 | ||
25 | struct heap_entry; | |
26 | struct connection_data; | |
27 | ||
28 | /* Expensive functions that we try to evaluate as late as possible | |
29 | * when spreading connection distances. | |
30 | */ | |
31 | typedef void (*connection_helper_fn_ptr) (struct connection_data *conn, | |
32 | int color); | |
33 | ||
34 | /* This heap contains a list of positions where we have delayed a | |
35 | * decision whether to "spread a connection distance". The function | |
36 | * helper() will be called when we finally need the decision. See | |
37 | * push_connection_heap_entry() for organization of the heap. | |
38 | */ | |
39 | struct heap_entry { | |
40 | int distance; | |
41 | int coming_from; | |
42 | int target; | |
43 | connection_helper_fn_ptr helper; | |
44 | }; | |
45 | ||
46 | /* Fixed-point arithmetic helper macros */ | |
47 | #define FIXED_POINT_BASIS 10000 | |
48 | #define FP(x) ((int) (0.5 + FIXED_POINT_BASIS * (x))) | |
49 | #define FIXED_TO_FLOAT(x) ((x) / (float) FIXED_POINT_BASIS) | |
50 | ||
51 | #define HUGE_CONNECTION_DISTANCE FP(100.0) | |
52 | ||
53 | struct connection_data { | |
54 | int distances[BOARDMAX]; | |
55 | int deltas[BOARDMAX]; | |
56 | int coming_from[BOARDMAX]; | |
57 | int vulnerable1[BOARDMAX]; | |
58 | int vulnerable2[BOARDMAX]; | |
59 | int queue[BOARDMAX]; | |
60 | int queue_start; | |
61 | int queue_end; | |
62 | ||
63 | int heap_data_size; | |
64 | int heap_size; | |
65 | struct heap_entry heap_data[4 * BOARDMAX]; | |
66 | struct heap_entry *heap[BOARDMAX]; | |
67 | ||
68 | int target; | |
69 | int cutoff_distance; | |
70 | int speculative; | |
71 | }; | |
72 | ||
73 | ||
74 | void compute_connection_distances(int str, int target, int cutoff, | |
75 | struct connection_data *conn, | |
76 | int speculative); | |
77 | void init_connection_data(int color, const signed char goal[BOARDMAX], | |
78 | int target, int cutoff, | |
79 | struct connection_data *conn, int speculative); | |
80 | void spread_connection_distances(int color, struct connection_data *conn); | |
81 | void sort_connection_queue_tail(struct connection_data *conn); | |
82 | void expand_connection_queue(struct connection_data *conn); | |
83 | void print_connection_distances(struct connection_data *conn); | |
84 | ||
85 | ||
86 | /* | |
87 | * Local Variables: | |
88 | * tab-width: 8 | |
89 | * c-basic-offset: 2 | |
90 | * End: | |
91 | */ |