Fast & Lightweight Random “Shuffle” Functionality

shufflewhatif

NOTE: THIS ARTICLE ENDS IN FAILURE. IF YOU WANT TO SKIP AHEAD TO THE SUCCESSFUL METHOD CHECK OUT THIS POST: Fast & Lightweight Random “Shuffle” Functionality – FIXED

Sometimes in game development we have a list of things that we want to choose from randomly, but we want to make sure and only choose each thing one time.

For instance, let’s say you are making a game where the player gets quests randomly from an NPC, but when they finish the current group of quests, they can then move onto the next group of quests (because the next group is harder than the first group).

Here’s some obvious ways you might implement this:

  • Make a list of the items you want to choose randomly from. When you choose an item from the list, remove it from the list so that it won’t be chosen from next time. You have to allocate and maintain (and maybe serialize) a list which is a little bit of a bummer, but it gets the job done.
  • Add a flag or bool to each item to remember whether it’s been chosen from. When you randomly choose an item, if it has already been chosen, roll a random number again. If it hasn’t been chosen, mark it as having been chosen and use it. The bummer here is that it isn’t constant time. If you have a lot of items to choose from, when you get near the end and only have a few items left unused, you’ll have to roll a bunch of random numbers before you find a valid one to use.
  • Taking a cue from the last article Efficiently Generate Random Numbers Without Repeats, you could go with the 2nd option, but count how many unused items there are, roll a random number for the number of unused items, and then count through the list again to find which unused item you rolled. This is nicer, but it might be costly to have to traverse the list, especially if the list has a lot of items in it.

Computer Science Magic

Computer science has some neat things to it that could help you out here. Most notably, there are various algorithms for traversing numbers or multidimensional spaces in ways other than sequentially, for various reasons. Here are 2 such things for example (but there are many more out there waiting for you to find them!):

You could likely leverage something like these guys to traverse the items in a list in a way that looked random to a player, but would actually be well defined and have a pattern to them. The unfortunate thing about these is that they may be the same “random” every time though. With some creativity and programming alchemy you might be able to get around that problem though.

If something like this works well enough for you, it might be your solution!

XOR Magic

XOR is a magical thing. I started game development back in 16 bit CPU days before hardware accelerated graphics, and when GL (and later directX) first appeared, my first question was “this is all very neat, but how do i XOR pixels?” Sadly, the answer was that I couldn’t, and as far as I know, we still don’t have that ability with shaders and it makes me sad LOL.

Anyways, besides making really snazzy “programmer art” style graphics (and selection boxes), XOR is one of the corner stones of encryption and other cryptography. (Like Cryptography? I have a bunch of posts on it, go check em out! Cryptography 101)

For instance, the “one time pad” is the ONLY mathematically proven uncrackable encryption scheme, and it uses XOR. In fact, it ONLY uses XOR.

One property of XOR that makes it useful for cryptography also makes it useful to us here in our shuffle code. That property is this: If you have a random number, and a non random number, when you XOR them together, the result will be a random number too. (BTW the other property that makes it useful for cryptography is that it’s reversible, but we don’t care about that right now).

Think about that for a minute… that means that if you have a random number, and you count from 1 to 10, XORing each number by the same random number, the resulting numbers ought to be random too. What else is great is that thanks to the fact that Boolean math is deterministic (1 xor 0 is always 1, every time you do it), the numbers you get out will all be unique and not repeat. TA-DA! There are some problems left to solve, but we now have the basis for our shuffle algorithm!

Are you down with the SHUF?

Ok so the basic idea for shuffling is this: We are going to loop through the list normally, but we are going to xor each index against a pre-rolled random number so that it randomizes the index for us in a way that will have no repeats. Let’s pretend that we have 5 things to loop through and that our random number is 3. Let’s try it out:

index 0: 0 ^ 3 == 3
index 1: 1 ^ 3 == 2
index 2: 2 ^ 3 == 1
index 3: 3 ^ 3 == 0
index 4: 4 ^ 3 == 7

Our last number ended up being 7, what the heck happened? Well, the issue here is that it’s randomizing the bits in our indices, not really shuffling our 5 items. With 5 items to loop through, that means there are 3 bits that it is randomizing, which means that we might encounter any 3 bit value at any time (including 7, the highest one!), and that we would need to iterate through all 3 bit values to encounter all the indices that we are looking for (0 through 5). We’ll just have to loop through all 3 bit indices and ignore anything too large. Here’s all of the values:

index 0: 0 ^ 3 == 3
index 1: 1 ^ 3 == 2
index 2: 2 ^ 3 == 1
index 3: 3 ^ 3 == 0
index 4: 4 ^ 3 == 7 (ignore)
index 5: 5 ^ 3 == 6 (ignore)
index 6: 6 ^ 3 == 5 (ignore)
index 7: 7 ^ 3 == 4

Looks like we solved that issue.

The other issue that comes up is that the random number can be any number that can fit in an unsigned int. When we xor a huge number by our small indices, we’ll get giant numbers out as a result.

For instance if our random number was 15367, xoring that against index 3 would give us 15364.

To fix that, we can just use the lowest 3 bits of the random number (& against 7). That way, the random number can only have bits set in the lowest 3 bits, and our index already can only have bits set in the lowest 3 bits, so the end result can also only have bits set in the lowest 3 bits.

I think we are ready to write some code!

The Source Code

#include 
#include 
#include 

template 
struct SShuffler
{
public:
	SShuffler()
	{
		Start();
	}

	// start a new shuffle
	void Start()
	{
		m_index = (unsigned int)-1;
		m_randomNumber = ((unsigned int)rand()) & c_numItemsNextPow2Mask;
	}

	// whether or not the shuffle is finished
	bool IsDone()
	{
		return m_index == c_numItemsNextPow2;
	}

	// Get the next index in the shuffle
	bool Shuffle(unsigned int &shuffleIndex)
	{
		// increment our index until we reach our max index,
		// or we find a valid index
		do
		{
			m_index++;
			shuffleIndex = m_index ^ m_randomNumber;
		}
		while (m_index = c_numItems);

		// if we haven't reached the max index, our shuffle was successful
		return m_index > 1;
	static const unsigned int c_B = c_A | c_A >> 2;
	static const unsigned int c_C = c_B | c_B >> 4;
	static const unsigned int c_D = c_C | c_C >> 8;
	static const unsigned int c_numItemsNextPow2Mask = c_D | c_D >> 16;
	static const unsigned int c_numItemsNextPow2 = c_numItemsNextPow2Mask + 1;

	// member vars
	unsigned int m_index;
	unsigned int m_randomNumber;
};

// our songs that we are going to shuffle through
const unsigned int g_numSongs = 10;
const char *g_SongList[g_numSongs] =
{
	"1. Head Like a Hole",
	"2. Terrible Lie",
	"3. Down in It",
	"4. Sanctified",
	"5. Something I Can Never Have",
	"6. Kinda I Want to",
	"7. Sin",
	"8. That's What I Get",
	"9. The Only Time",
	"10. Ringfinger"
};

int main(void)
{
	// use the current time as a seed for our random number generator
	srand((unsigned)time(0));

	// declare a shuffler object
	SShuffler shuffler;

	// shuffle play once
	printf("I wanna listen to some NIN...(seed = %i)rnrn", shuffler.DebugGetSeed());
	unsigned int shuffleIndex = 0;
	while(!shuffler.IsDone())
	{
		if (shuffler.Shuffle(shuffleIndex))
			printf("%srn",g_SongList[shuffleIndex]);
	}

	// shuffle play again
	shuffler.Start();
	printf("rnThat was great, let's listen again! (seed = %i)rnrn", shuffler.DebugGetSeed());
	while(!shuffler.IsDone())
	{
		if (shuffler.Shuffle(shuffleIndex))
			printf("%srn",g_SongList[shuffleIndex]);
	}

	printf("rn");
	system("pause");
	return 0;
}

Example Run

Here’s the output of an example run of this program. Note that if ever you encounter seed 0, it will not shuffle at all. Also, if you encounter seed 15, it will play the list exactly backwards!

shuffle

Something Weird Going On

After playing with this stuff a bit, it looks like even though this technique works “ok”, that it actually doesn’t randomize the list as much as I thought it was. It looks like no matter what my seed is, adjacent numbers seem to “pair up”. Like 1 and 2 will always be next to each other but will change which comes first. Same with 3 and 4, 5 and 6, etc.

I think the problem is that if you have a set of numbers in order, that for each possible order those numbers can be in, there doesn’t exist a number you can XOR the set of numbers to get to be in that order. I think that even though a simple XOR can re-arrange the numbers, it can’t give you all possible combinations (which makes sense… 16 seeds is a lot less than 10 factorial, which is how many combinations there ought to be!)

I have to play around with it some more and think about it a little more though. There might be a way at least to make it better, maybe using some more bits from the random number to do more math operations on the index or something.


14 comments

  1. You’ll start noticing more patterns if you look at it as a binary tree or focus on the Gray Code. You pointed out that the groups (1) and (2) are adjacent. But also the sets of (1,2) and (3,4) are adjacent and carrying that out the sets of (1,2,3,4) and (5,6,7,8) will be adjacent, (1…N) and (N+1…2N) will always be adjacent. The reason devolves into binary math and how XOR and binary positional values can relate.

    There’s a great article by Blizzard from 8 or 10 years ago (that I’ve lost my bookmark to) that details how perceived randomness is more important than true randomness for human interactions. If I flip a coin 20 times and it comes up heads every time then people will believe that tails is more likely to come up on the next flip. If a game used true randomness then someone would be “lucky” enough to always roll bad (over 5 million players the chances of the extremely unlikely becomes likely).

    Like

      • Yeah i noticed that too (the thing about the adjacency).

        Cool thing about the blizz talk. Jason basically said the same thing on FB.

        I’m reading up on some more stuff and the rabbit hole is getting pretty deep. Apparently this thing I’m trying to do is called Quasi Random Numbers and low discrepancy sequences. It looks like they use these things a lot in the financial world to do monte carlo sampling of N dimensional spaces.

        Crazy stuff but interesting, I’m going to summarize what i’ve found out and take a stab at making the shuffler class be a bit better at shuffling hehe.

        Like

      • This is one of those things that requires pictures to fully explain, but here goes:
        If you think of the array of values to be shuffled as leaves of a binary tree. Then you swap the left/right values based upon the bit of the input (the least significant bit corresponds with the Nth level of the tree, the 2nd least significant bit is N-1th level of the tree).
        / row 3
        / / row 2
        / / / / row 1
        1 2 3 4 5 6 7 8

        So with the basic tree (that I’m sure will lose formatting). An input of 1 would swap the left/right values of the children of row 1. An input of 2 would swap the left/right children of row 2. An input of 3 would swap the left/right children of row 1 and row 2, etc.

        Like

      • ah gotcha. If i catch your meaning, it isn’t so much that the binary tree / swapping will help me solve this issue, but more that the binary tree shows why xor alone will always have the pairing problem when applied to sequential numbers?

        FWIW i tried adding the random seed to every other index to help thwart the pairing problem (ANDing against the bitmask to keep it in range) and then converting the indices to gray code, and then xoring the random number in. It’s actually looking quite a bit better. There’s still some seeds that spit out values that make you say “WTF” but its getting better.

        Like

      • oh and by “add the random seed to every other index”, i mean “add the random seed * 2 to every other index”. Since i’m only offsetting the even or odd numbers, and I still need every number to be represented exactly once in the output of this operation, i can’t change the evens to odds or vice versa.

        Like

      • It seems like you’re going out of your way to shuffle a list without allocating any memory. Wouldn’t it be easier to just generate a bunch of random numbers and then sort them? Or if allocations are bad and you can guarantee that half of the bits are going to waste for the values you’re trying to shuffle you could set the high bits randomly, sort the list, and then clear the high bits.

        Like

  2. Apparently we reached max comment reply depth so starting a new one 😛

    Yeah so this technique is good at shuffling a large amount of data, which doesn’t come up that often, making this less useful.

    There are a couple interesting properties to this guy besides just being good at shuffling though.

    #1 – it can easily go forwards or backwards. If you have a game that involves being able to rewind time, or being able to watch replays (resimulations) and scrub back and forward in the timeline, this could help make that easier for you by providing a random number generator that doesn’t care about the flow of time 😛

    #2 – If the number you tell it to shuffle is a power of 2 minus 1 (so that it doesn’t round up to the next power of 2), you ca set the “shuffle iterator” index to any value and get the number generated for that index. I could tell a shuffler to shuffle 100,000 items, set the index to 75,683 and get the value instantly without having to generate the 75,683 numbers that came before it first.

    I don’t think it’s every day useful, but I think this thing is going to be a decent tool for the old game programming toolbox that can be used from time to time (:

    Like

    • OK, a reversible or random order deterministic random number does sound pretty awesome. But I don’t think that xor will get you there. I think the problem is that you’re only adding one random element to known values and a known ordering and trying to get a different ordering. There is probably some odd public key or symmetrical key encryption out there that is poor encryption but would match your requirements.

      Like

      • Yeah you might be right about xor… i thought i had done better w/ adding or xoring even numbers against an even random number, gray code, and then xor but it falls apart for larger numbers. (like… @ 100,000 random max, i get numbers that shift between being in the 400s back up to 10,000… and several pages of that bad behavior.

        To take it to the extreme i was thinking about jamming in more random numbers, and trying multiple passes through this “jumbling process” just to see if it helps any.

        Encryption has been on my mind too but haven’t tried that yet, that’s a good idea. I know hashing is no good though because unlike “single byte at a time, stateless encryption”, it will happily take N things and generate less than N unique outputs.

        Like

  3. Pingback: The Incredible Time Traveling Random Number Generator | The blog at the bottom of the sea

  4. Pingback: Fast & Lightweight Random “Shuffle” Functionality – FIXED! | The blog at the bottom of the sea


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