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

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

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

# Get bits for a single cell
sub ReadCell($$$)
{
   my ($cells, $x, $y) = @_;
   return ord(substr($$cells[$y], $x, 1));
}

# Add a single bit to a cell
sub UpdateCell($$$$)
{
   my ($cells, $x, $y, $mod) = @_;
   substr($$cells[$y], $x, 1) = chr(ReadCell($cells, $x, $y) + $mod);
}

# Create door between two cells
sub ConnectCells($$$$$)
{
   my ($cells, $x0, $y0, $x1, $y1) = @_;

   if( $x0 < $x1 )
   {
      UpdateCell($cells, $x0, $y1, DOOR_RIGHT);
   }
   elsif( $x0 > $x1 )
   {
      UpdateCell($cells, $x1, $y1, DOOR_RIGHT);
   }
   else
   {
      if( $y0 < $y1 )
      {
         UpdateCell($cells, $x1, $y0, DOOR_BOTTOM);
      }
      else
      {
         UpdateCell($cells, $x1, $y1, DOOR_BOTTOM);
      }
   }
}

# 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;
}

# Generate maze with padded cells
sub GenerateMaze($$$)
{
   my ($cells, $width, $height) = @_;

   # Initialize maze with walls
   push @$cells, chr(VISITED | DOOR_RIGHT) x ($width + 2);
   for(my $y = 0; $y < $height; $y++)
   {
      push @$cells,
           chr(VISITED | DOOR_BOTTOM) . (chr(0) x $width) .
           chr(VISITED | DOOR_BOTTOM);
   }
   push @$cells, chr(VISITED | DOOR_RIGHT) x ($width + 2);

   # Start marking cells at upper left corner
   my @visit = ([0, 1, 1, 1]);
   while( scalar @visit )
   {
      my ($x0, $y0, $x1, $y1) = @{pop @visit};

      next if (ReadCell($cells, $x1, $y1) & VISITED) != 0;

      # Mark path between current cell and previous cell
      UpdateCell($cells, $x1, $y1, VISITED);
      ConnectCells($cells, $x0, $y0, $x1, $y1);

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

   # Mark exit
   UpdateCell($cells, WIDTH, HEIGHT, DOOR_RIGHT);

   # Unmark entrance
   UpdateCell($cells, 0, 1, -(DOOR_RIGHT));
}

# Build output template for all mask values
sub BuildTiles($$)
{
   my ($odd_tiles, $even_tiles) = @_;

   for(my $y0x0 = 0; $y0x0 < 8; $y0x0++)
   {
      $$even_tiles{chr($y0x0)} = ($y0x0 & DOOR_RIGHT) != 0 ? '   ' : '  |';
      for(my $y0x1 = 0; $y0x1 < 8; $y0x1++)
      {
         for(my $y1x0 = 0; $y1x0 < 8; $y1x0++)
         {
            my $odd_cell = (($y0x0 & DOOR_BOTTOM) != 0 ? '  ' : '--');
            if( ($y0x0 & DOOR_RIGHT) != 0 && ($y1x0 & DOOR_RIGHT) != 0 )
            {
               $odd_cell .= '-';
            }
            elsif( ($y0x0 & DOOR_BOTTOM) != 0 && ($y0x1 & DOOR_BOTTOM) != 0 )
            {
               $odd_cell .= '|';
            }
            else
            {
               $odd_cell .= '+';
            }
            $$odd_tiles{chr($y0x0) . chr($y0x1) . chr($y1x0)} = $odd_cell;
         }
      }
   }
}

# Output maze to stdout
sub OutputMaze($)
{
   my ($cells) = @_;
   my $height = @$cells;

   my (%odd_tiles, %even_tiles);
   BuildTiles(\%odd_tiles, \%even_tiles);

   for(my $y = 0; $y < @$cells - 1; $y++)
   {
      my $row = $$cells[$y];
      my $next_row = $$cells[$y + 1];

      my $output = '';
      for(my $x = 0; $x < length($row) - 1; $x++)
      {
         $output .= $even_tiles{substr($row, $x, 1)};
      }
      print substr($output, 2), "\n";

      $output = '';
      for(my $x = 0; $x < length($row) - 1; $x++)
      {
         $output .= $odd_tiles{substr($row, $x, 2) .
                               substr($next_row, $x, 1)};
      }
      print substr($output, 2), "\n";
   }
}



my @cells = ();
GenerateMaze(\@cells, WIDTH, HEIGHT);
OutputMaze(\@cells);