It is currently Wed Nov 21, 2018 12:41 am

 All times are UTC - 7 hours

 Page 1 of 1 [ 8 posts ]
 Print view Previous topic | Next topic
Author Message
 Posted: Wed Jul 11, 2018 11:58 pm

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

Top

 Posted: Thu Jul 12, 2018 3:49 am

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

Top

 Posted: Thu Jul 12, 2018 7:14 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20791
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

 Posted: Thu Jul 12, 2018 8:33 am

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

 Posted: Thu Jul 12, 2018 9:29 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20791
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.

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.

Top

 Posted: Thu Jul 12, 2018 11:24 am

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

 Posted: Sat Jul 14, 2018 1:34 am

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

 Posted: Mon Jul 16, 2018 5:15 pm

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 8 posts ]

 All times are UTC - 7 hours

#### Who is online

Users browsing this forum: No registered users and 2 guests

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

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki