Deducting already chosen ints from a list?

Started by , Mon 17/01/2011 17:02:50

Previous topic - Next topic

m0ds

Hi techies, I'm looking for a simple and effective way to make AGS remove randomized ints that have already been chosen.

For example, the script chooses between 1 and 50 numbers. Say 6 comes up. The next time it randomizes, I want it to have removed the previous number/skip over it, so that 6 will never come up again, and preferably continue to do this until the last number is reached. I can't figure out how to do it.

If anyone has a script suggestion that would be great, this will help me with all manner of games in the future.

Mods

Matti

#1
Something like this perhaps:

Code: ags

bool AlreadyChosen[51], ready;
int i;

i=0;
while (i<51){
  AlreadyChosen[i]=false;
  i++;
}


Then the part to get a random number:

Code: ags

ready=false;
while (!ready){
  i=random(50);
  if (!AlreadyChosen[i]) {
    ready=true;
    AlreadyChosen[i]=true;
  }
}


I'm not sure if this could be done easier, but it should work.

i is the random number, AlreadyChosen[ i ] is true when i was already chosen once, ready is just there to stop the while loop.

RickJ

Make a bool array having the same number of elements as the range of random numbers you desire.   Each element in the array indicates whether the corresponding number has been used or not.   This ought to work for a range of 50..100 as your example suggests.   Here is an untested example of how to code such a thing.

Code: ags

#define  RANDSIZ 50
bool RandUsed[RANDSIZ];

int GetRand(bool init) {
   int i, n,  not_found;

   // Start over again
   if (init) :
      i=0;
      while (i<RANDSIZ) {
         RandUsed = false;
      }
   }

   // Get random number only once
   while (n<RANDSIZ) {
       i = Random(RANDSIZ);
       if (RandUsed[i]) return i;
       n++;
   } 
   return -1;   // Return -1 if all numbers have been used
} 


Kweepa

#3
Rick's example is good - except that he goofed the second loop.
I would separate out the first loop into a different function too.
So:

Code: ags

#define RANDSIZE 50
bool RandUsed[RANDSIZE];

function InitRand()
{
   int i = 0;
   while (i < RANDSIZE)
   {
      RandUsed[i] = false;
      i++;
   }
}

int GetRand()
{
   int i = 0;
   int n = Random(RANDSIZE-1); // Random() includes the top of the range
   while (i < RANDSIZE)
   {
      int x = (i + n) % RANDSIZE;
      if (!RandUsed[x]) return x;
      i++;
   }
   return -1;
}


As you can see, getting the random number is quite messy.
An alternative method is to imagine the random numbers are like a pack of cards, and to shuffle the pack, then just deal them out.

Code: ags

#define RANDSIZE 50
int randoms[RANDSIZE];
int currentRandom = 0;

function ShuffleRand()
{
   int i;
   // create in-order "pack"
   while (i < RANDSIZE)
   {
      randoms[i] = i;
      i++;
   }
   // shuffle
   i = 0;
   while (i < 3*RANDSIZE) // this is a reasonable amount to shuffle...
   {
       int a = Random(RANDSIZE-1);
       int b = Random(RANDSIZE-1);
       int t = randoms[a];
       randoms[a] = randoms[b];
       randoms[b] = t;
       i++;
   }
   currentRandom = 0;
}

int GetRand()
{
   if (currentRandom < RANDSIZE)
   {
       currentRandom++;
       return randoms[currentRandom-1];
   }
   return -1;
}


As you can see we've traded some up-front shuffling cost against per-random cost.
An advantage of this method is that the cards in the "pack" can be anything.

[EDIT] I should mention that Matti's will work as long as you change the AlreadyUsed array size to 51, and add some code to count the number of numbers doled out). The technique is frowned upon by purists since there's no guarantee in general that the loop will terminate in a reasonable time (although in AGS it's guaranteed, since the random number generator isn't truly random).
Still waiting for Purity of the Surf II

m0ds

3 versions to have a play with, thank you very much gentlemen! I'll give it a try tomorrow. I've never heard of "bool" in an AGS sense and what it is or can do, so thats all new to me, but yes much appreciated, I would never have been able to work this out!

Ryan Timothy B

Quote from: Mods on Mon 17/01/2011 21:42:19
I've never heard of "bool" in an AGS sense and what it is or can do, so thats all new to me
A bool stores either True (1) or False (0).

Matti

Quote from: SteveMcCrea on Mon 17/01/2011 20:27:19
[EDIT] I should mention that Matti's will work as long as you change the AlreadyUsed array size to 51, and add some code to count the number of numbers doled out). The technique is frowned upon by purists since there's no guarantee in general that the loop will terminate in a reasonable time (although in AGS it's guaranteed, since the random number generator isn't truly random).

Yes, it's a short but rather poor code. And yes, I forgot the fact that the while loop would've been stuck in case all the numbers were already used.

Also, there was a little mistake which I just corrected. The stupid txt-spelling made all my "r" variables to "are" and when I changed all the "are" to "i" I forgot one of them.

Knox

I was about to post a similar question, and if Mods doesnt mind me asking a question in his thread:

I was wondering if these scripts can be used in this situation (Im not sure because I tested the above scripts but sometimes certain numbers were returned multiple times in the test script I included at the bottom of my post):

Say Ive got 50 different gameplay events and each can only be played once. A script chooses randomly an int (from a number pool between 0 and 50).

From the returned int, its corresponding gameplay event gets chosen and its corresponding room is shown (with gameplay)...once played + completed, its corresponding int gets removed from the number pool forever, so that its corresponding gameplay event never gets chosen randomly again.

To quickly test (to see if I understand this), I tried using the above code in this way:

Upon clicking a "test" button:
Code: ags

ShuffleRand();
Display("%d", GetRand());


Im expecting that after 51 clicks on that "test" button, all the numbers would have been displayed only once, in random sequence until finally -1 gets returned each time after all numbers are exausted...right?

I think Im not using those lines right though because testing this, numbers get repeated and the number pool doesnt seem to "diminish".
--All that is necessary for evil to triumph is for good men to do nothing.

Khris

You aren't supposed to call ShuffleRand() more than once, that function resets the pool.

Knox

--All that is necessary for evil to triumph is for good men to do nothing.

monkey0506

Another fun way to do this, and yes I realize this is rather frivolous at this point, would be to make use of the built-in function Game.DoOnceOnly..and why not try using a dynamic array as well? :)

Code: ags
int __array[]; // the items in our random list's range, in a random order
int __arraySize = 0; // the current size of the array
int __instance = 0; // used like a session ID is for web pages, so we can dynamically change the size of our random list
int __random; // the current array index

void SeedRandomList(int size)
{ // (re)sizes and populated our array with random values
  if (size) size++; // Random is an inclusive range
  if ((size <= 0) || (size > 1000000)) return; // consider handling this better..
  __array = new int[size];
  int i = 0;
  while (i < size)
  {
    int ran = Random(size);
    if (Game.DoOnceOnly(String.Format("Random %d: %d", __instance, ran)))
    {
      __array[i] = ran;
      i++;
    }
  }
  __instance++;
  __arraySize = size;
  __random = 0;
}

int RandomFromList()
{
  if (__random >= __arraySize) return 0;
  int ran = __array[__random];
  __random++;
  return ran;
}


You would then use those functions like this:

Code: ags
// enters room or some such..
  SeedRandomList(5); // 5 unique responses in random order before default

// interact with..something
  int ran = RandomFromList();
  if (ran == 0) player.Say("I don't see what's so special about it.");
  else if (ran == 1) player.Say("Nothing to see here.");
  // ..you get the idea..
  else player.Say("I already told you five times there's nothing there, I'm not looking again!");


Okay, so my example is crappy, and the end-result is nearly identical to Steve's..but hey, using Game.DoOnceOnly in such a non-conventional fashion is fun! :=

m0ds

I forgot to mention, are those samples you guys posted compatible with 2.72?  :=

Kweepa

They should be... maybe Game.DoOnceOnly is a new function, but I you could always try it out and see if it compiles!
Still waiting for Purity of the Surf II

monkey0506

I think Game.DoOnceOnly is a 3.x funtion..but dynamic arrays definitely weren't around until 3.0..so, you can just ignore me then. :P

bicilotti

I was wondering if one could use prime numbers to write yet another method, but then I got asleep.

SMF spam blocked by CleanTalk