Jeffro's Space Gaming Blog

Microgames, Monster Games, and Role Playing Games

The Toy Universe: Exploring Iterative Functions

What functions look like when they’re iterated: several “trees” of connecting paths lead to repeating “loops” of varying lengths.

In our first installment of this series, we spun up a simple hex map program to use as the basis for some exploratory game programming. Last time we started experimenting with Von Neumann’s middle-square method to see if we could get some use out of it. Hopefully you messed around with that last bit a little as it could help you get a feel for the behavior that emerges when you start iterating a function. Even if you didn’t, though, I’m going to spill the beans here.

When we set up a function to do the middle square method, we are limiting its domain when we set the number of digits we’re going to keep after we drop them from both ends. In our example, the function returns a number between 0 and 9999 for any number that we feed into it. If we take the number that we get back and feed it in again… then we get a new number. Keep doing that and we get what looks like a series of random numbers. But there’s a catch: sooner or later we’ll get back a number that we’ve already gotten and a repeating sequence emerges.

Now… the place where we were going to use these sequences of numbers is in the context populating a hex map with worlds to explore. If we tried to use the same function with every hex on the map, then all the hexes would be using similar sets of numbers. If the function only had a few “loops” in them, then those same loops would end up emerging almost everywhere. This is so un-random that it could be noticeable even if it was obfuscated by random world creation routines! Another problem is that some seeds will return themselves; they won’t generate a series at all!

Now… a lot of people have done a lot of work on this problem. There are many, many ways to work around it. Here’s my solution, which… if not especially brilliant is hopefully at least interesting to tinker with. We set up a system to generate a different function for each hex. This will ensure that the “shape” of the function in each hex is different. The other thing we do is to make sure that we get the best possible seed for those functions. We can do that by analyzing them and then pulling out the number that will yield the longest sequence of random-looking numbers.

Here is the sample output from my program that demonstrates this. (Note that I call the series that precedes the sequence that loops back on itself a “tree” due to the branching nature of the way other paths lead into it.)

————————————————————
Hex: 0101
BiggestTree: 7714 —> 147 + 29 = 176
————————————————————
Hex: 0102
BiggestTree: 3850 —> 165 + 9 = 174
————————————————————
Hex: 0103
BiggestTree: 5719 —> 334 + 12 = 346
————————————————————
Hex: 0104
BiggestTree: 0376 —> 176 + 6 = 182
————————————————————
Hex: 0105
BiggestTree: 6415 —> 206 + 58 = 264
————————————————————
Hex: 0106
BiggestTree: 5063 —> 137 + 54 = 191
————————————————————
Hex: 0107
BiggestTree: 6579 —> 140 + 42 = 182
BiggestLoop: 0073 —> 130 + 72 = 202
————————————————————
Hex: 0108
BiggestTree: 0247 —> 220 + 39 = 259
————————————————————

<—- SNIP! —->

Looks like it works! The Von Neumann method squares a number and then drops digits off either end. My hack to it multiplies the number by the hex number before squaring. To prevent the situation where a sequence of zeroes repeats over and over, I also add the hex number taken to the fifth power before dropping off digits on each end. This may not be perfect and it may not be super-fast, but it does produce a series of at least 97 numbers for each hex on a map the size of a Traveller subsector. Again, there’s a lot of other ways you could do this… but my approach is sufficient for what I want to do, so I’ll move on to seeing what we can do with this stuff.

The code:


#!/usr/bin/perl
use Modern::Perl;

my %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 load_map {
    my ($x, $y) = @_;
    die "Map size ($x,$y) is too big!" if $x > 99 || $y > 99;
    undef(%map);
    for (1..$x) {
	my $a = $_;
	for (1..$y) {
	    my $b = $_;
	    $map{get_coords($a,$b)} = "";
	}
    }
}

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

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

load_map(8,10);
my $size = 4;

map {
    my $hex = $_;
    say "-" x 60;
    say "Hex: $hex";

    my $f = vonJeffmann2013($size, $hex);

    my %tree;
    my %loop;
    my %tot;

    my $bigtree = -1;
    my $bigloop = -1;

    for (0..9999) {
	my $seed = $_;
	$seed = "0" x (4 - length($seed)) . $seed;
	my ($length, $loopstart, $treelength, $looplength) = analyze($seed, $f);

	$tree{$seed} = $treelength;
	$loop{$seed} = $looplength;
	$tot{$seed} = $length;

	$bigtree = $seed if $treelength > ($tree{$bigtree} || 0);
	$bigloop = $seed if $length > ($tot{$bigloop} || 0);
    }

    my $treestuff = "$tree{$bigtree} + $loop{$bigtree} = $tot{$bigtree}";
    my $loopstuff = "$tree{$bigloop} + $loop{$bigloop} = $tot{$bigloop}";
    my $treetext = "BiggestTree: $bigtree ---> $treestuff";
    my $looptext = "BiggestLoop: $bigloop ---> $loopstuff";
    say $treetext;
    say $looptext if $bigtree ne $bigloop;
} sort keys %map;

Exercises for the novice programmer:

1)  This week’s program basically finds the key features of a series of iterated functions. We were only looking for long chains of random-looking numbers when we did this one, but maybe there are other features of these things that we could leverage later on. Alter the program to also provide a list of numbers that return themselves (if any exist.)

2)  I only demonstrated that we had a way to consistently get a set of about 100 random-looking numbers for each hex of a map the size of a Traveller subsector map. If we were to use a much larger map– say, a thousand hexes in size– can you prove that the “shape” of all of those functions would be different enough that we could depend on them to not behave too similarly?

3)  A hundred numbers is probably enough for what I want to do, but that may not turn out to be the case. Can you alter the main function of the program so that we find seeds that produce longer sequences of random-looking numbers?

Advertisements

10 responses to “The Toy Universe: Exploring Iterative Functions

  1. Robert Eaglestone July 29, 2013 at 10:44 am

    Interesting. How do these random numbers “look”?

    • jeffro July 29, 2013 at 10:57 am

      For any given function, there is a collection of “squigglies” implied by what would happen if you iterate it. If each star system had a number of planets equal to the number of squigglies… and if each squiggly determined the nature of its world depending on its properties….

  2. Robert Eaglestone July 29, 2013 at 10:44 am

    Nice abuse of map!

  3. Robert Eaglestone July 29, 2013 at 10:46 am

    I think what you’re doing here is approximating a hash function…

    • jeffro July 29, 2013 at 10:52 am

      In the approach I take here, we need a function that returns a function for each hex number we can pass to it. Then we need to store the best seeds for those in a hash so that we don’t have to keep looking for them. With four-digit pseudo-random numbers… it doesn’t take terribly long to dig these up… and we tend to get a series of about 200 numbers for each hex.

      • Robert Eaglestone July 29, 2013 at 11:36 am

        Right, gotcha. You’re creating a space, then exploring it (how’s that for a meta situation! That’s what you want this for in the FIRST place!)

      • Robert Eaglestone July 29, 2013 at 11:37 am

        It’s a clever idea, selecting the best function of the group assigned to each hex.

  4. Robert Eaglestone July 29, 2013 at 11:34 am

    …except hash functions are very poor for hex coordinates…

  5. Pingback: The Toy Universe: Exploring Dot Maps | Jeffro's Space Gaming Blog

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: