/**
 * maze.cc
 *
 * Generate, print and solve random mazes
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#include "maze.h"
#pragma lint -1

#define PATH  0x10
#define VISITED 0x20
#define ALL_WALLS 0xF

#define clear_north(a) ((maze[a] & NORTH) == 0)
#define clear_south(a) ((maze[a] & SOUTH) == 0)
#define clear_east(a) ((maze[a] & EAST) == 0)
#define clear_west(a) ((maze[a] & WEST) == 0)
#define visited(a) ((maze[a] & VISITED) != 0)
#define north(p) ((p) - MAZE_COLS)
#define south(p) ((p) + MAZE_COLS)
#define east(p) ((p) + 1)
#define west(p) ((p) - 1)

void createMaze( char *maze, unsigned int MAZE_ROWS, unsigned int MAZE_COLS )
{
   unsigned int sp, pos, x, y;
   unsigned int directions;
   unsigned int paths[4];
   unsigned int MAZE_SIZE = MAZE_ROWS*MAZE_COLS;

   /* Each element of the maze is a 4-bit number that marks edges */
   int *stack = (int *) malloc( sizeof( int ) * MAZE_SIZE );

   /* Clear the maze */
   for ( pos = 0; pos < MAZE_SIZE; pos++ )
      maze[pos] = ALL_WALLS;

   if ( stack == NULL )
      return;

   pos = sp = 0;

   /* Run a depth-first search until MAZE_SIZE cells have been visited */
   stack[sp++] = -1;

   while ( sp > 0 )
   {
      /* Compute the current cell's location */
      x   = pos % MAZE_COLS;
      y   = pos / MAZE_COLS;
                                                             
      /* Mark the current cell as visited */
      maze[pos] |= VISITED;

      /* Pick a neighbor that has not been visited yet */
      directions = 0;

      if ( y > 0 && !visited(north(pos)))
         paths[directions++] = NORTH;

      if ( x < MAZE_COLS - 1 && !visited(east(pos)))
         paths[directions++] = EAST;

      if ( y < MAZE_ROWS - 1 && !visited(south(pos)))
         paths[directions++] = SOUTH;

      if ( x > 0 && !visited(west(pos)))
         paths[directions++] = WEST;

      /* If no neighbors are available, pop the stack */
      if ( directions == 0 )
      {
         pos = stack[--sp];
         continue;
      }

      /* Push the current position onto the stack */
      stack[sp++] = pos;

      /* Move to a random neighbor */
      directions = ((unsigned) rand() % directions);

      /* Knock down the wall */
      switch( paths[directions] )
      {
         case NORTH:
           maze[pos]        &= ~NORTH;
           maze[north(pos)] &= ~SOUTH;
           pos = north(pos);
           break;

         case SOUTH:
           maze[pos]        &= ~SOUTH;
           maze[south(pos)] &= ~NORTH;
           pos = south(pos);
           break;           

         case EAST:
           maze[pos]       &= ~EAST;
           maze[east(pos)] &= ~WEST;
           pos = east(pos);
           break;

         case WEST:
           maze[pos]       &= ~WEST;
           maze[west(pos)] &= ~EAST;
           pos = west(pos);
           break;
      }
   }

   /* Knock out the start and end */
   maze[0] &= ~WEST;
   maze[MAZE_SIZE-1] &= ~EAST;

   /* Clear the visited and path flags of the maze */
   for ( pos = 0; pos < MAZE_SIZE; pos++ )
      maze[pos] &= ~(VISITED | PATH);

   free( stack );
}

void printMaze( char *maze, unsigned int MAZE_ROWS, unsigned int MAZE_COLS )
{
  int pos1, pos2, i,  j;
  unsigned int MAZE_SIZE = MAZE_ROWS*MAZE_COLS;
                                                                        
  pos1 = 0;
  for ( i = 0; i < MAZE_ROWS; i++, pos1 = south(pos1) )
  {
    /* Print the top of each cell */
    for ( pos2 = pos1, j = 0; j < MAZE_COLS; j++, pos2 = east(pos2) )
    {
       if ( maze[pos2] & NORTH )
          printf( "+--" );
       else
          printf( "+  " );
    }
    printf( "+\n" );

    /* Print the middle of each cell */
    for ( pos2 = pos1, j = 0; j < MAZE_COLS; j++, pos2++ )
    {
       if ( maze[pos2] & WEST )
          printf( "|%02x", maze[pos2] );
       else
          printf( " %02x", maze[pos2]);
    }

    if ( maze[pos2-1] & EAST )
       printf("|");
    printf( "\n" );
  }

  for ( pos2 = pos1 - MAZE_COLS, j = 0; j < MAZE_COLS; j++, pos2++ )
     if ( maze[pos2] & SOUTH )
        printf( "+--" );
     else
        printf( "+  " );

  printf( "+\n" );
}

void solveMaze( char *maze, unsigned int MAZE_ROWS, unsigned int MAZE_COLS )
{
   unsigned int x, y, pos, sp = 0;
   unsigned int MAZE_SIZE = MAZE_ROWS*MAZE_COLS;
   int *stack = (int *) malloc( sizeof( int ) * MAZE_SIZE );
   int *prev  = (int *) malloc( sizeof( int ) * MAZE_SIZE );

   stack[sp++] = 0;

   /* Run until we find the lower-right edge */
   while ( sp > 0 )
   {
      /* Pop the position off the stack */
      pos = stack[--sp];

      /* If we're at the exit, we're done! */
      if ( pos == MAZE_SIZE - 1 )
      {
         break;
      }

      /* Compute the current cell's location */
      x   = pos % MAZE_COLS;
      y   = pos / MAZE_COLS;

      /* Mark as visited */
      maze[pos] |= VISITED;

      /* Add neighbors to the stack */
      if ( y > 0 && clear_north(pos) && !visited(north(pos)))
      {  stack[sp++] = north(pos); prev[north(pos)] = pos; }

      if ( x < MAZE_COLS - 1 && clear_east(pos) && !visited(east(pos)))
      {  stack[sp++] = east(pos); prev[east(pos)] = pos; }

      if ( y < MAZE_ROWS -1 && clear_south(pos) && !visited(south(pos)))
      {  stack[sp++] = south(pos); prev[south(pos)] = pos; }

      if ( x > 0 && clear_west(pos) && !visited(west(pos)))
      {  stack[sp++] = west(pos); prev[west(pos)] = pos; }
   }

   /* Record the path */
   while ( pos != 0 )
   {
      maze[pos] |= PATH;
      pos = prev[pos];
   }
   maze[pos] |= PATH;

   /* Clear the visited flags of the maze */
   for ( pos = 0; pos < MAZE_SIZE; pos++ )
      maze[pos] &= ~VISITED;

   free( stack );
   free( prev );
}