Method to get a random entity from a query

[npetrangelo]

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

There is no out-of-the-box way to get a randomly selected result from a query.

What solution would you like?

A method on Query to pick one of the results at random, and another method to get n random results. Internally, a query has access to all valid results and should be able to select a random one in O(1) time. The ability to pick n random results should add the safety that no result appears more than once.

What alternative(s) have you considered?

I asked how to do this in the Bevy discord, and someone suggested I use the rand crate's choose method on a slice. To get that slice, I would have to iterate through every element using a query's iter and collect them first. This would be an O(n) operation for something that should only be O(1).

Additional context

Any other information you would like to add such as related previous work,
screenshots, benchmarks, etc.

[SarthakSingh31]

From what I understand, it cannot be done in O(1). Bevy does not maintain a list of entities that satisfy a query. The query iterator steps through every archetype storage that matches the query and then returns every entity in the storage that matches the filter.

To get random results that are fair across storages we will always have to iterate through every storage and build a list of entities that satisfy the query and filter. This will take O(N).

I think the best we can do is create a QueryRandomIter that will return the results in a random order. This will reduce the number of fetches to only the number of results you need.

[npetrangelo]

@SarthakSingh31 I'm actually really curious how Bevy works under the hood there, is there any conceptual documentation I can read about that?

[Victoronz]

It depends on what you define as "random". You can already get a random entity in 0.14 by sorting a query iterator by a random cmp function! You can lens your sort with () so only the entities themselves are fetched and randomized internally.
This way you can also define your own randomness!

An out of the box solution might just mean wrapping this kind of sort and exposing it as a method, this way no new machinery is needed.

Keep in mind that for this to work, every individual entity has to map to 1 random value within each "randomize" call, otherwise the sort may not finish/run for pathological periods.

[SarthakSingh31]

@npetrangelo I think the only way to learn the internals of bevy right now is to read the implementation. The ECS is fairly well documented. The logic to step through each entity in a query is defined here:

bevy/crates/bevy_ecs/src/query/iter.rs

Lines 1565 to 1673 in 9da18cc

	// NOTE: If you are changing query iteration code, remember to update the following places, where relevant:
	// QueryIter, QueryIterationCursor, QuerySortedIter, QueryManyIter, QueryCombinationIter, QueryState::par_fold_init_unchecked_manual
	/// # Safety
	/// `tables` and `archetypes` must belong to the same world that the [`QueryIterationCursor`]
	/// was initialized for.
	/// `query_state` must be the same [`QueryState`] that was passed to `init` or `init_empty`.
	#[inline(always)]
	unsafe fn next(
	&mut self,
	tables: &'w Tables,
	archetypes: &'w Archetypes,
	query_state: &'s QueryState<D, F>,
	) -> Option<D::Item<'w>> {
	if Self::IS_DENSE {
	loop {
	// we are on the beginning of the query, or finished processing a table, so skip to the next
	if self.current_row == self.current_len {
	let table_id = self.storage_id_iter.next()?.table_id;
	let table = tables.get(table_id).debug_checked_unwrap();
	// SAFETY: `table` is from the world that `fetch/filter` were created for,
	// `fetch_state`/`filter_state` are the states that `fetch/filter` were initialized with
	unsafe {
	D::set_table(&mut self.fetch, &query_state.fetch_state, table);
	F::set_table(&mut self.filter, &query_state.filter_state, table);
	}
	self.table_entities = table.entities();
	self.current_len = table.entity_count();
	self.current_row = 0;
	continue;
	}
	// SAFETY: set_table was called prior.
	// `current_row` is a table row in range of the current table, because if it was not, then the above would have been executed.
	let entity = unsafe { self.table_entities.get_unchecked(self.current_row) };
	let row = TableRow::from_usize(self.current_row);
	if !F::filter_fetch(&mut self.filter, *entity, row) {
	self.current_row += 1;
	continue;
	}
	// SAFETY:
	// - set_table was called prior.
	// - `current_row` must be a table row in range of the current table,
	// because if it was not, then the above would have been executed.
	// - fetch is only called once for each `entity`.
	let item = unsafe { D::fetch(&mut self.fetch, *entity, row) };
	self.current_row += 1;
	return Some(item);
	}
	} else {
	loop {
	if self.current_row == self.current_len {
	let archetype_id = self.storage_id_iter.next()?.archetype_id;
	let archetype = archetypes.get(archetype_id).debug_checked_unwrap();
	let table = tables.get(archetype.table_id()).debug_checked_unwrap();
	// SAFETY: `archetype` and `tables` are from the world that `fetch/filter` were created for,
	// `fetch_state`/`filter_state` are the states that `fetch/filter` were initialized with
	unsafe {
	D::set_archetype(
	&mut self.fetch,
	&query_state.fetch_state,
	archetype,
	table,
	);
	F::set_archetype(
	&mut self.filter,
	&query_state.filter_state,
	archetype,
	table,
	);
	}
	self.archetype_entities = archetype.entities();
	self.current_len = archetype.len();
	self.current_row = 0;
	continue;
	}
	// SAFETY: set_archetype was called prior.
	// `current_row` is an archetype index row in range of the current archetype, because if it was not, then the if above would have been executed.
	let archetype_entity =
	unsafe { self.archetype_entities.get_unchecked(self.current_row) };
	if !F::filter_fetch(
	&mut self.filter,
	archetype_entity.id(),
	archetype_entity.table_row(),
	) {
	self.current_row += 1;
	continue;
	}
	// SAFETY:
	// - set_archetype was called prior.
	// - `current_row` must be an archetype index row in range of the current archetype,
	// because if it was not, then the if above would have been executed.
	// - fetch is only called once for each `archetype_entity`.
	let item = unsafe {
	D::fetch(
	&mut self.fetch,
	archetype_entity.id(),
	archetype_entity.table_row(),
	)
	};
	self.current_row += 1;
	return Some(item);
	}
	}
	}
	}

[Victoronz]

Since I think it is relatively simple to do, I'll open a PR for a randomize method on QueryIter. This would return a QueryRandomIter type alias of QuerySortedIter.