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