Random Duplicates

Hi, I am working on a randomly generated game which means that it is infinite but I don't want the same obstacle to be chosen twice after one another.

Like if I get the random numbers (1.2.2.3.4.5.2)
I don't want that the two will only get displayed once but not after each other so (1.2.3.2.4.5.2) something like this.

 

Remember the last generated number. Generate a new one. If it's the same repeat until it's not the same anymore.

 

Can you give an example, please

 

Well.. at some point in your code you are generating these numbers and add them to the list of random numbers you already generated, right? So when you generate a new number, look at the last one you generated, and only accept the new number if they are not equal. Something like this:

Code (CSharp):

1. public List<int> GenerateRandomNumbersList(int length, int rangeMin, int rangeMax){
2.     List<int> randomNumbers = new List<int>(); // <-- i assume you store them like this
3.     int lastNumber = -1;
4.  
5.     for(int i = 0; i < length; i++){ // <-- we generate length-many numbers
6.         int newNumber;
7.         do{
8.             newNumber = Random.Range(rangeMin, rangeMax); // <-- we generate a random number in the desired range
9.         } while(newNumber == lastNumber); // <-- we get a new number if it's the same as the last
10.         randomNumbers.Add(newNumber); // <-- we save this number to the result list
11.         lastNumber = newNumber; // <-- we remember the new last number we generated
12.     }
13.     return randomNumbers; // <-- we return a list of random numbers without two repeating after each other
14. }

Typed it here on the forum so i hope there are no typos.

 

Code (CSharp):

1. float ObstcalePlace = Random.Range(1,10);
2.        CurrentRanNum = ObstcalePlace;
3.        if (CurrentRanNum == LastRanNum)
4.        {
5.          ObscalePlace ++;
6.        }
7.        LastRanNum = ObscalePlace;

I ended making my own code since the one you wrote was not working and I want to know if something like this will work

 

Dont just say "it does not work". It does. As i said i typed it directly in the forum, so small oversights are bound to happen. I added the missing variable declaration for newNumber in the above example.

The approach you posted has two problems:

• The numbers are not truly random anymore as you just increment them when they are duplicated
• You can end with numbers outisde the defined range. Example: 10 will be incremented to 11
• (You needlessly introduced the CurrentRanNum variable which could be replaced with ObstaclePlace)

 

Another approach is to make a "deck of cards" where you a) guarantee the distribution of certain elements, then b) shuffle the cards, c) check if they satisfy your condition, and if not d) swap the offenders according to some rule, and repeat (c) until it passes.

In your case, the cards are simple ints, so a basic List<int> would suffice.
1) populate the elements of this list without using random at all.
2) shuffle the slots of this list according to Fisher-Yates algorithm.
3) iterate the list starting from 1, while checking the two neighboring elements (n-1 and n): if they're equal, go to (4), otherwise (5).
4) swap the element n with the element n+1, wrap around as required; go to (3); optimally: run (3) while swapping until satisfied, then continue running (3) where it stopped; this way you can finish the algorithm in just two passes: (2) and (3).
5) success.

This algorithm may fail if you end up with poor statistics due to badly populated list in step (1).
I.e. if you have only 1s and 2s and there are two times as many 1s, it has no choice but to fail.
In other words, even though (4) can be implemented with

while

loop, you have to make sure there is a safety mechanism for debugging purposes, or it might hang Unity with poorly selected data.

 

If you just want to avoid picking the same number twice in a row there's no need for a loop to retry. You can simply "remap" the last number to some other number. The basic idea is that you simply reduce the range by one and if you picked the last number you simply remap to the last index of your original range. This is still uniformly distributed and doesn't have any issues with overflow.

Though this approach means you essentially have a different approach for the first roll you ever do and subsequent rolls. It would basically work like this:

Code (CSharp):

1.     public static int PickRandomNumber(int aMin, int aMax)
2.     {
3.         return Random.Range(aMin, aMax);
4.     }
5.     public static int PickRandomNumber(int aMin, int aMax, int aLastNum)
6.     {
7.         int num = Random.Range(aMin, aMax-1);
8.         if (num == aLastNum)
9.             num = aMax - 1;
10.         return num;
11.     }
12.  

This always works, even with a range of 2. So assume min is 0 and max is 2 (exclusive, as usual so we can only get the values 0 and 1). In this case the Random.Range call will always return the value 0. If the last value was a 0 we will pick the 1. If the last value was a 1 we get that 0. So it's effectively toggling between 0 and 1 since that's the only thing you can do when you don't want to pick the same number twice in a row.

Now imagine a range of 3 (min=0,max=3 so we get the number 0, 1, 2). Once we have picked the first number we only have two choices out of those 3 numbers. if the last picked number is 0 we only want to pick 1 or 2. Our random range will give us 0 or 1. If it's a 1 we will pick the 1 as the next number. If it's a 0 we will pick the highest number, 2 in this case. If the last value is 2 the random range can pick either 0 or 1 and everything works as it should.

The advantage is this approach has constant runtime and no potential for requiring a number of iterations. With a loop you also have to be very careful with the choice of your range. If you restrict the range to 1 for some reason you would get caught in an infinite loop since you can never roll a different number in that case.

Of course if you want to avoid the last "x" numbers there's no way around using some sort of list of available choices. A simple solution is to use an array and exclude the last x elements of that array from our random choice. Once we picked a random number from the first n-x elements we simply exchange the one we picked with one of the excluded list. The excluded list of numbers is essentially a queue. So the last number is the newest element in that queue and the one that is moved back into the active space is the oldest element. This can be implemented quite easily with an array and a "ring buffer" pointer.

Code (CSharp):

1.     public static int PickRandomNumber(int[] aNumbers, int aExcludeCount, ref int aExcludeIndex)
2.     {
3.         if (aExcludeCount <= 0 || aExcludeCount >= aNumbers.Length)
4.             throw new System.ArgumentOutOfRangeException("aExcludeCount", "Need to be greater than 0 and smaller than the array length");
5.         int index = Random.Range(0, aNumbers.Length - aExcludeCount);
6.         int num = aNumbers[index];
7.         aExcludeIndex = aExcludeIndex % aExcludeCount;
8.         // swap picked number with the "oldest" from the queue
9.         int swapIndex = aNumbers.Length - aExcludeCount + aExcludeIndex;
10.         aNumbers[index] = aNumbers[swapIndex];
11.         aNumbers[swapIndex] = num;
12.         aExcludeIndex++;
13.         return num;
14.     }
15.  
16.  
17.  
18.  

As explained this will actually modify / shuffle the array you pass to this method. You also need to provide a aExcludeIndex variable which will track the queue state. Note that since this approach uses a fixed length ring buffer the last elements may not be picked until "exclude count" many draws since those elements are initially in the exclude range. If you really need this behaviour you either need to use another "state" variable to track how many elements are in the ring buffer, or use an actual List + Queue and literally moving the elements around. Here's a .NET Fiddle of an example with an array of 10 numbers and we pick 50 times a random number. You will notice that the every number we pick will never be equal to any of the last 3 numbers. Though as I mentioned the first draw can never contain 8,9 or 10. The second draw can never contain 9 or 10, the third draw can not contain the 10. From the fourth draw on all numbers are up for being picked (except for the last 3 of course, that's the point).

 

Given you are generating random floats instead of ints, this seems like a solution in search of a problem. The chances you'd generate 2 identical floats back to back are somewhere in the billions.

 

I just came up with a fix for my first approach that actually works with a single "state" variable. So this version will properly pick a random number from the whole range on the first draw. After that the ring buffer grows each time by one until it reaches the desired count.

Code (CSharp):

1.     public static int PickRandomNumber(int[] aNumbers, int aExcludeCount, ref int aExcludeIndex)
2.     {
3.         if (aExcludeCount <= 0 || aExcludeCount >= aNumbers.Length)
4.             throw new System.ArgumentOutOfRangeException("aExcludeCount", "Need to be greater than 0 and smaller than the array length");
5.         int cEx = aExcludeIndex;
6.         int offset = aExcludeIndex;
7.         if (cEx >= aExcludeCount)
8.         {
9.             cEx = aExcludeCount;
10.             offset = aExcludeIndex  % cEx;
11.         }
12.         int index = Random.Range(0, aNumbers.Length - cEx);
13.         int num = aNumbers[index];
14.        
15.         // swap picked number with the "oldest" from the queue
16.         int swapIndex = aNumbers.Length - offset - 1;
17.         aNumbers[index] = aNumbers[swapIndex];
18.         aNumbers[swapIndex] = num;
19.         aExcludeIndex++;
20.         return num;
21.     }
22.  

Note that the "exclude index" has to start at 0 and will automatically grow infinitely. If you want to restart a new sequence (where you would pick a random number from the whole array) you just have to set the exclude index back to 0. Here's a fiddle for this example which also prints the state of the number array each draw which helps to follow what actually happens inside the array.


https://dotnetfiddle.net/61pTTz

 

Another simplistic solution (bloated by integrated statistics test)

Code (csharp):

1. void demo() {
2.   var list = new List<int>() { 0, 1, 2, 3, 4, 5, 6, 7 }; // source
3.  
4.   const int ITERATIONS = 500;
5.   var counts = new int[list.Count];
6.  
7.   int index = Random.Range(0, list.Count); // seed sample
8.  
9.   for(int i = 0; i < ITERATIONS ; i++) {
10.     index = walker(list, index, Random.Range(0, 2)); // core algorithm
11.  
12.     counts[index]++;
13.     Debug.Log(list[index]);
14.   }
15.  
16.   Debug.Log("---- stats ----");
17.   for(int i = 0; i < counts.Length; i++)
18.     Debug.Log($"{list[i]}: {counts[i]} ({100f*counts[i]/ITERATIONS:F1}%)");
19. }
20.  
21. int walker(List<int> list, int index, int offset) {
22.   return (index + (list.Count >> 1) + offset) % list.Count;
23. }

This little buddy swiftly generates uniformly-distributed stochastic sequences that are guaranteed to have unequal neighbors. Works well with 3+ elements, in one pass (or on-the-fly), includes statistical analysis as a proof of distribution.

Random.Range(0, 2) can be made as a lookup instead, making this the fastest algorithm I can think of.

(It can be simplified further.)

 

If you are choosing from a finite set, what about putting them all into a List, then picking an entry at random from 0 to Length-2, then remove that entry and add it to the end of the list? Edge case for the first choice as the last entry in the initial list will never be the first one chosen, but one could solve this any number of ways (choose the first item added to the list at random, then insert all the others at position 0, shoving the randomly chosen one to the end, for example).

 

That's what my code essentially does, however instead of removing it and adding it to the end you can simply swap the last element and the one you've choosen. My latest code also works with more than "one" last element. So it always excludes the given number of last elements. In my case the last 3 elements are essentially taken out of the pool and the oldest excluded one is re-integrated into the pool each draw.