Jeffro's Space Gaming Blog

Microgames, Monster Games, and Role Playing Games

The Toy Universe: Von Neumann’s Middle-Square Method

In our last installment, I threw together a quick program to let us navigate a hex map. I rigged up a system for using numbers to represent the cardinal directions… and though it didn’t do all that much, it nevertheless invoked a sense of Richard Garriot’s early Ultima games– or the old BBS game Trade Wars more likely. As soon I started messing around with changing the map size on the fly, it was hard not to imagine having one map at the stellar level and then spinning up a new map for each planetfall. With modern computing, this should be trivial, right? Well there’s just one problem. I don’t want to deal with setting up a big database and then figuring out how to load it up with beautiful data that is just perfect in every way. Not only am I not creative enough to craft the perfect universe, but really… if I’m going to code a database application to manage all of that I need to be getting paid by the hour.

Some of you probably know where I’m going with this… but the rest of you, hold tight for a second here. We’re going to briefly delve into some math stuff here. The idea is… since every hex has a pair of coordinates that can be expressed as a number… it’d be great if we could use that to generate a series of numbers that could be used to define what’s at that location. Now… it might seem easier to use some kind of random number generator to flesh out the universe– that worked for Traveller, after all– but if we do that, we’ll have to save the data somehow and I just don’t want to deal with that. What we need is a way to quickly get the same sequence of numbers every time we look back at that hex.

It turns out that it didn’t take long for someone to rig up a solution to this: Von Neumann figured out in the forties that using a middle-square method to generate random-looking numbers was more efficient than reading “real” random numbers off of punch cards. Basically, f you square numbers and then from off the digits on either end, you get something pretty close to random. Take the number you get and do it again, and it’s almost like rolling several percentile dice all over again– except, if you start with the same number, you always end up with the same sequence. Wrap all of this up into a quick command line app, and we have a tool for exploring these things.

[jeffro@foobar ToyUniverse]$ ./numbers.pl 0802 4
6432
3706
7344
9343
2916
5030
3009
0540
[jeffro@foobar ToyUniverse]$ ./numbers.pl 0540 4
2916
5030
3009
0540

The command line program takes two arguments… the first is the hex number you want to spin a list of numbers from. The second is to specify how many digits you want to get back with each number in the list. Notice there that for hex 0802, we got a list of eight numbers. That’s the first headache you come across when you try to wrangle these things– there’s no guarantee that your list will be particularly long. And mysteriously, while the number 0540 terminates the sequence in our first run, looking at it individually producses a sequence of four numbers.

If you look at what the numbers are doing, you’ll see that, if you start with 1000, say… that’ll square up to a number with scads of zeros on the inside… and you’ll get all zeroes back when you drop the numbers off each end. From there, the zeroes will just return more zeroes as you plug that result back in. If we were using these numbers to run a world generation sequence, we wouldn’t get anything back for hex 1000… which, maybe in that case it wouldn’t be so bad– we could just leave a hex empty if we don’t get enough numbers to do our thing. For instance, hex 0540 would only get four numbers back with these parameters. If that’s not good enough, we could just skip it and move on….

Nevertheless, that leads us to wonder just how these things behave…. Wouldn’t it be nice to know how these things work before we depend on them too much in our universe building scheme? A little bit of hacking, and we add in an “all” feature that breaks down every possible hex number and tells you how many numbers will be generated for each hex.

[jeffro@foobar ToyUniverse]$ ./numbers.pl all 4
6239,110
9251,109
3416,109
4655,109
5810,108
0167,108
3544,108
9511,108

<—- SNIP! —->

8000,0
4000,0
2000,0
0002,0
5000,0
6245,0
0009,0
3792,0
0007,0
[jeffro@foobar ToyUniverse]$

As you can see, some of these sequences can get pretty long. We can now use additional commands like the ones in our first example to examine some of the more interesting hexes to determine whether or not what we’re doing here can work for what we’re going to do. Do the numbers look random enough? Do they create any obvious-looking patterns? Should we take what we have and just try to make it work…? Or should we rework our methods so that we can get effectively infinite sequences…? Maybe we’ll answer that when we decide on our next move here….

The code:


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

# Patterns unfamiliar, patterns lead you through
# To patterns of discovery tracing out the clues
# Can you recognize the patterns that you find?
#                           -- Devo's "Patterns"

sub vonNeumann1949 {
    my ($size) = @_;
    return sub {
	my ($x) = @_;
	$x = $x**2;
	$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} || $seed =~ /^0+$/;
	$history{$seed}++;
	return $seed;
    }
}

my $x = shift(@ARGV);
my $size = shift(@ARGV) || 6;
my $plus = shift(@ARGV) || 0;
if ($x =~ /^\d+$/) {
    my $di = destructing_iterator($x + $plus, vonNeumann1949($size));
    while (defined($x)) {
	$x = $di->();
	say $x if $x;
    }
} else {
    my %tally;
    for (1..9999) {
	my $x = $_;
	$x = "0" x (4 - length($x)) . $x;
	my $original = $x;
	my $di = destructing_iterator($x + $plus, vonNeumann1949($size));
	my $count;
	while (defined($x)) {
	    $x = $di->();
	    $count++;
	}	
	$tally{$original} = $count - 1;
    }
    map {
	my $x = $_;
	say "$x,$tally{$x}";
    } sort {$tally{$b} <=> $tally{$a}} keys %tally;
}

Exercises for the novice programmer:

1) By making a command line program in this manner, we can use basic UNIX commands to provide additional utility without having to do a lot of hand coding. For instance, to write this post, I wanted a hex number from a Traveller subsector map that generated a short sequence– small enough that I could show it here in its entirety. By piping the output of the “all” command given in the second sample run above, I could quickly sift through this data without having to put it into a relational database. Devise a one-line bash command that can accomplish this.

2) Is there a way to alter this program and/or parameters  in such a way that every hex number returns a sequence of at least twenty random-looking numbers?

About these ads

4 responses to “The Toy Universe: Von Neumann’s Middle-Square Method

  1. Robert Eaglestone July 19, 2013 at 3:35 pm

    I’ve got a Perl package for you, a modification of ISAAC.

  2. Pingback: The Toy Universe: Exploring Iterative Functions | Jeffro's Space Gaming Blog

  3. 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

Follow

Get every new post delivered to your Inbox.

Join 121 other followers

%d bloggers like this: