/* Original code by Eddie Shields from C64 */
/* Solve routine by David Flynn            */
/* Intuition interface and rest by Charles J Carter */
/* Usage:
 * Run Maze
 * click LEFT mouse button on Make Maze; do NOT use front back gadget now
 * When Maze is finished use front back gadget to get to CLI
 * Run Lens
 * Use front back gadget to get back to Maze; click left button to make active
 * Object is to get from upper left hand corner to lower right hand corner
 * Use cursor keys or Keypad 2,4,6,8 to move to next junction;
 * Use Solve Maze to automatically solve maze; good for demo
 * Use Quit or Close gadget to Quit
 */


#include <exec/types.h>
#include <intuition/intuitionbase.h>
#include <graphics/gfxbase.h>


extern unsigned short rand();
extern long time();

#define DEPTH 2L
#define WIDTH 640L
#define HEIGHT 200L
#define TOP 8L

struct RastPort *rp;

long x,y;
int list[8];

#define INTUITION_REV 0L
#define GRAPHICS_REV  0L

struct IntuitionBase *IntuitionBase;
struct GfxBase *GfxBase;

struct NewWindow NewWindow = {
   0,0,
   640,200,
   0,
   1,
   CLOSEWINDOW | MOUSEBUTTONS | RAWKEY,
   WINDOWCLOSE | SMART_REFRESH | ACTIVATE |
      WINDOWDEPTH | REPORTMOUSE | BORDERLESS,
   NULL,
   NULL,
   (unsigned char *)" AMY MAZE | Quit | Make Maze | Solve Maze |",
   NULL,
   NULL,
   0, 0,
   640, 200,
   WBENCHSCREEN,
};

/******************/
/*      Main      */
/******************/

extern struct IntuitionBase *OpenLibrary();
extern struct Window *OpenWindow();
extern struct IntuiMessage *GetMsg();
struct Window *win;
main(argc,argv)
int argc;
char *argv[];
{
   struct IntuiMessage *NewMessage;
   ULONG class;
   USHORT code;
   
   USHORT pix;
   int dir,mx,my;

   SHORT KeepGoing = TRUE;

   IntuitionBase = OpenLibrary("intuition.library", INTUITION_REV);
   if( IntuitionBase == NULL )
      exit(FALSE);

   GfxBase = (struct GfxBase *)OpenLibrary("graphics.library",GRAPHICS_REV);
   if( GfxBase == NULL )
      exit(FALSE);

   if(( win = OpenWindow(&NewWindow) ) == NULL)
      exit(FALSE);

   rp=win->RPort;

   while(KeepGoing)
   {
      Wait( 1L << win->UserPort->mp_SigBit);
      while(NewMessage=GetMsg(win->UserPort))
      {
         class = NewMessage->Class;
         code = NewMessage->Code;
         mx = NewMessage->MouseX;
         my = NewMessage->MouseY;
         ReplyMsg( NewMessage );
         if (class==CLOSEWINDOW) KeepGoing = FALSE;
         if (class==MOUSEBUTTONS && code==SELECTUP)
         {
            if(my<TOP)
            {
               if(mx>115&&mx<368)
               {
                  if (mx<172) KeepGoing = FALSE;
                  else if (mx<266) domaze();
                  else if (mx<368) solvemaze();
               }
            }
         }
         if (class==RAWKEY)
         {
            switch(code)
            {
               case 0x4c: case 0x3e: /* up */
                  if((pix=readpixel(rp->BitMap,x,y-1))==0)
                  {
                     SetAPen(rp,2L);
                     update(3);
                     writepixel(rp,x,y);
                     while((dir=findpath())!=-1)
                     {
                        update(dir);
                        writepixel(rp,x,y);
                     }
                  }
                  else if(pix==2||pix==1)
                  {
                     SetAPen(rp,1L);
                     writepixel(rp,x,y);
                     update(3);
                  }
                  break;
               case 0x4d: case 0x1e: /* down */
                  if((pix=readpixel(rp->BitMap,x,y+1))==0)
                  {
                     SetAPen(rp,2L);
                     update(1);
                     writepixel(rp,x,y);
                     while((dir=findpath())!=-1)
                     {
                        update(dir);
                        writepixel(rp,x,y);
                     }
                  }
                  else if(pix==2||pix==1)
                  {
                     SetAPen(rp,1L);
                     writepixel(rp,x,y);
                     update(1);
                  }
                  break;
               case 0x4f: case 0x2d: /* left */
                  if((pix=readpixel(rp->BitMap,x-1,y))==0)
                  {
                     SetAPen(rp,2L);
                     update(0);
                     writepixel(rp,x,y);
                     while((dir=findpath())!=-1)
                     {
                        update(dir);
                        writepixel(rp,x,y);
                     }
                  }
                  else if(pix==2||pix==1)
                  {
                     SetAPen(rp,1L);
                     writepixel(rp,x,y);
                     update(0);
                  }
                  break;
               case 0x4e: case 0x2f: /* right */
                  if((pix=readpixel(rp->BitMap,x+1,y))==0)
                  {
                     SetAPen(rp,2L);
                     update(2);
                     writepixel(rp,x,y);
                     while((dir=findpath())!=-1)
                     {
                        update(dir);
                        writepixel(rp,x,y);
                     }
                  }
                  else if(pix==2||pix==1)
                  {
                     SetAPen(rp,1L);
                     writepixel(rp,x,y);
                     update(2);
                  }
                  break;
               default:
                  break;
            }
         }
         if((x==WIDTH-4)&&(y==HEIGHT-4)) domaze();
      }
   }

   CloseWindow(win);
   CloseLibrary(GfxBase);
   CloseLibrary(IntuitionBase);
}

domaze()
{
   long i;

   srand((unsigned short)time());

   SetDrMd(rp,JAM1);
   SetRast(rp,3L);
   RethinkDisplay();
   SetAPen(rp,0L);
   Move(rp,0L,TOP);
   Draw(rp,WIDTH-2,TOP);
   Draw(rp,WIDTH-2,HEIGHT-2);
   Draw(rp,0L,HEIGHT-2);
   Draw(rp,0L,TOP);
   Move(rp,WIDTH-1,TOP);
   Draw(rp,WIDTH-1,HEIGHT-1);
   Draw(rp,0L,HEIGHT-1);

   x = 2;   y = TOP+2;
   writepixel(rp,x,y);
   do { sketch(); } while (backtrack());
   SetAPen(rp,2L);
   x = 2;   y = TOP+2;
   writepixel(rp,x,y);
}

solvemaze()
{
   x = 2;   y = TOP+2;
   writepixel(rp,x,y);
   while (solve()) backsolve();
}

sketch()
{
   int dir;
   SetAPen(rp,1L);
   while ((dir = finddir())!=-1)
   {
      update(dir); writepixel(rp,x,y);
      update(dir); writepixel(rp,x,y);
   }
}

backtrack()
{
   int dir;
   SetAPen(rp,0L);
   while (finddir() == -1)
   {
      if((dir = finddirback()) == -1) return(0);
      writepixel(rp,x,y); update(dir);
      writepixel(rp,x,y); update(dir);
   }
   return(1);
}

solve()
{
   int dir;
   SetAPen(rp,2L);
   while ((dir = finddirsolve()) != -1)
   {
      update(dir); writepixel(rp,x,y);
      update(dir); writepixel(rp,x,y);
      if((x==WIDTH-4)&&(y==HEIGHT-4)) return(0);
   }
   return(1);
}

backsolve()
{
   int dir;
   SetAPen(rp,1L);
   while (finddirsolve() == -1)
   {
      dir=finddirbacksolve();
      writepixel(rp,x,y); update(dir);
      writepixel(rp,x,y); update(dir);
   }
}

finddir()
{
  UWORD c = 0;

  if(readpixel(rp->BitMap,x-2,y)==3) {list[c++]=0;list[c++]=0;list[c++]=0;}
  if(readpixel(rp->BitMap,x,y+2)==3) list[c++]=1;
  if(readpixel(rp->BitMap,x+2,y)==3) {list[c++]=2;list[c++]=2;list[c++]=2;}
  if(readpixel(rp->BitMap,x,y-2)==3) list[c++]=3;
  if(c==0)return(-1);
  return(list[rand()%c]);
}

finddirback()
{
  if(readpixel(rp->BitMap,x-1,y)==1) return(0);
  if(readpixel(rp->BitMap,x,y+1)==1) return(1);
  if(readpixel(rp->BitMap,x+1,y)==1) return(2);
  if(readpixel(rp->BitMap,x,y-1)==1) return(3);
  return(-1);
}

finddirsolve()
{
  UWORD c = 0;

  if(!readpixel(rp->BitMap,x-1,y)) list[c++]=0;
  if(!readpixel(rp->BitMap,x,y+1)) list[c++]=1;
  if(!readpixel(rp->BitMap,x+1,y)) list[c++]=2;
  if(!readpixel(rp->BitMap,x,y-1)) list[c++]=3;
  if(c==0)return(-1);
  return(list[rand()%c]);
}

findpath()
{
  UWORD c = 0;

  if(!readpixel(rp->BitMap,x-1,y)) list[c++]=0;
  if(!readpixel(rp->BitMap,x,y+1)) list[c++]=1;
  if(!readpixel(rp->BitMap,x+1,y)) list[c++]=2;
  if(!readpixel(rp->BitMap,x,y-1)) list[c++]=3;
  if(c!=1)return(-1);
  return(list[0]);
}

finddirbacksolve()
{
  if(readpixel(rp->BitMap,x-1,y)==2) return(0);
  if(readpixel(rp->BitMap,x,y+1)==2) return(1);
  if(readpixel(rp->BitMap,x+1,y)==2) return(2);
  if(readpixel(rp->BitMap,x,y-1)==2) return(3);
  return(-1);
}

update(a)
int a;
{
        if(a==0)--x; /* left */
   else if(a==1)y++; /* down */
   else if(a==2)x++; /* right */
   else if(a==3)--y; /* up */
}

readpixel(bm,x,y)
struct BitMap *bm;
long x,y;
{
   int color,p,bv;
   UBYTE **plane;
   UBYTE bit;
   long offset;

   offset = (x>>3)+(y*bm->BytesPerRow);
   bit    = 0x80>>(x&0x07);
   plane  = (UBYTE**)bm->Planes;
   bv     = 1;
   color  = 0;

   for(p=bm->Depth;p;--p,bv<<=1,plane++)
     if(*(*plane+offset)&bit) color+=bv;
   return(color);
}

writepixel(rp,x,y)
struct RastPort *rp;
long x,y;
{
   struct BitMap *bm;
   int color,p,bv;
   UBYTE **plane;
   UBYTE bit;
   long offset;

   bm = rp->BitMap;
   offset = (x>>3)+(y*bm->BytesPerRow);
   bit    = 0x80>>(x&0x07);
   plane  = (UBYTE**)&(bm->Planes[0]);
   bv     = 1;
   color  = rp->FgPen;

   for(p=bm->Depth;p;--p,bv<<=1,plane++)
     if(color&bv) *(*plane+offset)|=bit;
     else *(*plane+offset)&=(~bit);
}