1 /* $NetBSD: bdinit.c,v 1.37 2022/06/19 10:33:17 rillig Exp $ */
2
3 /*
4 * Copyright (c) 1994
5 * The Regents of the University of California. All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Ralph Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 * may be used to endorse or promote products derived from this software
20 * without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35 #include <sys/cdefs.h>
36 /* from: @(#)bdinit.c 8.2 (Berkeley) 5/3/95 */
37 __RCSID("$NetBSD: bdinit.c,v 1.37 2022/06/19 10:33:17 rillig Exp $");
38
39 #include <string.h>
40 #include "gomoku.h"
41
42 static void init_overlap(void);
43
44 static void
init_spot_flags_and_fval(struct spotstr * sp,int col,int row)45 init_spot_flags_and_fval(struct spotstr *sp, int col, int row)
46 {
47
48 sp->s_flags = 0;
49 if (row < 5) {
50 set_blocked(sp, DIR_DR);
51 set_blocked(sp, DIR_D_);
52 set_blocked(sp, DIR_DL);
53 sp->s_fval[BLACK][DIR_DR].s = 0x600;
54 sp->s_fval[BLACK][DIR_D_].s = 0x600;
55 sp->s_fval[BLACK][DIR_DL].s = 0x600;
56 sp->s_fval[WHITE][DIR_DR].s = 0x600;
57 sp->s_fval[WHITE][DIR_D_].s = 0x600;
58 sp->s_fval[WHITE][DIR_DL].s = 0x600;
59 } else if (row == 5) {
60 /* five spaces, blocked on one side */
61 sp->s_fval[BLACK][DIR_DR].s = 0x500;
62 sp->s_fval[BLACK][DIR_D_].s = 0x500;
63 sp->s_fval[BLACK][DIR_DL].s = 0x500;
64 sp->s_fval[WHITE][DIR_DR].s = 0x500;
65 sp->s_fval[WHITE][DIR_D_].s = 0x500;
66 sp->s_fval[WHITE][DIR_DL].s = 0x500;
67 } else {
68 /* six spaces, not blocked */
69 sp->s_fval[BLACK][DIR_DR].s = 0x401;
70 sp->s_fval[BLACK][DIR_D_].s = 0x401;
71 sp->s_fval[BLACK][DIR_DL].s = 0x401;
72 sp->s_fval[WHITE][DIR_DR].s = 0x401;
73 sp->s_fval[WHITE][DIR_D_].s = 0x401;
74 sp->s_fval[WHITE][DIR_DL].s = 0x401;
75 }
76 if (col > BSZ - 4) {
77 set_blocked(sp, DIR__R);
78 set_blocked(sp, DIR_DR);
79 sp->s_fval[BLACK][DIR__R].s = 0x600;
80 sp->s_fval[BLACK][DIR_DR].s = 0x600;
81 sp->s_fval[WHITE][DIR__R].s = 0x600;
82 sp->s_fval[WHITE][DIR_DR].s = 0x600;
83 } else if (col == BSZ - 4) {
84 sp->s_fval[BLACK][DIR__R].s = 0x500;
85 sp->s_fval[WHITE][DIR__R].s = 0x500;
86 if (!is_blocked(sp, DIR_DR)) {
87 sp->s_fval[BLACK][DIR_DR].s = 0x500;
88 sp->s_fval[WHITE][DIR_DR].s = 0x500;
89 }
90 } else {
91 sp->s_fval[BLACK][DIR__R].s = 0x401;
92 sp->s_fval[WHITE][DIR__R].s = 0x401;
93 if (col < 5) {
94 set_blocked(sp, DIR_DL);
95 sp->s_fval[BLACK][DIR_DL].s = 0x600;
96 sp->s_fval[WHITE][DIR_DL].s = 0x600;
97 } else if (col == 5 && !is_blocked(sp, DIR_DL)) {
98 sp->s_fval[BLACK][DIR_DL].s = 0x500;
99 sp->s_fval[WHITE][DIR_DL].s = 0x500;
100 }
101 }
102 }
103
104 /* Allocate one of the pre-allocated frames for each non-blocked frame. */
105 static void
init_spot_frame(struct spotstr * sp,frame_index * fip)106 init_spot_frame(struct spotstr *sp, frame_index *fip)
107 {
108
109 for (direction r = 4; r-- > 0; ) {
110 if (is_blocked(sp, r))
111 continue;
112
113 frame_index fi = (*fip)++;
114 sp->s_frame[r] = fi;
115
116 struct combostr *cbp = &frames[fi];
117 cbp->c_combo.s = sp->s_fval[BLACK][r].s;
118 cbp->c_vertex = (spot_index)(sp - board);
119 cbp->c_nframes = 1;
120 cbp->c_dir = r;
121 }
122 }
123
124 void
init_board(void)125 init_board(void)
126 {
127
128 game.nmoves = 0;
129 game.win_spot = 0;
130 game.user_x = 1 + (BSZ - 1) / 2;
131 game.user_y = 1 + (BSZ - 1) / 2;
132
133 struct spotstr *sp = board;
134 for (int i = 0; i < 1 + BSZ + 1; i++, sp++) {
135 sp->s_occ = BORDER; /* bottom border and corners */
136 sp->s_flags = BFLAGALL;
137 }
138
139 /* fill the playing area of the board with EMPTY spots */
140 frame_index fi = 0;
141 memset(frames, 0, sizeof(frames));
142 for (int row = 1; row <= BSZ; row++, sp++) {
143 for (int col = 1; col <= BSZ; col++, sp++) {
144 sp->s_occ = EMPTY;
145 sp->s_wval = 0;
146 init_spot_flags_and_fval(sp, col, row);
147 init_spot_frame(sp, &fi);
148 }
149 sp->s_occ = BORDER; /* combined left and right border */
150 sp->s_flags = BFLAGALL;
151 }
152
153 for (int i = 0; i < BSZ + 1; i++, sp++) {
154 sp->s_occ = BORDER; /* top border and top-right corner */
155 sp->s_flags = BFLAGALL;
156 }
157
158 sortframes[BLACK] = NULL;
159 sortframes[WHITE] = NULL;
160
161 init_overlap();
162 }
163
164 /*
165 * Variable names for frames A and B:
166 *
167 * fi index of the frame in the global 'frames'
168 * d direction delta, difference between adjacent spot indexes
169 * off index of the spot in the frame, 0 to 5
170 */
171
172 /*
173 * Each entry in the overlap array is a bit mask with eight bits corresponding
174 * to whether frame B overlaps frame A (as indexed by overlap[A * FAREA + B]).
175 *
176 * The eight bits correspond to whether A and B are open-ended (length 6) or
177 * closed (length 5).
178 *
179 * 0 A closed and B closed
180 * 1 A closed and B open
181 * 2 A open and B closed
182 * 3 A open and B open
183 * 4 A closed and B closed and overlaps in more than one spot
184 * 5 A closed and B open and overlaps in more than one spot
185 * 6 A open and B closed and overlaps in more than one spot
186 * 7 A open and B open and overlaps in more than one spot
187 *
188 * As pieces are played during the game, frames that no longer share an empty
189 * spot will be removed from the overlap array by setting the entry to 0.
190 */
191 static u_char
adjust_overlap(u_char ov,int ra,int offa,int rb,int offb,int mask)192 adjust_overlap(u_char ov, int ra, int offa, int rb, int offb, int mask)
193 {
194 ov |= (offb == 5) ? mask & 0xA : mask;
195 if (rb != ra)
196 return ov;
197
198 /* compute the multiple spot overlap values */
199 switch (offa) {
200 case 0:
201 if (offb == 4)
202 ov |= 0xA0;
203 else if (offb != 5)
204 ov |= 0xF0;
205 break;
206 case 1:
207 if (offb == 5)
208 ov |= 0xA0;
209 else
210 ov |= 0xF0;
211 break;
212 case 4:
213 if (offb == 0)
214 ov |= 0xC0;
215 else
216 ov |= 0xF0;
217 break;
218 case 5:
219 if (offb == 1)
220 ov |= 0xC0;
221 else if (offb != 0)
222 ov |= 0xF0;
223 break;
224 default:
225 ov |= 0xF0;
226 }
227
228 return ov;
229 }
230
231 /*
232 * Given a single spot 's' of frame A, update the overlap information for
233 * each frame B that overlaps frame A in that spot.
234 */
235 static void
init_overlap_frame(int fia,int ra,int offa,spot_index s,int mask)236 init_overlap_frame(int fia, int ra, int offa, spot_index s, int mask)
237 {
238
239 for (int rb = 4; --rb >= 0;) {
240 int db = dd[rb];
241
242 for (int offb = 0; offb < 6; offb++) {
243 /* spb0 is the spot where frame B starts. */
244 const struct spotstr *spb0 = &board[s - offb * db];
245 if (spb0->s_occ == BORDER)
246 break;
247 if (is_blocked(spb0, rb))
248 continue;
249
250 frame_index fib = spb0->s_frame[rb];
251 intersect[fia * FAREA + fib] = s;
252 u_char *op = &overlap[fia * FAREA + fib];
253 *op = adjust_overlap(*op, ra, offa, rb, offb, mask);
254 }
255 }
256 }
257
258 static void
init_overlap(void)259 init_overlap(void)
260 {
261
262 memset(overlap, 0, sizeof(overlap));
263 memset(intersect, 0, sizeof(intersect));
264
265 for (int fia = FAREA; fia-- > 0;) {
266 const struct combostr *fa = &frames[fia];
267 spot_index s = fa->c_vertex;
268 u_char ra = fa->c_dir;
269 int da = dd[ra];
270
271 /*
272 * len = 5 if closed, 6 if open. At this early stage, Black
273 * and White have the same value for cv_win.
274 */
275 int len = 5 + board[s].s_fval[BLACK][ra].cv_win;
276
277 for (int offa = 0; offa < len; offa++) {
278 /* spot[5] in frame A only overlaps if it is open */
279 int mask = (offa == 5) ? 0xC : 0xF;
280
281 init_overlap_frame(fia, ra, offa, s + offa * da, mask);
282 }
283 }
284 }
285