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
|
//! The `wfc` module contains the implementation of the
//! Wave Function Collapse algorithm for procedural generation of the `Floor`.
use crate::map::Tile;
use crate::pos::Pos;
/// The `State` struct represents each possible state of a tile in the WFC algorithm.
pub(crate) struct State {
/// Position of the tile
pos: Pos,
/// Possible tiles for this state
possible_tiles: Vec<Tile>,
/// Entropy of the state
entropy: f32,
}
impl State {
/// Creates a new State instance
pub fn new(pos: Pos, possible_tiles: Vec<Tile>) -> Self {
let entropy = 0.0;
Self {
pos,
possible_tiles,
entropy,
}
}
/// Updates the possible tiles and recalculates entropy
pub fn update_possible_tiles(&mut self, possible_tiles: Vec<Tile>) {
self.possible_tiles = possible_tiles;
self.entropy = self.entropy();
}
/// Calculates the entropy of the state
/// TODO: Implement shannon entropy calculation
pub fn entropy(&self) -> f32 {
self.possible_tiles.len() as f32
}
}
/// The `Wfc` struct encapsulates the Wave Function Collapse algorithm.
pub struct Wfc {
/// The seed used for randomness in the algorithm
seed: u64,
/// The size of the map to generate
mapsize: u16,
/// The current state of the WFC algorithm (smart pointer for interior mutability)
states: Vec<std::cell::RefCell<State>>,
/// The random number generator
rng: rand::rngs::StdRng,
}
impl Wfc {
/// Creates a new Wfc instance with the given seed and map size
pub fn new(seed: u64, mapsize: u16) -> Self {
let rng = rand::SeedableRng::seed_from_u64(seed);
Self {
seed,
mapsize,
states: Vec::with_capacity(mapsize as usize),
rng,
}
}
/// Initializes the states vector with default states
pub fn initialize_states(&mut self) {
for pos in Pos::values() {
let possible_tiles = Tile::all_tiles();
let state = State::new(pos, possible_tiles);
self.states.push(std::cell::RefCell::new(state));
}
}
/// Runs the Wave Function Collapse algorithm to generate the map
pub fn run(&mut self) {
// ----- Step 1: Read in input sample and define constraints -----
// TODO: add support for sample image input
// ----- Step 2: Initialize the grid of possible states -----
// Start with an empty box of tiles
// Store a superposition of all possible tiles for each position
// ----- Step 3: Collapse the superpositions -----
// Calculate the shannon entropy of all superpositions
// Collapse the tile with the lowest entropy
// (Assign a seeded random superposition)
// ----- Step 4: Propogate -----
// Update neighboring superpositions based on the collapsed tile
// (Remove any that violate constraints)
// ----- Step 5: Repeat until all superpositions are collapsed -----
// If any tiles are left with no possible states, restart
// TODO: backtrack
}
}
|
