• Advertisement

Archived

This topic is now archived and is closed to further replies.

Generating evenly distributed random numbers.

This topic is 5097 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi Guys, Ive made tetris clone, but I am not happy with the random number sequence I get when using rand() to get a new number which is the index of the next block to play. Is there a way of making the random numbers I get more evenly distributed so I dont get so many repeats of the same block so often. Thanks DarkStar UK ------------------------------- Loves cross-posting because it works

Share this post


Link to post
Share on other sites
Advertisement
you could store the last index in a variable and then, at create-piece time, compare... if they''re the same, then rand() again.

it may be an alternative

Share this post


Link to post
Share on other sites
Are you seeding the random number generator with something like:
srand(time(0));

?

Just because you get the same block twice doesn''t meant it isn''t random I hope you know.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I hope you''re not making something like

if (number < largest_piece_index) number = largest_piece_index; 


''Cause that would make piece # largest_piece_index show up more often than the rest.

If you have largest_piece_index types of pieces, this should over time generate a completely uniform distribution of pieces:

number = rand() % largest_piece_index 

Share this post


Link to post
Share on other sites
quote:
Original post by daerid
Actually, if you read up on it, using the modulous operator (%) does not distribute the numbers evenly.


If rand() creates a list of random numbers from zero to n, then rand() % x will be equally random as long as n % x == 0. If n is much greater than x, it will be hard to tell that rand() % x is creating a slightly less random list when n % x != 0.

This whole discussion is a little off, mathematically. The idea of a list of random numbers that you force to be evenly distributed is a contradiction in itself. If you have a good random number generator, the list will probably eventually become pretty well distributed, but there are no guarantees.

The rand() function in stdlib works pretty well - if you are finding that your numbers are horribly distributed, even in long lists, then you are probably doing something wrong. Can you post the line you''re using to pick the next block with? Then we can probably give you a little more help.

Share this post


Link to post
Share on other sites
Something like:
number = int( (float)rand() / float(MAX_RANDOM_NUMBER) * float(largest_piece_index) );

This might work, but you have to know that rand() isn''t the best random number to begin with.

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
rileyriley: mathematically correct, but the assumption that rand() is random is false. Given the pathetic VC generator (side note: unchanged since qbasic days), whose lower bits are of lesser ''quality'', it is better to use the whole range, as _DarkWIng_ suggests.

Share this post


Link to post
Share on other sites
Just a comment on _DarkWIng_''s suggestion: largest_piece_index would hardly ever be chosen. It would result only if rand() returned exactly MAX_RANDOM_NUMBER. Of course, he did use the phrase "Something like", so he''s forgiven. I''m pretty sure that this will work well enough:

int Random(int Min, int Max)
{
return (int)((double)rand() / ((double)RAND_MAX + 1.0) * (double)(Max - Min + 1)) + Min;
}

rand() / (RAND_MAX + 1) ensures that the resulting fraction is greater than or equal to 0, and almost up to, but not including 1, which is important when returning an evenly distributed integer value.

Share this post


Link to post
Share on other sites
thanks for the replies,

I am doing this for my random numbers

currentPiece = rand()%MAX_PIECES;

I can accept 2 or 3 of the same pieces appearing consecutively but not when I get 4-5 of the same in a row..like it sometimes does. This is what I have never seen in tetris...Infact Ive never ever seen a block appear more than 2 times in a row in Tetris before (It may, but Ive never seen it).

Thanks...maybe this problem is something thats really simple to solve, if I stop being silly and think but Im too stressed with assignments to think clearly right now

DarkStar
UK

-------------------------------
Loves cross-posting because it works

Share this post


Link to post
Share on other sites
This is an interesting problem. The rand() function combined with the modulus operator should not be that much of a problem in your case. Want you should do instead is to decrease the chances of obtaining a particular block next if it has been very common in a specific timespace. Of course, this is not truly random, but it does give much more even and nice result.

Myself I was faced with this problem when I made the card dealing routine for a card game. First I basically just handed out all cards to all players randomly, and made sure they got even numbers each. Since there is a limited number of cards in the deck, it had the unpleasant side effect that if player had gotten very few cards when almost all had been dealt out, that player got all the remaining cards. The loop that handed out the cards went through the cards in order, and it resulted in that a player could end up with a perfect matching string of cards: That is, for example all Sixes to Kings of Hearts. It was not good for the gameplay.

My solution was to remove the total randomness of my card dealing. It was accomplished with the function below:


i8 CSevenGame::GetRandomWithLimit(i8 range, i8 *outcomes, i8 max_seq)
{
i32 i;
i32 outcome_sum = 0;
i32 random;
i8 chance;
i8 offset = 0;

//calculate the sum of all outcomes

for(i = 0; i < range; i++)
outcome_sum += outcomes[i];

//get a random result

random = rand() % (max_seq * range - outcome_sum); //outcomes left


//loop to see which one of the future possible outcomes was taken

for(i = 0; i < range; i++)
{
//calculate "chance", which is the number of outcomes left in a sequence

chance = max_seq - outcomes[i];

//group this with previous chances and see if this sequence was selected

if((random < offset + chance) && (chance > 0))
{
return i;
}

//increase offset

offset += chance;
}

return -1; //in case of error

}


Don't worry if you have trouble understanding it at first, because the variable names are a bit hard to understand since the function is rather generic. Basically "range" is the number of players, "outcomes" the pointer to an array of which each index is a player's number of cards, and "max_seq" being the maximum number of cards a player may have. Essentially the function makes a player that already has a lot of cards get less of a chance to obtain a new one, while a player with few cards has a large chance.

I would imagine you could implement something like this where the maximum number of cards would be translated into the maximum number of Tetris blocks for a specific time period. I hope this helps.

EDIT: Messed up source tags.

[edited by - Unwise owl on February 8, 2004 3:17:11 PM]

Share this post


Link to post
Share on other sites
Assuming rand() works fine, which it does for me you might want to switch from tinkering with probabilties to fixing the problem at hand:

You don''t want more than 3 equal pieces in a row? So monitor the pieces you create and if the piece appears to often, pick another.

Not satisfying? Wouldn''t satisfy me either :-)
Initial state: 1/n probability for each piece
Later: 1/2*n probability for a repeat. And (if my math didn''t fail me)

1
( 1 - ------- )
2 * n 1 1
--------------------- = ----- - ----------
n - 1 n-1 2n*(n-1)

for each piece different from the last.
Should a piece be picked more than twice, set its probability to reapear to 0.



I may be getting older, but I refuse to grow up

Share this post


Link to post
Share on other sites

  • Advertisement