Shuffle node in Godot that uses crypto.generate_random_bytes if I want to be pedantic that every possible shuffle is possible

shuffle_tester.gd

extends Node
class_name ShuffleTester

var deck:Array

@export var shuffler:Shuffler

@export var simple_shuffler:SimpleShuffler

@export var shuffler_mod:ShufflerMod

@export var simple_shuffler_throw:SimpleShufflerThrowaway


func _input(event):
	if event is InputEventKey:
		if event.pressed && event.keycode == KEY_S:
			test_shuffles()

func print_deck() -> void:
	print(", ".join(deck))

func test_shuffles() -> void:
	# generate large number of random numbers to prove it's not biased
	const NUMBER_BINS:int = 10
	const TEST_COUNTS:int = 1000
	var number_tester:Array[int] = []
	number_tester.resize(NUMBER_BINS)
	for i in range(1000):
		number_tester[shuffler_mod.get_random(NUMBER_BINS)] += 1
	print("NUMBER FREQUENCY")
	@warning_ignore("integer_division")
	print("These numbers should approximate %d"%[(TEST_COUNTS / NUMBER_BINS)])
	print(", ".join(number_tester))
	
	# generate shuffles of small 5-card deck to prove results are unbiased 
	var shuffle_counts:Array[int] = []
	const DECK_SIZE:int = 10
	const TEST_MULT:int = 100
	shuffle_counts.resize(DECK_SIZE * DECK_SIZE)
	for i in range(DECK_SIZE * DECK_SIZE * TEST_MULT):
		# generates default order sequence
		var small_deck:Array = range(DECK_SIZE)
		var shuffled_deck:Array = shuffler_mod.shuffle_array(small_deck)
		for index in shuffled_deck.size():
			shuffle_counts[shuffled_deck[index] * DECK_SIZE + index] += 1
	print("These numbers should approximate %d"%[(DECK_SIZE * TEST_MULT)])
	print(", ".join(shuffle_counts))

	# shuffle 
	deck = []
	for suit in ["♠","♥","♣","♦"]:
		for rank in ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"]:
			deck.append(rank + suit)
	print("INITIAL DECK")
	print_deck()
	
	var throw_count:int = 0
	var start_time:int = Time.get_ticks_msec()
	const num_shuff:int = 1000
	for i in range(num_shuff):
		deck = shuffler.shuffle_array(deck)
		throw_count += shuffler.throw_away_count
	var end_time:int = Time.get_ticks_msec()
	print("Milliseconds elapse for %d shuffles = %d, throw_count = %d"%[num_shuff, (end_time - start_time), throw_count])
	print("SHUFFLED DECK")
	print_deck()
	
	start_time = Time.get_ticks_msec()
	for i in range(num_shuff):
		deck = shuffler_mod.shuffle_array(deck)
	end_time = Time.get_ticks_msec()
	print("Milliseconds elapse for %d mod shuffles = %d"%[num_shuff, (end_time - start_time)])

	
	start_time = Time.get_ticks_msec()
	for i in range(num_shuff):
		deck = simple_shuffler.shuffle_array(deck)
	end_time = Time.get_ticks_msec()
	print("Milliseconds elapse for %d quick shuffles = %d"%[num_shuff, (end_time - start_time)])

	start_time = Time.get_ticks_msec()
	for i in range(num_shuff):
		deck = simple_shuffler_throw.shuffle_array(deck)
	end_time = Time.get_ticks_msec()
	print("Milliseconds elapse for %d throwaway shuffles = %d"%[num_shuff, (end_time - start_time)])

shuffler.gd

extends Node
class_name Shuffler
# Does shuffling through cryptography to ensure all possible shuffles
# The regular Array.shuffle() relies on random seed.
# So I worried it wouldn't generate 52! possible shuffles based on only 2^64 possible seeds.

# crypto class used to generate guaranteed random numbers
var crypto:Crypto

# bytes pulled from crypto
var shuffle_bytes:PackedByteArray

# index for the next unused bit in shuffle_bytes
var bit_index:int = 0

# default number of bytes we start with
var default_length:int = 8

var throw_away_count:int = 0

func _ready() -> void:
	print("name = ",name)
	crypto = Crypto.new()
	shuffle_bytes = crypto.generate_random_bytes(default_length)

# gets a random number in a specified range
func get_random(range:int) -> int:
	var result:int = range # initial value is too high so while will run once
	var bits_needed:int = ceil(log(range) / log(2.0))
	var bytes_needed:int = ceil((bit_index + bits_needed)/8)
	if bytes_needed > shuffle_bytes.size(): # append more bytes if we'll need them
		shuffle_bytes.append_array(crypto.generate_random_bytes(default_length)) 

	var counter:int =0
	#print ("bits_needed = %d, bytes_needed = %d, result = %d, range = %d"%[bits_needed, bytes_needed, result, range])
	while result >= range: # throws out results too high
		# if I'm worried about efficiency of throwing them out, look at this:
		# https://arxiv.org/pdf/1805.10941
		result = 0
		bits_needed = ceil(log(range) / log(2.0))
		var byte_offset:int = 0 # bits offset for bytes
		while (bits_needed > 0):
			# number of bits we're currently reading
			var bit_reading:int = min(8 - bit_index, bits_needed)
			bits_needed -= bit_reading
			# bit_mask should be binary 1s of length needed
			var bit_mask:int = pow(2, bit_reading) - 1
			#print(bit_reading, ", needed = ", bits_needed, " mask = ", String.num_int64(bit_mask, 2) )
			result |= ((shuffle_bytes[0] >> bit_index) & bit_mask) << byte_offset
			#print ("result = %d, shuffle_bytes = %s, bit_mask = %d"%[result, str(shuffle_bytes), bit_mask])
	
			bit_index += bit_reading
			if bit_index >= 8:
				bit_index -= 8
				shuffle_bytes.remove_at(0) # finished with this byte
				if shuffle_bytes.size() == 0:
					shuffle_bytes.append_array(crypto.generate_random_bytes(default_length)) 
			
			byte_offset += 8
		#print ("result %d = %d "%[counter, result])
		counter += 1
	
	# count how many results had to be thrown away
	throw_away_count += counter - 1
	
	return result

func shuffle_array(array:Array) -> Array:
	if array.size()<=1:
		return array # no point in shuffling such a short array
	throw_away_count = 0
	var new_array:Array = []
	while array.size() > 1:
		var random_index:int = get_random(array.size())
		var new_element = array[random_index]
		array.remove_at(random_index)
		new_array.append(new_element)
	
	# last element since size == 1
	new_array.append(array[0])
	
	return new_array

shuffler_mod.gd

extends Node
class_name ShufflerMod
# Does shuffling through cryptography to ensure all possible shuffles
# The regular Array.shuffle() relies on random seed.
# So I worried it wouldn't generate 52! possible shuffles based on only 2^64 possible seeds.

# crypto class used to generate guaranteed random numbers
var crypto:Crypto

func _ready() -> void:
	crypto = Crypto.new()

# gets a random number in a specified range
func get_random(range:int) -> int:
	const UINT32_MAX:int = 0xFFFFFFFF
	# throwing an error just in case but it should be rare
	if range >= UINT32_MAX:
		push_error("range too high for random shuffle: %d"%[range])
	var random_bytes:PackedByteArray  = crypto.generate_random_bytes(4)
	var random_int:int = random_bytes.decode_u32(0)
	
	# rare occurence but if range doesn't evenly divide it would bias results
	#  so we throw out anything in that truncated range and try again
	@warning_ignore("integer_division")
	while floor(random_int / range) * range >= UINT32_MAX - range:
		random_bytes  = crypto.generate_random_bytes(4)
		random_int = random_bytes.decode_u32(0)
	
	return random_int % range

func shuffle_array(array:Array) -> Array:
	if array.size()<=1:
		return array # no point in shuffling such a short array
	
	var new_array:Array = []
	while array.size() > 1:
		var random_index:int = get_random(array.size())
		var new_element = array[random_index]
		array.remove_at(random_index)
		new_array.append(new_element)
	
	# last element since size == 1
	new_array.append(array[0])
	
	return new_array

simple_shuffler.gd

extends Node
class_name SimpleShuffler

# shuffler that just uses randi to shuffle
# might be susceptible to limits of 64-bit random seed and thus not capable of 52! possible shuffles

func shuffle_array(array:Array) -> Array:
	if array.size()<=1:
		return array # no point in shuffling a single card
	
	var new_array:Array = []
	while array.size() > 1:
		var random_index:int = randi_range(0, array.size() - 1)
		var new_element = array[random_index]
		array.remove_at(random_index)
		new_array.append(new_element)
	
	# last element since size == 1
	new_array.append(array[0])
	
	return new_array

simple_shuffler_throwaway.gd

extends Node
class_name SimpleShufflerThrowaway

# shuffler that just uses randi to shuffle
# might be susceptible to limits of 64-bit random seed and thus not capable of 52! possible shuffles

func get_random(range:int) -> int:
	var bits_needed:int = ceil(log(range) / log(2.0))
	var result:int = randi_range(0, 2^bits_needed)
	while result >= range:
		result = randi_range(0, 2 ^ bits_needed)
	return result

func shuffle_array(array:Array) -> Array:
	if array.size()<=1:
		return array # no point in shuffling a single card
	
	var new_array:Array = []
	while array.size() > 1: # randi_range(0, array.size() - 1)
		var random_index:int = get_random(array.size())
		var new_element = array[random_index]
		array.remove_at(random_index)
		new_array.append(new_element)
	
	# last element since size == 1
	new_array.append(array[0])
	
	return new_array

Seed in Godot's RandomNumberGenerator is a 64 bit int
State can be stored in an int

Read here to confirm about Godot's RNG
https://docs.godotengine.org/en/stable/classes/class_randomnumbergenerator.html

Given an identical Seed and State, the RNG will output the same sequence of random numbers.
2^64 * 2^64 = 340282366920938463463374607431768211456 possible shuffles if we use Godot's RNG

Shuffling a deck of 52 cards has 52 factorial possible shuffles
52! = 80658175170943878571660636856403766975289505440883277824000000000000

340282366920938463463374607431768211456
80658175170943878571660636856403766975289505440883277824000000000000

Both very large numbers but if we're being pedantic, we'd only get a tiny fraction of possible shuffles.

From running the benchmarks in shuffle tester, the crypto shuffle takes about 10 times as long as RNG, but if we are talking something like a card game, we're running it once per match, not thousands of times in a row.

I had initially been operating under an assumption that generating new bytes was the most expensive, so I designed the shuffler to minimize that, but in practice it looks like I can shuffle faster with a simpler algorithm. using shuffler_mod instead of shuffler even though it's generating more unused bits.

A test comparing shuffler to shuffler_mod over 1000 shuffles:

Shuffler = 342 milliseconds, bytes generated = 71272
ShufflerMod = 155 milliseconds, bytes generated = 204000

So even though ShufflerMod has to generate more bytes, the results are faster.