#include <exec/types.h>
#include <intuition/intuition.h>
#include <functions.h>
#include <graphics/gfxmacros.h>
#include <graphics/text.h>
struct IntuitionBase *IntuitionBase;
struct GfxBase       *GfxBase;

struct RastPort  tmpRPactual;
struct RastPort *tmpRP = &tmpRPactual;
struct BitMap    tmpBM;

struct TextAttr font = {
        (STRPTR)"topaz.font",   /* Font Name */
        TOPAZ_EIGHTY,    /* Font Height */
        FS_NORMAL,      /* Font Style */
        FPF_ROMFONT     /* Preferences */
        };

#define tmpBMxy 60L

#define windowW 552L
#define windowH 183L

struct NewWindow nw = {
      6, 12, windowW, windowH,      /* EDGES, SIZE */
      0, 1,                         /* PENS */
      CLOSEWINDOW,                  /* IDCMPFlags */
      WINDOWDRAG  | WINDOWDEPTH |   /* Flags (requested window features)*/
        WINDOWCLOSE | ACTIVATE | REPORTMOUSE,
      NULL,                         /* gadgets */
      NULL,                         /* checkmark image */
      NULL,                         /* title */
      NULL,                         /* screen */
      NULL,                         /* bitmap */
      0,0,0,0,                      /* min and max w and h */
      WBENCHSCREEN,                 /* TYPE */
      };


struct IntuiText it_GiveUp = {
        0,1,        /* frontpen, backpen */
        JAM1,       /* drawmode */
        1,1,        /* leftedge, topedge */
        &font,       /* TextAttr * ITextFont */
        (UBYTE *)" Give Up! ",  /* IText */
        NULL,       /* NextText */
        };
struct MenuItem mi_GiveUp = {
        (struct MenuItem *) NULL,
        0,40,                        /* LeftEdge, TopEdge */
        21*9,10,                    /* Width, Height */
        ITEMTEXT | HIGHCOMP | ITEMENABLED,        /* Flags */
        0,                          /* Mutual Exclude */
        (APTR)&it_GiveUp,           /* ItemFill */
        NULL,                       /* SelectFill */
        0,                          /* Command    */
        NULL,                       /* Subitem */
        0,                          /* NextSelect */
        };

struct IntuiText it_3Level = {
        0,1,        /* frontpen, backpen */
        JAM1,       /* drawmode */
        1,1,        /* leftedge, topedge */
        &font,       /* TextAttr * ITextFont */
        (UBYTE *)"New 3-Level Maze",  /* IText */
        NULL,       /* NextText */
        };
struct MenuItem mi_3Level = {
        (struct MenuItem *) &mi_GiveUp,
        0,30,                        /* LeftEdge, TopEdge */
        21*9,10,                    /* Width, Height */
        ITEMTEXT | HIGHCOMP | ITEMENABLED,        /* Flags */
        0,                          /* Mutual Exclude */
        (APTR)&it_3Level,           /* ItemFill */
        NULL,                       /* SelectFill */
        0,                          /* Command    */
        NULL,                       /* Subitem */
        0,                          /* NextSelect */
        };

struct IntuiText it_2Level = {
        0,1,        /* frontpen, backpen */
        JAM1,       /* drawmode */
        1,1,        /* leftedge, topedge */
        &font,       /* TextAttr * ITextFont */
        (UBYTE *)"New 2-Level Maze",  /* IText */
        NULL,       /* NextText */
        };
struct MenuItem mi_2Level = {
        (struct MenuItem *) &mi_3Level,
        0,20,                      /* LeftEdge, TopEdge */
        21*9,10,                    /* Width, Height */
        ITEMTEXT | HIGHCOMP | ITEMENABLED,        /* Flags */
        0,                          /* Mutual Exclude */
        (APTR)&it_2Level,           /* ItemFill */
        NULL,                       /* SelectFill */
        0,                          /* Command    */
        NULL,                       /* Subitem */
        0,                          /* NextSelect */
        };
struct IntuiText it_1Level = {
        0,1,        /* frontpen, backpen */
        JAM1,       /* drawmode */
        1,1,        /* leftedge, topedge */
        &font,       /* TextAttr * ITextFont */
        (UBYTE *)"New 1-Level Maze",  /* IText */
        NULL,       /* NextText */
        };
struct MenuItem mi_1Level = {
        (struct MenuItem *)&mi_2Level,
        0,10,                      /* LeftEdge, TopEdge */
        21*9,10,                    /* Width, Height */
        ITEMTEXT | HIGHCOMP | ITEMENABLED,        /* Flags */
        0,                          /* Mutual Exclude */
        (APTR)&it_1Level,            /* ItemFill */
        NULL,                       /* SelectFill */
        0,                          /* Command    */
        NULL,                       /* Subitem */
        0,                          /* NextSelect */
        };

struct IntuiText it_About = {
        0,1,        /* frontpen, backpen */
        JAM1,       /* drawmode */
        1,1,        /* leftedge, topedge */
        &font,       /* TextAttr * ITextFont */
        (UBYTE *)"About TML's AmigaMaze",  /* IText */
        NULL,      /* NextText */
        };
struct MenuItem mi_About = {
        (struct MenuItem *) &mi_1Level,
        0,0,                      /* LeftEdge, TopEdge */
        21*9,10,                    /* Width, Height */
        ITEMTEXT | HIGHCOMP | ITEMENABLED,        /* Flags */
        0,                          /* Mutual Exclude */
        (APTR)&it_About,            /* ItemFill */
        NULL,                       /* SelectFill */
        0,                          /* Command    */
        NULL,                       /* Subitem */
        0,                         /* NextSelect */
        };
struct Menu menu = {
        (struct Menu *) NULL,    /* NEXT menu */
        0, 0, 12*9, 0,           /* LeftEdge, TopEdge, Width, Height */
        MENUENABLED,             /* Flags */
        (BYTE *) "Maze Control", /* MenuName */
        (struct MenuItem *)&mi_About,            /* First item */
        0,0,0,0,                /* JazzX,JazzY, BeatX, BeatY */
        };

struct Window *window;

/* BEWARE: NOWHERE has a dual nature, being used as a doesn't-go-anywhere
   indicator, and also as an invalid level marker!!!   */
#define NOWHERE -1
#define SOUTH    0
#define EAST     1
#define WEST     2
#define NORTH    3

#define SOLVED   -3

#define DIRECTIONS 4
#define MAXLEVELS  3
#define BOARDMAXX 36
#define BOARDMAXY 29
/*** the following are "inpath" stata. (see struct square) *******/
#define NOTTRAVERSED  1
#define EDGE          2
#define LASTPIECE     3 + 32
#define FIRSTPIECE    3 + 64
#define CURPIECE      3 + 96
#define TRAVERSED     3

#define MIDCMP1 CLOSEWINDOW|MOUSEMOVE|MOUSEBUTTONS|MENUPICK|MENUVERIFY
#define MIDCMP2 REQCLEAR
#define MIDCMP3 CLOSEWINDOW

extern ULONG RangeRand();
extern int about();
extern int cycle();

typedef struct {
       int conlev[ DIRECTIONS ]; /** level connected to in each dir. **/
       int inpath;  /** Also the color this should be drawn in.  **/
       int compass; /** Which direction to go to get home from here **/
       } square;

typedef square BOARD[ BOARDMAXX+1 ][ BOARDMAXY+1 ][ MAXLEVELS ];

BOARD board;

struct RastPort *rp;

int StartX, StartY, StartLevel;
int EndX,   EndY,   EndLevel;

int CurX,   CurY,   CurLevel;
int NewX,   NewY,   NewLevel;
int MouseX, MouseY;
int MinLevel, MaxLevel;
int BoardMaxX = BOARDMAXX;
int BoardMaxY = BOARDMAXY;
int SquareXsize = 34;
int SquareYsize = 18;

/* We need to have some Fill patterns for various places.  Here goes... */
USHORT Pat_Normal[] = {  /** the normal filled pattern **/
       0xffff,  /* plane 1 pattern */
       0xffff,
       0xffff,  /* plane 2 pattern */
       0xffff  };

USHORT Pat_P1[] = {  /** first dithered filled pattern **/
       0x5555,  /* plane 1 pattern */
       0xaaaa,
       0xffff,  /* plane 2 pattern */
       0xffff  };

USHORT Pat_P2[] = {  /** second dithered filled pattern **/
       0xffff,  /* plane 1 pattern */
       0xffff,
       0x5555,  /* plane 2 pattern */
       0xaaaa   };

setHint(ShowHint)
int ShowHint;
{
    char *s;
    int  oldBPen;

    if (ShowHint) {
       switch ( board[CurX][CurY][CurLevel].compass) {
          case NORTH :   s = " HINT: Go North!                "; break;
          case SOUTH :   s = " HINT: Go South!                "; break;
          case EAST  :   s = " HINT: Go East!                 "; break;
          case WEST  :   s = " HINT: Go West!                 "; break;
          case SOLVED:   s = " CONGRATULATIONS!               "; break;
          default    :   s = " Hmm.  I don't know.            "; break;
          }
       }
      else {
       s = " (Press Left Button for a hint.)";
       }
    Move(rp, 20L, 180L);
    SetAPen(rp, 1L);
    oldBPen = rp -> BgPen;
    SetBPen(rp, 0L);
    SetDrMd(rp, (LONG)JAM2);
    Text(rp, s, 32L);
    SetBPen(rp, (LONG)oldBPen);
    }

showside(ax,ay, bx,by, cx,cy, dx,dy, color)
LONG ax,ay, bx,by, cx,cy, dx,dy, color;
{
    SetAPen(  tmpRP, color);   /* The shape isn't allways a rect., so */
    SetOPen(  tmpRP, color);   /*  we can't use RectFill() here...  */
    BNDRYOFF( tmpRP);          /* Boundaries look bad w/ patterns...*/
    switch (color) {
       case CURPIECE     :
       case TRAVERSED    : SetAfPt( tmpRP, Pat_P2,-1L); break;
       case LASTPIECE    : SetAfPt( tmpRP, Pat_P1,-1L); break;
       case NOTTRAVERSED :
       case FIRSTPIECE   :
       default           : SetAfPt( tmpRP, Pat_Normal,-1L); break;
       }

    AreaMove( tmpRP, ax,ay);
    AreaDraw( tmpRP, bx,by);
    AreaDraw( tmpRP, cx,cy);
    AreaDraw( tmpRP, dx,dy);
    AreaEnd(  tmpRP);
    SetAPen(  tmpRP, (LONG)EDGE);
    Move(     tmpRP, ax,  ay);
    Draw(     tmpRP, bx,  by);
    Draw(     tmpRP, bx+1,by);
    Draw(     tmpRP, ax+1,ay);
    Move(     tmpRP, cx,  cy);
    Draw(     tmpRP, dx,  dy);
    Draw(     tmpRP, dx+1,dy);
    Draw(     tmpRP, cx+1,cy);
    }

putedge(ax,ay,bx,by)
LONG ax,ay,bx,by;
{
    SetAPen(tmpRP,(LONG)EDGE);
    Move(tmpRP,ax,  ay);
    Draw(tmpRP,bx,  by);
    Draw(tmpRP,bx+1,by);
    Draw(tmpRP,ax+1,ay);
    }

LONG renderColor(x, y, z, x1, y1, z1)
int x, y, z, x1, y1, z1;
{   int color;
    color = board[x][y][z].inpath;
    if (!(z == MaxLevel-1 && (color == FIRSTPIECE || color == LASTPIECE)))
       if ((color == NOTTRAVERSED) ||
           (board[x1][y1][z1].inpath == NOTTRAVERSED))
           color = NOTTRAVERSED;
    return((LONG)color);
    }

#define XDIF 6
#define YDIF 3

render(x,y)
int x, y;
{
   LONG ax,ay, bx,by, cx,cy, dx,dy, color;
   int level, Bleft, Btop, deltaX, deltaY, tmpL;
   int left, right, bottom, top;

   /* clear the temporary bitmap */
   SetAPen( tmpRP, 0L);
   SetBPen( tmpRP, 0L);
   RectFill( tmpRP, 0L, 0L, (LONG)SquareXsize, (LONG)SquareYsize );

   Bleft  =  4 + (x - 1) * SquareXsize;
   Btop   = 11 + (y - 1) * SquareYsize;

   left   = 0;
   right  = SquareXsize - 1;
   top    = 0;
   bottom = SquareYsize - 1;

   for (level=MinLevel; level<MaxLevel; level++) {
       if (references(x, y, level) == 0)
          continue; /* This level doesn't go anywhere. */

       deltaY = YDIF * level  + 1;
       deltaX = XDIF * level  + 1;

       /**** Fill in the middle part first ****/
       ax = right - deltaX;         ay = top + deltaY;
       bx = left  + deltaX;         by = ay;
       cx = bx;                     cy = bottom - deltaY;
       dx = ax;                     dy = cy;
       color = board[x][y][level].inpath;
       showside(ax,ay,bx,by,cx,cy,dx,dy,color);

       /**** Do the NORTH side of this level first ****/
       ax = right-deltaX;      ay = top + deltaY;
       bx = ax;                by = top;
       cx = left +deltaX;      cy = by;
       dx = cx;                dy = ay;
       tmpL  = board[x][y][level].conlev[NORTH];
       if ( tmpL == NOWHERE) {
            putedge(ax,ay,dx,dy);
            goto DrawWest;
            }
       color = renderColor(x,y,level,x,y-1,tmpL);
       if (tmpL != level && level == 1) {
            bx = bx - XDIF*(tmpL - 1);
            cx = cx + XDIF*(tmpL - 1);
            }
       showside(ax,ay,bx,by,cx,cy,dx,dy,color);

       /**** Do the WEST side of this level next ****/
       DrawWest:
       ax = left + deltaX;      ay = top + deltaY;
       bx = left;               by = ay;
       cx = bx;                 cy = bottom - deltaY;
       dx = ax;                 dy = cy;
       tmpL  = board[x][y][level].conlev[WEST];
       if ( tmpL == NOWHERE) {
            putedge(ax,ay,dx,dy);
            goto DrawSouth;
            }
       color = renderColor(x,y,level,x-1,y,tmpL);
       if (tmpL != level && level == 1) {
            by = by + YDIF*(tmpL - 1);
            cy = cy - YDIF*(tmpL - 1);
            }
       showside(ax,ay,bx,by,cx,cy,dx,dy,color);

       /**** Do the SOUTH side of this level next ****/
       DrawSouth:
       ax = left + deltaX;      ay = bottom - deltaY;
       bx = ax;                 by = bottom;
       cx = right - deltaX;     cy = by;
       dx = cx;                 dy = ay;
       tmpL  = board[x][y][level].conlev[SOUTH];
       if ( tmpL == NOWHERE) {
            putedge(ax,ay,dx,dy);
            goto DrawEast;
            }
       color = renderColor(x,y,level,x,y+1,tmpL);
       if (tmpL != level && level == 1) {
            bx = bx + XDIF*(tmpL-1);
            cx = cx - XDIF*(tmpL-1);
            }
       showside(ax,ay,bx,by,cx,cy,dx,dy,color);

       /**** Do the EAST side of this level last ****/
       DrawEast:
       ax = right - deltaX;     ay = bottom - deltaY;
       bx = right;              by = ay;
       cx = bx;                 cy = top + deltaY;
       dx = ax;                 dy = cy;
       tmpL  = board[x][y][level].conlev[EAST];
       if ( tmpL == NOWHERE) {
            putedge(ax,ay,dx,dy);
            goto DrawComplete;
            }
       color = renderColor(x,y,level,x+1,y,tmpL);
       if (tmpL != level && level == 1) {
            by = by - YDIF*(tmpL - 1);
            cy = cy + YDIF*(tmpL - 1);
            }
       showside(ax,ay,bx,by,cx,cy,dx,dy,color);
       DrawComplete:;
       }
   /* now copy temporary bitmap into window */

   BltBitMapRastPort(&tmpBM,0L,0L, rp,(LONG)Bleft,(LONG)Btop,
            (LONG)SquareXsize,(LONG)SquareYsize, (LONG)0x0c0);
   }  /* end of render() */


/* references() returns the number connections from a given square. */
int references(x, y, level)
int x, y, level;
{ int i, refs;
    refs = 0;
    for (i=0; i < DIRECTIONS; i++)
        if (board[x][y][level].conlev[i] != NOWHERE)
            refs++;
    return(refs);
    }

/* linkable() returns true if we can connect the two indicated squares. */
/* NOTE: We don't allow connecting to the second square if it */
/* is already part of the maze.  This test if the first if stmt.*/
/* The second test if more subtle.  The problem being tested for is shown in */
/* the following diagram.  This is an edge-on view of the board: */
/*   a __    __ d   */
/*       \  /       */
/*         /        */
/*        /         */
/*   c __/  \__ b   */
/* If c and d are connected, I can't connect a to b because the paths would */
/* intersect.  The way the test is written, it will work regardless of whether */
/* the new path is going up, down, or level. */

int linkable(x1,y1,level1,dir1, x2,y2, level2, dir2)
int x1,y1,level1,dir1, x2,y2,level2;
{
   int tmp;
   if (references(x2,y2,level2)) return(0);
   if (board[x1][y1][level2].conlev[dir1] == level1) return(0);
   return(-1);
   }

/* Returns the other Direction, or NOWHERE if an invalid direction is passed. */
int otherDir(nd)
int nd;
{ switch (nd) {
    case NORTH : return(SOUTH); break;
    case SOUTH : return(NORTH); break;
    case EAST  : return(WEST) ; break;
    case WEST  : return(EAST) ; break;
    }
  return(NOWHERE);
  }


/* makepathlist() returns the number of directions we can go from here w/o */
/*  backtracking -- i.e., not counting the way we got here.  These */
/*  "uncharted" routes are characterized by .compus==NOWHERE.  The list of */
/*  directions is placed in pl[]. */

int makepathlist(x,y,z,pl)
int x, y, z, pl[];
{   int di, le, paths;
    paths = 0;
    for (di=0; di<DIRECTIONS; di++) {
        pl[paths] = di;
        le = board[x][y][z].conlev[di];
        if (le != NOWHERE)
           switch (di) {
              case NORTH   :  if (board[x][y-1][le].compass == NOWHERE)
                                 paths++;
                              break;
              case SOUTH   :  if (board[x][y+1][le].compass == NOWHERE)
                                 paths++;
                              break;
              case EAST    :  if (board[x+1][y][le].compass == NOWHERE)
                                 paths++;
                              break;
              case WEST    :  if (board[x-1][y][le].compass == NOWHERE)
                                 paths++;
                              break;
              case NOWHERE :  break;
              }
        }
    return(paths);
    }

int topscore;

/* buildreturnmap() is a recursive routine which starts the end of a path on */
/* our tree-structured maze and traverses up to an intersection or dead end. */
/* When we hit a dead end, we just return, but when we hit an intersection, we */
/* call buildreturnmap() again, once for each path going off from the */
/* intersection, except for the one got there on.  We keep a score for how far */
/* we are from the first square.  One point per square, plus 5 times the */
/* number of paths leading off from each intersection.  We keep a topscore to */
/* find out which square is farthest (in this modified sense) from our */
/* starting square.  This helps to ensure that we get a reasonably difficult */
/* maze to solve. */
/*   We also record the direction to the end of the maze in each square.  This */
/* information is used by the hint facility. */

buildreturnmap(x,y,z,score)
int x, y, z, score;
{   int pathlist[DIRECTIONS], paths, i, le;

    while ( (paths = makepathlist(x,y,z,pathlist)) == 1) {
          z = board[x][y][z].conlev[pathlist[0]];
          switch (pathlist[0]) {
            case NORTH : y--; break;
            case SOUTH : y++; break;
            case EAST  : x++; break;
            case WEST  : x--; break;
            }
          board[x][y][z].compass = otherDir(pathlist[0]);
          /* score++; */
          }

    if (paths == 0) {   /* We are at the end of a path... */
        if (score >= topscore) {
            topscore = score;
            StartX = x;
            StartY = y;
            StartLevel = z;
            }
        return;
        }

    /* if we got here, we are not at the end of a path.   paths > 1 */
    score = score + paths;

    for (i=0; i<paths; i++) {
        le = board[x][y][z].conlev[pathlist[i]];
        switch (pathlist[i]) {
           case NORTH   : board[x][y-1][le].compass = SOUTH;
                          buildreturnmap(x,y-1,le,score);     break;

           case SOUTH   : board[x][y+1][le].compass = NORTH;
                          buildreturnmap(x,y+1,le,score);     break;

           case EAST    : board[x+1][y][le].compass = WEST;
                          buildreturnmap(x+1,y,le,score);     break;

           case WEST    : board[x-1][y][le].compass = EAST;
                          buildreturnmap(x-1,y,le,score);     break;
           }
        }
    }

#define MAXENDS 120
#define FREEEND -1
#define LASTEND -1
typedef struct {
        int x,y,z;    /* board coordinates. x=FREEEND means this one is free */
        int prevdir;  /* The direction we went to get here. */
                      /*    In picking what direction to go, we are biased */
                      /*    toward this direction.  This gives paths */
                      /*    with several straight sections -- keeps one path from */
                      /*    knotting up one part of the board. */
        int nextfree; /* next unused end, LASTEND means no more  */
        } endtype;

endtype ends[MAXENDS];
int     firstfree;
int     MaxEnds = MAXENDS;

initends()
{   int i;

    for (i=0; i<MaxEnds; i++) {
        ends[i].x = -1;
        ends[i].y = -1;
        ends[i].z = -1;
        ends[i].nextfree = i - 1;
        }
    firstfree = MaxEnds - 1;
    /* NOTE that ends[0].nextfree == -1 == LASTEND.  If that define ever */
    /* changes, we will have to include the statement: */
    /* ends[0].nextfree = LASTEND; */
    }

/* IF you want to play around with the parameters that effect the way
   boards are built, you will want to try different combinations of
   "tries", "length", and global MaxEnds. */

int extendend(curend,tries,length)
int curend, tries, length;
{
    int x, y, level;
    int nd,od, nx, ny, nl, i, moves, link;

    moves = 0;

    x     = ends[curend].x;
    y     = ends[curend].y;
    level = ends[curend].z;
    nd    = ends[curend].prevdir;

    /* try up to i times to add a random square */
    for (i=0; i<tries && moves < length; i++) {
        do {         /*  try not to go out of bounds */
             nd = ((RangeRand(10L) < 4) ? (int)RangeRand((LONG)DIRECTIONS) : nd);
             } while ((nd == NORTH && y == 1)           ||
                      (nd == WEST  && x == 1)           ||
                      (nd == SOUTH && y == BoardMaxY-1) ||
                      (nd == EAST  && x == BoardMaxX-1)     );
        /* Now that we've got a direction, see that we don't already go that way */
        if (board[x][y][level].conlev[nd] != NOWHERE)
            continue;
        nx = x;  ny = y;
        switch (nd) {                /* work out the new x and y */
            case NORTH : ny = y - 1; break;
            case SOUTH : ny = y + 1; break;
            case EAST  : nx = x + 1; break;
            case WEST  : nx = x - 1; break;
            }
        od = otherDir(nd);
        nl = level;

        /** get some level we can go onto from here **/
        if (!(link=linkable(x, y, level, nd, nx, ny, nl, od))) {   /* stay on the same level if we can... */
           if (level > MinLevel) {    /* can't stay on this level so go down */
               nl = level - 1;
               link = linkable(x, y, level, nd, nx, ny, nl, od); /* if we can't go down, go up */
               }
           if (!link && (level < MaxLevel - 1)) {
               nl = level + 1;   /* can't go down or level, so try up */
               link = linkable(x, y, level, nd, nx, ny, nl, od);
               }
           }

        if (link) {
            board[x ][y ][level].conlev[nd] = nl;
            board[nx][ny][nl   ].conlev[od] = level;
            render( x, y);
            render(nx,ny);
            moves++;
            /* sometimes fork, putting our old coordinates in a free end slot. */
            if (firstfree != LASTEND) {  /* make sure there IS a free end slot */
                if (RangeRand(10L) < 4) {
                   ends[firstfree].x = x;
                   ends[firstfree].y = y;
                   ends[firstfree].z = level;
                   ends[firstfree].prevdir = nd;
                   firstfree = ends[firstfree].nextfree;
                   }
                }
            ends[curend].x = x     = nx;
            ends[curend].y = y     = ny;
            ends[curend].z = level = nl;
            }
        }
    /* if we got this far and made no moves, we are probably on dead end and */
    /* should put this ends[] on the free list. */
    if (moves == 0) {
          ends[curend].x = FREEEND;
          ends[curend].nextfree = firstfree;
          firstfree = curend;
          }
    return(moves);
    }
int xties, xlength;
int makepath()
{   int i, endsfound, totalsquares;

    initends();   /* This sets the table of path ends to all zeros */

    /*   ends[] is a list of the ends of paths which we can add more paths */
    /*   onto.  Note that they don't really have to be an end; they can be */
    /*   in the middle of a path as well.   Not all of them are in use as */
    /*   an end all the time.  Some are in a linked list of "free" ends, */
    /*   available for use if we want to add an end.  Free (unused) array */
    /*   elements are marked by a .x == FREEEND.  Ends get taken out of active */
    /*   service and put on the free list when the path generator "extendend()" */
    /*   fails to extend the path from that end.  When no active ends remain, */
    /*   maze generation terminates. */

    /*  p.s.: I don't particularly care for the mazes that are generated by */
    /*  this method, nor am I particularly fond of the method.  I would like */
    /*  to hear of other strategies for maze generation. */


    ends[firstfree].x = 1 + RangeRand((LONG)BoardMaxX - 1);
    ends[firstfree].y = 1 + RangeRand((LONG)BoardMaxY - 1);
    ends[firstfree].z = 0;
    ends[firstfree].prevdir = RangeRand((LONG)DIRECTIONS);
    firstfree = ends[firstfree].nextfree;

    totalsquares = 0;
    do {
         endsfound = 0;
         for (i=0; i< MaxEnds; i++) {
             if (ends[i].x != FREEEND) {
                    endsfound++;
                    totalsquares += extendend(i,xties,xlength);
                    }
             }
         } while (endsfound);
    return( totalsquares );
    }

pickends()
{   int x, y, z, i;

    /* Find then end of a path on the bottom level. */
    do {
        StartX = 1 + RangeRand( (LONG) BoardMaxX-1L );
        StartY = 1 + RangeRand( (LONG) BoardMaxY-1L );
        StartLevel =  MinLevel;
        } while (references( StartX, StartY, StartLevel) != 1);

    /* The reason for doing this 4 times is to make the ends as far apart as */
    /* possible.  If our first choice is close to the top of the tree, it */
    /* can't be very far away from every leaf node.  The way this works is: */
    /*     1  Find a leaf node. */
    /*     2  Find the leaf farthest from the one found in step 1. */
    /*     3  Find the leaf farthest from the one found in step 2. ... */
    /* Eventually you should end up with two good choices for the ends. */

    for (i=0; i<4; i++) {
        for (x=1; x<BoardMaxX; x++)
            for (y=1; y<BoardMaxY; y++)
                for (z=MinLevel; z<MaxLevel; z++)
                    board[x][y][z].compass = NOWHERE;

        EndX = StartX;   EndY = StartY;    EndLevel = StartLevel;
        board[ EndX ][ EndY ][ EndLevel ].compass = SOLVED;
        topscore = 0;
        buildreturnmap(EndX, EndY, EndLevel, 0);
        }

    board[ StartX ][ StartY ][ StartLevel ].inpath = FIRSTPIECE;
    board[ EndX   ][ EndY   ][ EndLevel   ].inpath = LASTPIECE;
    CurX     = StartX;
    CurY     = StartY;
    CurLevel = StartLevel;
    NewX     = CurX;
    NewY     = CurY;
    NewLevel = CurLevel;
    render( StartX, StartY);
    render( EndX,   EndY);
    }

init1( l )
int l;
{
  int i, x, y, level, dir;
  static int Xsize[] = { 54, 16, 24, 34 }; /* Square widths  */
  static int Xsqrs[] = { 10, 34, 22, 16 }; /* No. of squares */

  static int Ysize[] = { 26, 10, 14, 18 }; /* Square heights */
  static int Ysqrs[] = {  6, 16, 11,  9 }; /* No. of squares */

     /* Reset the entire board, including a strip of squares around */
     /* the edges that we never go into. */
  for(x=0; x <= BOARDMAXX; x++)
     for(y=0; y <= BOARDMAXY; y++)
        for(level=0; level < MAXLEVELS; level++) {
           board[x][y][level].inpath   =  NOTTRAVERSED;
           board[x][y][level].compass  =  NOWHERE;
           for(dir=0; dir < DIRECTIONS; dir++)
              board[x][y][level].conlev[dir] =  NOWHERE;
           }

  SetAPen( rp, 0L);
  SetBPen( rp, 0L);
  RectFill( rp, 4L, 11L, (LONG)windowW-4, (LONG)windowH-2);

  MaxLevel = l;   /* l==0 is a special-case first-time super-easy 1-level */
                  /* maze.  It generates fast so we can get to the menus. */

  BoardMaxX   = Xsqrs[ MaxLevel ] + 1;
  SquareXsize = Xsize[ MaxLevel ];
  BoardMaxY   = Ysqrs[ MaxLevel ] + 1;
  SquareYsize = Ysize[ MaxLevel ];

  if (MaxLevel == 0)
     MaxLevel = 1;

  makepath();

  pickends();
  setHint( (int)FALSE );
  }

int autosolve()
{   int newDir;
    square *oldSq, *newSq;

    while ( (newDir = board[CurX][CurY][CurLevel].compass) != SOLVED ) {
          NewX = CurX;
          NewY = CurY;
          NewLevel = board[CurX][CurY][CurLevel].conlev[newDir];
          switch (newDir) {
              case NORTH : NewY--; break;
              case SOUTH : NewY++; break;
              case EAST  : NewX++; break;
              case WEST  : NewX--; break;
              }

          oldSq = &board[ CurX ][ CurY ][ CurLevel];
          newSq = &board[ NewX ][ NewY ][ NewLevel];

          oldSq->inpath = TRAVERSED;

          switch (newSq->inpath) {
              case TRAVERSED  :
              case FIRSTPIECE : /* We must have backed up to get here, so...*/
                          oldSq->inpath = NOTTRAVERSED; break;
              default         : ;
              }

          /* set the inpath flag of the new square in any case */
          newSq->inpath = CURPIECE;

          /* Also, just in case we backed up to the starting square */
          /*   or from the ending square.... */
          board[StartX][StartY][StartLevel].inpath = FIRSTPIECE;
          board[EndX  ][EndY  ][EndLevel  ].inpath = LASTPIECE;

          /* Now draw both squares */
          render(CurX,CurY);
          render(NewX,NewY);

          /* Now new becomes current */
          CurX = NewX;
          CurY = NewY;
          CurLevel = NewLevel;

          }
    }



int mousewatch()
{   static int canmove = FALSE;
    int x, y, newDir;

    x = ((MouseX) -  4)/SquareXsize + 1;
    y = ((MouseY) - 11)/SquareYsize + 1;

    x = x * SIGN(MouseX);
    y = y * SIGN(MouseY);

    if (x == CurX && y == CurY) {
        canmove = TRUE;
        }

    newDir = NOWHERE;
    if (x == CurX) {
         if (y == CurY + 1 && y < BoardMaxY)
               newDir = SOUTH;
            else if (y == CurY - 1 && y > 0)
                      newDir = NORTH;
         }
      else
         if (y == CurY) {
               if (x == CurX + 1 && x < BoardMaxX)
                     newDir = EAST;
                  else if (x == CurX - 1 && x > 0)
                           newDir = WEST;
             }

    if (newDir == NOWHERE ) {
         canmove = FALSE;
         return(NOWHERE);
         }

    NewLevel = board[CurX][CurY][CurLevel].conlev[newDir];

    if (NewLevel == NOWHERE) {
       canmove = FALSE;
       return(NOWHERE);
       }
    NewX = x;
    NewY = y;
    return(newDir);
    }

int trymove() /* returns TRUE if we won, FALSE if we didn't win. */
{   int newDir;
    square *oldSq, *newSq;

    newDir = mousewatch();
    if (newDir == NOWHERE)
       return(board[CurX][CurY][CurLevel].compass == SOLVED);

    oldSq = &board[ CurX ][ CurY ][ CurLevel];
    newSq = &board[ NewX ][ NewY ][ NewLevel];

    oldSq->inpath = TRAVERSED;
    switch (newSq->inpath) {
        case TRAVERSED  :
        case FIRSTPIECE : /* We must have backed up to get here, so...*/
                          oldSq->inpath = NOTTRAVERSED; break;
        default         : ;
        }

    /* set the inpath flag of the new square in any case */
    newSq->inpath = CURPIECE;

    /* Also, just in case we backed up from the starting square */
    /*   or the ending square.... */
    board[StartX][StartY][StartLevel].inpath = FIRSTPIECE;
    board[EndX  ][EndY  ][EndLevel  ].inpath = LASTPIECE;

    /* Now draw both squares */
    render(CurX,CurY);
    render(NewX,NewY);

    /* Now new becomes current */
    CurX = NewX;
    CurY = NewY;
    CurLevel = NewLevel;

    /* ?did we win? */

    setHint((int)(newSq->compass == SOLVED));

    if (newSq->compass == SOLVED) {
          cycle( 3 );
          return( (int)TRUE );
          }
    return( (int)FALSE);
    }

HandleMenu(menucode)
USHORT menucode;
{
    ModifyIDCMP( window, (ULONG) MIDCMP2 );

    switch ( ITEMNUM( menucode) ) {
        case 0 : about()   ;  break;
        case 1 : init1( 1 );  break;
        case 2 : init1( 2 );  break;
        case 3 : init1( 3 );  break;
        case 4 : autosolve(); break;
        }

    ModifyIDCMP( window, (ULONG) MIDCMP1 );
    }


EventLoop()
{
  struct IntuiMessage *mesg;
  ULONG  class, code, mousemoved, closewindow, menupick;
  USHORT menucode;

  closewindow = FALSE;
  ModifyIDCMP( window, (ULONG) MIDCMP1 );

  do {
       mousemoved = FALSE;
       menupick   = FALSE;

       Wait( (LONG) 1 << window -> UserPort -> mp_SigBit);

       while ((mesg=(struct IntuiMessage *)GetMsg(window->UserPort))) {
             class = mesg->Class;
             code  = mesg->Code;
             MouseX = mesg->MouseX;
             MouseY = mesg->MouseY;
             ReplyMsg(mesg);
             if (class == MOUSEMOVE) mousemoved = TRUE;
             if (class == CLOSEWINDOW) closewindow = TRUE;
             if (class == MOUSEBUTTONS && code == SELECTDOWN)
                setHint( (int) TRUE);
             if (class == MENUPICK) {
                menupick = TRUE;
                menucode = code;
                }
             }
       if (mousemoved) trymove();
       if (menupick)   HandleMenu(menucode);
       } while (closewindow == FALSE);
  }

struct TextFont *textfont = NULL;

openstuff()
{   ULONG Seconds, Micros;

    IntuitionBase = (struct IntuitionBase *)OpenLibrary("intuition.library",0L);
    if (IntuitionBase == NULL) {closestuff(); exit(0);}

    GfxBase = (struct GfxBase *)OpenLibrary("graphics.library",0L);
    if (GfxBase == NULL) {closestuff(); exit(0); }

    /* My <functions.h> shows OpenFont() returns a *Font. */
    /* I think that is an error! */

    textfont = (struct TextFont *)OpenFont( &font );
    if (textfont==NULL) { closestuff(); exit(0); }

    if (( window=(struct Window *)OpenWindow(&nw))==NULL) {
       closestuff();
       exit(0);
       }
    if (SetFont(window->RPort,textfont)==0) { closestuff(); exit(0); }

    SetWindowTitles(window,(UBYTE *)" TML's AmigaMaze     ver. 1.2 ",
            (UBYTE *)"TML's AmigaMaze       First distributed on JUMPDISK.");

    SetMenuStrip( window, &menu);

    /*  This next bit is a cludge because I can't seem to get */
    /*                 extern ULONG RangeSeed; */
    /*      to work.  Anyone got any ideas? */
    /*  LATER: It turns out that the RangeSeed is not public */
    /*      in the Manx sources.  Hope they fix this someday. */
    CurrentTime(&Seconds,&Micros);
    Micros = Micros & (ULONG) 0x0fff;
    for (Seconds=0; Seconds < Micros; Seconds++)
         RangeRand(4L);
    }


closestuff()
{   int i;
    for(i=0; i<2; i++) {
       if (tmpBM.Planes[i])
            FreeRaster(tmpBM.Planes[i],tmpBMxy,tmpBMxy);
       }
    if (window) {
        ClearMenuStrip( window );
        CloseWindow(window);
        }
    if (textfont) CloseFont(textfont);
    if (GfxBase) CloseLibrary(GfxBase);
    if (IntuitionBase) CloseLibrary(IntuitionBase);
    }

main(/*argc,argv*/)
/* int argc; */
/* char *argv[]; */
{   UWORD areabuffer[250], areabuffer2[250];
    struct TmpRas   tmpras,   tmprasB;
    struct AreaInfo areainfo, areainfo2;
    PLANEPTR plane,planeB;
    int i;

    /* if (argc > 1) */
    /*     xties = atoi(argv[1]); */
    /* if (xties < 1 || xties > 100) */
        xties = 30;

    /* if (argc > 2) */
    /*     xlength = atoi(argv[2]); */
    /* if (xlength < 1 || xlength > 100) */
        xlength = 9;

    /* if (argc > 3) */
    /*     MaxEnds = atoi(argv[3]); */
    /* if (MaxEnds < 2 || MaxEnds > MAXENDS) */
        MaxEnds = MAXENDS;

    MaxLevel = 1;
    MinLevel = 0;
    openstuff();
    InitBitMap( &tmpBM, 2L, tmpBMxy, tmpBMxy );
    for (i=0; i<2; i++) {
         if ((tmpBM.Planes[i] = (PLANEPTR)AllocRaster(tmpBMxy,tmpBMxy))==NULL) {
             closestuff();
             exit(0);
             }
         }
    rp = window->RPort;
    if ((plane = AllocRaster(windowW,windowH))==NULL) {
        closestuff();
        exit(0);
        }
    if ((planeB = AllocRaster(tmpBMxy,tmpBMxy))==NULL) {
        FreeRaster(plane, windowW,windowH);
        closestuff();
        exit(0);
        }
    InitArea(&areainfo, areabuffer, 90L);
    InitArea(&areainfo2,areabuffer2,90L);

    InitTmpRas(&tmpras, plane, RASSIZE( windowW, windowH));
    InitTmpRas(&tmprasB,planeB,RASSIZE( tmpBMxy, tmpBMxy));

    rp->AreaInfo    = &areainfo;
    rp->TmpRas      = &tmpras;

    InitRastPort( tmpRP );
    if (SetFont(tmpRP,textfont)==0) { closestuff(); exit(0); }
    tmpRP->BitMap = &tmpBM;
    tmpRP->AreaInfo = &areainfo2;
    tmpRP->TmpRas   = &tmprasB;

    init1(0); /* Zero is a special case.  Super simple fast easy maze
                 so the user can get to the menus w/o waiting so long. */
    ModifyIDCMP( window, (ULONG) MIDCMP2 );
    about();
    EventLoop();
    FreeRaster(plane, windowW, windowH);
    FreeRaster(planeB,tmpBMxy, tmpBMxy);
    closestuff();
    }

/* Save some code space by stubbing _wb_parse() and _cli_parse(). */
void _wb_parse()
{ }

void _cli_parse()
{ }