thedes_gen/map/layer/
region.rs

1use std::{collections::HashSet, convert::Infallible};
2
3use num::rational::Ratio;
4use rand::{Rng, seq::SliceRandom};
5use rand_distr::{Triangular, TriangularError};
6use thedes_async_util::progress;
7use thedes_domain::{
8    geometry::{Coord, CoordPair},
9    map::Map,
10};
11use thedes_geometry::orientation::Direction;
12use thiserror::Error;
13use tokio::task;
14
15use crate::random::{MutableDistribution, PickedReproducibleRng};
16
17use super::Layer;
18
19#[derive(Debug, Error)]
20pub enum InitError {
21    #[error("Error creating random distribution for map layer's region count")]
22    CountDist(#[source] TriangularError),
23}
24
25#[derive(Debug, Error)]
26pub enum Error<Le, De, Ce> {
27    #[error("Error manipulating map layer")]
28    Layer(#[source] Le),
29    #[error("Error generating data of a map region")]
30    DataDistr(#[source] De),
31    #[error("Error collecting regions for outside generation components")]
32    Collection(#[source] Ce),
33}
34
35#[derive(Debug, Clone, Error)]
36pub enum InvalidRegionConfig {
37    #[error(
38        "Minimum region count ratio {min} cannot be greater than maximum {max}"
39    )]
40    CountBoundOrder { min: Ratio<Coord>, max: Ratio<Coord> },
41    #[error(
42        "Peak ratio of region count distribution {peak} must be between min \
43         and max rationes {min} and {max}"
44    )]
45    PeakOutOfBounds { min: Ratio<Coord>, peak: Ratio<Coord>, max: Ratio<Coord> },
46    #[error("Range must be in the interval [0, 1], given {ratio}")]
47    RatioRange { ratio: Ratio<Coord> },
48}
49
50pub trait Collector<T> {
51    type Error: std::error::Error;
52
53    fn add_region(
54        &mut self,
55        center: CoordPair,
56        data: &T,
57    ) -> Result<(), Self::Error>;
58
59    fn add_point(
60        &mut self,
61        region: usize,
62        point: CoordPair,
63    ) -> Result<(), Self::Error>;
64}
65
66impl<'a, C, T> Collector<T> for &'a mut C
67where
68    C: Collector<T> + ?Sized,
69{
70    type Error = C::Error;
71
72    fn add_region(
73        &mut self,
74        center: CoordPair,
75        data: &T,
76    ) -> Result<(), Self::Error> {
77        (**self).add_region(center, data)
78    }
79
80    fn add_point(
81        &mut self,
82        region: usize,
83        point: CoordPair,
84    ) -> Result<(), Self::Error> {
85        (**self).add_point(region, point)
86    }
87}
88
89#[derive(Debug, Clone, Copy)]
90pub struct NopCollector;
91
92impl<T> Collector<T> for NopCollector {
93    type Error = Infallible;
94
95    fn add_region(
96        &mut self,
97        _center: CoordPair,
98        _data: &T,
99    ) -> Result<(), Self::Error> {
100        Ok(())
101    }
102
103    fn add_point(
104        &mut self,
105        _region: usize,
106        _point: CoordPair,
107    ) -> Result<(), Self::Error> {
108        Ok(())
109    }
110}
111
112#[derive(Debug, Clone)]
113pub struct Config {
114    min_region_count: Ratio<Coord>,
115    max_region_count: Ratio<Coord>,
116    peak_region_count: Ratio<Coord>,
117}
118
119impl Default for Config {
120    fn default() -> Self {
121        Self::new()
122    }
123}
124
125impl Config {
126    pub fn new() -> Self {
127        Self {
128            min_region_count: Ratio::new(1, 30),
129            max_region_count: Ratio::new(1, 10),
130            peak_region_count: Ratio::new(1, 20),
131        }
132    }
133
134    pub fn with_min_region_count(
135        self,
136        ratio: Ratio<Coord>,
137    ) -> Result<Self, InvalidRegionConfig> {
138        if ratio < Ratio::ZERO || ratio > Ratio::ONE {
139            Err(InvalidRegionConfig::RatioRange { ratio })?;
140        }
141        if ratio > self.max_region_count {
142            Err(InvalidRegionConfig::CountBoundOrder {
143                min: ratio,
144                max: self.max_region_count,
145            })?;
146        }
147        if ratio > self.peak_region_count {
148            Err(InvalidRegionConfig::PeakOutOfBounds {
149                min: ratio,
150                peak: self.peak_region_count,
151                max: self.max_region_count,
152            })?;
153        }
154        Ok(Self { min_region_count: ratio, ..self })
155    }
156
157    pub fn with_max_region_count(
158        self,
159        ratio: Ratio<Coord>,
160    ) -> Result<Self, InvalidRegionConfig> {
161        if ratio < Ratio::ZERO || ratio > Ratio::ONE {
162            Err(InvalidRegionConfig::RatioRange { ratio })?;
163        }
164        if self.min_region_count > ratio {
165            Err(InvalidRegionConfig::CountBoundOrder {
166                min: self.min_region_count,
167                max: ratio,
168            })?;
169        }
170        if self.peak_region_count > ratio {
171            Err(InvalidRegionConfig::PeakOutOfBounds {
172                min: self.min_region_count,
173                peak: self.peak_region_count,
174                max: ratio,
175            })?;
176        }
177        Ok(Self { max_region_count: ratio, ..self })
178    }
179
180    pub fn with_peak_region_count(
181        self,
182        ratio: Ratio<Coord>,
183    ) -> Result<Self, InvalidRegionConfig> {
184        if ratio < Ratio::ZERO || ratio > Ratio::ONE {
185            Err(InvalidRegionConfig::RatioRange { ratio })?;
186        }
187        if self.min_region_count > ratio || ratio > self.max_region_count {
188            Err(InvalidRegionConfig::PeakOutOfBounds {
189                min: self.min_region_count,
190                peak: ratio,
191                max: self.max_region_count,
192            })?;
193        }
194        Ok(Self { peak_region_count: ratio, ..self })
195    }
196
197    pub fn finish(
198        self,
199        map: &Map,
200        rng: &mut PickedReproducibleRng,
201    ) -> Result<Generator, InitError> {
202        let unified_size = map.rect().size.x + map.rect().size.y;
203        let mut actual_min =
204            (self.min_region_count * unified_size).ceil().to_integer();
205        let mut actual_peak =
206            (self.peak_region_count * unified_size).floor().to_integer();
207        let mut actual_max =
208            (self.max_region_count * unified_size).floor().to_integer();
209        actual_min = actual_min.max(unified_size);
210        actual_max = actual_max.min(unified_size);
211        actual_min = actual_min.min(actual_max);
212        actual_max = actual_min.max(actual_min);
213        actual_peak = actual_peak.max(actual_min).min(actual_max);
214        let min = f64::from(actual_min);
215        let max = f64::from(actual_max) + 1.0 - f64::EPSILON;
216        let mode = f64::from(actual_peak);
217        let distr =
218            Triangular::new(min, max, mode).map_err(InitError::CountDist)?;
219
220        let region_count = rng.sample(&distr) as usize;
221
222        Ok(Generator { region_count })
223    }
224}
225
226#[derive(Debug)]
227pub struct Generator {
228    region_count: usize,
229}
230
231impl Generator {
232    pub fn region_count(&self) -> usize {
233        self.region_count
234    }
235
236    pub fn progress_goal(&self, map: &Map) -> usize {
237        let area = map.rect().map(usize::from).total_area();
238        let region_count = self.region_count();
239        let region_data_prog = region_count;
240        let init_avail_points_prog = area;
241        let shuf_avail_points_prog = 1;
242        let init_centers_prog = 1;
243        let convert_avail_points_prog = 1;
244        let init_frontiers_prog = region_count;
245        let shuf_expand_prog = area - region_count;
246        region_data_prog
247            + init_avail_points_prog
248            + shuf_avail_points_prog
249            + init_centers_prog
250            + convert_avail_points_prog
251            + init_frontiers_prog
252            + shuf_expand_prog
253    }
254
255    pub async fn execute<L, Dd, C>(
256        self,
257        layer: &L,
258        data_distr: &mut Dd,
259        map: &mut Map,
260        rng: &mut PickedReproducibleRng,
261        collector: &mut C,
262        progress_logger: progress::Logger,
263    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>>
264    where
265        L: Layer,
266        L::Data: Clone,
267        Dd: MutableDistribution<L::Data>,
268        C: Collector<L::Data>,
269    {
270        let area = map.rect().map(usize::from).total_area();
271
272        let mut execution = Execution {
273            region_count: self.region_count,
274            regions_data: Vec::with_capacity(self.region_count),
275            region_centers: Vec::with_capacity(self.region_count),
276            available_points_seq: Vec::with_capacity(area),
277            available_points: HashSet::with_capacity(area),
278            region_frontiers: Vec::with_capacity(self.region_count),
279            to_be_processed: Vec::new(),
280            layer,
281            data_distr,
282            map,
283            rng,
284            collector,
285            progress_logger,
286        };
287
288        execution.generate_region_data().await?;
289        execution.initialize_available_points().await?;
290        execution.shuffle_available_points().await?;
291        execution.initialize_centers().await?;
292        execution.converting_available_points().await?;
293        execution.initialize_region_frontiers().await?;
294        execution.expanding_region_frontiers().await?;
295
296        execution.progress_logger.set_status("done");
297
298        Ok(())
299    }
300}
301
302#[derive(Debug)]
303struct Execution<'a, D, L, Dd, C> {
304    region_count: usize,
305    regions_data: Vec<D>,
306    region_centers: Vec<CoordPair>,
307    available_points_seq: Vec<CoordPair>,
308    available_points: HashSet<CoordPair>,
309    region_frontiers: Vec<(usize, CoordPair)>,
310    to_be_processed: Vec<(usize, CoordPair)>,
311    layer: &'a L,
312    data_distr: &'a mut Dd,
313    map: &'a mut Map,
314    rng: &'a mut PickedReproducibleRng,
315    collector: &'a mut C,
316    progress_logger: progress::Logger,
317}
318
319impl<'a, L, Dd, C> Execution<'a, L::Data, L, Dd, C>
320where
321    L: Layer,
322    L::Data: Clone,
323    Dd: MutableDistribution<L::Data>,
324    C: Collector<L::Data>,
325{
326    pub async fn generate_region_data(
327        &mut self,
328    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>> {
329        self.progress_logger.set_status("generating region data");
330        while self.regions_data.len() < self.region_count {
331            let region_data = self
332                .data_distr
333                .sample_mut(self.rng)
334                .map_err(Error::DataDistr)?;
335            self.regions_data.push(region_data);
336            self.progress_logger.increment();
337            task::yield_now().await;
338        }
339        Ok(())
340    }
341
342    pub async fn initialize_available_points(
343        &mut self,
344    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>> {
345        self.progress_logger.set_status("initializing available points");
346        let map_rect = self.map.rect();
347        for y in map_rect.top_left.y .. map_rect.bottom_right().y {
348            for x in map_rect.top_left.x .. map_rect.bottom_right().x {
349                let point = CoordPair { y, x };
350                self.available_points_seq.push(point);
351                self.progress_logger.increment();
352                task::yield_now().await;
353            }
354        }
355        Ok(())
356    }
357
358    pub async fn shuffle_available_points(
359        &mut self,
360    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>> {
361        self.progress_logger.set_status("shuffling available points");
362        self.available_points_seq.shuffle(self.rng);
363        self.progress_logger.increment();
364        task::yield_now().await;
365        Ok(())
366    }
367
368    pub async fn initialize_centers(
369        &mut self,
370    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>> {
371        self.progress_logger.set_status("initializing region centers");
372        let drained = self
373            .available_points_seq
374            .drain(self.available_points_seq.len() - self.region_count ..);
375        for (center, data) in drained.zip(&mut self.regions_data) {
376            self.collector
377                .add_region(center, data)
378                .map_err(Error::Collection)?;
379            self.region_centers.push(center);
380        }
381        self.progress_logger.increment();
382        task::yield_now().await;
383        Ok(())
384    }
385
386    pub async fn converting_available_points(
387        &mut self,
388    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>> {
389        self.progress_logger.set_status("converting available points");
390        self.available_points.extend(self.available_points_seq.drain(..));
391        self.progress_logger.increment();
392        task::yield_now().await;
393        Ok(())
394    }
395
396    pub async fn initialize_region_frontiers(
397        &mut self,
398    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>> {
399        self.progress_logger.set_status("initializing region frontiers");
400        for region in 0 .. self.region_count {
401            self.expand_point(region, self.region_centers[region])?;
402            self.progress_logger.increment();
403            task::yield_now().await;
404        }
405        Ok(())
406    }
407
408    pub async fn expanding_region_frontiers(
409        &mut self,
410    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>> {
411        self.progress_logger.set_status("expanding region frontiers");
412        while !self.available_points.is_empty() {
413            self.region_frontiers.shuffle(self.rng);
414            let process_count = (self.region_frontiers.len() - 1).max(1);
415            let start = self.region_frontiers.len() - process_count;
416            let drained = self.region_frontiers.drain(start ..);
417            self.to_be_processed.extend(drained);
418
419            while let Some((region, point)) = self.to_be_processed.pop() {
420                if self.available_points.remove(&point) {
421                    self.expand_point(region, point)?;
422                    self.progress_logger.increment();
423                    task::yield_now().await;
424                }
425            }
426        }
427        Ok(())
428    }
429
430    fn expand_point(
431        &mut self,
432        region: usize,
433        point: CoordPair,
434    ) -> Result<(), Error<L::Error, Dd::Error, C::Error>> {
435        self.layer
436            .set(self.map, point, self.regions_data[region].clone())
437            .map_err(Error::Layer)?;
438        for direction in Direction::ALL {
439            if let Some(new_point) = point
440                .checked_move_unit(direction)
441                .filter(|new_point| self.available_points.contains(new_point))
442            {
443                self.collector
444                    .add_point(region, new_point)
445                    .map_err(Error::Collection)?;
446                self.region_frontiers.push((region, new_point));
447            }
448        }
449        Ok(())
450    }
451}
thedes_gen/map/layer/region.rs

thedes_gen/map/layer/
region.rs
