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

$params{scale} ||= 3;
$width = $params{width} || 50;
$height = $params{height} || 50;
$waters = $params{waters} || 15;
$sea_level = (defined($params{sealevel}) ? $params{sealevel} : 0);
$tree_line = $params{treeline} || 80;
$grass_line = $params{grassline} || ($tree_line+5);
$forest_dist = $params{treedist} || 20;
$grass_dist = $params{grassdist} || ($forest_dist+20);
$snow_level = $params{snowlevel} || $tree_line + 5;

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 = $params{hrand} || 50;
$lrandval = $params{lrand} || 1;

$heights[0][0] = int(rand 200)-100;
$heights[0][$pmax] = int(rand 200)-100;
$heights[$pmax][0] = int(rand 200)-100;
$heights[$pmax][$pmax] = int(rand 200)-100;

#$heights[0][0] = 100;
#$heights[0][$pmax] = 100;
#$heights[$pmax][0] = 100;
#$heights[$pmax][$pmax] = 100;

#$heights[0][0] = 0;
#$heights[0][$pmax] = 0;
#$heights[$pmax][0] = 0;
#$heights[$pmax][$pmax] = 0;

logtime("Start");
set_heights_new(0,0,$pmax,0);
logtime("Set Heights");
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];
    }
}
logtime("Normalized");
@typ = ();
add_ocean(\@res,\@typ,\@dist);
logtime("Ocean Added at level $sea_level");
add_snow(\@res,\@typ,\@dist);
logtime("Added snow");
for(my $witers=0;$witers<$waters;$witers++) {
    my($wx,$wy);
    $wx = int(rand $width);
    $wy = int(rand $height);
    #$res[$wy][$wx] = 100;
    add_water(\@res,\@typ,$wx,$wy);
}
logtime("$waters Water Added ($wi)");
my(@dist);
#fill_dist(\@res,\@typ,\@dist,0);
test_fill_dist(\@res,\@typ,\@dist,0);
logtime("Water Distance Done");
add_forest(\@res,\@typ,\@dist);
logtime("Forests added");
add_grass(\@res,\@typ,\@dist);
logtime("Grasslands added");
disp_res(\@res,\@typ,\@dist);
#disp_grid(\@dist);

# IDEA:
# Rather than snowcap each and every mountain, just make them normally brown/gray
# as you go up, then add snow the same way that water is added. Pick any arbitrary
# point above height N, and then add snow to it, tracing the path upward, rather
# than water which traces its way downward.
#
# Similar to water, any point above X height is randomly assigned as a snow start
# point (better chances at higher altitudes), and is traced upwards until there's
# no further upwards to go, or until another snow point is found.

sub logtime {
    my($mesg) = @_;
    push @times,time();
    if(@times > 1) {
	$diff = $times[$#times] - $times[$#times-1];
	print "$mesg - $diff<br>\n";
    }
}

sub test_fill_dist {
    my($res,$typ,$dist,$v) = @_;
    my($x,$y,$cdist,%done,%check);
    for($y=0;$y<$height;$y++) {
	for($x=0;$x<$width;$x++) {
	    if($typ->[$y][$x] eq 'w' ||
	       $typ->[$y][$x] eq 'o') {
		$dist->[$y][$x] = 0;
		$check{"$y,$x"} = 1;
		$filled{"$y,$x"} = 1;
	    }
	}
    }
    while (keys %check) {
	foreach my $key (keys %check) {
	    my($y,$x) = split /,/,$key;
	    my($k1);
	    if($y>0) {
		$k1 = "" . ($y-1) . ",$x";
		if(!$filled{$k1} || $dist->[$y-1][$x] > ($dist->[$y][$x]+1)) {
		    $dist->[$y-1][$x] = $dist->[$y][$x]+1;
		    $filled{$k1} = 1;
		    $check{$k1} = 1;
		}
	    }
	    if($y<$height) {
		$k1 = "" . ($y+1) . ",$x";
		if(!$filled{$k1} || $dist->[$y+1][$x] > ($dist->[$y][$x]+1)) {
		    $dist->[$y+1][$x] = $dist->[$y][$x]+1;
		    $filled{$k1} = 1;
		    $check{$k1} = 1;
		}
	    }

	    if($x>0) {
		$k1 = "$y,".($x-1);
		if(!$filled{$k1} || $dist->[$y][$x-1] > ($dist->[$y][$x]+1)) {
		    $dist->[$y][$x-1] = $dist->[$y][$x]+1;
		    $filled{$k1} = 1;
		    $check{$k1} = 1;
		}
	    }
	    if($x<$width) {
		$k1 = "$y,".($x+1);
		if(!$filled{$k1} || $dist->[$y][$x+1] > ($dist->[$y][$x]+1)) {
		    $dist->[$y][$x+1] = $dist->[$y][$x]+1;
		    $filled{$k1} = 1;
		    $check{$k1} = 1;
		}
	    }
	    delete $check{$key};
	}
    }
}

sub fill_dist {
    my($res,$typ,$dist,$v) = @_;
    my($x,$y);
    my($done) = 0;
    #print "Pass $v\n";
    if($v == 0) {
	for($y=0;$y<$height;$y++) {
	    for($x=0;$x<$width;$x++) {
		if($typ->[$y][$x] eq 'w' ||
		   $typ->[$y][$x] eq 'o') {
		    $dist->[$y][$x] = 0;
		} else {
		    $dist->[$y][$x] = -1;
		}
	    }
	}
    } else {
	$done = 1;
	for($y=0;$y<$height;$y++) {
	    for($x=0;$x<$width;$x++) {
		if($dist->[$y][$x] < 0) {
		    my(@checks);
		    if($y > 0) {
			push @checks,{y=>($y-1),x=>$x,d=>1};
			if($x > 0) {
			    push @checks,{y=>($y-1),x=>($x-1),d=>1.414};
			}
			if(($x+1) < $width) {
			    push @checks,{y=>($y-1),x=>($x+1),d=>1.414};
			}
		    }
		    if($x > 0) {
			push @checks,{y=>$y,x=>($x-1),d=>1};
		    }
		    if(($x+1) < $width) {
			push @checks,{y=>$y,x=>($x+1),d=>1};
		    }
		    if(($y+1) < $height) {
			push @checks,{y=>($y+1),x=>$x,d=>1};
			if($x > 0) {
			    push @checks,{y=>($y+1),x=>($x-1),d=>1.414};
			}
			if(($x+1) < $width) {
			    push @checks,{y=>($y+1),x=>($x+1),d=>1.414};
			}
		    }
		    my($mind) = -1;
		    foreach my $c (@checks) {
			my($d) = $dist->[$c->{y}][$c->{x}];
			if($d >= 0 && $d <= $v) {
			    if($mind <= 0) { $mind = $d+$c->{d}; }
			    elsif(($d+$c->{d}) < $mind) { $mind = $d+$c->{d}; }
			}
		    }
		    if($mind > 0) {
			$dist->[$y][$x] = $mind;
		    } else {
			$done = 0;
		    }

#		    if($y>0 && $dist->[$y-1][$x] >= 0) {
#			$dist->[$y][$x] = $dist->[$y-1][$x]+1;
#		    } elsif(($y+1)<$height && $dist->[$y+1][$x] >= 0) {
#			$dist->[$y][$x] = $v; #$dist->[$y+1][$x]+1;
#		    } elsif($x>0 && $dist->[$y][$x-1] >= 0) {
#			$dist->[$y][$x] = $v; #$dist->[$y][$x-1]+1;
#		    } elsif(($x+1)<$width && $dist->[$y][$x+1] >= 0) {
#			$dist->[$y][$x] = $v; #$dist->[$y][$x+1]+1;

#		    } elsif($y>0 && $x>0 && $dist->[$y-1][$x-1] >= 0) {
#			$dist->[$y][$x] = $dist->[$y-1][$x-1] + 1.414;
#		    } elsif($y>0 && ($x+1)<$width && $dist->[$y-1][$x+1] >= 0) {
#			$dist->[$y][$x] = $dist->[$y-1][$x+1] + 1.414;
#		    } elsif(($y+1)<$height && $x>0 && $dist->[$y+1][$x-1] >= 0) {
#			$dist->[$y][$x] = $dist->[$y+1][$x-1] + 1.414;
#		    } elsif(($y+1)<$height && ($x+1)<$width && $dist->[$y+1][$x+1] >= 0) {
#			$dist->[$y][$x] = $dist->[$y+1][$x+1] + 1.414;

#		    } else {
#			$done = 0;
#		    }
		}
	    }
	  }
    }
    if(!$done) {
	fill_dist($res,$typ,$dist,$v+1);
    }
}

sub add_forest {
    my($res,$typ,$dist) = @_;
    my($x,$y);
    for($y=0;$y<$height;$y++) {
	for($x=0;$x<$width;$x++) {
	    next if($typ->[$y][$x]);
	    #Can't be too far from water or above tree line
	    next if($dist->[$y][$x] > $forest_dist || $res->[$y][$x] > $tree_line);
	    my $r = int rand(20*(1+(21-$dist->[$y][$x])/21));
	    if($r > $dist->[$y][$x]) {
		$typ->[$y][$x] = 'f';
	    }
	}
    }
}

sub add_grass {
    my($res,$typ,$dist) = @_;
    my($x,$y);
    for($y=0;$y<$height;$y++) {
	for($x=0;$x<$width;$x++) {
	    next if($typ->[$y][$x]);
	    #Can't be too far from water or above grass line
	    next if($dist->[$y][$x] > $grass_dist || $res->[$y][$x] > $grass_line);
	    my $r = int rand(40*(1+(41-$dist->[$y][$x])/41));
	    if($r > $dist->[$y][$x]) {
		$typ->[$y][$x] = 'g';
	    }
	}
    }
}

sub add_ocean {
    my($res,$typ,$dist) = @_;
    my($x,$y);
    for($y=0;$y<$height;$y++) {
	for($x=0;$x<$width;$x++) {
	    if($res->[$y][$x] < $sea_level) {
		$typ->[$y][$x] = 'o';
	    }
	}
    }
}

sub add_snow {
    my($res,$typ,$dist) = @_;
    my($x,$y);
    for($y=0;$y<$height;$y++) {
	for($x=0;$x<$width;$x++) {
	    if($res->[$y][$x] >= $snow_level) {
		my $r = rand(($maxval-$res->[$y][$x])*($maxval/($maxval-$snow_level)));
		if($r < 1) {
		    $typ->[$y][$x] = 's';
		    add_snow_vein($x,$y,$res,$typ);
		}
	    }
	}
    }
}

sub add_snow_vein_old {
    my($sx,$sy,$res,$typ) = @_;
    my($top) = 0;
    my($x,$y) = ($sx,$sy);
    my(%visited) = ("$x.$y" => 1);
    my($snow_length) = 0;
    while(!$top) {
	my $max = $res->[$y][$x];
	my($nx,$ny) = ($x,$y);
	$top = 1;
	if($y > 0 && $res->[$y-1][$x] >= ($max-5) && !$visited{"$x.".($y-1)}) {
	    $max = $res->[$y-1][$x]; $nx = $x; $ny = $y-1; $top = 0;
	}
	if($y < $height && $res->[$y+1][$x] >= ($max-5) && !$visited{"$x.".($y+1)}) {
	    $max = $res->[$y+1][$x]; $nx = $x; $ny = $y+1; $top = 0;
	}
	if($x > 0 && $res->[$y][$x-1] >= ($max-5) && !$visited{"".($x-1).".$y"}) {
	    $max = $res->[$y][$x-1]; $nx = $x-1; $ny = $y; $top = 0;
	}
	if($x < $width && $res->[$y][$x+1] >= ($max-5) && !$visited{"".($x+1).".$y"}) {
	    $max = $res->[$y][$x+1]; $nx = $x+1; $ny = $y; $top = 0;
	}
	if(!$top) {
	    if($typ->[$ny][$nx] eq 's') { $top = 1; }
	    else {
		$snow_length++;
		$visited{"$nx.$ny"} = 1;
		$typ->[$ny][$nx] = 's';
	    }
	}
    }
    if($snow_length > 0) { print "Added snow vein of $snow_length<br>\n"; }
}

sub add_snow_vein {
    my($sx,$sy,$res,$typ) = @_;
    my($top) = 0;
    my($orig) = $res->[$y][$x];
    my($max_reached) = $res->[$y][$x];
    my($x,$y) = ($sx,$sy);
    my(@snowed,%dry) = ();
    my($safety) = 0;
    $snow_count++;
    while(!$top) {
	#print "Added snow at $x,$y<br>\n";
	last if($res->[$y][$x] >= $maxval); #Reached mountaintop
	$typ->[$y][$x] = 's';
	$snow_order->[$y][$x] = $snow_count;
	last if($y==0 || $x==0 || $y==$height || $x==$width);
	last if($res->[$y][$x] < ($orig)); #Lower than we started!
	last if($res->[$y][$x] < ($max_reached-3));
	push @snowed,{x=>$x,y=>$y};

	if($res->[$y][$x] > $max_reached) {
	    $max_reached = $res->[$y][$x];
	}
	if($typ->[$y][$x+1] ne 's') { $dry{"$y,".($x+1)} = $res->[$y][$x+1]; }
	if($typ->[$y][$x-1] ne 's') { $dry{"$y,".($x-1)} = $res->[$y][$x-1]; }
	if($typ->[$y+1][$x] ne 's') { $dry{($y+1).",$x"} = $res->[$y+1][$x]; }
	if($typ->[$y-1][$x] ne 's') { $dry{($y-1).",$x"} = $res->[$y-1][$x]; }

	if($x+1 < $width &&
	   $typ->[$y][$x+1] ne 's' &&
	   $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 's' &&
		$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 's' &&
		$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 's' &&
		$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($found) = 0;
	    DRY2: foreach my $coord (sort {$dry{$b} <=> $dry{$a}} (keys %dry)) {
		my($ny,$nx) = split /,/,$coord;
		delete $dry{$coord};
		if($typ->[$ny][$nx] ne "s") {
		    $found = 1;
		    $x = $nx;
		    $y = $ny;
		    last DRY2;
		}
	    }
	    if(!$found) {
		print "Maxxed!<br>\n";
		$top = 1;
	    }
	}
    }
}

sub add_water {
    my($res,$typ,$sx,$sy) = @_;
    my($bot) = 0;
    my($x,$y) = ($sx,$sy);
    my(@watered,%dry) = ();
    my($safety) = 0;
    $water_count++;
    while(!$bot) {
	#print "Added water at $x,$y<br>\n";
	last if($typ->[$y][$x] eq "o"); #Reached the ocean
	$typ->[$y][$x] = 'w';
	$water_order->[$y][$x] = $water_count;
	last if($y==0 || $x==0 || $y==$height || $x==$width);
	#last if($safety++ > 200);
	push @watered,{x=>$x,y=>$y};

	if($typ->[$y][$x+1] ne 'w') { $dry{"$y,".($x+1)} = $res->[$y][$x+1]; }
	if($typ->[$y][$x-1] ne 'w') { $dry{"$y,".($x-1)} = $res->[$y][$x-1]; }
	if($typ->[$y+1][$x] ne 'w') { $dry{($y+1).",$x"} = $res->[$y+1][$x]; }
	if($typ->[$y-1][$x] ne 'w') { $dry{($y-1).",$x"} = $res->[$y-1][$x]; }

#	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($found) = 0;
	    DRY: foreach my $coord (sort {$dry{$a} <=> $dry{$b}} (keys %dry)) {
		my($ny,$nx) = split /,/,$coord;
		delete $dry{$coord};
		if($typ->[$ny][$nx] ne "w") {
		    $found = 1;
		    $x = $nx;
		    $y = $ny;
		    last DRY;
		}
	    }
	    if(!$found) {
		print "Maxxed!<br>\n";
		$bot = 1;
	    }
	}
    }
}

sub disp_res {
    my($res,$typ,$dist) = @_;
    my($scale) = $params{scale};
    my $img = new GD::Image($width*$scale,$height*$scale,1);
    $img->fill(1,1,icolor(255,255,255,$img));
    for($r=0;$r<=$#$res;$r++) {
	for($c=0;$c<=$#{$res->[$r]};$c++) {
	    my(@c) = color($res->[$r][$c],$minval,$maxval,$typ->[$r][$c],$dist->[$r][$c]);
#	    if($water_order->[$r][$c]) {
#		my($cv) = 255-10*$water_order->[$r][$c];
#		@c = ($cv,0,0);
#	    }
	    $img->filledRectangle($c*$scale,$r*$scale,$c*$scale+$scale-1,$r*$scale+$scale-1,icolor(@c,$img));
	}
    }

    open(PNG,"> /home/dave/public_html/images/tmp/landscape4.png");
    binmode PNG;
    print PNG $img->png;
    close PNG;
    print "<img src=\"/~dave/images/tmp/landscape4.png\">\n";

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

#New set_heights -- find heights in different order
sub set_heights_new {
    my($x,$y,$d,$depth) = @_;
    my $sd = $d/2;
    my($ul,$ur,$ll,$lr,$md);
    $ul = $heights[$x][$y];
    $ur = $heights[$x+$d][$y];
    $ll = $heights[$x][$y+$d];
    $lr = $heights[$x+$d][$y+$d];
    my $multiplier = $d/$pmax;
    if($params{start_iters}) {
	if($depth <= $params{start_iters}) {
	    $multiplier = $pmax;
	} else {
	    $multiplier = 1/(2**($depth-$params{start_iters}));
	}
    }

    #middle
    if(!defined($heights[$x+$sd][$y+$sd])) {
	$heights[$x+$sd][$y+$sd] = ($ul + $ur + $ll + $lr)/ 4;
	my $r = rand ((($rscale_w+$rscale_h)/2)*($multiplier*($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; }
    }
    $md = $heights[$x+$sd][$y+$sd];

    #top
    if(!defined($heights[$x+$sd][$y])) {
	if($y-$sd>=0 && defined($heights[$x+$sd][$y-$sd])) {
	    $heights[$x+$sd][$y] = ($ul + $ur + $md + $heights[$x+$sd][$y-$sd]) / 4;
	} else {
	    $heights[$x+$sd][$y] = ($ul + $ur + $md) / 3;
	}
	#my $r = rand ($rscale_w*(($d/$pmax)*($hrandval-$lrandval)+$lrandval));
	my $r = rand ($rscale_w*($multiplier*($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])) {
	if($x-$sd>=0 && defined($heights[$x-$sd][$y+$sd])) {
	    $heights[$x][$y+$sd] = ($ul + $ll + $md + $heights[$x-$sd][$y+$sd]) / 4;
	} else {
	    $heights[$x][$y+$sd] = ($ul + $ll + $md) / 3;
	}
	my $r = rand ($rscale_h*($multiplier*($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])) {
	if($x+$d+$sd <= $width && defined($heights[$x+$d+$sd][$y+$sd])) {
	    $heights[$x+$d][$y+$sd] = ($ur + $lr + $md + $heights[$x+$d+$sd][$y+$sd]) / 4;
	} else {
	    $heights[$x+$d][$y+$sd] = ($ur + $lr + $md) / 3;
	}
	my $r = rand ($rscale_h*($multiplier*($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])) {
	if($y+$d+$sd <= $height && defined($heights[$x+$sd][$y+$d+$sd])) {
	    $heights[$x+$sd][$y+$d] = ($ll + $lr + $md + $heights[$x+$sd][$y+$d+$sd]) / 4;
	} else {
	    $heights[$x+$sd][$y+$d] = ($ll + $lr + $md) / 3;
	}
	my $r = rand ($rscale_w*($multiplier*($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; }
    }
    if($sd > 1) {
	set_heights_new($x,$y,$sd,$depth+1);
	set_heights_new($x+$sd,$y,$sd,$depth+1);
	set_heights_new($x,$y+$sd,$sd,$depth+1);
	set_heights_new($x+$sd,$y+$sd,$sd,$depth+1);
    }
}

sub set_heights {
    my($x,$y,$d,$depth) = @_;
    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];
    my $multiplier = $d/$pmax;
    if($params{start_iters}) {
	if($depth <= $params{start_iters}) {
	    $multiplier = $pmax;
	} else {
	    $multiplier = 1/(2**($depth-$params{start_iters}));
	}
    }
    #top
    if(!defined($heights[$x+$sd][$y])) {
	$heights[$x+$sd][$y] = ($ul + $ur) / 2;
	#my $r = rand ($rscale_w*(($d/$pmax)*($hrandval-$lrandval)+$lrandval));
	my $r = rand ($rscale_w*($multiplier*($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*($multiplier*($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*($multiplier*($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*($multiplier*($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)*($multiplier*($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,$depth+1);
	set_heights($x+$sd,$y,$sd,$depth+1);
	set_heights($x,$y+$sd,$sd,$depth+1);
	set_heights($x+$sd,$y+$sd,$sd,$depth+1);
    }
}

sub color {
    my($val,$min,$max,$type,$dist) = @_;
    my($c) = int((($val-$min)/($max-$min))*255);
    if($type eq 'w') { #water
	#return (0,0,255);
	if($val > 90) {
	    return ($c,$c,255); #Frozen lake
	} else {
	    return ($c/2,$c/2,($c<64)?64:$c);
	}
    } elsif($type eq 's') { #snow
	$c1 = $c - (255-$c);
	return($c1,$c1,$c);
    } elsif($type eq 'o') { #ocean
	#return(0,0,127);
	if($c<=0) {
	    return (0,0,64);
	}
	return ($c/2,$c/2,($c<64)?64:$c);
    } elsif($type eq 'f') { #forest
	#return(0,191,0);
	$c+=50;
	return ($c/4,$c/2,$c/4);
    } elsif($type eq 'g') { #grass
	#return(0,255,0);
	$c+=50;
	return ($c/3,$c/1.5,$c/4);
    } elsif($val > 80) { #tree line?
	#return (255,255,255);
	$c+=(50*($val-80)/20);
	return($c/1.15,$c/1.58,$c/4.03);

	if($val < 85) { #grass line?
	    return($c/2,$c/2,$c/4);
	} elsif($val < 90) {
	    return($c,$c/1.5,$c/2);
	} elsif($val < 95) {
	    return($c,$c/1.2,$c/1.5);
	} else {
	    return($c,$c,$c);
	}
    } elsif($dist >= 40) {
	#return(255,255,0);
	$c+=50;
	#return($c/1.5,$c/1.25,$c/4);
	if($dist <= 42) {
	    return($c/1.54,$c/1.34,$c/3.79);
	} elsif($dist <= 44) {
	    return($c/1.49,$c/1.37,$c/3.82);
	} elsif($dist <= 46) {
	    return($c/1.43,$c/1.41,$c/3.86);
	} elsif($dist <= 48) {
	    return($c/1.37,$c/1.44,$c/3.89);
	} elsif($dist <= 50) {
	    return($c/1.31,$c/1.48,$c/3.93);
	} elsif($dist <= 52) {
	    return($c/1.26,$c/1.51,$c/3.96);
	} else {
	    return($c/1.20,$c/1.55,$c/4.00);
	}
    } else {
	
	$c+=($dist*5/4);

	return($c/1.6,$c/1.3,$c/3.75);
	#return ($c,$c,$c);
    }
}

sub icolor {
    my($r,$g,$b,$img) = @_;
    if($r>255) { $r = 255; } elsif($r < 0) { $r=0; }
    if($g>255) { $g = 255; } elsif($g < 0) { $g=0; }
    if($b>255) { $b = 255; } elsif($b < 0) { $b=0; }
    if(!defined($pal{"$r\_$g\_$b"})) {
        $pal{"$r\_$g\_$b"} = $img->colorAllocate($r,$g,$b);
    }
    return $pal{"$r\_$g\_$b"};
}

sub disp_grid {
    my($grid) = @_;
    print "<table>\n";
    for($y=0;$y<=$height;$y++) {
	print "<tr>";
	for($x=0;$x<=$width;$x++) {
	    print "<td>".$grid->[$y][$x];
	}
	print "\n";
    }
    print "</table>\n";
}