Emanuele Feronato

Talking about Actionscript 3 and Flash.

With this post we’ll start talking about procedural generation.

Procedural generation is a widely used term in the production of media; it refers to content generated algorithmically rather than manually. Often times, this means creating content on the fly rather than prior to distribution. This is often related to computer graphics applications and video game level design (source).

This means we can generate random levels for some kind of games such as roguelike games, making people play randomly generated levels, making a game almost endless. Blizzard’s Diablo series is probably the most famous example of this technique.

But more interesting than the “simple” generation of random levels would be the capability of making a game with, let’s say, 10,000 levels procedurally generated starting from pseudorandom numbers, so that people will play a big set of different levels, but, as example, level 37 is the same on every game instance.

This is the case of The Sentinel, a game made in 1986 with 10,000 levels but no hardware to store them individually. They were all created by procedural generation. I loved this game (it’s one of the 5 Commodore 64 games I would like to see ported in Flash) so it’s obvious I am trying to play with procedural generation.

But before talking about it, let’s introduce pseudorandom numbers.

A pseudorandom number generator is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG’s state (source).

In everyday’s words, it’s a sequence of numbers that people will believe to be random, but it’s not. Just what we are looking for to start creating our “random” levels.

One of the simplest pseudorandom number generator is the Blum Blum Shub, called this way after the surnames of its creators: Lenore Blum, Manuel Blum and Michael Shub.

Although it’s not recognized as the quickest way to generate pseudorandom numbers, it’s very simple to code, and that’s what we are looking for.

Let’s look at this code:

package {
	import flash.display.Sprite;
	public class pseudorand extends Sprite {
		public function pseudorand() {
			var sequence:Array=new Array();
			var prime1:int=47;
			var prime2:int=67;
			var M:Number=prime1*prime2;
			var xi:int=6;
			do {
				xi=(xi*xi)%M;
				sequence.push(xi);
			} while (sequence.indexOf((xi*xi)%M)==-1);
			trace(sequence);
		}
	}
}

sequence is the array which will contain the pseudorandom sequence.

prime1 and prime2 are two prime numbers which should be both congruent to 3 modulo 4.

Two numbers are said to be congruent modulo m when their difference is divisible by m.

In our case this means that prime1-3 sould be divisible by 4, and (47-3)/4 = 11 so it’s divisible, and prime2-3 should be divisible by 4, and (67-3)/4 = 16 so it’s divisible.

This means The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue) and gcd(?(p-1), ?(q-1)) should be small (this makes the cycle length large).

Also, the greatest common divisor of prime1-1 and prime2-1 should be a small number, and that is since the greatest common divisor of 46 and 66 is 2.

M is the product of such prime numbers.

xi, also called “seed”, should be an integer different than 1.

Now, at every iteration, xi takes the value of (xi*xi)%M and we store all results in the array until we find a number we already have.

The results is this pseudorandom sequence:

36,1296,1199,1657,2870,2265,504,2096,361,1212,1510,224,2941,2327,1798,1930,2782,2431,2237,408,2716,1698,1869,920,2468,858,2447,1560,2572,2284,1912,2904,194,2997,1061,1528,1375,1225,1701,2619,639,2100,1400,1322,3138,121,2045,153,1366,1748,974,827,596,2528,1463,2198,638,823,294,1413,103,1162,2472,1724,2669,523,2715,2565,964,341,2917,291,2807,451,1865,1729,1040,1493,2706,1011,1845,3105,1936,786,592,925,2246,2967,1634,2753,2515,2033,1601,3064,927,2801,1442,1024,3108,1681,1108,2703,529,2729,56,3136,169,220,1165,6

which is a collection of “random” numbers everybody can get starting from the same values.

Next time, we’ll see how to turn these numbers into levels using procedural generation.