Randomizing block permutations for a color matching game.

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
User avatar
slembcke
Posts: 172
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Randomizing block permutations for a color matching game.

Post by slembcke »

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

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?
User avatar
pubby
Posts: 583
Joined: Thu Mar 31, 2016 11:15 am

Re: Randomizing block permutations for a color matching game

Post by pubby »

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! :beer: :P
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Randomizing block permutations for a color matching game

Post by tepples »

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 Fisher-Yates 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.
User avatar
slembcke
Posts: 172
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Re: Randomizing block permutations for a color matching game

Post by slembcke »

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.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Randomizing block permutations for a color matching game

Post by tepples »

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.
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
Notice that in "Bag test", each outcome appears once in each line of 24.
Attachments
bag_lru.zip
(1.37 KiB) Downloaded 120 times
User avatar
slembcke
Posts: 172
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Re: Randomizing block permutations for a color matching game

Post by slembcke »

The bag algorithm seems to be more or less exactly what I've done now. I wrote a script that used Fisher-Yates 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 non-POT modulos.
Rahsennor
Posts: 479
Joined: Thu Aug 20, 2015 3:09 am

Re: Randomizing block permutations for a color matching game

Post by Rahsennor »

RNGs can be reduced to non-power-of-two 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.
User avatar
slembcke
Posts: 172
Joined: Fri Nov 24, 2017 2:40 pm
Location: Minnesota

Re: Randomizing block permutations for a color matching game

Post by slembcke »

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. ;)
Post Reply