#!/usr/bin/perl -w
# Generate an ASCII art map of inter-connected caves.
#
# Uses this algorithm:
# https://www.roguebasin.com/index.php/Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels
#
# We also considered using Perlin noise as a starting point, but it
# takes a lot more code, and the resulting caves generally don't look
# as nice in low resolution.

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

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

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

# Convert cave data to printable text and output.
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) )
      {
         # Add space for empty areas that have been touched in one of the
         # floodfill passes.
         $text .= " ";
         $space_count++;
      }
      elsif( substr($cave[$y], $x, 1) eq chr(0) )
      {
         # Add dot for empty areas that have not been touched by floodfill.
         # These are disjoint areas that we weren't able to connect.  We
         # differentiate these in output for debugging, but for production
         # we don't need this branch -- everything that was not a floodfill
         # connected region is considered a wall.
         $text .= ".";
         $wall_count++;
      }
      else
      {
         # Add "#" for walls.
         $text .= "#";
         $wall_count++;
      }
   }
   $text .= "\n";
}
print $text, "space = $space_count, walls = $wall_count\n";