Voronoi Dungeon Generator

Voronoi Dungeon Generation

Continuing from the previous post on irregular shaped room generation. The idea is to make use of multiple rooms to create a dungeon. A room’s connectedness is determined by calculating a minimum spanning tree on a delaunay triangulation using a voronoi diagram from the as3-delaunay library. This ensures that all rooms are reachable given any starting room. The original idea for generating the dungeon came from Noel Berry’s post on the subject. The algorithm can be modified to select a predefined room from a pool; to generate an irregular shaped room; to use a straight rectangular room or a combination of the three. The method shown here is modular enough to cater for this.

Algorithm

  • Create a blank map given dimensions (width, height)
  • While there is space, place a room in the map
    • A room is generated using the irregular shaped room algorithm
    • The location for placing the room is randomly selected
    • There is space if there are no open spaces in the area to be affected
    • There is no more space when placement has failed to place a random room 100 times
  • Remember to keep track of all center points for placed rooms
  • Use the center points of the rooms to construct a voronoi diagram
  • Use the delaunay triangulation (voronoi) to construct a minimum spanning tree
  • Draw the minimum spanning tree onto the map
    • In this case 5 lines are drawn for each line segment of the minimum spanning tree
    • The 5 lines are used to widen the passageway
    • Using a drawLine() method with a thickness setting would be ideal
    • Here the extremely fast line algorithm is used to draw the lines (no wideness setting)
  • Drawing the lines this way leaves dots in the passageway, therefore a simple 1-pass cellula-automata is used to remove points that have fewer than 5 adjacent walls

Code

public function makeDungeon(width:int = 200, height:int = 150, minRoomWidth:int = 13, maxRoomWidth:int = 20, minRoomHeight:int = 10, maxRoomHeight:int = 15, roomEdge:int = 2, seed:int = 0):Vector.<Vector.>
{
	seed = seed == 0 ? Math.random() * int.MAX_VALUE : seed;
	height = height == 0 ? width : height;
	var rng:SeededRNG = new SeededRNG(seed);

	var centers:Vector. = new Vector.();
	var colors:Vector. = new Vector.();
	var map:Vector.<Vector.> = createIntVectorMatrix(height, width, 1);
	var isSpace:Boolean = true;
	while (isSpace)
	{
		var roomData:Vector.<Vector.> = makeIrregularSquareRoom(rng.integer(minRoomWidth, maxRoomWidth), rng.integer(minRoomHeight, maxRoomHeight), roomEdge, 2, 5);
		var roomWidth:int = roomData[0].length;
		var roomHeight:int = roomData.length;
		var pointInMap:Point = new Point();
		var fits:Boolean = false;
		var x:int, y:int;
		var iteration:int = 0;
		while (!fits && isSpace)
		{
			fits = true;
			pointInMap.x = rng.integer(1, width - (roomWidth + 2 * roomEdge) - 1);
			pointInMap.y = rng.integer(1, height - (roomHeight + 2 * roomEdge) - 1);
			for (x = 0; x < roomWidth && fits; x++)
				for (y = 0; y < roomHeight && fits; y++) 					if (map[pointInMap.y + y][pointInMap.x + x] == 0) 						fits = false; 			 			iteration++; 			if (iteration > 100)
				isSpace = false;
		}

		if (fits)
		{
			for (x = 0; x < roomWidth && fits; x++)
				for (y = 0; y < roomHeight && fits; y++) 					map[pointInMap.y + y][pointInMap.x + x] = roomData[y][x]; 			 			centers.push(new Point(pointInMap.x + (roomWidth >> 1), pointInMap.y + (roomHeight >> 1)));
			colors.push(0);
		}
	}

	var plotBounds:Rectangle = new Rectangle(0, 0, width, height);
	var voronoi:Voronoi = new Voronoi(centers, colors, plotBounds);
	var shortestPath:Vector. = voronoi.spanningTree();
	for each (var line:LineSegment in shortestPath)
	{
		drawFastLineVectorInts(map, line.p0.x, line.p0.y, line.p1.x, line.p1.y, 0);
		drawFastLineVectorInts(map, line.p0.x + 1, line.p0.y + 1, line.p1.x + 1, line.p1.y + 1, 0);
		drawFastLineVectorInts(map, line.p0.x - 1, line.p0.y + 1, line.p1.x - 1, line.p1.y + 1, 0);
		drawFastLineVectorInts(map, line.p0.x + 1, line.p0.y - 1, line.p1.x + 1, line.p1.y - 1, 0);
		drawFastLineVectorInts(map, line.p0.x - 1, line.p0.y - 1, line.p1.x - 1, line.p1.y - 1, 0);
	}

	widenSpaces(map, 1);

	return map;
}

public function widenSpaces(map:Vector.<Vector.>, smoothness:int):void
{
	var i:int, x:int, y:int;
	var height:int = map.length;
	var width:int = map[0].length;

	var mapBuffer:Vector.<Vector.>;
	var oneStepWallCount:int;

	var isBorder:Boolean;
	var lessThan4Walls:Boolean;

	for (i = 0; i < smoothness; i++)
	{
		mapBuffer = createIntVectorMatrix(height, width, 0);
		for (y = 0; y < height; y++)
		{
			for (x = 0; x < width; x++)
			{
				oneStepWallCount = calcNumWallsNStepsFromPoint(map, x, y, 1);

				isBorder = x == 0 || y == 0 || x == width - 1 || y == height - 1;
				lessThan4Walls = oneStepWallCount < 5;

				if (isBorder) {
					mapBuffer[y][x] = 1;
				} else if (lessThan4Walls) {
					mapBuffer[y][x] = 0;
				} else {
					mapBuffer[y][x] = map[y][x];
				}
			}
		}
		copyIntVectorMatrixInto(mapBuffer, map);
	}
}

Gallery

Examples of generated dungeons using this technique (e.g. the method described above)

  • Pingback: Flash | Pearltrees()

  • Felipe Pimentel

    Amazing article!
    Maybe I’m stupid, but I didnt get a thing: Why do you create a Voronoi Diagram? o.O
    I only read the article but seemed to me that all you need is the delaunay triangulation to get a MST… right?

    Anyway, thank you for the article. It helped me alot!

  • http://www.avanderw.co.za/ Andrew van der Westhuizen

    Hey Felipe

    You are quiet right, you do not need to have a Voronoi to get the MST. In fact the Voronoi will not visit the actual sites. I think it is just confusion in the library that I use. It is a Voronoi library that constructs the Voronoi from a Delaunay Triangulation and has an additional method in it called .spanningTree().

    This is what I used to get the spanning tree.

    var voronoi:Voronoi = new Voronoi(centers, colors, plotBounds);
    var shortestPath:Vector = voronoi.spanningTree();

    I have not gone into it in detail, but my assumption is that the Voronoi is not computed unless that specific method is called. One thing I have noted with the .spanningTree() method however, is that it returns duplicates (lines that are the same).

    Never really thought of the MST using the Triangulation until you mentioned it. Thanks for the thought!