steel_utils/
block_util.rs

1//! Vanilla `BlockUtil` helpers shared by gameplay systems.
2
3use crate::{BlockPos, axis::Axis};
4
5/// Rectangle found around a center block while scanning along two axes.
6#[derive(Debug, Clone, Copy, PartialEq, Eq)]
7pub struct FoundRectangle {
8    /// Minimum corner of the rectangle.
9    pub min_corner: BlockPos,
10    /// Size along the first scan axis.
11    pub axis1_size: i32,
12    /// Size along the second scan axis.
13    pub axis2_size: i32,
14}
15
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17struct IntBounds {
18    min: i32,
19    max: i32,
20}
21
22/// Returns vanilla `BlockUtil.getLargestRectangleAround`.
23///
24/// # Panics
25///
26/// Panics if either scan limit is negative.
27#[must_use]
28pub fn get_largest_rectangle_around(
29    center: BlockPos,
30    axis1: Axis,
31    limit1: i32,
32    axis2: Axis,
33    limit2: i32,
34    test: impl Fn(BlockPos) -> bool,
35) -> FoundRectangle {
36    assert!(
37        limit1 >= 0 && limit2 >= 0,
38        "rectangle scan limits must be non-negative"
39    );
40
41    let negative_delta1 = get_limit(&test, center, axis1, -1, limit1);
42    let positive_delta1 = get_limit(&test, center, axis1, 1, limit1);
43    let center_index1 = negative_delta1;
44    let mut bounds_by_axis1 =
45        vec![IntBounds { min: 0, max: 0 }; (center_index1 + 1 + positive_delta1) as usize];
46    bounds_by_axis1[center_index1 as usize] = IntBounds {
47        min: get_limit(&test, center, axis2, -1, limit2),
48        max: get_limit(&test, center, axis2, 1, limit2),
49    };
50    let center_index2 = bounds_by_axis1[center_index1 as usize].min;
51
52    for i in 1..=negative_delta1 {
53        let last_bounds = bounds_by_axis1[(center_index1 - (i - 1)) as usize];
54        let origin = center.relative_axis(axis1, -i);
55        bounds_by_axis1[(center_index1 - i) as usize] = IntBounds {
56            min: get_limit(&test, origin, axis2, -1, last_bounds.min),
57            max: get_limit(&test, origin, axis2, 1, last_bounds.max),
58        };
59    }
60
61    for i in 1..=positive_delta1 {
62        let last_bounds = bounds_by_axis1[(center_index1 + i - 1) as usize];
63        let origin = center.relative_axis(axis1, i);
64        bounds_by_axis1[(center_index1 + i) as usize] = IntBounds {
65            min: get_limit(&test, origin, axis2, -1, last_bounds.min),
66            max: get_limit(&test, origin, axis2, 1, last_bounds.max),
67        };
68    }
69
70    let mut min_axis1 = 0;
71    let mut min_axis2 = 0;
72    let mut size_axis1 = 0;
73    let mut size_axis2 = 0;
74    let mut columns = vec![0; bounds_by_axis1.len()];
75
76    for i2 in (0..=center_index2).rev() {
77        for (i1, bounds2) in bounds_by_axis1.iter().enumerate() {
78            let min2 = center_index2 - bounds2.min;
79            let max2 = center_index2 + bounds2.max;
80            columns[i1] = if i2 >= min2 && i2 <= max2 {
81                max2 + 1 - i2
82            } else {
83                0
84            };
85        }
86
87        let (bounds_axis1, new_size_axis2) = get_max_rectangle_location(&columns);
88        let new_size_axis1 = 1 + bounds_axis1.max - bounds_axis1.min;
89        if new_size_axis1 * new_size_axis2 > size_axis1 * size_axis2 {
90            min_axis1 = bounds_axis1.min;
91            min_axis2 = i2;
92            size_axis1 = new_size_axis1;
93            size_axis2 = new_size_axis2;
94        }
95    }
96
97    FoundRectangle {
98        min_corner: center
99            .relative_axis(axis1, min_axis1 - center_index1)
100            .relative_axis(axis2, min_axis2 - center_index2),
101        axis1_size: size_axis1,
102        axis2_size: size_axis2,
103    }
104}
105
106fn get_limit(
107    test: &impl Fn(BlockPos) -> bool,
108    start: BlockPos,
109    axis: Axis,
110    step: i32,
111    limit: i32,
112) -> i32 {
113    let mut max = 0;
114    let mut pos = start;
115    while max < limit {
116        pos = pos.relative_axis(axis, step);
117        if !test(pos) {
118            break;
119        }
120        max += 1;
121    }
122    max
123}
124
125fn get_max_rectangle_location(columns: &[i32]) -> (IntBounds, i32) {
126    let mut max_start = 0;
127    let mut max_end = 0;
128    let mut max_height = 0;
129    let mut stack = vec![0_usize];
130
131    for column in 1..=columns.len() {
132        let height = if column == columns.len() {
133            0
134        } else {
135            columns[column]
136        };
137
138        while let Some(&top) = stack.last() {
139            let stack_height = columns[top];
140            if height >= stack_height {
141                stack.push(column);
142                break;
143            }
144
145            stack.pop();
146            let start = stack.last().map_or(0, |top| top + 1);
147            if stack_height * (column - start) as i32 > max_height * (max_end - max_start) as i32 {
148                max_end = column;
149                max_start = start;
150                max_height = stack_height;
151            }
152        }
153
154        if stack.is_empty() {
155            stack.push(column);
156        }
157    }
158
159    (
160        IntBounds {
161            min: max_start as i32,
162            max: max_end as i32 - 1,
163        },
164        max_height,
165    )
166}
167
168#[cfg(test)]
169mod tests {
170    use super::{IntBounds, get_largest_rectangle_around, get_max_rectangle_location};
171    use crate::{BlockPos, axis::Axis};
172
173    #[test]
174    fn max_rectangle_location_matches_vanilla_histogram_scan() {
175        let (bounds, height) = get_max_rectangle_location(&[2, 1, 5, 6, 2, 3]);
176
177        assert_eq!(bounds, IntBounds { min: 2, max: 3 });
178        assert_eq!(height, 5);
179    }
180
181    #[test]
182    fn largest_rectangle_around_scans_both_axes_from_center() {
183        let center = BlockPos::ZERO;
184        let rectangle = get_largest_rectangle_around(center, Axis::X, 3, Axis::Y, 3, |pos| {
185            (-1..=2).contains(&pos.x()) && (-1..=1).contains(&pos.y()) && pos.z() == 0
186        });
187
188        assert_eq!(rectangle.min_corner, BlockPos::new(-1, -1, 0));
189        assert_eq!(rectangle.axis1_size, 4);
190        assert_eq!(rectangle.axis2_size, 3);
191    }
192}
steel_utils/block_util.rs

steel_utils/
block_util.rs
