#!/usr/bin/perl
use lib '.';
require "../cgi-lib.pl";
ReadParse(*params);
print "Content-Type: text/html\n\n";

$width = $params->{width} || 150;
$height = $params->{height} || 150;

if($width > $height) {
    $max = $width;
    $rscale_w = ($width/$height);
    $rscale_h = 1;
} else {
    $max = $height;
    $rscale_w = 1;
    $rscale_h = ($height/($width));
}
$p = 1;
while(2**$p+1 < $max) { $p++; }
print "P = $p => ".(2**$p+1)."<br>\n";
$pmax = 2**$p;

$maxval = 100;
$minval = 0;
$hrandval = 50;
$lrandval = 1;

$heights[0][0] = 100;
$heights[0][$pmax] = 50;
$heights[$pmax][0] = 50;
$heights[$pmax][$pmax] = 0;
set_heights(0,0,$pmax);

for(my $r=0;$r<$height;$r++) {
    for(my $c=0;$c<$width;$c++) {
	my $x = int(($r/($height-1))*$pmax);
	my $y = int(($c/($width-1))*$pmax);
	$res[$r][$c] = $heights[$y][$x];
    }
}

@typ = ();
for(1..15) {
    my($wx,$wy);
    $wx = int(rand $width);
    $wy = int(rand $height);
    #$res[$wy][$wx] = 100;
    add_water(\@res,\@typ,$wx,$wy);
}

disp_res(\@res,\@typ);

sub add_water {
    my($res,$typ,$sx,$sy) = @_;
    my($bot) = 0;
    my($x,$y) = ($sx,$sy);
    my(@watered) = ();
    my($safety) = 0;
    while(!$bot) {
	#print "Added water at $x,$y<br>\n";
	$typ->[$y][$x] = 'w';
	last if($y==0 || $x==0 || $y==$height || $x==$width);
	#last if($safety++ > 200);
	push @watered,{x=>$x,y=>$y};
#	print "<table border=1>\n";
#	print "<tr><td></td><td>$res->[$y-1][$x]</td><td></td></tr>\n";
#	print "<tr><td>$res->[$y][$x-1]</td><td>$res->[$y][$x]</td><td>$res->[$y][$x+1]</td></tr>\n";
#	print "<tr><td></td><td>$res->[$y+1][$x]</td><td></td></tr>\n";
#	print "</table>\n";

	if($x+1 < $width &&
	   $typ->[$y][$x+1] ne 'w' &&
	   $res->[$y][$x+1] <= $res->[$y][$x] &&
	   $res->[$y][$x+1] <= $res->[$y][$x-1] &&
	   $res->[$y][$x+1] <= $res->[$y+1][$x] &&
	   $res->[$y][$x+1] <= $res->[$y-1][$x]) {
	    $x++;
	} elsif($x > 0 &&
		$typ->[$y][$x-1] ne 'w' &&
		$res->[$y][$x-1] <= $res->[$y][$x] &&
		$res->[$y][$x-1] <= $res->[$y][$x+1] &&
		$res->[$y][$x-1] <= $res->[$y+1][$x] &&
		$res->[$y][$x-1] <= $res->[$y-1][$x]) {
	    $x--;
	} elsif($y < $height &&
		$typ->[$y+1][$x] ne 'w' &&
		$res->[$y+1][$x] <= $res->[$y][$x] &&
		$res->[$y+1][$x] <= $res->[$y][$x+1] &&
		$res->[$y+1][$x] <= $res->[$y][$x-1] &&
		$res->[$y+1][$x] <= $res->[$y-1][$x]) {
	    $y++;
	} elsif($y > 0 &&
		$typ->[$y-1][$x] ne 'w' &&
		$res->[$y-1][$x] <= $res->[$y][$x] &&
		$res->[$y-1][$x] <= $res->[$y][$x+1] &&
		$res->[$y-1][$x] <= $res->[$y][$x-1] &&
		$res->[$y-1][$x] <= $res->[$y+1][$x]) {
	    $y--;
	} else {
	    my($minx,$miny,$min) = (undef,undef,$maxval+1);
	    foreach my $w (@watered) {
		if($w->{x} < $width &&
		   $typ->[$w->{y}][$w->{x}+1] ne 'w' &&
		   $res->[$w->{y}][$w->{x}+1] < $min) {
		    $min = $res->[$w->{y}][$w->{x}+1];
		    $minx = $w->{x}+1;
		    $miny = $w->{y};
		}
		if($w->{x} > 0 &&
		   $typ->[$w->{y}][$w->{x}-1] ne 'w' &&
		   $res->[$w->{y}][$w->{x}-1] < $min) {
		    $min = $res->[$w->{y}][$w->{x}-1];
		    $minx = $w->{x}-1;
		    $miny = $w->{y};
		}
		if($w->{y} < $height &&
		   $typ->[$w->{y}+1][$w->{x}] ne 'w' &&
		   $res->[$w->{y}+1][$w->{x}] < $min) {
		    $min = $res->[$w->{y}+1][$w->{x}];
		    $minx = $w->{x};
		    $miny = $w->{y}+1;
		}
		if($w->{y} > 0 &&
		   $typ->[$w->{y}-1][$w->{x}] ne 'w' &&
		   $res->[$w->{y}-1][$w->{x}] < $min) {
		    $min = $res->[$w->{y}-1][$w->{x}];
		    $minx = $w->{x};
		    $miny = $w->{y}-1;
		}
	    }
	    if(defined($minx) && defined($miny)) {
		$x = $minx;
		$y = $miny;
	    } else {
		$bot = 1;
		print "Maxxed!<br>\n";
	    }
	}
    }
}

sub disp_res {
    my($res,$typ) = @_;
    print "<table cellspacing=0 cellpadding=0>\n";
    for($r=0;$r<=$#$res;$r++) {
	print "<tr>\n";
	for($c=0;$c<=$#{$res->[$r]};$c++) {
	    print "<td bgcolor=#";
	    print color($res->[$r][$c],$minval,$maxval,$typ->[$r][$c]);
	    print "><img src=\"/~dave/images/spacer.gif\" width=3 height=3></td>\n";
	}
	print "</tr>\n";
    }
    print "</table>\n";
}

sub set_heights {
    my($x,$y,$d) = @_;
    my $sd = $d/2;
    my($ul,$ur,$ll,$lr);
    $ul = $heights[$x][$y];
    $ur = $heights[$x+$d][$y];
    $ll = $heights[$x][$y+$d];
    $lr = $heights[$x+$d][$y+$d];
    #top
    if(!defined($heights[$x+$sd][$y])) {
	$heights[$x+$sd][$y] = ($ul + $ur) / 2;
	my $r = rand ($rscale_w*(($d/$pmax)*($hrandval-$lrandval)+$lrandval));
	if(rand 100 > 50) { $heights[$x+$sd][$y] += $r; }
	else { $heights[$x+$sd][$y] -= $r; }
	if($heights[$x+$sd][$y] > $maxval) { $heights[$x+$sd][$y] = $maxval; }
	if($heights[$x+$sd][$y] < $minval) { $heights[$x+$sd][$y] = $minval; }
    }
    #left
    if(!defined($heights[$x][$y+$sd])) {
	$heights[$x][$y+$sd] = ($ul + $ll) / 2;
	my $r = rand ($rscale_h*(($d/$pmax)*($hrandval-$lrandval)+$lrandval));
	if(rand 100 > 50) { $heights[$x][$y+$sd] += $r; }
	else { $heights[$x][$y+$sd] -= $r; }
	if($heights[$x][$y+$sd] > $maxval) { $heights[$x][$y+$sd] = $maxval; }
	if($heights[$x][$y+$sd] < $minval) { $heights[$x][$y+$sd] = $minval; }
    }
    #right
    if(!defined($heights[$x+$d][$y+$sd])) {
	$heights[$x+$d][$y+$sd] = ($ur + $lr) / 2;
	my $r = rand ($rscale_h*(($d/$pmax)*($hrandval-$lrandval)+$lrandval));
	if(rand 100 > 50) { $heights[$x+$d][$y+$sd] += $r; }
	else { $heights[$x+$d][$y+$sd] -= $r; }
	if($heights[$x+$d][$y+$sd] > $maxval) { $heights[$x+$d][$y+$sd] = $maxval; }
	if($heights[$x+$d][$y+$sd] < $minval) { $heights[$x+$d][$y+$sd] = $minval; }
    }
    #bottom
    if(!defined($heights[$x+$sd][$y+$d])) {
	$heights[$x+$sd][$y+$d] = ($ll + $lr) / 2;
	my $r = rand ($rscale_w*(($d/$pmax)*($hrandval-$lrandval)+$lrandval));
	if(rand 100 > 50) { $heights[$x+$sd][$y+$d] += $r; }
	else { $heights[$x+$sd][$y+$d] -= $r; }
	if($heights[$x+$sd][$y+$d] > $maxval) { $heights[$x+$sd][$y+$d] = $maxval; }
	if($heights[$x+$sd][$y+$d] < $minval) { $heights[$x+$sd][$y+$d] = $minval; }
    }
    #middle
    if(!defined($heights[$x+$sd][$y+$sd])) {
	$heights[$x+$sd][$y+$sd] = ($heights[$x+$sd][$y] + $heights[$x][$y+$sd] + $heights[$x+$d][$y+$sd] + $heights[$x+$sd][$y]) / 4;
	my $r = rand ((($rscale_w+$rscale_h)/2)*(($d/$pmax)*($hrandval-$lrandval)+$lrandval));
	if(rand 100 > 50) { $heights[$x+$sd][$y+$sd] += $r; }
	else { $heights[$x+$sd][$y+$sd] -= $r; }
	if($heights[$x+$sd][$y+$sd] > $maxval) { $heights[$x+$sd][$y+$sd] = $maxval; }
	if($heights[$x+$sd][$y+$sd] < $minval) { $heights[$x+$sd][$y+$sd] = $minval; }
    }
    if($sd > 1) {
	set_heights($x,$y,$sd);
	set_heights($x+$sd,$y,$sd);
	set_heights($x,$y+$sd,$sd);
	set_heights($x+$sd,$y+$sd,$sd);
    }
}

sub color {
    my($val,$min,$max,$type) = @_;
    my($c) = int((($val-$min)/($max-$min))*255);
    if($type eq 'w') {
	return sprintf("%02lx%02lx%02lx",$c/2,$c/2,($c<64)?64:$c);
    } else {
	return sprintf("%02lx%02lx%02lx",$c,$c,$c);
    }
}