Most of my games and prototypes lately are very board gamey and almost always involve dealing random “cards” to create a hand of cards. For example, in Subterfuge players have the choice of one of three specialists every few hours, which is similar to dealing 3 random cards and having the player pick one.
You would think that dealing cards at random would be trivially easy to implement. You would also be wrong.
Truly Random
Always the eternal optimist (and devout follower of the YAGNI principle), I start by implementing dealing cards by simply picking randomly among the types of cards available. Something along these lines:
for (int i=0; i<HandSize; ++i) hand[i] = Random_GetInt(0, CardType::COUNT-1);
The best part of this approach is that it’s simple. The bad part is… everything else.
Maybe that works for your game, and if so, congratulations, you can stop now and move on with the rest of the game. Unfortunately, this doesn’t cut it for most card games. The player might get a hand all of the same card. Or maybe never get a card type that she really needs. Most of the time, an algorithm like this will frustrate players quite a bit and get in the way of the enjoyment of the game.
Deck of Cards
The next approach I usually try is to simply copy physical games and build an actual deck. Remember that we’re talking about internal structures, so this doesn’t mean that the concept of a deck is exposed to the player at all. As far as they know, they’re just getting cards at “random”.
In this case, you create an array of card types, shuffle it, and give cards from the top to the player.
const int cardsPerType = 3; for (int i=0; i<CardType::COUNT; ++i) for (int j=0; j<cardsPerType; ++j) Deck_Add(deck, i); Deck_Shuffle(deck); for (int i=0; i<HandSize; ++i) hand[i] = deck[i];
This is quite an improvement over our first approach. To start with, we’re guaranteed never to get more than a certain amount of cards of each type in the deck. That will prevent ridiculous hands of all cards of the same type that make the game unplayable.
It also allows us to vary the amount of cards of each type in the deck. That way we can make some cards more rare than others, or even enforce unique cards by only adding one of each of those types.
You may argue that this approach is perfect since this is how “true” (meaning “physical) card games are designed most of the time. While that is true, physical card games often involve just randomly shuffling a deck because the alternative would be very time consuming (or might need a third-party who isn’t playing to set up the deck). Because of that, most games need to be able to deal with very uneven distribution of cards, which might be too limiting for your designs.
A lot of games games will benefit of having a more controlled deck, and since we’re running on a computer, we can afford to do a lot more than just shuffle cards together. We can take advantage of the digital medium and do things we couldn’t easily do with physical cards.
Aside: Shuffling a Deck
Shuffling a deck might seem like a trivial algorithm, but as usual the details can get a bit tricky.
If you wanted to get very physical, you could try to simulate real riffle shuffling of a deck: randomly split the deck into more-or-less equal parts, and interleave them with each other with some randomness. Then you’d have to run it several times and even so I think you’d get very suspect results.
A simplified algorithm is to randomly grab two cards in the deck and swap their positions. Is that good enough? How many times do you need to run that loop in order to get a proper (i.e. fully randomized) shuffle? I haven’t analyzed that algorithm, but I get the feeling it would have to be done many times in order to get something acceptable (especially considering the not-very-random nature of computer “random” number generators).
The best and simplest approach I have found to shuffle a deck is the following: assign a random number to each card in the deck, then sort the cards based on that random number. It’s easy to understand how a single sort will shuffle the deck properly and works the same for any number of cards (and runs in O(n log n) if we want to get pedantic about it).
Multiple Decks
One way to have more control over the deck composition is to have multiple decks. We don’t need to communicate to the player that there are in fact multiple decks, this is something that happens under the hood.
This is the approach we took in Subterfuge. Players are presented with a choice of 3 specialists every X hours. Initially those specialists were completely random, but the results were very underwhelming. The approach we ended up settling on involved classifying each specialist as being in the categories of attack, defense, or other. The game prepares 3 decks, one of each category with 3 of each of the specialists in each category. Additionally, we make sure that we never have 2 of the same specialist in a row.
When it comes time to generate 3 “random” specialists for the players to choose from, we pick the top one from each of the decks.
Blocks
In my current prototype, the player has a hand of 4-5 “cards”, and as soon as they use one, a new one is drawn and their hand refilled. Cards can be roughly classified in 6 different categories, and it’s important that the player gets access to one of those categories within a few turns.
I wanted to come up with an approach that guaranteed access to tiles of all categories, but without making the pattern too obvious. For example, I didn’t want to have the deck be one card of each category.
The solution I can up with was to break up the deck in blocks of 10 cards. Within each of those blocks, I can make some guarantees about its composition. This approach was inspired by the composition of boosters in collectable card games like Magic: The Gathering, or even in the way the deck is prepared in Pandemic.
The way I implemented it, each block of 10 cards will contain one card of each category, plus 4 other random cards (as long as they are not already in the block). Then all the cards in the block are shuffled and added to the deck. This results in apparently “random” draws without feeling predictable, and yet players are never left without a key resource they may need.
This kind of enforced structure can also add some depth to the game. Expert players might notice this pattern (or read this, which is a lot easier) and use it to their advantage when they’re trying to make decisions based on what cards might appear in future terms.
Any of you out there use a different method for creating random-but-not-quite-random draws in your games?