COMMUNITY

Pseudo Random Number Generator I wanted to share

Pseudo RNG is favorable for games that want to use randomness but maintain a deterministic behavior. My approach to this is to create the table of numbers and treat them like a deck of cards, relying on it’s own values to mix them around in a “human like” imprecision. If there was no “imprecision” to the shuffling, mixing the numbers would have a dramatically far less amount of producible combinations, equal to the half the number of values in the table. IE a deck of 52 cards can be shuffled 26 times before you would have the exact same deck as you started with (assuming every card was shuffled perfectly, and cut perfectly every time). While the same thing will happen with my algorithm, the time it would take is very likely impractical to measure. Would like to test this some time.

class Random 
{
	public var values:Array<Int>;
	public var p_random:Int = 0;
	public var limit:Int;
	
	//specify the number of values your table will have
	public function new(_size:Int = 256) 
	{
		values = new Array();
		
		limit = _size - 1;
		
		for (v in 0..._size) {
			values.push(v);
		}
	}
	
	//shuffle this deck
	public function shuffle(?_shuffles:Int = 0) {
		values = riffleShuffle(values, _shuffles);
	}
	
	//Shuffle any table of numbers.
	public static function riffleShuffle(_deck:Array<Int>, _shuffles:Int = 1):Array<Int> 
	{
		var midpoint:Int = Std.int(_deck.length / 2);
		
		var new_deck:Array<Int> = new Array();
		var workdeck:Array<Int> = _deck;
		
		for (a in 0..._shuffles) {
			
			var card_count:Int = 0;
			
			var half_a:Array<Int>;
			var half_b:Array<Int>;
			
			//Cut the deck in half. Finds a mid point with a "human like" imprecision.
			var cut:Int = Std.int(_deck.length / 2) - Std.int((_deck.length / 8) * getRandomNormal() * (getRandom() % 2 == 0 ? 1 : -1));
			
			half_a = workdeck.slice(0, cut);
			half_b = workdeck.slice(cut, workdeck.length);
			
			//reassemble the deck
			workdeck = new Array();
			
			for (b in half_b) workdeck.push(b);
			for (b in half_a) workdeck.push(b);
			
			half_a = workdeck.slice(0, midpoint);
			half_b = workdeck.slice(midpoint, _deck.length);
			new_deck = new Array();
			
			//Perform a perfect riffle shuffle.
			while (true) {
				
				if (card_count % 2 == 0) {
					new_deck.push(half_b.shift());
				} else {
					new_deck.push(half_a.shift());
				}
				
				++card_count;
				
				if (new_deck.length == _deck.length) break;
			}
			
			workdeck = new_deck;
		}
		
		return workdeck;
	}
	
	/* To get a random value, we just access an index in the values array.
	 * This means that as long as your random values are always dependant on exactly the same
	 * table, you will always have exactly the same results every time your program runs.
	 * 
	 * Adding more random calls will, of course, change these results. But the point is they
	 * will stay the same every time until the developer changes it.
	 */
	public function getRandom():Int {
		p_random += 1;
		if (p_random == values.length) p_random = 0;
		trace(p_random, values[p_random], values[p_random] / limit);
		return values[p_random];
	}
	
	//For a traditional random value between 0.0 and 1.0
	public function getRandomNormal():Float {
		return getRandom() / limit;
	}
	
	/* For when you need a table of very specific values.
	 * A good example of this need is in Doom's source code: https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/m_random.c
	 * It's a table of 256 values, but it does not contain every value between 0 and 255.
	 */
	public static function fromPredeterminedIntArray(_array:Array<Int>):Random
	{
		var rng = new Random();
		rng.values = _array;
		var high:Int = 0;
		for (v in rng.values) {
			if (v >= high) high = v;
		}
		rng.limit = high;
		return rng;
	}
}
2 Likes