MVP of marching squares

11 files changed, 288 insertions, 66 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 07e4b66..042caee 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -2447,6 +2447,7 @@ dependencies = [
  "env_logger",
  "futures",
  "fxhash",
+ "glam 0.33.3",
  "puffin",
  "puffin_http",
  "rand",
diff --git a/Cargo.toml b/Cargo.toml
index 2af9919..cd84554 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -19,6 +19,7 @@ futures = "0.3.34"
 bytemuck = "1.25.2"
 fxhash = "0.2.1"
 rapier2d = { version = "0.35.2", features = ["debug-render"] }
+glam = "0.33.3"
 
 [features]
 profiler = []
diff --git a/src/main.rs b/src/main.rs
index 3452065..640e5b9 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -5,6 +5,7 @@ mod sim;
 
 use futures::executor;
 use fxhash::FxHashMap;
+use glam::Vec2;
 use rand::random_range;
 use std::{collections::VecDeque, sync::Arc, time::Instant};
 use winit::{
@@ -20,7 +21,7 @@ use winit::{
 
 use crate::{
     camera::Camera,
-    config::{PHYSICS_DELTA_TIME, PHYSICS_FPS, SIM_FPS, WINDOW_TITLE},
+    config::{CHUNK_SIZE, PHYSICS_DELTA_TIME, PHYSICS_FPS, SIM_FPS, WINDOW_TITLE},
     renderer::RendererState,
     sim::{
         cell::{cell::Cell, materials::MaterialId},
@@ -45,8 +46,11 @@ struct Config {
 struct Input {
     last_mouse_pos_on_screen: Option<(f32, f32)>,
     last_mouse_world_pos: Option<(f32, f32)>,
+    last_mouse_chunk_pos: Option<(i32, i32)>,
+    last_mouse_local_pos: Option<(u8, u8)>,
     is_lmb_pressed: bool,
     trigger_test_1: bool,
+    trigger_test_2: bool,
 
     // keybindings
     is_up_pressed: bool,
@@ -110,6 +114,18 @@ impl App {
             rbsm.test_spawn_box(lm.0, lm.1, self.config.dropper_material);
         }
 
+        if self.input.trigger_test_2
+            && let Some((cx, cy)) = self.input.last_mouse_chunk_pos
+            && let Some(world) = &self.world
+            && let Some(rbsm) = &mut self.rb_sim_manager
+        {
+            self.input.trigger_test_2 = false;
+            rbsm.test_add_collider_from_chunk(
+                Vec2::new((cx * CHUNK_SIZE) as f32, (cy * CHUNK_SIZE) as f32),
+                &world.chunks[*world.chunk_position_to_chunk_idx.get(&(cx, cy)).unwrap()],
+            );
+        }
+
         // --TEST DRAWING--
         if self.input.is_lmb_pressed
             && let Some(lm) = self.input.last_mouse_world_pos
@@ -201,8 +217,11 @@ impl Default for App {
             input: Input {
                 last_mouse_pos_on_screen: None,
                 last_mouse_world_pos: None,
+                last_mouse_chunk_pos: None,
+                last_mouse_local_pos: None,
 
                 trigger_test_1: false,
+                trigger_test_2: false,
                 is_lmb_pressed: false,
                 is_up_pressed: false,
                 is_left_pressed: false,
@@ -328,15 +347,24 @@ impl ApplicationHandler for App {
                     }
                     KeyCode::Space if pressed => self.sim_paused = !self.sim_paused,
                     KeyCode::KeyX if pressed => self.ignore_pause_next_tick = true,
-                    KeyCode::KeyQ if pressed && !repeat => self.input.trigger_test_1 = true,
+                    KeyCode::Digit1 if pressed && !repeat => self.input.trigger_test_1 = true,
+                    KeyCode::Digit2 if pressed && !repeat => self.input.trigger_test_2 = true,
                     _ => {}
                 }
             }
             WindowEvent::CursorMoved { position, .. } => {
                 self.input.last_mouse_pos_on_screen = Some((position.x as f32, position.y as f32));
-                self.input.last_mouse_world_pos = self.camera.as_mut().map(|camera| {
-                    camera.screen_position_to_world(position.x as f32, position.y as f32)
-                })
+
+                if let Some(camera) = &mut self.camera {
+                    let world_pos =
+                        camera.screen_position_to_world(position.x as f32, position.y as f32);
+
+                    self.input.last_mouse_world_pos = Some(world_pos);
+                    let ((cx, cy), (lx, ly)) =
+                        World::split_game_position(world_pos.0 as i32, world_pos.1 as i32);
+                    self.input.last_mouse_chunk_pos = Some((cx, cy));
+                    self.input.last_mouse_local_pos = Some((lx, ly));
+                }
             }
             WindowEvent::MouseInput { state, button, .. } => {
                 if button == MouseButton::Left {
diff --git a/src/renderer/ui.rs b/src/renderer/ui.rs
index a1ac31f..56bf278 100644
--- a/src/renderer/ui.rs
+++ b/src/renderer/ui.rs
@@ -100,18 +100,20 @@ pub fn draw_egui<'a>(
     ui.add(egui::Slider::new(&mut camera.zoom, 0.0..=10.0).text("Zoom"));
     ui.heading("Input");
 
-    input.last_mouse_pos_on_screen.map(|p| {
-        ui.label(format!(
-            "Mouse: x,y=({x}, {y}), lmb_pressed={lmb}",
-            x = p.0,
-            y = p.1,
-            lmb = input.is_lmb_pressed
-        ))
-    });
+    input
+        .last_mouse_world_pos
+        .map(|p| ui.label(format!("Mouse (world): x,y=({x}, {y})", x = p.0, y = p.1,)));
+
+    input
+        .last_mouse_chunk_pos
+        .map(|p| ui.label(format!("Mouse (chunk): x,y=({x}, {y})", x = p.0, y = p.1,)));
+
+    input
+        .last_mouse_local_pos
+        .map(|p| ui.label(format!("Mouse (local): x,y=({x}, {y})", x = p.0, y = p.1,)));
 
     if let Some((x, y)) = input.last_mouse_world_pos {
         ui.heading("Entity");
-        ui.label(format!("x,y=({x}, {y})"));
         if let Some(cell) = world.get_cell_from_game_position(x.round() as i32, y.round() as i32) {
             let material = cell.material.def();
             let cell_label = ui.label(
diff --git a/src/sim/cell_sim/chunk.rs b/src/sim/cell_sim/chunk.rs
index 116a38a..8c3acb4 100644
--- a/src/sim/cell_sim/chunk.rs
+++ b/src/sim/cell_sim/chunk.rs
@@ -1,6 +1,9 @@
 use crate::{
     config::{CELLS_IN_CHUNK, CHUNK_SIZE},
-    sim::cell::cell::Cell,
+    sim::{
+        cell::{cell::Cell, materials::MaterialId},
+        lib::marching_squares::Marchable,
+    },
 };
 
 pub struct Chunk {
@@ -27,3 +30,13 @@ impl Chunk {
         }
     }
 }
+
+impl Marchable for Chunk {
+    fn occupied(&self, x: i32, y: i32) -> bool {
+        if x < 0 || x >= CHUNK_SIZE || y < 0 || y >= CHUNK_SIZE {
+            false
+        } else {
+            self.get_cell_at_local_position(x as u8, y as u8).material != MaterialId::Void
+        }
+    }
+}
diff --git a/src/sim/cell_sim/mod.rs b/src/sim/cell_sim/mod.rs
index a1db2a1..b7d0597 100644
--- a/src/sim/cell_sim/mod.rs
+++ b/src/sim/cell_sim/mod.rs
@@ -1,4 +1,3 @@
 pub mod chunk;
-pub mod overlay;
 pub mod sim;
 pub mod world;
diff --git a/src/sim/cell_sim/overlay.rs b/src/sim/cell_sim/overlay.rs
deleted file mode 100644
index ee494ae..0000000
--- a/src/sim/cell_sim/overlay.rs
+++ /dev/null
@@ -1,50 +0,0 @@
-use crate::{Config, Input, sim::cell_sim::world::World};
-
-pub fn create_compute_combined_overlay_offset(
-    world: &World,
-    config: &Config,
-    input: &Input,
-) -> impl Fn(i32, i32) -> (u8, u8, u8, u8) {
-    puffin::profile_function!();
-    // TODO fix this move?
-    move |pixel_x: i32, pixel_y: i32| {
-        // could allow negative offsets too
-        let mut offset: (u8, u8, u8, u8) = (0x00, 0x00, 0x00, 0x00);
-
-        // // bounds
-        // // left
-        // let xl = -((board.get_game_width() / 2 + 1) as i32);
-        // // right
-        // let xu = (board.get_game_width() / 2 + 1) as i32;
-        // // bottom
-        // let yl = -((board.get_game_height() / 2 + 1) as i32);
-        // // top
-        // let yu = (board.get_game_height() / 2 + 1) as i32;
-
-        // if ((pixel_x == xl || pixel_x == xu) && (pixel_y <= yu && pixel_y >= yl))
-        //     || (pixel_y == yl || pixel_y == yu) && (pixel_x <= xu && pixel_x >= xl)
-        // {
-        //     offset.0 = offset.0.saturating_add(0xFF);
-        //     offset.1 = offset.1.saturating_add(0xFF);
-        //     offset.2 = offset.2.saturating_add(0xFF);
-        // }
-
-        // // grid
-        // if pixel_x % 30 == 0 || pixel_y % 30 == 0 {
-        //     offset.0 = offset.0.saturating_add(0x10);
-        //     offset.1 = offset.1.saturating_add(0x10);
-        //     offset.2 = offset.2.saturating_add(0x10);
-        // }
-
-        // // brush/selection
-        // if input.last_mouse_pos_on_board.is_some_and(|p| {
-        //     ((pixel_x - p.0).pow(2) + (pixel_y - p.1).pow(2)) < (config.brush_radius as i32).pow(2)
-        // }) {
-        //     offset.0 = offset.0.saturating_add(0x82);
-        //     offset.1 = offset.1.saturating_add(0xA1);
-        //     offset.2 = offset.2.saturating_add(0xAD);
-        // }
-
-        return offset;
-    }
-}
diff --git a/src/sim/lib/marching_squares.rs b/src/sim/lib/marching_squares.rs
new file mode 100644
index 0000000..41d50ee
--- /dev/null
+++ b/src/sim/lib/marching_squares.rs
@@ -0,0 +1,201 @@
+use glam::Vec2;
+
+/**
+0b(tl)(tr)(br)(bl), 0..=15
+
+0 0000 - -
+
+1 0001 BL S → W
+
+2 0010 BR E → S
+
+3 0011 BL BR E → W
+
+4 0100 TR N → E
+
+5 0101 TR BL saddle: N → W, S → E
+
+6 0110 TR BR N → S
+
+7 0111 TR BR BL N → W
+
+8 1000 TL W → N
+
+9 1001 TL BL S → N
+
+10 1010 TL BR saddle: E → N, W → S
+
+11 1011 TL BR BL E → N
+
+12 1100 TL TR W → E
+
+13 1101 TL TR BL S → E
+
+14 1110 TL TR BR W → S
+
+15 1111 - -
+*/
+
+#[inline]
+fn derive_type(tl: bool, tr: bool, br: bool, bl: bool) -> usize {
+    bl as usize | (br as usize) << 1 | (tr as usize) << 2 | (tl as usize) << 3
+}
+
+pub trait Marchable {
+    fn occupied(&self, x: i32, y: i32) -> bool;
+}
+
+pub fn compute_types(marchable: &impl Marchable, w: i32, h: i32) -> Vec<u8> {
+    // TODO could pre-allocate size
+    let mut types = Vec::new();
+    for y in -1..h {
+        // TODO precompute per column
+        for x in -1..w {
+            let tl = marchable.occupied(x, y);
+            let tr = marchable.occupied(x + 1, y);
+            let br = marchable.occupied(x + 1, y + 1);
+            let bl = marchable.occupied(x, y + 1);
+            types.push(derive_type(tl, tr, br, bl) as u8);
+        }
+    }
+    types
+}
+
+#[derive(PartialEq, Eq, Clone, Copy)]
+enum Side {
+    None,
+    N,
+    E,
+    S,
+    W,
+}
+
+const EDGE_COUNT_BY_TYPE: [usize; 16] = [0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 0];
+const EDGE_START_BY_TYPE_BY_IDX: [[Side; 2]; 16] = [
+    [Side::None, Side::None],
+    [Side::S, Side::None],
+    [Side::E, Side::None],
+    [Side::E, Side::None],
+    [Side::N, Side::None],
+    [Side::N, Side::S],
+    [Side::N, Side::None],
+    [Side::N, Side::None],
+    [Side::W, Side::None],
+    [Side::S, Side::None],
+    [Side::E, Side::W],
+    [Side::E, Side::None],
+    [Side::W, Side::None],
+    [Side::S, Side::None],
+    [Side::W, Side::None],
+    [Side::None, Side::None],
+];
+
+const EDGE_END_BY_TYPE: [[Side; 2]; 16] = [
+    [Side::None, Side::None],
+    [Side::W, Side::None],
+    [Side::S, Side::None],
+    [Side::W, Side::None],
+    [Side::E, Side::None],
+    [Side::W, Side::E],
+    [Side::S, Side::None],
+    [Side::W, Side::None],
+    [Side::N, Side::None],
+    [Side::N, Side::None],
+    [Side::N, Side::S],
+    [Side::N, Side::None],
+    [Side::E, Side::None],
+    [Side::E, Side::None],
+    [Side::S, Side::None],
+    [Side::None, Side::None],
+];
+
+fn side_centre(x: i32, y: i32, s: Side) -> Vec2 {
+    let (x, y) = (x as f32, y as f32);
+    match s {
+        Side::N => Vec2::new(x + 0.5, y),
+        Side::E => Vec2::new(x + 1.0, y + 0.5),
+        Side::S => Vec2::new(x + 0.5, y + 1.0),
+        Side::W => Vec2::new(x, y + 0.5),
+        Side::None => panic!("Tried to access None side"),
+    }
+}
+
+fn toward_side(x: i32, y: i32, exit: Side) -> (i32, i32, Side) {
+    match exit {
+        Side::N => (x, y - 1, Side::S),
+        Side::E => (x + 1, y, Side::W),
+        Side::S => (x, y + 1, Side::N),
+        Side::W => (x - 1, y, Side::E),
+        Side::None => panic!("Tried to access None side"),
+    }
+}
+
+// outer is cw, inner ccw
+pub fn marching_squares_vertex_trace(marchable: &impl Marchable, w: i32, h: i32) -> Vec<Vec<Vec2>> {
+    let mut visited = vec![0u8; ((w + 1) * (h + 1)) as usize];
+    let idx = |cx: i32, cy: i32| (((cy + 1) * (w + 1)) + (cx + 1)) as usize;
+
+    let types = compute_types(marchable, w, h);
+    let mut polys = Vec::new();
+
+    for y in -1..h {
+        for x in -1..w {
+            let mut t = types[(x + 1 + (y + 1) * (w + 1)) as usize] as usize;
+            // if there are multiple edges for this type (saddle), try to build a poly for each
+            for e in 0..EDGE_COUNT_BY_TYPE[t] {
+                // if we have already visited this cell FOR this edge, skip
+                if visited[idx(x, y)] & (1 << e) != 0 {
+                    continue;
+                }
+
+                let mut poly = Vec::new();
+                let (mut xi, mut yi, mut ei) = (x, y, e);
+                // keep collecting until we don't connect to an edge
+                loop {
+                    // if we have already visited this cell FOR this edge, skip
+                    if visited[idx(xi, yi)] & (1 << ei) != 0 {
+                        break;
+                    }
+                    // set this on the inner loop since every cell we take on the loop is claimed
+                    visited[idx(xi, yi)] |= 1 << ei;
+
+                    // this edge starts and ends against some side of our cell
+                    let (start, end) = (EDGE_START_BY_TYPE_BY_IDX[t][ei], EDGE_END_BY_TYPE[t][ei]);
+                    poly.push(side_centre(xi, yi, start));
+
+                    // move ourselves into the cell that our edge ends in, unless it's out of the grid
+                    let (nx, ny, entry) = toward_side(xi, yi, end);
+                    // TODO is equality cheaper?
+                    if nx < -1 || nx >= w || ny < -1 || ny >= h {
+                        // exited the board
+                        panic!(
+                            "Expecting closed loop but it's not (off the board)! Came from ({xi}, {yi}, {ei}) to ({nx}, {ny})"
+                        )
+                    }
+
+                    let nt = types[(nx + 1 + (ny + 1) * (w + 1)) as usize] as usize;
+
+                    if EDGE_START_BY_TYPE_BY_IDX[nt][0] == entry {
+                        // there's an edge starting where we entered
+                        xi = nx;
+                        yi = ny;
+                        ei = 0;
+                        t = nt;
+                    } else if EDGE_START_BY_TYPE_BY_IDX[nt][1] == entry {
+                        // entering the other side of the saddle
+                        xi = nx;
+                        yi = ny;
+                        ei = 1;
+                        t = nt;
+                    } else {
+                        panic!(
+                            "Expecting closed loop but it's not! Came from ({xi}, {yi}, {ei}) to ({nx}, {ny})"
+                        )
+                    }
+                }
+                polys.push(poly);
+            }
+        }
+    }
+    polys
+}
diff --git a/src/sim/lib/mod.rs b/src/sim/lib/mod.rs
new file mode 100644
index 0000000..1d802dc
--- /dev/null
+++ b/src/sim/lib/mod.rs
@@ -0,0 +1 @@
+pub mod marching_squares;
diff --git a/src/sim/mod.rs b/src/sim/mod.rs
index dfc99c3..56a8276 100644
--- a/src/sim/mod.rs
+++ b/src/sim/mod.rs
@@ -5,6 +5,7 @@ use crate::{
 
 pub mod cell;
 pub mod cell_sim;
+pub mod lib;
 pub mod rb_sim;
 
 pub fn write_rb_entity_to_world(
diff --git a/src/sim/rb_sim/mod.rs b/src/sim/rb_sim/mod.rs
index 48e4282..0192555 100644
--- a/src/sim/rb_sim/mod.rs
+++ b/src/sim/rb_sim/mod.rs
@@ -2,6 +2,7 @@ pub mod debug_render;
 pub mod rb_entity;
 
 use fxhash::FxHashMap;
+use glam::Vec2;
 use rapier2d::{
     dynamics::{self},
     geometry,
@@ -13,6 +14,8 @@ use crate::{
     config::{CELLS_IN_CHUNK, CHUNK_SIZE, PHYSICS_DELTA_TIME, PIXELS_TO_METRES},
     sim::{
         cell::{cell::Cell, materials::MaterialId},
+        cell_sim::chunk::Chunk,
+        lib::marching_squares::marching_squares_vertex_trace,
         rb_sim::{
             debug_render::{DebugLineBuffer, DebugVertex},
             rb_entity::RbEntity,
@@ -161,6 +164,28 @@ impl RbSimManager {
         }
     }
 
+    fn collider_from_chunk(&self, position: Vec2, chunk: &Chunk) -> geometry::Collider {
+        let mut paths = marching_squares_vertex_trace(chunk, CHUNK_SIZE, CHUNK_SIZE);
+        let mut path: Vec<Vec2> = paths
+            // NAIVE, using the second and assuming it's the outer path
+            .swap_remove(0)
+            .iter()
+            .map(|v| v / PIXELS_TO_METRES)
+            .collect();
+        // close the loop
+        let first = (*path.first().unwrap()).clone();
+        path.push(first);
+
+        geometry::ColliderBuilder::polyline(path, None)
+            .translation(position / PIXELS_TO_METRES)
+            .build()
+    }
+
+    pub fn test_add_collider_from_chunk(&mut self, position: Vec2, chunk: &Chunk) {
+        let collider = self.collider_from_chunk(position, chunk);
+        self.physics_manager.collider_set.insert(collider);
+    }
+
     pub fn test(&mut self) {
         /* Create the ground. */
         let collider =