gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > random numbers + elimination

#19914 - darknet - Wed Apr 28, 2004 12:01 am

Well one of the mini-games I am working on goes like so:

Its basically a classical video gaming quiz (since my project is a collection of classic remakes) that shows the user a screenshot of some famous game that they have to name by selecting from the choices given. I have 25 built in as of now but only require the user to look at 10 and get 10 correct.

The entire mini-game seems very trivial to me with the exception of one aspect. I want the sequence of screens to be random and not have the same one appear twice.

For example, I want to prevent the folowing sequence: Mortal Kombat II, Dig Dug, Mario Kart, Mortal Kombat II.

To fight that right now, I have a screenshot structure that has a 'used' flag that is set when the screenshot has been randomly generated.

However, the only routine I can think of for generating a random screen is as follows:

Code:

//num_screens is the total amount available.

Screenshot screens[num_screens];

.....

 while(lessThanTenCorrect) {

   int screenToShow = (rand()%(num_screens-1));

      if( !screens[screenToShow].used) {
       //go ahead and process and getinput and whatnot, set to used.
      }

       else {
      //pick another random number?
      }

    //check if ten have been answered....set lessThanTen to false if true
}


Ideally, I want a function that gets a random number bounded by the amount of screens available, and once a number has been generated, DO NOT use that same generated value again when the random function is recalled within a loop.

Sorry if this seems trivial, I know what I have will work, but I want to somehow prevent from constantly generating the same random number, thus slowing down the program dramatically.

Any help is greatly appreciated,
-Mike

#19917 - tepples - Wed Apr 28, 2004 12:17 am

So you want to create a random permutation. The easiest way to do this:
  1. Initialize an array to [0, 1, 2, 3, ...] as long as the permutation.
  2. For each element in the array, swap it with a PRNG-chosen element.

Another way borrows from implementation of hash tables: if you choose an item that's already in use, jump to another item using probing.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#19919 - darknet - Wed Apr 28, 2004 12:26 am

of course! thats a great idea, thanks tepples, I will try that immediately.

-Mike

#19927 - darknet - Wed Apr 28, 2004 2:41 am

I did exactly what I believe it was you told me to do...however the problem is that it gives me many many repeat values. Here's the function:

Code:

void createRandomPermutation(int a[]) {

  int swapWith, temp;

  for(int i = 0; i < NUMBER_OF_SCREENSHOTS; i++) {

     swapWith = (rand()%(NUMBER_OF_SCREENSHOTS-1));

     temp = a[i];
     a[i] = a[swapWith];
     a[swapWith] = a[temp];

  }
}

I did initalize the loop first and then I called that function (i.e. array[0] = 0, array[1] = 1, etc...)

Even stranger, every time the program is ran I get THE SAME set of random generations....

hmmm..

any reply is appreciated, thanks a lot,
-Mike

#19929 - sgeos - Wed Apr 28, 2004 3:10 am

darknet wrote:
Even stranger, every time the program is ran I get THE SAME set of random generations....

How are you seeding your RNG? If you seed it with the same value every time, you will get the same "random" sequence. If your code looks something like this:
Code:
initialize_timers(REALLY_FAST);
setup_code();
srand(get_timer_value());

That will run the same way
Code:
srand(PRESET_VALUE);

does, because the setup code takes a fixed amount of time. You'll need to seed from SRAM or after the user input to make thing less predictable:
Code:
initialize_timers(REALLY_FAST);
setup_code();
wait_for_input();
srand(get_timer_value());

-Brendan

#19930 - niltsair - Wed Apr 28, 2004 4:04 am

Also here:
Code:
temp = a[i];
     a[i] = a[swapWith];
     a[swapWith] = a[temp];


You made an error. Last line should be : a[swapWith] = temp;
Since you're storing the value directly and not the position.

To get a better random number, search on this forum 'random', there are a couple of post that discuss this in details. Just using the rand() function won't do on the Gba.
_________________
-Inside every large program is a small program struggling to get out. (Hoare's Law of Large Programs)
-The man who can smile when things go wrong has thought of someone he can blame it on. (Nixon's Theorem)

#19938 - sgeos - Wed Apr 28, 2004 6:57 am

rand() will work. It is just not the best RNG out there.

rand() % VALUE is a horrible way to get a random number. Read the rand man page for details.

-Brendan