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!):

• Morton Order
• Gray Code (thanks to Jason for telling me about this guy!)

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!

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.

Sometimes in game development, you want to get a random number, but you want it to be different than the last random number you got.

For instance, let’s say you were making a game where the player was an elemental golem and could change between ice, fire, electricity and earth randomly but it cost 50 mana to change to a new random element.

When the player presses the button to change forms, if your game rolled a random number to figure out the new element, sometimes it would choose the exact same element that the player already had, but the player would still get charged the 50 mana.

As a player, wouldn’t you feel kind of ripped off if that happened? Wouldn’t it be better if it just chose randomly from all elements except the current one?

I’m going to show you how so if you want to think about it a bit first and see if you can work out a solution, do so now! SPOILERS AHEAD!

Not so Great Implementations

To implement that, there are a couple of “not so great” ways to do it such as…

• Make a list of all elements except the current one, and randomly choose from that list. This isn’t so great because you would have to allocate space for a list, copy in the elements, and then do the random roll. Memory allocations and data copying isn’t cheap. Imagine if there were 100 or 1000 different things you were choosing between. Then imagine that this operation happened for enemies every few game loops and that there were 1000 enemies on the screen at a time. That would a be a LOT of overhead just to roll fresh random numbers!
• Roll a random number and if it’s the same as the current value, roll it again. Repeat until you get a new number. This isn’t so great because this code will randomly take longer than others. As an extreme case for instance, what if the random number generator chose the same number 100 times in a row? It would take 100 times longer to run the code in that case.
• Another option might be to roll a random number, and if it was the same number as before, just add one (and use modulus to make sure it’s within valid range). This isn’t so great because you are basically giving the next number higher than your current number twice as much chance of coming up versus any other number. The solution shouldn’t bias the random chance in any way.

Solution 1

I faced this problem a few days ago and below is how i solved it. Note that Dice() is zero based, so if you call Dice(6), you will get a random number between 0 and 5. Dice() might be implemented using rand(), or a fast pseudo random number generator like Mersenne Twister or whatever else you would like to use.

unsigned int DiceNoRepeat(unsigned int numSides, unsigned int currentValue)
{
  if (numSides = currentValue)
    newValue++;

  return newValue;
}

Why that works is that if you throw out the current value, there are only numSides – 1 numbers left to choose from, so you first roll a number for which remaining number is the new number.

The numbers you chose from didn’t include the current value, but the values you are working with DO include the current value, so if the value is >= the current value, add one.

This solution is nice because it works in constant time (it only calls Dice() once), and also, it doesn’t mess up the probabilities (the chance of getting each number is the same).

Solution 2

Jay, a friend of mine who I used to work with, came up with a different solution that I think is essentially the same in terms of performance, and also has the nice properties of working in constant time and it doesn’t mess up the probabilities.

unsigned int DiceNoRepeat(unsigned int numSides, unsigned int currentValue)
{
  if (numSides < 1)
    return 0;

  unsigned int offset = Dice(numSides - 1) + 1;

  return (currentValue + offset) % numSides;
}

The reason this works is that instead of picking a random number, you are picking a random offset to add to your current number (wrapping around with modulus). You know that you want to move at least one space, and at most, numSides – 1. Since Dice() is zero based, Dice(numSides – 1) + 1 will give you a random number between 1 and numSides – 1.

When you add the offset to the current value and wrap it around by using modulus against numSides, you get a different random number.

Have a Different Solution?

Have a different way to do this? Post a comment and share! (:

If you are a C++ programmer, I’ll bet at some point in time, maybe during a code review, someone told you “hey you should use a pre-increment there because post-increments are slower”.

I had heard this some years ago in the context of for loops with the caveat of “they might have fixed it by now [the compiler], but why take the chance”. Fair enough I thought, and I started using pre-increment in for loops, but kept using post increment in other places because i felt it felt more natural. Also i don’t write code that makes it actually matter. I try to be explicit instead of clever to prevent bugs and such. For instance, lots of C++ programmers with years of experience probably wouldn’t be 100% sure about what order things happen in for this small code sample: *++p = 3;

To be more explicit, you could increment p on one line and then set *p to 3 on the next. That’s easier to get your head around because it’s more explicit. The optimizer can handle the details of combining the code, and as we will see a little bit later, code generation without an optimizer seems to do just fine too!

Ayways, I heard this again today during a code review. Someone saw i had a piece of code where i was incrementing an unsigned int like this (not as part of a for loop, just inside of an if statement): numEnables++;

They said “you should change that to a pre-increment because it’s faster”. Well, I decided I should have a look and see if that was true and that’s where today’s journey begins (:

Disclaimer: All my findings are based on what I’ve seen in MSVC 2010 and 2012 using default settings for debug and release building a win32 console application. When in doubt, check your own disassembly and make sure your code is doing what you think it is. I wish I had years ago so I would have known the truth back then.

Will It Blend?

Lets check out the assembly generated in release of a simple program to see what assembly it makes

int main(void)
{
int someNumber = 3;
someNumber++;
return 0;
}

Here is the resulting code from the disassembly window. The assembly code of our program is in the blue box:

PS you can find the diasassembly window by setting a breakpoint on someNumber++, running the program and when it hits the breapoint, going under the “Debug” menu, selecting “Windows” and then selecting “Disassembly”.

Ok so what the heck happened to our program? All it’s doing is xoring the eax register against itself (to set it to zero) and then it’s calling “ret”. That is our “return 0” statement. Everything else got optimized away! The optimizer realized that nothing meaningful changes if it doesn’t calculate someNumber, so it decides not to.

Let’s try a printf to print out our number. That way the optimizer CAN’T optimize our code away.

#include
#include

int main(void)
{
int someNumber = 3;
someNumber++;
printf("someNumber = %irn", someNumber);
return 0;
}

Now here’s the disassembly:

Ok we are doing better i guess. we see a push, a call, an add and then our return 0 code (xor eax, eax and ret).

I included the watch window so that you could see the values that the code is working with. The push pushes our printf format string onto the stack, and then it calls printf. Then it has the line “add sp, 8”. What that does is move the stack pointer up 8 bytes. Parameters are passed on the stack, so that line is there to undo the 4 byte push of the printf format string, and also the 4 byte push of someNumber. It’s just cleaning up the stack.

But where the heck was someNumber pushed onto the stack? I actually have no idea… do you know? If you know, please post a comment, I’m really curious how that works LOL.

EDIT: Thanks to Christophe for unraveling this, he points out that the assembly window was just not showing all the instructions:

For some reason, your MSVC debug window screencap shows the actual main() asm debug starting at 0x10b1002, not 0x10b1000. If you look at the line above at 0x10b0fff, it shows some “add byte ptr [edx+4], ch”. Which is because MSVC incorrectly deduced that there were some code starting at 0x10b0fff and so it messes up the debug print out of the actual code at 0x10b1000 (which would be some “push 4” on the stack, which is the incremented “someNumber” var).

We are not quite there. The optimizer is doing some funky stuff, and I think it’s because the optimizer knows that someNumber is the number “4”. It doesnt have to do any run time calculations so it isn’t

To make it so the optimizer can’t optimizer our number away like that, lets have the user input someNumber so the compiler has no idea what the right value is until run time.

#include
#include

int main(void)
{
int someNumber = 0;
printf("Please enter a number.rn");
scanf("%i",&someNumber);
someNumber++;
printf("someNumber = %irn", someNumber);
return 0;
}

And here’s the code generated. The important part (our increment) is in the blue box:

Ok there’s our post increment code. Let’s change the post increment to a preincrement:

#include
#include

int main(void)
{
int someNumber = 0;
printf("Please enter a number.rn");
scanf("%i",&someNumber);
++someNumber;
printf("someNumber = %irn", someNumber);
return 0;
}

And here’s the code it generates:

If you compare this generated code to the previously generated code, you’ll see it’s the exact same (some memory addresses have changed, but the instructions are the same). This is pretty good evidence that for this type of usage case, it doesn’t matter if you use post or pre increment – in RELEASE anyways.

Well, you might think to yourself “the optimizer does a good job, but if using a pre-increment, maybe you can make your DEBUG code faster so it isn’t so painful to debug the program”. Good point! It turns out that in debug though, preincrement and post increment give the same generated code. Here it is:

So, it looks like in this usage case that the compiler does not care whether you use preincrement or post increment.

Let’s check out for loops real quick before calling it a day.

For Loops

Here’s our post increment for loop testing code. Note we are doing the same tricks as before to prevent the key parts from getting optimized away.

#include
#include

int main(void)
{
int someNumber = 0;
printf("Please enter a number.rn");
scanf("%i",&someNumber);
for(int index = 0; index < someNumber; index++)
printf("index = %irn", index);
return 0;
}

Post and pre-increment generate the same code in release! Here it is:

It turns out they generate the same code in debug as well:

Summary

Well, it looks like for these usage cases (admittedly, they are not very complex code), it really just does not matter. You still ought to check your own usage cases just to make sure you see the results I’m seeing. See something different? Post a comment!

In part 2 I’ll show you a case where using pre or post increment does matter. Here it is!

Is pre-increment really faster than post increment? Part 2