home *** CD-ROM | disk | FTP | other *** search
/ The Best of Mecomp Multimedia 1 / Mecomp-CD.iso / spiele / workbench / tripppin / source / trip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-07  |  11.9 KB  |  509 lines
  1. /* TO ADD:
  2.     choice of aggressive or defensive computer play (aggressive = assume you
  3.         will fuck up if given the chance) ?
  4.     requester to tell you the rules ?
  5. */
  6.  
  7.  
  8. /*
  9. This is sort of the game of TRIPPPLES ® that was marketed by some game
  10. company I forget which, and I can't find it in the stores so this
  11. implementation is based purely on my memory of having played the game years
  12. and years ago ...  the computer opponent uses a straightforward lookahead
  13. strategy of variable depth.  I wrote this mainly for practice with the
  14. graphics.library which I hadn't hardly used much yet, and just to prove I
  15. COULD write an honest-to-god event loop ... most everything else I've been
  16. writing has been CLI utilities ... It was easier than I expected; day 1 got
  17. the board displayed pretty well (the tricky part was keeping everything
  18. proportioned right on both interlaced and non-laced displays), day 2 I made
  19. player tokens that could be moved around with the mouse (took some trial and
  20. error to get the hang of using Bobs), the next evening got it to know all the
  21. rules of the game, and display the game status in the right margin, another
  22. evening got the computer opponent working, including the task synchronization
  23. ... after that it was just a matter of adding bells and whistles, like
  24. putting arrowheads on the arrows, adding a menu, flashing X's to show where
  25. the pieces are trying to go, the suggest-a-move and take-back-a-move
  26. features, stuff to make it adapt gracefully to different sized fonts ... 
  27. After the first release users gave me some suggestions which prompted me to
  28. add an option to turn off the prevention of loops, and stifle the sprites
  29. when the window is inactive or the menus are up.  I also found two bugs.
  30.  
  31. This program is written by Paul Kienitz and is placed in the public domain.
  32. */
  33.  
  34.  
  35. #include <hardware/intbits.h>
  36. #include <exec/interrupts.h>
  37. #include <libraries/dosextens.h>
  38. #include "trip.h"
  39.  
  40.  
  41.  
  42. import void ShowBoard(), TellTurn(), LiftBob(), DropBob(), DrawSquare(),
  43.         DragBob(), Play(), MakePrettyPictures(),
  44.         DropPrettyPictures(), KillAnts(), Ding();
  45.  
  46.  
  47. import adr GfxBase, IntuitionBase;
  48.  
  49.  
  50. import long startedthinking, Now();
  51.  
  52.  
  53. piece oo, bb, *turn;
  54.  
  55.  
  56. history ohist, bhist;
  57.  
  58.  
  59. ubyte board[8][8];            /* grid of 8 bit masks */
  60.  
  61. bool won = false, bluefirst = false, looprevent = true;
  62. bool thinking = false, abort_think = false, notadrill;
  63.  
  64. struct Message *wbs;            /* Workbench startup message */
  65.  
  66. short difficulty = 3, depth, thinkx, thinky, suggx, suggy, oldpri;
  67.  
  68.  
  69. short sigdone = -1, sigkillme = -1;        /* child -> parent */
  70.  
  71. struct Task *child, *parent;
  72.  
  73.  
  74. void VBsignal_func();
  75.  
  76. struct Interrupt VBsignal = {
  77.     { null, null, NT_INTERRUPT, 6, "Tripppin signaler" },    /* node */
  78.     null,            /* data - will be address of task to signal */
  79.     VBsignal_func        /* code */
  80. };
  81.  
  82.  
  83.  
  84. void Die(s) str s;
  85. {
  86.     if (child) {
  87.     RemIntServer(INTB_VERTB, &VBsignal);
  88.     Signal(child, bit(sigdie));
  89.     Wait(bit(sigkillme));
  90.     DeleteTask(child);
  91.     }
  92.     if (~sigdone)
  93.     FreeSignal((long) sigdone);
  94.     if (~sigkillme)
  95.     FreeSignal((long) sigkillme);
  96.     KillAnts();
  97.     DumpPrettyPictures();
  98.     if (IntuitionBase)
  99.     CloseLibrary(IntuitionBase);
  100.     if (GfxBase)
  101.     CloseLibrary(GfxBase);
  102.     if (s && Output())
  103.     Write(Output(), s, (long) strlen(s));
  104.     if (wbs) {
  105.     Forbid();
  106.     ReplyMsg(wbs);
  107.     } else
  108.     SetTaskPri(parent, (long) oldpri);
  109.     Exit(s ? 20L : 0L);
  110. }
  111.  
  112.  
  113.  
  114. #asm
  115.         public    _VBsignal_func,_LVOSignal
  116.  
  117. _VBsignal_func:    move.l    #sigf_tof,d0
  118.         move.l    4,a6        ; is_Data (task addr) already in a1
  119.         jsr    _LVOSignal(a6)
  120.         moveq    #0,d0        ; set the Z bit
  121.         rts            ; don't preserve a6 cause pri < 10
  122. #endasm
  123.  
  124. /* This stupid interrupt server really serves no purpose any more, all it
  125. does could be done as well by IntuiTicks.  But it's here so I'm not going to
  126. bother to take it out. */
  127.  
  128.  
  129.  
  130. void Init()
  131. {
  132.     long d[3];
  133.     void ThinkerTask();
  134.  
  135.     DateStamp(d);
  136.     srand((int) ((d[0] << 2) + (d[1] << 4) + d[2]));
  137.     if (!(GfxBase = (adr) OpenLibrary("graphics.library", 0L)))
  138.     Die("No graphics!!\n");
  139.     if (!(IntuitionBase = OpenLibrary("intuition.library", 0L)))
  140.     Die("No intuition!!\n");
  141.     MakePrettyPictures();
  142.     if (!~(sigdone = AllocSignal(-1L)) || !~(sigkillme = AllocSignal(-1L)))
  143.     Die("Couldn't allocate signals!\n");
  144.     if (!(child = CreateTask("Thinkin and Trippin", 0L, ThinkerTask, 8000L)))
  145.     Die("Couldn't create subtask!\n");
  146.     parent = FindTask(null);
  147.     VBsignal.is_Data = (adr) parent;
  148.     AddIntServer(INTB_VERTB, &VBsignal);
  149.     oo.hist = &ohist;
  150.     bb.hist = &bhist;
  151.     oo.other = &bb;
  152.     bb.other = &oo;
  153.     oo.machine = false;
  154.     bb.machine = true;
  155. }
  156.  
  157.  
  158.  
  159. void StopThinking()
  160. {
  161.     if (thinking) {
  162.     abort_think = true;
  163.     Wait(bit(sigdone));        /* thinking = false */
  164.     abort_think = false;
  165.     }
  166. }
  167.  
  168.  
  169.  
  170. void StartThinking()
  171. {
  172.     StopThinking();
  173.     suggx = suggy = -1;
  174.     abort_think = false;
  175.     notadrill = turn->machine;
  176.     depth = notadrill ? difficulty : 3;
  177.     /* just an initial value        ^^^        goes up with time */
  178.     startedthinking = Now();
  179.     thinking = true;
  180.     Signal(child, bit(sigthink));
  181. }
  182.  
  183.  
  184.  
  185. short xgoals[6] = { 4, 6, 6, 1, 1, 3 };
  186. short ygoals[6] = { 7, 6, 1, 1, 6, 7 };
  187.  
  188. void SetGoal(p) piece *p;
  189. {
  190.     short i;
  191.     i = (p == &oo ? p->reached + 1 : 4 - p->reached);
  192.     p->goalx = xgoals[i];
  193.     p->goaly = ygoals[i];
  194. }
  195.  
  196.  
  197.  
  198. short xoffs[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
  199. short yoffs[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
  200.  
  201. #define NX(x, i) ((x) + xoffs[i])
  202. #define NY(y, i) ((y) + yoffs[i])
  203.  
  204.  
  205.  
  206. void Allow(from, tu) piece *from, *tu;
  207. {
  208.     register short i, x , y;
  209.     ubyte r = 0;
  210.     for (i = 0; i < 8; i++) {
  211.     x = NX(tu->x, i);
  212.     y = NY(tu->y, i);
  213.     if (!(x & ~7) && !(y & ~7) && !(x == from->x && y == from->y))
  214.         r |= 1 << i;
  215.     }
  216.     tu->allowed = r & board[from->x][from->y];
  217. }
  218.  
  219.  
  220.  
  221. void Restart()
  222. {
  223.     Shuffle();
  224.     KillAnts();
  225.     oo.x = 4;
  226.     bb.x = 3;
  227.     oo.y = bb.y = 7;
  228.     Allow(&bb, &oo);
  229.     Allow(&oo, &bb);
  230.     oo.reached = bb.reached = 0;
  231.     SetGoal(&oo);
  232.     SetGoal(&bb);
  233.     ohist.top = bhist.top = HISTORY - 1;
  234.     ohist.count = bhist.count = 0;
  235.     turn = bluefirst ? &bb : &oo;
  236.     bluefirst = !bluefirst;
  237.     won = false;
  238.     StartThinking();
  239. }
  240.  
  241.  
  242.  
  243. void Mooove(who, x, y) piece *who; short x, y;
  244. {
  245.     register history *gh = who->hist;
  246.  
  247.     if (gh->top < HISTORY - 1)
  248.     gh->top++;
  249.     else gh->top = 0;
  250.     if (gh->count < HISTORY)
  251.     gh->count++;
  252.     gh->hx[gh->top] = who->x;
  253.     gh->hy[gh->top] = who->y;
  254.     gh->madegoal[gh->top] = x == who->goalx && y == who->goaly;
  255.     who->x = x;
  256.     who->y = y;
  257.     Allow(who, who->other);
  258.     if (gh->madegoal[gh->top])
  259.     if (!(won = ++who->reached > 4))
  260.         SetGoal(who);
  261. }
  262.  
  263.  
  264.  
  265. bool TryMove(who, x, y) piece *who; short x, y;
  266. {
  267.     short i, xd, yd;
  268.  
  269.     xd = x - who->x;
  270.     yd = y - who->y;
  271.     if (!xd && !yd)
  272.     return true;            /* give player another try */
  273.     if (xd > 1 || xd < -1 || yd > 1 || yd < -1)
  274.     return false;                /* moved too far */
  275.     if (!xd)
  276.     i = yd > 0 ? 4 : 0;
  277.     else if (xd > 0)
  278.     i = 2 + yd;
  279.     else
  280.     i = 6 - yd;
  281.     if (!(who->allowed & (1 << i)))
  282.     return false;                /* forbidden move */
  283.     KillAnts();
  284.     StopThinking();
  285.     Mooove(who, x, y);
  286.     turn = turn->other;
  287.     if (!won)
  288.     StartThinking();
  289.     TellTurn();
  290.     return true;
  291. }
  292.  
  293.  
  294.  
  295. #define max(a, b) ((a) > (b) ? (a) : (b))
  296.  
  297. #define abs(a) ((a) < 0 ? -(a) : (a))
  298.  
  299. short WayToGo(p) piece *p;        /* Way To Go, Dexter Riley! */
  300. {
  301.     register short d, dx, dy;
  302.  
  303.     dx = abs(p->x - p->goalx);
  304.     dy = abs(p->y - p->goaly);
  305.     d = max(dx, dy);
  306.     if (p->reached < 4)
  307.     d += 5 * (4 - p->reached) - 2;
  308.     return d;
  309. }
  310.  
  311.  
  312.  
  313. /* true if p's last move makes a forbidden loop - twice through is okay,
  314. starting on a third time through is forbidden.  Does not detect loops longer
  315. than HISTORY / 2. */
  316.  
  317. bool Loopin(p) piece *p;
  318. {
  319.     short len, pt, ot, pi, oi, n;
  320.     history *hp = p->hist, *ho = p->other->hist;
  321.  
  322.     for (len = 2; len <= HISTORY >> 1; len++) {
  323.     if (hp->count < len << 1)
  324.         break;
  325.     pt = (hp->top + HISTORY + 1 - len) % HISTORY;
  326.     ot = (ho->top + HISTORY + 1 - len) % HISTORY;
  327.     if (p->other->x == ho->hx[ot] && p->other->y == ho->hy[ot]
  328.                 && p->x == hp->hx[pt] && p->y == hp->hy[pt]) {
  329.         /* possible loop -- confirm: */
  330.         pi = hp->top;
  331.         oi = ho->top;
  332.         for (n = 0; n < len; n++) {
  333.         pt = (pt + HISTORY - 1) % HISTORY;
  334.         ot = (ot + HISTORY - 1) % HISTORY;
  335.         if (hp->hx[pt] != hp->hx[pi] || hp->hy[pt] != hp->hy[pi] ||
  336.              ho->hx[ot] != ho->hx[oi] || ho->hy[ot] != ho->hy[oi])
  337.             break;
  338.         pi = (pi + HISTORY - 1) % HISTORY;
  339.         oi = (oi + HISTORY - 1) % HISTORY;
  340.         }
  341.         if (n >= len)
  342.         return true;
  343.     }
  344.     }
  345.     return false;
  346. }
  347.  
  348.  
  349.  
  350. /* here we have the recursive lookahead strategy -- this function tries all
  351. the moves available to player "me" against player "it" and sets rx and ry to
  352. the best move available to "me", and returns a number that rates how well off
  353. "me" ends up.  It abandons computation and returns meaningless values if the
  354. global variable abort_think ever becomes true.  It does recursive lookahead
  355. to depth "d". */
  356.  
  357. #define EXTREME 9999
  358.  
  359. short PickBestMove(d, me, it, rx, ry) short d; piece *me, *it; short *rx, *ry;
  360. {
  361.     short i, besti, best = -EXTREME, t, go, bgo = 999;
  362.     short otop, ntop, oxx, oyy, oco;
  363.     piece p, *oooth;
  364.     history *h = me->hist;
  365.  
  366.     if (!me->allowed)
  367.     return -EXTREME;            /* I lose */
  368.     d--;
  369.     if (rx) {
  370.     t = 0;
  371.     for (i = 0; i <= 7; i++)
  372.         if (me->allowed & (1 << i)) {
  373.         t++;
  374.         *rx = NX(me->x, i);
  375.         *ry = NY(me->y, i);
  376.         }
  377.     if (t == 1) return 0;     /* only legal move, skip other thinking */
  378.     }
  379.  
  380.     otop = h->top;
  381.     oco = h->count;
  382.     if (h->count < HISTORY)
  383.     h->count++;
  384.     if (otop < HISTORY - 1)
  385.     ntop = otop + 1;
  386.     else ntop = 0;
  387.     h->top = ntop;
  388.     oxx = h->hx[ntop];
  389.     oyy = h->hy[ntop];
  390.     h->hx[ntop] = me->x;
  391.     h->hy[ntop] = me->y;
  392.     oooth = it->other;
  393.     it->other = &p;
  394.  
  395.     for (i = 0; i <= 7; i++)
  396.     if (me->allowed & (1 << i)) {
  397.         if (abort_think)
  398.         return 0;
  399.         p = *me;
  400.         p.x = NX(p.x, i);
  401.         p.y = NY(p.y, i);
  402.         if (p.x == p.goalx && p.y == p.goaly)
  403.         if (++p.reached > 4) {
  404.             if (rx)
  405.             *rx = p.x, *ry = p.y;
  406.             best = EXTREME;        /* I win */
  407.             break;
  408.         } else SetGoal(&p);
  409.         if (d <= 0)
  410.         t = WayToGo(it) - WayToGo(&p);
  411.         else {
  412.         ubyte a = it->allowed;
  413.         Allow(&p, it);
  414.         t = - PickBestMove(d, it, &p, null, null);
  415.         it->allowed = a;
  416.         }               /* VVV oops, forgot that! */
  417.         if (rx && looprevent && notadrill && Loopin(&p))
  418.         t -= EXTREME << 1;
  419.         go = WayToGo(&p);
  420.         if (t > best || (t == best && go < bgo)) {
  421.         best = t;
  422.         besti = i;
  423.         bgo = go;
  424.         if (rx)
  425.             *rx = p.x, *ry = p.y;
  426.         }
  427.     }
  428.  
  429.     it->other = oooth;
  430.     h->hx[ntop] = oxx;
  431.     h->hy[ntop] = oyy;
  432.     h->count = oco;
  433.     h->top = otop;
  434.     return best;
  435. }
  436.  
  437.  
  438.  
  439. /* the following is started up as a separate task to calculate the best move.
  440. When it gets the "sigthink" signal it looks in the global variables for what
  441. to think about.  It signals the parent when finished or aborted.  When not
  442. aborted it puts the move that the player whose turn it is should make in the
  443. global vars thinkx and thinky. */
  444.  
  445. void ThinkerTask()
  446. {
  447.     piece who, whom;
  448.     history wo, wm;
  449.  
  450.     geta4();
  451.     for (;;) {
  452.     if (Wait(bit(sigthink) | bit(sigdie)) & bit(sigdie)) {
  453.         Signal(parent, bit(sigkillme));
  454.         Wait(0L);
  455.     }
  456.     thinking = true;
  457.     who = *turn;
  458.     whom = *who.other;
  459.     who.other = &whom;
  460.     whom.other = &who;
  461.     wo = *who.hist;
  462.     wm = *whom.hist;
  463.     who.hist = &wo;
  464.     whom.hist = &wm;
  465.     PickBestMove(depth, &who, &whom, &thinkx, &thinky);
  466.     Forbid();
  467.     thinking = false;
  468.     Signal(parent, bit(sigdone));
  469.     Permit();
  470.     }
  471. }
  472.  
  473.  
  474.  
  475. void MachineMove()
  476. {
  477.     piece *who;
  478.     short oldx, oldy;
  479.  
  480.     oldx = turn->x;
  481.     oldy = turn->y;
  482.     Mooove(turn, thinkx, thinky);
  483.     LiftBob(turn);
  484.     DrawSquare(oldx, oldy);        /* erase old image from rastport */
  485.     DropBob(turn);            /* draw in new position */
  486.     turn = turn->other;
  487.     if (!won)
  488.     StartThinking();
  489.     TellTurn();
  490. }
  491.  
  492.  
  493.  
  494. long _main()
  495. {
  496.     struct Process *me = ThisProcess();
  497.     if (!me->pr_CLI) {
  498.     WaitPort(&me->pr_MsgPort);
  499.     wbs = GetMsg(&me->pr_MsgPort);
  500.     }
  501.     Init();
  502.     Restart();
  503.     ShowBoard();
  504.     if (me->pr_Task.tc_Node.ln_Pri <= 0)
  505.     oldpri = SetTaskPri(me, 1L);
  506.     Play();
  507.     Die(null);
  508. }
  509.