entity partitioning

6 files changed, 222 insertions, 45 deletions

diff --git a/src/content/entities/entity_bullet_emitter.rs b/src/content/entities/entity_bullet_emitter.rs
index c58bd6b..1a39440 100644
--- a/src/content/entities/entity_bullet_emitter.rs
+++ b/src/content/entities/entity_bullet_emitter.rs
@@ -31,9 +31,10 @@ impl EntityBehaviour for BulletEmitterEntityBehaviour {
                     ctx,
                     update_ctx.entity_data.transform(ctx).unwrap().0,
                     target,
-                    400,
+                    1000,
                 );
-                self.shot_timer = 0.1;
+                // self.shot_timer = 0.1;
+                update_ctx.deferred_destroy(update_ctx.entity_data.id);
             }
 
             self.life -= delta_time;
diff --git a/src/main.rs b/src/main.rs
index 81b5ee6..f896de3 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -98,44 +98,6 @@ impl App {
                 ));
             }
 
-            // --TEST DRAWING--
-            if self.input_manager.lmb_held || self.input_manager.rmb_held {
-                // start with the bounding box of the drawing brush circle + some margin
-                // clamp the bounding box to the board sie
-                let bb_xl = (self.input_manager.world_mouse_pos.x - self.config.brush_radius)
-                    .round() as i32;
-                let bb_xu = (self.input_manager.world_mouse_pos.x + self.config.brush_radius)
-                    .round() as i32;
-                let bb_yl = (self.input_manager.world_mouse_pos.y - self.config.brush_radius)
-                    .round() as i32;
-                let bb_yu = (self.input_manager.world_mouse_pos.y + self.config.brush_radius)
-                    .round() as i32;
-
-                // for each point, check if the distance is less than the brush size and write the pixel
-                for x in bb_xl..bb_xu {
-                    for y in bb_yl..bb_yu {
-                        let r = random_range(0.0..1.0);
-                        if ((x - self.input_manager.world_mouse_pos.x.round() as i32).pow(2)
-                            + (y - self.input_manager.world_mouse_pos.y.round() as i32).pow(2))
-                            < (self.config.brush_radius as i32).pow(2)
-                            && r > 0.9
-                        {
-                            let cell = if self.input_manager.lmb_held {
-                                let mut cell = Cell::from_material(self.config.brush_material);
-                                // ensure we simulate on the first tick
-                                cell.match_parity(sim.cell_manager.seqno);
-                                cell
-                            } else {
-                                Cell::void()
-                            };
-                            sim.cell_manager.set_cell_from_game_position(
-                                x, y, cell, false, // wake the chunk
-                            )
-                        }
-                    }
-                }
-            }
-
             sim.update(&self.config, &self.input_manager, delta_time);
             self.input_manager.reset_for_frame();
         }
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
+}
diff --git a/src/sim/lib/mod.rs b/src/sim/lib/mod.rs
index 01373bc..8b3abb5 100644
--- a/src/sim/lib/mod.rs
+++ b/src/sim/lib/mod.rs
@@ -1,3 +1,4 @@
+pub mod components;
 pub mod force;
 pub mod marching_squares;
 pub mod ray;
diff --git a/src/sim/sim_manager/mod.rs b/src/sim/sim_manager/mod.rs
index 8fab9cf..b2441ef 100644
--- a/src/sim/sim_manager/mod.rs
+++ b/src/sim/sim_manager/mod.rs
@@ -1,12 +1,14 @@
 use std::time::Instant;
 
 use fxhash::FxHashMap;
+use rand::random_range;
 
 use crate::{
     Config, InputManager,
     config::{PHYSICS_DELTA_TIME, PHYSICS_FPS, SIM_FPS},
     input::Input,
     sim::{
+        cell::Cell,
         cell_manager::manager::CellManager,
         entity::{Entity, EntityDef, EntityId},
         particle_manager::ParticleManager,
@@ -99,6 +101,41 @@ impl SimManager {
         // before we tick, write all the entities into the sim world
         let cells_written_by_entity = write_entities_to_world(self);
 
+        // --TEST DRAWING--
+        if input_manager.lmb_held || input_manager.rmb_held {
+            // start with the bounding box of the drawing brush circle + some margin
+            // clamp the bounding box to the board sie
+            let bb_xl = (input_manager.world_mouse_pos.x - config.brush_radius).round() as i32;
+            let bb_xu = (input_manager.world_mouse_pos.x + config.brush_radius).round() as i32;
+            let bb_yl = (input_manager.world_mouse_pos.y - config.brush_radius).round() as i32;
+            let bb_yu = (input_manager.world_mouse_pos.y + config.brush_radius).round() as i32;
+
+            // for each point, check if the distance is less than the brush size and write the pixel
+            for x in bb_xl..bb_xu {
+                for y in bb_yl..bb_yu {
+                    let r = random_range(0.0..1.0);
+                    if ((x - input_manager.world_mouse_pos.x.round() as i32).pow(2)
+                        + (y - input_manager.world_mouse_pos.y.round() as i32).pow(2))
+                        < (config.brush_radius as i32).pow(2)
+                        && r > 0.9
+                    {
+                        let cell = if input_manager.lmb_held {
+                            let mut cell = Cell::from_material(config.brush_material);
+                            // ensure we simulate on the first tick
+                            cell.match_parity(self.cell_manager.seqno);
+                            cell
+                        } else {
+                            Cell::void()
+                        };
+
+                        self.cell_manager.set_cell_from_game_position(
+                            x, y, cell, false, // wake the chunk
+                        )
+                    }
+                }
+            }
+        }
+
         // tick
         self.cell_manager.tick(config.use_threading);
 
diff --git a/src/sim/sim_manager/utils.rs b/src/sim/sim_manager/utils.rs
index f30e9a0..264597d 100644
--- a/src/sim/sim_manager/utils.rs
+++ b/src/sim/sim_manager/utils.rs
@@ -1,10 +1,13 @@
 use glam::IVec2;
+use rapier2d::{dynamics::RigidBodyBuilder, math::Pose};
 
 use crate::{
+    config::CELLS_TO_METRES,
     content::materials::MaterialId,
     sim::{
         cell::Cell,
-        entity::{EntityId, EntityUpdateResult},
+        entity::{EntityCells, EntityDef, EntityId, EntityUpdateResult},
+        lib::components::compute_components,
         sim_manager::SimManager,
     },
 };
@@ -117,10 +120,17 @@ pub fn read_back_entities_from_world(
         if let Some(entity) = &mut entity
             && should_update_entity
         {
-            puffin::profile_scope!("Recompute collider");
-            if let Some(new_collider) = entity.compute_collider() {
-                {
-                    puffin::profile_scope!("Upsert collider");
+            // correctness: there's no way to get here if the entity is an uncelled entity
+            let ec = entity.data.cells.as_mut().unwrap();
+            // first check if the entity has been partitioned
+            let components = compute_components(&ec.cells, ec.size.x, ec.size.y);
+            if components.len() == 0 {
+                panic!("The entity was completely destroyed?")
+            } else if components.len() == 1 {
+                // the entity's cells were changed, but not partitioned
+                puffin::profile_scope!("Recompute collider");
+                if let Some(new_collider) = entity.compute_collider() {
+                    // don't profile this separately as it's basically free
                     sim.rb_manager
                         .physics_manager
                         .world
@@ -134,6 +144,44 @@ pub fn read_back_entities_from_world(
 
                     entity.data.collider_h = Some(new_handle);
                 }
+            } else {
+                // the entity was partitioned
+                // destroy the original entity
+                // correctness -- not correct! because we don't have pos without rb
+                let old_rb = sim
+                    .rb_manager
+                    .physics_manager
+                    .world
+                    .bodies
+                    .get(entity.data.rb_h.unwrap())
+                    .unwrap();
+                let old_pose = old_rb.position().clone();
+                let old_linvel = old_rb.linvel().clone();
+                let old_angvel = old_rb.angvel().clone();
+
+                sim.destroy_entity(entity_id);
+                // and create a new entity for each component
+                for component in components {
+                    let r = old_pose.transform_vector(component.position / CELLS_TO_METRES);
+                    let mut pose = old_pose;
+                    pose.translation += r;
+
+                    let rb = RigidBodyBuilder::dynamic()
+                        .pose(pose)
+                        .linvel(old_linvel)
+                        .angvel(old_angvel)
+                        .build();
+
+                    let def = EntityDef::from_cells_and_rb(
+                        EntityCells {
+                            cells: component.cells,
+                            size: component.size,
+                        },
+                        rb,
+                        None,
+                    );
+                    sim.create_entity(def);
+                }
             }
         }
     }