rust/landgen/src/outline_template_based/outline.rs
author unC0Rr
Tue, 10 Sep 2024 13:56:51 +0200
branchtransitional_engine
changeset 16032 31cc1e450273
parent 16029 9cbd18220eb7
child 16035 0caa3dfb3ba2
permissions -rw-r--r--
Add maze land generator ported from pascal engine
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
     1
use itertools::Itertools;
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
     2
use std::cmp::min;
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
     3
15828
44b49f255e31 add type safe power of two sizes
alfadur
parents: 15755
diff changeset
     4
use integral_geometry::{Line, Point, Polygon, Ray, Rect, Size};
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
     5
use land2d::Land2D;
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
     6
15921
5f00829c55ec Refactor landgen package structure
unC0Rr
parents: 15912
diff changeset
     7
use super::outline_template::OutlineTemplate;
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
     8
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
     9
pub struct OutlinePoints {
14124
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
    10
    pub islands: Vec<Polygon>,
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    11
    pub fill_points: Vec<Point>,
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    12
    pub size: Size,
14137
3119d665d3c6 collapse rectangle types back together with consistent usage of size
alfadur
parents: 14135
diff changeset
    13
    pub play_box: Rect,
16032
31cc1e450273 Add maze land generator ported from pascal engine
unC0Rr
parents: 16029
diff changeset
    14
    pub intersections_box: Rect,
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    15
}
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    16
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    17
impl OutlinePoints {
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    18
    pub fn from_outline_template<I: Iterator<Item = u32>>(
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    19
        outline_template: &OutlineTemplate,
14137
3119d665d3c6 collapse rectangle types back together with consistent usage of size
alfadur
parents: 14135
diff changeset
    20
        play_box: Rect,
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
    21
        size: Size,
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    22
        random_numbers: &mut I,
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    23
    ) -> Self {
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    24
        Self {
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
    25
            play_box,
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
    26
            size,
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    27
            islands: outline_template
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    28
                .islands
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    29
                .iter()
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    30
                .map(|i| {
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    31
                    i.iter()
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    32
                        .zip(random_numbers.tuples())
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    33
                        .map(|(rect, (rnd_a, rnd_b))| {
14137
3119d665d3c6 collapse rectangle types back together with consistent usage of size
alfadur
parents: 14135
diff changeset
    34
                            play_box.top_left() + rect.quotient(rnd_a as usize, rnd_b as usize)
14122
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
    35
                        })
14125
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    36
                        .collect::<Vec<_>>()
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    37
                        .into()
14122
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
    38
                })
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
    39
                .collect(),
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    40
            fill_points: outline_template.fill_points.clone(),
14137
3119d665d3c6 collapse rectangle types back together with consistent usage of size
alfadur
parents: 14135
diff changeset
    41
            intersections_box: Rect::at_origin(size)
14125
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    42
                .with_margin(size.to_square().width as i32 * -2),
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    43
        }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    44
    }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    45
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    46
    pub fn total_len(&self) -> usize {
14124
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
    47
        self.islands.iter().map(|i| i.edges_count()).sum::<usize>() + self.fill_points.len()
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    48
    }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    49
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    50
    pub fn iter(&self) -> impl Iterator<Item = &Point> {
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    51
        self.islands
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    52
            .iter()
14124
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
    53
            .flat_map(|p| p.iter())
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    54
            .chain(self.fill_points.iter())
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    55
    }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    56
14134
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
    57
    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut Point> {
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
    58
        self.islands
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
    59
            .iter_mut()
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
    60
            .flat_map(|i| i.iter_mut())
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
    61
            .chain(self.fill_points.iter_mut())
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    62
    }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    63
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    64
    fn divide_edge<I: Iterator<Item = u32>>(
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    65
        &self,
14076
e5904ead4864 Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents: 14069
diff changeset
    66
        segment: Line,
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    67
        distance_divisor: u32,
16032
31cc1e450273 Add maze land generator ported from pascal engine
unC0Rr
parents: 16029
diff changeset
    68
        distortion_limiting_factor: u32,
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    69
        random_numbers: &mut I,
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
    70
    ) -> Option<Point> {
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    71
        #[inline]
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
    72
        fn intersects(ray: &Ray, edge: &Line) -> bool {
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
    73
            ray.orientation(edge.start) != ray.orientation(edge.end)
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    74
        }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    75
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    76
        #[inline]
14135
7f5a591e1c43 separate rectangle types based on right/bottom edge inclusivity
alfadur
parents: 14134
diff changeset
    77
        fn solve_intersection(
14137
3119d665d3c6 collapse rectangle types back together with consistent usage of size
alfadur
parents: 14135
diff changeset
    78
            intersections_box: &Rect,
14135
7f5a591e1c43 separate rectangle types based on right/bottom edge inclusivity
alfadur
parents: 14134
diff changeset
    79
            ray: &Ray,
15828
44b49f255e31 add type safe power of two sizes
alfadur
parents: 15755
diff changeset
    80
            edge: &Line,
44b49f255e31 add type safe power of two sizes
alfadur
parents: 15755
diff changeset
    81
        ) -> Option<(i32, u32)> {
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
    82
            let edge_dir = edge.scaled_direction();
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
    83
            let aqpb = ray.direction.cross(edge_dir) as i64;
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    84
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    85
            if aqpb != 0 {
15828
44b49f255e31 add type safe power of two sizes
alfadur
parents: 15755
diff changeset
    86
                let mut iy = ((((edge.start.x - ray.start.x) as i64 * ray.direction.y as i64
44b49f255e31 add type safe power of two sizes
alfadur
parents: 15755
diff changeset
    87
                    + ray.start.y as i64 * ray.direction.x as i64)
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
    88
                    * edge_dir.y as i64
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
    89
                    - edge.start.y as i64 * edge_dir.x as i64 * ray.direction.y as i64)
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
    90
                    / aqpb) as i32;
14125
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    91
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    92
                // is there better way to do it?
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    93
                if iy < intersections_box.top() {
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    94
                    iy = intersections_box.top();
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    95
                } else if iy > intersections_box.bottom() {
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    96
                    iy = intersections_box.bottom();
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    97
                }
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
    98
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
    99
                let ix = if ray.direction.y.abs() > edge_dir.y.abs() {
14142
11202097584f fix tangents
alfadur
parents: 14141
diff changeset
   100
                    ray.start.x + ray.direction.cotangent_mul(iy - ray.start.y)
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   101
                } else {
14142
11202097584f fix tangents
alfadur
parents: 14141
diff changeset
   102
                    edge.start.x + edge_dir.cotangent_mul(iy - edge.start.y)
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   103
                };
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   104
14132
alfadur
parents: 14131 14130
diff changeset
   105
                let intersection_point = Point::new(ix, iy).clamp(intersections_box);
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   106
                let diff_point = ray.start - intersection_point;
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   107
                let t = ray.direction.dot(diff_point);
14132
alfadur
parents: 14131 14130
diff changeset
   108
14122
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   109
                if diff_point.max_norm() >= std::i16::MAX as i32 {
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   110
                    Some((t, std::i32::MAX as u32))
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   111
                } else {
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   112
                    let d = diff_point.integral_norm();
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   113
14122
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   114
                    Some((t, d))
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   115
                }
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   116
            } else {
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   117
                None
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   118
            }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   119
        }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   120
16028
509ecce37522 Make outline template generator behave more like old engine
unC0Rr
parents: 15926
diff changeset
   121
        let min_distance = distance_divisor as i32;
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   122
        // new point should fall inside this box
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   123
        let map_box = self.play_box.with_margin(min_distance);
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   124
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   125
        let normal = segment.scaled_normal();
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   126
        let normal_len = normal.integral_norm();
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   127
        let mid_point = segment.center();
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   128
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   129
        if (normal_len < min_distance as u32 * 3) || !map_box.contains_inside(mid_point) {
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   130
            return None;
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   131
        }
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   132
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   133
        let normal_ray = Ray::new(mid_point, normal);
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   134
        let mut dist_left = (self.size.width + self.size.height) as u32;
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   135
        let mut dist_right = dist_left;
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   136
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   137
        // find distances to map borders
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   138
        if normal.x != 0 {
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   139
            // where the normal line intersects the left map border
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   140
            let left_intersection = Point::new(
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   141
                map_box.left(),
14142
11202097584f fix tangents
alfadur
parents: 14141
diff changeset
   142
                mid_point.y + normal.tangent_mul(map_box.left() - mid_point.x),
14122
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   143
            );
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   144
            dist_left = (mid_point - left_intersection).integral_norm();
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   145
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   146
            // same for the right border
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   147
            let right_intersection = Point::new(
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   148
                map_box.right(),
15828
44b49f255e31 add type safe power of two sizes
alfadur
parents: 15755
diff changeset
   149
                mid_point.y + normal.tangent_mul(map_box.right() - mid_point.x),
14122
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   150
            );
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   151
            dist_right = (mid_point - right_intersection).integral_norm();
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   152
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   153
            if normal.x > 0 {
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   154
                std::mem::swap(&mut dist_left, &mut dist_right);
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   155
            }
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   156
        }
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   157
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   158
        if normal.y != 0 {
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   159
            // where the normal line intersects the top map border
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   160
            let top_intersection = Point::new(
14142
11202097584f fix tangents
alfadur
parents: 14141
diff changeset
   161
                mid_point.x + normal.cotangent_mul(map_box.top() - mid_point.y),
14122
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   162
                map_box.top(),
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   163
            );
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   164
            let dl = (mid_point - top_intersection).integral_norm();
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   165
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   166
            // same for the bottom border
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   167
            let bottom_intersection = Point::new(
14142
11202097584f fix tangents
alfadur
parents: 14141
diff changeset
   168
                mid_point.x + normal.cotangent_mul(map_box.bottom() - mid_point.y),
14122
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   169
                map_box.bottom(),
c27461e6a9eb Implement non-overflowing calculations for high values
unc0rr
parents: 14121
diff changeset
   170
            );
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   171
            let dr = (mid_point - bottom_intersection).integral_norm();
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   172
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   173
            if normal.y < 0 {
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   174
                dist_left = min(dist_left, dl);
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   175
                dist_right = min(dist_right, dr);
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   176
            } else {
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   177
                dist_left = min(dist_left, dr);
14110
21642eb0ff29 import some clarity into border distance computation
alfadur
parents: 14109
diff changeset
   178
                dist_right = min(dist_right, dl);
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   179
            }
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   180
        }
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   181
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   182
        // now go through all other segments
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   183
        for s in self.segments_iter() {
15926
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   184
            if s != segment && intersects(&normal_ray, &s) {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   185
                if let Some((t, d)) = solve_intersection(&self.intersections_box, &normal_ray, &s) {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   186
                    if t > 0 {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   187
                        dist_right = min(dist_right, d);
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   188
                    } else {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   189
                        dist_left = min(dist_left, d);
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   190
                    }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   191
                }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   192
            }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   193
        }
14081
5d42204ac35e Start convertion of FindPoint()
unC0Rr
parents: 14078
diff changeset
   194
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   195
        // go through all points, including fill points
14126
32383b888309 resolve some clippy complaints
alfadur
parents: 14125
diff changeset
   196
        for pi in self.iter().cloned() {
15926
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   197
            if pi != segment.start
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   198
                && pi != segment.end
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   199
                && intersects(&pi.ray_with_dir(normal), &segment)
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   200
            {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   201
                // ray from segment.start
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   202
                if let Some((t, d)) = solve_intersection(
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   203
                    &self.intersections_box,
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   204
                    &normal_ray,
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   205
                    &segment.start.line_to(pi),
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   206
                ) {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   207
                    if t > 0 {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   208
                        dist_right = min(dist_right, d);
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   209
                    } else {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   210
                        dist_left = min(dist_left, d);
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   211
                    }
15926
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   212
                }
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   213
15926
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   214
                // ray from segment.end
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   215
                if let Some((t, d)) = solve_intersection(
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   216
                    &self.intersections_box,
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   217
                    &normal_ray,
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   218
                    &segment.end.line_to(pi),
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   219
                ) {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   220
                    if t > 0 {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   221
                        dist_right = min(dist_right, d);
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   222
                    } else {
c273908218f3 Format the code, apply clippy fixes
unC0Rr
parents: 15921
diff changeset
   223
                        dist_left = min(dist_left, d);
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   224
                    }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   225
                }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   226
            }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   227
        }
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   228
16032
31cc1e450273 Add maze land generator ported from pascal engine
unC0Rr
parents: 16029
diff changeset
   229
        let max_dist = normal_len * 128 / distortion_limiting_factor;
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   230
        dist_left = min(dist_left, max_dist);
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   231
        dist_right = min(dist_right, max_dist);
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   232
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   233
        if dist_right + dist_left < min_distance as u32 * 2 + 10 {
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   234
            // limits are too narrow, just divide
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   235
            Some(mid_point)
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   236
        } else {
14113
be4419243735 fix normal offset for split points and make directions more consistent
alfadur
parents: 14111
diff changeset
   237
            // select distance within [-dist_right; dist_left], keeping min_distance in mind
be4419243735 fix normal offset for split points and make directions more consistent
alfadur
parents: 14111
diff changeset
   238
            let d = -(dist_right as i32)
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   239
                + min_distance
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   240
                + random_numbers.next().unwrap() as i32
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   241
                    % (dist_right as i32 + dist_left as i32 - min_distance * 2);
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   242
14131
c416d32764b7 organize landgen a bit more
alfadur
parents: 14126
diff changeset
   243
            Some(mid_point + normal * d / normal_len as i32)
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   244
        }
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   245
    }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   246
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   247
    fn divide_edges<I: Iterator<Item = u32>>(
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   248
        &mut self,
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   249
        distance_divisor: u32,
16032
31cc1e450273 Add maze land generator ported from pascal engine
unC0Rr
parents: 16029
diff changeset
   250
        distortion_limiting_factor: u32,
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   251
        random_numbers: &mut I,
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   252
    ) {
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   253
        for is in 0..self.islands.len() {
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   254
            let mut i = 0;
14124
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
   255
            while i < self.islands[is].edges_count() {
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
   256
                let segment = self.islands[is].get_edge(i);
16029
9cbd18220eb7 Fix cavern templates
unC0Rr
parents: 16028
diff changeset
   257
                if let Some(new_point) = self.divide_edge(
9cbd18220eb7 Fix cavern templates
unC0Rr
parents: 16028
diff changeset
   258
                    segment,
9cbd18220eb7 Fix cavern templates
unC0Rr
parents: 16028
diff changeset
   259
                    distance_divisor,
16032
31cc1e450273 Add maze land generator ported from pascal engine
unC0Rr
parents: 16029
diff changeset
   260
                    distortion_limiting_factor,
16029
9cbd18220eb7 Fix cavern templates
unC0Rr
parents: 16028
diff changeset
   261
                    random_numbers,
9cbd18220eb7 Fix cavern templates
unC0Rr
parents: 16028
diff changeset
   262
                ) {
14124
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
   263
                    self.islands[is].split_edge(i, new_point);
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   264
                    i += 2;
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   265
                } else {
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   266
                    i += 1;
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   267
                }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   268
            }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   269
        }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   270
    }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   271
14140
3078123e84ea Bezierize land outline
unc0rr
parents: 14137
diff changeset
   272
    pub fn bezierize(&mut self, segments_number: u32) {
3078123e84ea Bezierize land outline
unc0rr
parents: 14137
diff changeset
   273
        for island in &mut self.islands {
3078123e84ea Bezierize land outline
unc0rr
parents: 14137
diff changeset
   274
            island.bezierize(segments_number);
3078123e84ea Bezierize land outline
unc0rr
parents: 14137
diff changeset
   275
        }
3078123e84ea Bezierize land outline
unc0rr
parents: 14137
diff changeset
   276
    }
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   277
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   278
    pub fn distort<I: Iterator<Item = u32>>(
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   279
        &mut self,
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   280
        distance_divisor: u32,
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   281
        random_numbers: &mut I,
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   282
    ) {
16032
31cc1e450273 Add maze land generator ported from pascal engine
unC0Rr
parents: 16029
diff changeset
   283
        let distortion_limiting_factor = 100 + random_numbers.next().unwrap() as u32 % 8 * 10;
16028
509ecce37522 Make outline template generator behave more like old engine
unC0Rr
parents: 15926
diff changeset
   284
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   285
        loop {
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   286
            let old_len = self.total_len();
16032
31cc1e450273 Add maze land generator ported from pascal engine
unC0Rr
parents: 16029
diff changeset
   287
            self.divide_edges(distance_divisor, distortion_limiting_factor, random_numbers);
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   288
14093
dbaa125a0fe9 fix infinite loop in landgen
alfadur
parents: 14081
diff changeset
   289
            if self.total_len() == old_len {
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   290
                break;
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   291
            }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   292
        }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   293
    }
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   294
15912
6e22f4390b7e Add basics of wavefront collapse algorithm
unC0Rr
parents: 15828
diff changeset
   295
    pub fn draw<T: Copy + PartialEq + Default>(&self, land: &mut Land2D<T>, value: T) {
14076
e5904ead4864 Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents: 14069
diff changeset
   296
        for segment in self.segments_iter() {
e5904ead4864 Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents: 14069
diff changeset
   297
            land.draw_line(segment, value);
e5904ead4864 Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents: 14069
diff changeset
   298
        }
e5904ead4864 Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents: 14069
diff changeset
   299
    }
e5904ead4864 Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents: 14069
diff changeset
   300
14124
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
   301
    fn segments_iter<'a>(&'a self) -> impl Iterator<Item = Line> + 'a {
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
   302
        self.islands.iter().flat_map(|p| p.iter_edges())
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   303
    }
14095
b2feb190e4bc Move flip and mirror to outline methods
unc0rr
parents: 14093
diff changeset
   304
b2feb190e4bc Move flip and mirror to outline methods
unc0rr
parents: 14093
diff changeset
   305
    pub fn mirror(&mut self) {
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   306
        let r = self.size.width as i32 - 1;
14134
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
   307
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
   308
        self.iter_mut().for_each(|p| p.x = r - p.x);
14095
b2feb190e4bc Move flip and mirror to outline methods
unc0rr
parents: 14093
diff changeset
   309
    }
b2feb190e4bc Move flip and mirror to outline methods
unc0rr
parents: 14093
diff changeset
   310
b2feb190e4bc Move flip and mirror to outline methods
unc0rr
parents: 14093
diff changeset
   311
    pub fn flip(&mut self) {
14100
4d22be35cfa2 Finish porting FindPoint()
unc0rr
parents: 14097
diff changeset
   312
        let t = self.size.height as i32 - 1;
14134
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
   313
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
   314
        self.iter_mut().for_each(|p| p.y = t - p.y);
14095
b2feb190e4bc Move flip and mirror to outline methods
unc0rr
parents: 14093
diff changeset
   315
    }
14069
abb42ba345b6 Rework lib structure, no code changes
unC0Rr
parents:
diff changeset
   316
}
14076
e5904ead4864 Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents: 14069
diff changeset
   317
15755
2eb3469a28a0 trying to build
nemo
parents: 14207
diff changeset
   318
#[test]
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   319
fn points_test() {
14135
7f5a591e1c43 separate rectangle types based on right/bottom edge inclusivity
alfadur
parents: 14134
diff changeset
   320
    let size = Size::square(100);
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   321
    let mut points = OutlinePoints {
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   322
        islands: vec![
14124
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
   323
            Polygon::new(&[Point::new(0, 0), Point::new(20, 0), Point::new(30, 30)]),
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
   324
            Polygon::new(&[Point::new(10, 15), Point::new(15, 20), Point::new(20, 15)]),
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   325
        ],
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   326
        fill_points: vec![Point::new(1, 1)],
14137
3119d665d3c6 collapse rectangle types back together with consistent usage of size
alfadur
parents: 14135
diff changeset
   327
        play_box: Rect::at_origin(size).with_margin(10),
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   328
        size: Size::square(100),
14137
3119d665d3c6 collapse rectangle types back together with consistent usage of size
alfadur
parents: 14135
diff changeset
   329
        intersections_box: Rect::at_origin(size),
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   330
    };
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   331
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   332
    let segments: Vec<Line> = points.segments_iter().collect();
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   333
    assert_eq!(
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   334
        segments.first(),
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   335
        Some(&Line::new(Point::new(0, 0), Point::new(20, 0)))
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   336
    );
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   337
    assert_eq!(
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   338
        segments.last(),
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   339
        Some(&Line::new(Point::new(20, 15), Point::new(10, 15)))
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   340
    );
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   341
14134
09f62bb046ef actually there is a way to preserve mutable polygon iterator
alfadur
parents: 14133
diff changeset
   342
    points.iter_mut().for_each(|p| p.x = 2);
14125
376a0551b00a - Add distance-divider option to land_dump
unc0rr
parents: 14124
diff changeset
   343
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   344
    assert_eq!(points.fill_points[0].x, 2);
14124
6e0be42d0a8f polygonize OutlinePoints
alfadur
parents: 14122
diff changeset
   345
    assert_eq!(points.islands[0].get_edge(0).start.x, 2);
14078
bf40b5f938b0 - Add methods to work with Rect as box
unC0Rr
parents: 14077
diff changeset
   346
}