Switch to Vec2D in wavefront algorithm transitional_engine
authorunC0Rr
Wed, 01 Feb 2023 10:58:45 +0100
branchtransitional_engine
changeset 15943 c5684cc62de8
parent 15942 6e22f4390b7e
child 15944 c571d4b8879c
Switch to Vec2D in wavefront algorithm
rust/land2d/src/lib.rs
rust/landgen/Cargo.toml
rust/landgen/src/wavefront_collapse.rs
rust/landgen/src/wavefront_collapse/generator.rs
rust/landgen/src/wavefront_collapse/mod.rs
rust/landgen/src/wavefront_collapse/tile_image.rs
rust/landgen/src/wavefront_collapse/wavefront_collapse.rs
rust/vec2d/src/lib.rs
--- a/rust/land2d/src/lib.rs	Mon Jan 30 15:50:14 2023 +0100
+++ b/rust/land2d/src/lib.rs	Wed Feb 01 10:58:45 2023 +0100
@@ -19,7 +19,7 @@
         let play_box = Rect::from_size(top_left, *play_size);
         Self {
             play_box,
-            pixels: vec2d::Vec2D::new(real_size.size(), fill_value),
+            pixels: vec2d::Vec2D::new(&real_size.size(), fill_value),
             mask: real_size.to_mask(),
         }
     }
--- a/rust/landgen/Cargo.toml	Mon Jan 30 15:50:14 2023 +0100
+++ b/rust/landgen/Cargo.toml	Wed Feb 01 10:58:45 2023 +0100
@@ -7,4 +7,5 @@
 [dependencies]
 integral-geometry = { path = "../integral-geometry" }
 land2d = { path = "../land2d" }
+vec2d = { path = "../vec2d" }
 itertools = "0.7.8"
--- a/rust/landgen/src/wavefront_collapse.rs	Mon Jan 30 15:50:14 2023 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,150 +0,0 @@
-use integral_geometry::Size;
-use land2d::Land2D;
-use std::collections::HashMap;
-
-#[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
-enum Tile {
-    Empty,
-    Outside,
-    Numbered(u32),
-}
-
-impl Tile {
-    fn is(&self, i: u32) -> bool {
-        *self == Tile::Numbered(i)
-    }
-
-    fn is_empty(&self) -> bool {
-        match self {
-            Tile::Empty => true,
-            Tile::Outside => true,
-            _ => false,
-        }
-    }
-
-    fn is_empty_or(&self, i: u32) -> bool {
-        match self {
-            Tile::Numbered(n) => *n == i,
-            Tile::Empty => true,
-            _ => false,
-        }
-    }
-
-    fn is_void_or(&self, i: u32) -> bool {
-        match self {
-            Tile::Numbered(n) => *n == i,
-            _ => true,
-        }
-    }
-}
-
-impl Default for Tile {
-    fn default() -> Self {
-        Tile::Outside
-    }
-}
-
-struct CollapseRule {
-    to_tile: Tile,
-    condition: fn([Tile; 4]) -> bool,
-}
-
-#[derive(Default)]
-struct WavefrontCollapse {
-    rules: HashMap<Tile, Vec<CollapseRule>>,
-}
-
-impl WavefrontCollapse {
-    pub fn generate_map<I: Iterator<Item = u32>, F: FnOnce(&mut Land2D<Tile>)>(
-        &mut self,
-        map_size: &Size,
-        seed_fn: F,
-        random_numbers: &mut I,
-    ) -> Land2D<Tile> {
-        let mut land = Land2D::new(map_size, Tile::Empty);
-
-        seed_fn(&mut land);
-
-        while self.collapse_step(&mut land, random_numbers) {}
-
-        land
-    }
-
-    fn add_rule(&mut self, from_tile: Tile, to_tile: Tile, condition: fn([Tile; 4]) -> bool) {
-        let rule = CollapseRule { to_tile, condition };
-        self.rules
-            .entry(from_tile)
-            .or_insert_with(Vec::new)
-            .push(rule);
-    }
-
-    fn collapse_step<I: Iterator<Item = u32>>(
-        &self,
-        land: &mut Land2D<Tile>,
-        random_numbers: &mut I,
-    ) -> bool {
-        let mut collapse_occurred = false;
-        for x in 0..land.width() {
-            for y in 0..land.height() {
-                let current_tile = land.map(y as i32, x as i32, |p| *p);
-
-                if let Some(rules) = self.rules.get(&current_tile) {
-                    for rule in rules
-                        .iter()
-                        .cycle()
-                        .skip(
-                            random_numbers.next().unwrap_or_default() as usize % (rules.len() + 1),
-                        )
-                        .take(rules.len())
-                    {
-                        let neighbors = self.get_neighbors(&land, x, y);
-                        let have_neighbors = neighbors.iter().any(|t| !t.is_empty());
-                        if have_neighbors && (rule.condition)(neighbors) {
-                            land.map(y as i32, x as i32, |p| *p = rule.to_tile);
-                            collapse_occurred = true;
-                            break;
-                        }
-                    }
-                }
-            }
-        }
-
-        collapse_occurred
-    }
-
-    fn get_neighbors(&self, land: &Land2D<Tile>, x: usize, y: usize) -> [Tile; 4] {
-        [
-            land.get(y as i32, x as i32 + 1),
-            land.get(y as i32 + 1, x as i32),
-            land.get(y as i32, x as i32 - 1),
-            land.get(y as i32 - 1, x as i32),
-        ]
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use super::{CollapseRule, Tile, WavefrontCollapse};
-    use integral_geometry::Size;
-    use land2d::Land2D;
-    use std::collections::HashMap;
-
-    #[test]
-    fn test_wavefront_collapse() {
-        let size = Size::new(4, 4);
-        let mut rnd = [0u32; 64].into_iter();
-        let mut wfc = WavefrontCollapse::default();
-
-        let empty_land = Land2D::new(&size, Tile::Empty);
-        let no_rules_land = wfc.generate_map(&size, |l| {}, &mut rnd);
-
-        assert_eq!(empty_land.raw_pixels(), no_rules_land.raw_pixels());
-
-        wfc.add_rule(Tile::Empty, Tile::Numbered(0), |neighbors| {
-            neighbors.iter().filter(|&n| *n == Tile::Empty).count() >= 2
-        });
-        let ruled_map = wfc.generate_map(&size, |l| {}, &mut rnd);
-
-        assert_eq!(ruled_map.raw_pixels(), empty_land.raw_pixels());
-    }
-}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/landgen/src/wavefront_collapse/generator.rs	Wed Feb 01 10:58:45 2023 +0100
@@ -0,0 +1,31 @@
+use super::wavefront_collapse::WavefrontCollapse;
+use super::tile_image::TileImage;
+use crate::{LandGenerationParameters, LandGenerator};
+
+pub struct WavefrontCollapseLandGenerator {
+    wfc: WavefrontCollapse,
+    tiles: Vec<TileImage>,
+}
+
+impl WavefrontCollapseLandGenerator {
+    pub fn new() -> Self {
+        Self {
+            wfc: WavefrontCollapse::default(),
+            tiles: Vec::new()
+        }
+    }
+
+    pub fn load_template() {
+
+    }
+}
+
+impl LandGenerator for WavefrontCollapseLandGenerator {
+    fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(
+        &self,
+        parameters: &LandGenerationParameters<T>,
+        random_numbers: &mut I,
+    ) -> land2d::Land2D<T> {
+        todo!()
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/landgen/src/wavefront_collapse/mod.rs	Wed Feb 01 10:58:45 2023 +0100
@@ -0,0 +1,3 @@
+pub mod generator;
+mod tile_image;
+mod wavefront_collapse;
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/landgen/src/wavefront_collapse/tile_image.rs	Wed Feb 01 10:58:45 2023 +0100
@@ -0,0 +1,34 @@
+use land2d::Land2D;
+use std::rc::Rc;
+
+pub struct TileImage {
+    image: Rc<Land2D<u8>>,
+    flip: bool,
+    mirror: bool,
+}
+
+impl TileImage {
+    pub fn new(flip: bool, mirror: bool) -> Self {
+        Self {
+            image: todo!(),
+            flip,
+            mirror,
+        }
+    }
+
+    pub fn mirrored(&self) -> Self {
+        Self {
+            image: self.image.clone(),
+            flip: self.flip,
+            mirror: !self.mirror
+        }
+    }
+
+    pub fn flipped(&self) -> Self {
+        Self {
+            image: self.image.clone(),
+            flip: !self.flip,
+            mirror: self.mirror
+        }
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/landgen/src/wavefront_collapse/wavefront_collapse.rs	Wed Feb 01 10:58:45 2023 +0100
@@ -0,0 +1,149 @@
+use integral_geometry::Size;
+use vec2d::Vec2D;
+use std::collections::HashMap;
+
+#[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)]
+pub enum Tile {
+    Empty,
+    Outside,
+    Numbered(u32),
+}
+
+impl Tile {
+    fn is(&self, i: u32) -> bool {
+        *self == Tile::Numbered(i)
+    }
+
+    fn is_empty(&self) -> bool {
+        match self {
+            Tile::Empty => true,
+            Tile::Outside => true,
+            _ => false,
+        }
+    }
+
+    fn is_empty_or(&self, i: u32) -> bool {
+        match self {
+            Tile::Numbered(n) => *n == i,
+            Tile::Empty => true,
+            _ => false,
+        }
+    }
+
+    fn is_void_or(&self, i: u32) -> bool {
+        match self {
+            Tile::Numbered(n) => *n == i,
+            _ => true,
+        }
+    }
+}
+
+impl Default for Tile {
+    fn default() -> Self {
+        Tile::Outside
+    }
+}
+
+struct CollapseRule {
+    to_tile: Tile,
+    condition: fn([Tile; 4]) -> bool,
+}
+
+#[derive(Default)]
+pub struct WavefrontCollapse {
+    rules: HashMap<Tile, Vec<CollapseRule>>,
+}
+
+impl WavefrontCollapse {
+    pub fn generate_map<I: Iterator<Item = u32>, F: FnOnce(&mut Vec2D<Tile>)>(
+        &mut self,
+        map_size: &Size,
+        seed_fn: F,
+        random_numbers: &mut I,
+        ) -> Vec2D<Tile> {
+        let mut land = Vec2D::new(&map_size, Tile::Empty);
+
+        seed_fn(&mut land);
+
+        while self.collapse_step(&mut land, random_numbers) {}
+
+        land
+    }
+
+    fn add_rule(&mut self, from_tile: Tile, to_tile: Tile, condition: fn([Tile; 4]) -> bool) {
+        let rule = CollapseRule { to_tile, condition };
+        self.rules
+            .entry(from_tile)
+            .or_insert_with(Vec::new)
+            .push(rule);
+    }
+
+    fn collapse_step<I: Iterator<Item = u32>>(
+        &self,
+        land: &mut Vec2D<Tile>,
+        random_numbers: &mut I,
+    ) -> bool {
+        let mut collapse_occurred = false;
+        for x in 0..land.width() {
+            for y in 0..land.height() {
+                let current_tile = land.get(y, x).expect("valid iteration range");
+
+                if let Some(rules) = self.rules.get(&current_tile) {
+                    for rule in rules
+                        .iter()
+                        .cycle()
+                        .skip(
+                            random_numbers.next().unwrap_or_default() as usize % (rules.len() + 1),
+                        )
+                        .take(rules.len())
+                    {
+                        let neighbors = self.get_neighbors(&land, x, y);
+                        let have_neighbors = neighbors.iter().any(|t| !t.is_empty());
+                        if have_neighbors && (rule.condition)(neighbors) {
+                            *land.get_mut(y, x).expect("valid iteration range") = rule.to_tile;
+                            collapse_occurred = true;
+                            break;
+                        }
+                    }
+                }
+            }
+        }
+
+        collapse_occurred
+    }
+
+    fn get_neighbors(&self, land: &Vec2D<Tile>, x: usize, y: usize) -> [Tile; 4] {
+        [
+            land.get(y, x + 1).map(|p| *p).unwrap_or_default(),
+            land.get(y + 1, x).map(|p| *p).unwrap_or_default(),
+            land.get(y, x.wrapping_sub(1)).map(|p| *p).unwrap_or_default(),
+            land.get(y.wrapping_sub(1), x).map(|p| *p).unwrap_or_default(),
+        ]
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::{Tile, WavefrontCollapse};
+    use integral_geometry::Size;
+    use vec2d::Vec2D;
+
+    #[test]
+    fn test_wavefront_collapse() {
+        let size = Size::new(4, 4);
+        let mut rnd = [0u32; 64].into_iter();
+        let mut wfc = WavefrontCollapse::default();
+
+        let empty_land = Vec2D::new(&size, Tile::Empty);
+        let no_rules_land = wfc.generate_map(&size, |_| {}, &mut rnd);
+
+        assert_eq!(empty_land.as_slice(), no_rules_land.as_slice());
+
+        wfc.add_rule(Tile::Empty, Tile::Numbered(0), |neighbors| {
+            neighbors.iter().filter(|&n| *n == Tile::Empty).count() >= 2
+        });
+        let ruled_map = wfc.generate_map(&size, |_| {}, &mut rnd);
+
+        assert_eq!(ruled_map.as_slice(), empty_land.as_slice());
+    }
+}
--- a/rust/vec2d/src/lib.rs	Mon Jan 30 15:50:14 2023 +0100
+++ b/rust/vec2d/src/lib.rs	Wed Feb 01 10:58:45 2023 +0100
@@ -1,8 +1,8 @@
+use integral_geometry::Size;
 use std::{
     ops::{Index, IndexMut},
-    slice::SliceIndex
+    slice::SliceIndex,
 };
-use integral_geometry::Size;
 
 #[derive(Debug)]
 pub struct Vec2D<T> {
@@ -34,7 +34,7 @@
     }
 }
 
-impl <T> Vec2D<T> {
+impl<T> Vec2D<T> {
     #[inline]
     pub fn width(&self) -> usize {
         self.size.width
@@ -52,8 +52,11 @@
 }
 
 impl<T: Copy> Vec2D<T> {
-    pub fn new(size: Size, value: T) -> Self {
-        Self { size, data: vec![value; size.area()] }
+    pub fn new(size: &Size, value: T) -> Self {
+        Self {
+            size: *size,
+            data: vec![value; size.area()],
+        }
     }
 
     #[inline]
@@ -68,21 +71,41 @@
 
     #[inline]
     pub fn get(&self, row: usize, column: usize) -> Option<&<usize as SliceIndex<[T]>>::Output> {
-        self.data.get(row * self.width() + column)
+        if row < self.height() && column < self.width() {
+            Some(unsafe { self.data.get_unchecked(row * self.width() + column) })
+        } else {
+            None
+        }
     }
 
     #[inline]
-    pub fn get_mut(&mut self, row: usize, column: usize) -> Option<&mut <usize as SliceIndex<[T]>>::Output> {
-        self.data.get_mut(row * self.size.width + column)
+    pub fn get_mut(
+        &mut self,
+        row: usize,
+        column: usize,
+    ) -> Option<&mut <usize as SliceIndex<[T]>>::Output> {
+        if row < self.height() && column < self.width() {
+            Some(unsafe { self.data.get_unchecked_mut(row * self.size.width + column) })
+        } else {
+            None
+        }
     }
 
     #[inline]
-    pub unsafe fn get_unchecked(&self, row: usize, column: usize) -> &<usize as SliceIndex<[T]>>::Output {
+    pub unsafe fn get_unchecked(
+        &self,
+        row: usize,
+        column: usize,
+    ) -> &<usize as SliceIndex<[T]>>::Output {
         self.data.get_unchecked(row * self.width() + column)
     }
 
     #[inline]
-    pub unsafe fn get_unchecked_mut(&mut self, row: usize, column: usize) -> &mut <usize as SliceIndex<[T]>>::Output {
+    pub unsafe fn get_unchecked_mut(
+        &mut self,
+        row: usize,
+        column: usize,
+    ) -> &mut <usize as SliceIndex<[T]>>::Output {
         self.data.get_unchecked_mut(row * self.size.width + column)
     }
 
@@ -99,10 +122,7 @@
 
     #[inline]
     pub unsafe fn as_bytes(&self) -> &[u8] {
-        use std::{
-            slice,
-            mem
-        };
+        use std::{mem, slice};
 
         slice::from_raw_parts(
             self.data.as_ptr() as *const u8,