MVP of marching squares

7 files changed, 242 insertions, 52 deletions

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 =