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