#!/usr/bin/perl
# maze.pl - Don Yang (uguu.org)
#
# 2014-02-17

use strict;
use constant WIDTH => 39;
use constant HEIGHT => 11;

use constant VISITED => 1;
use constant DOOR_RIGHT => 2;
use constant DOOR_BOTTOM => 4;

# Initialize empty cell
sub InitEmptyMaze($)
{
   my ($cell) = @_;
   for(my $y = 0; $y < HEIGHT; $y++)
   {
      for(my $x = 0; $x < WIDTH; $x++)
      {
         $$cell[$y][$x] = 0;
      }
   }
}

# Connect two cell
sub ConnectCells($$$$$)
{
   my ($cell, $cx, $cy, $px, $py) = @_;

   if( $cy > $py )
   {
      $$cell[$py][$cx] |= DOOR_BOTTOM;
   }
   elsif( $cy < $py )
   {
      $$cell[$cy][$cx] |= DOOR_BOTTOM;
   }
   else
   {
      if( $cx > $px )
      {
         $$cell[$cy][$px] |= DOOR_RIGHT;
      }
      elsif( $cx < $px )
      {
         $$cell[$cy][$cx] |= DOOR_RIGHT;
      }
   }
}

# Return 4 pairs of deltas in random order
sub GenerateDeltas()
{
   my @delta = ([-1, 0], [1, 0], [0, -1], [0, 1]);

   # Fisher-Yates shuffle
   for(my $i = @delta; --$i;)
   {
      my $j = int(rand($i + 1));
      next if $i == $j;
      @delta[$i, $j] = @delta[$j, $i];
   }
   return @delta;
}

# Mark cells in maze
sub GenerateMaze($)
{
   my ($cell) = @_;
   my $height = @$cell;
   my $width = @{$$cell[0]};

   # Start at upper left corner and visit cells
   my @visit = ();
   push @visit, [0, 0, 0, 0];
   while( scalar @visit )
   {
      my ($cx, $cy, $px, $py) = @{pop @visit};

      # Drop cells that are out of bounds, and cells that have already
      # been visited.
      if( $cx < 0 || $cx >= $width || $cy < 0 || $cy >= $height ||
          ($$cell[$cy][$cx] & VISITED) != 0 )
      {
         next;
      }

      # Mark current cell as visited
      $$cell[$cy][$cx] |= VISITED;
      ConnectCells($cell, $cx, $cy, $px, $py);

      # Do not visit additional neighbors of goal cell.  This guarantees
      # that goal cell only has one entrance, and increases the amount of
      # maze space that might be traversed before reaching the goal cell.
      next if $cx == $width - 1 && $cy == $height - 1;

      # Add neighbors in random order
      my @delta = GenerateDeltas();
      while( scalar @delta )
      {
         my ($dx, $dy) = @{pop @delta};
         push @visit, [$cx + $dx, $cy + $dy, $cx, $cy];
      }
   }

   # No more nodes to visit, mark exit next to goal
   $$cell[$height - 1][$width - 1] |= DOOR_RIGHT;
}

# Output maze to stdout
sub OutputMaze($)
{
   my ($cell) = @_;
   my $height = @$cell;
   my $width = @{$$cell[0]};
   
   # Top border and first left wall
   print (("+-" x $width), "+\n");

   # Cells
   for(my $y = 0; $y < $height; $y++)
   {
      # Cell rows
      print "|";
      for(my $x = 0; $x < $width; $x++)
      {
         print (($$cell[$y][$x] & DOOR_RIGHT) != 0 ? "  " : " |");
      }

      # Border rows
      print "\n+";
      for(my $x = 0; $x < $width; $x++)
      {
         print (($$cell[$y][$x] & DOOR_BOTTOM) != 0 ? " +" : "-+");
      }

      # Right border
      print "\n";
   }
}



my @cell = ();
InitEmptyMaze(\@cell);
GenerateMaze(\@cell);
OutputMaze(\@cell);