Advertisement
Implementation

Shuffle Bags: Making Random() Feel More Random

by

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.

Boggle, by therichbrooks on Flickr

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.

Related Posts
  • Code
    Android SDK
    Create a Music Player on Android: User Controls0d63m preview image@2x
    We are building a simple music player app for Android in this series. So far, we have presented a list of the songs on the device and allowed the user to make selections from it, starting playback using the MediaPlayer class in a Service class. In this final part of the series, we will let the user control playback, including skipping to the next and previous tracks, fast-forwarding, rewinding, playing, pausing, and seeking to particular points in the track. We will also display a notification during playback so that the user can jump back to the music player after using other apps.Read More…
  • Code
    Android SDK
    Create a Music Player on Android: Project Setup0d63m preview image@2x
    The Android platform provides resources for handling media playback, which your apps can use to create an interface between the user and their music files. In this tutorial series, we will create a basic music player application for Android. The app will present a list of songs on the user device, so that the user can select songs to play. The app will also present controls for interacting with playback and will continue playing when the user moves away from the app, with a notification displayed while playback elapses.Read More…
  • Game Development
    Implementation
    Make a Neon Vector Shooter for iOS: Particle EffectsGeometry wars ios particle effects
    In this series of tutorials, I'll show you how to make a Geometry Wars-inspired twin-stick shooter, with neon graphics, crazy particle effects, and awesome music, for iOS using C++ and OpenGL ES 2.0. In this part, we'll add explosions and visual flair.Read More…
  • Game Development
    Implementation
    Make a Neon Vector Shooter for iOS: More GameplayGeometry wars ios enemies
    In this series of tutorials, I'll show you how to make a Geometry Wars-inspired twin-stick shooter, with neon graphics, crazy particle effects, and awesome music, for iOS using C++ and OpenGL ES 2.0. So far, we've set up the basic gameplay; now, we'll add enemies and a scoring system.Read More…
  • Code
    Mobile Development
    C++ Succinctly: TypesPreview image@2x
    C++ contains the same familiar keywords that you recognize from C#. This is unsurprising given that both are C-like languages. In this article, we'll take a look at the types available in C++.Read More…
  • Code
    iOS SDK
    Objective-C Succinctly: Data Types0e5ds8 preview image@2x
    Objective-C has two categories of data types. First, remember that Objective-C is a superset of C, so you have access to all of the native C data types like char, int, float, etc. Objective-C also defines a few of its own low-level types, including a Boolean type. Let's call all of these "primitive data types."Read More…