1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
use fxhash::FxHashSet;
use glam::{IVec2, Vec2};
use crate::{content::materials::MaterialId, sim::cell::Cell};
struct ComponentCell {
x: i32,
y: i32,
cell: Cell,
}
struct Component {
// (least_x, least_y, most_x, most_y)
bounds: [IVec2; 2],
cells: Vec<ComponentCell>,
}
pub struct PositionedComponent {
// offset of this chunk compared to the original object
pub position: Vec2,
pub size: IVec2,
pub cells: Vec<Cell>,
}
// i32 could be u8 if this is chunk size bounded
fn dfs(
seed: IVec2,
w: i32,
h: i32,
cells: &[Cell],
visited: &mut FxHashSet<(i32, i32)>,
component: &mut Component,
stack: &mut Vec<IVec2>,
) -> bool {
stack.clear();
stack.push(seed);
let mut started_component = false;
while let Some(pos) = stack.pop() {
if pos.x < 0 || pos.x >= w || pos.y < 0 || pos.y >= h {
continue;
}
// insert returns false if it was already present, so this is the
// contains-then-insert pair in one lookup
if !visited.insert((pos.x, pos.y)) {
continue;
}
let cell = cells[(pos.x + pos.y * w) as usize];
// TODO this is hacky
// note we mark void cells visited before bailing, so they aren't retried
if cell.material == MaterialId::Void {
continue;
}
started_component = true;
component.cells.push(ComponentCell {
x: pos.x,
y: pos.y,
cell,
});
component.bounds[0] = component.bounds[0].min(pos);
component.bounds[1] = component.bounds[1].max(pos);
// includes diagonal neighbours because marching squares colliders do
for dx in -1..=1 {
for dy in -1..=1 {
if dx == 0 && dy == 0 {
continue;
}
stack.push(pos + IVec2::new(dx, dy));
}
}
}
started_component
}
// this is a naive implementation
pub fn compute_components(cells: &[Cell], w: i32, h: i32) -> Vec<PositionedComponent> {
puffin::profile_function!();
let mut visited: FxHashSet<(i32, i32)> = FxHashSet::default();
let mut positioned_components: Vec<PositionedComponent> = Vec::new();
let mut stack: Vec<IVec2> = Vec::new();
for x in 0..w {
for y in 0..h {
let mut c = Component {
cells: Vec::new(),
bounds: [IVec2::MAX, IVec2::MIN],
};
if dfs(
IVec2::new(x, y),
w,
h,
cells,
&mut visited,
&mut c,
&mut stack,
) {
let pc_size = (c.bounds[1] - c.bounds[0]) + IVec2::ONE;
let mut pc_cells = vec![Cell::void(); (pc_size.x * pc_size.y) as usize];
for old_cell in c.cells {
pc_cells[((old_cell.x - c.bounds[0].x)
+ (old_cell.y - c.bounds[0].y) * pc_size.x)
as usize] = old_cell.cell;
}
let pc_centre = (c.bounds[0] + c.bounds[1] + IVec2::ONE).as_vec2() / 2.0;
let adjusted_pc_centre = pc_centre - (Vec2::new(w as f32, h as f32) / 2.0);
let pc = PositionedComponent {
position: adjusted_pc_centre,
size: pc_size,
cells: pc_cells,
};
positioned_components.push(pc);
}
}
}
positioned_components
}
|
