1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
use micro_ndarray::Array;
use rand::{
seq::{IteratorRandom, SliceRandom},
Rng,
};
use crate::{pixel::PixelChangeResult, PossibleValues, Unique};
use super::pixel::Pixel;
/// Trait representing an error during Grid initialization. The only possible error is currently SizeMustNotBeZero.
#[derive(Debug)]
pub enum SizeErr {
SizeMustNotBeZero,
}
/// A microwfc grid.
pub struct Grid<T: PossibleValues, const D: usize> {
pub(crate) size: [usize; D],
pub(crate) data: Array<Pixel<T>, D>,
}
impl<T: PossibleValues, const D: usize> Grid<T, D> {
/// Constructs a new Grid using the n-dimensional size.
pub fn new(size: [usize; D]) -> Result<Self, SizeErr> {
if size.iter().any(|x| *x == 0) {
return Err(SizeErr::SizeMustNotBeZero);
}
Ok(Self {
size,
data: Array::new(size),
})
}
/// Returns the n-dimensional size of the Grid.
/// In all default implementations, this returns a n-tuple where n is the dimensionality of the Grid.
pub fn size(&self) -> [usize; D] {
self.size
}
/// Returns an immutable reference to the inner microNDArray
pub fn as_inner(&self) -> &Array<Pixel<T>, D> {
&self.data
}
/// Returns an mutable reference to the inner microNDArray
pub fn as_mut_inner(&mut self) -> &mut Array<Pixel<T>, D> {
&mut self.data
}
/// Clones and returns a Pixel from the Grid.
pub fn get_item(&self, location: [usize; D]) -> Pixel<T> {
self.data[location].clone()
}
/// Sets a Pixel in the Grid.
pub fn set_item(&mut self, location: [usize; D], item: Pixel<T>) {
self.data[location] = item;
}
/// Returns unidirectional neighbors, meaning only neighbord with one common face.
/// This means the corners will not be returned.
pub fn unidirectional_neighbors(&self, location: [usize; D]) -> Vec<([usize; D], Pixel<T>)> {
self.neighbors(location, 1)
.into_iter()
.filter(|neighbor| {
neighbor
.0
.iter()
.enumerate()
.filter(|(i, x)| location[*i].overflowing_sub(**x).0 != 0)
.count()
== 1
})
.collect()
}
/// Returns all neighbors, including ones touching only at a single point.
/// This does return corners.
pub fn neighbors(&self, location: [usize; D], distance: usize) -> Vec<([usize; D], Pixel<T>)> {
let mut r = Vec::new();
let start_location: [usize; D] = location
.into_iter()
.map(|x| if x < distance { x } else { x - distance })
.collect::<Vec<_>>()
.try_into()
.unwrap();
let mut loc = start_location;
loop {
if loc != location {
r.push((loc, self.get_item(loc)));
}
for n in 0..D {
loc[n] += 1;
if loc[n] > location[n] + distance || loc[n] == self.size[n] {
loc[n] = start_location[n];
} else {
break;
}
}
if loc == start_location {
// will reset to [0; D] when end is reached, but will NOT reach that before as it is incremented first
break;
}
}
r
}
/// Checks if a location is inside the Grid, then returns its Grid coordinates.
pub fn check_loc(&self, location: [i128; D]) -> Option<[usize; D]> {
for (i, dimensionality) in self.size.iter().enumerate() {
if location[i] < 0 || location[i] >= *dimensionality as i128 {
return None;
}
}
Some(location.map(|x| x as usize))
}
/// Checks if the Grid is valid
pub fn check_validity<F>(&mut self, test: F) -> Result<(), [usize; D]>
where
F: Fn(&Grid<T, D>, [usize; D], &T, f32) -> (bool, f32),
{
let mut data = self.data.clone();
for (loc, pixel) in data.iter_mut() {
if pixel.determined_value.is_some() {
continue;
}
if let PixelChangeResult::Invalid =
pixel.recalc(self, loc, &test, None::<&mut rand::rngs::mock::StepRng>)
{
return Err(loc);
}
}
self.data = data;
Ok(())
}
fn update<F>(
&mut self,
to_update: &mut Vec<([usize; D], Pixel<T>)>,
(location, mut pixel): ([usize; D], Pixel<T>),
test: &F,
effect_distance: usize,
rng: &mut impl Rng,
should_collapse: bool,
) -> PixelChangeResult
where
F: Fn(&Grid<T, D>, [usize; D], &T, f32) -> (bool, f32),
{
let result = pixel.recalc(
self,
location,
test,
if should_collapse { Some(rng) } else { None },
);
match result {
PixelChangeResult::Invalid => {
return PixelChangeResult::Invalid;
}
PixelChangeResult::Updated => {
self.data[location] = pixel;
let mut to_add = self.neighbors(location, effect_distance);
to_add.shuffle(rng);
to_update.append(&mut to_add);
}
PixelChangeResult::Unchanged => return result,
}
result
}
/// Collapses a single Pixel and updates neighbors. This will return false if the Grid is invalid.
/// Please note that this function is not very useful, and you should use wfc instead
pub fn collapse<F, R>(
&mut self,
test: F,
effect_distance: usize,
rng: &mut R,
item: ([usize; D], Pixel<T>),
) -> Result<(), [usize; D]>
where
F: Fn(&Grid<T, D>, [usize; D], &T, f32) -> (bool, f32),
R: Rng,
{
let mut to_update = vec![item];
let mut i = 0;
while !to_update.is_empty() {
let item = to_update.remove(0);
let r = self.update(
&mut to_update,
(item.0, item.1.clone()),
&test,
effect_distance,
rng,
i == 0,
);
if r == PixelChangeResult::Invalid {
return Err(item.0);
}
i += 1;
}
Ok(())
}
/// Performs the wave-function-collapse algorithm on the Grid.
/// This returns if the algorithm was successful, and the state of the Grid is not guaranteed
/// to be valid if it returns false, but there is never unsafety in reading from the Grid.
///
/// The chance parameter determines the likelyhood of a random collapse happening anywhere on the
/// grid. In some strict environments, this can cause unsolvable grids.
pub fn wfc<F, R>(
&mut self,
test: F,
effect_distance: usize,
rng: &mut R,
chance: f32,
on_update: impl Fn(&Self),
) -> Result<(), [usize; D]>
where
F: Fn(&Grid<T, D>, [usize; D], &T, f32) -> (bool, f32),
R: Rng,
{
self.check_validity(&test)?;
loop {
let backup = self.data.clone();
// Get all items that haven't been determined yet
let to_update: Vec<_> = self
.data
.iter()
.filter(|x| x.1.determined_value.is_none())
.collect();
if to_update.is_empty() {
// We're done
break;
}
// Get a random pixel with minimal entropy and collapse it
let min = to_update
.iter()
.min_by_key(|x| x.1.possible_values.unique().len())
.unwrap() // SAFETY: This is safe because the list is known to be non-empty.
.1
.possible_values
.unique()
.len();
let to_update = if rng.gen::<f32>() > chance {
to_update
.into_iter()
.filter(|x| x.1.possible_values.unique().len() == min)
.map(|x| (x.0, x.1.clone()))
.choose(rng)
.unwrap() // SAFETY: This is safe because the list is known to be non-empty.
} else {
to_update
.into_iter()
.choose(rng)
.map(|x| (x.0, x.1.clone()))
.unwrap() // SAFETY: This is safe because the list is known to be non-empty.
};
let loc = to_update.0;
// Now collapse the Pixel
if self
.collapse(&test, effect_distance, rng, to_update)
.is_err()
{
self.data = backup;
self.data[loc] = Pixel::default();
}
on_update(self);
}
Ok(())
}
}