# HG changeset patch # User unC0Rr # Date 1675090214 -3600 # Node ID 6e22f4390b7e2a76811736a76b38572aa3fe68dd # Parent b4809653f9d6ab3214e2fc051d45e2d3f11d8330 Add basics of wavefront collapse algorithm diff -r b4809653f9d6 -r 6e22f4390b7e rust/land2d/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 { pixels: vec2d::Vec2D, play_box: Rect, mask: SizeMask, } -impl Land2D { +impl Land2D { 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>(&mut self, point: Point, f: F) -> U { self.map(point.y, point.x, f) } diff -r b4809653f9d6 -r 6e22f4390b7e rust/landgen/Cargo.toml --- 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 "] -edition = "2018" +edition = "2021" [dependencies] integral-geometry = { path = "../integral-geometry" } diff -r b4809653f9d6 -r 6e22f4390b7e rust/landgen/src/lib.rs --- 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 { @@ -11,7 +12,7 @@ skip_bezier: bool, } -impl LandGenerationParameters { +impl LandGenerationParameters { pub fn new( zero: T, basic: T, @@ -38,17 +39,9 @@ } pub trait LandGenerator { - fn generate_land>( + fn generate_land>( &self, parameters: &LandGenerationParameters, random_numbers: &mut I, ) -> land2d::Land2D; } - -#[cfg(test)] -mod tests { - #[test] - fn it_works() { - assert_eq!(2 + 2, 4); - } -} diff -r b4809653f9d6 -r 6e22f4390b7e rust/landgen/src/outline.rs --- 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(&self, land: &mut Land2D, value: T) { + pub fn draw(&self, land: &mut Land2D, value: T) { for segment in self.segments_iter() { land.draw_line(segment, value); } diff -r b4809653f9d6 -r 6e22f4390b7e rust/landgen/src/template_based.rs --- 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>( + fn generate_land>( &self, parameters: &LandGenerationParameters, random_numbers: &mut I, diff -r b4809653f9d6 -r 6e22f4390b7e rust/landgen/src/wavefront_collapse.rs --- /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>, +} + +impl WavefrontCollapse { + pub fn generate_map, F: FnOnce(&mut Land2D)>( + &mut self, + map_size: &Size, + seed_fn: F, + random_numbers: &mut I, + ) -> Land2D { + 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>( + &self, + land: &mut Land2D, + 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(¤t_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, 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()); + } +} diff -r b4809653f9d6 -r 6e22f4390b7e rust/lib-hwengine-future/src/lib.rs --- 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] diff -r b4809653f9d6 -r 6e22f4390b7e rust/vec2d/src/lib.rs --- 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 { data: Vec, size: Size,