# HG changeset patch
# User unC0Rr
# Date 1738514874 -3600
# Node ID 65c017453e8315371e97c72c9eabb813b7ef734f
# Parent  e12d9a4d0e0448cc12c6b8c81404ef189c47669a
Add anti_match feature, log some info when cannot satisfy rules

diff -r e12d9a4d0e04 -r 65c017453e83 rust/landgen/src/wavefront_collapse/generator.rs
--- a/rust/landgen/src/wavefront_collapse/generator.rs	Thu Jan 30 16:38:20 2025 +0100
+++ b/rust/landgen/src/wavefront_collapse/generator.rs	Sun Feb 02 17:47:54 2025 +0100
@@ -1,4 +1,4 @@
-use super::tile_image::{Edge, TileImage};
+use super::tile_image::{Edge, EdgeSet, MatchSide, TileImage};
 use super::wavefront_collapse::{CollapseRule, Tile, WavefrontCollapse};
 use crate::{LandGenerationParameters, LandGenerator};
 use integral_geometry::Size;
@@ -29,6 +29,7 @@
     pub name: String,
     pub weight: u8,
     pub edges: EdgesDescription,
+    pub anti_match: Option<[u64; 4]>,
     pub is_negative: Option<bool>,
     pub can_flip: Option<bool>,
     pub can_mirror: Option<bool>,
@@ -130,15 +131,19 @@
             }
         }
 
-        let [top_edge, right_edge, bottom_edge, left_edge]: [Edge<String>; 4] = [
+        let edge_set: EdgeSet<String> = EdgeSet::new([
             (&tile_description.edges.top).into(),
             (&tile_description.edges.right).into(),
             (&tile_description.edges.bottom).into(),
             (&tile_description.edges.left).into(),
-        ];
+        ]);
 
-        let tile =
-            TileImage::<T, String>::new(tiles_image, tile_description.weight, top_edge, right_edge, bottom_edge, left_edge);
+        let tile = TileImage::<T, String>::new(
+            tiles_image,
+            tile_description.weight,
+            edge_set,
+            tile_description.anti_match.unwrap_or_default(),
+        );
 
         result.push(tile.clone());
 
@@ -209,10 +214,10 @@
             let mut top = default_connection.clone();
 
             let iteration = [
-                (&grid_top_edge, tile.top_edge(), &mut top),
-                (&grid_right_edge, tile.right_edge(), &mut right),
-                (&grid_bottom_edge, tile.bottom_edge(), &mut bottom),
-                (&grid_left_edge, tile.left_edge(), &mut left),
+                (&grid_top_edge, tile.edge_set().top(), &mut top),
+                (&grid_right_edge, tile.edge_set().right(), &mut right),
+                (&grid_bottom_edge, tile.edge_set().bottom(), &mut bottom),
+                (&grid_left_edge, tile.edge_set().left(), &mut left),
             ];
 
             // compatibility with grid edges
@@ -237,12 +242,12 @@
             }
 
             // compatibility with itself
-            if tile.left_edge().is_compatible(tile.right_edge()) {
+            if tile.is_compatible(&tile, MatchSide::OnLeft) {
                 left.insert(Tile::Numbered(i));
                 right.insert(Tile::Numbered(i));
             }
 
-            if tile.top_edge().is_compatible(tile.bottom_edge()) {
+            if tile.is_compatible(&tile, MatchSide::OnTop) {
                 top.insert(Tile::Numbered(i));
                 bottom.insert(Tile::Numbered(i));
             }
@@ -250,25 +255,25 @@
             // compatibility with previously defined tiles
             for p in 0..i {
                 // Check left edge
-                if tiles[p].left_edge().is_compatible(tile.right_edge()) {
+                if tiles[p].is_compatible(&tile, MatchSide::OnLeft) {
                     rules[p].left.insert(Tile::Numbered(i));
                     right.insert(Tile::Numbered(p));
                 }
 
                 // Check right edge
-                if tiles[p].right_edge().is_compatible(tile.left_edge()) {
+                if tiles[p].is_compatible(&tile, MatchSide::OnRight) {
                     rules[p].right.insert(Tile::Numbered(i));
                     left.insert(Tile::Numbered(p));
                 }
 
                 // Check top edge
-                if tiles[p].top_edge().is_compatible(tile.bottom_edge()) {
+                if tiles[p].is_compatible(&tile, MatchSide::OnTop) {
                     rules[p].top.insert(Tile::Numbered(i));
                     bottom.insert(Tile::Numbered(p));
                 }
 
                 // Check bottom edge
-                if tiles[p].bottom_edge().is_compatible(tile.top_edge()) {
+                if tiles[p].is_compatible(&tile, MatchSide::OnBottom) {
                     rules[p].bottom.insert(Tile::Numbered(i));
                     top.insert(Tile::Numbered(p));
                 }
@@ -279,7 +284,7 @@
                 - probability_distribution_factor) as u32;
 
             rules.push(CollapseRule {
-                weight: weight * tile.weight as u32 + 1,
+                weight: weight * tile.weight as u32,
                 tile: Tile::Numbered(i),
                 top,
                 right,
@@ -344,6 +349,46 @@
                             );
                         }
                     }
+                } else {
+                    // couldn't find a tile to place here, dump some debug info for tile set maker
+                    let mut edges = ["-", "|", "-", "|"].map(|s| s.to_owned());
+
+                    if row > 0 {
+                        let tile = wfc.grid().get(row - 1, column);
+                        edges[0] = if let Some(Tile::Numbered(tile_index)) = tile {
+                            tiles[*tile_index].edge_set().bottom().name()
+                        } else {
+                            format!("{:?}", tile.unwrap())
+                        }
+                    }
+                    if column < wfc_size.width as usize - 1 {
+                        let tile = wfc.grid().get(row, column + 1);
+                        edges[1] = if let Some(Tile::Numbered(tile_index)) = tile {
+                            tiles[*tile_index].edge_set().left().name()
+                        } else {
+                            format!("{:?}", tile.unwrap())
+                        }
+                    }
+                    if row < wfc_size.height as usize - 1 {
+                        let tile = wfc.grid().get(row + 1, column);
+                        edges[2] = if let Some(Tile::Numbered(tile_index)) = tile {
+                            tiles[*tile_index].edge_set().top().name()
+                        } else {
+                            format!("{:?}", tile.unwrap())
+                        }
+                    }
+                    if column > 0 {
+                        let tile = wfc.grid().get(row, column - 1);
+                        edges[3] = if let Some(Tile::Numbered(tile_index)) = tile {
+                            tiles[*tile_index].edge_set().right().name()
+                        } else {
+                            format!("{:?}", tile.unwrap())
+                        }
+                    }
+                    eprintln!(
+                        "Couldn't find a tile to place here (row, column): ({}, {}), edges are: [{}]",
+                        row, column, edges.join(", "),
+                    );
                 }
             }
         }
diff -r e12d9a4d0e04 -r 65c017453e83 rust/landgen/src/wavefront_collapse/tile_image.rs
--- a/rust/landgen/src/wavefront_collapse/tile_image.rs	Thu Jan 30 16:38:20 2025 +0100
+++ b/rust/landgen/src/wavefront_collapse/tile_image.rs	Sun Feb 02 17:47:54 2025 +0100
@@ -35,34 +35,143 @@
     }
 }
 
+impl Edge<String> {
+    pub fn name(&self) -> String {
+        if self.reverse {
+            self.id.chars().rev().collect()
+        } else {
+            self.id.clone()
+        }
+    }
+}
+
+#[derive(PartialEq, Clone, Debug)]
+pub struct EdgeSet<I: PartialEq + Clone>([Edge<I>; 4]);
+
+impl<I: PartialEq + Clone> EdgeSet<I> {
+    pub fn new(edge_set: [Edge<I>; 4]) -> Self {
+        Self(edge_set)
+    }
+
+    pub fn top(&self) -> &Edge<I> {
+        &self.0[0]
+    }
+
+    pub fn right(&self) -> &Edge<I> {
+        &self.0[1]
+    }
+
+    pub fn bottom(&self) -> &Edge<I> {
+        &self.0[2]
+    }
+
+    pub fn left(&self) -> &Edge<I> {
+        &self.0[3]
+    }
+
+    pub fn mirrored(&self) -> Self {
+        Self([
+            self.0[0].reversed(),
+            self.0[3].reversed(),
+            self.0[2].reversed(),
+            self.0[1].reversed(),
+        ])
+    }
+
+    pub fn flipped(&self) -> Self {
+        Self([
+            self.0[2].reversed(),
+            self.0[1].reversed(),
+            self.0[0].reversed(),
+            self.0[3].reversed(),
+        ])
+    }
+
+    pub fn rotated90(&self) -> Self {
+        Self([
+            self.0[3].clone(),
+            self.0[0].clone(),
+            self.0[1].clone(),
+            self.0[2].clone(),
+        ])
+    }
+
+    pub fn rotated180(&self) -> Self {
+        Self([
+            self.0[2].clone(),
+            self.0[3].clone(),
+            self.0[0].clone(),
+            self.0[1].clone(),
+        ])
+    }
+
+    pub fn rotated270(&self) -> Self {
+        Self([
+            self.0[1].clone(),
+            self.0[2].clone(),
+            self.0[3].clone(),
+            self.0[0].clone(),
+        ])
+    }
+}
+
+#[derive(PartialEq, Clone, Debug)]
+pub enum MatchSide {
+    OnTop,
+    OnRight,
+    OnBottom,
+    OnLeft,
+}
 #[derive(Clone)]
 pub struct TileImage<T, I: PartialEq + Clone> {
     image: Rc<Vec2D<T>>,
     pub weight: u8,
     pub transform: Transform,
-    top: Edge<I>,
-    right: Edge<I>,
-    bottom: Edge<I>,
-    left: Edge<I>,
+    edges: EdgeSet<I>,
+    anti_match: [u64; 4],
 }
 
 impl<T: Copy, I: PartialEq + Clone> TileImage<T, I> {
-    pub fn new(
-        image: Vec2D<T>,
-        weight: u8,
-        top: Edge<I>,
-        right: Edge<I>,
-        bottom: Edge<I>,
-        left: Edge<I>,
-    ) -> Self {
+    pub fn new(image: Vec2D<T>, weight: u8, edges: EdgeSet<I>, anti_match: [u64; 4]) -> Self {
         Self {
             image: Rc::new(image),
             weight,
             transform: Transform::default(),
-            top,
-            right,
-            bottom,
-            left,
+            edges,
+            anti_match,
+        }
+    }
+
+    pub fn is_compatible(&self, other: &Self, direction: MatchSide) -> bool {
+        match direction {
+            MatchSide::OnTop => {
+                self.anti_match[0] & other.anti_match[2] == 0
+                    && self
+                        .edge_set()
+                        .top()
+                        .is_compatible(other.edge_set().bottom())
+            }
+            MatchSide::OnRight => {
+                self.anti_match[1] & other.anti_match[3] == 0
+                    && self
+                        .edge_set()
+                        .right()
+                        .is_compatible(other.edge_set().left())
+            }
+            MatchSide::OnBottom => {
+                self.anti_match[2] & other.anti_match[0] == 0
+                    && self
+                        .edge_set()
+                        .bottom()
+                        .is_compatible(other.edge_set().top())
+            }
+            MatchSide::OnLeft => {
+                self.anti_match[3] & other.anti_match[1] == 0
+                    && self
+                        .edge_set()
+                        .left()
+                        .is_compatible(other.edge_set().right())
+            }
         }
     }
 
@@ -71,10 +180,13 @@
             image: self.image.clone(),
             weight: self.weight,
             transform: self.transform.mirror(),
-            top: self.top.reversed(),
-            right: self.left.reversed(),
-            bottom: self.bottom.reversed(),
-            left: self.right.reversed(),
+            edges: self.edges.mirrored(),
+            anti_match: [
+                self.anti_match[0],
+                self.anti_match[3],
+                self.anti_match[2],
+                self.anti_match[1],
+            ],
         }
     }
 
@@ -83,10 +195,13 @@
             image: self.image.clone(),
             weight: self.weight,
             transform: self.transform.flip(),
-            top: self.bottom.reversed(),
-            right: self.right.reversed(),
-            bottom: self.top.reversed(),
-            left: self.left.reversed(),
+            edges: self.edges.flipped(),
+            anti_match: [
+                self.anti_match[2],
+                self.anti_match[1],
+                self.anti_match[0],
+                self.anti_match[3],
+            ],
         }
     }
 
@@ -95,10 +210,13 @@
             image: self.image.clone(),
             weight: self.weight,
             transform: self.transform.rotate90(),
-            top: self.left.clone(),
-            right: self.top.clone(),
-            bottom: self.right.clone(),
-            left: self.bottom.clone(),
+            edges: self.edges.rotated90(),
+            anti_match: [
+                self.anti_match[3],
+                self.anti_match[0],
+                self.anti_match[1],
+                self.anti_match[2],
+            ],
         }
     }
 
@@ -107,10 +225,13 @@
             image: self.image.clone(),
             weight: self.weight,
             transform: self.transform.rotate180(),
-            top: self.bottom.clone(),
-            right: self.left.clone(),
-            bottom: self.top.clone(),
-            left: self.right.clone(),
+            edges: self.edges.rotated180(),
+            anti_match: [
+                self.anti_match[2],
+                self.anti_match[3],
+                self.anti_match[0],
+                self.anti_match[1],
+            ],
         }
     }
 
@@ -119,31 +240,19 @@
             image: self.image.clone(),
             weight: self.weight,
             transform: self.transform.rotate270(),
-            top: self.right.clone(),
-            right: self.bottom.clone(),
-            bottom: self.left.clone(),
-            left: self.top.clone(),
+            edges: self.edges.rotated270(),
+            anti_match: [
+                self.anti_match[1],
+                self.anti_match[2],
+                self.anti_match[3],
+                self.anti_match[0],
+            ],
         }
     }
 
     #[inline]
-    pub fn right_edge(&self) -> &Edge<I> {
-        &self.right
-    }
-
-    #[inline]
-    pub fn bottom_edge(&self) -> &Edge<I> {
-        &self.bottom
-    }
-
-    #[inline]
-    pub fn left_edge(&self) -> &Edge<I> {
-        &self.left
-    }
-
-    #[inline]
-    pub fn top_edge(&self) -> &Edge<I> {
-        &self.top
+    pub fn edge_set(&self) -> &EdgeSet<I> {
+        &self.edges
     }
 
     #[inline]
diff -r e12d9a4d0e04 -r 65c017453e83 rust/landgen/src/wavefront_collapse/wavefront_collapse.rs
--- a/rust/landgen/src/wavefront_collapse/wavefront_collapse.rs	Thu Jan 30 16:38:20 2025 +0100
+++ b/rust/landgen/src/wavefront_collapse/wavefront_collapse.rs	Sun Feb 02 17:47:54 2025 +0100
@@ -63,7 +63,7 @@
         while let Some(b) = self.collapse_step(random_numbers) {
             backtracks += b;
 
-            if backtracks >= 1000 {
+            if backtracks >= 128 {
                 println!("[WFC] Too much backtracking, stopping generation!");
                 break;
             }
@@ -161,10 +161,19 @@
                     if entropy > 0 {
                         if entropy <= tiles_to_collapse.0 {
                             let weights = possibilities.iter().map(|(weight, _)| weight.pow(2));
-                            let distribution = WeightedIndex::new(weights).unwrap();
 
-                            let entry =
-                                (y, x, possibilities[distribution.sample(random_numbers)].1);
+                            let tile = if weights.clone().sum::<u32>() == 0 {
+                                possibilities
+                                    .as_slice()
+                                    .choose(random_numbers)
+                                    .expect("non-empty slice")
+                                    .1
+                            } else {
+                                let distribution = WeightedIndex::new(weights).unwrap();
+                                possibilities[distribution.sample(random_numbers)].1
+                            };
+
+                            let entry = (y, x, tile);
 
                             if entropy < tiles_to_collapse.0 {
                                 tiles_to_collapse = (entropy, vec![entry])
@@ -173,15 +182,6 @@
                             }
                         }
                     } else {
-                        /*
-                        println!("We're here: {}, {}", x, y);
-                        println!(
-                            "Neighbour tiles are: {:?} {:?} {:?} {:?}",
-                            right_tile, bottom_tile, left_tile, top_tile
-                        );
-                        println!("Rules are: {:?}", self.rules);
-                        */
-
                         let entries = neighbors
                             .iter()
                             .filter(|(y, x)| self.grid.get(*y, *x).is_some())
@@ -193,8 +193,6 @@
                         } else {
                             tiles_to_collapse.1.extend(entries);
                         }
-
-                        //todo!("no collapse possible - what to do?")
                     }
                 }
             }
@@ -220,6 +218,7 @@
 
                 Some(0)
             } else {
+                // all tiles are filled according to the rules
                 None
             }
         }
@@ -229,23 +228,3 @@
         &self.grid
     }
 }
-
-#[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().cycle();
-        let mut wfc = WavefrontCollapse::default();
-
-        wfc.generate_map(&size, |_| {}, &mut rnd);
-
-        let empty_land = Vec2D::new(&size, Tile::Empty);
-
-        assert_eq!(empty_land.as_slice(), wfc.grid().as_slice());
-    }
-}
diff -r e12d9a4d0e04 -r 65c017453e83 rust/mapgen/src/template/wavefront_collapse.rs
--- a/rust/mapgen/src/template/wavefront_collapse.rs	Thu Jan 30 16:38:20 2025 +0100
+++ b/rust/mapgen/src/template/wavefront_collapse.rs	Sun Feb 02 17:47:54 2025 +0100
@@ -10,6 +10,7 @@
     pub name: String,
     pub weight: Option<u8>,
     pub edges: [String; 4],
+    pub anti_match: Option<[u64; 4]>,
     pub is_negative: Option<bool>,
     pub can_flip: Option<bool>,
     pub can_mirror: Option<bool>,
@@ -103,6 +104,7 @@
                 bottom,
                 left,
             },
+            anti_match: desc.anti_match,
             is_negative: desc.is_negative,
             can_flip: desc.can_flip,
             can_mirror: desc.can_mirror,
diff -r e12d9a4d0e04 -r 65c017453e83 share/hedgewars/Data/Tiles/shoppa_endpiece.png
Binary file share/hedgewars/Data/Tiles/shoppa_endpiece.png has changed
diff -r e12d9a4d0e04 -r 65c017453e83 share/hedgewars/Data/Tiles/shoppa_hill_side_2m.png
Binary file share/hedgewars/Data/Tiles/shoppa_hill_side_2m.png has changed
diff -r e12d9a4d0e04 -r 65c017453e83 share/hedgewars/Data/wfc_templates.toml
--- a/share/hedgewars/Data/wfc_templates.toml	Thu Jan 30 16:38:20 2025 +0100
+++ b/share/hedgewars/Data/wfc_templates.toml	Sun Feb 02 17:47:54 2025 +0100
@@ -115,6 +115,7 @@
 # shoppa tiles
 [[tiles.Shoppa]]
 name = "120_filled.png"
+weight = 0
 edges = [ "first_layer_reyal_tsrif", "f", "f", "f" ]
 is_negative = true
 
@@ -123,32 +124,39 @@
 edges = [ "e", "e", "e", "e" ]
 
 [[tiles.Shoppa]]
+# forced space
 name = "120_filled.png"
-edges = [ "e", "e", "first_layer_reyal_tsrif", "e" ]
+weight = 0
+edges = [ "E", "e", "e", "e" ]
+can_rotate90 = true
+can_rotate180 = true
+can_rotate270 = true
 
 [[tiles.Shoppa]]
 name = "120_filled.png"
-edges = [ "e", "E", "e", "e" ] # forced space
-can_mirror = true
+weight = 10
+edges = [ "e", "e", "first_layer_reyal_tsrif", "e" ]
 
 [[tiles.Shoppa]]
 name = "shoppa_bar.png"
 weight = 15
 edges = [ "e", "efe", "e", "efe" ]
+anti_match = [1, 0, 1, 0]
 can_rotate90 = true
 
 [[tiles.Shoppa]]
-name = "shoppa_endpiece.png"
-weight = 2
+# used as end piece
+name = "shoppa_bar.png"
+weight = 10
 edges = [ "e", "e", "e", "efe" ]
-can_rotate90 = true
-can_rotate180 = true
-can_rotate270 = true
+anti_match = [1, 1, 1, 0]
+can_mirror = true
 
 [[tiles.Shoppa]]
 name = "shoppa_roundedendpiece.png"
-weight = 10
+weight = 8
 edges = [ "e", "e", "e", "efe" ]
+anti_match = [1, 1, 1, 0]
 can_rotate90 = true
 can_rotate270 = true
 can_mirror = true
@@ -157,64 +165,68 @@
 name = "shoppa_t.png"
 weight = 4
 edges = [ "e", "efe", "efe", "efe" ]
+anti_match = [1, 1, 1, 1]
 can_rotate90 = true
 can_rotate270 = true
 
 [[tiles.Shoppa]]
+# first layer semicircle
 name = "shoppa_sector.png"
 weight = 5
 edges = [ "e", "sector_rotces", "first_layer_reyal_tsrif", "e" ]
+anti_match = [1, 0, 0, 1]
 can_mirror = true
 
 [[tiles.Shoppa]]
 name = "shoppa_sector.png"
 edges = [ "e", "sector", "rotces", "e" ]
+anti_match = [1, 0, 0, 1]
 can_rotate90 = true
 can_rotate180 = true
 can_rotate270 = true
 
 [[tiles.Shoppa]]
 name = "shoppa_hill_center_1.png"
-weight = 1
-edges = [ "e", "E", "retnecllih", "E" ]
+weight = 0
+edges = [ "E", "E", "retnecllih", "E" ]
 
 [[tiles.Shoppa]]
 name = "shoppa_hill_center_2.png"
-weight = 1
-edges = [ "hillcenter", "hillside2R", "H", "L2edisllih" ]
+weight = 0
+edges = [ "hillcenter", "hillside2", "H", "2edisllih" ]
+anti_match = [0, 2, 0, 2]
 
 [[tiles.Shoppa]]
 name = "shoppa_hill_side_2.png"
-weight = 1
-edges = [ "e", "hillside2L", "3edisllih", "e" ]
-
-[[tiles.Shoppa]]
-name = "shoppa_hill_side_2m.png"
-weight = 1
-edges = [ "e", "e", "hillside3", "R2edisllih" ]
+weight = 0
+edges = [ "e", "hillside2", "3edisllih", "e" ]
+anti_match = [0, 1, 0, 0]
+can_mirror = true
 
 [[tiles.Shoppa]]
 name = "shoppa_hill_side_3.png"
-weight = 1
+weight = 0
 edges = [ "hillside3", "H", "4edisllih", "e" ]
 can_mirror = true
 
 [[tiles.Shoppa]]
 name = "shoppa_hill_side_4.png"
-weight = 4
+weight = 6
 edges = [ "hillside4", "H", "first_layer_reyal_tsrif", "e" ]
+anti_match = [0, 4, 0, 0]
 can_mirror = true
 
 [[tiles.Shoppa]]
 name = "120_filled.png"
-weight = 1
+weight = 0
 edges = [ "H", "H", "first_layer_reyal_tsrif", "H" ]
 is_negative = true
 
 [[tiles.Shoppa]]
 name = "120_filled.png"
-weight = 0
+weight = 10
 edges = [ "H", "H", "H", "H" ]
+anti_match = [0, 2, 0, 2]
 is_negative = true
 
 ################ EDGES ################