Generation of pseudorandom numbers with Blum Blum Shub method

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.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers