-
-
Notifications
You must be signed in to change notification settings - Fork 3.4k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Method to get a random entity from a query #14393
Comments
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 |
@SarthakSingh31 I'm actually really curious how Bevy works under the hood there, is there any conceptual documentation I can read about that? |
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 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 " |
@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
|
Since I think it is relatively simple to do, I'll open a PR for a |
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 getn
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 pickn
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'siter
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.
The text was updated successfully, but these errors were encountered: