# 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;
}```