1 use integral_geometry::Size; |
1 use integral_geometry::Size; |
2 use rand::distributions::Distribution; |
2 use rand::distr::{weighted::WeightedIndex, Distribution}; |
3 use rand::distributions::WeightedIndex; |
3 use rand::prelude::IndexedRandom; |
4 use rand::Rng; |
4 use rand::Rng; |
5 use std::collections::HashSet; |
5 use std::collections::HashSet; |
6 use vec2d::Vec2D; |
6 use vec2d::Vec2D; |
7 |
7 |
8 #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] |
8 #[derive(PartialEq, Eq, Hash, Clone, Copy, Debug)] |
57 ) { |
57 ) { |
58 self.grid = Vec2D::new(map_size, Tile::Empty); |
58 self.grid = Vec2D::new(map_size, Tile::Empty); |
59 |
59 |
60 seed_fn(&mut self.grid); |
60 seed_fn(&mut self.grid); |
61 |
61 |
62 while self.collapse_step(random_numbers) {} |
62 let mut backtracks = 0usize; |
|
63 while let Some(b) = self.collapse_step(random_numbers) { |
|
64 backtracks += b; |
|
65 |
|
66 if backtracks >= 1000 { |
|
67 println!("[WFC] Too much backtracking, stopping generation!"); |
|
68 break; |
|
69 } |
|
70 } |
|
71 |
|
72 if backtracks > 0 { |
|
73 println!("[WFC] Had to backtrack {} times...", backtracks); |
|
74 } |
63 } |
75 } |
64 |
76 |
65 pub fn set_rules(&mut self, rules: Vec<CollapseRule>) { |
77 pub fn set_rules(&mut self, rules: Vec<CollapseRule>) { |
66 self.rules = rules; |
78 self.rules = rules; |
67 } |
79 } |
107 } |
119 } |
108 } |
120 } |
109 }) |
121 }) |
110 } |
122 } |
111 |
123 |
112 fn collapse_step(&mut self, random_numbers: &mut impl Rng) -> bool { |
124 fn collapse_step(&mut self, random_numbers: &mut impl Rng) -> Option<usize> { |
113 let mut tiles_to_collapse = (usize::MAX, Vec::new()); |
125 let mut tiles_to_collapse = (usize::MAX, Vec::new()); |
114 |
126 |
115 // Iterate through the tiles in the land |
127 // Iterate through the tiles in the land |
116 for x in 0..self.grid.width() { |
128 for x in 0..self.grid.width() { |
117 for y in 0..self.grid.height() { |
129 for y in 0..self.grid.height() { |
118 let current_tile = self.get_tile(y, x); |
130 let current_tile = self.get_tile(y, x); |
119 |
131 |
120 if let Tile::Empty = current_tile { |
132 if let Tile::Empty = current_tile { |
|
133 let neighbors = [ |
|
134 (y, x.wrapping_add(1)), |
|
135 (y.wrapping_add(1), x), |
|
136 (y, x.wrapping_sub(1)), |
|
137 (y.wrapping_sub(1), x), |
|
138 ]; |
|
139 |
121 // calc entropy |
140 // calc entropy |
122 let right_tile = self.get_tile(y, x.wrapping_add(1)); |
141 let [right_tile, bottom_tile, left_tile, top_tile] = |
123 let bottom_tile = self.get_tile(y.wrapping_add(1), x); |
142 neighbors.map(|(y, x)| self.get_tile(y, x)); |
124 let left_tile = self.get_tile(y, x.wrapping_sub(1)); |
|
125 let top_tile = self.get_tile(y.wrapping_sub(1), x); |
|
126 |
143 |
127 let possibilities: Vec<(u32, Tile)> = self |
144 let possibilities: Vec<(u32, Tile)> = self |
128 .rules |
145 .rules |
129 .iter() |
146 .iter() |
130 .filter_map(|rule| { |
147 .filter_map(|rule| { |
144 if entropy > 0 { |
161 if entropy > 0 { |
145 if entropy <= tiles_to_collapse.0 { |
162 if entropy <= tiles_to_collapse.0 { |
146 let weights = possibilities.iter().map(|(weight, _)| *weight); |
163 let weights = possibilities.iter().map(|(weight, _)| *weight); |
147 let distribution = WeightedIndex::new(weights).unwrap(); |
164 let distribution = WeightedIndex::new(weights).unwrap(); |
148 |
165 |
149 let entry = (y, x, possibilities[distribution.sample(random_numbers)]); |
166 let entry = |
|
167 (y, x, possibilities[distribution.sample(random_numbers)].1); |
150 |
168 |
151 if entropy < tiles_to_collapse.0 { |
169 if entropy < tiles_to_collapse.0 { |
152 tiles_to_collapse = (entropy, vec![entry]) |
170 tiles_to_collapse = (entropy, vec![entry]) |
153 } else { |
171 } else { |
154 tiles_to_collapse.1.push(entry) |
172 tiles_to_collapse.1.push(entry) |
155 } |
173 } |
156 } |
174 } |
157 } else { |
175 } else { |
158 /*println!("We're here: {}, {}", x, y); |
176 /* |
|
177 println!("We're here: {}, {}", x, y); |
159 println!( |
178 println!( |
160 "Neighbour tiles are: {:?} {:?} {:?} {:?}", |
179 "Neighbour tiles are: {:?} {:?} {:?} {:?}", |
161 right_tile, bottom_tile, left_tile, top_tile |
180 right_tile, bottom_tile, left_tile, top_tile |
162 ); |
181 ); |
163 println!("Rules are: {:?}", self.rules);*/ |
182 println!("Rules are: {:?}", self.rules); |
|
183 */ |
|
184 |
|
185 let entries = neighbors |
|
186 .iter() |
|
187 .filter(|(y, x)| self.grid.get(*y, *x).is_some()) |
|
188 .map(|(y, x)| (*y, *x, Tile::Empty)) |
|
189 .collect::<Vec<_>>(); |
|
190 |
|
191 if entropy < tiles_to_collapse.0 { |
|
192 tiles_to_collapse = (entropy, entries); |
|
193 } else { |
|
194 tiles_to_collapse.1.extend(entries); |
|
195 } |
164 |
196 |
165 //todo!("no collapse possible - what to do?") |
197 //todo!("no collapse possible - what to do?") |
166 } |
198 } |
167 } |
199 } |
168 } |
200 } |
169 } |
201 } |
170 |
202 |
171 let tiles_to_collapse = tiles_to_collapse.1; |
203 if tiles_to_collapse.0 == 0 { |
172 let possibilities_number = tiles_to_collapse.len(); |
204 // cannot collapse, we're clearing some tiles |
173 |
205 |
174 if possibilities_number > 0 { |
206 for (y, x, tile) in tiles_to_collapse.1 { |
175 let weights = tiles_to_collapse.iter().map(|(_, _, (weight, _))| *weight); |
207 *self |
176 let distribution = WeightedIndex::new(weights).unwrap(); |
208 .grid |
177 |
209 .get_mut(y, x) |
178 let (y, x, (_, tile)) = tiles_to_collapse[distribution.sample(random_numbers)]; |
210 .expect("correct iteration over grid") = tile; |
179 |
211 } |
180 *self |
212 |
181 .grid |
213 Some(1) |
182 .get_mut(y, x) |
|
183 .expect("correct iteration over grid") = tile; |
|
184 |
|
185 true |
|
186 } else { |
214 } else { |
187 false |
215 if let Some(&(y, x, tile)) = tiles_to_collapse.1.as_slice().choose(random_numbers) { |
|
216 *self |
|
217 .grid |
|
218 .get_mut(y, x) |
|
219 .expect("correct iteration over grid") = tile; |
|
220 |
|
221 Some(0) |
|
222 } else { |
|
223 None |
|
224 } |
188 } |
225 } |
189 } |
226 } |
190 |
227 |
191 pub fn grid(&self) -> &Vec2D<Tile> { |
228 pub fn grid(&self) -> &Vec2D<Tile> { |
192 &self.grid |
229 &self.grid |