parallelization

6 files changed, 89 insertions, 40 deletions

diff --git a/src/main.rs b/src/main.rs
index b048122..313a7a8 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -7,6 +7,7 @@ use egui::Id;
 use egui_wgpu::{RendererOptions, ScreenDescriptor};
 use egui_winit::egui::{self, Context};
 use pixels::{Pixels, ScalingMode, SurfaceTexture};
+use rand::random_range;
 use std::time::{Duration, Instant};
 use winit::{
     application::ApplicationHandler,
@@ -30,10 +31,10 @@ pub type Error = Box<dyn std::error::Error>;
 pub type Result<T> = std::result::Result<T, Error>;
 
 struct Config {
-    show_ticks: bool,
     fps: u16,
     brush_radius: u8,
     brush_material: MaterialId,
+    use_threading: bool,
 }
 
 struct Input {
@@ -118,7 +119,7 @@ impl Default for App {
 
             config: Config {
                 fps: 120,
-                show_ticks: false,
+                use_threading: true,
                 brush_radius: 10,
                 brush_material: MaterialId::Sand,
             },
@@ -270,24 +271,26 @@ impl ApplicationHandler for App {
                         // 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 {
-                                // brush/selection
+                                let r = random_range(0.0..1.0);
                                 if ((x - lm.0).pow(2) + (y - lm.1).pow(2))
                                     < (self.config.brush_radius as i32).pow(2)
+                                    && r > 0.9
                                 {
+                                    let mut cell = Cell::from_material(self.config.brush_material);
+                                    cell.flags = (self.sim_seqno as u8) & 0b1;
                                     world.set_cell_from_game_position(
-                                        x,
-                                        y,
-                                        Cell::from_material(self.config.brush_material),
+                                        x, y, cell, // wake the chunk
+                                        false,
                                     );
                                 }
                             }
                         }
                     }
 
-                    // TODO check if we need to run another sim tick given the sim speed
+                    // TODO check if we need to run another sim tick given the sim speed + delta_time
                     // SIM logic
                     if !self.sim_paused || self.ignore_pause_next_tick {
-                        sim_tick(world, self.sim_seqno);
+                        sim_tick(world, self.sim_seqno, self.config.use_threading);
                         self.sim_seqno += 1;
                         self.ignore_pause_next_tick = false;
                     }
diff --git a/src/sim/chunk.rs b/src/sim/chunk.rs
index 154cf82..cf4179a 100644
--- a/src/sim/chunk.rs
+++ b/src/sim/chunk.rs
@@ -5,6 +5,7 @@ use crate::{
 
 pub struct Chunk {
     pub cells: Box<[Cell; CELLS_IN_CHUNK as usize]>,
+    pub sleeping: bool,
 }
 
 impl Chunk {
@@ -20,6 +21,7 @@ impl Chunk {
     pub fn void() -> Self {
         Chunk {
             cells: Box::new([Cell::void(); CELLS_IN_CHUNK]),
+            sleeping: true,
         }
     }
 }
diff --git a/src/sim/materials/water.rs b/src/sim/materials/water.rs
index 65782dd..d76ec5b 100644
--- a/src/sim/materials/water.rs
+++ b/src/sim/materials/water.rs
@@ -25,6 +25,17 @@ pub fn sim_update(ctx: &mut UpdateCtx) {
         return;
     }
 
+    // if we can't move left, just move right
+    if !can_move_left {
+        ctx.candidates_swap(&[(1, 0)]);
+        return;
+    }
+    // and vice versa
+    if !can_move_right {
+        ctx.candidates_swap(&[(-1, 0)]);
+        return;
+    }
+
     // find the closest hole within 20 pixels (TODO optimize)
     // a hole is any space below us with a lesser density
     // prevents equidistance stuck state
@@ -35,9 +46,6 @@ pub fn sim_update(ctx: &mut UpdateCtx) {
         } else {
             -starting_side
         };
-        if (side == 1 && !can_move_right) || (side == -1 && !can_move_left) {
-            continue;
-        }
 
         let offset = side * (1 + i / 2);
         let hole_target = ctx.get_cell(offset, 1);
diff --git a/src/sim/sim.rs b/src/sim/sim.rs
index 5cd065e..6e0029e 100644
--- a/src/sim/sim.rs
+++ b/src/sim/sim.rs
@@ -1,4 +1,6 @@
-use std::marker::PhantomData;
+use std::{collections::HashMap, marker::PhantomData};
+
+use rayon::iter::{IntoParallelRefIterator, ParallelIterator};
 
 use crate::{
     config::CHUNK_SIZE,
@@ -25,6 +27,8 @@ impl<'a> ChunkAccess<'a> {
     }
 }
 
+unsafe impl Sync for ChunkAccess<'_> {}
+
 pub struct UpdateCtx<'a, 'b, 'c> {
     pub chunks: &'a mut [Option<&'b mut Chunk>; 9],
     pub seqno: u64,
@@ -87,6 +91,12 @@ impl UpdateCtx<'_, '_, '_> {
         let x = self.x + dx;
         let y = self.y + dy;
         set_cell(self.chunks, x, y, cell);
+        // wake all the chunks
+        self.chunks.iter_mut().for_each(|c| {
+            if let Some(chunk) = c {
+                chunk.sleeping = false;
+            }
+        });
     }
 
     pub fn candidates_swap(&mut self, candidates: &[(i32, i32)]) -> bool {
@@ -155,37 +165,57 @@ const NEIGHBORHOOD_OFFSETS: [(i32, i32); 9] = [
     (1, 1),
 ];
 
-pub fn sim_tick(world: &mut World, seqno: u64) {
+pub fn sim_tick(world: &mut World, seqno: u64, use_threading: bool) {
     puffin::profile_function!();
-    let mut update_groups: [Vec<(i32, i32)>; 9] = Default::default();
 
-    // assign a color to each chunk s.t. every chunk is surrounded by <= 8 chunks of different colors
+    let mut columns: HashMap<i32, Vec<i32>> = HashMap::new();
+    for &(cx, cy) in world.chunk_position_to_chunk_idx.keys() {
+        columns.entry(cx).or_default().push(cy);
+    }
+
+    // color columns s.t. columns of same color are separated by two columns
+    // and sort the column bottom-to-top
     // --------------------
     // | 0, 1, 2, 0, 1, 2 |
-    // | 3, 4, 5, 3, 4, 5 |
-    // | 6, 7, 8, 6, 7, 8 |
     // | 0, 1, 2, 0, 1, 2 |
-    // | 3, 4, 5, 3, 4, 5 |
-    // | 6, 7, 8, 6, 7, 8 |
+    // | 0, 1, 2, 0, 1, 2 |
     // --------------------
-
-    for (&(cx, cy), _) in &world.chunk_position_to_chunk_idx {
-        let color = (cx.rem_euclid(3) * 3 + cy.rem_euclid(3)) as usize;
-        update_groups[color].push((cx, cy));
+    let mut columns_by_color: [Vec<(i32, Vec<i32>)>; 3] = Default::default();
+    for (cx, mut cys) in columns {
+        cys.sort_unstable_by(|a, b| b.cmp(a));
+        columns_by_color[cx.rem_euclid(3) as usize].push((cx, cys));
     }
 
-    for group in &update_groups {
-        let access = ChunkAccess::new(&mut world.chunks);
-        // TODO this can be parallelized since they will never share neighbours
-        for &(cx, cy) in group {
-            let mut chunks: [Option<&mut Chunk>; 9] = NEIGHBORHOOD_OFFSETS.map(|(dx, dy)| {
-                world
-                    .chunk_position_to_chunk_idx
-                    .get(&(cx + dx, cy + dy))
-                    .map(|&idx| unsafe { access.get(idx) })
-            });
+    let access = ChunkAccess::new(&mut world.chunks);
 
-            sim_tick_chunk(&mut chunks, seqno);
-        }
+    for color in &columns_by_color {
+        puffin::profile_scope!("chunk_color");
+
+        let chunk_closure = |(cx, cys): &(i32, Vec<i32>)| {
+            let cx = *cx;
+            for &cy in cys {
+                let mut chunks: [Option<&mut Chunk>; 9] = NEIGHBORHOOD_OFFSETS.map(|(dx, dy)| {
+                    world
+                        .chunk_position_to_chunk_idx
+                        .get(&(cx + dx, cy + dy))
+                        .map(|&idx| unsafe { access.get(idx) })
+                });
+
+                if let Some(target) = &mut chunks[4] {
+                    if target.sleeping {
+                        continue;
+                    }
+                    target.sleeping = true;
+                }
+
+                sim_tick_chunk(&mut chunks, seqno);
+            }
+        };
+
+        if use_threading {
+            color.par_iter().for_each(chunk_closure);
+        } else {
+            color.iter().for_each(chunk_closure);
+        };
     }
 }
diff --git a/src/sim/world.rs b/src/sim/world.rs
index 3c7b05b..7775744 100644
--- a/src/sim/world.rs
+++ b/src/sim/world.rs
@@ -36,10 +36,18 @@ impl World {
     }
 
     // VERY EXPENSIVE
-    pub fn set_cell_from_game_position(&mut self, x: i32, y: i32, cell: Cell) -> () {
+    pub fn set_cell_from_game_position(
+        &mut self,
+        x: i32,
+        y: i32,
+        cell: Cell,
+        sleeping: bool,
+    ) -> () {
         let ((cx, cy), (dx, dy)) = World::split_game_position(x, y);
         if let Some(&idx) = self.chunk_position_to_chunk_idx.get(&(cx, cy)) {
             self.chunks[idx].set_cell_at_local_position(dx, dy, cell);
+            // this is a temporary hack
+            self.chunks[idx].sleeping = sleeping;
         }
     }
 
@@ -56,7 +64,7 @@ impl World {
         };
 
         for y in -10..10 {
-            for x in -10..10 {
+            for x in -50..50 {
                 world.insert(x, y, Chunk::void());
             }
         }
diff --git a/src/ui.rs b/src/ui.rs
index 9c8f6c3..9d13f74 100644
--- a/src/ui.rs
+++ b/src/ui.rs
@@ -40,12 +40,10 @@ pub fn draw_egui<'a>(
         });
 
     ui.add(egui::Slider::new(&mut config.fps, 1..=1000).text("Max FPS"));
-    ui.checkbox(&mut config.show_ticks, "Visualize ticks");
+    ui.checkbox(&mut config.use_threading, "Use multithreading");
     ui.label(format!("Real FPS: {}", diagnostics.fps));
     ui.heading("Camera");
     ui.add(egui::Slider::new(&mut camera.zoom, 0.0..=10.0).text("Zoom"));
-    ui.add(egui::Slider::new(&mut camera.x, -1000.0..=1000.0).text("X"));
-    ui.add(egui::Slider::new(&mut camera.y, -1000.0..=1000.0).text("Y"));
     ui.heading("Input");
 
     input.last_mouse_pos_on_screen.map(|p| {