Irregular Shaped Rooms / Caves

Irregular shaped room
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

rooms1

  • 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;
}

Gallery