27:null 28:["$","title",null,{"children":"Vector-Based Room and Dungeon Generation | Rick Martin | Observable"}] 2d:T8ee,# Vector-Based Room and Dungeon Generation This is a work in progress. The goal is to assemble rooms from basic shapes, then assemble those rooms into larger dungeons. I have done a lot of work with Tile-based procedural generation, but would like to break away from the grid in some upcoming projects. ## Defining a Dungeon Dungeons will be rendered as a single contiguous shape, made of multiple rooms, connected by doorways and hallways. All walls are represented as line segments. ## Building Rooms Rooms can be assembled from different methods, but they are stored as a generic shape, alongside a collection of exits and spawn locations. - Rooms could be manually created by placing shapes and merging them, or by manually placing points. - Rooms could also be randomly generated from a few preset shapes (rectangles, circles). These shapes could also be merged together. - With some additional tools, rooms could also be generated to fit certain purposes (long halls, meeting rooms, living quarters, boss rooms, etc). ## Building Dungeons Build a list of rooms from any source or combination of sources. - Select and place a "Start" room. - For each exit from the start room, place additional rooms. - Check for collisions with any existing rooms. - Aim to place a certain number of rooms before continuing. - If there are any remaining unpopulated exits, attempt to connect them with generated pathways. This will allow looping paths. - Any remaining exits at this point should be capped. We may need some specialized "Cap Rooms" for this. - Assign an "End" room with some minimum distance from the start. Along with the physical shape of the dungeon, this should result in a data structure representing the network of connected rooms. From this network, we can create puzzles and problems for a player to solve. For instance, Block certain exits with doors, and hide keys in rooms that are accessible from the start room. Based on the dungeon's data, it may also be useful to calculate a difficulty rating. Once these key elements are populated, any remaining spawn locations in the rooms can be populated with decorations, collectibles, and enemies. ## References - [Polygon/Point Collision Detection](http://www.jeffreythompson.org/collision-detection/poly-point.php)2e:T1112,// Rooms are shapes defined by a center point and a set of wall points. // Rooms have 1 or more exits, and some number of spawns. class Room { constructor(shape) { this.position = new Victor(0,0); this.exits = []; this.spawns = []; if (!shape) this.shape = Room.generateRoomShape(); else this.shape = shape; } // TODO Simple rooms, single-exit rooms // TODO hallway style rooms // TODO radial rooms // TODO Caverns // TODO rooms targeting specific shapes. "T", "U", "L", etc // Also, the "Place random rectangles and merge them" method is acutally neat sometimes. /*static axisBasedRoomShape(scale) { let constituents = []; // Define two axes. At least 35 degrees between them, ideally 90. TODO Random. let primaryAxis = new Victor().randomize(new Victor(-1, 1), new Victor(1, -1)).normalize(); let secondaryAxis = primaryAxis.clone().rotateByDeg(90); if (Math.random() > 0.5) { // Optionally, define a focal point. let bounds = scale * 0.75; let focalPoint = new Victor(new Victor(-bounds, bounds), new Victor(bounds, -bounds)); // If there is a focal point, create a square, rectangle, or circle at that point, rotated randomly. } // Generate some number of rectangles, rotating them to match the axes. // If a rectangle matches the second axis, optionally create an array of duplicate rectangles. // Merge all of the shapes together. }*/ // Arbitrary first-stab room generation algorithm. static generateRoomShape() { // Place some random rectangles, then merge them. let rectCount = Math.floor(Math.random() * 4) + 1; let rects = []; for (let i = 0; i < rectCount; i++) { let offset = new Victor(Math.floor(Math.random() * 4) - 1, Math.floor(Math.random() * 4) - 1); let extents = new Victor(Math.floor(Math.random() * 3) + 1, Math.floor(Math.random() * 3) + 1); let rotation = (Math.random() * Math.PI) - (Math.PI / 2); rects.push(Shape.generateRectangle(extents, offset, rotation)); } // Place a random circle as well. rects.push(Shape.generateCircle(2, new Victor(Math.floor(Math.random() * 4) - 1, Math.floor(Math.random() * 4) - 1), 12)); // Start joining the shapes together to create an outline. var shape = rects[0]; for (let i = 1; i < rects.length; i++) { shape = shape.merge(rects[i]); } // Beautify the outline by: // - removing small segments // - removing adjacent segments that have a nearly equal angle // - removing segments that have too acute of an angle between them shape = shape.simplify(0.25); shape = shape.straighten(22, 60); //shape = shape.translate(new Victor(10, 5)); //shape = shape.rotate(180, new Victor(5, 5)); return shape; } // Place up to a specified number of exits on outward facing walls which are large enough. placeExits(count, segmentSizeThreshold=2.0) { let segments = this.shape.getSegments(); // Filter down to only segments that are long enough. let valid = segments.filter((segment) => { return segment[0].distance(segment[1]) > segmentSizeThreshold; }); // TODO try to diversify which direction the doors will face. // Maybe just randomize the valid segments instead of starting at the beginning. for (let i = 0; i < Math.min(valid.length, count); i++) { let segment = valid[i]; // Find the center of the segment. let center = new Victor(segment[0].x + (0.5 * (segment[1].x-segment[0].x)), segment[0].y + (0.5 * (segment[1].y-segment[0].y))); // Cast a ray out from the center of the segment, along its normal. // If the ray doesn't hit anything, we can place a door here. let exit = new Exit(center, 0, 5); this.exits.push(exit); } } draw(sketch, scale=25) { sketch.push(); sketch.translate(this.position.x, this.position.y, 5); sketch.noFill(); this.shape.draw(sketch, scale); for (let i = 0; i < this.exits.length; i++) { this.exits[i].draw(sketch, scale); } for (let i = 0; i < this.spawns.length; i++) { this.spawns[i].draw(sketch, scale); } sketch.pop(); } drawExits(sketch, scale=25) { sketch.push(); sketch.translate(this.position.x, this.position.y, 5); sketch.noFill(); } }2f:T2eb9,class Shape { points = []; // Accepts a list of points going clockwise around the outside of the shape. constructor(points, constituents=false) { this.points = points; if (!constituents) this.constituents = [points]; else this.constituents = constituents; } // Draw the shape in p5. draw(sketch, scale=1) { sketch.push(); sketch.beginShape(); for (let i = 0; i < this.points.length; i++) { sketch.vertex(this.points[i].x * scale, this.points[i].y * scale); } sketch.endShape(sketch.CLOSE); sketch.pop(); } // Debug method to show how the shape was constructed. drawConstituents(sketch, scale=1) { sketch.push(); for (let c = 0; c < this.constituents.length; c++) { sketch.noFill(); sketch.beginShape(); for (let i = 0; i < this.constituents[c].length; i++) { if (!this.constituents[c]) console.log(this.constituents); sketch.vertex(this.constituents[c][i].x * scale, this.constituents[c][i].y * scale); } sketch.endShape(sketch.CLOSE); /*sketch.fill('#000000'); for (let i = 0; i < this.constituents[c].length; i++) { sketch.text(`${i}`, this.constituents[c][i].x * scale, this.constituents[c][i].y * scale); }*/ } sketch.noFill(); sketch.stroke('#ff0000'); sketch.circle(this.points[0].x * scale, this.points[0].y * scale, 10); /*sketch.noStroke(); sketch.fill('#ff0000'); for (let p = 0; p < this.points.length; p++) { sketch.text(`${p}`, this.points[p].x * scale, this.points[p].y * scale + 12); }*/ sketch.pop(); } // Return a new shape merging these two shapes. If the shapes do not overlap, return a clone of this shape. merge(other, accuracy=0.0001) { if (!other instanceof Shape) return new Shape(this.points, this.constituents); // It's critical that we start tracing from the outside of the intersection of the two shapes. let start = this.findOutsidePoint(other); if (start === null) { // The other shape contains this shape. return new Shape(other.points, [...this.constituents, ...other.constituents]); } var currentShape = this; // this or other. var otherShape = other; // opposite of currentShape; var newPoints = []; //Create a line segment from the start vertex to the next vertex on the current shape. var currentSegment = [this.points[start], this.points[(start + 1) % this.points.length]]; var shortCircuit = this.points.length * other.points.length; while (shortCircuit > 0) { shortCircuit -= 1; // If this is the second time we have seen the start point, we have completed the shape, and can break. if (newPoints.indexOf(currentSegment[0]) >= 0) break; // Check for a collision against every segment on the other shape. let collision = Shape.lineShapeCollision(currentSegment[0], currentSegment[1], otherShape.getSegments(), accuracy); if (collision) { // If there is a collision, add the start of the currentSegment to newPoints. newPoints.push(currentSegment[0]); // Our next segment will be from the collision location to the end of the colliding vector. // (We'll actually start slightly offset from the collision location to avoid re-colliding.) currentSegment = [collision.safeOffsetPosition, collision.segment[1]]; // Swap contexts to the other shape. [currentShape, otherShape] = [otherShape, currentShape]; } else { // If no collision is detected, add the start point to newPoints, then repeat from the end point. newPoints.push(currentSegment[0]); let nextEnd = currentShape.points[(currentShape.points.indexOf(currentSegment[1]) + 1) % currentShape.points.length]; currentSegment = [currentSegment[1], nextEnd]; } } if (newPoints.length == this.points.length) { // Other shape may be entirely contained, or completely separate. // There was no change to this shape. } return new Shape(newPoints, [...this.constituents, ...other.constituents]); } clone(onlyPoints=false) { var newPoints = []; for (let i = 0; i < this.points.length; i++) { newPoints.push(this.points[i].clone()); } if (onlyPoints) return newPoints; return new Shape(newPoints, this.constituents); } // Translate the shape by some amount along the X and Y axes. translate(offset=new Victor(0, 0)) { var newPoints = this.clone(true); for (let i = 0; i < newPoints.length; i++) { newPoints[i] = newPoints[i].add(offset); } return new Shape(newPoints, this.constituents); } // Rotate the shape around a given origin point. rotate(degrees, origin=null) { if (origin === null) origin = new Victor(0, 0);//TODO this.centerByMean()? var radians = degrees * 0.0174533; var newPoints = this.clone(true); for (let i = 0; i < newPoints.length; i++) { // Subtract the origin. Rotate the vertex. Add the origin back. let point = newPoints[i]; let cos = Math.cos(radians); let sin = Math.sin(radians); let x = point.x - origin.x; let y = point.y - origin.y; newPoints[i] = new Victor((x * cos - y * sin) + origin.x, (y * cos + x * sin) + origin.y); } return new Shape(newPoints, this.constituents); } // TODO Scale the object around a given origin by some constant. scale(scale=1.0, origin=null) { if (origin === null) origin = new Victor(0, 0);//TODO this.centerByMean()? } // Return the central point of this shape by determining the mean of all vertices. centerByMean() { let sum = new Victor(0, 0); for (let i = 0; i < this.points.length; i++) { sum = sum.add(this.points[i]); } return sum.divide(new Victor(this.points.length, this.points.length)); } // Remove small segments. simplify(threshold=0.25) { // Can't simplify a Triangle. if (this.points.length <= 3) return new Shape(this.points, this.drawConstituents); var newPoints = []; for (let i = 0; i < this.points.length; i++) { newPoints.push(this.points[i].clone()); } for (let i = 0; i < newPoints.length; i++) { let point = newPoints[i]; let nextPoint = newPoints[(i + 1) % newPoints.length]; let pointAfterThat = newPoints[(i + 2) % newPoints.length]; if (point.distance(nextPoint) < threshold && nextPoint.distance(pointAfterThat) < threshold) { // If the next two segments are short, keep the middle point. newPoints.splice(i, 1); newPoints.splice((i + 2) % newPoints.length, 1); } else if (point.distance(nextPoint) < threshold) { // If only the next segment is short, remove the next point. newPoints.splice((i + 1) % newPoints.length, 1); } if (newPoints.length <= 3) break; } return new Shape(newPoints, this.constituents); } // For adjacent segments that create an extremely obtuse or acute angle, delete the middle vertex. straighten(upperThreshold=5.0, lowerThreshold=25.0) { // Can't simplify a Triangle. if (this.points.length <= 3) return new Shape(this.points, this.drawConstituents); var newPoints = []; for (let i = 0; i < this.points.length; i++) { newPoints.push(this.points[i].clone()); } for (let i = 0; i < newPoints.length; i++) { let a = newPoints[i]; let b = newPoints[(i + 1) % newPoints.length]; let c = newPoints[(i + 2) % newPoints.length]; // Calculate the angle made by ba,bc. let ba = a.clone().subtract(b).horizontalAngleDeg() + 180.0; let bc = c.clone().subtract(b).horizontalAngleDeg() + 180.0; let theta = Math.abs(bc - ba); if (upperThreshold && upperThreshold > 0 && theta >= 180 - upperThreshold && theta <= 180 + upperThreshold) { // If the angle is within upperThreshold of 180 degrees, remove b // Then, decrement i to check again from a on the next loop. newPoints.splice((i + 1) % newPoints.length, 1); i--; } else if (lowerThreshold && lowerThreshold > 0 && theta >= -lowerThreshold && theta <= lowerThreshold) { // If the angle is within lowerThreshold of 0 degrees, remove b. newPoints.splice((i + 1) % newPoints.length, 1); i--; } if (newPoints.length <= 3) break; } return new Shape(newPoints, this.constituents); } // Return a list of pairs of adjacent points getSegments() { let segments = []; for (let i = 0; i < this.points.length; i++) { segments.push([ this.points[i], this.points[(i + 1) % this.points.length] ]); } return segments; } // Try to find a point on this shape which is outside of another shape. findOutsidePoint(other) { var segments = other.getSegments(); for (let i = 0; i < this.points.length; i++) { if (!Shape.pointShapeCollision(this.points[i], segments)) return i; } // This shape might contain the other shape. return null; } // Test whether a point is within a shape. Return true or false. static pointShapeCollision(point, segments) { var collision = false; for (let i in segments) { let segment = segments[i]; let verticalCheck = (segment[0].y > point.y) != (segment[1].y > point.y); let jctCheck = point.x < (segment[1].x - segment[0].x) * (point.y - segment[0].y) / (segment[1].y - segment[0].y) + segment[0].x; if (verticalCheck && jctCheck) { collision = !collision; } } return collision; } // Apply lineLineCollision against a bunch of segments and return the closest collision to the start point. static lineShapeCollision(a1, a2, segments, accuracy=0.0001) { var closest = null; for (let i = 0; i < segments.length; i++) { let segment = segments[i]; let collision = Shape.lineLineCollision(a1, a2, segment[0], segment[1], accuracy); if (collision) { if (!closest) closest = collision; else if (a1.distanceSq(collision.position) < a1.distanceSq(closest.position)) closest = collision; } } return closest; } // Check if two lines intersect. If so, return a collision object. If not, return null static lineLineCollision(a1, a2, b1, b2, accuracy=0.0001) { let uA = ((b2.x-b1.x)*(a1.y-b1.y) - (b2.y-b1.y)*(a1.x-b1.x)) / ((b2.y-b1.y)*(a2.x-a1.x) - (b2.x-b1.x)*(a2.y-a1.y)); let uB = ((a2.x-a1.x)*(a1.y-b1.y) - (a2.y-a1.y)*(a1.x-b1.x)) / ((b2.y-b1.y)*(a2.x-a1.x) - (b2.x-b1.x)*(a2.y-a1.y)); // Don't include cases where a point is exactly on the line, otherwise precision works against us. if (uA > 0 && uA < 1 && uB > 0 && uB < 1) { // The lines are colliding. Return the position, since it will be a new point. let uBSafe = Math.min(uB + accuracy,1); return { position: new Victor(a1.x + (uA * (a2.x-a1.x)), a1.y + (uA * (a2.y-a1.y))), safeOffsetPosition: new Victor(b1.x + (uBSafe * (b2.x-b1.x)), b1.y + (uBSafe * (b2.y-b1.y))), direction: 1, // 1 for clockwise, -1 for counter-clockwise? segment: [b1, b2] }; } return null; } static generateRectangle(extents=new Victor(1.0, 1.0), position=new Victor(0.0, 0.0), rotation=0.0) { let points = [ new Victor(extents.x, extents.y).rotate(rotation).add(position), new Victor(-extents.x, extents.y).rotate(rotation).add(position), new Victor(-extents.x, -extents.y).rotate(rotation).add(position), new Victor(extents.x, -extents.y).rotate(rotation).add(position) ]; return new Shape(points); } static generateCircle(radius, position, detail=12) { detail = Math.min(Math.max(3, detail), 36); let theta = 360.0 / detail; let points = []; for (let i = 0; i < detail; i++) { points.push(new Victor(radius, 0).rotateByDeg(theta * i).add(position)); } return new Shape(points); } }30:T494,p5(sketch => { sketch.setup = function() { sketch.createCanvas(width, 250); sketch.a = new Shape([ new Victor(1, 2), new Victor(2, 0), new Victor(1, -1), new Victor(-1, -1), new Victor(-1, 1), ]); sketch.b = new Shape([ new Victor(3, -1), new Victor(1, 0), new Victor(1, 1), new Victor(4, 2) ]); sketch.c = sketch.a.merge(sketch.b); }; sketch.draw = function() { sketch.background("#ffffff"); sketch.noFill(); sketch.fill("#000000"); sketch.noStroke(); sketch.text("Example of merging two shapes.", 25, 25); sketch.translate(100, 100); sketch.noFill(); // Draw the merged shape. sketch.stroke(0, 255, 0); sketch.strokeWeight(5); sketch.c.draw(sketch, 50); // Draw A. sketch.stroke(204, 0, 0); sketch.strokeWeight(2); sketch.a.draw(sketch, 50); // Draw B. sketch.stroke(0, 0, 204); sketch.strokeWeight(2); sketch.b.draw(sketch, 50); sketch.noFill(); sketch.strokeWeight(1); sketch.stroke('#000000'); sketch.translate(300, 0); sketch.c.drawConstituents(sketch, 50); } })31:[] 2b:{"id":"81c0c81c7cac0e65","slug":null,"title":"Vector-Based Room and Dungeon Generation","thumbnail":"a04a956cc64eba352097ada93ea6d5214a41903a33b10025c4af8dd6991c15fe","access_level":"public","create_time":"$D2023-10-18T05:11:48.931Z","update_time":"$D2023-11-26T03:42:45.390Z","view_time":null,"first_public_time":"$D2023-10-18T05:11:48.931Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"3d7535b4ad979a57","login":"martin-pi","name":"Rick Martin","avatar_url":"https://avatars-next.observableusercontent.com/a13d596c4e162d5af1526a474e6cf6db62a235aec2094a699c2329df5200fa0c","tier":"starter_2024"},"version":435,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"09a9ff3d030f86ac","login":"martin-pi","name":"Rick Martin","avatar_url":"https://avatars-next.observableusercontent.com/a13d596c4e162d5af1526a474e6cf6db62a235aec2094a699c2329df5200fa0c","tier":null}],"members":[{"type":"individual","id":"09a9ff3d030f86ac","login":"martin-pi","name":"Rick Martin","avatar_url":"https://avatars-next.observableusercontent.com/a13d596c4e162d5af1526a474e6cf6db62a235aec2094a699c2329df5200fa0c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Vector-Based Room and Dungeon Generation","cells":[{"id":0,"value":"$2d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":21,"value":"p5(sketch => {\n sketch.setup = function() {\n sketch.createCanvas(width, 300);\n sketch.rooms = [];\n for (let i = 0; i < 16; i++) {\n sketch.rooms.push(new Room());\n }\n };\n sketch.draw = function() {\n sketch.background(\"#ffffff\");\n sketch.translate(100, 100);\n for (let i = 0; i < 16; i++) {\n sketch.push();\n sketch.translate(i * 60, 0);\n sketch.rooms[i].draw(sketch, 5);\n sketch.pop();\n }\n\n sketch.translate(0, 100);\n for (let i = 0; i < 16; i++) {\n sketch.push();\n sketch.translate(i * 60, 0);\n sketch.rooms[i].shape.drawConstituents(sketch, 5);\n sketch.pop();\n }\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"$2e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"class Exit {\n constructor(position, direction, width=0.5) {\n this.position = new Victor(0,0);\n this.direction = new Victor(0,0);\n this.width = width;\n }\n\n draw(sketch, scale=1.0) {\n sketch.push();\n sketch.translate(this.position.x * scale, this.position.y * scale);\n sketch.rotate(this.direction);\n sketch.rectMode(sketch.CENTER);\n sketch.rect(0, 0, 0.5 * scale, this.width * scale);\n sketch.line(0, 0, 2 * scale, 0);\n sketch.pop();\n }\n\n static placeOnSegment(segment, align=1) {\n \n }\n\n static get ALIGN_START() { return 0; }\n static get ALIGN_CENTER() { return 1; }\n static get ALIGN_END() { return 2; }\n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"class Spawn {\n constructor() {\n this.position = new Victor(0, 0);\n }\n\n draw(sketch) {\n sketch.circle(this.position.x, this.position.y, 4);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":56,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":405,"value":"p5(sketch => {\n sketch.setup = function() {\n sketch.createCanvas(width, 400);\n sketch.rooms = [];\n for (let i = 0; i < 3; i++) {\n let room = new Room();\n room.placeExits(2);\n sketch.rooms.push(room);\n }\n };\n \n sketch.draw = function() {\n sketch.background(\"#ffffff\");\n sketch.translate(100, 100);\n for (let i = 0; i < this.rooms.length; i++) {\n sketch.push();\n sketch.translate(0, i * 100);\n sketch.rooms[i].shape.drawConstituents(sketch, 5);\n sketch.pop();\n }\n\n sketch.translate(100, 0);\n for (let i = 0; i < this.rooms.length; i++) {\n sketch.push();\n sketch.translate(0, i * 100);\n sketch.rooms[i].draw(sketch, 5);\n sketch.pop();\n }\n }\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"Victor = require('https://bundle.run/victor@1.1.0')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"import {p5} from \"@tmcw/p5\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2c:"$2b:body"