docs/bevy/examples/stress_tests/transform_hierarchy.rs 16.5 K · 550 lines · raw · history

1 //! Hierarchy and transform propagation stress test.
2 //!
3 //! Running this example:
4 //!
5 //! ```
6 //! cargo r --release --example transform_hierarchy <configuration name>
7 //! ```
8 //!
9 //! | Configuration | Description |
10 //! | -------------------- | ----------------------------------------------------------------- |
11 //! | `large_tree` | A fairly wide and deep tree. |
12 //! | `wide_tree` | A shallow but very wide tree. |
13 //! | `deep_tree` | A deep but not very wide tree. |
14 //! | `chain` | A chain. 2500 levels deep. |
15 //! | `update_leaves` | Same as `large_tree`, but only leaves are updated. |
16 //! | `update_shallow` | Same as `large_tree`, but only the first few levels are updated. |
17 //! | `humanoids_active` | 4000 active humanoid rigs. |
18 //! | `humanoids_inactive` | 4000 humanoid rigs. Only 10 are active. |
19 //! | `humanoids_mixed` | 2000 active and 2000 inactive humanoid rigs. |
20
21 use bevy::{
22 diagnostic::{FrameTimeDiagnosticsPlugin, LogDiagnosticsPlugin},
23 prelude::*,
24 window::ExitCondition,
25 };
26 use rand::RngExt;
27
28 /// pre-defined test configurations with name
29 const CONFIGS: [(&str, Cfg); 9] = [
30 (
31 "large_tree",
32 Cfg {
33 test_case: TestCase::NonUniformTree {
34 depth: 18,
35 branch_width: 8,
36 },
37 update_filter: UpdateFilter {
38 probability: 0.5,
39 min_depth: 0,
40 max_depth: u32::MAX,
41 },
42 },
43 ),
44 (
45 "wide_tree",
46 Cfg {
47 test_case: TestCase::Tree {
48 depth: 3,
49 branch_width: 500,
50 },
51 update_filter: UpdateFilter {
52 probability: 0.5,
53 min_depth: 0,
54 max_depth: u32::MAX,
55 },
56 },
57 ),
58 (
59 "deep_tree",
60 Cfg {
61 test_case: TestCase::NonUniformTree {
62 depth: 25,
63 branch_width: 2,
64 },
65 update_filter: UpdateFilter {
66 probability: 0.5,
67 min_depth: 0,
68 max_depth: u32::MAX,
69 },
70 },
71 ),
72 (
73 "chain",
74 Cfg {
75 test_case: TestCase::Tree {
76 depth: 2500,
77 branch_width: 1,
78 },
79 update_filter: UpdateFilter {
80 probability: 0.5,
81 min_depth: 0,
82 max_depth: u32::MAX,
83 },
84 },
85 ),
86 (
87 "update_leaves",
88 Cfg {
89 test_case: TestCase::Tree {
90 depth: 18,
91 branch_width: 2,
92 },
93 update_filter: UpdateFilter {
94 probability: 0.5,
95 min_depth: 17,
96 max_depth: u32::MAX,
97 },
98 },
99 ),
100 (
101 "update_shallow",
102 Cfg {
103 test_case: TestCase::Tree {
104 depth: 18,
105 branch_width: 2,
106 },
107 update_filter: UpdateFilter {
108 probability: 0.5,
109 min_depth: 0,
110 max_depth: 8,
111 },
112 },
113 ),
114 (
115 "humanoids_active",
116 Cfg {
117 test_case: TestCase::Humanoids {
118 active: 4000,
119 inactive: 0,
120 },
121 update_filter: UpdateFilter {
122 probability: 1.0,
123 min_depth: 0,
124 max_depth: u32::MAX,
125 },
126 },
127 ),
128 (
129 "humanoids_inactive",
130 Cfg {
131 test_case: TestCase::Humanoids {
132 active: 10,
133 inactive: 3990,
134 },
135 update_filter: UpdateFilter {
136 probability: 1.0,
137 min_depth: 0,
138 max_depth: u32::MAX,
139 },
140 },
141 ),
142 (
143 "humanoids_mixed",
144 Cfg {
145 test_case: TestCase::Humanoids {
146 active: 2000,
147 inactive: 2000,
148 },
149 update_filter: UpdateFilter {
150 probability: 1.0,
151 min_depth: 0,
152 max_depth: u32::MAX,
153 },
154 },
155 ),
156 ];
157
158 fn print_available_configs() {
159 println!("available configurations:");
160 for (name, _) in CONFIGS {
161 println!(" {name}");
162 }
163 }
164
165 fn main() {
166 // parse cli argument and find the selected test configuration
167 let cfg: Cfg = match std::env::args().nth(1) {
168 Some(arg) => match CONFIGS.iter().find(|(name, _)| *name == arg) {
169 Some((name, cfg)) => {
170 println!("test configuration: {name}");
171 cfg.clone()
172 }
173 None => {
174 println!("test configuration \"{arg}\" not found.\n");
175 print_available_configs();
176 return;
177 }
178 },
179 None => {
180 println!("missing argument: <test configuration>\n");
181 print_available_configs();
182 return;
183 }
184 };
185
186 println!("\n{cfg:#?}");
187
188 App::new()
189 .insert_resource(cfg)
190 .add_plugins((
191 DefaultPlugins.set(WindowPlugin {
192 primary_window: None,
193 exit_condition: ExitCondition::DontExit,
194 ..default()
195 }),
196 FrameTimeDiagnosticsPlugin::default(),
197 LogDiagnosticsPlugin::default(),
198 ))
199 .add_systems(Startup, setup)
200 // Updating transforms *must* be done before `PostUpdate`
201 // or the hierarchy will momentarily be in an invalid state.
202 .add_systems(Update, update)
203 .run();
204 }
205
206 /// test configuration
207 #[derive(Resource, Debug, Clone)]
208 struct Cfg {
209 /// which test case should be inserted
210 test_case: TestCase,
211 /// which entities should be updated
212 update_filter: UpdateFilter,
213 }
214
215 #[derive(Debug, Clone)]
216 enum TestCase {
217 /// a uniform tree, exponentially growing with depth
218 Tree {
219 /// total depth
220 depth: u32,
221 /// number of children per node
222 branch_width: u32,
223 },
224 /// a non uniform tree (one side is deeper than the other)
225 /// creates significantly less nodes than `TestCase::Tree` with the same parameters
226 NonUniformTree {
227 /// the maximum depth
228 depth: u32,
229 /// max number of children per node
230 branch_width: u32,
231 },
232 /// one or multiple humanoid rigs
233 Humanoids {
234 /// number of active instances (uses the specified [`UpdateFilter`])
235 active: u32,
236 /// number of inactive instances (always inactive)
237 inactive: u32,
238 },
239 }
240
241 /// a filter to restrict which nodes are updated
242 #[derive(Debug, Clone)]
243 struct UpdateFilter {
244 /// starting depth (inclusive)
245 min_depth: u32,
246 /// end depth (inclusive)
247 max_depth: u32,
248 /// probability of a node to get updated (evaluated at insertion time, not during update)
249 /// 0 (never) .. 1 (always)
250 probability: f32,
251 }
252
253 /// update component with some per-component value
254 #[derive(Component)]
255 struct UpdateValue(f32);
256
257 /// update positions system
258 fn update(time: Res<Time>, mut query: Query<(&mut Transform, &mut UpdateValue)>) {
259 for (mut t, mut u) in &mut query {
260 u.0 += time.delta_secs() * 0.1;
261 set_translation(&mut t.translation, u.0);
262 }
263 }
264
265 /// set translation based on the angle `a`
266 fn set_translation(translation: &mut Vec3, a: f32) {
267 translation.x = ops::cos(a) * 32.0;
268 translation.y = ops::sin(a) * 32.0;
269 }
270
271 fn setup(mut commands: Commands, cfg: Res<Cfg>) {
272 warn!(include_str!("warning_string.txt"));
273
274 commands.spawn((Camera2d, Transform::from_xyz(0.0, 0.0, 100.0)));
275
276 let result = match cfg.test_case {
277 TestCase::Tree {
278 depth,
279 branch_width,
280 } => {
281 let tree = gen_tree(depth, branch_width);
282 spawn_tree(&tree, &mut commands, &cfg.update_filter, default())
283 }
284 TestCase::NonUniformTree {
285 depth,
286 branch_width,
287 } => {
288 let tree = gen_non_uniform_tree(depth, branch_width);
289 spawn_tree(&tree, &mut commands, &cfg.update_filter, default())
290 }
291 TestCase::Humanoids { active, inactive } => {
292 let mut result = InsertResult::default();
293 let mut rng = rand::rng();
294
295 for _ in 0..active {
296 result.combine(spawn_tree(
297 &HUMANOID_RIG,
298 &mut commands,
299 &cfg.update_filter,
300 Transform::from_xyz(
301 rng.random::<f32>() * 500.0 - 250.0,
302 rng.random::<f32>() * 500.0 - 250.0,
303 0.0,
304 ),
305 ));
306 }
307
308 for _ in 0..inactive {
309 result.combine(spawn_tree(
310 &HUMANOID_RIG,
311 &mut commands,
312 &UpdateFilter {
313 // force inactive by setting the probability < 0
314 probability: -1.0,
315 ..cfg.update_filter
316 },
317 Transform::from_xyz(
318 rng.random::<f32>() * 500.0 - 250.0,
319 rng.random::<f32>() * 500.0 - 250.0,
320 0.0,
321 ),
322 ));
323 }
324
325 result
326 }
327 };
328
329 println!("\n{result:#?}");
330 }
331
332 /// overview of the inserted hierarchy
333 #[derive(Default, Debug)]
334 struct InsertResult {
335 /// total number of nodes inserted
336 inserted_nodes: usize,
337 /// number of nodes that get updated each frame
338 active_nodes: usize,
339 /// maximum depth of the hierarchy tree
340 maximum_depth: usize,
341 }
342
343 impl InsertResult {
344 fn combine(&mut self, rhs: Self) -> &mut Self {
345 self.inserted_nodes += rhs.inserted_nodes;
346 self.active_nodes += rhs.active_nodes;
347 self.maximum_depth = self.maximum_depth.max(rhs.maximum_depth);
348 self
349 }
350 }
351
352 /// spawns a tree defined by a parent map (excluding root)
353 /// the parent map must be ordered (parent must exist before child)
354 fn spawn_tree(
355 parent_map: &[usize],
356 commands: &mut Commands,
357 update_filter: &UpdateFilter,
358 root_transform: Transform,
359 ) -> InsertResult {
360 // total count (# of nodes + root)
361 let count = parent_map.len() + 1;
362
363 #[derive(Default, Clone, Copy)]
364 struct NodeInfo {
365 child_count: u32,
366 depth: u32,
367 }
368
369 // node index -> entity lookup list
370 let mut ents: Vec<Entity> = Vec::with_capacity(count);
371 let mut node_info: Vec<NodeInfo> = vec![default(); count];
372 for (i, &parent_idx) in parent_map.iter().enumerate() {
373 // assert spawn order (parent must be processed before child)
374 assert!(parent_idx <= i, "invalid spawn order");
375 node_info[parent_idx].child_count += 1;
376 }
377
378 // insert root
379 ents.push(commands.spawn(root_transform).id());
380
381 let mut result = InsertResult::default();
382 let mut rng = rand::rng();
383 // used to count through the number of children (used only for visual layout)
384 let mut child_idx: Vec<u16> = vec![0; count];
385
386 // insert children
387 for (current_idx, &parent_idx) in parent_map.iter().enumerate() {
388 let current_idx = current_idx + 1;
389
390 // separation factor to visually separate children (0..1)
391 let sep = child_idx[parent_idx] as f32 / node_info[parent_idx].child_count as f32;
392 child_idx[parent_idx] += 1;
393
394 // calculate and set depth
395 // this works because it's guaranteed that we have already iterated over the parent
396 let depth = node_info[parent_idx].depth + 1;
397 let info = &mut node_info[current_idx];
398 info.depth = depth;
399
400 // update max depth of tree
401 result.maximum_depth = result.maximum_depth.max(depth.try_into().unwrap());
402
403 // insert child
404 let child_entity = {
405 let mut cmd = commands.spawn_empty();
406
407 // check whether or not to update this node
408 let update = (rng.random::<f32>() <= update_filter.probability)
409 && (depth >= update_filter.min_depth && depth <= update_filter.max_depth);
410
411 if update {
412 cmd.insert(UpdateValue(sep));
413 result.active_nodes += 1;
414 }
415
416 let transform = {
417 let mut translation = Vec3::ZERO;
418 // use the same placement fn as the `update` system
419 // this way the entities won't be all at (0, 0, 0) when they don't have an `Update` component
420 set_translation(&mut translation, sep);
421 Transform::from_translation(translation)
422 };
423
424 // only insert the components necessary for the transform propagation
425 cmd.insert(transform);
426
427 cmd.id()
428 };
429
430 commands.entity(ents[parent_idx]).add_child(child_entity);
431
432 ents.push(child_entity);
433 }
434
435 result.inserted_nodes = ents.len();
436 result
437 }
438
439 /// generate a tree `depth` levels deep, where each node has `branch_width` children
440 fn gen_tree(depth: u32, branch_width: u32) -> Vec<usize> {
441 // calculate the total count of branches
442 let mut count: usize = 0;
443 for i in 0..(depth - 1) {
444 count += TryInto::<usize>::try_into(branch_width.pow(i)).unwrap();
445 }
446
447 // the tree is built using this pattern:
448 // 0, 0, 0, ... 1, 1, 1, ... 2, 2, 2, ... (count - 1)
449 (0..count)
450 .flat_map(|i| std::iter::repeat_n(i, branch_width.try_into().unwrap()))
451 .collect()
452 }
453
454 /// recursive part of [`gen_non_uniform_tree`]
455 fn add_children_non_uniform(
456 tree: &mut Vec<usize>,
457 parent: usize,
458 mut curr_depth: u32,
459 max_branch_width: u32,
460 ) {
461 for _ in 0..max_branch_width {
462 tree.push(parent);
463
464 curr_depth = curr_depth.checked_sub(1).unwrap();
465 if curr_depth == 0 {
466 return;
467 }
468 add_children_non_uniform(tree, tree.len(), curr_depth, max_branch_width);
469 }
470 }
471
472 /// generate a tree that has more nodes on one side that the other
473 /// the deepest hierarchy path is `max_depth` and the widest branches have `max_branch_width` children
474 fn gen_non_uniform_tree(max_depth: u32, max_branch_width: u32) -> Vec<usize> {
475 let mut tree = Vec::new();
476 add_children_non_uniform(&mut tree, 0, max_depth, max_branch_width);
477 tree
478 }
479
480 /// parent map for a decently complex humanoid rig (based on mixamo rig)
481 const HUMANOID_RIG: [usize; 67] = [
482 // (0: root)
483 0, // 1: hips
484 1, // 2: spine
485 2, // 3: spine 1
486 3, // 4: spine 2
487 4, // 5: neck
488 5, // 6: head
489 6, // 7: head top
490 6, // 8: left eye
491 6, // 9: right eye
492 4, // 10: left shoulder
493 10, // 11: left arm
494 11, // 12: left forearm
495 12, // 13: left hand
496 13, // 14: left hand thumb 1
497 14, // 15: left hand thumb 2
498 15, // 16: left hand thumb 3
499 16, // 17: left hand thumb 4
500 13, // 18: left hand index 1
501 18, // 19: left hand index 2
502 19, // 20: left hand index 3
503 20, // 21: left hand index 4
504 13, // 22: left hand middle 1
505 22, // 23: left hand middle 2
506 23, // 24: left hand middle 3
507 24, // 25: left hand middle 4
508 13, // 26: left hand ring 1
509 26, // 27: left hand ring 2
510 27, // 28: left hand ring 3
511 28, // 29: left hand ring 4
512 13, // 30: left hand pinky 1
513 30, // 31: left hand pinky 2
514 31, // 32: left hand pinky 3
515 32, // 33: left hand pinky 4
516 4, // 34: right shoulder
517 34, // 35: right arm
518 35, // 36: right forearm
519 36, // 37: right hand
520 37, // 38: right hand thumb 1
521 38, // 39: right hand thumb 2
522 39, // 40: right hand thumb 3
523 40, // 41: right hand thumb 4
524 37, // 42: right hand index 1
525 42, // 43: right hand index 2
526 43, // 44: right hand index 3
527 44, // 45: right hand index 4
528 37, // 46: right hand middle 1
529 46, // 47: right hand middle 2
530 47, // 48: right hand middle 3
531 48, // 49: right hand middle 4
532 37, // 50: right hand ring 1
533 50, // 51: right hand ring 2
534 51, // 52: right hand ring 3
535 52, // 53: right hand ring 4
536 37, // 54: right hand pinky 1
537 54, // 55: right hand pinky 2
538 55, // 56: right hand pinky 3
539 56, // 57: right hand pinky 4
540 1, // 58: left upper leg
541 58, // 59: left leg
542 59, // 60: left foot
543 60, // 61: left toe base
544 61, // 62: left toe end
545 1, // 63: right upper leg
546 63, // 64: right leg
547 64, // 65: right foot
548 65, // 66: right toe base
549 66, // 67: right toe end
550 ];