BSP Dungeon Generation

Developer
Laerin
Size
5,326 Kb
Views
6,072
  1. BSP Dungeon Generation Previews
  2. BSP Dungeon Generation HTML Codes
  3. BSP Dungeon Generation CSS Codes
  4. BSP Dungeon Generation JS Codes

How do I make an bsp dungeon generation?

Playing around with Binary Space Partitioning for dungeon generation. Right now is just basic room generation and basic corridors. WARING: Code's kinda a mess right now. UPDATE: Red line shows room connections based on first adjacent match.. What is a bsp dungeon generation? How do you make a bsp dungeon generation? This script and codes were developed by Laerin on 26 December 2022, Monday.

BSP Dungeon Generation Previews
IQ Test

BSP Dungeon Generation - Script Codes HTML Codes

<!DOCTYPE html>
<html >
<head> <meta charset="UTF-8"> <title>BSP Dungeon Generation</title> <link rel="stylesheet" href="css/style.css">
</head>
<body> <script src='https://codepen.io/xgundam05/pen/gbOgGj.js'></script> <script src="js/index.js"></script>
</body>
</html>

BSP Dungeon Generation - Script Codes CSS Codes

body{ background-color: #2e2e2e;
}

BSP Dungeon Generation - Script Codes JS Codes

/* Documentation: class room{ bounds: { x, y, width, height } -- the BSP bounds of the room size: { x, y, width, height } -- the actual size/location of the room created in 'roomPainter' function left: &room right: &room parent: &room depth: int } hallPainter(leftRoom, rightRoom) -- creates the halls between rooms modifies bsp.map[] must take two rooms as input roomPainter(room) -- creates the rooms modifies bsp.map[] must take room as input splitDir(width, height) -- determines direction to split bsp must return 0-1 values > 0.5 split horizontally values <= 0.5 split vertically splitMod(width, height) -- determines modifier to multiply splitChance by may return any value rooms split using rand(0-1), with splits occuring on values less than splitChance * splitMod(room.width, room.height) tiles is an enum for painting the map used by default painters, not necessary for custom painters to use, just handy DGEN.BSP({ width: int, height: int, roomSize: int, minDepth: int, splitChance: float (0-1), seed: int/long, roomPainter: function, hallPainter: function, splitMod: function, splitDir: function, tiles: object enum })
*/
var DGEN = (function(){ /* Dungeon Generation Algorithm(s) * Created By: XGundam05 */ var rand = function(seed){ this.m_w = seed; this.m_z = 987654321; this.mask = 0xffffffff; }; rand.prototype = { next: function(){ this.m_z = (36969 * (this.m_z & 65535) + (this.m_z >> 16)) & this.mask; this.m_w = (18000 * (this.m_w & 65535) + (this.m_w >> 16)) & this.mask; var result = ((this.m_z << 16) + this.m_w) & this.mask; result /= 4294967296; return result + 0.5; } }; var flatLeafBSP = function(tree){ var flat = []; var stack = []; var current = tree; while (stack.length > 0 || current !== undefined){ if (current !== undefined){ stack.push(current); current = current.left; } else { current = stack.pop(); if (current.left === undefined && current.right === undefined) flat.push(current); current = current.right; } } return flat; }; var defaultsBSP = { tiles: { EMPTY: 0, WALL: 1, FLOOR: 2 }, splitMod: function(width, height){ if (width > 2.5 * height || height > 2.5 * width) return 1.7; else return 1.0; }, splitDir: function(width, height){ if (width >= 2.5 * height || height < this.roomSize * 2) return 0.75; else if (height > 2.5 * width || width < this.roomSize * 2) return 0.25; else return this.rand.next(); }, hallPainter: function(left, right){ if (left.bounds.x + left.bounds.width == right.bounds.x){ // ============== // Left/right // ============== if (left.size.y + left.size.height - 3 < right.size.y || right.size.y + right.size.height - 3 < left.size.y){ // ------------ // Z Corridor // ------------ var pointL = left.size.y + 1 + ((this.rand.next() * (left.size.height - 2)) | 0); var pointR = right.size.y + 1 + ((this.rand.next() * (right.size.height - 2)) | 0); var diff = 0, mid = 0; if (left.bounds.height >= right.bounds.height){ diff = (left.bounds.x + left.bounds.width - 1) - (left.size.x + left.size.width); mid = ((this.rand.next() * diff) | 0) + left.size.x + left.size.width - 1; } else { diff = (right.size.x - 1) - (right.bounds.x + 1); mid = ((this.rand.next() * diff) | 0) + right.bounds.x; } var y = 0, x = 0; for (x = left.size.x + left.size.width - 1; x <= mid; x++){ if (this.map[(pointL - 1) * this.width + x] != this.tiles.FLOOR) this.map[(pointL - 1) * this.width + x] = this.tiles.WALL; this.map[pointL * this.width + x] = this.tiles.FLOOR; if (this.map[(pointL + 1) * this.width + x] != this.tiles.FLOOR) this.map[(pointL + 1) * this.width + x] = this.tiles.WALL; } var lMin = Math.min(pointL - 1, pointR - 1); var lMax = Math.max(pointL + 1, pointR + 1); for (y = lMin; y <= lMax; y++){ if (this.map[y * this.width + x - 1] != this.tiles.FLOOR) this.map[y * this.width + x - 1] = this.tiles.WALL; if (y != lMin && y != lMax) this.map[y * this.width + x] = this.tiles.FLOOR; else if (this.map[y * this.width + x] != this.tiles.FLOOR) this.map[y * this.width + x] = this.tiles.WALL; if (this.map[y * this.width + x + 1] != this.tiles.FLOOR) this.map[y * this.width + x + 1] = this.tiles.WALL; } for (x = x; x <= right.size.x; x++){ if (this.map[(pointR - 1) * this.width + x] != this.tiles.FLOOR) this.map[(pointR - 1) * this.width + x] = this.tiles.WALL; this.map[pointR * this.width + x] = this.tiles.FLOOR; if (this.map[(pointR + 1) * this.width + x] != this.tiles.FLOOR) this.map[(pointR + 1) * this.width + x] = this.tiles.WALL; } } else { var t = Math.min(left.size.y + left.size.height, right.size.y + right.size.height); var b = Math.max(left.size.y, right.size.y); var diff = (t - 1) - (b + 1); diff = (this.rand.next() * diff) | 0; var pos = b + diff + 1; var len = right.size.x - (left.size.x + left.size.width - 1); for (var k = 0; k <= len; k++){ var _x = (left.size.x + left.size.width - 1 + k); this.map[(pos - 1) * this.width + _x] = this.tiles.WALL; this.map[pos * this.width + _x] = this.tiles.FLOOR; this.map[(pos + 1) * this.width + _x] = this.tiles.WALL; } } } else { // ============== // Top/Bottom // ============== if (left.size.x + left.size.width - 3 < right.size.x || right.size.x + right.size.width - 3 < left.size.x){ // ------------ // Z Corridor // ------------ var pointL = left.size.x + 1 + ((this.rand.next() * (left.size.width - 2)) | 0); var pointR = right.size.x + 1 + ((this.rand.next() * (right.size.width - 2)) | 0); var diff = 0, mid = 0; if (left.bounds.width >= right.bounds.width){ diff = (left.bounds.y + left.bounds.height) - (left.size.y + left.size.height); mid = ((this.rand.next() * diff) | 0) + left.size.y + left.size.height - 1; } else { diff = (right.size.y - 1) - (right.bounds.y + 1); mid = ((this.rand.next() * diff) | 0) + right.bounds.y; } var y = 0, x = 0; for (y = left.size.y + left.size.height - 1; y <= mid; y++){ if (this.map[y * this.width + pointL - 1] != this.tiles.FLOOR) this.map[y * this.width + pointL - 1] = this.tiles.WALL; this.map[y * this.width + pointL] = this.tiles.FLOOR; if (this.map[y * this.width + pointL + 1] != this.tiles.FLOOR) this.map[y * this.width + pointL + 1] = this.tiles.WALL; } var lMin = Math.min(pointL - 1, pointR - 1); var lMax = Math.max(pointL + 1, pointR + 1); for (x = lMin; x <= lMax; x++){ if (this.map[(y - 1) * this.width + x] != this.tiles.FLOOR) this.map[(y - 1) * this.width + x] = this.tiles.WALL; if (x != lMin && x != lMax) this.map[y * this.width + x] = this.tiles.FLOOR; else if (this.map[y * this.width + x] != this.tiles.FLOOR) this.map[y * this.width + x] = this.tiles.WALL; if (this.map[(y + 1) * this.width + x] != this.tiles.FLOOR) this.map[(y + 1) * this.width + x] = this.tiles.WALL; } for (y = y; y <= right.size.y; y++){ if (this.map[y * this.width + pointR - 1] != this.tiles.FLOOR) this.map[y * this.width + pointR - 1] = this.tiles.WALL; this.map[y * this.width + pointR] = this.tiles.FLOOR; if (this.map[y * this.width + pointR + 1] != this.tiles.FLOOR) this.map[y * this.width + pointR + 1] = this.tiles.WALL; } } else { var r = Math.min(left.size.x + left.size.width, right.size.x + right.size.width); var l = Math.max(left.size.x, right.size.x); var diff = (r - 1) - (l + 1); diff = (this.rand.next() * diff) | 0; var pos = l + diff + 1; var len = right.size.y - (left.size.y + left.size.height - 1); for (var k = 0; k <= len; k++){ var _y = (left.size.y + left.size.height - 1 + k); this.map[_y * this.width + pos - 1] = this.tiles.WALL; this.map[_y * this.width + pos] = this.tiles.FLOOR; this.map[_y * this.width + pos + 1] = this.tiles.WALL; } } } }, roomPainter: function(room){ var w = this.roomSize + (this.rand.next() * (room.bounds.width - this.roomSize - 2)) | 0; var h = this.roomSize + (this.rand.next() * (room.bounds.height - this.roomSize - 2)) | 0; var x = room.bounds.x + 1 + ((room.bounds.width - w - 1) * this.rand.next()) | 0; var y = room.bounds.y + 1 + ((room.bounds.height - h - 1) * this.rand.next()) | 0; for (var _y = y; _y < h + y; _y++){ for (var _x = x; _x < w + x; _x++){ if (_x == x || _x == w + x - 1 || _y == y || _y == h + y - 1) this.map[_y * this.width + _x] = this.tiles.WALL; else this.map[_y * this.width + _x] = this.tiles.FLOOR; } } room.size = { x: x, y: y, width: w, height: h }; } }; var generateBSP = function(bsp){ var stack = []; stack.push({ bounds: { x: 0, y: 0, width: bsp.width, height: bsp.height }, left: undefined, right: undefined, parent: undefined, depth: 0 }); bsp.tree = stack[0]; var split = 0; var dir = 0; var room = undefined; var width = 0; var height = 0; while (stack.length > 0){ room = stack.pop(); if (room.bounds.width < bsp.roomSize * 2 && room.bounds.height < bsp.roomSize * 2) { continue; } split = bsp.splitChance * bsp.splitMod(room.bounds.width, room.bounds.height); if (bsp.rand.next() > split && room.depth >= bsp.minDepth) continue; dir = bsp.splitDir(room.bounds.width, room.bounds.height); if (dir > 0.5){ width = ((bsp.rand.next() * 2 - 1) * (room.bounds.width - bsp.roomSize * 2) * 0.5); width = room.bounds.width * 0.5 + (width | 0); room.left = { bounds: { x: room.bounds.x, y: room.bounds.y, width: width, height: room.bounds.height }, left: undefined, right: undefined, parent: room, depth: room.depth + 1 }; room.right = { bounds: { x: room.bounds.x + width, y: room.bounds.y, width: room.bounds.width - width, height: room.bounds.height }, left: undefined, right: undefined, parent: room, depth: room.depth + 1 }; } else { height = ((bsp.rand.next() * 2 - 1) * (room.bounds.height - this.roomSize * 2) * 0.5); height = room.bounds.height * 0.5 + (height | 0); room.left = { bounds: { x: room.bounds.x, y: room.bounds.y, width: room.bounds.width, height: height }, left: undefined, right: undefined, parent: room, depth: room.depth + 1 }; room.right = { bounds: { x: room.bounds.x, y: room.bounds.y + height, width: room.bounds.width, height: room.bounds.height - height }, left: undefined, right: undefined, parent: room, depth: room.depth + 1 }; } stack.push(room.left); stack.push(room.right); } }; var paintBSP = function(bsp){ var i = 0; for (i = 0; i < bsp.width * bsp.height; i++) bsp.map[i] = bsp.tiles.EMPTY; var rooms = flatLeafBSP(bsp.tree); for (i = 0; i < rooms.length; i++){ var room = rooms[i]; bsp.roomPainter(room); if (room.size === undefined) room.size = { x: room.bounds.x, y: room.bounds.y, width: room.bounds.width, height: room.bounds.height }; } for (i = 0; i < bsp.connections.length; i++){ var hall = bsp.connections[i]; bsp.hallPainter(hall.left, hall.right); } }; var adjacentBSP = function(left, right){ var flatL = flatLeafBSP(left); var flatR = flatLeafBSP(right); var found = false; for (var i = 0; i < flatL.length; i++){ if (found) break; var L = flatL[i]; for (var j = 0; j < flatR.length; j++){ if (found) break; var R = flatR[j]; if (L.bounds.x + L.bounds.width == R.bounds.x && ((L.bounds.y <= R.bounds.y + R.bounds.height && L.bounds.y >= R.bounds.y) || (R.bounds.y <= L.bounds.y + L.bounds.height && R.bounds.y >= L.bounds.y))) { found = true; } else if (L.bounds.y + L.bounds.height == R.bounds.y && ((L.bounds.x <= R.bounds.x + R.bounds.width && L.bounds.x >= R.bounds.x) || (R.bounds.x <= L.bounds.x + L.bounds.width && R.bounds.x >= L.bounds.x))) { found = true; } if (found){ return { left: L, right: R }; } } } return undefined; }; var connectBSP = function(bsp){ var stack = []; if (bsp.connections === undefined) bsp.connections = []; stack.push(bsp.tree); while (stack.length > 0){ var room = stack.pop(); if (room === undefined) continue; stack.push(room.left); stack.push(room.right); var edge = adjacentBSP(room.left, room.right); if (edge !== undefined) bsp.connections.push(edge); } }; var BSP = function(options){ var obj = { width: 100, height: 100, roomSize: 4, minDepth: 4, splitChance: 0.35, seed: Date.now(), roomPainter: undefined, hallPainter: undefined, splitMod: undefined, splitDir: undefined, tiles: undefined }; for (var prop in defaultsBSP){ if (obj.hasOwnProperty(prop) && obj[prop] === undefined) obj[prop] = defaultsBSP[prop]; } for (var prop in options){ if (obj.hasOwnProperty(prop)) obj[prop] = options[prop]; } obj.map = []; obj.connections = []; obj.tree = undefined; obj.graph = undefined; obj.rand = new rand(obj.seed); generateBSP(obj); connectBSP(obj); paintBSP(obj); return { width: obj.width, height: obj.height, map: obj.map, tree: obj.tree, connections: obj.connections, mapDef: obj.tiles } }; return { BSP: BSP };
}());
// Testing BSP Generation
// =============================
var bsp = DGEN.BSP({ width: window.innerWidth, height: window.innerHeight, roomSize: 10, seed: Date.now()
});
var canvas = document.createElement('canvas');
canvas.width = bsp.width;
canvas.height = bsp.height;
ctx = canvas.getContext('2d');
ctx.strokeStyle = '0x888888';
for (var i = 0; i < bsp.connections.length; i++){ var item = bsp.connections[i]; ctx.strokeRect(item.left.bounds.x, item.left.bounds.y, item.left.bounds.width, item.left.bounds.height); ctx.strokeRect(item.right.bounds.x, item.right.bounds.y, item.right.bounds.width, item.right.bounds.height);
}
for (var y = 0; y < bsp.height; y++){ for (var x = 0; x < bsp.width; x++){ var id = bsp.map[y * bsp.width + x]; if (id == 0 || id === undefined) continue; if (id == bsp.mapDef.WALL) ctx.fillStyle = 'cyan'; else if (id == bsp.mapDef.FLOOR) ctx.fillStyle = 'black'; ctx.fillRect(x, y, 1, 1); }
}
ctx.strokeStyle = 'red';
ctx.beginPath();
for (var i = 0; i < bsp.connections.length; i++){ var item = bsp.connections[i]; ctx.moveTo(item.left.size.x + (item.left.size.width * 0.5), item.left.size.y + (item.left.size.height * 0.5)); ctx.lineTo(item.right.size.x + (item.right.size.width * 0.5), item.right.size.y + (item.right.size.height * 0.5));
}
ctx.stroke();
canvas.style.position = 'absolute';
canvas.style.top = '0';
canvas.style.left = '0';
document.body.appendChild(canvas);
BSP Dungeon Generation - Script Codes
BSP Dungeon Generation - Script Codes
Home Page Home
Developer Laerin
Username xgundam05
Uploaded December 26, 2022
Rating 4
Size 5,326 Kb
Views 6,072
Do you need developer help for BSP Dungeon Generation?

Find the perfect freelance services for your business! Fiverr's mission is to change how the world works together. Fiverr connects businesses with freelancers offering digital services in 500+ categories. Find Developer!

Laerin (xgundam05) Script Codes
Name
Simple Raycast Engine
Slalom Prototype
CSS Discrete Progress Bar
Image to ASCII converter
Matrix Effect
Threaded Voxel-based Terrain example
Perlin Terrain
SVG BSP Generator
Stat Polygon using JS and SVG
CSS Hex Menu Idea
Create amazing SEO content with AI!

Jasper is the AI Content Generator that helps you and your team break through creative blocks to create amazing, original content 10X faster. Discover all the ways the Jasper AI Content Platform can help streamline your creative workflows. Start For Free!