search

bevyengine / bevy

A refreshingly simple data-driven game engine built in Rust
https://bevyengine.org
Apache License 2.0
33.7k stars 3.27k forks source link

Scene graph #3064

Open caperaven opened 2 years ago

caperaven commented 2 years ago

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

Fast query of objects in vicinity of a given point

What solution would you like?

Octree, quadtree ...

What alternative(s) have you considered?

None

Additional context

I am evaluating bevy for future development that requires performant graphics using wgpu on the web. An important part of that is proper culling and scene queries to determine visibility and proximity. Libraries like threejs does not come out the box with such things. I would like to understand the vision around this for bevy, please.

alice-i-cecile commented 2 years ago

So, this is a special but very important case of "indexing" (see #1205 and #1587 for some early thoughts): secondary acceleration data structures that make accessing specific entities faster.

The basic design of these in Bevy is:

  1. Create an index, stored in a resource, that records the values of interest, and allows you to quickly look up which entities are relevant. Entity is used as the key here.
  2. Carefully keep this index up to date.
  3. Use the Entity returned by your index to quickly look up the entity in question's components using World::get or Query::get.

Right now, this basically works: you can implement this yourself with whatever index you'd like to make things faster. However, steps 1 and 2 are manual (and users can create frustrating data desynchronization bugs due to lack of atomicity), and step 3 could be optimized further (see #2965 for example).

To improve the difficulties around 2, the informal ECS team has been working on designs towards a permissions model of data access, to ensure appropriate atomicity of transactions. See #2801 (and ask onthe #ecs-dev channel on Discord) for some very early thoughts on that.

Once that's firmly in place and a good extensible API is ready, we can begin the work of baking in and optimizing several common indexing strategies into Bevy itself, making it fast and easy for users to accelerate their lookups in this way,.

caperaven commented 2 years ago

It sounds like there is still a lot of thought, design and works to be done in this space. Is there any hard targets (version number) for these kinds of optimizations or is it still a bit shoot from the hip? I am very excited about the future of Bevy but it is hard for me to guage the future facing feature timelines.

Either way thank you for the feedback it is much appreciated

alice-i-cecile commented 2 years ago

Is there any hard targets (version number) for these kinds of optimizations or is it still a bit shoot from the hip?

No hard targets; we're limited to one paid full-time dev (Cart) right now, so progress is fairly organic and we've been focusing on polish for one major feature area per release. Completely unofficially, this work is likely to happen on the side by the ECS team over the next 6 months to a year.

For now, rolling your own index and manually updating it should get you the performance you need, and debug asserts will help dramatically with safety.