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