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