Jeffro's Space Gaming Blog

Microgames, Monster Games, and Role Playing Games

The Toy Universe: Exploring Dot Maps

Okay, time to go back to our first program and fold in some of the tools we worked out during the second and third installments of this series. And note how distracting mathematics can be. It’s dangerous stuff– especially when the math turns out to be more interesting than any sort of game we’d want to make. This week’s code adds in a few minor features that we can hopefully leverage later on, so maybe the math and coding are now boring enough that we have some impetus to get back to our original objective: exploratory game design.

The first problem we need to overcome has to do with the way we’re rigging up our pseudo-random number generators. We have a slightly different function for each hex on the map. But then… we didn’t want to risk getting too little information back when we iterate the function, so we took some time to find the best seed possible. Unfortunately, this takes time… a long time given that we haven’t spent any effort in making our code efficient or fast. So, what I did in this installment was to add in some code to save back these seeds… and then only look a seed if we don’t already have it “on file.” Here’s all the seeds for a subsector-sized map:

{“0403″:”6698″,”0101″:”7714″,”0606″:”4143″,”0810″:”0245″,”0703″:”1933”,
“0402”:”7509″,”0707″:”4121″,”0307″:”5467″,”0106″:”5063″,”0806″:”2578″,
“0605”:”1682″,”0804″:”1613″,”0309″:”0856″,”0107″:”6579″,”0704″:”1729″,
“0405”:”6222″,”0204″:”4947″,”0507″:”2322″,”0603″:”0402″,”0102″:”3850″,
“0602”:”2193″,”0202″:”7551″,”0505″:”7794″,”0104″:”0376″,”0708″:”5210″,
“0610”:”3839″,”0601″:”5182″,”0404″:”0517″,”0303″:”5565″,”0801″:”7228″,
“0706”:”7860″,”0604″:”7764″,”0108″:”0247″,”0305″:”6578″,”0406″:”5263″,
“0203”:”8095″,”0103″:”5719″,”0807″:”8311″,”0409″:”4010″,”0408″:”1188″,
“0503”:”1051″,”0705″:”9554″,”0609″:”6303″,”0207″:”3097″,”0201″:”8309″,
“0803”:”9806″,”0210″:”6888″,”0308″:”0877″,”0701″:”3837″,”0301″:”0967″,
“0306”:”5079″,”0206″:”5020″,”0109″:”4325″,”0407″:”1211″,”0805″:”2421″,
“0110”:”2397″,”0208″:”0443″,”0310″:”0644″,”0504″:”5863″,”0802″:”0424″,
“0501”:”5848″,”0410″:”9013″,”0302″:”0102″,”0105″:”6415″,”0502″:”0573″,
“0401”:”1231″,”0510″:”2691″,”0209″:”0857″,”0809″:”6734″,”0702″:”0579″,
“0509”:”0099″,”0506″:”3686″,”0710″:”7146″,”0709″:”7725″,”0304″:”4101″,
“0205”:”9344″,”0607″:”8287″,”0808″:”9299″,”0508″:”2446″,”0608″:”0400″}

So far I’ve avoided libraries and funky tools so that the code is all-in-one-file and relatively clear. In this case, I broke with that. By using File:Slurp from CPAN, you don’t have to look at any I/O operations. By using JSON¹, we can save the data structures we depend on without having to really give thought to parsing and file formats. Plus… everything is in text if we need to go back and do some extra hacking later on…!

Which brings us to another point…. Our little sample application is pretty much a custom command line environment, right? And all our commands are pure text, right…? So, given that we’ve already taken the trouble to save and load these seeds on the fly, I’ve added in some commands to save and load the program’s command history. This will let us explore and tinker with various universes… and then save them back for later. A nice side effect here is that we end up with a macro-language for the program that even non-programmers can use to develop and manage our universe-building tools.

Finally… our third feature for the week lets us put our iterative functions to work by making our first star maps. The way it works is, for each hex… we plug that hex’s “best” seed into that hex’s function. If the resulting number is between the range that we set, then there’s a star in that system. Simple and anticlimactic, I know… but we’ll be getting some more use out of these seeds and function in future installments.

Even though we’re only testing the waters here, I think you might be surprised at what can be done just with what we have so far. With a very small investment of coding time, we can generate a hex map… and then gradually turn up the stellar density until things look about right.  Then using the display command, we can zoom in on the exact region we want to look at. We can then save our work-in-progress so that we don’t have to redo all of those commands after we implement new features… and we don’t have to look up our “best” seeds anymore unless we increase the map’s size. See you next time for some world building!

Sample Run:

Welcome to the toy universe!
You are now at 0406.

> d 0 3500
Making dots between 0 and 3500.
Found world in 0101 with seed 7714: 2872
Found world in 0106 with seed 5063: 0553
Found world in 0108 with seed 0247: 0488
Found world in 0109 with seed 4325: 2777
Found world in 0110 with seed 2397: 2696
Found world in 0201 with seed 8309: 3444
Found world in 0203 with seed 8095: 1164
Found world in 0205 with seed 9344: 2674
Found world in 0208 with seed 0443: 1944
Found world in 0302 with seed 0102: 0361
Found world in 0303 with seed 5565: 2079
Found world in 0401 with seed 1231: 3131
Found world in 0405 with seed 6222: 1476
Found world in 0406 with seed 5263: 2084
Found world in 0410 with seed 9013: 0839
Found world in 0503 with seed 1051: 2916
Found world in 0506 with seed 3686: 2009
Found world in 0508 with seed 2446: 2655
Found world in 0509 with seed 0099: 1282
Found world in 0510 with seed 2691: 0343
Found world in 0603 with seed 0402: 2981
Found world in 0608 with seed 0400: 2417
Found world in 0706 with seed 7860: 0719
Found world in 0707 with seed 4121: 2015
Found world in 0708 with seed 5210: 2403
Found world in 0801 with seed 7228: 2918
Found world in 0802 with seed 0424: 2163
Found world in 0806 with seed 2578: 1243
Found world in 0807 with seed 8311: 2625
Found world in 0809 with seed 6734: 0002

> display
   *   .   .   .
     *   *   .   *
   .   *   .   .
     .   .   .   *
   .   *   *   .
     *   .   *   .
   .   .   .   .
     .   .   .   .
   .   .   .   .
     *   *   .   .
   *   .   *   *
     .   *   .   *
   .   .   .   *
     .   .   .   *
   *   .   *   *
     *   .   *   .
   *   .   *   .
     .   .   .   *
   *   .   *   .
     .   *   .   .

> display 4 6
   *   .
     *   *
   .   *
     .   .
   .   *
     *   .
   .   .
     .   .
   .   .
     *   *
   *   .
     .   *

> display 4 6 2 2
   *
     .   .
   *
     *   .
   .
     .   .
   .
     *   *
   .
     .   *

> save example.toy

> x

The code:

#!/usr/bin/perl
use Modern::Perl;
use File::Slurp;
use JSON;

my %map;
my %worlds;
my %state;
my %seeds;
my $size = 4;
my @history;
my ($min_x, $min_y) = (1,1);
my ($max_x, $max_y) = (0,0);

my %commands = (
    "x" => sub { exit(); },
    "l" => \&load_map,
    "s" => \&show_map,
    "j" => \&jump,
    "m" => \&move,
    "d" => \&dots,
    "display" => \&display,
    "clear" => \&clear,
    "save" => \&save,
    "load" => \&load,
    );

sub load_map {
    my ($x, $y) = @_;
    die "Map size ($x,$y) is too big!" if $x > 99 || $y > 99;
    ($max_x, $max_y) = ($x,$y);
    undef(%map);
    for (1..$x) {
	my $a = $_;
	for (1..$y) {
	    my $b = $_;
	    my $hex = get_coords($a,$b);
	    $map{$hex} = "";
	    unless ($seeds{$hex}) {
		$seeds{$hex} = find_seed($hex);
	    }
	}
    }
    save_seeds();
}

sub get_coords {
    my ($x, $y) = @_;
    $x = "0$x" if $x < 10;
    $y = "0$y" if $y < 10;
    return "$x$y";
}

sub show_map {
    print "Hexes: ";
    map {
	print " $_";
    } sort keys %map;
    print "\n\n";
}

sub jump {
    my ($to) = @_;
    if (exists ($map{$to})) {
	$state{cur} = $to;
	say "You are now at $to.";
    } else {
	say "There is no location at hex $to.";
    }
}

sub move {
    my $dir = shift(@_);
    my ($x, $y);
   
    ($x, $y) = ($1, $2) if $state{cur} =~ /(\d{2})(\d{2})/;
    $x =~ s/^0+//;
    $y =~ s/^0+//;
 
    if ($dir == 8) {
	$y -= 1; #North
    } elsif ($dir == 2) {
	$y += 1; #South
    } elsif ($dir == 7) {
	$x -= 1; #Northwest
	$y -= 1 unless ($x % 2);
    } elsif ($dir == 9) {
	$x += 1; #Northeast
	$y -= 1 unless ($x % 2);
    } elsif ($dir == 1) {
	$x -= 1; #Southwest
	$y += 1 if ($x % 2);
    } elsif ($dir == 3) {
	$x += 1; #Southeast
	$y += 1 if ($x % 2);
    }
  
    my $c = get_coords($x,$y);
    if (exists $map{$c}) {
	$state{cur} = $c;
	if (scalar @_) {
	    move(@_);
	} else {
	    say "You are now at $c.";
	}
    } else {
	say "That is off the map!";
    }
}

sub vonJeffmann2013 {
    my ($size,$hex) = @_;
    $hex = 1 unless $hex;
    return sub {
	my $x = shift || 0;
	$x = ($x * $hex)**2 + $hex**5;
	$x = "0" x (8 - length($x)) . $x if length($x) < 8;
	my $start = int(length($x)/2) - $size/2;
	return substr($x,$start, $size);
    }
}

sub destructing_iterator {
    my ($seed, $function) = @_;;
    my %history;
    $history{$seed}++;
    return sub {
	$seed = $function->($seed);
	return if $history{$seed};
	$history{$seed}++;
	return $seed;
    }
}

sub analyze {
    my ($seed, $f) = @_;
    my $di = destructing_iterator($seed, $f);
    my %history;
    my $count = 0;
    my $last;
    $history{$seed} = $count;
    while (my $x = $di->()) {
	$count++;
	$history{$x} = $count;
	$last = $x;
    }    
    my $loopstart =  $f->($last);
    my $val = $history{$f->($last)} || 1;
    my $looplength = $count - $val + 1;
    my $treelength = $count - $looplength;

    return ($count, $looplength, $treelength, $looplength);
}

sub get_function {
    my ($hex) = @_;
    return vonJeffmann2013($size, $hex);
}

sub find_seed {
    my $hex = shift;
    say "... Finding best seed for hex $hex.";
    my $f = get_function($hex);

    my $bigtree = -1;
    my %tree;
    for (0..9999) {
	my $seed = $_;
	$seed = "0" x (4 - length($seed)) . $seed;
	my ($length, $loopstart, $treelength, $looplength) = analyze($seed, $f);
	$tree{$seed} = $treelength;
	$bigtree = $seed if $treelength > ($tree{$bigtree} || 0);
    }
    return $bigtree;
}

sub save_seeds {
    my $json = JSON->new->allow_nonref;
    write_file("seeds.json", $json->encode( \%seeds ));
}

sub clear {
    undef(%map);
    undef(%worlds);
    # leave seeds alone!
}

sub dots {
    my ($min, $max) = @_;
    say "Making dots between $min and $max.";

    map {
	my $hex = $_;
	unless ($worlds{$hex}) {
	    my $f = get_function($hex);
	    my $value = $f->($seeds{$hex});
	    if ($value >= $min && $value <= $max) {
		say "Found world in $hex with seed $seeds{$hex}: $value";
		$worlds{$hex}++;
	    }
	}
    } sort keys %map;
}

sub display {
    my ($x2, $y2, $x1, $y1) = @_;
    $x1 = $min_x unless $x1;
    $y1 = $min_y unless $y1;
    $x2 = $max_x unless $x2;
    $y2 = $max_y unless $y2;
    if ($x1 < $min_x) {
	say "Display x1 must be less than $min_x.";
	return;
    }
    if ($y1 < $min_y) {
	say "Display y1 must be less than $min_y.";
	return;
    }
    if ($x2 > $max_x) {
	say "Display x2 must be less than $max_x.";
	return;
    }
    if ($y2 > $max_y) {
	say "Display y2 must be less than $max_y.";
	return;
    }

    for ($y1..$y2) {
	my $y = $_;
	my $one = "";
	my $two = "  ";
	for ($x1..$x2) {
	    my $x = $_;
	    my $hex = get_coords($x,$y);
	    my $c = ".";
	    $c = "*" if $worlds{$hex};
	    if ($x%2) {
		$one .= "   $c";
	    } else {
		$two .= "   $c";
	    }
	}
	print $one . "\n";
	print $two . "\n";
    }
}

sub save {
    my $file = shift || "default.toy";
    my $json = JSON->new->allow_nonref;
    write_file($file, $json->encode( \@history ));
}

sub load {
    my $file = shift || "default.toy";
    my $json = JSON->new->allow_nonref;
    @history = @{ $json->decode( read_file($file) ) };
    map {
	say "> $_";
	execute($_);
	say "";
    } @history;
}

sub execute {
    my ($x, $record) = @_;
    push(@history, $x) if $record;
    my @args = split(/\s+/, $x);
    my $c = shift(@args);
    
    if ($commands{$c}) {
	$commands{$c}->(@args);
    }
}

if (-e "seeds.json") {
    my $json = JSON->new->allow_nonref;
    %seeds = %{ $json->decode( read_file('seeds.json') ) };
}

unless (-e "default.toy") {
    execute("l 8 10", 1);
    say "Welcome to the toy universe!";
    execute("j 0406", 1);
} else {
    load("default.toy");
}

while (1) {
    print "\n> ";
    my $x = <STDIN>;
    chomp($x);
    push(@history, $x) unless $x =~ /^save/i;
    execute($x);
}

¹ Thanks to GURPS author, gamemaster, and man-in-black Roger Burton West for pointing me in the direction of using JSON in this manner. It has saved me a tremendous amount of pain over the past year or so and is greatly appreciated.

Advertisements

One response to “The Toy Universe: Exploring Dot Maps

  1. Robert Eaglestone August 5, 2013 at 8:40 am

    Rather than JSON, I’d suggest using Data::Dumper.

    Then, when you need to export your data to some requestor, then you can tell Data::Dumper to dump using the “:” pair operator, in effect turning the output into pure JSON.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: