Complex Mapping Problem

idgarad has asked for the wisdom of the Perl Monks concerning the following question:

I am exploring some procedural map development using perl as a simulation language for taking an arbitrary map size of X by Y and generating randomly a desireability for land. (Say 1 to 100).

Then I set a threshold of say 60 and any areas that are 60 or higher become Village canidates.

Here is where things get weird.

PASS 1 Using a virutal cell size of 1x1 we do a pass and if any 2 squares touch they are converted into a 2x2 town and as we scan later we ignore any other village squares that fall inside the new towns. (We are allocating SPACE for villages, town, cities, capitals for use later in placement) Once we have scanned through and merged villages into towns we then merge adjacent towns into 4x4 cities (ignoring any overlapping towns from there on out.) We then scan through and merge any adjacent cities into 8x8 capitals. We then nuke (ignore) and of the village squares inside the capital area we found.

PASS 2 We now upsize the virutal grid to a 2x2 cell size. We then repeat the same process as in pass one, it's just that we have doubled the virtual cell size. The difference though on pass 2 is we de-allocate villages for both found capitals AND cities.

PASS 3 We now use a virtual grid size of 3x3. Same process but now we deallocate TOWN, CITIES, and CAPITALs if any are found.

PASS 4 With a virtial grid size of 4x4 we scan and detect and remaining villages.

PASS 5 With all the areas allocate within each allocated area we randomly place a village, town, city, or capital within the areas we found earlier.

For instance the last village we find in PASS 4 would have an area of 4x4 so we would randomly place a village in that area.

Villages are 1x1 Towns are 2x2 Cities are 4x4 Capitals are 8x8

So a capital found in PASS 1 wouldn't be randomly placed as it takes up the whole 8x8 area already.

It's a weird algorithm I found that the small the town, the less dense it is so we use this map technique to develop progressively less dense areas radiating out from high density areas.

I am running into several problems though as I try to take this manual process (I do it with pencil and highlighters) and code it into perl:

PROBLEM 1: Mapping a grid and testing the adjacent cells WITHOUT WRAPPING AND IGNORING NON-EXISTING LOCATIONS.
For instance I am scanning left to right, top to bottom. At 0,0 (Upper left corner) I want to see if the cell to the right, down-right, and down have a V in them. If so then 0,0 becomes a T (TEMPORARILY) and we flag (TEMPORARILY) 0,1 1,0 and 1,1 to be ignored (they are now in the town allocation). Then we continue on with the algorithm.
so we do have a bit of a cheat, we will always be scanning from an origin point and going right and down rather then a centered scan. I get confused when I have to scale of the virtual grid size. I could tweak it to take into account all 8 directions really but I only use all 8 in smoothing the random values.

PROBLEM 2: Scanning with virtual CELL sizes. The grid is easy to generate but handling the virtual size test I am at a loss on how to handle. I was thinking of cheating and creating a bitmap version of the data grid and using a CPAN module to test for overlapping.

Below is my existing code so far and executing it will output everything so far up to starting the village placement.

It's a really interesting algorithm to play with. I have been using it for about 17 years for generating maps for role playing games, I'd just like to get it coded up so others can use it and play with the thesholds and stuff.
I normally use big 400x400 sheets and use a scale of 1-100 for placing the initial cells with a threshold of 65.

It's easy to do by hand but translating it into code is a pain. By hand it takes me about 5-6 hours to do but I really have liked the results (Take an arial photo of an area. Assign desirability to an overlaid grid, process the algorithm.)

#
use strict;
#


#TO DO
# Virtual GRID SUPPORT SO WE CAN DO POST-PASS 1
my $max_y=200;
my $max_x=200;
my $rCap=100;
my $threshold=65;
my $empty= chr(176);
my $village="v";
my $town="t";
my $city="c";
my $capital="p";


my @grid = ();



for(my $i=0; $i < $max_y;$i++)
{
    for(my $j=0;$j < $max_x; $j++)
    {
      my $randi = int(rand($rCap));
      push @grid, { x => $j, y => $i, value => $randi, type => $empty,
+ locked => 0 }
    }
}

smooth(\@grid);
purge(\@grid);

print "----- Placing Villages-----\n";
mapVillages(\@grid);showmap(\@grid);



#functions
sub showmap {
my $grid = @_;
print "----- MAP $max_x by $max_y\n";

my $currentCell=0;

for(my $i=0; $i < $max_y;$i++)
{
    for(my $j=0;$j < $max_x; $j++)
    {
        print $grid[$currentCell]{type};
            $currentCell++;
    }
    print "\n";
}

}



sub smooth {
my($grid) = @_;
my $currentCell=0;
for(my $i=0; $i < $max_y;$i++)
{
    for(my $j=0;$j < $max_x; $j++)
    {
        my @average=();
        #########
        # SELF
        push @average, $grid[$currentCell]{value};
        #print "S:$grid[$currentCell]{value}\t";
        #########

        #########
        #find UP
        if($currentCell - $max_x >= 0) {
        push @average, $grid[$currentCell - $max_x]{value};
        #print "U:$grid[$currentCell - $max_x]{value}\t";

        }
        #########
        #########
        #find DOWN
        if($currentCell + $max_x >= 0) {
        push @average, $grid[$currentCell + $max_x]{value};
        #print "D:$grid[$currentCell + $max_x]{value}\t";
        }
        #########
        #########
        #find LEFT
        if($currentCell - 1 >= 0) {
        push @average, $grid[$currentCell - 1]{value};
        #print "L:$grid[$currentCell - 1]{value}\t";
        }
        #########
        #########
        #find RIGHT
        if($currentCell + 1 >= 0) {
        push @average, $grid[$currentCell + 1]{value};
        #print "R:$grid[$currentCell + 1]{value}\t";
        }
        #########
        #########
        #find UP-L
        if($currentCell - $max_x+1 >= 0) {
        push @average, $grid[$currentCell - $max_x+1]{value};
        #print "UL:$grid[$currentCell - $max_x+1]{value}\t";
        }
        #########
        #########
        #find UP-R
        if($currentCell - $max_x-1 >= 0) {
        push @average, $grid[$currentCell - $max_x-1]{value};
        #print "UR:$grid[$currentCell - $max_x-1]{value}\t";
        }
        #########
        #########
        #find DOWN-L
        if($currentCell + $max_x-1 >= 0) {
        push @average, $grid[$currentCell + $max_x-1]{value};
        #print "DL:$grid[$currentCell + $max_x-1]{value}\t";
        }
        #########
        #########
        #find DOWN-R
        if($currentCell + $max_x+1 >= 0) {
        push @average, $grid[$currentCell + $max_x+1]{value};
        #print "DR:$grid[$currentCell + $max_x+1]{value}\t";
        }
        #########
        
        
        my $newAvg=int(&average(\@average));
        #print "Changing $grid[$currentCell]{value} to $newAvg\n";
        $grid[$currentCell]{value}=$newAvg;

      $currentCell++;
    }

}
}


sub average { 
@_ == 1 or die ('Sub usage: $average = average(\@array);'); 
my ($array_ref) = @_; 
my $sum; 
my $count = scalar @$array_ref; 
foreach (@$array_ref) { $sum += $_; } 
return $sum / $count; 
} 

sub median { 
@_ == 1 or die ('Sub usage: $median = median(\@array);'); 
my ($array_ref) = @_; 
my $count = scalar @$array_ref; 
# Sort a COPY of the array, leaving the original untouched 
my @array = sort { $a <=> $b } @$array_ref; 
if ($count % 2) { 
return $array[int($count/2)]; 
} else { 
return ($array[$count/2] + $array[$count/2 - 1]) / 2; 
} 
}


sub purge {
my $grid = @_;
my $currentCell=0;

for(my $i=0; $i < $max_y;$i++)
{
    for(my $j=0;$j < $max_x; $j++)
    {
        if ($grid[$currentCell]{value} < $threshold) { $grid[$currentC
+ell]{value}=0} else {$grid[$currentCell]{type} =$village;}
            $currentCell++;
    }
}

}

sub mapVillages {
my($grid) = @_;

my $currentCell=0;

for(my $i=0; $i < $max_y;$i++)
{
    for(my $j=0;$j < $max_x; $j++)
    {

        if($grid[$currentCell]{type} eq $village) {
#################### BIG CODE HERE

### Check Neighbors if also village if so set ourselves as a town.
#########
        
        #########
        #find UP
        if(($currentCell - $max_x >= 0) && ($grid[$currentCell - $max_
+x]{type} eq $village)) {
        $grid[$currentCell]{type} = $town;
        $grid[$currentCell - $max_x]{type} = $empty;
        }
        #########
        #########
        #find DOWN
        if(($currentCell + $max_x >= 0) && ($grid[$currentCell + $max_
+x]{type} eq $village)) {
        $grid[$currentCell]{type} = $town;
        $grid[$currentCell + $max_x]{type} = $empty;
        }
        #########
        #########
        #find LEFT
        if(($currentCell - 1 >= 0) && ($grid[$currentCell - 1]{type} e
+q $village)) {
        $grid[$currentCell]{type} = $town;
        $grid[$currentCell - 1]{type} = $empty;
        }
        #########
        



#################### END BIG CODE
        } 
        $currentCell++;
    }

}
}
[download]

So in short: Best way to handle scanning corrdinates and best way to handle the virtual grid size?

Comment on Complex Mapping Problem Download Code

Replies are listed 'Best First'.
Re: Complex Mapping Problem by jethro (Monsignor) on Feb 17, 2009 at 19:24 UTC
I don't understand what you mean by 'deallocate' on the later passes. And what do you do on the later passes if the type in the subcells of a virtual grid differ ? My guess is that you ignore such a virtual grid location except if the other type is 'empty'. The following is based on this assumption. You might change the grid to a two-dimensional array, that makes the code a bit more readable I think You should create a lot of helper functions that operate on the grid in an abstract way (object-oriented design would be even better, but I don't know if you know enough about that). You should have a function `get_area(x,y,virtualgridsize,villagesize)`. x and y are the coordinates of the upper left corner, gridsize is 1,2,3,4..., villagesize could be 1,2,3,8 or for readability you could have strings like 'village', 'town'... This function should return an error code (for example 0) if the area is partly outside of the grid so you can simply do a foreach over the gridsize when you call this function and not worry about the edge cases. If successful it should return a reference to an array of size villagesize x villagesize, with any array value corresponding to one virtual grid cell. Typical code would then look like this `foreach my $x (0..$maxx) { foreach my $y (..$maxy) { if (my $area= get_area($x,$y,virtgridsize,'town')) { ...` [download] If you have that function, create another higher-level function that calls get_area() and checks if all cells belong to one type or are empty. If yes, it returns the type, otherwise -1. This function would be called get_type_of_area(x,y,virtgridsize,villagesize) Another function would be called set_area(type,x,y,virtgridsize,villagesize), that sets all cells to type 'type' Now build ever higher functions out of these until you have just 5 calls to some function for every pass. What you want to arrive at is that for example checks whether some x coordinate is out of bounds or the handling of the virtual grid size is handled in some low level functions that do just the right thing. The higher level functions should only get the information in an abstraction that is useful for them. The functions I proposed are only an example. If they don't do what you need, change them. But you need to refactor your problem into easier blocks and have this kind of abstraction so that you can reuse code and not have to write the same loops with slight variations over and over again.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re: Complex Mapping Problem
by jethro (Monsignor) on Feb 17, 2009 at 19:24 UTC

I don't understand what you mean by 'deallocate' on the later passes. And what do you do on the later passes if the type in the subcells of a virtual grid differ ? My guess is that you ignore such a virtual grid location except if the other type is 'empty'. The following is based on this assumption.

You might change the grid to a two-dimensional array, that makes the code a bit more readable I think

You should create a lot of helper functions that operate on the grid in an abstract way (object-oriented design would be even better, but I don't know if you know enough about that). You should have a function get_area(x,y,virtualgridsize,villagesize). x and y are the coordinates of the upper left corner, gridsize is 1,2,3,4..., villagesize could be 1,2,3,8 or for readability you could have strings like 'village', 'town'...

This function should return an error code (for example 0) if the area is partly outside of the grid so you can simply do a foreach over the gridsize when you call this function and not worry about the edge cases. If successful it should return a reference to an array of size villagesize x villagesize, with any array value corresponding to one virtual grid cell. Typical code would then look like this

foreach my $x (0..$maxx) {
  foreach my $y (..$maxy) {
    if (my $area= get_area($x,$y,virtgridsize,'town')) {
      
...
[download]

If you have that function, create another higher-level function that calls get_area() and checks if all cells belong to one type or are empty. If yes, it returns the type, otherwise -1. This function would be called get_type_of_area(x,y,virtgridsize,villagesize)

Another function would be called set_area(type,x,y,virtgridsize,villagesize), that sets all cells to type 'type'

Now build ever higher functions out of these until you have just 5 calls to some function for every pass. What you want to arrive at is that for example checks whether some x coordinate is out of bounds or the handling of the virtual grid size is handled in some low level functions that do just the right thing. The higher level functions should only get the information in an abstraction that is useful for them.

The functions I proposed are only an example. If they don't do what you need, change them. But you need to refactor your problem into easier blocks and have this kind of abstraction so that you can reuse code and not have to write the same loops with slight variations over and over again.

[reply]
[d/l]
[select]