Add basics of wavefront collapse algorithm transitional_engine
authorunC0Rr
Mon, 30 Jan 2023 15:50:14 +0100
branchtransitional_engine
changeset 15942 6e22f4390b7e
parent 15935 b4809653f9d6
child 15943 c5684cc62de8
Add basics of wavefront collapse algorithm
rust/land2d/src/lib.rs
rust/landgen/Cargo.toml
rust/landgen/src/lib.rs
rust/landgen/src/outline.rs
rust/landgen/src/template_based.rs
rust/landgen/src/wavefront_collapse.rs
rust/lib-hwengine-future/src/lib.rs
rust/vec2d/src/lib.rs
--- a/rust/land2d/src/lib.rs	Wed Jan 04 15:26:30 2023 +0100
+++ b/rust/land2d/src/lib.rs	Mon Jan 30 15:50:14 2023 +0100
@@ -2,13 +2,14 @@
 use vec2d::Vec2D;
 use integral_geometry::{ArcPoints, EquidistantPoints, Line, Point, PotSize, Rect, Size, SizeMask};
 
+#[derive(Debug)]
 pub struct Land2D<T> {
     pixels: vec2d::Vec2D<T>,
     play_box: Rect,
     mask: SizeMask,
 }
 
-impl<T: Copy + PartialEq> Land2D<T> {
+impl<T: Copy + PartialEq + Default> Land2D<T> {
     pub fn new(play_size: &Size, fill_value: T) -> Self {
         let real_size = play_size.next_power_of_two();
         let top_left = Point::new(
@@ -99,6 +100,18 @@
     }
 
     #[inline]
+    pub fn get(&self, y: i32, x: i32) -> T {
+        if self.is_valid_coordinate(x, y) {
+            unsafe {
+                // hey, I just checked that coordinates are valid!
+                *self.pixels.get_unchecked(y as usize, x as usize)
+            }
+        } else {
+            T::default()
+        }
+    }
+
+    #[inline]
     pub fn map_point<U: Default, F: FnOnce(&mut T) -> U>(&mut self, point: Point, f: F) -> U {
         self.map(point.y, point.x, f)
     }
--- a/rust/landgen/Cargo.toml	Wed Jan 04 15:26:30 2023 +0100
+++ b/rust/landgen/Cargo.toml	Mon Jan 30 15:50:14 2023 +0100
@@ -2,7 +2,7 @@
 name = "landgen"
 version = "0.1.0"
 authors = ["Andrey Korotaev <a.korotaev@hedgewars.org>"]
-edition = "2018"
+edition = "2021"
 
 [dependencies]
 integral-geometry = { path = "../integral-geometry" }
--- a/rust/landgen/src/lib.rs	Wed Jan 04 15:26:30 2023 +0100
+++ b/rust/landgen/src/lib.rs	Mon Jan 30 15:50:14 2023 +0100
@@ -1,6 +1,7 @@
 mod outline;
 pub mod outline_template;
 pub mod template_based;
+pub mod wavefront_collapse;
 
 #[derive(Clone, Copy)]
 pub struct LandGenerationParameters<T> {
@@ -11,7 +12,7 @@
     skip_bezier: bool,
 }
 
-impl<T: Copy + PartialEq> LandGenerationParameters<T> {
+impl<T: Copy + PartialEq + Default> LandGenerationParameters<T> {
     pub fn new(
         zero: T,
         basic: T,
@@ -38,17 +39,9 @@
 }
 
 pub trait LandGenerator {
-    fn generate_land<T: Copy + PartialEq, I: Iterator<Item = u32>>(
+    fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(
         &self,
         parameters: &LandGenerationParameters<T>,
         random_numbers: &mut I,
     ) -> land2d::Land2D<T>;
 }
-
-#[cfg(test)]
-mod tests {
-    #[test]
-    fn it_works() {
-        assert_eq!(2 + 2, 4);
-    }
-}
--- a/rust/landgen/src/outline.rs	Wed Jan 04 15:26:30 2023 +0100
+++ b/rust/landgen/src/outline.rs	Mon Jan 30 15:50:14 2023 +0100
@@ -287,7 +287,7 @@
         }
     }
 
-    pub fn draw<T: Copy + PartialEq>(&self, land: &mut Land2D<T>, value: T) {
+    pub fn draw<T: Copy + PartialEq + Default>(&self, land: &mut Land2D<T>, value: T) {
         for segment in self.segments_iter() {
             land.draw_line(segment, value);
         }
--- a/rust/landgen/src/template_based.rs	Wed Jan 04 15:26:30 2023 +0100
+++ b/rust/landgen/src/template_based.rs	Mon Jan 30 15:50:14 2023 +0100
@@ -16,7 +16,7 @@
 }
 
 impl LandGenerator for TemplatedLandGenerator {
-    fn generate_land<T: Copy + PartialEq, I: Iterator<Item = u32>>(
+    fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(
         &self,
         parameters: &LandGenerationParameters<T>,
         random_numbers: &mut I,
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rust/landgen/src/wavefront_collapse.rs	Mon Jan 30 15:50:14 2023 +0100
@@ -0,0 +1,150 @@
+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());
+    }
+}
--- a/rust/lib-hwengine-future/src/lib.rs	Wed Jan 04 15:26:30 2023 +0100
+++ b/rust/lib-hwengine-future/src/lib.rs	Mon Jan 30 15:50:14 2023 +0100
@@ -110,8 +110,8 @@
 }
 
 #[no_mangle]
-pub extern "C" fn land_get(game_field: &mut GameField, x: i32, y: i32) -> u16 {
-    game_field.collision.map(y, x, |p| *p)
+pub extern "C" fn land_get(game_field: &GameField, x: i32, y: i32) -> u16 {
+    game_field.collision.get(y, x)
 }
 
 #[no_mangle]
@@ -138,8 +138,8 @@
 }
 
 #[no_mangle]
-pub extern "C" fn land_pixel_get(game_field: &mut GameField, x: i32, y: i32) -> u32 {
-    game_field.pixels.map(y, x, |p| *p)
+pub extern "C" fn land_pixel_get(game_field: &GameField, x: i32, y: i32) -> u32 {
+    game_field.pixels.get(y, x)
 }
 
 #[no_mangle]
--- a/rust/vec2d/src/lib.rs	Wed Jan 04 15:26:30 2023 +0100
+++ b/rust/vec2d/src/lib.rs	Mon Jan 30 15:50:14 2023 +0100
@@ -4,6 +4,7 @@
 };
 use integral_geometry::Size;
 
+#[derive(Debug)]
 pub struct Vec2D<T> {
     data: Vec<T>,
     size: Size,