It is currently Thu Sep 20, 2018 7:18 am

All times are UTC - 7 hours





Post new topic Reply to topic  [ 8 posts ] 
Author Message
PostPosted: Wed Jul 11, 2018 11:58 pm 
Offline
User avatar

Joined: Fri Nov 24, 2017 2:40 pm
Posts: 80
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?


Top
 Profile  
 
PostPosted: Thu Jul 12, 2018 3:49 am 
Offline
User avatar

Joined: Thu Mar 31, 2016 11:15 am
Posts: 359
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


Top
 Profile  
 
PostPosted: Thu Jul 12, 2018 7:14 am 
Offline

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


Top
 Profile  
 
PostPosted: Thu Jul 12, 2018 8:33 am 
Offline
User avatar

Joined: Fri Nov 24, 2017 2:40 pm
Posts: 80
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.


Top
 Profile  
 
PostPosted: Thu Jul 12, 2018 9:29 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
Location: NE Indiana, USA (NTSC)
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:
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 22 times
Top
 Profile  
 
PostPosted: Thu Jul 12, 2018 11:24 am 
Offline
User avatar

Joined: Fri Nov 24, 2017 2:40 pm
Posts: 80
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.


Top
 Profile  
 
PostPosted: Sat Jul 14, 2018 1:34 am 
Offline

Joined: Thu Aug 20, 2015 3:09 am
Posts: 396
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.


Top
 Profile  
 
PostPosted: Mon Jul 16, 2018 5:15 pm 
Offline
User avatar

Joined: Fri Nov 24, 2017 2:40 pm
Posts: 80
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. ;)


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 7 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group