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 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 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 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 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 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 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
Indexes created Wed Sep 24 14:09:57 GMT 2025