1 files changed, 100 insertions, 0 deletions
diff --git a/dungeon/src/wfc.rs b/dungeon/src/wfc.rs
new file mode 100644
index 0000000..5968000
--- /dev/null
+++ b/dungeon/src/wfc.rs
@@ -0,0 +1,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
+	}
+}