home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 047.lha / maze.c < prev    next >
C/C++ Source or Header  |  1986-11-20  |  9KB  |  397 lines
  1. /* Original code by Eddie Shields from C64 */
  2. /* Solve routine by David Flynn            */
  3. /* Intuition interface and rest by Charles J Carter */
  4. /* Usage:
  5.  * Run Maze
  6.  * click LEFT mouse button on Make Maze; do NOT use front back gadget now
  7.  * When Maze is finished use front back gadget to get to CLI
  8.  * Run Lens
  9.  * Use front back gadget to get back to Maze; click left button to make active
  10.  * Object is to get from upper left hand corner to lower right hand corner
  11.  * Use cursor keys or Keypad 2,4,6,8 to move to next junction;
  12.  * Use Solve Maze to automatically solve maze; good for demo
  13.  * Use Quit or Close gadget to Quit
  14.  */
  15.  
  16.  
  17. #include <exec/types.h>
  18. #include <intuition/intuitionbase.h>
  19. #include <graphics/gfxbase.h>
  20.  
  21.  
  22. extern unsigned short rand();
  23. extern long time();
  24.  
  25. #define DEPTH 2L
  26. #define WIDTH 640L
  27. #define HEIGHT 200L
  28. #define TOP 8L
  29.  
  30. struct RastPort *rp;
  31.  
  32. long x,y;
  33. int list[8];
  34.  
  35. #define INTUITION_REV 0L
  36. #define GRAPHICS_REV  0L
  37.  
  38. struct IntuitionBase *IntuitionBase;
  39. struct GfxBase *GfxBase;
  40.  
  41. struct NewWindow NewWindow = {
  42.    0,0,
  43.    640,200,
  44.    0,
  45.    1,
  46.    CLOSEWINDOW | MOUSEBUTTONS | RAWKEY,
  47.    WINDOWCLOSE | SMART_REFRESH | ACTIVATE |
  48.       WINDOWDEPTH | REPORTMOUSE | BORDERLESS,
  49.    NULL,
  50.    NULL,
  51.    (unsigned char *)" AMY MAZE | Quit | Make Maze | Solve Maze |",
  52.    NULL,
  53.    NULL,
  54.    0, 0,
  55.    640, 200,
  56.    WBENCHSCREEN,
  57. };
  58.  
  59. /******************/
  60. /*      Main      */
  61. /******************/
  62.  
  63. extern struct IntuitionBase *OpenLibrary();
  64. extern struct Window *OpenWindow();
  65. extern struct IntuiMessage *GetMsg();
  66. struct Window *win;
  67. main(argc,argv)
  68. int argc;
  69. char *argv[];
  70. {
  71.    struct IntuiMessage *NewMessage;
  72.    ULONG class;
  73.    USHORT code;
  74.    
  75.    USHORT pix;
  76.    int dir,mx,my;
  77.  
  78.    SHORT KeepGoing = TRUE;
  79.  
  80.    IntuitionBase = OpenLibrary("intuition.library", INTUITION_REV);
  81.    if( IntuitionBase == NULL )
  82.       exit(FALSE);
  83.  
  84.    GfxBase = (struct GfxBase *)OpenLibrary("graphics.library",GRAPHICS_REV);
  85.    if( GfxBase == NULL )
  86.       exit(FALSE);
  87.  
  88.    if(( win = OpenWindow(&NewWindow) ) == NULL)
  89.       exit(FALSE);
  90.  
  91.    rp=win->RPort;
  92.  
  93.    while(KeepGoing)
  94.    {
  95.       Wait( 1L << win->UserPort->mp_SigBit);
  96.       while(NewMessage=GetMsg(win->UserPort))
  97.       {
  98.          class = NewMessage->Class;
  99.          code = NewMessage->Code;
  100.          mx = NewMessage->MouseX;
  101.          my = NewMessage->MouseY;
  102.          ReplyMsg( NewMessage );
  103.          if (class==CLOSEWINDOW) KeepGoing = FALSE;
  104.          if (class==MOUSEBUTTONS && code==SELECTUP)
  105.          {
  106.             if(my<TOP)
  107.             {
  108.                if(mx>115&&mx<368)
  109.                {
  110.                   if (mx<172) KeepGoing = FALSE;
  111.                   else if (mx<266) domaze();
  112.                   else if (mx<368) solvemaze();
  113.                }
  114.             }
  115.          }
  116.          if (class==RAWKEY)
  117.          {
  118.             switch(code)
  119.             {
  120.                case 0x4c: case 0x3e: /* up */
  121.                   if((pix=readpixel(rp->BitMap,x,y-1))==0)
  122.                   {
  123.                      SetAPen(rp,2L);
  124.                      update(3);
  125.                      writepixel(rp,x,y);
  126.                      while((dir=findpath())!=-1)
  127.                      {
  128.                         update(dir);
  129.                         writepixel(rp,x,y);
  130.                      }
  131.                   }
  132.                   else if(pix==2||pix==1)
  133.                   {
  134.                      SetAPen(rp,1L);
  135.                      writepixel(rp,x,y);
  136.                      update(3);
  137.                   }
  138.                   break;
  139.                case 0x4d: case 0x1e: /* down */
  140.                   if((pix=readpixel(rp->BitMap,x,y+1))==0)
  141.                   {
  142.                      SetAPen(rp,2L);
  143.                      update(1);
  144.                      writepixel(rp,x,y);
  145.                      while((dir=findpath())!=-1)
  146.                      {
  147.                         update(dir);
  148.                         writepixel(rp,x,y);
  149.                      }
  150.                   }
  151.                   else if(pix==2||pix==1)
  152.                   {
  153.                      SetAPen(rp,1L);
  154.                      writepixel(rp,x,y);
  155.                      update(1);
  156.                   }
  157.                   break;
  158.                case 0x4f: case 0x2d: /* left */
  159.                   if((pix=readpixel(rp->BitMap,x-1,y))==0)
  160.                   {
  161.                      SetAPen(rp,2L);
  162.                      update(0);
  163.                      writepixel(rp,x,y);
  164.                      while((dir=findpath())!=-1)
  165.                      {
  166.                         update(dir);
  167.                         writepixel(rp,x,y);
  168.                      }
  169.                   }
  170.                   else if(pix==2||pix==1)
  171.                   {
  172.                      SetAPen(rp,1L);
  173.                      writepixel(rp,x,y);
  174.                      update(0);
  175.                   }
  176.                   break;
  177.                case 0x4e: case 0x2f: /* right */
  178.                   if((pix=readpixel(rp->BitMap,x+1,y))==0)
  179.                   {
  180.                      SetAPen(rp,2L);
  181.                      update(2);
  182.                      writepixel(rp,x,y);
  183.                      while((dir=findpath())!=-1)
  184.                      {
  185.                         update(dir);
  186.                         writepixel(rp,x,y);
  187.                      }
  188.                   }
  189.                   else if(pix==2||pix==1)
  190.                   {
  191.                      SetAPen(rp,1L);
  192.                      writepixel(rp,x,y);
  193.                      update(2);
  194.                   }
  195.                   break;
  196.                default:
  197.                   break;
  198.             }
  199.          }
  200.          if((x==WIDTH-4)&&(y==HEIGHT-4)) domaze();
  201.       }
  202.    }
  203.  
  204.    CloseWindow(win);
  205.    CloseLibrary(GfxBase);
  206.    CloseLibrary(IntuitionBase);
  207. }
  208.  
  209. domaze()
  210. {
  211.    long i;
  212.  
  213.    srand((unsigned short)time());
  214.  
  215.    SetDrMd(rp,JAM1);
  216.    SetRast(rp,3L);
  217.    RethinkDisplay();
  218.    SetAPen(rp,0L);
  219.    Move(rp,0L,TOP);
  220.    Draw(rp,WIDTH-2,TOP);
  221.    Draw(rp,WIDTH-2,HEIGHT-2);
  222.    Draw(rp,0L,HEIGHT-2);
  223.    Draw(rp,0L,TOP);
  224.    Move(rp,WIDTH-1,TOP);
  225.    Draw(rp,WIDTH-1,HEIGHT-1);
  226.    Draw(rp,0L,HEIGHT-1);
  227.  
  228.    x = 2;   y = TOP+2;
  229.    writepixel(rp,x,y);
  230.    do { sketch(); } while (backtrack());
  231.    SetAPen(rp,2L);
  232.    x = 2;   y = TOP+2;
  233.    writepixel(rp,x,y);
  234. }
  235.  
  236. solvemaze()
  237. {
  238.    x = 2;   y = TOP+2;
  239.    writepixel(rp,x,y);
  240.    while (solve()) backsolve();
  241. }
  242.  
  243. sketch()
  244. {
  245.    int dir;
  246.    SetAPen(rp,1L);
  247.    while ((dir = finddir())!=-1)
  248.    {
  249.       update(dir); writepixel(rp,x,y);
  250.       update(dir); writepixel(rp,x,y);
  251.    }
  252. }
  253.  
  254. backtrack()
  255. {
  256.    int dir;
  257.    SetAPen(rp,0L);
  258.    while (finddir() == -1)
  259.    {
  260.       if((dir = finddirback()) == -1) return(0);
  261.       writepixel(rp,x,y); update(dir);
  262.       writepixel(rp,x,y); update(dir);
  263.    }
  264.    return(1);
  265. }
  266.  
  267. solve()
  268. {
  269.    int dir;
  270.    SetAPen(rp,2L);
  271.    while ((dir = finddirsolve()) != -1)
  272.    {
  273.       update(dir); writepixel(rp,x,y);
  274.       update(dir); writepixel(rp,x,y);
  275.       if((x==WIDTH-4)&&(y==HEIGHT-4)) return(0);
  276.    }
  277.    return(1);
  278. }
  279.  
  280. backsolve()
  281. {
  282.    int dir;
  283.    SetAPen(rp,1L);
  284.    while (finddirsolve() == -1)
  285.    {
  286.       dir=finddirbacksolve();
  287.       writepixel(rp,x,y); update(dir);
  288.       writepixel(rp,x,y); update(dir);
  289.    }
  290. }
  291.  
  292. finddir()
  293. {
  294.   UWORD c = 0;
  295.  
  296.   if(readpixel(rp->BitMap,x-2,y)==3) {list[c++]=0;list[c++]=0;list[c++]=0;}
  297.   if(readpixel(rp->BitMap,x,y+2)==3) list[c++]=1;
  298.   if(readpixel(rp->BitMap,x+2,y)==3) {list[c++]=2;list[c++]=2;list[c++]=2;}
  299.   if(readpixel(rp->BitMap,x,y-2)==3) list[c++]=3;
  300.   if(c==0)return(-1);
  301.   return(list[rand()%c]);
  302. }
  303.  
  304. finddirback()
  305. {
  306.   if(readpixel(rp->BitMap,x-1,y)==1) return(0);
  307.   if(readpixel(rp->BitMap,x,y+1)==1) return(1);
  308.   if(readpixel(rp->BitMap,x+1,y)==1) return(2);
  309.   if(readpixel(rp->BitMap,x,y-1)==1) return(3);
  310.   return(-1);
  311. }
  312.  
  313. finddirsolve()
  314. {
  315.   UWORD c = 0;
  316.  
  317.   if(!readpixel(rp->BitMap,x-1,y)) list[c++]=0;
  318.   if(!readpixel(rp->BitMap,x,y+1)) list[c++]=1;
  319.   if(!readpixel(rp->BitMap,x+1,y)) list[c++]=2;
  320.   if(!readpixel(rp->BitMap,x,y-1)) list[c++]=3;
  321.   if(c==0)return(-1);
  322.   return(list[rand()%c]);
  323. }
  324.  
  325. findpath()
  326. {
  327.   UWORD c = 0;
  328.  
  329.   if(!readpixel(rp->BitMap,x-1,y)) list[c++]=0;
  330.   if(!readpixel(rp->BitMap,x,y+1)) list[c++]=1;
  331.   if(!readpixel(rp->BitMap,x+1,y)) list[c++]=2;
  332.   if(!readpixel(rp->BitMap,x,y-1)) list[c++]=3;
  333.   if(c!=1)return(-1);
  334.   return(list[0]);
  335. }
  336.  
  337. finddirbacksolve()
  338. {
  339.   if(readpixel(rp->BitMap,x-1,y)==2) return(0);
  340.   if(readpixel(rp->BitMap,x,y+1)==2) return(1);
  341.   if(readpixel(rp->BitMap,x+1,y)==2) return(2);
  342.   if(readpixel(rp->BitMap,x,y-1)==2) return(3);
  343.   return(-1);
  344. }
  345.  
  346. update(a)
  347. int a;
  348. {
  349.         if(a==0)--x; /* left */
  350.    else if(a==1)y++; /* down */
  351.    else if(a==2)x++; /* right */
  352.    else if(a==3)--y; /* up */
  353. }
  354.  
  355. readpixel(bm,x,y)
  356. struct BitMap *bm;
  357. long x,y;
  358. {
  359.    int color,p,bv;
  360.    UBYTE **plane;
  361.    UBYTE bit;
  362.    long offset;
  363.  
  364.    offset = (x>>3)+(y*bm->BytesPerRow);
  365.    bit    = 0x80>>(x&0x07);
  366.    plane  = (UBYTE**)bm->Planes;
  367.    bv     = 1;
  368.    color  = 0;
  369.  
  370.    for(p=bm->Depth;p;--p,bv<<=1,plane++)
  371.      if(*(*plane+offset)&bit) color+=bv;
  372.    return(color);
  373. }
  374.  
  375. writepixel(rp,x,y)
  376. struct RastPort *rp;
  377. long x,y;
  378. {
  379.    struct BitMap *bm;
  380.    int color,p,bv;
  381.    UBYTE **plane;
  382.    UBYTE bit;
  383.    long offset;
  384.  
  385.    bm = rp->BitMap;
  386.    offset = (x>>3)+(y*bm->BytesPerRow);
  387.    bit    = 0x80>>(x&0x07);
  388.    plane  = (UBYTE**)&(bm->Planes[0]);
  389.    bv     = 1;
  390.    color  = rp->FgPen;
  391.  
  392.    for(p=bm->Depth;p;--p,bv<<=1,plane++)
  393.      if(color&bv) *(*plane+offset)|=bit;
  394.      else *(*plane+offset)&=(~bit);
  395. }
  396.  
  397.