# HG changeset patch # User unC0Rr # Date 1675431873 -3600 # Node ID e82de0410da59ebb0634c9ec55437fda310cec6e # Parent 8f093b1b18bca0e7dea0e58b0a8ffccd7a7a1b6d Rework how rules are defined, add transformations for tiles diff -r 8f093b1b18bc -r e82de0410da5 rust/landgen/src/template_based.rs --- a/rust/landgen/src/template_based.rs Thu Feb 02 08:41:31 2023 +0100 +++ b/rust/landgen/src/template_based.rs Fri Feb 03 14:44:33 2023 +0100 @@ -2,7 +2,6 @@ outline::OutlinePoints, outline_template::OutlineTemplate, LandGenerationParameters, LandGenerator, }; -use integral_geometry::{Point, Size}; use land2d::Land2D; pub struct TemplatedLandGenerator { diff -r 8f093b1b18bc -r e82de0410da5 rust/landgen/src/wavefront_collapse/generator.rs --- a/rust/landgen/src/wavefront_collapse/generator.rs Thu Feb 02 08:41:31 2023 +0100 +++ b/rust/landgen/src/wavefront_collapse/generator.rs Fri Feb 03 14:44:33 2023 +0100 @@ -1,4 +1,4 @@ -use super::tile_image::TileImage; +use super::tile_image::{Edge, TileImage}; use super::wavefront_collapse::WavefrontCollapse; use crate::{LandGenerationParameters, LandGenerator}; use integral_geometry::Size; @@ -17,7 +17,12 @@ } } - pub fn load_template(&self, parameters: &LandGenerationParameters) -> Vec> { + pub fn load_template( + &self, + parameters: &LandGenerationParameters, + ) -> Vec> { + let mut result = Vec::new(); + let file = File::open("sample.png").expect("file exists"); let decoder = Decoder::new(BufReader::new(file)); let mut reader = decoder.read_info().unwrap(); @@ -47,7 +52,18 @@ } } - TileImage::::new(tiles_image).split(3, 3) + let top_edge = Edge::new("edge".to_owned(), false); + let right_edge = Edge::new("edge".to_owned(), false); + let bottom_edge = Edge::new("edge".to_owned(), false); + let left_edge = Edge::new("edge".to_owned(), false); + + let tile = + TileImage::::new(tiles_image, top_edge, right_edge, bottom_edge, left_edge); + + result.push(tile.clone()); + result.push(tile.mirrored()); + + result } } @@ -66,13 +82,13 @@ #[cfg(test)] mod tests { use super::WavefrontCollapseLandGenerator; - use crate::{LandGenerator, LandGenerationParameters}; + use crate::{LandGenerationParameters, LandGenerator}; use integral_geometry::Size; use vec2d::Vec2D; #[test] fn test_generation() { - let wfc_gen =WavefrontCollapseLandGenerator::new(); + let wfc_gen = WavefrontCollapseLandGenerator::new(); let landgen_params = LandGenerationParameters::new(0u8, 255u8, 0, true, true); wfc_gen.generate_land(&landgen_params, &mut std::iter::repeat(1u32)); } diff -r 8f093b1b18bc -r e82de0410da5 rust/landgen/src/wavefront_collapse/mod.rs --- a/rust/landgen/src/wavefront_collapse/mod.rs Thu Feb 02 08:41:31 2023 +0100 +++ b/rust/landgen/src/wavefront_collapse/mod.rs Fri Feb 03 14:44:33 2023 +0100 @@ -1,3 +1,4 @@ pub mod generator; mod tile_image; +mod transform; mod wavefront_collapse; diff -r 8f093b1b18bc -r e82de0410da5 rust/landgen/src/wavefront_collapse/tile_image.rs --- a/rust/landgen/src/wavefront_collapse/tile_image.rs Thu Feb 02 08:41:31 2023 +0100 +++ b/rust/landgen/src/wavefront_collapse/tile_image.rs Fri Feb 03 14:44:33 2023 +0100 @@ -1,78 +1,115 @@ -use vec2d::Vec2D; +use super::transform::RotationTransform; use std::rc::Rc; -use integral_geometry::Size; +use vec2d::Vec2D; -pub struct TileImage { - image: Rc>, - flip: bool, - mirror: bool, +#[derive(PartialEq, Clone)] +pub struct Edge { + id: I, + symmetrical: bool, + reverse: bool, } -impl TileImage { - pub fn new(image: Vec2D) -> Self { +impl Edge { + pub fn new(id: I, symmetrical: bool) -> Self { + Self { + id, + symmetrical, + reverse: false, + } + } + + pub fn reversed(&self) -> Self { + Self { + id: self.id.clone(), + symmetrical: self.symmetrical, + reverse: !self.symmetrical && !self.reverse, + } + } +} + +#[derive(Clone)] +pub struct TileImage { + image: Rc>, + transform: RotationTransform, + top: Edge, + right: Edge, + bottom: Edge, + left: Edge, +} + +impl TileImage { + pub fn new( + image: Vec2D, + top: Edge, + right: Edge, + bottom: Edge, + left: Edge, + ) -> Self { Self { image: Rc::new(image), - flip: false, - mirror: false, + transform: RotationTransform::default(), + top, + right, + bottom, + left, } } pub fn mirrored(&self) -> Self { Self { image: self.image.clone(), - flip: self.flip, - mirror: !self.mirror, + transform: self.transform.mirror(), + top: self.top.reversed(), + right: self.left.reversed(), + bottom: self.bottom.reversed(), + left: self.right.reversed(), } } pub fn flipped(&self) -> Self { Self { image: self.image.clone(), - flip: !self.flip, - mirror: self.mirror, + transform: self.transform.flip(), + top: self.bottom.reversed(), + right: self.right.reversed(), + bottom: self.top.reversed(), + left: self.left.reversed(), + } + } + + pub fn rotated90(&self) -> Self { + Self { + image: self.image.clone(), + transform: self.transform.rotate90(), + top: self.left.clone(), + right: self.top.clone(), + bottom: self.right.clone(), + left: self.bottom.clone(), } } - pub fn split(&self, rows: usize, columns: usize) -> Vec> { - let mut result = Vec::new(); - let self_image = self.image.as_ref(); - let (result_width, result_height) = (self_image.width() / columns, self.image.height() / rows); - - for row in 0..rows { - for column in 0..columns { - let mut tile_pixels = Vec::new(); + pub fn rotated180(&self) -> Self { + Self { + image: self.image.clone(), + transform: self.transform.rotate90(), + top: self.bottom.clone(), + right: self.left.clone(), + bottom: self.top.clone(), + left: self.right.clone(), + } + } - for out_row in 0..result_height { - tile_pixels.push(self_image[row * result_height + out_row][column*result_width..(column+1)*result_width].iter()); - } - - let tile_image = Vec2D::from_iter(tile_pixels.into_iter().flatten().map(|p| *p), &Size::new(result_width, result_height)); - - result.push(TileImage::new(tile_image.expect("correct calculation of tile dimensions"))); - } + pub fn rotated270(&self) -> Self { + Self { + image: self.image.clone(), + transform: self.transform.rotate90(), + top: self.left.clone(), + right: self.top.clone(), + bottom: self.right.clone(), + left: self.bottom.clone(), } - - result } } #[cfg(test)] -mod tests { - use super::TileImage; - use integral_geometry::Size; - use vec2d::Vec2D; - - #[test] - fn test_split() { - let size = Size::new(6, 4); - let sample_data = Vec2D::from_iter((0..24).into_iter(), &size); - - assert!(sample_data.is_some()); - - let sample_data = sample_data.unwrap(); - let big_tile = TileImage::new(sample_data); - let subtiles = big_tile.split(2, 2); - - assert_eq!(subtiles.len(), 4); - } -} +mod tests {} diff -r 8f093b1b18bc -r e82de0410da5 rust/landgen/src/wavefront_collapse/transform.rs --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/rust/landgen/src/wavefront_collapse/transform.rs Fri Feb 03 14:44:33 2023 +0100 @@ -0,0 +1,213 @@ +#[derive(Debug, PartialEq, Clone, Copy)] +pub enum SymmetryTransform { + Id, + Flip, + Mirror, + FlipMirror, +} + +#[derive(Debug, PartialEq, Clone, Copy)] +pub enum RotationTransform { + Rotate0(SymmetryTransform), + Rotate90(SymmetryTransform), + Rotate180(SymmetryTransform), + Rotate270(SymmetryTransform), +} + +impl Default for RotationTransform { + fn default() -> Self { + RotationTransform::Rotate0(SymmetryTransform::Id) + } +} + +impl SymmetryTransform { + pub fn mirror(&self) -> Self { + use SymmetryTransform::*; + match self { + Id => Mirror, + Flip => FlipMirror, + Mirror => Id, + FlipMirror => Flip, + } + } + + pub fn flip(&self) -> Self { + use SymmetryTransform::*; + match self { + Id => Flip, + Flip => Id, + Mirror => FlipMirror, + FlipMirror => Mirror, + } + } +} + +impl RotationTransform { + pub fn new() -> Self { + Self::default() + } + + pub fn mirror(self) -> RotationTransform { + match self { + RotationTransform::Rotate0(s) => RotationTransform::Rotate0(s.mirror()), + RotationTransform::Rotate90(s) => RotationTransform::Rotate270(s.mirror()).simplified(), + RotationTransform::Rotate180(s) => { + RotationTransform::Rotate180(s.mirror()).simplified() + } + RotationTransform::Rotate270(s) => RotationTransform::Rotate90(s.mirror()), + } + } + + pub fn flip(self) -> RotationTransform { + match self { + RotationTransform::Rotate0(s) => RotationTransform::Rotate0(s.flip()), + RotationTransform::Rotate90(s) => RotationTransform::Rotate90(s.flip()), + RotationTransform::Rotate180(s) => RotationTransform::Rotate180(s.flip()).simplified(), + RotationTransform::Rotate270(s) => RotationTransform::Rotate270(s.flip()).simplified(), + } + } + + pub fn rotate90(self) -> RotationTransform { + match self { + RotationTransform::Rotate0(s) => RotationTransform::Rotate90(s), + RotationTransform::Rotate90(s) => RotationTransform::Rotate180(s).simplified(), + RotationTransform::Rotate180(s) => RotationTransform::Rotate270(s).simplified(), + RotationTransform::Rotate270(s) => RotationTransform::Rotate0(s), + } + } + + pub fn rotate180(self) -> RotationTransform { + match self { + RotationTransform::Rotate0(s) => RotationTransform::Rotate180(s).simplified(), + RotationTransform::Rotate90(s) => RotationTransform::Rotate270(s).simplified(), + RotationTransform::Rotate180(s) => RotationTransform::Rotate0(s), + RotationTransform::Rotate270(s) => RotationTransform::Rotate90(s), + } + } + + pub fn rotate270(self) -> RotationTransform { + match self { + RotationTransform::Rotate0(s) => RotationTransform::Rotate270(s).simplified(), + RotationTransform::Rotate90(s) => RotationTransform::Rotate0(s), + RotationTransform::Rotate180(s) => RotationTransform::Rotate90(s), + RotationTransform::Rotate270(s) => RotationTransform::Rotate180(s).simplified(), + } + } + + fn simplified(self) -> Self { + match self { + RotationTransform::Rotate0(s) => RotationTransform::Rotate0(s), + RotationTransform::Rotate90(s) => RotationTransform::Rotate90(s), + RotationTransform::Rotate180(s) => RotationTransform::Rotate0(s.flip().mirror()), + RotationTransform::Rotate270(s) => RotationTransform::Rotate90(s.flip().mirror()), + } + } +} + +#[cfg(test)] +mod tests { + use super::{RotationTransform::*, SymmetryTransform::*, *}; + + // I totally wrote all of this myself and didn't use ChatGPT + #[test] + fn test_default() { + let rt = RotationTransform::new(); + assert_eq!(rt, Rotate0(Id)); + } + + #[test] + fn test_mirror() { + let rt = Rotate90(Flip); + let mirrored = rt.mirror(); + assert_eq!(mirrored, Rotate90(Id)); + } + + #[test] + fn test_flip() { + let rt = Rotate180(Mirror); + let flipped = rt.flip(); + assert_eq!(flipped, Rotate0(Id)); + } + + #[test] + fn test_rotate90() { + let rt = Rotate0(Id); + let rotated = rt.rotate90(); + assert_eq!(rotated, Rotate90(Id)); + } + + #[test] + fn test_rotate180() { + let rt = Rotate90(Mirror); + let rotated = rt.rotate180(); + assert_eq!(rotated, Rotate90(Flip)); + } + + #[test] + fn test_rotate270() { + let rt = Rotate180(Flip); + let rotated = rt.rotate270(); + assert_eq!(rotated, Rotate90(Flip)); + } + + #[test] + fn test_simplified() { + let rt = Rotate180(Id); + let simplified = rt.simplified(); + assert_eq!(simplified, Rotate0(FlipMirror)); + } + + #[test] + fn test_rotation_chain() { + assert_eq!( + RotationTransform::default(), + RotationTransform::default() + .rotate90() + .rotate90() + .rotate90() + .rotate90() + ); + assert_eq!( + RotationTransform::default().rotate90(), + RotationTransform::default() + .rotate180() + .rotate90() + .rotate180() + ); + assert_eq!( + RotationTransform::default().rotate180(), + RotationTransform::default() + .rotate180() + .rotate270() + .rotate90() + ); + } + + #[test] + fn test_combinations_chain() { + assert_eq!( + RotationTransform::default(), + RotationTransform::default() + .flip() + .rotate180() + .flip() + .rotate180() + ); + assert_eq!( + RotationTransform::default(), + RotationTransform::default() + .mirror() + .rotate180() + .mirror() + .rotate180() + ); + assert_eq!( + RotationTransform::default(), + RotationTransform::default() + .rotate90() + .flip() + .rotate90() + .mirror() + ); + } +} diff -r 8f093b1b18bc -r e82de0410da5 rust/landgen/src/wavefront_collapse/wavefront_collapse.rs --- a/rust/landgen/src/wavefront_collapse/wavefront_collapse.rs Thu Feb 02 08:41:31 2023 +0100 +++ b/rust/landgen/src/wavefront_collapse/wavefront_collapse.rs Fri Feb 03 14:44:33 2023 +0100 @@ -1,5 +1,5 @@ use integral_geometry::Size; -use std::collections::HashMap; +use std::collections::{HashMap, HashSet}; use vec2d::Vec2D; #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] @@ -44,14 +44,26 @@ } } -struct CollapseRule { - to_tile: Tile, - condition: fn([Tile; 4]) -> bool, +pub struct CollapseRule { + tile: Tile, + right: HashSet, + bottom: HashSet, + left: HashSet, + top: HashSet, } -#[derive(Default)] pub struct WavefrontCollapse { - rules: HashMap>, + rules: Vec, + grid: Vec2D, +} + +impl Default for WavefrontCollapse { + fn default() -> Self { + Self { + rules: Vec::new(), + grid: Vec2D::new(&Size::new(1, 1), Tile::Empty), + } + } } impl WavefrontCollapse { @@ -60,69 +72,90 @@ map_size: &Size, seed_fn: F, random_numbers: &mut I, - ) -> Vec2D { - let mut land = Vec2D::new(&map_size, Tile::Empty); + ) { + self.grid = Vec2D::new(&map_size, Tile::Empty); - seed_fn(&mut land); + seed_fn(&mut self.grid); - while self.collapse_step(&mut land, random_numbers) {} - - land + while self.collapse_step(random_numbers) {} } - 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 add_rule(&mut self, rule: CollapseRule) { + self.rules.push(rule); + } + + fn get_tile(&self, y: usize, x: usize) -> Tile { + self.grid.get(y, x).map(|p| *p).unwrap_or_default() } - fn collapse_step>( - &self, - land: &mut Vec2D, - 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"); + fn collapse_step>(&mut self, random_numbers: &mut I) -> bool { + let mut tiles_to_collapse = (usize::max_value(), Vec::new()); + + // Iterate through the tiles in the land + for x in 0..self.grid.width() { + for y in 0..self.grid.height() { + let current_tile = self.get_tile(y, x); - if let Some(rules) = self.rules.get(¤t_tile) { - for rule in rules + if let Tile::Empty = current_tile { + // calc entropy + let right_tile = self.get_tile(y, x + 1); + let bottom_tile = self.get_tile(y + 1, x); + let left_tile = self.get_tile(y, x.wrapping_sub(1)); + let top_tile = self.get_tile(y.wrapping_sub(1), x); + + let possibilities: Vec = self + .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; + .filter_map(|rule| { + if rule.right.contains(&right_tile) + && rule.bottom.contains(&bottom_tile) + && rule.left.contains(&left_tile) + && rule.top.contains(&top_tile) + { + Some(rule.tile) + } else { + None + } + }) + .collect(); + + let entropy = possibilities.len(); + if entropy > 0 && entropy <= tiles_to_collapse.0 { + let entry = ( + y, + x, + possibilities + [random_numbers.next().unwrap_or_default() as usize % entropy], + ); + + if entropy < tiles_to_collapse.0 { + tiles_to_collapse = (entropy, vec![entry]) + } else { + tiles_to_collapse.1.push(entry) } + } else { + todo!("no collapse possible") } } } } - collapse_occurred - } + let tiles_to_collapse = tiles_to_collapse.1; + let possibilities_number = tiles_to_collapse.len(); + + if possibilities_number > 0 { + let (y, x, tile) = tiles_to_collapse + [random_numbers.next().unwrap_or_default() as usize % possibilities_number]; - fn get_neighbors(&self, land: &Vec2D, 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(), - ] + *self + .grid + .get_mut(y, x) + .expect("correct iteration over grid") = tile; + + true + } else { + false + } } } @@ -139,15 +172,7 @@ 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()); + assert_eq!(empty_land.as_slice(), wfc.grid.as_slice()); } }