How can I get N random objects from array?

Question

[Range(5, 50)]
    public int waypointsCount = 10;

    private System.Random random = new System.Random();

    // Use this for initialization
    void Start ()
    {
        var Nodes = UnityEngine.GameObject.FindGameObjectsWithTag("Node");
    }

I want to get a random number of gameobjects from Nodes according to the number in waypointsCount. So if for example the number is 10 then I want to get 10 random gameobjects from the array nodes. And the gameobjects should not be duplicates.

Answer 1

Use the greatest tricks of all time:

using System.Collections.Generic;

[Range(5, 50)]
public int waypointsCount = 10;

void Start ()
{
    var Nodes = UnityEngine.GameObject.FindGameObjectsWithTag("Node");

    HashSet<GameObject> randomObjects = new HashSet<GameObject>();

    while(randomObjects.Count < waypointsCount){
        randomObjects.Add(Nodes[UnityEngine.Random.Range(0, Nodes.Length)]);
    }

    // use randomObjects
}

Here are HashSet docs. When you add an objects to a HashSet, the system checks if the object is already there. Only if it isn't - the object is added. That's why sets are used to maintain uniqueness in programming languages.

The script will choose a random GameObject from nodes, until randomGameobjects HashSet's size is equal to waypointsCount. Even if it chooses an already existing waypoint/node - it won't add it to the collection (because it's a HashSet - it does what it does).

Answer 2

You can do this faster than a Hashset with a simple linear scan:

var randomObjects = new GameObject[waypointsCount]; 

for(i = 0; i < waypointsCount; i++) {
    // Take only from the latter part of the list - ignore the first i items.
    int take = Random.Range(i, Nodes.Length);
    randomObjects[i] = Nodes[take];

    // Swap our random choice to the beginning of the array,
    // so we don't choose it again on subsequent iterations.
    Nodes[take] = Nodes[i];
    Nodes[i] = randomObjects[i];
}

This is effectively a Fisher-Yates shuffle (also called a Knuth shuffle) that terminates early.

Doing it this way has a couple of advantages:

• we can build the output array in-place (even just using the same memory as the input Nodes array if we want to), without setting aside extra memory for the hash structure for membership tests.

• if we want 49 items from a list of 50, we finish in exactly 49 iterations, every time. The Hashset method will take on average 3-4 times longer in this scenario, because its probability of choosing a duplicate and retrying goes up the longer our output list gets in proportion to the input. To pick the last random item in this scenario, the Hashset would need to try 25 times on average, since the list only contains 2 valid non-duplicate choices out of 50. The linear scan guarantees that we pick each item in a single try while avoiding duplicates through the re-ordering trick.