Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From \$16.50/m

# Shuffle Bags: Making Random() Feel More Random

Difficulty:IntermediateLength:ShortLanguages:

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:

...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.

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:

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).

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.

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.

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.

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.