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