angled_random_walker/
lib.rs

1//! Angled Random Walker approach to Brownian tree generation.
2//!
3//! Lets you generate Brownian-tree-like structures faster than traditional
4//! diffusion-limited aggregation approaches.
5//!
6//! Useful for procedurally generating heightmaps.
7
8use rand::distributions::{Distribution, WeightedIndex};
9use rand::{Rng, SeedableRng};
10use rand_xoshiro::Xoshiro256PlusPlus;
11
12#[derive(Clone, Copy)]
13struct Direction(i32, i32);
14
15const DIRECTIONS: [Direction; 8] = [
16    Direction(1, 0),   // East
17    Direction(1, -1),  // North-East
18    Direction(0, -1),  // North
19    Direction(-1, -1), // North-West
20    Direction(-1, 0),  // West
21    Direction(-1, 1),  // South-West
22    Direction(0, 1),   // South
23    Direction(1, 1),   // South-East
24];
25
26impl Direction {
27    fn to_angle(self) -> f64 {
28        match self {
29            Direction(1, 0) => 0.00,
30            Direction(1, -1) => 0.25,
31            Direction(0, -1) => 0.50,
32            Direction(-1, -1) => 0.75,
33            Direction(-1, 0) => 1.00,
34            Direction(-1, 1) => 1.25,
35            Direction(0, 1) => 1.50,
36            Direction(1, 1) => 1.75,
37            Direction(x, y) => {
38                (f64::atan2(y as f64, x as f64) - f64::atan2(0.00, 1.00)) / std::f64::consts::PI
39            }
40        }
41    }
42}
43
44fn angle_distance(a: f64, b: f64) -> f64 {
45    f64::min((a - b).abs(), 2.00 - (a - b).abs())
46}
47
48fn angle_to_direction_weights(angle: f64) -> [f64; 8] {
49    let weights = DIRECTIONS.map(|d| 2.00 - angle_distance(angle, d.to_angle()));
50    let least_likely = weights.iter().min_by(|a, b| a.total_cmp(b)).unwrap();
51    weights.map(|w| w - least_likely)
52}
53
54fn choose_direction(angle: f64, rng: &mut Xoshiro256PlusPlus) -> Direction {
55    let dist = WeightedIndex::new(angle_to_direction_weights(angle)).unwrap();
56    DIRECTIONS[dist.sample(rng)]
57}
58
59fn angle_displace_random(angle: f64, divergence: f64, rng: &mut Xoshiro256PlusPlus) -> f64 {
60    (angle + rng.gen_range(-divergence..divergence)).clamp(0.00, 2.00)
61}
62
63#[derive(Clone, Copy, Debug)]
64struct Position(usize, usize);
65
66impl Position {
67    fn move_in(&self, dir: Direction, size: usize) -> Self {
68        let x = ((self.0 as i32) + dir.0).clamp(0, (size - 1) as i32) as usize;
69        let y = ((self.1 as i32) + dir.1).clamp(0, (size - 1) as i32) as usize;
70        Self(x, y)
71    }
72}
73
74#[derive(Clone, Copy, Debug, PartialEq)]
75enum WalkerKind {
76    Short,
77    Long,
78}
79
80#[derive(Clone, Copy, Debug)]
81struct AngledRandomWalker {
82    kind: WalkerKind,
83    age: usize,
84    cumulative_age: usize,
85    generation: usize,
86    position: Position,
87    angle: f64,
88}
89
90/// What values should be used to fill the grid.
91pub enum Paint {
92    /// The age of the walker when it reached that point.
93    Age,
94    /// The cumulative age, i.e. the age of the walker plus that of all its ancestors.
95    CumulativeAge,
96    /// The walker's generation (older is lower).
97    Generation,
98    /// The constant value `1`.
99    Constant,
100}
101
102/// Determines the orientation of the initial walkers placed at the start of the simulation.
103pub enum InitialWalkers {
104    /// Eight walkers, oriented towards each one of the cardinal and ordinal directions (N, S, E, W, NE, SE, NW, SW).
105    CardinalsAndOrdinals,
106    /// Walkers will be oriented at the angles in this vector. Angles are in units of Pi radians. Values will be clamped to `0.00..=2.00`.
107    Custom(Vec<f64>),
108}
109
110/// The parameters that control the simulation.
111pub struct SimulationParams {
112    /// Size of the grid.
113    pub size: usize,
114    /// Maximum age that long walkers survive to.
115    pub max_long_age: usize,
116    /// Maximum age that short walkers survive to.
117    pub max_short_age: usize,
118    /// Maximum generations of walkers.
119    pub max_generations: usize,
120    /// How many children a walker spawns when it ends.
121    pub children: usize,
122    /// Maximum angle that a long walker can diverge from its parent. Angles are in units of Pi radians, and clamped to `0.00..=2.00`.
123    pub max_long_angle_divergence: f64,
124    /// Maximum angle that a short walker can diverge from its parent. Angles are in units of Pi radians, and clamped to `0.00..=2.00`.
125    pub max_short_angle_divergence: f64,
126    /// How often a long walker produces a short branch.
127    pub short_branch_frequency: usize,
128    /// What to fill the grid with.
129    pub paint: Paint,
130    /// How to place initial walkers.
131    pub initial_walkers: InitialWalkers,
132    /// Seed for the randomness.
133    pub seed: u64,
134}
135
136struct ShortWalkerSpawn {
137    position: Position,
138    angle: f64,
139    generation: usize,
140    cumulative_age: usize,
141}
142
143/// Main simulation function.
144pub fn simulate(params: SimulationParams) -> Vec<Vec<u16>> {
145    let mut grid = vec![vec![0u16; params.size]; params.size];
146    let mut walkers: Vec<AngledRandomWalker> = match params.initial_walkers {
147        InitialWalkers::CardinalsAndOrdinals => (0..8)
148            .map(|n| AngledRandomWalker {
149                kind: WalkerKind::Long,
150                age: 0,
151                cumulative_age: 0,
152                generation: 0,
153                position: Position(params.size / 2, params.size / 2),
154                angle: 0.25 * n as f64,
155            })
156            .collect(),
157        InitialWalkers::Custom(angles) => angles
158            .into_iter()
159            .map(|angle| AngledRandomWalker {
160                kind: WalkerKind::Long,
161                age: 0,
162                cumulative_age: 0,
163                generation: 0,
164                position: Position(params.size / 2, params.size / 2),
165                angle: angle.clamp(0.00, 2.00),
166            })
167            .collect(),
168    };
169    let mut rng_direction_chooser = Xoshiro256PlusPlus::seed_from_u64(params.seed);
170    let mut rng_short_diverger = Xoshiro256PlusPlus::seed_from_u64(params.seed);
171    let mut rng_long_diverger = Xoshiro256PlusPlus::seed_from_u64(params.seed);
172    let mut short_walker_spawns: Vec<ShortWalkerSpawn> = Vec::new();
173    while !walkers.is_empty() {
174        let mut next_walkers: Vec<AngledRandomWalker> = Vec::new();
175        for walker in &walkers {
176            let max_age = match walker.kind {
177                WalkerKind::Short => params.max_short_age,
178                WalkerKind::Long => params.max_long_age,
179            };
180            if walker.age % params.short_branch_frequency == 0
181                && walker.kind != WalkerKind::Short
182                && walker.generation < params.max_generations
183            {
184                short_walker_spawns.push(ShortWalkerSpawn {
185                    position: walker.position,
186                    angle: walker.angle,
187                    generation: walker.generation + 1,
188                    cumulative_age: walker.cumulative_age + walker.age,
189                });
190            }
191            if walker.age > max_age {
192                if walker.generation < params.max_generations && walker.kind != WalkerKind::Short {
193                    for _ in 0..params.children {
194                        next_walkers.push(AngledRandomWalker {
195                            kind: WalkerKind::Long,
196                            age: 0,
197                            cumulative_age: walker.cumulative_age + walker.age,
198                            generation: walker.generation + 1,
199                            position: walker.position,
200                            angle: angle_displace_random(
201                                walker.angle,
202                                params.max_long_angle_divergence.clamp(0.00, 2.00),
203                                &mut rng_long_diverger,
204                            ),
205                        });
206                    }
207                }
208            } else {
209                let Position(x, y) = walker.position.move_in(
210                    choose_direction(walker.angle, &mut rng_direction_chooser),
211                    params.size,
212                );
213
214                grid[y][x] = match params.paint {
215                    Paint::Age => walker.age + 1,
216                    Paint::CumulativeAge => walker.cumulative_age + walker.age + 1,
217                    Paint::Generation => walker.generation + 1,
218                    Paint::Constant => 1,
219                } as u16;
220                next_walkers.push(AngledRandomWalker {
221                    kind: walker.kind,
222                    age: walker.age + 1,
223                    cumulative_age: walker.cumulative_age,
224                    generation: walker.generation,
225                    position: Position(x, y),
226                    angle: walker.angle,
227                });
228            }
229        }
230        walkers = next_walkers;
231    }
232    let mut short_walkers: Vec<AngledRandomWalker> = short_walker_spawns
233        .iter()
234        .map(
235            |ShortWalkerSpawn {
236                 position,
237                 angle,
238                 generation,
239                 cumulative_age,
240             }| AngledRandomWalker {
241                kind: WalkerKind::Short,
242                age: 0,
243                cumulative_age: *cumulative_age,
244                generation: *generation,
245                position: *position,
246                angle: angle_displace_random(
247                    *angle,
248                    params.max_short_angle_divergence,
249                    &mut rng_short_diverger,
250                ),
251            },
252        )
253        .collect();
254    while !short_walkers.is_empty() {
255        let mut next_short_walkers: Vec<AngledRandomWalker> = Vec::new();
256        for walker in &short_walkers {
257            if walker.age <= params.max_short_age {
258                let Position(x, y) = walker.position.move_in(
259                    choose_direction(walker.angle, &mut rng_direction_chooser),
260                    params.size,
261                );
262
263                grid[y][x] = match params.paint {
264                    Paint::Age => walker.age + 1,
265                    Paint::CumulativeAge => walker.cumulative_age + walker.age + 1,
266                    Paint::Generation => walker.generation + 1,
267                    Paint::Constant => 1,
268                } as u16;
269                next_short_walkers.push(AngledRandomWalker {
270                    kind: WalkerKind::Short,
271                    age: walker.age + 1,
272                    cumulative_age: walker.cumulative_age,
273                    generation: walker.generation,
274                    position: Position(x, y),
275                    angle: walker.angle,
276                });
277            }
278        }
279        short_walkers = next_short_walkers;
280    }
281    grid
282}
angled_random_walker/lib.rs

angled_random_walker/
lib.rs
