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

steel_utils/
block_util.rs
