1 files changed, 209 insertions, 2 deletions
diff --git a/html/broughlike/index.html b/html/broughlike/index.html
index 03e0015..2a768f5 100644
--- a/html/broughlike/index.html
+++ b/html/broughlike/index.html
@@ -153,7 +153,7 @@
             }
         }
 
-        function generateWalls() {
+        function generateWallsNaive() {
             walls = [];
             let numWalls = Math.floor(Math.random() * (WALLS_MAX - WALLS_MIN + 1)) + WALLS_MIN;
             while (walls.length < numWalls) {
@@ -173,8 +173,215 @@
             }
 
             if (!isPassable()) {
-                generateWalls();
+                generateWallsNaive();
+            }
+        }
+
+        function generateWallsDrunkardsWalk() {
+            walls = [];
+            const numWalls = Math.floor(Math.random() * (WALLS_MAX - WALLS_MIN + 1)) + WALLS_MIN;
+            let wallX = Math.floor(Math.random() * GRID_SIZE);
+            let wallY = Math.floor(Math.random() * GRID_SIZE);
+
+            while (walls.length < numWalls) {
+            if (
+                (wallX !== player.x || wallY !== player.y) &&                     // Check that a wall is not placed on the starting position
+                (wallX !== exit.x || wallY !== exit.y) &&                         // Check that a wall is not placed on the exit
+                !enemies.some(enemy => enemy.x === wallX && enemy.y === wallY) && // Check that a wall is not placed on any enemies
+                !items.some(item => item.x === wallX && item.y === wallY) &&      // Check that a wall is not placed on any items
+                !walls.some(wall => wall.x === wallX && wall.y === wallY)         // Check that a wall is not placed on an existing wall
+            ) {
+                walls.push({ x: wallX, y: wallY });
+            }
+
+            // Randomly move to a neighboring cell
+            const direction = Math.floor(Math.random() * 4);
+            switch (direction) {
+                case 0: wallX = Math.max(0, wallX - 1); break;             // Move left
+                case 1: wallX = Math.min(GRID_SIZE - 1, wallX + 1); break; // Move right
+                case 2: wallY = Math.max(0, wallY - 1); break;             // Move up
+                case 3: wallY = Math.min(GRID_SIZE - 1, wallY + 1); break; // Move down
+            }
+            }
+
+            if (!isPassable()) {
+                generateWallsDrunkardsWalk();
+            }
+        }
+
+        function generateWallsCellularAutomata() {
+            walls = [];
+            const map = Array(GRID_SIZE).fill().map(() => Array(GRID_SIZE).fill(0));
+
+            // Initialize a map with random walls
+            for (let x = 0; x < GRID_SIZE; x++) {
+                for (let y = 0; y < GRID_SIZE; y++) {
+                    if (Math.random() < 0.4) {
+                    map[x][y] = 1;
+                    }
+                }
+            }
+
+            for (let i = 0; i < 4; i++) {
+                // Create a new map to store the next state of the cellular automata
+                const newMap = Array(GRID_SIZE).fill().map(() => Array(GRID_SIZE).fill(0));
+
+                // Iterate over each cell in the grid
+                for (let x = 0; x < GRID_SIZE; x++) {
+                    for (let y = 0; y < GRID_SIZE; y++) {
+                        // Count the number of neighboring walls
+                        const neighbors = countNeighbors(map, x, y);
+
+                        if (map[x][y] === 1) {
+                            // If the cell is a wall, it stays a wall if it has 4 or more neighbors
+                            newMap[x][y] = neighbors >= 4 ? 1 : 0;
+                        } else {
+                            // If the cell is empty, it turn into a wall if it has 5 or more neighbors
+                            newMap[x][y] = neighbors >= 5 ? 1 : 0;
+                        }
+                    }
+                }
+
+                // Update the original map with the new state
+                map.forEach((row, x) => row.forEach((cell, y) => map[x][y] = newMap[x][y]));
+            }
+
+            // Convert map to walls array
+            for (let x = 0; x < GRID_SIZE; x++) {
+                for (let y = 0; y < GRID_SIZE; y++) {
+                    if (map[x][y] === 1 && 
+                    (x !== player.x || y !== player.y) && 
+                    (x !== exit.x || y !== exit.y) && 
+                    !enemies.some(enemy => enemy.x === x && enemy.y === y) && 
+                    !items.some(item => item.x === x && item.y === y)) {
+                        walls.push({ x, y });
+                    }
+                }
+            }
+
+            if (!isPassable()) {
+                generateWallsCellularAutomata();
+            }
+        }
+
+        function countNeighbors(map, x, y) {
+            let count = 0;
+            for (let dx = -1; dx <= 1; dx++) {
+                for (let dy = -1; dy <= 1; dy++) {
+                    if (dx === 0 && dy === 0) continue;
+                    const nx = x + dx;
+                    const ny = y + dy;
+                    if (nx >= 0 && nx < GRID_SIZE && ny >= 0 && ny < GRID_SIZE) {
+                        count += map[nx][ny];
+                    } else {
+                        count++; // Consider out-of-bounds bits as walls
+                    }
+                }
             }
+            return count;
+        }
+
+        function generateWallsRSP() {
+            walls = [];
+            const MIN_ROOM_SIZE = 2;
+
+            class Node {
+                constructor(x, y, width, height) {
+                    this.x = x;
+                    this.y = y;
+                    this.width = width;
+                    this.height = height;
+                    this.left = null;
+                    this.right = null;
+                    this.room = null;
+                }
+
+                split() {
+                    if (this.left || this.right) return false;
+
+                    const splitHorizontally = Math.random() > 0.5;
+                    const max = (splitHorizontally ? this.height : this.width) - MIN_ROOM_SIZE;
+
+                    if (max <= MIN_ROOM_SIZE) return false;
+
+                    const split = Math.floor(Math.random() * (max - MIN_ROOM_SIZE)) + MIN_ROOM_SIZE;
+
+                    if (splitHorizontally) {
+                        this.left = new Node(this.x, this.y, this.width, split);
+                        this.right = new Node(this.x, this.y + split, this.width, this.height - split);
+                    } else {
+                        this.left = new Node(this.x, this.y, split, this.height);
+                        this.right = new Node(this.x + split, this.y, this.width - split, this.height);
+                    }
+
+                    return true;
+                }
+
+                createRooms() {
+                    if (this.left || this.right) {
+                        // If the node has children, recursively create rooms in the children
+                        if (this.left) this.left.createRooms();
+                        if (this.right) this.right.createRooms();
+                    } else {
+                        // If the node has no children, create a room within the node
+                        const roomWidth = Math.floor(Math.random() * (this.width - 1)) + 1;            // Random room width
+                        const roomHeight = Math.floor(Math.random() * (this.height - 1)) + 1;          // Random room height
+                        const roomX = this.x + Math.floor(Math.random() * (this.width - roomWidth));   // Random x position inside of node
+                        const roomY = this.y + Math.floor(Math.random() * (this.height - roomHeight)); // Random y position inside of node
+                        this.room = { x: roomX, y: roomY, width: roomWidth, height: roomHeight };      // Assign the room to the node
+                    }
+                }
+            }
+
+            const root = new Node(0, 0, GRID_SIZE, GRID_SIZE);
+            const nodes = [root];
+
+            while (nodes.length) {
+                const node = nodes.pop();
+                if (node.split()) {
+                    nodes.push(node.left, node.right);
+                }
+            }
+
+            root.createRooms();
+
+            function traverse(node) {
+                if (node.room) {
+                    for (let x = node.room.x; x < node.room.x + node.room.width; x++) {
+                        for (let y = node.room.y; y < node.room.y + node.room.height; y++) {
+                            if (
+                                (x !== player.x || y !== player.y) &&
+                                (x !== exit.x || y !== exit.y) &&
+                                !enemies.some(enemy => enemy.x === x && enemy.y === y) &&
+                                !items.some(item => item.x === x && item.y === y)
+                            ) {
+                                walls.push({ x, y });
+                            }
+                        }
+                    }
+                }
+                if (node.left) traverse(node.left);
+                if (node.right) traverse(node.right);
+            }
+
+            traverse(root);
+
+            if (!isPassable()) {
+                generateWallsRSP();
+            }
+        }
+
+        function generateWalls() {
+            const wallGenerators = [
+                { name: 'RSP Tree', func: generateWallsRSP },
+                { name: 'Naive', func: generateWallsNaive },
+                { name: 'Cellular Automata', func: generateWallsCellularAutomata },
+                { name: 'Drunkard\'s Walk', func: generateWallsDrunkardsWalk }
+            ];
+            const randomIndex = Math.floor(Math.random() * wallGenerators.length);
+            const selectedGenerator = wallGenerators[randomIndex];
+            console.log(`Wall generator: ${selectedGenerator.name}`);
+            selectedGenerator.func();
         }
 
         function generateItems() {