Jump to content
Sign in to follow this  
Karl G

Shuffling Algorithm

Recommended Posts

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? 

Share this post


Link to post
Share on other sites

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

 

  • Like 1

Share this post


Link to post
Share on other sites

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

 

127_plus_31.png.d4c3c2a39e36099ab41d6f2e21803200.png

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

  • Like 2

Share this post


Link to post
Share on other sites

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.

  • Like 2

Share this post


Link to post
Share on other sites
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

 

  • Like 1

Share this post


Link to post
Share on other sites
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. 

Share this post


Link to post
Share on other sites

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.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...