veloren_common/terrain/
mod.rs

1pub mod biome;
2pub mod block;
3pub mod chonk;
4pub mod map;
5pub mod site;
6pub mod sprite;
7pub mod structure;
8
9use std::ops::{Add, Mul};
10
11// Reexports
12pub use self::{
13    biome::BiomeKind,
14    block::{Block, BlockKind},
15    map::MapSizeLg,
16    site::SiteKindMeta,
17    sprite::{SpriteCfg, SpriteKind, StructureSprite, UnlockKind},
18    structure::{Structure, StructuresGroup},
19};
20use hashbrown::HashMap;
21use roots::find_roots_cubic;
22use serde::{Deserialize, Serialize};
23
24use crate::{
25    vol::{ReadVol, RectVolSize},
26    volumes::vol_grid_2d::VolGrid2d,
27};
28use vek::*;
29
30// TerrainChunkSize
31
32#[derive(Debug, Clone, Serialize, Deserialize)]
33pub struct TerrainChunkSize;
34
35/// Base two logarithm of the number of blocks along either horizontal axis of
36/// a chunk.
37///
38/// NOTE: (1 << CHUNK_SIZE_LG) is guaranteed to fit in a u32.
39///
40/// NOTE: A lot of code assumes that the two dimensions are equal, so we make it
41/// explicit here.
42///
43/// NOTE: It is highly unlikely that a value greater than 5 will work, as many
44/// frontend optimizations rely on being able to pack chunk horizontal
45/// dimensions into 5 bits each.
46pub const TERRAIN_CHUNK_BLOCKS_LG: u32 = 5;
47
48impl RectVolSize for TerrainChunkSize {
49    const RECT_SIZE: Vec2<u32> = Vec2 {
50        x: (1 << TERRAIN_CHUNK_BLOCKS_LG),
51        y: (1 << TERRAIN_CHUNK_BLOCKS_LG),
52    };
53}
54
55impl TerrainChunkSize {
56    #[inline(always)]
57    /// Convert dimensions in terms of chunks into dimensions in terms of blocks
58    /// ```
59    /// use vek::*;
60    /// use veloren_common::terrain::TerrainChunkSize;
61    ///
62    /// assert_eq!(TerrainChunkSize::blocks(Vec2::new(3, 2)), Vec2::new(96, 64));
63    /// ```
64    pub fn blocks(chunks: Vec2<u32>) -> Vec2<u32> { chunks * Self::RECT_SIZE }
65
66    /// Calculate the world position (i.e. in blocks) at the center of this
67    /// chunk
68    /// ```
69    /// use vek::*;
70    /// use veloren_common::terrain::TerrainChunkSize;
71    ///
72    /// assert_eq!(
73    ///     TerrainChunkSize::center_wpos(Vec2::new(0, 2)),
74    ///     Vec2::new(16, 80)
75    /// );
76    /// ```
77    pub fn center_wpos(chunk_pos: Vec2<i32>) -> Vec2<i32> {
78        chunk_pos * Self::RECT_SIZE.as_::<i32>() + Self::RECT_SIZE.as_::<i32>() / 2
79    }
80}
81
82pub trait CoordinateConversions {
83    fn wpos_to_cpos(&self) -> Self;
84    fn cpos_to_wpos(&self) -> Self;
85    fn cpos_to_wpos_center(&self) -> Self;
86}
87
88impl CoordinateConversions for Vec2<i32> {
89    #[inline]
90    fn wpos_to_cpos(&self) -> Self {
91        self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| e.div_euclid(sz as i32))
92    }
93
94    #[inline]
95    fn cpos_to_wpos(&self) -> Self { self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| e * sz as i32) }
96
97    #[inline]
98    fn cpos_to_wpos_center(&self) -> Self {
99        self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| {
100            e * sz as i32 + sz as i32 / 2
101        })
102    }
103}
104
105impl CoordinateConversions for Vec2<f32> {
106    #[inline]
107    fn wpos_to_cpos(&self) -> Self { self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| e / sz as f32) }
108
109    #[inline]
110    fn cpos_to_wpos(&self) -> Self { self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| e * sz as f32) }
111
112    #[inline]
113    fn cpos_to_wpos_center(&self) -> Self {
114        self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| {
115            e * sz as f32 + sz as f32 / 2.0
116        })
117    }
118}
119
120impl CoordinateConversions for Vec2<f64> {
121    #[inline]
122    fn wpos_to_cpos(&self) -> Self { self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| e / sz as f64) }
123
124    #[inline]
125    fn cpos_to_wpos(&self) -> Self { self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| e * sz as f64) }
126
127    #[inline]
128    fn cpos_to_wpos_center(&self) -> Self {
129        self.map2(TerrainChunkSize::RECT_SIZE, |e, sz| {
130            e * sz as f64 + sz as f64 / 2.0
131        })
132    }
133}
134
135// TerrainChunkMeta
136
137#[derive(Debug, Clone, Serialize, Deserialize)]
138pub struct TerrainChunkMeta {
139    name: Option<String>,
140    biome: BiomeKind,
141    alt: f32,
142    tree_density: f32,
143    contains_river: bool,
144    near_water: bool,
145    river_velocity: Vec3<f32>,
146    approx_chunk_terrain_normal: Option<Vec3<f32>>,
147    rockiness: f32,
148    cliff_height: f32,
149    temp: f32,
150    humidity: f32,
151    site: Option<SiteKindMeta>,
152    tracks: Vec<CubicBezier3<f32>>,
153    debug_points: Vec<Vec3<f32>>,
154    debug_lines: Vec<LineSegment3<f32>>,
155    sprite_cfgs: HashMap<Vec3<i32>, SpriteCfg>,
156}
157
158impl TerrainChunkMeta {
159    pub fn new(
160        name: Option<String>,
161        biome: BiomeKind,
162        alt: f32,
163        tree_density: f32,
164        contains_river: bool,
165        near_water: bool,
166        river_velocity: Vec3<f32>,
167        temp: f32,
168        humidity: f32,
169        site: Option<SiteKindMeta>,
170        approx_chunk_terrain_normal: Option<Vec3<f32>>,
171        rockiness: f32,
172        cliff_height: f32,
173    ) -> Self {
174        Self {
175            name,
176            biome,
177            alt,
178            tree_density,
179            contains_river,
180            near_water,
181            river_velocity,
182            temp,
183            humidity,
184            site,
185            tracks: Vec::new(),
186            debug_points: Vec::new(),
187            debug_lines: Vec::new(),
188            sprite_cfgs: HashMap::default(),
189            approx_chunk_terrain_normal,
190            rockiness,
191            cliff_height,
192        }
193    }
194
195    pub fn void() -> Self {
196        Self {
197            name: None,
198            biome: BiomeKind::Void,
199            alt: 0.0,
200            tree_density: 0.0,
201            contains_river: false,
202            near_water: false,
203            river_velocity: Vec3::zero(),
204            temp: 0.0,
205            humidity: 0.0,
206            site: None,
207            tracks: Vec::new(),
208            debug_points: Vec::new(),
209            debug_lines: Vec::new(),
210            sprite_cfgs: HashMap::default(),
211            approx_chunk_terrain_normal: None,
212            rockiness: 0.0,
213            cliff_height: 0.0,
214        }
215    }
216
217    pub fn name(&self) -> Option<&str> { self.name.as_deref() }
218
219    pub fn biome(&self) -> BiomeKind { self.biome }
220
221    /// Altitude in blocks
222    pub fn alt(&self) -> f32 { self.alt }
223
224    pub fn tree_density(&self) -> f32 { self.tree_density }
225
226    pub fn contains_river(&self) -> bool { self.contains_river }
227
228    pub fn near_water(&self) -> bool { self.near_water }
229
230    pub fn river_velocity(&self) -> Vec3<f32> { self.river_velocity }
231
232    pub fn site(&self) -> Option<SiteKindMeta> { self.site }
233
234    /// Temperature from 0 to 1 (possibly -1 to 1)
235    pub fn temp(&self) -> f32 { self.temp }
236
237    pub fn humidity(&self) -> f32 { self.humidity }
238
239    pub fn tracks(&self) -> &[CubicBezier3<f32>] { &self.tracks }
240
241    pub fn add_track(&mut self, bezier: CubicBezier3<f32>) { self.tracks.push(bezier); }
242
243    pub fn debug_points(&self) -> &[Vec3<f32>] { &self.debug_points }
244
245    pub fn add_debug_point(&mut self, point: Vec3<f32>) { self.debug_points.push(point); }
246
247    pub fn debug_lines(&self) -> &[LineSegment3<f32>] { &self.debug_lines }
248
249    pub fn add_debug_line(&mut self, line: LineSegment3<f32>) { self.debug_lines.push(line); }
250
251    pub fn sprite_cfg_at(&self, rpos: Vec3<i32>) -> Option<&SpriteCfg> {
252        self.sprite_cfgs.get(&rpos)
253    }
254
255    pub fn set_sprite_cfg_at(&mut self, rpos: Vec3<i32>, sprite_cfg: SpriteCfg) {
256        self.sprite_cfgs.insert(rpos, sprite_cfg);
257    }
258
259    pub fn approx_chunk_terrain_normal(&self) -> Option<Vec3<f32>> {
260        self.approx_chunk_terrain_normal
261    }
262
263    pub fn rockiness(&self) -> f32 { self.rockiness }
264
265    pub fn cliff_height(&self) -> f32 { self.cliff_height }
266}
267
268// Terrain type aliases
269
270pub type TerrainChunk = chonk::Chonk<Block, TerrainChunkSize, TerrainChunkMeta>;
271pub type TerrainGrid = VolGrid2d<TerrainChunk>;
272
273const TERRAIN_GRID_SEARCH_DIST: i32 = 63;
274
275impl TerrainGrid {
276    /// Find a location suitable for spawning an entity near the given
277    /// position (but in the same chunk).
278    pub fn find_ground(&self, pos: Vec3<i32>) -> Vec3<i32> {
279        self.try_find_ground(pos).unwrap_or(pos)
280    }
281
282    pub fn is_space(&self, pos: Vec3<i32>) -> bool {
283        (0..2).all(|z| {
284            self.get(pos + Vec3::unit_z() * z)
285                .map_or(true, |b| !b.is_solid())
286        })
287    }
288
289    pub fn try_find_space(&self, pos: Vec3<i32>) -> Option<Vec3<i32>> {
290        (0..TERRAIN_GRID_SEARCH_DIST * 2 + 1)
291            .map(|i| if i % 2 == 0 { i } else { -i } / 2)
292            .map(|z_diff| pos + Vec3::unit_z() * z_diff)
293            .find(|pos| self.is_space(*pos))
294    }
295
296    pub fn try_find_ground(&self, pos: Vec3<i32>) -> Option<Vec3<i32>> {
297        (0..TERRAIN_GRID_SEARCH_DIST * 2 + 1)
298            .map(|i| if i % 2 == 0 { i } else { -i } / 2)
299            .map(|z_diff| pos + Vec3::unit_z() * z_diff)
300            .find(|pos| {
301                self.get(pos - Vec3::unit_z()).is_ok_and(|b| b.is_filled()) && self.is_space(*pos)
302            })
303    }
304
305    pub fn get_interpolated<T, F>(&self, pos: Vec2<i32>, mut f: F) -> Option<T>
306    where
307        T: Copy + Default + Add<Output = T> + Mul<f32, Output = T>,
308        F: FnMut(&TerrainChunk) -> T,
309    {
310        let pos = pos.as_::<f64>().wpos_to_cpos();
311
312        let cubic = |a: T, b: T, c: T, d: T, x: f32| -> T {
313            let x2 = x * x;
314
315            // Catmull-Rom splines
316            let co0 = a * -0.5 + b * 1.5 + c * -1.5 + d * 0.5;
317            let co1 = a + b * -2.5 + c * 2.0 + d * -0.5;
318            let co2 = a * -0.5 + c * 0.5;
319            let co3 = b;
320
321            co0 * x2 * x + co1 * x2 + co2 * x + co3
322        };
323
324        let mut x = [T::default(); 4];
325
326        for (x_idx, j) in (-1..3).enumerate() {
327            let y0 = f(self.get_key(pos.map2(Vec2::new(j, -1), |e, q| e.max(0.0) as i32 + q))?);
328            let y1 = f(self.get_key(pos.map2(Vec2::new(j, 0), |e, q| e.max(0.0) as i32 + q))?);
329            let y2 = f(self.get_key(pos.map2(Vec2::new(j, 1), |e, q| e.max(0.0) as i32 + q))?);
330            let y3 = f(self.get_key(pos.map2(Vec2::new(j, 2), |e, q| e.max(0.0) as i32 + q))?);
331
332            x[x_idx] = cubic(y0, y1, y2, y3, pos.y.fract() as f32);
333        }
334
335        Some(cubic(x[0], x[1], x[2], x[3], pos.x.fract() as f32))
336    }
337
338    /// Note, this returns `None` both when a chunk doesn't exist and when there
339    /// is no sprite cfg at this position in an existing chunk.
340    pub fn sprite_cfg_at(&self, wpos: Vec3<i32>) -> Option<&SpriteCfg> {
341        let chunk = self.pos_chunk(wpos)?;
342        let sprite_chunk_pos = TerrainGrid::chunk_offs(wpos);
343
344        chunk.meta().sprite_cfg_at(sprite_chunk_pos)
345    }
346}
347
348impl TerrainChunk {
349    /// Generate an all-water chunk at a specific sea level.
350    pub fn water(sea_level: i32) -> TerrainChunk {
351        TerrainChunk::new(
352            sea_level,
353            Block::water(SpriteKind::Empty),
354            Block::air(SpriteKind::Empty),
355            TerrainChunkMeta::void(),
356        )
357    }
358
359    /// Find the highest or lowest accessible position within the chunk
360    pub fn find_accessible_pos(&self, spawn_wpos: Vec2<i32>, ascending: bool) -> Vec3<f32> {
361        let min_z = self.get_min_z();
362        let max_z = self.get_max_z();
363
364        let pos = Vec3::new(
365            spawn_wpos.x,
366            spawn_wpos.y,
367            if ascending { min_z } else { max_z },
368        );
369        (0..(max_z - min_z))
370            .map(|z_diff| {
371                if ascending {
372                    pos + Vec3::unit_z() * z_diff
373                } else {
374                    pos - Vec3::unit_z() * z_diff
375                }
376            })
377            .find(|test_pos| {
378                let chunk_relative_xy = test_pos
379                    .xy()
380                    .map2(TerrainChunkSize::RECT_SIZE, |e, sz| e.rem_euclid(sz as i32));
381                self.get(
382                    Vec3::new(chunk_relative_xy.x, chunk_relative_xy.y, test_pos.z)
383                        - Vec3::unit_z(),
384                )
385                .is_ok_and(|b| b.is_filled())
386                    && (0..3).all(|z| {
387                        self.get(
388                            Vec3::new(chunk_relative_xy.x, chunk_relative_xy.y, test_pos.z)
389                                + Vec3::unit_z() * z,
390                        )
391                        .map_or(true, |b| !b.is_solid())
392                    })
393            })
394            .unwrap_or(pos)
395            .map(|e| e as f32)
396            + 0.5
397    }
398}
399
400// Terrain helper functions used across multiple crates.
401
402/// Computes the position Vec2 of a SimChunk from an index, where the index was
403/// generated by uniform_noise.
404///
405/// NOTE: Dimensions obey constraints on [map::MapConfig::map_size_lg].
406#[inline(always)]
407pub fn uniform_idx_as_vec2(map_size_lg: MapSizeLg, idx: usize) -> Vec2<i32> {
408    let x_mask = (1 << map_size_lg.vec().x) - 1;
409    Vec2::new((idx & x_mask) as i32, (idx >> map_size_lg.vec().x) as i32)
410}
411
412/// Computes the index of a Vec2 of a SimChunk from a position, where the index
413/// is generated by uniform_noise.  NOTE: Both components of idx should be
414/// in-bounds!
415#[inline(always)]
416pub fn vec2_as_uniform_idx(map_size_lg: MapSizeLg, idx: Vec2<i32>) -> usize {
417    ((idx.y as usize) << map_size_lg.vec().x) | idx.x as usize
418}
419
420// NOTE: want to keep this such that the chunk index is in ascending order!
421pub const NEIGHBOR_DELTA: [(i32, i32); 8] = [
422    (-1, -1),
423    (0, -1),
424    (1, -1),
425    (-1, 0),
426    (1, 0),
427    (-1, 1),
428    (0, 1),
429    (1, 1),
430];
431
432/// Iterate through all cells adjacent to a chunk.
433#[inline(always)]
434pub fn neighbors(map_size_lg: MapSizeLg, posi: usize) -> impl Clone + Iterator<Item = usize> {
435    let pos = uniform_idx_as_vec2(map_size_lg, posi);
436    let world_size = map_size_lg.chunks();
437    NEIGHBOR_DELTA
438        .iter()
439        .map(move |&(x, y)| Vec2::new(pos.x + x, pos.y + y))
440        .filter(move |pos| {
441            pos.x >= 0 && pos.y >= 0 && pos.x < world_size.x as i32 && pos.y < world_size.y as i32
442        })
443        .map(move |pos| vec2_as_uniform_idx(map_size_lg, pos))
444}
445
446pub fn river_spline_coeffs(
447    // _sim: &WorldSim,
448    chunk_pos: Vec2<f64>,
449    spline_derivative: Vec2<f32>,
450    downhill_pos: Vec2<f64>,
451) -> Vec3<Vec2<f64>> {
452    let dxy = downhill_pos - chunk_pos;
453    // Since all splines have been precomputed, we don't have to do that much work
454    // to evaluate the spline.  The spline is just ax^2 + bx + c = 0, where
455    //
456    // a = dxy - chunk.river.spline_derivative
457    // b = chunk.river.spline_derivative
458    // c = chunk_pos
459    let spline_derivative = spline_derivative.map(|e| e as f64);
460    Vec3::new(dxy - spline_derivative, spline_derivative, chunk_pos)
461}
462
463/// Find the nearest point from a quadratic spline to this point (in terms of t,
464/// the "distance along the curve" by which our spline is parameterized).  Note
465/// that if t < 0.0 or t >= 1.0, we probably shouldn't be considered "on the
466/// curve"... hopefully this works out okay and gives us what we want (a
467/// river that extends outwards tangent to a quadratic curve, with width
468/// configured by distance along the line).
469pub fn quadratic_nearest_point(
470    spline: &Vec3<Vec2<f64>>,
471    point: Vec2<f64>,
472    _line: Vec2<Vec2<f64>>, // Used for alternative distance functions below
473) -> Option<(f64, Vec2<f64>, f64)> {
474    //let eval_at = |t: f64| spline.x * t * t + spline.y * t + spline.z;
475
476    // Linear
477
478    // let line = LineSegment2 {
479    //     start: line.x,
480    //     end: line.y,
481    // };
482    // let len_sq = line.start.distance_squared(line.end);
483    // let t = ((point - line.start).dot(line.end - line.start) /
484    // len_sq).clamped(0.0, 1.0); let pos = line.start + (line.end - line.start)
485    // * t; return Some((t, pos, pos.distance_squared(point)));
486
487    // Quadratic
488
489    // let curve = QuadraticBezier2 {
490    //     start: line.x,
491    //     ctrl: eval_at(0.5),
492    //     end: line.y,
493    // };
494    // let (t, pos) = curve.binary_search_point_by_steps(point, 16, 0.001);
495    // let t = t.clamped(0.0, 1.0);
496    // let pos = curve.evaluate(t);
497    // return Some((t, pos, pos.distance_squared(point)));
498
499    // Cubic
500
501    // let ctrl_at = |t: f64, end: f64| {
502    //     let a = eval_at(end);
503    //     let b = eval_at(Lerp::lerp(end, t, 0.1));
504    //     let dir = (b - a).normalized();
505    //     let exact = eval_at(t);
506    //     a + dir * exact.distance(a)
507    // };
508    // let curve = CubicBezier2 {
509    //     start: line.x,
510    //     ctrl0: ctrl_at(0.33, 0.0),
511    //     ctrl1: ctrl_at(0.66, 1.0),
512    //     end: line.y,
513    // };
514    // let (t, pos) = curve.binary_search_point_by_steps(point, 12, 0.01);
515    // let t = t.clamped(0.0, 1.0);
516    // let pos = curve.evaluate(t);
517    // return Some((t, pos, pos.distance_squared(point)));
518
519    let a = spline.z.x;
520    let b = spline.y.x;
521    let c = spline.x.x;
522    let d = point.x;
523    let e = spline.z.y;
524    let f = spline.y.y;
525    let g = spline.x.y;
526    let h = point.y;
527    // This is equivalent to solving the following cubic equation (derivation is a
528    // bit annoying):
529    //
530    // A = 2(c^2 + g^2)
531    // B = 3(b * c + g * f)
532    // C = ((a - d) * 2 * c + b^2 + (e - h) * 2 * g + f^2)
533    // D = ((a - d) * b + (e - h) * f)
534    //
535    // Ax³ + Bx² + Cx + D = 0
536    //
537    // Once solved, this yield up to three possible values for t (reflecting minimal
538    // and maximal values).  We should choose the minimal such real value with t
539    // between 0.0 and 1.0.  If we fall outside those bounds, then we are
540    // outside the spline and return None.
541    let a_ = (c * c + g * g) * 2.0;
542    let b_ = (b * c + g * f) * 3.0;
543    let a_d = a - d;
544    let e_h = e - h;
545    let c_ = a_d * c * 2.0 + b * b + e_h * g * 2.0 + f * f;
546    let d_ = a_d * b + e_h * f;
547    let roots = find_roots_cubic(a_, b_, c_, d_);
548    let roots = roots.as_ref();
549
550    roots
551        .iter()
552        .copied()
553        .map(|root| {
554            let river_point = spline.x * root * root + spline.y * root + spline.z;
555            if root > 0.0 && root < 1.0 {
556                (root, river_point)
557            } else {
558                let root = root.clamped(0.0, 1.0);
559                let river_point = spline.x * root * root + spline.y * root + spline.z;
560                (root, river_point)
561            }
562        })
563        .map(|(root, river_point)| {
564            let river_distance = river_point.distance_squared(point);
565            (root, river_point, river_distance)
566        })
567        // In the (unlikely?) case that distances are equal, prefer the earliest point along the
568        // river.
569        .min_by(|&(ap, _, a), &(bp, _, b)| {
570            (a, !(0.0..=1.0).contains(&ap), ap)
571                .partial_cmp(&(b, !(0.0..=1.0).contains(&bp), bp))
572                .unwrap()
573        })
574}