Randomizing block permutations for a color matching game.
Moderator: Moderators
Randomizing block permutations for a color matching game.
So for some reference, I'm working on a falling block, color matching game. There are 4 colors of chests, and keys that unlock them.
What I want to do is make it so that every N drops there will be an exact count of each color of chests and keys. That way you never get too many keys all at once, or a long run where you don't get a color of key that you really need. To get the pacing of the game right based on the key/chest ratio, N ended up being 24 (not a convenient power of two). The column the blocks fall from is also stored in a separate permutation table where "N" is 6. Between the two, it's ~400 bytes of tables.
The quick and dirty method I've used so far was to concatenate a few permutation tables together into the ROM. Are there any good dirt simple algorithms for generating permutation tables on the fly that fit the NES well? Should I just consider the permutation tables good enough and small enough as is?
What I want to do is make it so that every N drops there will be an exact count of each color of chests and keys. That way you never get too many keys all at once, or a long run where you don't get a color of key that you really need. To get the pacing of the game right based on the key/chest ratio, N ended up being 24 (not a convenient power of two). The column the blocks fall from is also stored in a separate permutation table where "N" is 6. Between the two, it's ~400 bytes of tables.
The quick and dirty method I've used so far was to concatenate a few permutation tables together into the ROM. Are there any good dirt simple algorithms for generating permutation tables on the fly that fit the NES well? Should I just consider the permutation tables good enough and small enough as is?
Re: Randomizing block permutations for a color matching game
Can you store the table in RAM and randomly shuffle it at runtime?
BTW I wouldn't fret about table size in a puzzle game!
BTW I wouldn't fret about table size in a puzzle game!
Re: Randomizing block permutations for a color matching game
The Bag algorithm used in most Tetris products since 2001 generates all possible outcomes into an array in RAM and then deals the whole set before reshuffling. This can be done with a FisherYates shuffle at the cost of one RNG call and one multiply (to rescale the RNG's output to the number of items remaining to be shuffled) per piece dealt. Modern Tetris games usually use an array of length 7, one for each Tetrimino, but The New Tetris for N64 may have used an array of length 63, with 9 copies of each Tetrimino to serve it's added play mechanic of making gold "monosquares" for bonus points.
The least recently used (LRU) algorithm, a variant of which is used in Tetris the Grand Master, loads all outcomes into a circular array in RAM. On each turn, it runs the RNG once, truncates the result to a range of about half of the array size, swaps the current outcome with the outcome r positions later (with wraparound), deals that, and moves to the next position in the array. It somewhat resembles a neutered RC4 algorithm, and the subjective output isn't quite as sensitive to whether the RNG's range is or isn't a power of 2. I've used it for target selection in Thwaite, piece selection in RHDE, and NKI selection in my port of robotfindskitten.
Both have the useful property of making an outcome not repeat immediately, instead making it more likely after other outcomes have been dealt.
The least recently used (LRU) algorithm, a variant of which is used in Tetris the Grand Master, loads all outcomes into a circular array in RAM. On each turn, it runs the RNG once, truncates the result to a range of about half of the array size, swaps the current outcome with the outcome r positions later (with wraparound), deals that, and moves to the next position in the array. It somewhat resembles a neutered RC4 algorithm, and the subjective output isn't quite as sensitive to whether the RNG's range is or isn't a power of 2. I've used it for target selection in Thwaite, piece selection in RHDE, and NKI selection in my port of robotfindskitten.
Both have the useful property of making an outcome not repeat immediately, instead making it more likely after other outcomes have been dealt.
Re: Randomizing block permutations for a color matching game
Oh! I really like that LRU + ring buffer idea, it nicely solves the issue of the selection array not being a power of two. I think that might be exactly what I was looking for, and even solves a couple of the issues with just concatenating a bunch of permutations together.
Re: Randomizing block permutations for a color matching game
The name "LRU" comes from a cache replacement policy, and "bag" comes from "Random Tetrimino Bag" in EA's description of a mobile Tetris game, as discussed on tetrisconcept.net.
If anyone cares, I've made a reference implementation of the Bag and LRU algorithms in Python. Here's what it prints:
Notice that in "Bag test", each outcome appears once in each line of 24.
Random Tetrimino Bag: This feature eliminates long runs of bad luck by shuffling the seven Tetriminos.See also "Random Generator" and "TGM randomizer" on Hard Drop Wiki.
If anyone cares, I've made a reference implementation of the Bag and LRU algorithms in Python. Here's what it prints:
Code: Select all
Memoryless test:
4 3 12 3 22 1 17 9 15 3 19 16 21 19 22 21 10 12 6 22 21 15 0 17
21 15 6 5 4 20 5 7 8 18 0 20 2 17 21 20 2 4 22 3 23 13 7 16
9 6 5 9 1 16 19 3 15 6 5 21 17 9 16 12 0 11 6 22 5 23 4 2
22 6 15 20 21 18 17 4 16 20 15 22 23 0 12 2 11 15 13 12 20 2 22 3
17 20 17 20 19 6 4 14 16 19 11 7 2 20 16 19 16 20 0 2 2 4 16 1
0 6 18 14 1 12 11 16 22 7 22 3 7 3 9 22 20 9 21 22 4 10 16 2
23 17 22 8 22 15 18 13 15 15 7 16 20 2 19 14 4 10 9 5 7 2 5 12
21 10 11 7 13 22 6 13 0 22 19 5 22 22 5 3 22 6 17 5 17 9 11 11
22 16 13 16 6 14 5 21 7 12 15 21 19 21 21 16 8 1 4 3 16 12 16 4
9 15 12 18 4 20 22 17 17 13 0 0 15 3 22 12 15 2 21 5 8 18 0 23
LRU test:
4 2 8 5 7 3 9 0 10 6 14 16 13 17 12 1 18 21 19 11 5 4 22 2
8 20 7 15 6 10 9 17 3 23 12 18 11 1 14 5 13 4 8 21 7 15 10 6
19 2 3 12 23 16 20 22 14 0 11 1 13 8 17 15 18 19 2 21 7 3 4 5
9 14 20 12 1 6 16 22 13 10 19 2 0 8 11 7 4 23 9 5 15 18 21 1
22 14 10 17 20 6 16 13 0 8 23 19 9 2 15 11 7 18 1 10 4 14 21 16
17 13 8 5 6 22 19 2 20 0 3 9 10 18 23 11 4 1 13 17 14 7 21 15
12 19 8 5 20 22 2 0 18 10 11 16 13 23 17 21 4 6 3 19 8 7 12 2
9 0 22 1 20 11 13 17 10 4 6 23 14 3 7 5 19 16 0 9 8 1 18 12
20 11 21 17 15 23 3 7 10 13 4 5 16 2 19 8 12 0 1 22 18 9 14 11
3 6 10 15 4 21 17 20 16 12 19 2 23 13 9 14 8 18 22 3 6 7 11 15
Bag test:
12 2 21 1 8 5 20 23 13 6 11 19 9 10 15 22 14 17 7 3 4 16 18 0
6 23 19 11 22 16 13 15 18 0 21 12 8 9 4 10 5 7 2 1 3 17 20 14
5 19 0 9 10 17 1 3 13 11 18 20 22 6 15 8 2 12 4 7 23 21 14 16
11 16 12 19 22 23 1 13 10 21 2 7 8 18 14 0 9 20 3 15 4 5 6 17
7 14 0 18 11 16 2 1 10 15 22 20 19 3 13 23 8 4 9 5 12 17 21 6
6 20 1 12 9 18 21 15 11 2 13 5 16 4 0 14 17 7 10 3 22 8 19 23
19 21 3 17 22 12 0 6 1 11 15 18 8 14 9 20 7 2 4 13 23 10 16 5
15 8 21 4 16 10 3 2 13 18 20 0 9 1 17 19 22 14 23 5 6 7 12 11
1 8 9 12 15 21 13 20 17 14 6 10 0 11 23 5 16 4 7 2 22 19 3 18
6 1 15 12 22 8 21 3 23 10 2 13 0 9 19 11 5 16 18 20 4 17 14 7
 Attachments

 bag_lru.zip
 (1.37 KiB) Downloaded 81 times
Re: Randomizing block permutations for a color matching game
The bag algorithm seems to be more or less exactly what I've done now. I wrote a script that used FisherYates and concatenated a few permutations. The most noticeable thing is that certain drops are notable (like there is a double red chest drop), and are always followed by the same drop since there are only a handful of permutations. Obviously that wouldn't be a problem using a RNG at runtime. Still... I really like that LRU version, and it doesn't need any nonPOT modulos.
Re: Randomizing block permutations for a color matching game
RNGs can be reduced to nonpoweroftwo ranges using rerolls: modulo by the next largest power of two, then if the value is out of range, reject it and reroll. The masking ensures a second roll happens less than 50% of the time (and a third less than 25% of the time, etc) so the performance hit is normally neglible. I haven't tried it on the NES, but it may well be faster than a modulo.
This is the only unbiased way to reduce the range of a random number generator, if you care about perfect fairness. A modulo or multiplication doesn't distribute the inputs to the outputs evenly  some outputs will always be slightly more likely than others, unless the input range is an integer multiple of the output range.
This is the only unbiased way to reduce the range of a random number generator, if you care about perfect fairness. A modulo or multiplication doesn't distribute the inputs to the outputs evenly  some outputs will always be slightly more likely than others, unless the input range is an integer multiple of the output range.
Re: Randomizing block permutations for a color matching game
So far I've been terribly happy with that modified LRU algorithm. The "key" blocks in this game should be fairly spread out, and the way it works feels really good.
Rerolling: That's also really interesting... I was pondering how to do that fairly. Kind of obvious in retrospect, basically the same as generating uniform noise within a unit sphere. I'm currently using the 8 bit LFSR algorithm from the wiki, and didn't bother to read up on a statistical analysis of it. Maybe that isn't good enough to bother? Meh. PRNGs are such a black hole. If it feels good move on I guess.
Rerolling: That's also really interesting... I was pondering how to do that fairly. Kind of obvious in retrospect, basically the same as generating uniform noise within a unit sphere. I'm currently using the 8 bit LFSR algorithm from the wiki, and didn't bother to read up on a statistical analysis of it. Maybe that isn't good enough to bother? Meh. PRNGs are such a black hole. If it feels good move on I guess.