Select a random element (or set of elements) from a query

[alice-i-cecile]

What problem does this solve or what need does it fill?

Selecting random elements is a common gameplay tasks. We can quickly and ergonomically generate possible lists of

What solution would you like?

Implement the SliceRandom trait for Query.
Nope, this is not publically implementable. We have to use the alternative, implementing it for our associated iterator type.

Create an example.

What alternative(s) have you considered?

1. Users could manually implement this functionality each time. This is tedious, error prone and probably slower.
2. We could create our own methods that do this. This breaks from the ecosystem standard for no good reason.
3. We could implement the IteratorRandom trait instead. Taking a look, our ability to mutate the elements of the query + desire to be able to shuffle the order probably makes SliceRandom more fitting. More importantly, Query isn't itself an iterator (nor should it be): being able to operate directly on a query rather than query.iter() is more natural and convenient.

Additional context

Related to #1470.

[alice-i-cecile]

Of note: this will be trickiest with Changed and Added filters: we can't determine a list of possible entities directly from the archetypes. In those cases, we will likely need to collect, making this an O(n) operation, rather than a O(1) operation.

[TheRawMeatball]

When implementing this for filters that involve Changed or Added, we probably want to use the NopFetch introduced in #2305 and count the iterator to get the length with minimal overhead.

[mfdorst]

@alice-i-cecile Is it possiple to implement SliceRandom? SliceRandom::choose_multiple returns SliceChooseIter, which I don't see a way to construct.

[alice-i-cecile]

Yep, looks like you're correct @mfdorst. rand doesn't provide any public constructors :(

[mfdorst]

Looks like IteratorRandom is possible to implement. Should we do that?

[mfdorst]

On QueryIter that is. Or should we just emulate SliceRandom without actually implementing the trait (that is, provide the methods it provides, but with our own version of the SliceChooseIter type)?

[mfdorst]

Oh, actually, from the rand::seq::IteratorRandom documentation:

This trait is implemented on all iterators I where I: Iterator + Sized and provides methods for choosing one or more elements.

So I guess all the user needs to do is

use rand::seq::IteratorRandom;

and they will have this functionality already.

[alice-i-cecile]

So I guess all the user needs to do is

use rand::seq::IteratorRandom;
and they will have this functionality already.

Excellent! @mfdorst, could you make an example showcasing this? We can add rand as a dev-dependency :)

[TheRawMeatball]

For this method to be efficient, we should also consider adding a custom nth implementation.