Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm making a game which presents a number of different kinds of puzzles in sequence. I choose each puzzle with a pseudorandom number. For each puzzle, there are a number of variations. I choose the variation with another pseudorandom number. And so on.

The thing is, while this produces near-true randomness, this isn't what the player really wants. The player typically wants what they perceive to be and identify as random, but only if it doesn't tend to repeat puzzles. So, not really random. Just unpredictable.

Giving it some thought, I can imagine hacky ways of doing it. For example, temporarily eliminating the most recent N choices from the set of possibilities when selecting a new choice. Or assigning every choice an equal probability, reducing a choice's probability to zero on selection, and then increasing all probabilities slowly with each selection.

I assume there's an established way of doing this, but I just don't know the terminology so I can't find it. Anyone know? Or has anyone solved this in a pleasing way?

share|improve this question
4  
The book "AI Game Programming Wisdom 2" has a chapter on filtered randomness which, from what I recall, is pretty much exactly what you're looking for. I don't have it at the moment though so I can't really give you a full answer. –  Anton May 28 '12 at 13:55
    
To try and clarify: when you say 'not repeat puzzles' do you mean you just don't want two puzzles of the same type next to each other? So in other words, if you just picked a sudoku, don't offer another sudoku puzzle, but if it was Sudoku #19, then it's okay to offer Picross #19 next (in other words, the variation number doesn't matter)? –  Steven Stadnicki May 28 '12 at 15:35
2  
Very related question: stackoverflow.com/questions/910215/… –  Chris Burt-Brown May 28 '12 at 16:22
    
@Steven yes, not two of the same type next to each other as you describe. –  Hilton Campbell May 29 '12 at 14:28
1  
OK, my copy of AI Game Programming Wisdom 2 just arrived. I read the chapter on filtered randomness and checked out the source code. This is probably the best approach. It allows me to just use random numbers, but then filter the numbers so that unexpected patterns don't occur. It seems more bullet proof than the shuffle bag. –  Hilton Campbell Jun 2 '12 at 3:27
show 2 more comments

2 Answers

up vote 22 down vote accepted

If you have a finite number of puzzles, you can:

  • Build a list of puzzles, either all of them or some randomly picked;
  • Shuffle this list (see the Knuth Shuffle for instance);
  • Let your player play through this list;
  • When the list is empty, start with a new one.

EDIT

I didn't know this, but browsing SE made me realize that this is actually known as a "shuffle bag". Some more infos here, here or there.

EDIT 2

The classic Knuth Shuffle goes this way:

To shuffle an array a of n elements (indices 0..n-1):
    for i from n − 1 down to 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]

Steven Stadnicki rightfully pointed out in his comment that this kind of thing doesn't prevent repetition on a reshuffle. A way to take this into account is to add a special case for the last item:

To reshuffle an array a of n elements and prevent repetitions (indices 0..n-1):
    return if n <= 2

    // Classic Knuth Shuffle for all items *except* the last one
    for i from n − 2 down to 1 do
        j ← random integer with 0 ≤ j ≤ i
        exchange a[j] and a[i]

    // Special case for the last item
    // Exchange it with an item which is *not* the first one
    r ← random integer with 1 ≤ r ≤ n - 1
    exchange a[r] and a[n - 1]
share|improve this answer
1  
This can work but you have to be a little careful if you reshuffle after every playthrough not to start with the same item you ended on. –  Steven Stadnicki May 28 '12 at 15:38
    
@Steven Indeed. This item could be excluded from the new list. Actually, it could be an idea to build a list of a few random items only, and build the next list with only the remaining items. So if you have 100 items, build e.g. a shuffled list of 10. When done with this list, build the next one with 10 items in the 90 that weren't picked previously. –  Laurent Couvidou May 28 '12 at 15:45
    
+1. Added support for this technique being "more fun": this is how Tetris, for example, produces "random" pieces. A set of one of each piece is shuffled and iterated through, which avoids the long sequences of duplicates that true randomness would inevitably produce. –  Michael Edenfield May 28 '12 at 16:22
1  
@Hilton I tend to dislike this kind of "while loop until random gives me what I want" approach... Not very likely that this will cause any trouble. But still, I always feel like this is a call for random infinite loops or performance drops - which are awful to debug. Excluding the last item of the previous list from the new one lets you shuffle only once, for the same result. –  Laurent Couvidou Jun 18 '12 at 23:42
1  
You're right, and I had the same reservations. Rather than exclude the previous last item, I now have it just shuffle once, and then if the previous last item is now first, I swap it with some other item randomly. –  Hilton Campbell Jun 23 '12 at 17:24
show 6 more comments

A variant on lorancou's approach: for each puzzle type, keep an array of (shuffled) puzzle numbers; then every time you hit a puzzle of that type, get the next number off the list. for instance, let's say you have Sudoku, Picross and Kenken puzzles, each with puzzles #1..6. You'd create three shuffled arrays of the numbers 1..6, one for each puzzle type:

  • Sudoku: [5, 6, 1, 3, 4, 2]
  • Picross: [6, 2, 4, 1, 3, 5]
  • KenKen: [3, 2, 5, 6, 4, 1]

Now, you'd shuffle the puzzle types just like lorancu suggests; let's say it comes up [Picross, Sudoku, Kenken]. Then every time you hit a puzzle of a given type, use the next number in its 'shuffle list'; overall your puzzle presentation would be [Sudoku #5, Picross #6, Kenken #3, Sudoku #6, Picross #2, Kenken #2, ...]

If you don't want to keep the puzzles in the same overall order each time through the loop, then I think your 'choose randomly, ignoring the last few picks' option is the best. There are ways you can make this a little bit more efficient, too; for instance, let's say that you have 20 things and you want to ignore the last 5 picked. Then instead of randomly choosing a number 1..20 and 'rerolling' until you get one outside the last 5, instead just choose a number 1..15 and walk through your puzzle types that many steps, just skipping over any puzzle type that's been picked (you can do this easily by keeping a bit array that holds the last 5 picked puzzles).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.