# Irregular Shaped Rooms / Caves

I was looking at procedural dungeon generation and found a link on how to generate irregular shaped rooms which can be included in dungeon generation. The idea is to reduce the repetition of square rooms and give a more natural look to the dungeon. I decided to implement the algorithm and at the same time decided to look into generating more features for the cave or room structure. In this case I treated the irregular shape as a cave and added stalagmites and stalactites as features.

# Algorithm

- Given the room size, create rectangles at the edges outwards to enclose the area. E.g. one on the top, right, bottom, and left
- In each rectangle generate at least one random point, after which order the points
- Order the points in the top rectangle by their X value, from low to high
- Order the points in the right rectangle by their Y value, from low to high
- Order the points in the bottom rectangle by their X value, for high to low
- Order the points in the left rectangle by their Y value, from high to low

- Drawing from the first point through the points in order, draw a line to the last point and back to the first
- Run a flood fill on the centre point of the room to flesh out the irregular shape

## Features

- Adding additional points in each rectangles produces a more square shaped room
- Increasing the width of the rectangles will increase the variability of the shape edges

### Water

- Starting at the lowest row that contains an empty space
- Iterate upwards through X amount of rows filling all empty spaces with water

Here, X is the width of the rectangles- which helps with visualising the algorithm

### Stalagmites / Stalactites

This is a slight modification of the waterfall algorithm I used in a previous demo. I will describe the stalactite algorithm here, as the stalagmite is the reverse of the algorithm.

- Firstly, choose X amount of random locations which are empty that have a roof block above
- Grow each of those locations downwards for Y steps

X is the amount of random stalactites you want. Y is the length of the stalactite being grown. It is best to have Y normally distributed around point Y or uniformly distributed between a low and high length.

# Code

/** * http://roguebasin.roguelikedevelopment.org/index.php?title=Irregular_Shaped_Rooms * * @param width * @param height * @param edge * @param minPoints * @param maxPoints * @return */ public function makeIrregularSquareRoom(width:int, height:int, edge:int, minPoints:int = 1, maxPoints:int = 4):Vector.<Vector.> { var rectangleTop:Rectangle = new Rectangle(edge, 0, width - 2 * edge, edge); var rectangleRight:Rectangle = new Rectangle(width - edge, edge, edge, height - 2 * edge); var rectangleBottom:Rectangle = new Rectangle(edge, height - edge, width - 2 * edge, edge); var rectangleLeft:Rectangle = new Rectangle(0, edge, edge, height - 2 * edge); var i:int = 0; var drawCoords:Vector. = new Vector.(); drawCoords = drawCoords.concat(randomPointsInRectangle(rectangleTop, randomInteger(minPoints, maxPoints)).sort(function(p1:Point, p2:Point):Number{return p1.x - p2.x;})); drawCoords = drawCoords.concat(randomPointsInRectangle(rectangleRight, randomInteger(minPoints, maxPoints)).sort(function(p1:Point, p2:Point):Number{return p1.y - p2.y;})); drawCoords = drawCoords.concat(randomPointsInRectangle(rectangleBottom, randomInteger(minPoints, maxPoints)).sort(function(p1:Point, p2:Point):Number{return p2.x - p1.x;})); drawCoords = drawCoords.concat(randomPointsInRectangle(rectangleLeft, randomInteger(minPoints, maxPoints)).sort(function(p1:Point, p2:Point):Number{return p2.y - p1.y;})); var bmpData:BitmapData = new BitmapData(width, height, false, 1); var lastPoint:Point = drawCoords[0]; for each (var point:Point in drawCoords) { drawFastLine(bmpData, lastPoint.x, lastPoint.y, point.x, point.y, 0); lastPoint = point; } drawFastLine(bmpData, lastPoint.x, lastPoint.y, drawCoords[0].x, drawCoords[0].y, 0); bmpData.floodFill(width >> 1, height >> 1, 0); var room:Vector.<Vector.> = createIntVectorMatrix(height, width, 0); for (var y:int = 0; y < height; y++) for (var x:int = 0; x < width; x++) room[y][x] = (bmpData.getPixel(x, y)); bmpData.dispose(); return room; } public function addCaveStalactites(map:Vector.<Vector.>, numSpawns:int = 16, low:int = 2, high:int = 10, seed:int = 0):Vector.<Vector.> { var x:int, y:int; var height:int = map.length; var width:int = map[0].length; seed = seed == 0 ? Math.random() * int.MAX_VALUE : seed; var rng:SeededRNG = new SeededRNG(seed); // spawn locations var spawns:Vector. = new Vector.(); while (spawns.length < numSpawns) { x = rng.integer(width); y = rng.integer(height); if (map[y][x] == 0 && y - 1 >= 0 && map[y - 1][x] == 1) spawns.push(new Point(x, y)); } // grow spawns var length:int; while (spawns.length != 0) { var loc:Point = spawns.pop(); length = rng.integer(low, high); for (var i:int = 0; i < length; i++) { if (map[loc.y + i][loc.x] == 0) map[loc.y + i][loc.x] = 3; else break; } } return map; } public function fillCaveWithWater(map:Vector.<Vector.>, depth:int = 15):Vector.<Vector.> { var x:int, y:int; var height:int = map.length; var width:int = map[0].length; var lowestPoint:int; for (y = height - 1; y > 0; y--) for (x = 0; x < width; x++) if (lowestPoint == 0 && map[y][x] == 0) lowestPoint = y; for (y = lowestPoint; y > lowestPoint - depth; y--) for (x = 0; x < width; x++) if (map[y][x] == 0) map[y][x] = 2; return map; }

Pingback: Voronoi Dungeon Generator()