Started implementing wfc crate into map

3 files changed, 119 insertions, 1 deletions

diff --git a/dungeon/src/lib.rs b/dungeon/src/lib.rs
index b65ebed..75400e9 100644
--- a/dungeon/src/lib.rs
+++ b/dungeon/src/lib.rs
@@ -4,6 +4,7 @@
 mod entity;
 mod map;
 mod pos;
+mod wfc;
 
 pub use entity::*;
 pub use map::*;
diff --git a/dungeon/src/map.rs b/dungeon/src/map.rs
index f962180..d9a4323 100644
--- a/dungeon/src/map.rs
+++ b/dungeon/src/map.rs
@@ -1,6 +1,7 @@
 //! The `map` module contains structures of the dungeon game map
 //! including the current `Floor`, and map `Tile`.
 
+use crate::wfc::Wfc;
 use crate::{const_pos, pos::Pos};
 
 /// `MAP_SIZE` is the size of the size of the dungeon grid.
@@ -20,6 +21,17 @@ pub enum Tile {
 	Wall,
 	/// `Air` represents empty walkable space
 	Air,
+	/// `Stairs` represents stairs to another floor
+	Stairs,
+}
+
+impl Tile {
+	/// Returns a list of all possible tiles
+	/// TODO! Use a crate for enum itterator
+	#[must_use]
+	pub fn all_tiles() -> Vec<Tile> {
+		vec![Tile::Wall, Tile::Air, Tile::Stairs]
+	}
 }
 
 /// The `Floor` type represents the current playing
@@ -65,7 +77,12 @@ impl Floor {
 	/// let floor = Floor::generate_seeded(seed);
 	/// ```
 	#[must_use]
-	pub fn generate_seeded(_seed: u64) -> Self {
+	pub fn generate_seeded(seed: u64) -> Self {
+		let mut wfc = Wfc::new(seed, MAP_SIZE);
+		wfc.initialize_states();
+		wfc.run();
+
+		// TODO
 		unimplemented!()
 	}
 
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
+	}
+}