veloren_world/layer/
tree.rs

1use crate::{
2    Canvas, CanvasInfo, ColumnSample,
3    all::*,
4    block::block_from_structure,
5    column::ColumnGen,
6    layer::cave::tunnel_bounds_at,
7    util::{RandomPerm, Sampler, UnitChooser, gen_cache::StructureGenCache},
8};
9use common::{
10    assets::AssetHandle,
11    calendar::{Calendar, CalendarEvent},
12    terrain::{
13        Block, BlockKind, SpriteKind,
14        structure::{Structure, StructureBlock, StructuresGroup},
15    },
16    vol::ReadVol,
17};
18use lazy_static::lazy_static;
19use rand::prelude::*;
20use std::{f32, ops::Range};
21use vek::*;
22
23lazy_static! {
24    static ref OAK_STUMPS: AssetHandle<StructuresGroup> = Structure::load_group("trees.oak_stumps");
25    static ref PALMS: AssetHandle<StructuresGroup> = Structure::load_group("trees.palms");
26    static ref FRUIT_TREES: AssetHandle<StructuresGroup> =
27        Structure::load_group("trees.fruit_trees");
28    static ref BIRCHES: AssetHandle<StructuresGroup> = Structure::load_group("trees.birch");
29    static ref SWAMP_TREES: AssetHandle<StructuresGroup> =
30        Structure::load_group("trees.swamp_trees");
31}
32
33static MODEL_RAND: RandomPerm = RandomPerm::new(0xDB21C052);
34static UNIT_CHOOSER: UnitChooser = UnitChooser::new(0x700F4EC7);
35static QUIRKY_RAND: RandomPerm = RandomPerm::new(0xA634460F);
36
37// Ensure that it's valid to place a tree here
38pub fn tree_valid_at(
39    wpos: Vec2<i32>,
40    col: &ColumnSample,
41    info: Option<CanvasInfo<'_>>,
42    seed: u32,
43) -> bool {
44    if col.alt < col.water_level
45        || col.spawn_rate < 0.9
46        || col.water_dist.map(|d| d < 8.0).unwrap_or(false)
47        || col.path.map(|(d, _, _, _)| d < 12.0).unwrap_or(false)
48        || info.is_some_and(|info| {
49            tunnel_bounds_at(wpos, &info, &info.land())
50                .any(|(_, z_range, _, _, _, _)| z_range.contains(&(col.alt as i32 - 2)))
51        })
52    {
53        return false;
54    }
55
56    if ((seed.wrapping_mul(13)) & 0xFF) as f32 / 256.0 > col.tree_density {
57        return false;
58    }
59
60    true
61}
62
63pub fn apply_trees_to(
64    canvas: &mut Canvas,
65    dynamic_rng: &mut impl Rng,
66    calendar: Option<&Calendar>,
67) {
68    // TODO: Get rid of this
69    #[expect(clippy::large_enum_variant)]
70    enum TreeModel {
71        Structure(Structure),
72        Procedural(ProceduralTree),
73    }
74
75    struct Tree {
76        pos: Vec3<i32>,
77        model: TreeModel,
78        leaf_block: StructureBlock,
79        seed: u32,
80        units: (Vec2<i32>, Vec2<i32>),
81        lights: bool,
82    }
83
84    let info = canvas.info();
85    let mut tree_cache = StructureGenCache::new(info.chunks().gen_ctx.structure_gen.clone());
86
87    canvas.foreach_col(|canvas, wpos2d, col| {
88        let trees = tree_cache.get(wpos2d, |wpos, seed| {
89            let scale = 1.0;
90            let inhabited = false;
91            let forest_kind = *info
92                .chunks()
93                .make_forest_lottery(wpos)
94                .choose_seeded(seed)
95                .as_ref()?;
96
97            let col = ColumnGen::new(info.chunks()).get((wpos, info.index(), calendar))?;
98
99            let crowding = col.tree_density;
100
101            if !tree_valid_at(wpos, &col, Some(info), seed) {
102                return None;
103            }
104
105            Some(Tree {
106                pos: Vec3::new(wpos.x, wpos.y, col.alt as i32),
107                model: 'model: {
108                    let models: AssetHandle<_> = match forest_kind {
109                        ForestKind::Oak if QUIRKY_RAND.chance(seed + 1, 1.0 / 16.0) => *OAK_STUMPS,
110                        ForestKind::Oak if QUIRKY_RAND.chance(seed + 2, 1.0 / 20.0) => {
111                            break 'model TreeModel::Procedural(ProceduralTree::generate(
112                                TreeConfig::apple(&mut RandomPerm::new(seed), scale),
113                                &mut RandomPerm::new(seed),
114                            ));
115                        },
116                        ForestKind::Palm => *PALMS,
117                        ForestKind::Acacia => {
118                            break 'model TreeModel::Procedural(ProceduralTree::generate(
119                                TreeConfig::acacia(&mut RandomPerm::new(seed), scale),
120                                &mut RandomPerm::new(seed),
121                            ));
122                        },
123                        ForestKind::Baobab => {
124                            break 'model TreeModel::Procedural(ProceduralTree::generate(
125                                TreeConfig::baobab(&mut RandomPerm::new(seed), scale),
126                                &mut RandomPerm::new(seed),
127                            ));
128                        },
129                        ForestKind::Oak => {
130                            break 'model TreeModel::Procedural(ProceduralTree::generate(
131                                TreeConfig::oak(&mut RandomPerm::new(seed), scale, crowding),
132                                &mut RandomPerm::new(seed),
133                            ));
134                        },
135                        ForestKind::Dead => {
136                            break 'model TreeModel::Procedural(ProceduralTree::generate(
137                                TreeConfig::dead(&mut RandomPerm::new(seed), scale),
138                                &mut RandomPerm::new(seed),
139                            ));
140                        },
141                        ForestKind::Chestnut => {
142                            break 'model TreeModel::Procedural(ProceduralTree::generate(
143                                TreeConfig::chestnut(&mut RandomPerm::new(seed), scale, crowding),
144                                &mut RandomPerm::new(seed),
145                            ));
146                        },
147                        ForestKind::Pine => {
148                            break 'model TreeModel::Procedural(ProceduralTree::generate(
149                                TreeConfig::pine(&mut RandomPerm::new(seed), scale, calendar),
150                                &mut RandomPerm::new(seed),
151                            ));
152                        },
153                        ForestKind::Cedar => {
154                            break 'model TreeModel::Procedural(ProceduralTree::generate(
155                                TreeConfig::cedar(&mut RandomPerm::new(seed), scale),
156                                &mut RandomPerm::new(seed),
157                            ));
158                        },
159                        ForestKind::Redwood => {
160                            break 'model TreeModel::Procedural(ProceduralTree::generate(
161                                TreeConfig::redwood(&mut RandomPerm::new(seed), scale),
162                                &mut RandomPerm::new(seed),
163                            ));
164                        },
165                        ForestKind::Birch => {
166                            break 'model TreeModel::Procedural(ProceduralTree::generate(
167                                TreeConfig::birch(&mut RandomPerm::new(seed), scale),
168                                &mut RandomPerm::new(seed),
169                            ));
170                        },
171                        ForestKind::Frostpine => {
172                            break 'model TreeModel::Procedural(ProceduralTree::generate(
173                                TreeConfig::frostpine(&mut RandomPerm::new(seed), scale),
174                                &mut RandomPerm::new(seed),
175                            ));
176                        },
177
178                        ForestKind::Mangrove => {
179                            break 'model TreeModel::Procedural(ProceduralTree::generate(
180                                TreeConfig::jungle(&mut RandomPerm::new(seed), scale),
181                                &mut RandomPerm::new(seed),
182                            ));
183                        },
184                        ForestKind::Swamp => *SWAMP_TREES,
185                        ForestKind::Giant => {
186                            break 'model TreeModel::Procedural(ProceduralTree::generate(
187                                TreeConfig::giant(&mut RandomPerm::new(seed), scale, inhabited),
188                                &mut RandomPerm::new(seed),
189                            ));
190                        },
191                        ForestKind::Mapletree => {
192                            break 'model TreeModel::Procedural(ProceduralTree::generate(
193                                TreeConfig::oak(&mut RandomPerm::new(seed), scale, crowding),
194                                &mut RandomPerm::new(seed),
195                            ));
196                        },
197                        ForestKind::Cherry => {
198                            break 'model TreeModel::Procedural(ProceduralTree::generate(
199                                TreeConfig::cherry(&mut RandomPerm::new(seed), scale),
200                                &mut RandomPerm::new(seed),
201                            ));
202                        },
203                        ForestKind::AutumnTree => {
204                            break 'model TreeModel::Procedural(ProceduralTree::generate(
205                                TreeConfig::oak(&mut RandomPerm::new(seed), scale, crowding),
206                                &mut RandomPerm::new(seed),
207                            ));
208                        },
209                    };
210
211                    let models = models.read();
212                    TreeModel::Structure(
213                        models
214                            [(MODEL_RAND.get(seed.wrapping_mul(17)) / 13) as usize % models.len()]
215                        .clone(),
216                    )
217                },
218                leaf_block: forest_kind.leaf_block(),
219                seed,
220                units: UNIT_CHOOSER.get(seed),
221                lights: inhabited,
222            })
223        });
224
225        for tree in trees {
226            let bounds = match &tree.model {
227                TreeModel::Structure(s) => s.get_bounds(),
228                TreeModel::Procedural(t) => t.get_bounds().map(|e| e as i32),
229            };
230
231            let rpos2d = (wpos2d - tree.pos.xy())
232                .map2(Vec2::new(tree.units.0, tree.units.1), |p, unit| unit * p)
233                .sum();
234            if !Aabr::from(bounds).contains_point(rpos2d) {
235                // Skip this column
236                continue;
237            }
238
239            let hanging_sprites = match &tree.model {
240                TreeModel::Structure(_) => [(0.0004, SpriteKind::Beehive)].as_ref(),
241                TreeModel::Procedural(t) => t.config.hanging_sprites,
242            };
243
244            let mut is_top = true;
245            let mut is_leaf_top = true;
246            let mut last_block = Block::empty();
247            for z in (bounds.min.z..bounds.max.z).rev() {
248                let wpos = Vec3::new(wpos2d.x, wpos2d.y, tree.pos.z + z);
249                let model_pos = Vec3::from(
250                    (wpos - tree.pos)
251                        .xy()
252                        .map2(Vec2::new(tree.units.0, tree.units.1), |rpos, unit| {
253                            unit * rpos
254                        })
255                        .sum(),
256                ) + Vec3::unit_z() * (wpos.z - tree.pos.z);
257                let sblock;
258                block_from_structure(
259                    info.index(),
260                    if let Some(block) = match &tree.model {
261                        TreeModel::Structure(s) => s.get(model_pos).ok(),
262                        TreeModel::Procedural(t) => Some(
263                            match t.is_branch_or_leaves_at(model_pos.map(|e| e as f32 + 0.5)) {
264                                (_, _, true, _) => {
265                                    sblock = StructureBlock::Filled(
266                                        BlockKind::Wood,
267                                        Rgb::new(150, 98, 41),
268                                    );
269                                    &sblock
270                                },
271                                (_, _, _, true) => &StructureBlock::None,
272                                (true, _, _, _) => &t.config.trunk_block,
273                                (_, true, _, _) => &tree.leaf_block,
274                                _ => &StructureBlock::None,
275                            },
276                        ),
277                    } {
278                        block
279                    } else {
280                        break;
281                    },
282                    wpos,
283                    tree.pos.xy(),
284                    tree.seed,
285                    col,
286                    Block::air,
287                    calendar,
288                    &Vec2::new(tree.units.0, tree.units.1),
289                )
290                .map(|(block, sprite_cfg)| {
291                    // Add lights to the tree
292                    if tree.lights
293                        && last_block.is_air()
294                        && block.kind() == BlockKind::Wood
295                        && dynamic_rng.gen_range(0..256) == 0
296                    {
297                        canvas.set(wpos + Vec3::unit_z(), Block::air(SpriteKind::Lantern));
298                        // Add a snow covering to the block above under certain
299                        // circumstances
300                    } else if col.snow_cover
301                        && ((block.kind() == BlockKind::Leaves && is_leaf_top)
302                            || (is_top && block.is_filled()))
303                    {
304                        canvas.set(
305                            wpos + Vec3::unit_z(),
306                            Block::new(BlockKind::Snow, Rgb::new(210, 210, 255)),
307                        );
308                    }
309                    canvas.set(wpos, block);
310                    if let Some(sprite_cfg) = sprite_cfg {
311                        canvas.set_sprite_cfg(wpos, sprite_cfg);
312                    }
313                    is_leaf_top = false;
314                    is_top = false;
315                    last_block = block;
316                })
317                .unwrap_or_else(|| {
318                    // Hanging sprites
319                    if last_block.is_filled() {
320                        for (chance, sprite) in hanging_sprites {
321                            if dynamic_rng.gen_bool(*chance as f64) {
322                                canvas.map_resource(wpos, |block| block.with_sprite(*sprite));
323                            }
324                        }
325                    }
326
327                    is_leaf_top = true;
328                    last_block = Block::empty();
329                });
330            }
331        }
332    });
333}
334
335/// A type that specifies the generation properties of a tree.
336#[derive(Clone)]
337pub struct TreeConfig {
338    /// Length of trunk, also scales other branches.
339    pub trunk_len: f32,
340    /// Radius of trunk, also scales other branches.
341    pub trunk_radius: f32,
342    /// The scale that child branch lengths should be compared to their parents.
343    pub branch_child_len: f32,
344    /// The scale that child branch radii should be compared to their parents.
345    pub branch_child_radius: f32,
346    /// Whether the child of a branch has its radius lerped to its parent.
347    pub branch_child_radius_lerp: bool,
348    /// The range of radii that leaf-emitting branches might have.
349    pub leaf_radius: Range<f32>,
350    /// An additional leaf radius that may be scaled with proportion along the
351    /// parent and `branch_len_bias`.
352    pub leaf_radius_scaled: f32,
353    /// 0 - 1 (0 = chaotic, 1 = straight).
354    pub straightness: f32,
355    /// Maximum number of branch layers (not including trunk).
356    pub max_depth: usize,
357    /// The number of branches that form from each branch.
358    pub splits: Range<f32>,
359    /// The range of proportions along a branch at which a split into another
360    /// branch might occur. This value is clamped between 0 and 1, but a
361    /// wider range may bias the results towards branch ends.
362    pub split_range: Range<f32>,
363    /// The bias applied to the length of branches based on the proportion along
364    /// their parent that they eminate from. -1.0 = negative bias (branches
365    /// at ends are longer, branches at the start are shorter) 0.0 = no bias
366    /// (branches do not change their length with regard to parent branch
367    /// proportion) 1.0 = positive bias (branches at ends are shorter,
368    /// branches at the start are longer)
369    pub branch_len_bias: f32,
370    /// The scale of leaves in the vertical plane. Less than 1.0 implies a
371    /// flattening of the leaves.
372    pub leaf_vertical_scale: f32,
373    /// How evenly spaced (vs random) sub-branches are along their parent.
374    pub proportionality: f32,
375    /// Whether the tree is inhabited (adds various features and effects)
376    pub inhabited: bool,
377    pub hanging_sprites: &'static [(f32, SpriteKind)],
378    /// The colour of branches and the trunk.
379    pub trunk_block: StructureBlock,
380}
381
382impl TreeConfig {
383    pub fn oak(rng: &mut impl Rng, scale: f32, crowding: f32) -> Self {
384        let scale = scale * (0.8 + rng.gen::<f32>().powi(2) * 0.5);
385        let log_scale = 1.0 + scale.log2().max(0.0);
386
387        Self {
388            trunk_len: 11.0 * scale,
389            trunk_radius: 1.5 * scale,
390            branch_child_len: 0.75,
391            branch_child_radius: 0.75,
392            branch_child_radius_lerp: true,
393            leaf_radius: 2.0 * log_scale..2.5 * log_scale,
394            leaf_radius_scaled: 0.0,
395            straightness: 0.3 + crowding * 0.3,
396            max_depth: 4,
397            splits: 4.25..6.25,
398            split_range: 0.75..1.5,
399            branch_len_bias: 0.0,
400            leaf_vertical_scale: 1.0,
401            proportionality: 0.0,
402            inhabited: false,
403            hanging_sprites: &[(0.0002, SpriteKind::Apple), (0.00007, SpriteKind::Beehive)],
404            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(90, 45, 15)),
405        }
406    }
407
408    pub fn dead(rng: &mut impl Rng, scale: f32) -> Self {
409        let scale = scale * (0.8 + rng.gen::<f32>().powi(2) * 0.5);
410
411        Self {
412            trunk_len: 9.0 * scale,
413            trunk_radius: 2.0 * scale,
414            branch_child_len: 0.9,
415            branch_child_radius: 0.7,
416            branch_child_radius_lerp: true,
417            leaf_radius: 0.0..0.1,
418            leaf_radius_scaled: 0.0,
419            straightness: 0.35,
420            max_depth: 3,
421            splits: 2.25..3.25,
422            split_range: 0.75..1.5,
423            branch_len_bias: 0.0,
424            leaf_vertical_scale: 1.0,
425            proportionality: 0.0,
426            inhabited: false,
427            hanging_sprites: &[(0.0002, SpriteKind::Apple), (0.00007, SpriteKind::Beehive)],
428            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(55, 34, 32)),
429        }
430    }
431
432    pub fn apple(rng: &mut impl Rng, scale: f32) -> Self {
433        let scale = scale * (0.8 + rng.gen::<f32>().powi(2) * 0.5);
434        let log_scale = 1.0 + scale.log2().max(0.0);
435
436        Self {
437            trunk_len: 3.0 * scale,
438            trunk_radius: 1.5 * scale,
439            branch_child_len: 0.9,
440            branch_child_radius: 0.9,
441            branch_child_radius_lerp: true,
442            leaf_radius: 2.0 * log_scale..3.0 * log_scale,
443            leaf_radius_scaled: 0.0,
444            straightness: 0.4,
445            max_depth: 6,
446            splits: 1.0..3.0,
447            split_range: 0.5..2.0,
448            branch_len_bias: 0.0,
449            leaf_vertical_scale: 0.7,
450            proportionality: 0.0,
451            inhabited: false,
452            hanging_sprites: &[(0.03, SpriteKind::Apple), (0.007, SpriteKind::Beehive)],
453            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(90, 45, 15)),
454        }
455    }
456
457    pub fn frostpine(rng: &mut impl Rng, scale: f32) -> Self {
458        let scale = scale * (0.8 + rng.gen::<f32>().powi(2) * 0.5);
459        let log_scale = 1.0 + scale.log2().max(0.0);
460
461        Self {
462            trunk_len: 36.0 * scale,
463            trunk_radius: 2.3 * scale,
464            branch_child_len: 0.25 / scale,
465            branch_child_radius: 0.0,
466            branch_child_radius_lerp: false,
467            leaf_radius: 1.3..2.2,
468            leaf_radius_scaled: 0.4 * log_scale,
469            straightness: 0.3,
470            max_depth: 1,
471            splits: 34.0 * scale..35.0 * scale,
472            split_range: 0.1..1.2,
473            branch_len_bias: 0.75,
474            leaf_vertical_scale: 0.6,
475            proportionality: 1.0,
476            inhabited: false,
477            hanging_sprites: &[(0.0001, SpriteKind::Beehive)],
478            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(79, 102, 105)),
479        }
480    }
481
482    pub fn jungle(rng: &mut impl Rng, scale: f32) -> Self {
483        let scale = scale * (0.8 + rng.gen::<f32>() * 0.5);
484        let log_scale = 1.0 + scale.log2().max(0.0);
485
486        Self {
487            trunk_len: 44.0 * scale,
488            trunk_radius: 2.25 * scale,
489            branch_child_len: 0.35,
490            branch_child_radius: 0.5,
491            branch_child_radius_lerp: true,
492            leaf_radius: 10.0 * log_scale..11.5 * log_scale,
493            leaf_radius_scaled: -8.0 * log_scale,
494            straightness: 0.2,
495            max_depth: 2,
496            splits: 7.5..8.5,
497            split_range: 0.2..1.25,
498            branch_len_bias: 0.5,
499            leaf_vertical_scale: 0.35,
500            proportionality: 0.8,
501            inhabited: false,
502            hanging_sprites: &[(0.00007, SpriteKind::Beehive), (0.015, SpriteKind::Liana)],
503
504            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(69, 62, 43)),
505        }
506    }
507
508    pub fn baobab(rng: &mut impl Rng, scale: f32) -> Self {
509        let scale = scale * (0.5 + rng.gen::<f32>().powi(4) * 1.0);
510        let log_scale = 1.0 + scale.log2().max(0.0);
511
512        Self {
513            trunk_len: 24.0 * scale,
514            trunk_radius: 7.0 * scale,
515            branch_child_len: 0.55,
516            branch_child_radius: 0.3,
517            branch_child_radius_lerp: true,
518            leaf_radius: 2.5 * log_scale..3.0 * log_scale,
519            leaf_radius_scaled: 0.0,
520            straightness: 0.5,
521            max_depth: 4,
522            splits: 3.0..3.5,
523            split_range: 0.95..1.0,
524            branch_len_bias: 0.0,
525            leaf_vertical_scale: 0.2,
526            proportionality: 1.0,
527            inhabited: false,
528            hanging_sprites: &[(0.00007, SpriteKind::Beehive)],
529            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(125, 60, 6)),
530        }
531    }
532
533    pub fn cedar(rng: &mut impl Rng, scale: f32) -> Self {
534        let scale = scale * (0.8 + rng.gen::<f32>().powi(2) * 0.5);
535        let log_scale = 1.0 + scale.log2().max(0.0);
536
537        Self {
538            trunk_len: 45.0 * scale,
539            trunk_radius: 1.3 * scale,
540            branch_child_len: 0.4,
541            branch_child_radius: 0.6,
542            branch_child_radius_lerp: true,
543            leaf_radius: 2.0 * log_scale..2.5 * log_scale,
544            leaf_radius_scaled: 0.0,
545            straightness: 0.3,
546            max_depth: 2,
547            splits: 16.0..18.0,
548            split_range: 0.2..1.2,
549            branch_len_bias: 0.7,
550            leaf_vertical_scale: 0.3,
551            proportionality: 0.7,
552            inhabited: false,
553            hanging_sprites: &[(0.00007, SpriteKind::Beehive)],
554            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(110, 68, 65)),
555        }
556    }
557
558    pub fn birch(rng: &mut impl Rng, scale: f32) -> Self {
559        let scale = scale * (0.8 + rng.gen::<f32>().powi(2) * 0.5);
560        let log_scale = 1.0 + scale.log2().max(0.0);
561
562        Self {
563            trunk_len: 24.0 * scale,
564            trunk_radius: 1.2 * scale,
565            branch_child_len: 0.4,
566            branch_child_radius: 0.75,
567            branch_child_radius_lerp: true,
568            leaf_radius: 4.0 * log_scale..5.0 * log_scale,
569            leaf_radius_scaled: 0.0,
570            straightness: 0.6,
571            max_depth: 4,
572            splits: 1.75..2.5,
573            split_range: 0.6..1.2,
574            branch_len_bias: 0.0,
575            leaf_vertical_scale: 0.5,
576            proportionality: 0.0,
577            inhabited: false,
578            hanging_sprites: &[(0.00007, SpriteKind::Beehive)],
579            trunk_block: StructureBlock::BirchWood,
580        }
581    }
582
583    pub fn acacia(rng: &mut impl Rng, scale: f32) -> Self {
584        let scale = scale * (0.9 + rng.gen::<f32>().powi(4) * 0.75);
585        let log_scale = 1.0 + scale.log2().max(0.0);
586
587        Self {
588            trunk_len: 7.5 * scale,
589            trunk_radius: 1.5 * scale,
590            branch_child_len: 0.75,
591            branch_child_radius: 0.75,
592            branch_child_radius_lerp: true,
593            leaf_radius: 4.5 * log_scale..5.5 * log_scale,
594            leaf_radius_scaled: 0.0,
595            straightness: 0.4,
596            max_depth: 5,
597            splits: 1.75..2.25,
598            split_range: 1.0..1.25,
599            branch_len_bias: 0.0,
600            leaf_vertical_scale: 0.2,
601            proportionality: 1.0,
602            inhabited: false,
603            hanging_sprites: &[(0.00005, SpriteKind::Beehive)],
604            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(150, 95, 65)),
605        }
606    }
607
608    pub fn chestnut(rng: &mut impl Rng, scale: f32, crowding: f32) -> Self {
609        let scale = scale * (0.85 + rng.gen::<f32>().powi(4) * 0.3);
610        let log_scale = 1.0 + scale.log2().max(0.0);
611
612        Self {
613            trunk_len: 13.0 * scale,
614            trunk_radius: 1.65 * scale,
615            branch_child_len: 0.75,
616            branch_child_radius: 0.6,
617            branch_child_radius_lerp: true,
618            leaf_radius: 1.5 * log_scale..2.0 * log_scale,
619            leaf_radius_scaled: 0.0,
620            straightness: 0.25 + crowding * 0.2,
621            max_depth: 5,
622            splits: 3.5..4.25,
623            split_range: 0.5..1.25,
624            branch_len_bias: 0.0,
625            leaf_vertical_scale: 0.65,
626            proportionality: 0.5,
627            inhabited: false,
628            hanging_sprites: &[(0.00007, SpriteKind::Beehive)],
629            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(110, 42, 28)),
630        }
631    }
632
633    pub fn pine(rng: &mut impl Rng, scale: f32, calendar: Option<&Calendar>) -> Self {
634        let scale = scale * (1.0 + rng.gen::<f32>().powi(4) * 0.5);
635        let log_scale = 1.0 + scale.log2().max(0.0);
636
637        Self {
638            trunk_len: 32.0 * scale,
639            trunk_radius: 1.25 * scale,
640            branch_child_len: 0.3 / scale,
641            branch_child_radius: 0.0,
642            branch_child_radius_lerp: false,
643            leaf_radius: 1.9..2.1,
644            leaf_radius_scaled: 1.5 * log_scale,
645            straightness: -0.25,
646            max_depth: 1,
647            splits: 34.0 * scale..35.0 * scale,
648            split_range: 0.2..1.2,
649            branch_len_bias: 0.75,
650            leaf_vertical_scale: 0.3,
651            proportionality: 1.0,
652            inhabited: false,
653            hanging_sprites: if calendar.is_some_and(|c| c.is_event(CalendarEvent::Christmas)) {
654                &[(0.0001, SpriteKind::Beehive), (0.01, SpriteKind::Orb)]
655            } else {
656                &[(0.0001, SpriteKind::Beehive)]
657            },
658            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(90, 35, 15)),
659        }
660    }
661
662    pub fn redwood(rng: &mut impl Rng, scale: f32) -> Self {
663        let scale = scale * (1.0 + rng.gen::<f32>().powi(4) * 0.5);
664
665        Self {
666            trunk_len: 80.0 * scale,
667            trunk_radius: 2.75 * scale,
668            branch_child_len: 0.25,
669            branch_child_radius: 0.3,
670            branch_child_radius_lerp: false,
671            leaf_radius: 1.3..1.5,
672            leaf_radius_scaled: 0.0,
673            straightness: -0.3,
674            max_depth: 2,
675            splits: 45.0 * scale..50.0 * scale,
676            split_range: 0.4..1.2,
677            branch_len_bias: 0.75,
678            leaf_vertical_scale: 0.6,
679            proportionality: 1.0,
680            inhabited: false,
681            hanging_sprites: &[(0.001, SpriteKind::Beehive)],
682            trunk_block: StructureBlock::RedwoodWood,
683        }
684    }
685
686    pub fn giant(_rng: &mut impl Rng, scale: f32, inhabited: bool) -> Self {
687        let log_scale = 1.0 + scale.log2().max(0.0);
688
689        Self {
690            trunk_len: 11.0 * scale,
691            trunk_radius: 6.0 * scale,
692            branch_child_len: 0.9,
693            branch_child_radius: 0.75,
694            branch_child_radius_lerp: true,
695            leaf_radius: 2.5 * scale..3.75 * scale,
696            leaf_radius_scaled: 0.0,
697            straightness: 0.36,
698            max_depth: (7.0 + log_scale) as usize,
699            splits: 1.5..2.5,
700            split_range: 1.0..1.1,
701            branch_len_bias: 0.0,
702            leaf_vertical_scale: 0.6,
703            proportionality: 0.0,
704            inhabited,
705            hanging_sprites: &[(0.00025, SpriteKind::Apple), (0.00025, SpriteKind::Beehive)],
706            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(110, 68, 22)),
707        }
708    }
709
710    pub fn cherry(rng: &mut impl Rng, scale: f32) -> Self {
711        let scale = scale * (0.8 + rng.gen::<f32>().powi(2) * 0.5);
712        let log_scale = 1.0 + scale.log2().max(0.0);
713
714        Self {
715            trunk_len: 7.0 * scale,
716            trunk_radius: 1.27 * scale,
717            branch_child_len: 0.9,
718            branch_child_radius: 0.70,
719            branch_child_radius_lerp: true,
720            leaf_radius: 2.5 * log_scale..3.0 * log_scale,
721            leaf_radius_scaled: 0.0,
722            straightness: 0.55,
723            max_depth: 4,
724            splits: 2.0..3.0,
725            split_range: 0.75..1.3,
726            branch_len_bias: 0.0,
727            leaf_vertical_scale: 1.0,
728            proportionality: 0.0,
729            inhabited: false,
730            hanging_sprites: &[],
731            trunk_block: StructureBlock::Filled(BlockKind::Wood, Rgb::new(69, 37, 17)),
732        }
733    }
734}
735
736// TODO: Rename this to `Tree` when the name conflict is gone
737pub struct ProceduralTree {
738    branches: Vec<Branch>,
739    trunk_idx: usize,
740    config: TreeConfig,
741    roots: Vec<Root>,
742    root_aabb: Aabb<f32>,
743}
744
745impl ProceduralTree {
746    /// Generate a new tree using the given configuration and seed.
747    pub fn generate(config: TreeConfig, rng: &mut impl Rng) -> Self {
748        let mut this = Self {
749            branches: Vec::new(),
750            trunk_idx: 0, // Gets replaced later
751            config: config.clone(),
752            roots: Vec::new(),
753            root_aabb: Aabb::new_empty(Vec3::zero()),
754        };
755
756        // Make the roots visible a little
757        let trunk_origin = Vec3::unit_z() * (config.trunk_radius * 0.25 + 3.0);
758
759        // Add the tree trunk (and sub-branches) recursively
760        let (trunk_idx, _) = this.add_branch(
761            &config,
762            // Our trunk starts at the origin...
763            trunk_origin,
764            // ...and has a roughly upward direction
765            Vec3::new(rng.gen_range(-1.0..1.0), rng.gen_range(-1.0..1.0), 10.0).normalized(),
766            config.trunk_len,
767            config.trunk_radius,
768            0,
769            None,
770            1.0,
771            rng,
772        );
773        this.trunk_idx = trunk_idx;
774
775        // Add roots
776        let mut root_aabb = Aabb::new_empty(Vec3::zero());
777        for _ in 0..4 {
778            let dir =
779                Vec3::new(rng.gen_range(-1.0..1.0), rng.gen_range(-1.0..1.0), -1.0).normalized();
780            let len = config.trunk_len * 0.75;
781            let radius = config.trunk_radius;
782            let mut aabb = Aabb {
783                min: trunk_origin,
784                max: trunk_origin + dir * len,
785            }
786            .made_valid();
787            aabb.min -= radius;
788            aabb.max += radius;
789
790            root_aabb.expand_to_contain(aabb);
791
792            this.roots.push(Root {
793                line: LineSegment3 {
794                    start: trunk_origin,
795                    end: trunk_origin + dir * 10.0,
796                },
797                radius,
798            });
799        }
800
801        this.root_aabb = root_aabb;
802
803        this
804    }
805
806    // Recursively add a branch (with sub-branches) to the tree's branch graph,
807    // returning the index and AABB of the branch. This AABB gets propagated
808    // down to the parent and is used later during sampling to cull the branches to
809    // be sampled.
810    fn add_branch(
811        &mut self,
812        config: &TreeConfig,
813        start: Vec3<f32>,
814        dir: Vec3<f32>,
815        branch_len: f32,
816        branch_radius: f32,
817        depth: usize,
818        sibling_idx: Option<usize>,
819        proportion: f32,
820        rng: &mut impl Rng,
821    ) -> (usize, Aabb<f32>) {
822        let end = start + dir * branch_len;
823        let line = LineSegment3 { start, end };
824        let wood_radius = branch_radius;
825        let leaf_radius = if depth == config.max_depth {
826            rng.gen_range(config.leaf_radius.clone())
827                + config.leaf_radius_scaled
828                    * Lerp::lerp(1.0, 1.0 - proportion, config.branch_len_bias.abs())
829        } else {
830            0.0
831        };
832
833        let has_stairs = config.inhabited
834            && depth < config.max_depth
835            && branch_radius > 6.5
836            && start.xy().distance(end.xy()) < (start.z - end.z).abs() * 1.5;
837        let bark_radius = if has_stairs { 5.0 } else { 0.0 } + wood_radius * 0.25;
838
839        // The AABB that covers this branch, along with wood and leaves that eminate
840        // from it
841        let mut aabb = Aabb {
842            min: Vec3::partial_min(start, end) - (wood_radius + bark_radius).max(leaf_radius),
843            max: Vec3::partial_max(start, end) + (wood_radius + bark_radius).max(leaf_radius),
844        };
845
846        let mut child_idx = None;
847        // Don't add child branches if we're already enough layers into the tree
848        if depth < config.max_depth {
849            let x_axis = dir
850                .cross(Vec3::<f32>::zero().map(|_| rng.gen_range(-1.0..1.0)))
851                .normalized();
852            let y_axis = dir.cross(x_axis).normalized();
853            let screw_shift = rng.gen_range(0.0..f32::consts::TAU);
854
855            let splits = rng.gen_range(config.splits.clone()).round() as usize;
856            for i in 0..splits {
857                let proportion = i as f32 / (splits - 1) as f32;
858                let dist = Lerp::lerp(rng.gen_range(0.0..1.0), proportion, config.proportionality);
859
860                const PHI: f32 = 0.618;
861                const RAD_PER_BRANCH: f32 = f32::consts::TAU * PHI;
862                let screw = (screw_shift + i as f32 * RAD_PER_BRANCH).sin() * x_axis
863                    + (screw_shift + i as f32 * RAD_PER_BRANCH).cos() * y_axis;
864
865                // Choose a point close to the branch to act as the target direction for the
866                // branch to grow in let split_factor =
867                // rng.gen_range(config.split_range.start, config.split_range.end).clamped(0.0,
868                // 1.0);
869                let split_factor =
870                    Lerp::lerp(config.split_range.start, config.split_range.end, dist);
871                let tgt = Lerp::lerp_unclamped(start, end, split_factor)
872                    + Lerp::lerp(
873                        Vec3::<f32>::zero().map(|_| rng.gen_range(-1.0..1.0)),
874                        screw,
875                        config.proportionality,
876                    );
877                // Start the branch at the closest point to the target
878                let branch_start = line.projected_point(tgt);
879                // Now, interpolate between the target direction and the parent branch's
880                // direction to find a direction
881                let branch_dir =
882                    Lerp::lerp_unclamped(tgt - branch_start, dir, config.straightness).normalized();
883
884                let (branch_idx, branch_aabb) = self.add_branch(
885                    config,
886                    branch_start,
887                    branch_dir,
888                    branch_len
889                        * config.branch_child_len
890                        * (1.0
891                            - (split_factor - 0.5)
892                                * 2.0
893                                * config.branch_len_bias.clamped(-1.0, 1.0)),
894                    branch_radius * config.branch_child_radius,
895                    depth + 1,
896                    child_idx,
897                    proportion,
898                    rng,
899                );
900                child_idx = Some(branch_idx);
901                // Parent branches AABBs include the AABBs of child branches to allow for
902                // culling during sampling
903                aabb.expand_to_contain(branch_aabb);
904            }
905        }
906
907        let idx = self.branches.len(); // Compute the index that this branch is going to have
908        self.branches.push(Branch {
909            line,
910            wood_radius,
911            leaf_radius,
912            leaf_vertical_scale: config.leaf_vertical_scale,
913            aabb,
914            sibling_idx,
915            child_idx,
916            has_stairs,
917        });
918
919        (idx, aabb)
920    }
921
922    /// Get the bounding box that covers the tree (all branches and leaves)
923    pub fn get_bounds(&self) -> Aabb<f32> {
924        self.branches[self.trunk_idx].aabb.union(self.root_aabb)
925    }
926
927    // Recursively search for branches or leaves by walking the tree's branch graph.
928    fn walk_inner(
929        &self,
930        descend: &mut impl FnMut(&Branch, &Branch) -> bool,
931        parent: &Branch,
932        branch_idx: usize,
933    ) {
934        let branch = &self.branches[branch_idx];
935        // Always probe the sibling branch, since it's not a child of the current
936        // branch.
937        let _branch_or_leaves = branch
938            .sibling_idx
939            .map(|idx| self.walk_inner(descend, parent, idx));
940
941        // Only continue probing this sub-graph of the tree if the branch maches a
942        // criteria (usually that it falls within the region we care about
943        // sampling)
944        if descend(branch, parent) {
945            // Probe the children of this branch
946            let _children = branch
947                .child_idx
948                .map(|idx| self.walk_inner(descend, branch, idx));
949        }
950    }
951
952    /// Recursively walk the tree's branches, calling the current closure with
953    /// the branch and its parent. If the closure returns `false`, recursion
954    /// into the child branches is skipped.
955    pub fn walk<F: FnMut(&Branch, &Branch) -> bool>(&self, mut f: F) {
956        self.walk_inner(&mut f, &self.branches[self.trunk_idx], self.trunk_idx);
957    }
958
959    /// Determine whether there are either branches or leaves at the given
960    /// position in the tree.
961    #[inline(always)]
962    pub fn is_branch_or_leaves_at(&self, pos: Vec3<f32>) -> (bool, bool, bool, bool) {
963        let mut flags = Vec4::broadcast(false);
964        self.walk(|branch, parent| {
965            if branch.aabb.contains_point(pos) {
966                flags |=
967                    Vec4::<bool>::from(branch.is_branch_or_leaves_at(&self.config, pos, parent).0);
968                true
969            } else {
970                false
971            }
972        });
973
974        let (log, leaf, platform, air) = flags.into_tuple();
975
976        let root = if self.root_aabb.contains_point(pos) {
977            self.roots.iter().any(|root| {
978                let p = root.line.projected_point(pos);
979                let d2 = p.distance_squared(pos);
980                d2 < root.radius.powi(2)
981            })
982        } else {
983            false
984        };
985        (
986            (log || root), /* & !air */
987            leaf & !air,
988            platform & !air,
989            air,
990        )
991    }
992}
993
994// Branches are arranged in a graph shape. Each branch points to both its first
995// child (if any) and also to the next branch in the list of child branches
996// associated with the parent. This means that the entire tree is laid out in a
997// walkable graph where each branch refers only to two other branches. As a
998// result, walking the tree is simply a case of performing double recursion.
999pub struct Branch {
1000    line: LineSegment3<f32>,
1001    wood_radius: f32,
1002    leaf_radius: f32,
1003    leaf_vertical_scale: f32,
1004    aabb: Aabb<f32>,
1005
1006    sibling_idx: Option<usize>,
1007    child_idx: Option<usize>,
1008
1009    has_stairs: bool,
1010}
1011
1012impl Branch {
1013    /// Determine whether there are either branches or leaves at the given
1014    /// position in the branch.
1015    /// (branch, leaves, stairs, forced_air)
1016    pub fn is_branch_or_leaves_at(
1017        &self,
1018        config: &TreeConfig,
1019        pos: Vec3<f32>,
1020        parent: &Branch,
1021    ) -> ((bool, bool, bool, bool), f32) {
1022        // fn finvsqrt(x: f32) -> f32 {
1023        //     let y = f32::from_bits(0x5f375a86 - (x.to_bits() >> 1));
1024        //     y * (1.5 - ( x * 0.5 * y * y ))
1025        // }
1026
1027        fn length_factor(line: LineSegment3<f32>, p: Vec3<f32>) -> f32 {
1028            let len_sq = line.start.distance_squared(line.end);
1029            if len_sq < 0.001 {
1030                0.0
1031            } else {
1032                (p - line.start).dot(line.end - line.start) / len_sq
1033            }
1034        }
1035
1036        // fn smooth(a: f32, b: f32, k: f32) -> f32 {
1037        //     // let h = (0.5 + 0.5 * (b - a) / k).clamped(0.0, 1.0);
1038        //     // Lerp::lerp(b, a, h) - k * h * (1.0 - h)
1039
1040        //     let h = (k-(a-b).abs()).max(0.0);
1041        //     a.min(b) - h * h * 0.25 / k
1042        // }
1043
1044        let p = self.line.projected_point(pos);
1045        let d2 = p.distance_squared(pos);
1046
1047        let length_factor = length_factor(self.line, pos);
1048        let wood_radius = if config.branch_child_radius_lerp {
1049            Lerp::lerp(parent.wood_radius, self.wood_radius, length_factor)
1050        } else {
1051            self.wood_radius
1052        };
1053
1054        let mask = if d2 < wood_radius.powi(2) {
1055            (true, false, false, false) // Wood
1056        } else if {
1057            let diff = (p - pos) / Vec3::new(1.0, 1.0, self.leaf_vertical_scale);
1058            diff.magnitude_squared() < self.leaf_radius.powi(2)
1059        } {
1060            (false, true, false, false) // Leaves
1061        } else {
1062            let stair_width = 5.0;
1063            let stair_thickness = 2.0;
1064            let stair_space = 5.0;
1065            if self.has_stairs {
1066                let (platform, air) = if pos.z >= self.line.start.z.min(self.line.end.z) - 1.0
1067                    && pos.z
1068                        <= self.line.start.z.max(self.line.end.z) + stair_thickness + stair_space
1069                    && d2 < (wood_radius + stair_width).powi(2)
1070                {
1071                    let rpos = pos.xy() - p;
1072                    let stretch = 32.0;
1073                    let stair_section = (rpos.x.atan2(rpos.y) / (f32::consts::PI * 2.0) * stretch
1074                        + pos.z)
1075                        .rem_euclid(stretch);
1076                    (
1077                        stair_section < stair_thickness,
1078                        stair_section >= stair_thickness
1079                            && stair_section < stair_thickness + stair_space,
1080                    ) // Stairs
1081                } else {
1082                    (false, false)
1083                };
1084
1085                let platform = platform
1086                    || (self.has_stairs
1087                        && self.wood_radius > 4.0
1088                        && !air
1089                        && d2 < (wood_radius + 10.0).powi(2)
1090                        && pos.z % 48.0 < stair_thickness);
1091
1092                (false, false, platform, air)
1093            } else {
1094                (false, false, false, false)
1095            }
1096        };
1097
1098        (mask, d2)
1099    }
1100
1101    /// This returns an AABB of both the branch and all of the children of that
1102    /// branch
1103    pub fn get_aabb(&self) -> Aabb<f32> { self.aabb }
1104
1105    pub fn get_line(&self) -> LineSegment3<f32> { self.line }
1106
1107    pub fn get_wood_radius(&self) -> f32 { self.wood_radius }
1108
1109    pub fn get_leaf_radius(&self) -> f32 { self.leaf_radius }
1110}
1111
1112struct Root {
1113    line: LineSegment3<f32>,
1114    radius: f32,
1115}
veloren_world/layer/tree.rs

veloren_world/layer/
tree.rs
