simple_tiled_wfc/
grid_generation.rs

1use {
2    rand::{thread_rng, Rng},
3    std::{
4        hash::Hash,
5        collections::{HashMap, VecDeque},
6        sync::mpsc::{channel, Sender}
7    },
8    bitsetium::{BitSearch, BitEmpty, BitSet, BitIntersection, BitUnion, BitTestNone},
9    crate::{
10        grid_drawing::{get_brush_ranges, DRAW_LOOKUP},
11        get_bits_set_count,
12        make_one_bit_entry,
13        make_initial_probabilities,
14        errors::WfcError,
15        BitsIterator
16    }
17};
18
19struct NeighbourQueryResult {
20    north: Option<usize>,
21    south: Option<usize>,
22    east: Option<usize>,
23    west: Option<usize>,
24}
25
26/// A trait which lets a user to define exact heuristic on how minimal entropy slot should be chosen
27pub trait WfcEntropyHeuristic<TBitSet>
28    where TBitSet:
29    BitSearch + BitEmpty + BitSet + BitIntersection +
30    BitUnion + BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
31    BitUnion<Output = TBitSet>
32{
33    /// A function which lets a user to define exact heuristic on how minimal entropy slot should be chosen
34    fn choose_next_collapsed_slot(
35        &self,
36        width: usize,
37        height: usize,
38        modules: &[WfcModule<TBitSet>],
39        available_indices: &[usize]
40    ) -> usize;
41}
42
43/// Default WfcEntropyHeuristic used by a library
44///
45/// It just chooses a random slot from a set of slots and does not do anything extra
46#[derive(Default)]
47pub struct DefaultEntropyHeuristic;
48impl<TBitSet> WfcEntropyHeuristic<TBitSet> for DefaultEntropyHeuristic
49    where TBitSet:
50    BitSearch + BitEmpty + BitSet + BitIntersection +
51    BitUnion + BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
52    BitUnion<Output = TBitSet> {
53    fn choose_next_collapsed_slot(
54        &self,
55        _width: usize,
56        _height: usize,
57        _modules: &[WfcModule<TBitSet>],
58        available_indices: &[usize]
59    ) -> usize {
60        let mut rng = thread_rng();
61        rng.gen_range(0, available_indices.len())
62    }
63}
64
65/// A trait which lets a user to define exact heuristic on how to chose a variant from a
66/// probability set inside a slot
67pub trait WfcEntropyChoiceHeuristic<TBitSet>
68    where TBitSet:
69    BitSearch + BitEmpty + BitSet + BitIntersection +
70    BitUnion + BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
71    BitUnion<Output = TBitSet>
72{
73    /// A function which lets a user to define exact heuristic on how to chose a variant from a
74    /// probability set inside a slot
75    fn choose_least_entropy_bit(
76        &self,
77        width: usize,
78        height: usize,
79        row: usize,
80        column: usize,
81        modules: &[WfcModule<TBitSet>],
82        slot_bits: &TBitSet,
83    ) -> Option<usize>;
84}
85
86/// Default WfcEntropyChoiceHeuristic used by a library
87///
88/// It just chooses a random non-zero bit from a bitset and does not do anything extra
89#[derive(Default)]
90pub struct DefaultEntropyChoiceHeuristic;
91impl<TBitSet> WfcEntropyChoiceHeuristic<TBitSet> for DefaultEntropyChoiceHeuristic
92    where TBitSet:
93    BitSearch + BitEmpty + BitSet + BitIntersection +
94    BitUnion + BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
95    BitUnion<Output = TBitSet> {
96    fn choose_least_entropy_bit(
97        &self,
98        _width: usize,
99        _height: usize,
100        _row: usize,
101        _column: usize,
102        _modules: &[WfcModule<TBitSet>],
103        slot_bits: &TBitSet
104    ) -> Option<usize>
105    {
106        let mut rng = thread_rng();
107        let random_bit_id = rng.gen_range(0, get_bits_set_count(slot_bits));
108        let mut iterator = BitsIterator::new(slot_bits);
109        Some(iterator.nth(random_bit_id).unwrap())
110    }
111}
112
113/// A building block of WFC, which lets user to set adjacency rules for tiles
114///
115/// Each **neighbours** bitset are expected to hold indices of neighbour modules which will be
116/// hold in a &[WfcModule] used by **WfcContext**
117#[derive(Copy, Clone)]
118pub struct WfcModule<TBitSet>
119    where TBitSet:
120        BitSearch + BitEmpty + BitSet + BitIntersection +
121        BitUnion + BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
122        BitUnion<Output = TBitSet>
123{
124    /// North neighbouring modules
125    pub north_neighbours: TBitSet,
126
127    /// South neighbouring modules
128    pub south_neighbours: TBitSet,
129
130    /// East neighbouring modules
131    pub east_neighbours: TBitSet,
132
133    /// West neighbouring modules
134    pub west_neighbours: TBitSet,
135}
136
137impl<TBitSet> WfcModule<TBitSet>
138    where TBitSet:
139    BitSearch + BitEmpty + BitSet + BitIntersection +
140    BitUnion + BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
141    BitUnion<Output = TBitSet>
142{
143    /// A constructor of a module with all neighbouring sets empty
144    pub fn new() -> Self {
145        Self {
146            north_neighbours: TBitSet::empty(),
147            south_neighbours: TBitSet::empty(),
148            east_neighbours: TBitSet::empty(),
149            west_neighbours: TBitSet::empty(),
150        }
151    }
152
153    /// A function which adds a neighbour on a north side
154    pub fn add_north_neighbour(&mut self, idx: usize) {
155        self.north_neighbours.set(idx)
156    }
157
158    /// A function which adds a neighbour on a south side
159    pub fn add_south_neighbour(&mut self, idx: usize) {
160        self.south_neighbours.set(idx)
161    }
162
163    /// A function which adds a neighbour on an east side
164    pub fn add_east_neighbour(&mut self, idx: usize) {
165        self.east_neighbours.set(idx)
166    }
167
168    /// A function which adds a neighbour on a west side
169    pub fn add_west_neighbour(&mut self, idx: usize) {
170        self.west_neighbours.set(idx)
171    }
172}
173
174enum WfcContextBuilderExtra<'a, TBitSet>
175    where TBitSet:
176        BitSearch + BitEmpty + BitSet + BitIntersection + BitUnion +
177        BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
178        BitUnion<Output = TBitSet>
179{
180    General,
181    UsingCustomInitializer { initializer: Box<dyn Fn(usize, usize) -> TBitSet>},
182    FromExisting { collapse: &'a [usize] }
183}
184
185/// A builder with a fluent API to create WfcContext
186pub struct WfcContextBuilder<'a, TBitSet>
187    where TBitSet:
188        BitSearch + BitEmpty + BitSet + BitIntersection + BitUnion +
189        BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
190        BitUnion<Output = TBitSet>
191{
192    extra: WfcContextBuilderExtra<'a, TBitSet>,
193    modules: &'a [WfcModule<TBitSet>],
194    width: usize,
195    height: usize,
196    entropy_heuristic: Box<dyn WfcEntropyHeuristic<TBitSet>>,
197    entropy_choice_heuristic: Box<dyn WfcEntropyChoiceHeuristic<TBitSet>>,
198    history_transmitter: Option<Sender<(usize, TBitSet)>>
199}
200
201impl<'a, TBitSet> WfcContextBuilder<'a, TBitSet>
202    where TBitSet:
203        BitSearch + BitEmpty + BitSet + BitIntersection + BitUnion +
204        BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
205        BitUnion<Output = TBitSet>
206{
207    /// A constructor with minimally needed info to construct a context
208    pub fn new(modules: &'a [WfcModule<TBitSet>], width: usize, height: usize) -> Self {
209        Self {
210            extra: WfcContextBuilderExtra::General,
211            modules,
212            width,
213            height,
214            entropy_heuristic: Box::new(DefaultEntropyHeuristic::default()),
215            entropy_choice_heuristic: Box::new(DefaultEntropyChoiceHeuristic::default()),
216            history_transmitter: None
217        }
218    }
219
220    /// A function which lets user to start collapse using a result of an other.
221    /// **collapse** here holds indices of modules which have been chosen for each slot of a grid
222    /// last time
223    pub fn use_existing_collapse(self, collapse: &'a [usize]) -> Self {
224        Self {
225            extra: WfcContextBuilderExtra::FromExisting { collapse },
226            ..self
227        }
228    }
229
230    /// A function which lets user to override default initialization of slots.
231    /// This could be useful when user wants different sets of tiles be possible on different
232    /// places of a grid
233    pub fn use_custom_initializer(self, initializer: Box<dyn Fn(usize, usize) -> TBitSet>) -> Self {
234        Self {
235            extra: WfcContextBuilderExtra::UsingCustomInitializer { initializer },
236            ..self
237        }
238    }
239
240    /// A function which lets a user to set its own implementation of WfcEntropyHeuristic
241    pub fn with_entropy_heuristic(
242        self,
243        heuristic: Box<dyn WfcEntropyHeuristic<TBitSet>>
244    ) -> Self {
245        Self {
246            entropy_heuristic: heuristic,
247            ..self
248        }
249    }
250
251    /// A function which lets a user to set its own implementation of WfcEntropyChoiceHeuristic
252    pub fn with_entropy_choice_heuristic(
253        self,
254        heuristic: Box<dyn WfcEntropyChoiceHeuristic<TBitSet>>
255    ) -> Self {
256        Self {
257            entropy_choice_heuristic: heuristic,
258            ..self
259        }
260    }
261
262    /// A function which lets a user to set a transmitter which will send all steps of an algorithm
263    /// so the user could visualize it in time
264    pub fn with_history_transmitter(
265        self,
266        history_transmitter: Sender<(usize, TBitSet)>
267    ) -> Self {
268        Self {
269            history_transmitter: Some(history_transmitter),
270            ..self
271        }
272    }
273
274    /// A function which builds a context
275    pub fn build(self) -> WfcContext<'a, TBitSet> {
276        match self.extra {
277            WfcContextBuilderExtra::General => {
278                WfcContext::new(
279                    self.modules,
280                    self.width,
281                    self.height,
282                    self.entropy_heuristic,
283                    self.entropy_choice_heuristic,
284                    None,
285                    self.history_transmitter
286                )
287            }
288            WfcContextBuilderExtra::FromExisting { collapse } => {
289                WfcContext::from_existing_collapse(
290                    self.modules,
291                    self.width,
292                    self.height,
293                    self.entropy_heuristic,
294                    self.entropy_choice_heuristic,
295                    collapse,
296                    self.history_transmitter
297                )
298            }
299            WfcContextBuilderExtra::UsingCustomInitializer { initializer } => {
300                WfcContext::new(
301                    self.modules,
302                    self.width,
303                    self.height,
304                    self.entropy_heuristic,
305                    self.entropy_choice_heuristic,
306                    Some(initializer),
307                    self.history_transmitter
308                )
309            }
310        }
311    }
312}
313
314/// A heart of WFC. Does an actual collapse work
315pub struct WfcContext<'a, TBitSet>
316    where TBitSet:
317        BitSearch + BitEmpty + BitSet + BitIntersection + BitUnion +
318        BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
319        BitUnion<Output = TBitSet>
320{
321    modules: &'a [WfcModule<TBitSet>],
322    width: usize,
323    height: usize,
324    grid: Vec<TBitSet>,
325    north_memoizer: HashMap<TBitSet, TBitSet>,
326    south_memoizer: HashMap<TBitSet, TBitSet>,
327    east_memoizer: HashMap<TBitSet, TBitSet>,
328    west_memoizer: HashMap<TBitSet, TBitSet>,
329    entropy_heuristic: Box<dyn WfcEntropyHeuristic<TBitSet>>,
330    entropy_choice_heuristic: Box<dyn WfcEntropyChoiceHeuristic<TBitSet>>,
331    buckets: Vec<Vec<usize>>,
332    history_transmitter: Option<Sender<(usize, TBitSet)>>
333}
334
335macro_rules! neighbour_func_impl {
336    ($func_name:ident of $memo_name:ident and $neighbours_member:ident) => {
337        fn $func_name(&mut self, module_variants: &TBitSet) -> TBitSet {
338            self.$memo_name
339                .get(module_variants)
340                .map(|it| *it)
341                .unwrap_or_else(|| {
342                    let mut set = TBitSet::empty();
343                    for module_id in BitsIterator::new(module_variants) {
344                        set = set.union(self.modules[module_id].$neighbours_member);
345                    }
346                    self.$memo_name.insert(module_variants.clone(), set);
347                    set
348                })
349        }
350    }
351}
352
353impl<'a, TBitSet> WfcContext<'a, TBitSet>
354    where TBitSet:
355        BitSearch + BitEmpty + BitSet + BitIntersection + BitUnion +
356        BitTestNone + Hash + Eq + Copy + BitIntersection<Output = TBitSet> +
357        BitUnion<Output = TBitSet>
358{
359    fn new(
360        modules: &'a [WfcModule<TBitSet>],
361        width: usize,
362        height: usize,
363        entropy_heuristic: Box<dyn WfcEntropyHeuristic<TBitSet>>,
364        entropy_choice_heuristic: Box<dyn WfcEntropyChoiceHeuristic<TBitSet>>,
365        initializer: Option<Box<dyn Fn(usize, usize) -> TBitSet>>,
366        history_transmitter: Option<Sender<(usize, TBitSet)>>
367    ) -> Self {
368        let mut grid: Vec<TBitSet> = Vec::new();
369        let mut buckets: Vec<Vec<usize>> = vec![Vec::new(); modules.len()+1];
370        let initial_probabilities = make_initial_probabilities(modules.len());
371        for idx in 0..(width * height) {
372            if let Some(sender) = &history_transmitter {
373                sender.send((idx, initial_probabilities)).unwrap();
374            }
375            if let Some(init) = &initializer {
376                let row = idx / width;
377                let col = idx % width;
378                let value = init(row, col);
379                buckets[get_bits_set_count(&value)].push(idx);
380                grid.push(value);
381            } else {
382                grid.push(initial_probabilities);
383                buckets[modules.len()].push(idx);
384            }
385        }
386        Self {
387            modules,
388            width,
389            height,
390            grid,
391            north_memoizer: HashMap::new(),
392            south_memoizer: HashMap::new(),
393            east_memoizer: HashMap::new(),
394            west_memoizer: HashMap::new(),
395            entropy_heuristic,
396            entropy_choice_heuristic,
397            buckets,
398            history_transmitter
399        }
400    }
401
402    fn from_existing_collapse(
403        modules: &'a [WfcModule<TBitSet>],
404        width: usize,
405        height: usize,
406        entropy_heuristic: Box<dyn WfcEntropyHeuristic<TBitSet>>,
407        entropy_choice_heuristic: Box<dyn WfcEntropyChoiceHeuristic<TBitSet>>,
408        collapse: &[usize],
409        history_transmitter: Option<Sender<(usize, TBitSet)>>
410    ) -> Self {
411        assert_eq!(collapse.len(), width * height);
412
413        let mut grid: Vec<TBitSet> = Vec::new();
414        let mut buckets: Vec<Vec<usize>> = vec![Vec::new(); modules.len()+1];
415        for idx in 0..(width * height) {
416            buckets[1].push(idx);
417            grid.push(make_one_bit_entry(collapse[idx]));
418        }
419        Self {
420            modules,
421            width,
422            height,
423            grid,
424            north_memoizer: HashMap::new(),
425            south_memoizer: HashMap::new(),
426            east_memoizer: HashMap::new(),
427            west_memoizer: HashMap::new(),
428            entropy_heuristic,
429            entropy_choice_heuristic,
430            buckets,
431            history_transmitter
432        }
433    }
434
435    /// A function which lets a user to "draw" some new parts above existing collapse result
436    ///
437    /// When the work is done, the result is being sent through *result_transmitter* to a
438    /// corresponding receiver
439    ///
440    /// The successful result is composed of a vec with a `size = (self.width * self.height)`
441    /// indices of modules which have been chosen of corresponding slots during collapse
442    pub fn local_collapse(
443        &mut self,
444        row: usize,
445        column: usize,
446        module: usize,
447        result_transmitter: Sender<Result<Vec<usize>, WfcError>>
448    ) {
449        let old_grid = self.grid.clone();
450        let old_buckets = self.buckets.clone();
451
452        let initial_probabilities: TBitSet = make_initial_probabilities(self.modules.len());
453
454        for brush_id in 0..6 {
455            // for test just draw a cross and exit
456            let (hor_range_dest, vert_range_dest, hor_range_source, vert_range_source) =
457                get_brush_ranges(
458                    row,
459                    column,
460                    brush_id,
461                    self.width,
462                    self.height
463                );
464
465            if brush_id > 0 {
466                // backtrack
467                self.buckets = old_buckets.clone();
468                for j in vert_range_dest.clone() {
469                    for i in hor_range_dest.clone() {
470                        self.grid[j * self.width + i] = old_grid[j * self.width + i];
471                    }
472                }
473            }
474
475            let (v_zip, h_zip) = (
476                vert_range_dest.clone().zip(vert_range_source),
477                hor_range_dest.clone().zip(hor_range_source)
478            );
479
480            let lookup = &(DRAW_LOOKUP[brush_id]);
481            for (j_dest, j_source) in v_zip.clone() {
482                for (i_dest, i_source) in h_zip.clone() {
483                    if lookup[j_source * 15 + i_source] == 1 {
484                        continue;
485                    }
486
487                    let mut probability_set = initial_probabilities;
488                    let idx = j_dest * self.width + i_dest;
489
490                    let neighbours = self.get_neighbours(idx);
491
492                    if neighbours.north.is_some() && lookup[(j_source - 1) * 15 + i_source] == 1 {
493                        let north_neighbour_slot = self.grid[neighbours.north.unwrap()];
494                        probability_set = probability_set.intersection(
495                            self.south_neighbours(&north_neighbour_slot)
496                        );
497                    }
498                    if neighbours.south.is_some() && lookup[(j_source + 1) * 15 + i_source] == 1 {
499                        let south_neighbour_slot = self.grid[neighbours.south.unwrap()];
500                        probability_set = probability_set.intersection(
501                            self.north_neighbours(&south_neighbour_slot)
502                        );
503                    }
504                    if neighbours.east.is_some() && lookup[j_source * 15 + i_source + 1] == 1 {
505                        let east_neighbour_slot = self.grid[neighbours.east.unwrap()];
506                        probability_set = probability_set.intersection(
507                            self.west_neighbours(&east_neighbour_slot)
508                        );
509                    }
510                    if neighbours.west.is_some() && lookup[j_source * 15 + i_source - 1] == 1 {
511                        let west_neighbour_slot = self.grid[neighbours.west.unwrap()];
512                        probability_set = probability_set.intersection(
513                            self.east_neighbours(&west_neighbour_slot)
514                        );
515                    }
516                    self.set(idx, probability_set);
517                }
518            }
519            self.set_module(row, column, module);
520
521            let (tx, rc) = channel();
522
523            self.collapse(10, tx.clone());
524
525            match rc.recv() {
526                Ok(res) => {
527                    if res.is_ok() {
528                        result_transmitter.send(res).unwrap();
529                        return;
530                    }
531                }
532                Err(_) => {
533                    result_transmitter.send(Err(WfcError::SomeCreepyShit)).unwrap();
534                    return;
535                }
536            }
537        }
538        result_transmitter.send(Err(WfcError::TooManyContradictions)).unwrap();
539    }
540
541    fn set(&mut self, idx: usize, value: TBitSet) {
542        let old_v = self.grid[idx];
543        let old_bits_set = get_bits_set_count(&old_v);
544        let new_bits_set = get_bits_set_count(&value);
545
546        let len = self.buckets[old_bits_set].len();
547
548        for i in (0..len).rev() {
549            if self.buckets[old_bits_set][i].eq(&idx) {
550                self.buckets[old_bits_set][i] = self.buckets[old_bits_set][len-1];
551                self.buckets[old_bits_set].remove(len-1);
552                break;
553            }
554        }
555
556        self.buckets[new_bits_set].push(idx);
557        self.grid[idx] = value;
558        if let Some(sender) = &self.history_transmitter {
559            sender.send((idx, value)).unwrap();
560        }
561    }
562
563    /// A function which lets a user to "preset" some modules before doing actual collapse
564    pub fn set_module(&mut self, row: usize, column: usize, module: usize) {
565        let idx = row * self.width + column;
566        self.set(idx, make_one_bit_entry(module));
567        let mut propagation_queue: VecDeque<usize> = VecDeque::new();
568        propagation_queue.push_back(idx);
569        self.propagate(&mut propagation_queue);
570    }
571
572    /// A function which is making actual collapse
573    ///
574    /// When the work is done, the result is being sent through *result_transmitter* to a
575    /// corresponding receiver
576    ///
577    /// The successful result is composed of a vec with a `size = (self.width * self.height)`
578    /// indices of modules which have been chosen of corresponding slots during collapse
579    pub fn collapse(
580        &mut self,
581        max_contradictions: i32,
582        result_transmitter: Sender<Result<Vec<usize>, WfcError>>
583    ) {
584        let mut contradictions_allowed = max_contradictions;
585        let old_grid = self.grid.clone();
586        let old_buckets = self.buckets.clone();
587        let mut propagation_queue: VecDeque<usize> = VecDeque::new();
588        'outer: loop {
589            'backtrack: loop {
590                // I. Detect quit condition
591                if !self.buckets[0].is_empty() {
592                    break 'backtrack; // we found contradiction and need to backtrack
593                }
594                let mut min_bucket_id = 1;
595                'bucket_search: for i in 2_..self.buckets.len() {
596                    if !self.buckets[i].is_empty() {
597                        min_bucket_id = i;
598                        break 'bucket_search;
599                    }
600                }
601                if min_bucket_id == 1 {
602                    result_transmitter.send(Ok(self.grid
603                        .iter()
604                        .map(|it| it.find_first_set(0).unwrap())
605                        .collect()
606                    )).unwrap();
607                    return; // We are done!
608                }
609
610                // II. Choose random slot with a minimum probability set and collapse it's
611                // set to just one module
612                if self.collapse_next_slot(&mut propagation_queue, min_bucket_id).is_none() {
613                    break 'backtrack; // couldn't find next slot to collapse, need to backtrack
614                }
615
616                // III. While propagation queue is not empty, propagate probability set to neighbours
617                // If neighbour's probability set is changed, add its index to a propagation queue
618                self.propagate(&mut propagation_queue);
619            }
620
621            // In the case of backtrack we need to bring the state of a grid back to what it was
622            // at the beginning. The propagation queue need to be flushed too, obviously
623            for i in 0..self.grid.len() {
624                self.grid[i] = old_grid[i];
625                if let Some(sender) = &self.history_transmitter {
626                    sender.send((i, old_grid[i])).unwrap();
627                }
628            }
629            self.buckets = old_buckets.clone();
630            propagation_queue.clear();
631
632            if contradictions_allowed == 0 {
633                break 'outer;
634            }
635
636            contradictions_allowed -= 1;
637        }
638        result_transmitter.send(Err(WfcError::TooManyContradictions)).unwrap();
639    }
640
641    fn get_neighbours(&self, idx: usize) -> NeighbourQueryResult {
642        let row = idx / self.width;
643        let column = idx % self.width;
644        NeighbourQueryResult {
645            north: if row == 0 { None } else {Some(idx-self.width)},
646            south: if row >= self.height-1 { None } else {Some(idx+self.width)},
647            east: if column >= self.width-1 { None } else {Some(idx+1)},
648            west: if column == 0 { None } else {Some(idx-1)}
649        }
650    }
651
652    fn propagate(&mut self, mut propagation_queue: &mut VecDeque<usize>) {
653        'propagation: while !propagation_queue.is_empty() {
654            let next_id = propagation_queue.pop_front().unwrap();
655            let nbr_ids = self.get_neighbours(next_id);
656            for neighbour in &[nbr_ids.north, nbr_ids.south, nbr_ids.east, nbr_ids.west] {
657                if let &Some(neighbour_slot_id) = neighbour {
658                    if get_bits_set_count(&self.grid[neighbour_slot_id]) != 1 {
659                        self.propagate_slot(&mut propagation_queue, neighbour_slot_id);
660                        if self.grid[neighbour_slot_id].test_none() {
661                            // We hit a contradiction.
662                            break 'propagation;
663                        }
664                    }
665                }
666            }
667        }
668    }
669
670    fn propagate_slot(&mut self, propagation_queue: &mut VecDeque<usize>, neighbour_id: usize) {
671        let mut probability_set: TBitSet = make_initial_probabilities(self.modules.len());
672        let nbr_ids = self.get_neighbours(neighbour_id);
673        if let Some(west_neighbour) = nbr_ids.west {
674            let west_neighbour = self.grid[west_neighbour];
675            probability_set = probability_set.intersection(self.east_neighbours(&west_neighbour));
676        }
677        if let Some(east_neighbour) = nbr_ids.east {
678            let east_neighbour = self.grid[east_neighbour];
679            probability_set = probability_set.intersection(self.west_neighbours(&east_neighbour));
680        }
681        if let Some(north_neighbour) = nbr_ids.north {
682            let north_neighbour = self.grid[north_neighbour];
683            probability_set = probability_set.intersection(self.south_neighbours(&north_neighbour));
684        }
685        if let Some(south_neighbour) = nbr_ids.south {
686            let south_neighbour = self.grid[south_neighbour];
687            probability_set = probability_set.intersection(self.north_neighbours(&south_neighbour));
688        }
689
690        if self.grid[neighbour_id].eq(&probability_set) { return; }
691
692        self.set(neighbour_id, probability_set);
693
694        if probability_set.test_none() { return; }
695        propagation_queue.push_back(neighbour_id);
696    }
697
698    fn collapse_next_slot(
699        &mut self,
700        propagation_queue: &mut VecDeque<usize>,
701        min_bucket_id: usize
702    ) -> Option<TBitSet> {
703        let next_slot_id_in_bucket = self.entropy_heuristic.choose_next_collapsed_slot(
704            self.width,
705            self.height,
706            self.modules,
707            &self.buckets[min_bucket_id]
708        );
709        let slot_id = self.buckets[min_bucket_id][next_slot_id_in_bucket];
710        let next_bit = self.entropy_choice_heuristic.choose_least_entropy_bit(
711            self.width,
712            self.height,
713            slot_id / self.width,
714            slot_id % self.width,
715            self.modules,
716            &self.grid[slot_id]
717        )?;
718        let new_slot = make_one_bit_entry(next_bit);
719        self.grid[slot_id] = new_slot;
720        if let Some(sender) = &self.history_transmitter {
721            sender.send((slot_id, new_slot)).unwrap();
722        }
723        self.buckets[min_bucket_id].remove(next_slot_id_in_bucket);
724        self.buckets[1].push(slot_id);
725        propagation_queue.push_back(slot_id);
726        Some(new_slot)
727    }
728
729    neighbour_func_impl!{ east_neighbours of east_memoizer and east_neighbours }
730    neighbour_func_impl!{ west_neighbours of west_memoizer and west_neighbours }
731    neighbour_func_impl!{ north_neighbours of north_memoizer and north_neighbours }
732    neighbour_func_impl!{ south_neighbours of south_memoizer and south_neighbours }
733}
simple_tiled_wfc/grid_generation.rs

simple_tiled_wfc/
grid_generation.rs
