+Karl G Posted August 27, 2021 Share Posted August 27, 2021 I'm trying to figure out a good 8-bit shuffling algorithm. In this case, it's for a 7800Basic project, but the strategy would likely be the same regardless of language, or even 8-bit platform. The classic way to randomize a finite set of objects like cards would be to generate a random number between 0 and (#items - 1), then place the chosen item into a new list. The original list would be reduced by one, a new random number is generated for the smaller range, etc, continuing until all of the items from the original list have been selected and placed in the new list. The problem with this approach is that I don't know a good, easy way to generate random values for arbitrary number ranges. For powers of two it is easy, but what about generating numbers between 0-2 or 0-4, etc? Does anyone have a suggestion either for a better method for shuffling items like this, or for a decent way to generate random numbers for odd number ranges like this? 1 Quote Link to comment Share on other sites More sharing options...
+Karl G Posted August 27, 2021 Author Share Posted August 27, 2021 It occurs to me that I can divide 256 by each of the "odd" ranges, and make a table for each cutoff number, distributing the bias throughout the range. then I can get my random value, and iterate through the appropriate table to determine the random number for that range. threerange 85, 170 fiverange 51, 102, 153, 204 sixrange 42, 85, 127, 170, 213 sevenrange 36, 73, 109, 146, 182, 219 1 Quote Link to comment Share on other sites More sharing options...
RevEng Posted August 27, 2021 Share Posted August 27, 2021 Yep, that's a good way for lower-ranges. It does get a little out of hand for comparisons, for larger ranges. Near powers-of-two aren't bad either. You just have to throw out results that don't match and go back to the pot. Depending on how close the range is to the power-of-two, you only wind up iterating on occasion. ; return 0-2 getval val=rand&3 ; val is 0-3 if val>2 then goto getval ; throw back the any 3 result Of course, it's not a good choice for large numbers that aren't near a power-of-two. We have a thread somewhere here that have combined power-of-two random routines that are quick, but not evenly distributed. Something like this... val=rand & 127 val=val+(rand & 31) ; return a value between 0-158 gives a probability curve that looks like this... ...which might be fine for some purposes, and beneficial for other purposes. (ignore the jagged line. the segments would be perfectly straight from a probability perspective) 2 Quote Link to comment Share on other sites More sharing options...
BydoEmpire Posted August 27, 2021 Share Posted August 27, 2021 I went the cheesy and probably slow (but fairly effective) route of: for loop = 0 to 255 a = rand%max b = rand%max temp = mydata[a] mydata[a] = mydata[b] mydata[b] = temp next loop I haven't really had need to do this per frame or anything, so speed hasn't been a concern. 2 Quote Link to comment Share on other sites More sharing options...
ZylonBane Posted September 11, 2021 Share Posted September 11, 2021 On 8/27/2021 at 2:35 PM, Karl G said: The classic way to randomize a finite set of objects like cards would be to generate a random number between 0 and (#items - 1), then place the chosen item into a new list. The original list would be reduced by one, a new random number is generated for the smaller range, etc, continuing until all of the items from the original list have been selected and placed in the new list. That would waste RAM on two lists. You want a Fisher-Yates shuffle, which can randomize a list in-place. https://en.wikipedia.org/wiki/Fisher–Yates_shuffle 1 Quote Link to comment Share on other sites More sharing options...
+Karl G Posted September 11, 2021 Author Share Posted September 11, 2021 1 hour ago, ZylonBane said: That would waste RAM on two lists. You want a Fisher-Yates shuffle, which can randomize a list in-place. https://en.wikipedia.org/wiki/Fisher–Yates_shuffle In this case, the initial list will be in ROM, and the shuffled list would go in RAM. Edit: I did end up doing in-place shuffling after copying to RAM. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.