]> git.cameronkatri.com Git - bsdgames-darwin.git/blob - gomoku/pickmove.c
git.ckatri.com / bsdgames-darwin.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Add use of `const' where appropriate to the games.
[bsdgames-darwin.git] / gomoku / pickmove.c
1 /* $NetBSD: pickmove.c,v 1.6 1999/09/08 21:17:49 jsm 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. All advertising materials mentioning features or use of this software
19 * must display the following acknowledgement:
20 * This product includes software developed by the University of
21 * California, Berkeley and its contributors.
22 * 4. Neither the name of the University nor the names of its contributors
23 * may be used to endorse or promote products derived from this software
24 * without specific prior written permission.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
37 */
38
39 #include <sys/cdefs.h>
40 #ifndef lint
41 #if 0
42 static char sccsid[] = "@(#)pickmove.c 8.2 (Berkeley) 5/3/95";
43 #else
44 __RCSID("$NetBSD: pickmove.c,v 1.6 1999/09/08 21:17:49 jsm Exp $");
45 #endif
46 #endif /* not lint */
47
48 #include <stdlib.h>
49 #include <string.h>
50 #include <curses.h>
51 #include <machine/limits.h>
52
53 #include "gomoku.h"
54
55 #define BITS_PER_INT (sizeof(int) * CHAR_BIT)
56 #define MAPSZ (BAREA / BITS_PER_INT)
57
58 #define BIT_SET(a, b) ((a)[(b)/BITS_PER_INT] |= (1 << ((b) % BITS_PER_INT)))
59 #define BIT_CLR(a, b) ((a)[(b)/BITS_PER_INT] &= ~(1 << ((b) % BITS_PER_INT)))
60 #define BIT_TEST(a, b) ((a)[(b)/BITS_PER_INT] & (1 << ((b) % BITS_PER_INT)))
61
62 struct combostr *hashcombos[FAREA]; /* hash list for finding duplicates */
63 struct combostr *sortcombos; /* combos at higher levels */
64 int combolen; /* number of combos in sortcombos */
65 int nextcolor; /* color of next move */
66 int elistcnt; /* count of struct elist allocated */
67 int combocnt; /* count of struct combostr allocated */
68 int forcemap[MAPSZ]; /* map for blocking <1,x> combos */
69 int tmpmap[MAPSZ]; /* map for blocking <1,x> combos */
70 int nforce; /* count of opponent <1,x> combos */
71
72 int
73 pickmove(us)
74 int us;
75 {
76 struct spotstr *sp, *sp1, *sp2;
77 union comboval *Ocp, *Tcp;
78 int m;
79
80 /* first move is easy */
81 if (movenum == 1)
82 return (PT(K,10));
83
84 /* initialize all the board values */
85 for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
86 sp->s_combo[BLACK].s = MAXCOMBO + 1;
87 sp->s_combo[WHITE].s = MAXCOMBO + 1;
88 sp->s_level[BLACK] = 255;
89 sp->s_level[WHITE] = 255;
90 sp->s_nforce[BLACK] = 0;
91 sp->s_nforce[WHITE] = 0;
92 sp->s_flg &= ~(FFLAGALL | MFLAGALL);
93 }
94 nforce = 0;
95 memset(forcemap, 0, sizeof(forcemap));
96
97 /* compute new values */
98 nextcolor = us;
99 scanframes(BLACK);
100 scanframes(WHITE);
101
102 /* find the spot with the highest value */
103 for (sp = sp1 = sp2 = &board[PT(T,19)]; --sp >= &board[PT(A,1)]; ) {
104 if (sp->s_occ != EMPTY)
105 continue;
106 if (debug && (sp->s_combo[BLACK].c.a == 1 ||
107 sp->s_combo[WHITE].c.a == 1)) {
108 sprintf(fmtbuf, "- %s %x/%d %d %x/%d %d %d", stoc(sp - board),
109 sp->s_combo[BLACK].s, sp->s_level[BLACK],
110 sp->s_nforce[BLACK],
111 sp->s_combo[WHITE].s, sp->s_level[WHITE],
112 sp->s_nforce[WHITE],
113 sp->s_wval);
114 dlog(fmtbuf);
115 }
116 /* pick the best black move */
117 if (better(sp, sp1, BLACK))
118 sp1 = sp;
119 /* pick the best white move */
120 if (better(sp, sp2, WHITE))
121 sp2 = sp;
122 }
123
124 if (debug) {
125 sprintf(fmtbuf, "B %s %x/%d %d %x/%d %d %d",
126 stoc(sp1 - board),
127 sp1->s_combo[BLACK].s, sp1->s_level[BLACK],
128 sp1->s_nforce[BLACK],
129 sp1->s_combo[WHITE].s, sp1->s_level[WHITE],
130 sp1->s_nforce[WHITE], sp1->s_wval);
131 dlog(fmtbuf);
132 sprintf(fmtbuf, "W %s %x/%d %d %x/%d %d %d",
133 stoc(sp2 - board),
134 sp2->s_combo[WHITE].s, sp2->s_level[WHITE],
135 sp2->s_nforce[WHITE],
136 sp2->s_combo[BLACK].s, sp2->s_level[BLACK],
137 sp2->s_nforce[BLACK], sp2->s_wval);
138 dlog(fmtbuf);
139 /*
140 * Check for more than one force that can't
141 * all be blocked with one move.
142 */
143 sp = (us == BLACK) ? sp2 : sp1;
144 m = sp - board;
145 if (sp->s_combo[!us].c.a == 1 && !BIT_TEST(forcemap, m))
146 dlog("*** Can't be blocked");
147 }
148 if (us == BLACK) {
149 Ocp = &sp1->s_combo[BLACK];
150 Tcp = &sp2->s_combo[WHITE];
151 } else {
152 Tcp = &sp1->s_combo[BLACK];
153 Ocp = &sp2->s_combo[WHITE];
154 sp = sp1;
155 sp1 = sp2;
156 sp2 = sp;
157 }
158 /*
159 * Block their combo only if we have to (i.e., if they are one move
160 * away from completing a force and we don't have a force that
161 * we can complete which takes fewer moves to win).
162 */
163 if (Tcp->c.a <= 1 && (Ocp->c.a > 1 ||
164 Tcp->c.a + Tcp->c.b < Ocp->c.a + Ocp->c.b))
165 return (sp2 - board);
166 return (sp1 - board);
167 }
168
169 /*
170 * Return true if spot 'sp' is better than spot 'sp1' for color 'us'.
171 */
172 int
173 better(sp, sp1, us)
174 const struct spotstr *sp;
175 const struct spotstr *sp1;
176 int us;
177 {
178 int them, s, s1;
179
180 if (sp->s_combo[us].s < sp1->s_combo[us].s)
181 return (1);
182 if (sp->s_combo[us].s != sp1->s_combo[us].s)
183 return (0);
184 if (sp->s_level[us] < sp1->s_level[us])
185 return (1);
186 if (sp->s_level[us] != sp1->s_level[us])
187 return (0);
188 if (sp->s_nforce[us] > sp1->s_nforce[us])
189 return (1);
190 if (sp->s_nforce[us] != sp1->s_nforce[us])
191 return (0);
192
193 them = !us;
194 s = sp - board;
195 s1 = sp1 - board;
196 if (BIT_TEST(forcemap, s) && !BIT_TEST(forcemap, s1))
197 return (1);
198 if (!BIT_TEST(forcemap, s) && BIT_TEST(forcemap, s1))
199 return (0);
200 if (sp->s_combo[them].s < sp1->s_combo[them].s)
201 return (1);
202 if (sp->s_combo[them].s != sp1->s_combo[them].s)
203 return (0);
204 if (sp->s_level[them] < sp1->s_level[them])
205 return (1);
206 if (sp->s_level[them] != sp1->s_level[them])
207 return (0);
208 if (sp->s_nforce[them] > sp1->s_nforce[them])
209 return (1);
210 if (sp->s_nforce[them] != sp1->s_nforce[them])
211 return (0);
212
213 if (sp->s_wval > sp1->s_wval)
214 return (1);
215 if (sp->s_wval != sp1->s_wval)
216 return (0);
217
218 #ifdef SVR4
219 return (rand() & 1);
220 #else
221 return (random() & 1);
222 #endif
223 }
224
225 int curcolor; /* implicit parameter to makecombo() */
226 int curlevel; /* implicit parameter to makecombo() */
227
228 /*
229 * Scan the sorted list of non-empty frames and
230 * update the minimum combo values for each empty spot.
231 * Also, try to combine frames to find more complex (chained) moves.
232 */
233 void
234 scanframes(color)
235 int color;
236 {
237 struct combostr *cbp, *ecbp;
238 struct spotstr *sp;
239 union comboval *cp;
240 struct elist *ep, *nep;
241 int i, r, d, n;
242 union comboval cb;
243
244 curcolor = color;
245
246 /* check for empty list of frames */
247 cbp = sortframes[color];
248 if (cbp == (struct combostr *)0)
249 return;
250
251 /* quick check for four in a row */
252 sp = &board[cbp->c_vertex];
253 cb.s = sp->s_fval[color][d = cbp->c_dir].s;
254 if (cb.s < 0x101) {
255 d = dd[d];
256 for (i = 5 + cb.c.b; --i >= 0; sp += d) {
257 if (sp->s_occ != EMPTY)
258 continue;
259 sp->s_combo[color].s = cb.s;
260 sp->s_level[color] = 1;
261 }
262 return;
263 }
264
265 /*
266 * Update the minimum combo value for each spot in the frame
267 * and try making all combinations of two frames intersecting at
268 * an empty spot.
269 */
270 n = combolen;
271 ecbp = cbp;
272 do {
273 sp = &board[cbp->c_vertex];
274 cp = &sp->s_fval[color][r = cbp->c_dir];
275 d = dd[r];
276 if (cp->c.b) {
277 /*
278 * Since this is the first spot of an open ended
279 * frame, we treat it as a closed frame.
280 */
281 cb.c.a = cp->c.a + 1;
282 cb.c.b = 0;
283 if (cb.s < sp->s_combo[color].s) {
284 sp->s_combo[color].s = cb.s;
285 sp->s_level[color] = 1;
286 }
287 /*
288 * Try combining other frames that intersect
289 * at this spot.
290 */
291 makecombo2(cbp, sp, 0, cb.s);
292 if (cp->s != 0x101)
293 cb.s = cp->s;
294 else if (color != nextcolor)
295 memset(tmpmap, 0, sizeof(tmpmap));
296 sp += d;
297 i = 1;
298 } else {
299 cb.s = cp->s;
300 i = 0;
301 }
302 for (; i < 5; i++, sp += d) { /* for each spot */
303 if (sp->s_occ != EMPTY)
304 continue;
305 if (cp->s < sp->s_combo[color].s) {
306 sp->s_combo[color].s = cp->s;
307 sp->s_level[color] = 1;
308 }
309 if (cp->s == 0x101) {
310 sp->s_nforce[color]++;
311 if (color != nextcolor) {
312 n = sp - board;
313 BIT_SET(tmpmap, n);
314 }
315 }
316 /*
317 * Try combining other frames that intersect
318 * at this spot.
319 */
320 makecombo2(cbp, sp, i, cb.s);
321 }
322 if (cp->s == 0x101 && color != nextcolor) {
323 if (nforce == 0)
324 memcpy(forcemap, tmpmap, sizeof(tmpmap));
325 else {
326 for (i = 0; i < MAPSZ; i++)
327 forcemap[i] &= tmpmap[i];
328 }
329 }
330 /* mark frame as having been processed */
331 board[cbp->c_vertex].s_flg |= MFLAG << r;
332 } while ((cbp = cbp->c_next) != ecbp);
333
334 /*
335 * Try to make new 3rd level combos, 4th level, etc.
336 * Limit the search depth early in the game.
337 */
338 d = 2;
339 while (d <= ((movenum + 1) >> 1) && combolen > n) {
340 if (debug) {
341 sprintf(fmtbuf, "%cL%d %d %d %d", "BW"[color],
342 d, combolen - n, combocnt, elistcnt);
343 dlog(fmtbuf);
344 refresh();
345 }
346 n = combolen;
347 addframes(d);
348 d++;
349 }
350
351 /* scan for combos at empty spots */
352 for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
353 for (ep = sp->s_empty; ep; ep = nep) {
354 cbp = ep->e_combo;
355 if (cbp->c_combo.s <= sp->s_combo[color].s) {
356 if (cbp->c_combo.s != sp->s_combo[color].s) {
357 sp->s_combo[color].s = cbp->c_combo.s;
358 sp->s_level[color] = cbp->c_nframes;
359 } else if (cbp->c_nframes < sp->s_level[color])
360 sp->s_level[color] = cbp->c_nframes;
361 }
362 nep = ep->e_next;
363 free(ep);
364 elistcnt--;
365 }
366 sp->s_empty = (struct elist *)0;
367 for (ep = sp->s_nempty; ep; ep = nep) {
368 cbp = ep->e_combo;
369 if (cbp->c_combo.s <= sp->s_combo[color].s) {
370 if (cbp->c_combo.s != sp->s_combo[color].s) {
371 sp->s_combo[color].s = cbp->c_combo.s;
372 sp->s_level[color] = cbp->c_nframes;
373 } else if (cbp->c_nframes < sp->s_level[color])
374 sp->s_level[color] = cbp->c_nframes;
375 }
376 nep = ep->e_next;
377 free(ep);
378 elistcnt--;
379 }
380 sp->s_nempty = (struct elist *)0;
381 }
382
383 /* remove old combos */
384 if ((cbp = sortcombos) != (struct combostr *)0) {
385 struct combostr *ncbp;
386
387 /* scan the list */
388 ecbp = cbp;
389 do {
390 ncbp = cbp->c_next;
391 free(cbp);
392 combocnt--;
393 } while ((cbp = ncbp) != ecbp);
394 sortcombos = (struct combostr *)0;
395 }
396 combolen = 0;
397
398 #ifdef DEBUG
399 if (combocnt) {
400 sprintf(fmtbuf, "scanframes: %c combocnt %d", "BW"[color],
401 combocnt);
402 dlog(fmtbuf);
403 whatsup(0);
404 }
405 if (elistcnt) {
406 sprintf(fmtbuf, "scanframes: %c elistcnt %d", "BW"[color],
407 elistcnt);
408 dlog(fmtbuf);
409 whatsup(0);
410 }
411 #endif
412 }
413
414 /*
415 * Compute all level 2 combos of frames intersecting spot 'osp'
416 * within the frame 'ocbp' and combo value 's'.
417 */
418 void
419 makecombo2(ocbp, osp, off, s)
420 struct combostr *ocbp;
421 struct spotstr *osp;
422 int off;
423 int s;
424 {
425 struct spotstr *fsp;
426 struct combostr *ncbp;
427 int f, r, d, c;
428 int baseB, fcnt, emask, bmask, n;
429 union comboval ocb, fcb;
430 struct combostr **scbpp, *fcbp;
431
432 /* try to combine a new frame with those found so far */
433 ocb.s = s;
434 baseB = ocb.c.a + ocb.c.b - 1;
435 fcnt = ocb.c.a - 2;
436 emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0;
437 for (r = 4; --r >= 0; ) { /* for each direction */
438 /* don't include frames that overlap in the same direction */
439 if (r == ocbp->c_dir)
440 continue;
441 d = dd[r];
442 /*
443 * Frame A combined with B is the same value as B combined with A
444 * so skip frames that have already been processed (MFLAG).
445 * Also skip blocked frames (BFLAG) and frames that are <1,x>
446 * since combining another frame with it isn't valid.
447 */
448 bmask = (BFLAG | FFLAG | MFLAG) << r;
449 fsp = osp;
450 for (f = 0; f < 5; f++, fsp -= d) { /* for each frame */
451 if (fsp->s_occ == BORDER)
452 break;
453 if (fsp->s_flg & bmask)
454 continue;
455
456 /* don't include frames of the wrong color */
457 fcb.s = fsp->s_fval[curcolor][r].s;
458 if (fcb.c.a >= MAXA)
459 continue;
460
461 /*
462 * Get the combo value for this frame.
463 * If this is the end point of the frame,
464 * use the closed ended value for the frame.
465 */
466 if ((f == 0 && fcb.c.b) || fcb.s == 0x101) {
467 fcb.c.a++;
468 fcb.c.b = 0;
469 }
470
471 /* compute combo value */
472 c = fcb.c.a + ocb.c.a - 3;
473 if (c > 4)
474 continue;
475 n = fcb.c.a + fcb.c.b - 1;
476 if (baseB < n)
477 n = baseB;
478
479 /* make a new combo! */
480 ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
481 2 * sizeof(struct combostr *));
482 scbpp = (struct combostr **)(ncbp + 1);
483 fcbp = fsp->s_frame[r];
484 if (ocbp < fcbp) {
485 scbpp[0] = ocbp;
486 scbpp[1] = fcbp;
487 } else {
488 scbpp[0] = fcbp;
489 scbpp[1] = ocbp;
490 }
491 ncbp->c_combo.c.a = c;
492 ncbp->c_combo.c.b = n;
493 ncbp->c_link[0] = ocbp;
494 ncbp->c_link[1] = fcbp;
495 ncbp->c_linkv[0].s = ocb.s;
496 ncbp->c_linkv[1].s = fcb.s;
497 ncbp->c_voff[0] = off;
498 ncbp->c_voff[1] = f;
499 ncbp->c_vertex = osp - board;
500 ncbp->c_nframes = 2;
501 ncbp->c_dir = 0;
502 ncbp->c_frameindex = 0;
503 ncbp->c_flg = (ocb.c.b) ? C_OPEN_0 : 0;
504 if (fcb.c.b)
505 ncbp->c_flg |= C_OPEN_1;
506 ncbp->c_framecnt[0] = fcnt;
507 ncbp->c_emask[0] = emask;
508 ncbp->c_framecnt[1] = fcb.c.a - 2;
509 ncbp->c_emask[1] = ncbp->c_framecnt[1] ?
510 ((fcb.c.b ? 0x1E : 0x1F) & ~(1 << f)) : 0;
511 combocnt++;
512
513 if ((c == 1 && debug > 1) || debug > 3) {
514 sprintf(fmtbuf, "%c c %d %d m %x %x o %d %d",
515 "bw"[curcolor],
516 ncbp->c_framecnt[0], ncbp->c_framecnt[1],
517 ncbp->c_emask[0], ncbp->c_emask[1],
518 ncbp->c_voff[0], ncbp->c_voff[1]);
519 dlog(fmtbuf);
520 printcombo(ncbp, fmtbuf);
521 dlog(fmtbuf);
522 }
523 if (c > 1) {
524 /* record the empty spots that will complete this combo */
525 makeempty(ncbp);
526
527 /* add the new combo to the end of the list */
528 appendcombo(ncbp, curcolor);
529 } else {
530 updatecombo(ncbp, curcolor);
531 free(ncbp);
532 combocnt--;
533 }
534 #ifdef DEBUG
535 if (c == 1 && debug > 1 || debug > 5) {
536 markcombo(ncbp);
537 bdisp();
538 whatsup(0);
539 clearcombo(ncbp, 0);
540 }
541 #endif /* DEBUG */
542 }
543 }
544 }
545
546 /*
547 * Scan the sorted list of frames and try to add a frame to
548 * combinations of 'level' number of frames.
549 */
550 void
551 addframes(level)
552 int level;
553 {
554 struct combostr *cbp, *ecbp;
555 struct spotstr *sp, *fsp;
556 struct elist *ep, *nep;
557 int i, r, d;
558 struct combostr **cbpp, *pcbp;
559 union comboval fcb, cb;
560
561 curlevel = level;
562
563 /* scan for combos at empty spots */
564 i = curcolor;
565 for (sp = &board[PT(T,20)]; --sp >= &board[PT(A,1)]; ) {
566 for (ep = sp->s_empty; ep; ep = nep) {
567 cbp = ep->e_combo;
568 if (cbp->c_combo.s <= sp->s_combo[i].s) {
569 if (cbp->c_combo.s != sp->s_combo[i].s) {
570 sp->s_combo[i].s = cbp->c_combo.s;
571 sp->s_level[i] = cbp->c_nframes;
572 } else if (cbp->c_nframes < sp->s_level[i])
573 sp->s_level[i] = cbp->c_nframes;
574 }
575 nep = ep->e_next;
576 free(ep);
577 elistcnt--;
578 }
579 sp->s_empty = sp->s_nempty;
580 sp->s_nempty = (struct elist *)0;
581 }
582
583 /* try to add frames to the uncompleted combos at level curlevel */
584 cbp = ecbp = sortframes[curcolor];
585 do {
586 fsp = &board[cbp->c_vertex];
587 r = cbp->c_dir;
588 /* skip frames that are part of a <1,x> combo */
589 if (fsp->s_flg & (FFLAG << r))
590 continue;
591
592 /*
593 * Don't include <1,x> combo frames,
594 * treat it as a closed three in a row instead.
595 */
596 fcb.s = fsp->s_fval[curcolor][r].s;
597 if (fcb.s == 0x101)
598 fcb.s = 0x200;
599
600 /*
601 * If this is an open ended frame, use
602 * the combo value with the end closed.
603 */
604 if (fsp->s_occ == EMPTY) {
605 if (fcb.c.b) {
606 cb.c.a = fcb.c.a + 1;
607 cb.c.b = 0;
608 } else
609 cb.s = fcb.s;
610 makecombo(cbp, fsp, 0, cb.s);
611 }
612
613 /*
614 * The next four spots are handled the same for both
615 * open and closed ended frames.
616 */
617 d = dd[r];
618 sp = fsp + d;
619 for (i = 1; i < 5; i++, sp += d) {
620 if (sp->s_occ != EMPTY)
621 continue;
622 makecombo(cbp, sp, i, fcb.s);
623 }
624 } while ((cbp = cbp->c_next) != ecbp);
625
626 /* put all the combos in the hash list on the sorted list */
627 cbpp = &hashcombos[FAREA];
628 do {
629 cbp = *--cbpp;
630 if (cbp == (struct combostr *)0)
631 continue;
632 *cbpp = (struct combostr *)0;
633 ecbp = sortcombos;
634 if (ecbp == (struct combostr *)0)
635 sortcombos = cbp;
636 else {
637 /* append to sort list */
638 pcbp = ecbp->c_prev;
639 pcbp->c_next = cbp;
640 ecbp->c_prev = cbp->c_prev;
641 cbp->c_prev->c_next = ecbp;
642 cbp->c_prev = pcbp;
643 }
644 } while (cbpp != hashcombos);
645 }
646
647 /*
648 * Compute all level N combos of frames intersecting spot 'osp'
649 * within the frame 'ocbp' and combo value 's'.
650 */
651 void
652 makecombo(ocbp, osp, off, s)
653 struct combostr *ocbp;
654 struct spotstr *osp;
655 int off;
656 int s;
657 {
658 struct combostr *cbp, *ncbp;
659 struct spotstr *sp;
660 struct elist *ep;
661 int n, c;
662 struct elist *nep;
663 struct combostr **scbpp;
664 int baseB, fcnt, emask, verts;
665 union comboval ocb;
666 struct ovlp_info vertices[1];
667
668 ocb.s = s;
669 baseB = ocb.c.a + ocb.c.b - 1;
670 fcnt = ocb.c.a - 2;
671 emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0;
672 for (ep = osp->s_empty; ep; ep = ep->e_next) {
673 /* check for various kinds of overlap */
674 cbp = ep->e_combo;
675 verts = checkframes(cbp, ocbp, osp, s, vertices);
676 if (verts < 0)
677 continue;
678
679 /* check to see if this frame forms a valid loop */
680 if (verts) {
681 sp = &board[vertices[0].o_intersect];
682 #ifdef DEBUG
683 if (sp->s_occ != EMPTY) {
684 sprintf(fmtbuf, "loop: %c %s", "BW"[curcolor],
685 stoc(sp - board));
686 dlog(fmtbuf);
687 whatsup(0);
688 }
689 #endif
690 /*
691 * It is a valid loop if the intersection spot
692 * of the frame we are trying to attach is one
693 * of the completion spots of the combostr
694 * we are trying to attach the frame to.
695 */
696 for (nep = sp->s_empty; nep; nep = nep->e_next) {
697 if (nep->e_combo == cbp)
698 goto fnd;
699 if (nep->e_combo->c_nframes < cbp->c_nframes)
700 break;
701 }
702 /* frame overlaps but not at a valid spot */
703 continue;
704 fnd:
705 ;
706 }
707
708 /* compute the first half of the combo value */
709 c = cbp->c_combo.c.a + ocb.c.a - verts - 3;
710 if (c > 4)
711 continue;
712
713 /* compute the second half of the combo value */
714 n = ep->e_fval.c.a + ep->e_fval.c.b - 1;
715 if (baseB < n)
716 n = baseB;
717
718 /* make a new combo! */
719 ncbp = (struct combostr *)malloc(sizeof(struct combostr) +
720 (cbp->c_nframes + 1) * sizeof(struct combostr *));
721 scbpp = (struct combostr **)(ncbp + 1);
722 if (sortcombo(scbpp, (struct combostr **)(cbp + 1), ocbp)) {
723 free(ncbp);
724 continue;
725 }
726 combocnt++;
727
728 ncbp->c_combo.c.a = c;
729 ncbp->c_combo.c.b = n;
730 ncbp->c_link[0] = cbp;
731 ncbp->c_link[1] = ocbp;
732 ncbp->c_linkv[1].s = ocb.s;
733 ncbp->c_voff[1] = off;
734 ncbp->c_vertex = osp - board;
735 ncbp->c_nframes = cbp->c_nframes + 1;
736 ncbp->c_flg = ocb.c.b ? C_OPEN_1 : 0;
737 ncbp->c_frameindex = ep->e_frameindex;
738 /*
739 * Update the completion spot mask of the frame we
740 * are attaching 'ocbp' to so the intersection isn't
741 * listed twice.
742 */
743 ncbp->c_framecnt[0] = ep->e_framecnt;
744 ncbp->c_emask[0] = ep->e_emask;
745 if (verts) {
746 ncbp->c_flg |= C_LOOP;
747 ncbp->c_dir = vertices[0].o_frameindex;
748 ncbp->c_framecnt[1] = fcnt - 1;
749 if (ncbp->c_framecnt[1]) {
750 n = (vertices[0].o_intersect - ocbp->c_vertex) /
751 dd[ocbp->c_dir];
752 ncbp->c_emask[1] = emask & ~(1 << n);
753 } else
754 ncbp->c_emask[1] = 0;
755 ncbp->c_voff[0] = vertices[0].o_off;
756 } else {
757 ncbp->c_dir = 0;
758 ncbp->c_framecnt[1] = fcnt;
759 ncbp->c_emask[1] = emask;
760 ncbp->c_voff[0] = ep->e_off;
761 }
762
763 if ((c == 1 && debug > 1) || debug > 3) {
764 sprintf(fmtbuf, "%c v%d i%d d%d c %d %d m %x %x o %d %d",
765 "bw"[curcolor], verts, ncbp->c_frameindex, ncbp->c_dir,
766 ncbp->c_framecnt[0], ncbp->c_framecnt[1],
767 ncbp->c_emask[0], ncbp->c_emask[1],
768 ncbp->c_voff[0], ncbp->c_voff[1]);
769 dlog(fmtbuf);
770 printcombo(ncbp, fmtbuf);
771 dlog(fmtbuf);
772 }
773 if (c > 1) {
774 /* record the empty spots that will complete this combo */
775 makeempty(ncbp);
776 combolen++;
777 } else {
778 /* update board values */
779 updatecombo(ncbp, curcolor);
780 }
781 #ifdef DEBUG
782 if (c == 1 && debug > 1 || debug > 4) {
783 markcombo(ncbp);
784 bdisp();
785 whatsup(0);
786 clearcombo(ncbp, 0);
787 }
788 #endif /* DEBUG */
789 }
790 }
791
792 #define MAXDEPTH 100
793 struct elist einfo[MAXDEPTH];
794 struct combostr *ecombo[MAXDEPTH]; /* separate from elist to save space */
795
796 /*
797 * Add the combostr 'ocbp' to the empty spots list for each empty spot
798 * in 'ocbp' that will complete the combo.
799 */
800 void
801 makeempty(ocbp)
802 struct combostr *ocbp;
803 {
804 struct combostr *cbp, *tcbp, **cbpp;
805 struct elist *ep, *nep;
806 struct spotstr *sp;
807 int s, d, m, emask, i;
808 int nframes;
809
810 if (debug > 2) {
811 sprintf(fmtbuf, "E%c ", "bw"[curcolor]);
812 printcombo(ocbp, fmtbuf + 3);
813 dlog(fmtbuf);
814 }
815
816 /* should never happen but check anyway */
817 if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
818 return;
819
820 /*
821 * The lower level combo can be pointed to by more than one
822 * higher level 'struct combostr' so we can't modify the
823 * lower level. Therefore, higher level combos store the
824 * real mask of the lower level frame in c_emask[0] and the
825 * frame number in c_frameindex.
826 *
827 * First we traverse the tree from top to bottom and save the
828 * connection info. Then we traverse the tree from bottom to
829 * top overwriting lower levels with the newer emask information.
830 */
831 ep = &einfo[nframes];
832 cbpp = &ecombo[nframes];
833 for (cbp = ocbp; (tcbp = cbp->c_link[1]) != NULL;
834 cbp = cbp->c_link[0]) {
835 ep--;
836 ep->e_combo = cbp;
837 *--cbpp = cbp->c_link[1];
838 ep->e_off = cbp->c_voff[1];
839 ep->e_frameindex = cbp->c_frameindex;
840 ep->e_fval.s = cbp->c_linkv[1].s;
841 ep->e_framecnt = cbp->c_framecnt[1];
842 ep->e_emask = cbp->c_emask[1];
843 }
844 cbp = ep->e_combo;
845 ep--;
846 ep->e_combo = cbp;
847 *--cbpp = cbp->c_link[0];
848 ep->e_off = cbp->c_voff[0];
849 ep->e_frameindex = 0;
850 ep->e_fval.s = cbp->c_linkv[0].s;
851 ep->e_framecnt = cbp->c_framecnt[0];
852 ep->e_emask = cbp->c_emask[0];
853
854 /* now update the emask info */
855 s = 0;
856 for (i = 2, ep += 2; i < nframes; i++, ep++) {
857 cbp = ep->e_combo;
858 nep = &einfo[ep->e_frameindex];
859 nep->e_framecnt = cbp->c_framecnt[0];
860 nep->e_emask = cbp->c_emask[0];
861
862 if (cbp->c_flg & C_LOOP) {
863 s++;
864 /*
865 * Account for the fact that this frame connects
866 * to a previous one (thus forming a loop).
867 */
868 nep = &einfo[cbp->c_dir];
869 if (--nep->e_framecnt)
870 nep->e_emask &= ~(1 << cbp->c_voff[0]);
871 else
872 nep->e_emask = 0;
873 }
874 }
875
876 /*
877 * We only need to update the emask values of "complete" loops
878 * to include the intersection spots.
879 */
880 if (s && ocbp->c_combo.c.a == 2) {
881 /* process loops from the top down */
882 ep = &einfo[nframes];
883 do {
884 ep--;
885 cbp = ep->e_combo;
886 if (!(cbp->c_flg & C_LOOP))
887 continue;
888
889 /*
890 * Update the emask values to include the
891 * intersection spots.
892 */
893 nep = &einfo[cbp->c_dir];
894 nep->e_framecnt = 1;
895 nep->e_emask = 1 << cbp->c_voff[0];
896 ep->e_framecnt = 1;
897 ep->e_emask = 1 << ep->e_off;
898 ep = &einfo[ep->e_frameindex];
899 do {
900 ep->e_framecnt = 1;
901 ep->e_emask = 1 << ep->e_off;
902 ep = &einfo[ep->e_frameindex];
903 } while (ep > nep);
904 } while (ep != einfo);
905 }
906
907 /* check all the frames for completion spots */
908 for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
909 /* skip this frame if there are no incomplete spots in it */
910 if ((emask = ep->e_emask) == 0)
911 continue;
912 cbp = *cbpp;
913 sp = &board[cbp->c_vertex];
914 d = dd[cbp->c_dir];
915 for (s = 0, m = 1; s < 5; s++, sp += d, m <<= 1) {
916 if (sp->s_occ != EMPTY || !(emask & m))
917 continue;
918
919 /* add the combo to the list of empty spots */
920 nep = (struct elist *)malloc(sizeof(struct elist));
921 nep->e_combo = ocbp;
922 nep->e_off = s;
923 nep->e_frameindex = i;
924 if (ep->e_framecnt > 1) {
925 nep->e_framecnt = ep->e_framecnt - 1;
926 nep->e_emask = emask & ~m;
927 } else {
928 nep->e_framecnt = 0;
929 nep->e_emask = 0;
930 }
931 nep->e_fval.s = ep->e_fval.s;
932 if (debug > 2) {
933 sprintf(fmtbuf, "e %s o%d i%d c%d m%x %x",
934 stoc(sp - board),
935 nep->e_off,
936 nep->e_frameindex,
937 nep->e_framecnt,
938 nep->e_emask,
939 nep->e_fval.s);
940 dlog(fmtbuf);
941 }
942
943 /* sort by the number of frames in the combo */
944 nep->e_next = sp->s_nempty;
945 sp->s_nempty = nep;
946 elistcnt++;
947 }
948 }
949 }
950
951 /*
952 * Update the board value based on the combostr.
953 * This is called only if 'cbp' is a <1,x> combo.
954 * We handle things differently depending on whether the next move
955 * would be trying to "complete" the combo or trying to block it.
956 */
957 void
958 updatecombo(cbp, color)
959 struct combostr *cbp;
960 int color;
961 {
962 struct spotstr *sp;
963 struct combostr *tcbp;
964 int i, d;
965 int nframes, flg, s;
966 union comboval cb;
967
968 flg = 0;
969 /* save the top level value for the whole combo */
970 cb.c.a = cbp->c_combo.c.a;
971 nframes = cbp->c_nframes;
972
973 if (color != nextcolor)
974 memset(tmpmap, 0, sizeof(tmpmap));
975
976 for (; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
977 flg = cbp->c_flg;
978 cb.c.b = cbp->c_combo.c.b;
979 if (color == nextcolor) {
980 /* update the board value for the vertex */
981 sp = &board[cbp->c_vertex];
982 sp->s_nforce[color]++;
983 if (cb.s <= sp->s_combo[color].s) {
984 if (cb.s != sp->s_combo[color].s) {
985 sp->s_combo[color].s = cb.s;
986 sp->s_level[color] = nframes;
987 } else if (nframes < sp->s_level[color])
988 sp->s_level[color] = nframes;
989 }
990 } else {
991 /* update the board values for each spot in frame */
992 sp = &board[s = tcbp->c_vertex];
993 d = dd[tcbp->c_dir];
994 i = (flg & C_OPEN_1) ? 6 : 5;
995 for (; --i >= 0; sp += d, s += d) {
996 if (sp->s_occ != EMPTY)
997 continue;
998 sp->s_nforce[color]++;
999 if (cb.s <= sp->s_combo[color].s) {
1000 if (cb.s != sp->s_combo[color].s) {
1001 sp->s_combo[color].s = cb.s;
1002 sp->s_level[color] = nframes;
1003 } else if (nframes < sp->s_level[color])
1004 sp->s_level[color] = nframes;
1005 }
1006 BIT_SET(tmpmap, s);
1007 }
1008 }
1009
1010 /* mark the frame as being part of a <1,x> combo */
1011 board[tcbp->c_vertex].s_flg |= FFLAG << tcbp->c_dir;
1012 }
1013
1014 if (color != nextcolor) {
1015 /* update the board values for each spot in frame */
1016 sp = &board[s = cbp->c_vertex];
1017 d = dd[cbp->c_dir];
1018 i = (flg & C_OPEN_0) ? 6 : 5;
1019 for (; --i >= 0; sp += d, s += d) {
1020 if (sp->s_occ != EMPTY)
1021 continue;
1022 sp->s_nforce[color]++;
1023 if (cb.s <= sp->s_combo[color].s) {
1024 if (cb.s != sp->s_combo[color].s) {
1025 sp->s_combo[color].s = cb.s;
1026 sp->s_level[color] = nframes;
1027 } else if (nframes < sp->s_level[color])
1028 sp->s_level[color] = nframes;
1029 }
1030 BIT_SET(tmpmap, s);
1031 }
1032 if (nforce == 0)
1033 memcpy(forcemap, tmpmap, sizeof(tmpmap));
1034 else {
1035 for (i = 0; i < MAPSZ; i++)
1036 forcemap[i] &= tmpmap[i];
1037 }
1038 nforce++;
1039 }
1040
1041 /* mark the frame as being part of a <1,x> combo */
1042 board[cbp->c_vertex].s_flg |= FFLAG << cbp->c_dir;
1043 }
1044
1045 /*
1046 * Add combo to the end of the list.
1047 */
1048 void
1049 appendcombo(cbp, color)
1050 struct combostr *cbp;
1051 int color;
1052 {
1053 struct combostr *pcbp, *ncbp;
1054
1055 combolen++;
1056 ncbp = sortcombos;
1057 if (ncbp == (struct combostr *)0) {
1058 sortcombos = cbp;
1059 cbp->c_next = cbp;
1060 cbp->c_prev = cbp;
1061 return;
1062 }
1063 pcbp = ncbp->c_prev;
1064 cbp->c_next = ncbp;
1065 cbp->c_prev = pcbp;
1066 ncbp->c_prev = cbp;
1067 pcbp->c_next = cbp;
1068 }
1069
1070 /*
1071 * Return zero if it is valid to combine frame 'fcbp' with the frames
1072 * in 'cbp' and forms a linked chain of frames (i.e., a tree; no loops).
1073 * Return positive if combining frame 'fcbp' to the frames in 'cbp'
1074 * would form some kind of valid loop. Also return the intersection spots
1075 * in 'vertices[]' beside the known intersection at spot 'osp'.
1076 * Return -1 if 'fcbp' should not be combined with 'cbp'.
1077 * 's' is the combo value for frame 'fcpb'.
1078 */
1079 int
1080 checkframes(cbp, fcbp, osp, s, vertices)
1081 struct combostr *cbp;
1082 struct combostr *fcbp;
1083 struct spotstr *osp;
1084 int s;
1085 struct ovlp_info *vertices;
1086 {
1087 struct combostr *tcbp, *lcbp;
1088 int i, n, mask, flg, verts, loop, index, fcnt;
1089 union comboval cb;
1090 u_char *str;
1091 short *ip;
1092
1093 lcbp = NULL;
1094 flg = 0;
1095
1096 cb.s = s;
1097 fcnt = cb.c.a - 2;
1098 verts = 0;
1099 loop = 0;
1100 index = cbp->c_nframes;
1101 n = (fcbp - frames) * FAREA;
1102 str = &overlap[n];
1103 ip = &intersect[n];
1104 /*
1105 * i == which overlap bit to test based on whether 'fcbp' is
1106 * an open or closed frame.
1107 */
1108 i = cb.c.b ? 2 : 0;
1109 for (; (tcbp = cbp->c_link[1]) != NULL;
1110 lcbp = cbp, cbp = cbp->c_link[0]) {
1111 if (tcbp == fcbp)
1112 return (-1); /* fcbp is already included */
1113
1114 /* check for intersection of 'tcbp' with 'fcbp' */
1115 index--;
1116 mask = str[tcbp - frames];
1117 flg = cbp->c_flg;
1118 n = i + ((flg & C_OPEN_1) != 0);
1119 if (mask & (1 << n)) {
1120 /*
1121 * The two frames are not independent if they
1122 * both lie in the same line and intersect at
1123 * more than one point.
1124 */
1125 if (tcbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)))
1126 return (-1);
1127 /*
1128 * If this is not the spot we are attaching
1129 * 'fcbp' to and it is a reasonable intersection
1130 * spot, then there might be a loop.
1131 */
1132 n = ip[tcbp - frames];
1133 if (osp != &board[n]) {
1134 /* check to see if this is a valid loop */
1135 if (verts)
1136 return (-1);
1137 if (fcnt == 0 || cbp->c_framecnt[1] == 0)
1138 return (-1);
1139 /*
1140 * Check to be sure the intersection is not
1141 * one of the end points if it is an open
1142 * ended frame.
1143 */
1144 if ((flg & C_OPEN_1) &&
1145 (n == tcbp->c_vertex ||
1146 n == tcbp->c_vertex + 5 * dd[tcbp->c_dir]))
1147 return (-1); /* invalid overlap */
1148 if (cb.c.b &&
1149 (n == fcbp->c_vertex ||
1150 n == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
1151 return (-1); /* invalid overlap */
1152
1153 vertices->o_intersect = n;
1154 vertices->o_fcombo = cbp;
1155 vertices->o_link = 1;
1156 vertices->o_off = (n - tcbp->c_vertex) /
1157 dd[tcbp->c_dir];
1158 vertices->o_frameindex = index;
1159 verts++;
1160 }
1161 }
1162 n = i + ((flg & C_OPEN_0) != 0);
1163 }
1164 if (cbp == fcbp)
1165 return (-1); /* fcbp is already included */
1166
1167 /* check for intersection of 'cbp' with 'fcbp' */
1168 mask = str[cbp - frames];
1169 if (mask & (1 << n)) {
1170 /*
1171 * The two frames are not independent if they
1172 * both lie in the same line and intersect at
1173 * more than one point.
1174 */
1175 if (cbp->c_dir == fcbp->c_dir && (mask & (0x10 << n)))
1176 return (-1);
1177 /*
1178 * If this is not the spot we are attaching
1179 * 'fcbp' to and it is a reasonable intersection
1180 * spot, then there might be a loop.
1181 */
1182 n = ip[cbp - frames];
1183 if (osp != &board[n]) {
1184 /* check to see if this is a valid loop */
1185 if (verts)
1186 return (-1);
1187 if (fcnt == 0 || lcbp->c_framecnt[0] == 0)
1188 return (-1);
1189 /*
1190 * Check to be sure the intersection is not
1191 * one of the end points if it is an open
1192 * ended frame.
1193 */
1194 if ((flg & C_OPEN_0) &&
1195 (n == cbp->c_vertex ||
1196 n == cbp->c_vertex + 5 * dd[cbp->c_dir]))
1197 return (-1); /* invalid overlap */
1198 if (cb.c.b &&
1199 (n == fcbp->c_vertex ||
1200 n == fcbp->c_vertex + 5 * dd[fcbp->c_dir]))
1201 return (-1); /* invalid overlap */
1202
1203 vertices->o_intersect = n;
1204 vertices->o_fcombo = lcbp;
1205 vertices->o_link = 0;
1206 vertices->o_off = (n - cbp->c_vertex) /
1207 dd[cbp->c_dir];
1208 vertices->o_frameindex = 0;
1209 verts++;
1210 }
1211 }
1212 return (verts);
1213 }
1214
1215 /*
1216 * Merge sort the frame 'fcbp' and the sorted list of frames 'cbpp' and
1217 * store the result in 'scbpp'. 'curlevel' is the size of the 'cbpp' array.
1218 * Return true if this list of frames is already in the hash list.
1219 * Otherwise, add the new combo to the hash list.
1220 */
1221 int
1222 sortcombo(scbpp, cbpp, fcbp)
1223 struct combostr **scbpp;
1224 struct combostr **cbpp;
1225 struct combostr *fcbp;
1226 {
1227 struct combostr **spp, **cpp;
1228 struct combostr *cbp, *ecbp;
1229 int n, inx;
1230
1231 #ifdef DEBUG
1232 if (debug > 3) {
1233 char *str;
1234
1235 sprintf(fmtbuf, "sortc: %s%c l%d", stoc(fcbp->c_vertex),
1236 pdir[fcbp->c_dir], curlevel);
1237 dlog(fmtbuf);
1238 str = fmtbuf;
1239 for (cpp = cbpp; cpp < cbpp + curlevel; cpp++) {
1240 sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
1241 pdir[(*cpp)->c_dir]);
1242 str += strlen(str);
1243 }
1244 dlog(fmtbuf);
1245 }
1246 #endif /* DEBUG */
1247
1248 /* first build the new sorted list */
1249 n = curlevel + 1;
1250 spp = scbpp + n;
1251 cpp = cbpp + curlevel;
1252 do {
1253 cpp--;
1254 if (fcbp > *cpp) {
1255 *--spp = fcbp;
1256 do
1257 *--spp = *cpp;
1258 while (cpp-- != cbpp);
1259 goto inserted;
1260 }
1261 *--spp = *cpp;
1262 } while (cpp != cbpp);
1263 *--spp = fcbp;
1264 inserted:
1265
1266 /* now check to see if this list of frames has already been seen */
1267 cbp = hashcombos[inx = *scbpp - frames];
1268 if (cbp == (struct combostr *)0) {
1269 /*
1270 * Easy case, this list hasn't been seen.
1271 * Add it to the hash list.
1272 */
1273 fcbp = (struct combostr *)
1274 ((char *)scbpp - sizeof(struct combostr));
1275 hashcombos[inx] = fcbp;
1276 fcbp->c_next = fcbp->c_prev = fcbp;
1277 return (0);
1278 }
1279 ecbp = cbp;
1280 do {
1281 cbpp = (struct combostr **)(cbp + 1);
1282 cpp = cbpp + n;
1283 spp = scbpp + n;
1284 cbpp++; /* first frame is always the same */
1285 do {
1286 if (*--spp != *--cpp)
1287 goto next;
1288 } while (cpp != cbpp);
1289 /* we found a match */
1290 #ifdef DEBUG
1291 if (debug > 3) {
1292 char *str;
1293
1294 sprintf(fmtbuf, "sort1: n%d", n);
1295 dlog(fmtbuf);
1296 str = fmtbuf;
1297 for (cpp = scbpp; cpp < scbpp + n; cpp++) {
1298 sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
1299 pdir[(*cpp)->c_dir]);
1300 str += strlen(str);
1301 }
1302 dlog(fmtbuf);
1303 printcombo(cbp, fmtbuf);
1304 dlog(fmtbuf);
1305 str = fmtbuf;
1306 cbpp--;
1307 for (cpp = cbpp; cpp < cbpp + n; cpp++) {
1308 sprintf(str, " %s%c", stoc((*cpp)->c_vertex),
1309 pdir[(*cpp)->c_dir]);
1310 str += strlen(str);
1311 }
1312 dlog(fmtbuf);
1313 }
1314 #endif /* DEBUG */
1315 return (1);
1316 next:
1317 ;
1318 } while ((cbp = cbp->c_next) != ecbp);
1319 /*
1320 * This list of frames hasn't been seen.
1321 * Add it to the hash list.
1322 */
1323 ecbp = cbp->c_prev;
1324 fcbp = (struct combostr *)((char *)scbpp - sizeof(struct combostr));
1325 fcbp->c_next = cbp;
1326 fcbp->c_prev = ecbp;
1327 cbp->c_prev = fcbp;
1328 ecbp->c_next = fcbp;
1329 return (0);
1330 }
1331
1332 /*
1333 * Print the combo into string 'str'.
1334 */
1335 void
1336 printcombo(cbp, str)
1337 struct combostr *cbp;
1338 char *str;
1339 {
1340 struct combostr *tcbp;
1341
1342 sprintf(str, "%x/%d", cbp->c_combo.s, cbp->c_nframes);
1343 str += strlen(str);
1344 for (; (tcbp = cbp->c_link[1]) != NULL; cbp = cbp->c_link[0]) {
1345 sprintf(str, " %s%c%x", stoc(tcbp->c_vertex), pdir[tcbp->c_dir],
1346 cbp->c_flg);
1347 str += strlen(str);
1348 }
1349 sprintf(str, " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]);
1350 }
1351
1352 #ifdef DEBUG
1353 void
1354 markcombo(ocbp)
1355 struct combostr *ocbp;
1356 {
1357 struct combostr *cbp, *tcbp, **cbpp;
1358 struct elist *ep, *nep, **epp;
1359 struct spotstr *sp;
1360 int s, d, m, i;
1361 int nframes;
1362 int r, n, flg, cmask, omask;
1363
1364 /* should never happen but check anyway */
1365 if ((nframes = ocbp->c_nframes) >= MAXDEPTH)
1366 return;
1367
1368 /*
1369 * The lower level combo can be pointed to by more than one
1370 * higher level 'struct combostr' so we can't modify the
1371 * lower level. Therefore, higher level combos store the
1372 * real mask of the lower level frame in c_emask[0] and the
1373 * frame number in c_frameindex.
1374 *
1375 * First we traverse the tree from top to bottom and save the
1376 * connection info. Then we traverse the tree from bottom to
1377 * top overwriting lower levels with the newer emask information.
1378 */
1379 ep = &einfo[nframes];
1380 cbpp = &ecombo[nframes];
1381 for (cbp = ocbp; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
1382 ep--;
1383 ep->e_combo = cbp;
1384 *--cbpp = cbp->c_link[1];
1385 ep->e_off = cbp->c_voff[1];
1386 ep->e_frameindex = cbp->c_frameindex;
1387 ep->e_fval.s = cbp->c_linkv[1].s;
1388 ep->e_framecnt = cbp->c_framecnt[1];
1389 ep->e_emask = cbp->c_emask[1];
1390 }
1391 cbp = ep->e_combo;
1392 ep--;
1393 ep->e_combo = cbp;
1394 *--cbpp = cbp->c_link[0];
1395 ep->e_off = cbp->c_voff[0];
1396 ep->e_frameindex = 0;
1397 ep->e_fval.s = cbp->c_linkv[0].s;
1398 ep->e_framecnt = cbp->c_framecnt[0];
1399 ep->e_emask = cbp->c_emask[0];
1400
1401 /* now update the emask info */
1402 s = 0;
1403 for (i = 2, ep += 2; i < nframes; i++, ep++) {
1404 cbp = ep->e_combo;
1405 nep = &einfo[ep->e_frameindex];
1406 nep->e_framecnt = cbp->c_framecnt[0];
1407 nep->e_emask = cbp->c_emask[0];
1408
1409 if (cbp->c_flg & C_LOOP) {
1410 s++;
1411 /*
1412 * Account for the fact that this frame connects
1413 * to a previous one (thus forming a loop).
1414 */
1415 nep = &einfo[cbp->c_dir];
1416 if (--nep->e_framecnt)
1417 nep->e_emask &= ~(1 << cbp->c_voff[0]);
1418 else
1419 nep->e_emask = 0;
1420 }
1421 }
1422
1423 /*
1424 * We only need to update the emask values of "complete" loops
1425 * to include the intersection spots.
1426 */
1427 if (s && ocbp->c_combo.c.a == 2) {
1428 /* process loops from the top down */
1429 ep = &einfo[nframes];
1430 do {
1431 ep--;
1432 cbp = ep->e_combo;
1433 if (!(cbp->c_flg & C_LOOP))
1434 continue;
1435
1436 /*
1437 * Update the emask values to include the
1438 * intersection spots.
1439 */
1440 nep = &einfo[cbp->c_dir];
1441 nep->e_framecnt = 1;
1442 nep->e_emask = 1 << cbp->c_voff[0];
1443 ep->e_framecnt = 1;
1444 ep->e_emask = 1 << ep->e_off;
1445 ep = &einfo[ep->e_frameindex];
1446 do {
1447 ep->e_framecnt = 1;
1448 ep->e_emask = 1 << ep->e_off;
1449 ep = &einfo[ep->e_frameindex];
1450 } while (ep > nep);
1451 } while (ep != einfo);
1452 }
1453
1454 /* mark all the frames with the completion spots */
1455 for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) {
1456 m = ep->e_emask;
1457 cbp = *cbpp;
1458 sp = &board[cbp->c_vertex];
1459 d = dd[s = cbp->c_dir];
1460 cmask = CFLAG << s;
1461 omask = (IFLAG | CFLAG) << s;
1462 s = ep->e_fval.c.b ? 6 : 5;
1463 for (; --s >= 0; sp += d, m >>= 1)
1464 sp->s_flg |= (m & 1) ? omask : cmask;
1465 }
1466 }
1467
1468 void
1469 clearcombo(cbp, open)
1470 struct combostr *cbp;
1471 int open;
1472 {
1473 struct spotstr *sp;
1474 struct combostr *tcbp;
1475 int d, n, mask;
1476
1477 for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) {
1478 clearcombo(tcbp, cbp->c_flg & C_OPEN_1);
1479 open = cbp->c_flg & C_OPEN_0;
1480 }
1481 sp = &board[cbp->c_vertex];
1482 d = dd[n = cbp->c_dir];
1483 mask = ~((IFLAG | CFLAG) << n);
1484 n = open ? 6 : 5;
1485 for (; --n >= 0; sp += d)
1486 sp->s_flg &= mask;
1487 }
1488
1489 int
1490 list_eq(scbpp, cbpp, n)
1491 struct combostr **scbpp;
1492 struct combostr **cbpp;
1493 int n;
1494 {
1495 struct combostr **spp, **cpp;
1496
1497 spp = scbpp + n;
1498 cpp = cbpp + n;
1499 do {
1500 if (*--spp != *--cpp)
1501 return (0);
1502 } while (cpp != cbpp);
1503 /* we found a match */
1504 return (1);
1505 }
1506 #endif /* DEBUG */
Port of NetBSD games to Darwin