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