kahuna/
lib.rs

1//! Wave Function Collapse
2//! 
3//! Provides an implementation of the wave function collapse algorithm.
4//!
5//! Wave function collapse works by iteratively "collapsing" a collecion of
6//! cells (such as a square grid) from all possible states to only the states
7//! possible with a given ruleset, selecting randomly where ambiguous.
8
9mod space;
10mod collapse_rule;
11mod state;
12mod set_state;
13mod all_state;
14pub mod square_grid;
15pub mod bitset_state;
16pub mod hashset_state;
17pub mod set_rule;
18
19use std::{collections::{HashSet, VecDeque}};
20
21use rand::{thread_rng, Rng};
22pub use space::*;
23pub use state::*;
24pub use collapse_rule::*;
25pub use set_state::*;
26pub use all_state::*;
27
28fn find_next_to_collapse<St: State, Sp: Space<St>>(unresoved_set: &mut HashSet<Sp::Coordinate>, lowest_entropy_set: &mut Vec<Sp::Coordinate>, resolved_set: &mut HashSet<Sp::Coordinate>, space: &Sp) -> Option<Sp::Coordinate> {
29	let mut lowest_entropy = std::u32::MAX;
30	lowest_entropy_set.clear();
31	resolved_set.clear();
32	for unresolved in unresoved_set.iter() {
33		let entropy = space[*unresolved].entropy();
34		if entropy == 0 {
35			resolved_set.insert(*unresolved);
36		} else if entropy < lowest_entropy {
37			lowest_entropy = entropy;
38			lowest_entropy_set.clear();
39			lowest_entropy_set.push(*unresolved);
40		} else if entropy == lowest_entropy {
41			lowest_entropy_set.push(*unresolved);
42		}
43	}
44	unresoved_set.retain(|x| !resolved_set.contains(x));
45	if lowest_entropy_set.len() == 0 {
46		return None;
47	} else {
48		Some(lowest_entropy_set[thread_rng().gen_range(0..lowest_entropy_set.len())])
49	}
50}
51
52/// Perform the wave function collapse algorithm on a given state-space with
53/// the provided collapse rule.
54pub fn collapse<Rule: CollapseRule<St, Sp>, St: State, Sp: Space<St>>(space: &mut Sp, rule: &Rule) {
55	let mut unresolved_set = HashSet::new();
56	let mut resolved_set = HashSet::new();
57	let mut lowest_entropy_set = Vec::new();
58	let neighbor_directions = rule.neighbor_offsets();
59	for coord in &space.coordinate_list()[..] {
60		if space[*coord].entropy() > 0 {
61			unresolved_set.insert(*coord);
62		}
63	}
64	let mut neighbors = vec![None; neighbor_directions.len()].into_boxed_slice();
65	let mut neighbor_states = vec![Option::<St>::None; neighbor_directions.len()].into_boxed_slice();
66	let mut to_propogate = VecDeque::new();
67	
68	for coordinate in unresolved_set.iter() {
69		to_propogate.push_back(*coordinate);
70	}
71	run_propogation(space, rule, &mut to_propogate, &neighbor_directions, &mut neighbors, &mut neighbor_states);
72	
73	while let Some(to_collapse) = find_next_to_collapse(&mut unresolved_set, &mut lowest_entropy_set, &mut resolved_set, space) {
74		to_propogate.clear();
75		space.neighbors(to_collapse, &neighbor_directions, &mut neighbors);
76		for i in 0 .. neighbor_directions.len() {
77			neighbor_states[i] = neighbors[i].map(|coord| space[coord].clone());
78		}
79		rule.observe(&mut space[to_collapse], &neighbor_states[..]);
80		for i in 0..neighbor_directions.len() {
81			if let Some(neighbor_coord) = neighbors[i] {
82				to_propogate.push_back(neighbor_coord);
83			}
84		}
85		run_propogation(space, rule, &mut to_propogate, &neighbor_directions, &mut neighbors, &mut neighbor_states);
86	}
87}
88
89fn run_propogation<Rule: CollapseRule<St, Sp>, St: State, Sp: Space<St>>(space: &mut Sp, rule: &Rule, to_propogate: &mut VecDeque<Sp::Coordinate>, neighbor_directions: &[Sp::CoordinateDelta], neighbors: &mut [Option<Sp::Coordinate>], neighbor_states: &mut [Option<St>]) {
90	while let Some(propogating) = to_propogate.pop_front() {
91		let entropy_before = space[propogating].entropy();
92		
93		if entropy_before != 0 {
94			space.neighbors(propogating, &neighbor_directions, neighbors);
95			for i in 0 .. neighbor_directions.len() {
96				neighbor_states[i] = neighbors[i].map(|coord| space[coord].clone());
97			}
98			rule.collapse(&mut space[propogating], &neighbor_states[..]);
99			let entropy_after = space[propogating].entropy();
100			
101			if entropy_after < entropy_before {
102				for i in 0 .. neighbor_directions.len() {
103					if let Some(neighbor) = neighbors[i] {
104						if space[neighbor].entropy() != 0 {
105							to_propogate.push_back(neighbor);
106						}
107					}
108				}
109			}
110		}
111	}
112}
kahuna/lib.rs

kahuna/
lib.rs
