entity partitioning

1 files changed, 128 insertions, 0 deletions

diff --git a/src/sim/lib/components.rs b/src/sim/lib/components.rs
new file mode 100644
index 0000000..f1c34ac
--- /dev/null
+++ b/src/sim/lib/components.rs
@@ -0,0 +1,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
+}