#include <exec/types.h>
#include "maze.h"

extern void	*AllocMem();
extern long	MouseX,MouseY;

long	seed;		/* FastRand() stuff */

short testpoint[4][2] =
{
  {-1, 0},
  { 1, 0},
  { 0, 1},
  { 0,-1}
};  /* = left,right,down,up */

short stackptr,direction,newpos(),CreateMaze();

long *vpos = (long*)0xdff004; /* Beam position */

short CreateMaze(width,height,area)
register short width;
register char  *area;
short height;
{
 register short x,y;
 register short *stack;
 short i,j;
 short wayout;

 seed=*vpos;           /* new Seed for FastRand() */

 x=2; /* starting position */
 y=0xFFFE&((seed=FastRand(seed)) % (height-4) + 2);

 /* we need a 'stack' to store those positions, from where we can */
 /* continue if we get into a dead end */
 if(!(stack=(short*) AllocMem(width*height,NULL))) return(NULL);

 stackptr=1;
 StackX=x;StackY=y;

 for(i=0;i<width;i++) for(j=0;j<height;j++) MAZECLR(i,j,width,area);

 j= width & 1 ? width-1:width-2;
 for(i=0;i<height;i++)          /* surround the 'maze' with 'passages' */
 {
   MAZESET(0,i,width,area);
   MAZESET(j,i,width,area);
 }
 j= height & 1 ? height-1:height-2;
 for(i=0;i<width;i++)
 {
   MAZESET(i,0,width,area);
   MAZESET(i,j,width,area);
 }

 MAZESET(x,y,width,area);         /* set the first position to 'passage' */

 while(stackptr)                  /* do we have an untested position left ? */
 {
  direction=seed=FastRand(seed);  /* pick up a random direction */

  for (i=0;i<4;i++,direction++)   /* test all 4 directions */
  {
   direction &= 3;                /* = %4 */
   /* test if the position we are moving to is already a 'passage' */
   if(! MAZETEST(x+2*testpoint[direction][0],2*testpoint[direction][1]+y,width,area))
   {
    /* if not, move to the new position */
    MAZESET(x+testpoint[direction][0],testpoint[direction][1]+y,width,area);
    x+=2*testpoint[direction][0];
    y+=2*testpoint[direction][1];
    MAZESET(x,y,width,area);
    StackX=x;                     /* stack current position because */
    StackY=y;                     /* there may be more than one direction */
    stackptr++;                   /* we can move to */
    break;
   }
  }

  if (i==4)
  {
    stackptr--;                   /* dead-end, delete this point from stack */
    x=StackX;                     /* test last position again */
    y=StackY;
  }
 }

 j= width-1;
 for(i=0;i<height;i++)          /* surround the 'maze' with 'walls' */
 {
   MAZECLR(0,i,width,area);
   MAZECLR(j,i,width,area);
 }
 j= height-1;
 for(i=0;i<width;i++)
 {
   MAZECLR(i,0,width,area);
   MAZECLR(i,j,width,area);
 }

 FreeMem(stack,width*height);
 MouseX= 2;
 MouseY= ((seed & 0x7ffe) % (height-4)+2) & 0x7ffe;  /* random start point */
 seed = FastRand(seed);
 wayout = ((seed & 0x7ffe) % (height-4)+2) & 0x7ffe;  /* random exit */
 MAZESET(width-3,wayout,width,area);               /* open exit */

 return(1);
}