// Create random maze using the algorithm from "How to Build a Maze",
// David Matuszek, Byte Magazine, vol.6, n.12, pp.190-196, December 1981,
// https://archive.org/details/byte-magazine-1981-12
//
// Usage: create [-d] [m [n]]
//
//  -d  debug
//   m  maze number of rows
//   n   and columns
//
// R. Perry, March 1991; updated Nov 2006, Jan 2016, Apr 2023
//
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "maze.h"

#define MARK(x,y) { maze[x][y].type = FRONTIER; push( x, y); }

static struct frontier *stack = NULL;
static int nstack = 0;
static int stack_size = 0;

/* choose random frontier cell */

struct frontier pop( void)
{
  int i;
  struct frontier f = { 0, 0 };

  if( nstack == 0) /* stack is empty! */
  {
    fprintf( stderr, "pop: stack is empty!\n");
    return f;
  }

  i = irand( nstack);
  f = stack[i];
  stack[i] = stack[--nstack];

#ifdef DEBUG
  fprintf( stderr, "pop: %d, %d\n", f.row, f.col);
#endif

  return f;
}

/* put frontier cell on stack */

void push( int row, int col)
{
  if( nstack == stack_size) /* stack is full */
  {
    int newsize = 1.5*stack_size + 100;
    struct frontier *newstack = realloc( stack, newsize*sizeof(struct frontier) );
    if( newstack == NULL)
    {
      fprintf( stderr, "push: realloc() failed.\n");
      return;
    }
    stack = newstack;
    stack_size = newsize;
  }

  stack[nstack].row = row;
  stack[nstack].col = col;
  ++nstack;

#ifdef DEBUG
  fprintf( stderr, "push: %d, %d\n", row, col);
#endif
}

/* mark i,j neighbors */

void mark( struct cell **maze, int m, int n, int i, int j)
{
  if( i > 0   && maze[i-1][j].type == NEITHER) MARK( i-1, j);
  if( i < m-1 && maze[i+1][j].type == NEITHER) MARK( i+1, j);
  if( j > 0   && maze[i][j-1].type == NEITHER) MARK( i, j-1);
  if( j < n-1 && maze[i][j+1].type == NEITHER) MARK( i, j+1);
}
 
/* maze creation via spanning tree */

void maze_tree( struct cell **maze, int m, int n)
{
  int i, j, found;
  struct frontier f;
  int r[4] = { 0, 1, 2, 3 }; /* for choosing random neighbor */

  /* 1. Randomly choose any cell of the array and mark it as a spanning
   *    tree cell.
   */
  i = irand(m);
  j = irand(n);
  maze[i][j].type = SPANTREE;

  /* The four cells immediately adjacent to it (fewer if it is on an
   * edge or in a corner) are then marked as frontier cells.
   */
  mark( maze, m, n, i, j);
 
  if( debug)
    maze_print_X( maze, m, n);

  /* Repeat steps 2 and 3 until there are no frontier cells left:
   */
  while( nstack > 0)
  {
    /* 2. Randomly choose a frontier cell and connect it to one cell of the
     *    current spanning tree by opening one wall.  If it is adjacent to
     *    more than one cell of the spanning tree (it could be adjacent to
     *    as many as four), randomly choose one of them to connect it to
     *    and mark the appropriate wall as open.  Note: to connect cell maze[i][j]
     *    to the cell above it means  maze[i-1][j].down = OPEN;
     */
    f = pop();

    maze[f.row][f.col].type = SPANTREE;

    shuffle( r, 4);

    found = i = 0;

    while( !found)
    {
      switch( r[i++])
      {
	case 0: /* above */

	  if( f.row > 0 && maze[f.row-1][f.col].type == SPANTREE)
	  {
	    maze[f.row-1][f.col].down = OPEN;
	    found = 1;
	  }
	  break;

	case 1: /* below */

	  if( f.row < m-1 && maze[f.row+1][f.col].type == SPANTREE)
	  {
	    maze[f.row][f.col].down = OPEN;
	    found = 1;
	  }
	  break;

	case 2: /* left */

	  if( f.col > 0 && maze[f.row][f.col-1].type == SPANTREE)
	  {
	    maze[f.row][f.col].left = OPEN;
	    found = 1;
	  }
	  break;

	case 3: /* right */

	  if( f.col < n-1 && maze[f.row][f.col+1].type == SPANTREE)
	  {
	    maze[f.row][f.col+1].left = OPEN;
	    found = 1;
	  }
	  break;
      }

    } /* while( !found) */

 
    /* 3. Check the cells adjacent to the cell just added to the spanning
     *    tree.  Any such cells that are neither part of the spanning tree
     *    nor the frontier must now be marked as frontier cells.
     */
    mark( maze, m, n, f.row, f.col);

    if( debug)
      maze_print_X( maze, m, n);

  } /* while( nstack > 0) */
    
}

int main( int argc, char *argv[])
{
  int m = 8, n = 16, r;  struct cell **maze;

  srand(time(0));

  while( argc > 1 && argv[1][0] == '-')
  {
    switch( argv[1][1])
    {
      case 'D': case 'd': debug = 1; break; 
      default: fprintf( stderr, "maze: unknown option: %s\n", argv[1]); break;
    }
    --argc, ++argv;
  }

  if( argc > 1 && (r = atoi(argv[1])) > 0) { m = r; if( argc == 2) n = m; }

  if( argc > 2 && (r = atoi(argv[2])) > 0) n = r;

  maze = maze_alloc( m, n);

  if( maze == 0) { fprintf( stderr, "maze_alloc() failed.\n"); return 1; }

  maze_init( maze, m, n);

  maze_tree( maze, m, n);

  maze_print_raw( maze, m, n);

  return 0;
}