#!/usr/bin/perl -w
# Generate cave repeatedly and collect stats on amount of space used.
#
# Forked from cave.pl

use strict;
use constant MIN_WIDTH => 16;
use constant MIN_HEIGHT => 16;
use constant ITERATION_COUNT => 100;

# Set size from command line arguments.
if( $#ARGV != 1 )
{
   die "$0 {width} {height}\n";
}
my ($width, $height) = @ARGV;
unless( $width =~ /^(\d+)$/ && $height =~ /^(\d+)$/ &&
        $width >= MIN_WIDTH && $height >= MIN_HEIGHT )
{
   die "Invalid size: ($ARGV[0], $ARGV[1]), minimum size is (" .
       MIN_WIDTH . ", " . MIN_HEIGHT . ")\n";
}

my $total_wall = 0;
my $total_space = 0;
my $min_wall = undef;
my $max_wall = undef;
for(my $seed = 1; $seed <= ITERATION_COUNT; $seed++)
{
   srand($seed);

   # Initialize field filled with walls.
   #
   # Note that we generate a field with double the requested height to
   # compensate for the non-square character cells.
   my @cave = ();
   for(my $y = 0; $y < $height * 2; $y++)
   {
      push @cave, chr(1) x $width;
   }

   # Replace random wall cells with empty spaces, avoiding boundaries.
   for(my $y = 1; $y < $height * 2 - 2; $y++)
   {
      for(my $x = 1; $x < $width - 1; $x++)
      {
         # Set initial walls by comparing random numbers against a threshold.
         # Amount of walls we end up with will be proportional to this
         # threshold, but the relationship is not linear due to the smoothing
         # pass.
         #
         # On average, with a threshold of 0.47, we end up with just over half
         # of the cells as walls.
         substr($cave[$y], $x, 1) = chr(rand() <= 0.47 ? 1 : 0);
      }
   }

   # Apply smoothing function.
   for(my $pass = 0; $pass < 3; $pass++)
   {
      # Iterate over non-boundary cells and add counts from bit 0, then
      # store the results in bit 1.  The next loop shifts all the cells
      # values right by 1 bit so that only bit 0 is used after each pass.
      #
      # Instead of using two bits to separate inputs and outputs for each
      # pass, we can apply the updated cell directly in one pass.  As
      # expected, this would result in excessive smoothing, and also
      # cause the walls to be biased toward upper left.  It would still
      # look reasonable, just not as good.
      for(my $y = 1; $y < $height * 2 - 1; $y++)
      {
         for(my $x = 1; $x < $width - 1; $x++)
         {
            my $count = 0;
            for(my $dy = -1; $dy <= 1; $dy++)
            {
               for(my $dx = -1; $dx <= 1; $dx++)
               {
                  $count += ord(substr($cave[$y + $dy], $x + $dx, 1)) & 1;
               }
            }
            my $c = ord(substr($cave[$y], $x, 1));
            substr($cave[$y], $x, 1) = chr($c | ($count >= 5 ? 2 : 0));
         }
      }
      for(my $y = 1; $y < $height * 2 - 1; $y++)
      {
         for(my $x = 1; $x < $width - 1; $x++)
         {
            substr($cave[$y], $x, 1) = chr(ord(substr($cave[$y], $x, 1)) >> 1);
         }
      }
   }

   # Shrink cave vertically to the requested size.
   for(my $y = 0; $y < $height * 2; $y += 2)
   {
      for(my $x = 0; $x < $width; $x++)
      {
         substr($cave[$y >> 1], $x, 1) =
            chr(ord(substr($cave[$y], $x, 1)) |
                ord(substr($cave[$y + 1], $x, 1)));
      }
   }

   # Find disjoint empty spaces and try to connect them.
   my ($last_x, $last_y);
   for(my $r = 0; $r < 6; $r++)
   {
      # Find a random starting point that's empty and not yet filled.
      my $start_x = int(rand($width - 2)) + 1;
      my $start_y = int(rand($height - 2)) + 1;
      for(my $i = 0; $i < $width * $height; $i++)
      {
         if( substr($cave[$start_y], $start_x, 1) eq chr(0) )
         {
            last;
         }
         $start_x++;
         if( $start_x == $width - 1 )
         {
            $start_x = 1;
            $start_y = $start_y % ($height - 2) + 1;
         }
      }
      if( substr($cave[$start_y], $start_x, 1) ne chr(0) )
      {
         # Filled all empty spaces.
         last;
      }

      # For all rounds after the first round, if we managed to find a
      # new starting position, it means current space is disjoint from
      # previously filled space.  We will connect both by carving a
      # path to the previous starting point.
      if( $r > 0 )
      {
         for(my $x = $start_x; $x != $last_x; $x += $x > $last_x ? -1 : 1)
         {
            substr($cave[$start_y], $x, 1) = chr(0);
         }
         for(my $y = $start_y; $y != $last_y; $y += $y > $last_y ? -1 : 1)
         {
            substr($cave[$y], $last_x, 1) = chr(0);
         }
      }

      # Flood fill.
      my @stack = ([$start_x, $start_y]);
      while( scalar @stack )
      {
         my ($x, $y) = @{pop @stack};
         if( substr($cave[$y], $x, 1) eq chr(0) )
         {
            push @stack, [$x, $y - 1],
                         [$x - 1, $y],
                         [$x, $y + 1],
                         [$x + 1, $y];
            substr($cave[$y], $x, 1) = chr(2);
         }
      }

      $last_x = $start_x;
      $last_y = $start_y;
   }

   # Count number of wall and space characters.
   my $text = "";
   my $space_count = 0;
   my $wall_count = 0;
   for(my $y = 0; $y < $height; $y++)
   {
      for(my $x = 0; $x < $width; $x++)
      {
         if( substr($cave[$y], $x, 1) eq chr(2) )
         {
            $space_count++;
         }
         else
         {
            $wall_count++;
         }
      }
   }
   print "seed = $seed, space = $space_count, walls = $wall_count\n";
   $total_wall += $wall_count;
   $total_space += $space_count;

   if( defined($min_wall) )
   {
      $min_wall = $min_wall < $wall_count ? $min_wall : $wall_count;
      $max_wall = $max_wall > $wall_count ? $max_wall : $wall_count;
   }
   else
   {
      $min_wall = $max_wall = $wall_count;
   }
}
printf 'average space = %.2f, average wall = %.2f, min = %d, max = %d'."\n",
       $total_space / ITERATION_COUNT,
       $total_wall / ITERATION_COUNT,
       $min_wall,
       $max_wall;