Shuffle Bags: Making Random() Feel More Random

A pseudo random number generator (PRNG) like the Random Class in C# is not a true random number generator: its goal is to approximate randomness with speed. This means it will often return an uneven distribution of values, which may not be what you want. In this tutorial, I’ll show you how to solve this problem with a shuffle bag.

Note: Although this tutorial uses C#, you should be able to use the same techniques and concepts in almost any game development environment.

---

Introduction

When I first started creating games, I used the standard Random() methods to create variety in gameplay, creating large if/else conditions until I received my desired results. If the results weren’t balanced the way I wanted them, I would create additional conditions until I felt the gameplay was fun. It wasn’t until recently I realized there are better approaches in creating a truly entertaining game play experience.

There is nothing wrong with the use of the built-in Random class: the problem of not getting the desired results stems from the implementation of the methods. In this article we’ll use the “Shuffle Bag” method to make Random() feel more random (and more fun), using Boggle boards as a practical example.

---

The Problem

Have you ever noticed that an expression like:

  int value = Random.Next(lowerBounds, upperBounds);  

…gives you an uneven distribution of numbers?

A random number generator that picks values between 0 and 1 doesn’t care if it returns all 1s, so if you’ve created an if/else block using the above expression to pick a branch, you probably aren’t getting the results you expect.

  var rand = new Random();  for (int i = 0; i < 10; i++)      Console.WriteLine(rand.Next(0, 2));  

There’s nothing technically wrong with Random.Next(), but it doesn’t guarantee a nice even distribution of numbers. This means that in many gameplay situations, Random() isn’t fun.

---

What Is a Shuffle Bag?

A Shuffle Bag is a technique for controlling randomness to create the distribution we desire. The idea is:

• Pick a range of values with the desired distribution.
• Put all these values into a bag.
• Shuffle the bag’s contents.
• Pull the values out one by one until you reach the end.
• Once you reach the end, you start over, pulling the values out one by one again.

---

Implementing a Shuffle Bag

Implementing a Shuffle Bag in C# is simple, and the technique can easily be converted to any language.

As the purpose of this article is to focus on the implementation of Shuffle Bags and not language features, we will not look at the use of generics. However, I strongly recommend the use of generics because they allow us to make type safe data structures without committing to actual data types. Generics allow you to use the same code to create Shuffle Bags that hold many different types of data.

Here’s the basic code:

  public class ShuffleBag  {      private Random random = new Random();      private List<char> data;      private char currentItem;      private int currentPosition = -1;      private int Capacity { get { return data.Capacity; } }      public int Size { get { return data.Count; } }      public ShuffleBag(int initCapacity)      {          data = new List(initCapacity);      }  

The beginning of the class sets up the instance variables, and the constructor initializes the data instance variable to the programmer’s initial capacity (i.e. how big the bag is to begin with).

      public void Add(char item, int amount)      {          for (int i = 0; i < amount; i++)              data.Add(item);          currentPosition = Size - 1;      }  

The Add method simply adds the char to data as many times as the programmer specifies.

Note that the currentPosition is set to the end of the list, as we will traverse from the end later on. Why from the end of the list? You could make the Shuffle Bag traverse from the beginning, but starting at the end and working backwards makes for cleaner code.

      public char Next()      {          if (currentPosition < 1)          {              currentPosition = Size - 1;              currentItem = data[0];              return currentItem;          }          var pos = random.Next(currentPosition);          currentItem = data[pos];          data[pos] = data[currentPosition];          data[currentPosition] = currentItem;          currentPosition--;          return currentItem;      }  

The Next method is the meat of this technique.

If currentPosition is less than one, we reset it to point to the end of the list and return the first item from the bag. (This covers the situation where we’ve traversed through all the items and now wish to start again.)

Otherwise, we use random.Next() to pick a random item from the bag, from somewhere between the first item and the item at our current position. We swap this randomly selected item with the item at our current position, and then decrease currentPosition by 1.

Finally, we return the randomly selected item. The result is that we keep picking items we haven’t picked before, while shuffling the bag as we go. This means that its contents are in a different order when we want to traverse it again.

Now it’s time to try out our newly created class.

---

Using the Shuffle Bag Class

Several years ago I created a Boggle clone for the iPhone.

Image credit: Rich Brooks

One problem I faced was creating dense boards that only used 16 letters, but allowed the user to form hundreds of words with those 16 letters. I learned about letter frequencies, and how I could use it to create a positive user experience.

By using the frequency that letters appear in English text we can construct a weighted dictionary.

  private static Dictionary letterFrequencies<char, double> = new Dictionary  {      {'E', 12.702},      {'T', 9.056},      {'A', 8.167},      {'O', 7.507},      {'I', 6.966},      {'N', 6.769},      {'S', 6.327},      {'H', 6.094},      {'R', 5.987},      {'D', 4.253},      {'L', 4.025},      {'C', 2.782},      {'U', 2.758},      {'M', 2.406},      {'W', 2.306},      {'F', 2.228},      {'G', 2.015},      {'Y', 1.974},      {'P', 1.929},      {'B', 1.492},      {'V', 0.978},      {'K', 0.772},      {'J', 0.153},      {'X', 0.150},      {'Q', 0.095},      {'Z', 0.074}  };  //total: 99.965  

Note: Q is handled a bit differently than the other letters. It retains the value from the letter frequency table, but it appears as Qu in many word games.

Now we can create an instance of our Shuffle Bag class, fill our Shuffle Bag with data and create dense Boggle Boards.

          static void Main(string[] args)          {              var shuffleBag = new ShuffleBag(88000);              int amount = 0;              foreach (var letter in letterFrequencies)              {                  amount = (int)letter.Value * 1000;                  shuffleBag.Add(letter.Key, amount);              }              for (int i = 0; i < 16; i++)                  Console.Write(shuffleBag.Next());              Console.WriteLine();          }  

Note: The most important thing to take away from this piece of code is the amount. A multiplier of 1000 returns better results than a multiplier of 10.

Run the results through an online solver. How many words do you find?

---

Conclusion

In this article, we acknowledged the problem in using random values with if/else conditions, we introduced a solution using Shuffle Bags, and demonstrated a usage by creating dense Boggle Boards. With the use of Shuffle Bags we take control of Random() methods and create an even distribution of values that aid in a positive gaming experience.