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