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