Instantly share code, notes, and snippets.

Embed
What would you like to do?
2d Dungeon Layout Generator
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;
// NOTE: Some of the classes here (namely the primitives like Vector2d and Rect2d) are not provided,
// but most should be fairly easy to implement yourself or replace with similar
// classes from other libraries.
// The exception is the Delaunay triangulation - that takes quite a bit more effort to implement. That said,
// there are a number of resources that are out there (both libraries and sample implementations) to implement
// it. This code is meant as a guideline on how this method of dungeon generation works - not a complete
// implementation.
namespace DungeonGenerator
{
public enum RegionType
{
None,
Default,
Main,
Hallway
}
public enum RegionTag
{
None,
Spawn,
Exit
}
public class Region
{
public int RegionId { get; set; }
public RegionType RegionType { get; set; }
public RegionTag RegionTag { get; set; }
public Rect2d Rect { get; set; }
}
// #TODO: Some sort of data structure to store and query regions efficiently
public class DungeonLayout
{
public List<Region> Regions { get; set; } = new List<Region>();
public List<Edge2d> Graph { get; set; } = new List<Edge2d>();
public bool HasRegionAtPoint(Vector2d position)
{
foreach (var region in this.Regions)
{
if (region.Rect.Contains(position))
return true;
}
return false;
}
public bool GetRegionAtPoint(Vector2d position, out Region outRegion)
{
foreach (var region in this.Regions)
{
if (region.Rect.Contains(position))
{
outRegion = region;
return true;
}
}
outRegion = null;
return false;
}
}
public struct LayoutParameters
{
public static readonly LayoutParameters Defaults = new LayoutParameters()
{
MinRegionSize = new Vector2d(2, 2),
MaxRegionSize = new Vector2d(20, 20),
RegionCount = 100,
GenerationRadius = 20,
MainRegionThresholdMultiplier = 1.25,
AdditionalEdgePercent = 0.08,
HallwayRadius = 1
};
public Vector2d MinRegionSize { get; set; }
public Vector2d MaxRegionSize { get; set; }
public int RegionCount { get; set; }
public int GenerationRadius { get; set; }
// This is multiplied by the average room size to get the main room selection threshold
public double MainRegionThresholdMultiplier { get; set; }
// Percent (between 0 and 1) of edges that are added back into the graph after the MST stage
public double AdditionalEdgePercent { get; set; }
public int HallwayRadius { get; set; }
}
public class Generator
{
public LayoutParameters Parameters { get; set; } = LayoutParameters.Defaults;
public async Task<Level> GenerateLevel(Random random)
{
Debug.Assert(Parameters.MinRegionSize.X > 0 && Parameters.MaxRegionSize.Y > 0);
Debug.Assert(Parameters.MaxRegionSize.X >= Parameters.MinRegionSize.X && Parameters.MaxRegionSize.Y >= Parameters.MinRegionSize.Y);
Debug.Assert(Parameters.GenerationRadius > 0);
Debug.Assert(Parameters.RegionCount > 0);
Debug.Assert(Parameters.AdditionalEdgePercent >= 0.0 && Parameters.AdditionalEdgePercent <= 1.0);
DungeonLayout layout = null;
await Task.Run(() =>
{
layout = GenerateLayout(random);
if (layout == null)
return;
if (!SelectSpecialRegions(random, layout))
return;
});
return level;
}
protected bool SelectSpecialRegions(Random random, DungeonLayout layout)
{
var availableMainRegions = new List<Region>();
foreach (var region in layout.Regions)
{
if (region.RegionType == RegionType.Main && region.RegionTag == RegionTag.None)
availableMainRegions.Add(region);
}
if (availableMainRegions.Count < 2)
{
Console.WriteLine("No untagged main regions found, cannot select spawn and exit regions");
return false;
}
// select spawn region
var index = random.Next(availableMainRegions.Count);
var spawnRegion = availableMainRegions[index];
availableMainRegions.RemoveAt(index);
spawnRegion.RegionTag = RegionTag.Spawn;
// select exit region
double maxDistance = 0;
index = -1;
for (var i = 0; i < availableMainRegions.Count; ++i)
{
var region = availableMainRegions[i];
double distance = spawnRegion.Rect.Center.Distance(region.Rect.Center);
if (distance > maxDistance)
{
maxDistance = distance;
index = i;
}
}
if (index < 0)
{
return false;
}
var exitRegion = availableMainRegions[index];
availableMainRegions.RemoveAt(index);
exitRegion.RegionTag = RegionTag.Exit;
return true;
}
protected DungeonLayout GenerateLayout(Random random)
{
var result = new DungeonLayout();
// STEP: Creation
// Generate the base set of regions.
for (var i = 0; i < this.Parameters.RegionCount; ++i)
{
var region = new Region();
region.RegionType = RegionType.Default;
region.RegionId = i;
Vector2d center = this.GenerateRandomCenter(random);
Vector2d size = this.GenerateRandomSize(random);
region.Rect = new Rect2d(center - (size / 2), size);
result.Regions.Add(region);
}
// STEP: Separation
// Separate regions so that they aren't overlapping but are still close together
bool regionsOk = false;
int separationTicks = 0;
while (!regionsOk && separationTicks < 2 * Parameters.RegionCount)
{
regionsOk = true;
foreach (var region in result.Regions)
{
if (region.RegionType != RegionType.Default)
continue;
var movement = Vector2d.Zero;
int separationCount = 0;
foreach (var other in result.Regions)
{
if (region == other)
continue;
if (!region.Rect.Intersects(other.Rect))
continue;
movement += other.Rect.Center - region.Rect.Center;
++separationCount;
}
if (separationCount > 0)
{
movement *= -1;
movement = movement.GetNormalized(true);
var newRect = region.Rect;
newRect.Min += movement;
if (!newRect.Equals(region.Rect))
{
region.Rect = newRect;
regionsOk = false;
}
}
}
++separationTicks;
}
if (!regionsOk)
{
Console.WriteLine("Hit maximum separation ticks, some regions may be overlapping");
}
// STEP: Main region selection
// Select regions above a certain size threshold and select them as being "main" regions
double mainThresholdX = 0;
double mainThresholdY = 0;
foreach (var region in result.Regions)
{
mainThresholdX += region.Rect.Width;
mainThresholdY += region.Rect.Height;
}
mainThresholdX /= result.Regions.Count;
mainThresholdY /= result.Regions.Count;
mainThresholdX *= Parameters.MainRegionThresholdMultiplier;
mainThresholdY *= Parameters.MainRegionThresholdMultiplier;
int mainRegionCount = 0;
foreach (var region in result.Regions)
{
var size = region.Rect.Size;
if (size.X > mainThresholdX && size.Y > mainThresholdY)
{
region.RegionType = RegionType.Main;
++mainRegionCount;
}
}
if (mainRegionCount <= 2)
{
return null;
}
// STEP: Triangulation
// Get the Delaunay triangulation of the main rooms
List<Vector2d> graphVertices = new List<Vector2d>();
foreach (var region in result.Regions)
{
if (region.RegionType == RegionType.Main)
graphVertices.Add(region.Rect.Center);
}
var triangulation = GraphUtilities.DelaunayTriangulation(graphVertices);
if (triangulation.Edges.Count < 1)
{
Console.WriteLine($"Only {triangulation.Edges.Count} created from triangulation, generation cannot continue");
return null;
}
result.Graph = triangulation.Edges;
result.Graph.Sort((a, b) =>
{
return (int)Math.Round(a.Length - b.Length);
});
// STEP: Minimum spanning tree
// Generate a minimum spanning tree from the triangulation graph
List<Edge2d> mst = new List<Edge2d>();
List<Vector2d> mstVerticies = new List<Vector2d>();
mstVerticies.Add(graphVertices[0]);
while (mstVerticies.Count != graphVertices.Count)
{
foreach (var vertex in graphVertices)
{
if (mstVerticies.Contains(vertex))
continue;
Edge2d shortestEdge = new Edge2d();
double shortestDist = double.PositiveInfinity;
foreach (var edge in result.Graph)
{
if (mst.Contains(edge))
continue;
if ((edge.A.Equals(vertex) && mstVerticies.Contains(edge.B)) || (edge.B.Equals(vertex) && mstVerticies.Contains(edge.A)))
{
double dist = edge.Length;
if (dist < shortestDist)
{
shortestDist = dist;
shortestEdge = edge;
}
}
}
if (double.IsInfinity(shortestDist))
continue;
mst.Add(shortestEdge);
mstVerticies.Add(vertex);
}
}
result.Graph = mst;
// STEP: Edge Addition
// Add edges back into the graph to create more interesting paths
var allowedEdges = new List<Edge2d>();
foreach (var edge in triangulation.Edges)
{
if (!mst.Contains(edge) && !allowedEdges.Contains(edge))
allowedEdges.Add(edge);
}
int additionalEdgeCount = (int)Math.Round(allowedEdges.Count * Parameters.AdditionalEdgePercent);
for (var i = 0; i < additionalEdgeCount; ++i)
{
int index = random.Next(allowedEdges.Count);
result.Graph.Add(allowedEdges[index]);
allowedEdges.RemoveAt(index);
}
// STEP: Remove default regions
// Remove all regions that are unused at the moment. These may be added back later.
foreach (var region in result.Regions)
{
if (region.RegionType == RegionType.Default)
region.RegionType = RegionType.None;
}
// STEP: Hallway Graph
// Generate a set of edges to define the paths for hallways. These edges are based on the layout graph.
var hallwayGraph = new List<Edge2d>();
foreach (var edge in result.Graph)
{
Region a = null;
Region b = null;
foreach (var region in result.Regions)
{
if (region.RegionType != RegionType.Main)
continue;
if (a == null && region.Rect.Contains(edge.A))
{
a = region;
}
else if (b == null && region.Rect.Contains(edge.B))
{
b = region;
}
if (a != null && b != null)
{
break;
}
}
if (a == null || b == null)
{
Console.WriteLine($"Unable to find all main regions for edge {edge.A} <-> {edge.B}, skipping edge");
continue;
}
Vector2d aCenter = a.Rect.Center;
Vector2d bCenter = b.Rect.Center;
Vector2d midpoint = (aCenter + bCenter) / 2;
bool useX = false;
if (midpoint.X >= a.Rect.Min.X && midpoint.X <= a.Rect.Max.X &&
midpoint.X >= b.Rect.Min.X && midpoint.X <= b.Rect.Max.X)
{
useX = true;
}
bool useY = false;
if (midpoint.Y >= a.Rect.Min.Y && midpoint.Y <= a.Rect.Max.Y &&
midpoint.Y >= b.Rect.Min.Y && midpoint.Y <= b.Rect.Max.Y)
{
useY = true;
}
if (useX && useY)
{
if (random.NextBool())
{
useX = false;
}
else
{
useY = false;
}
}
if (useX)
{
// Hallway goes up/down
hallwayGraph.Add(
new Edge2d(
new Vector2d(midpoint.X, aCenter.Y),
new Vector2d(midpoint.X, bCenter.Y)
));
}
else if (useY)
{
// Hallway goes left/right
hallwayGraph.Add(
new Edge2d(
new Vector2d(aCenter.X, midpoint.Y),
new Vector2d(bCenter.X, midpoint.Y)
));
}
else
{
// Hallway has a corner
hallwayGraph.Add(
new Edge2d(
new Vector2d(aCenter.X, aCenter.Y),
new Vector2d(aCenter.X, bCenter.Y)
));
hallwayGraph.Add(
new Edge2d(
new Vector2d(aCenter.X, bCenter.Y),
new Vector2d(bCenter.X, bCenter.Y)
));
}
}
result.Graph = hallwayGraph;
// STEP: Hallway selection
// Select existing regions to become hallways
int hallwayRegionCount = 0;
foreach (var edge in result.Graph)
{
foreach (var region in result.Regions)
{
if (region.RegionType != RegionType.None)
continue;
if (region.Rect.Intersects(edge))
{
region.RegionType = RegionType.Hallway;
++hallwayRegionCount;
}
}
}
// STEP: Hallway Fill
// Fill in empty space for hallways
int additionalHallwayCount = 0;
foreach (var edge in result.Graph)
{
// from http://playtechs.blogspot.ca/2007/03/raytracing-on-grid.html
int x1 = edge.A.X;
int y1 = edge.A.Y;
int x2 = edge.B.X;
int y2 = edge.B.Y;
int dx = Math.Abs(x2 - x1);
int dy = Math.Abs(y2 - y1);
int x = x1;
int y = y1;
int n = 1 + dx + dy;
int xInc = x2 > x1 ? 1 : -1;
int yInc = y2 > y1 ? 1 : -1;
int error = dx - dy;
dx *= 2;
dy *= 2;
var direction = dx > dy ? new Vector2d(1, 0) : new Vector2d(0, 1);
var opposite = dx > dy ? new Vector2d(0, 1) : new Vector2d(1, 0);
for (; n > 0; n -= 1)
{
for (int i = -Parameters.HallwayRadius; i <= Parameters.HallwayRadius; ++i)
{
bool hasRegion = false;
var position = new Vector2d(x, y) + opposite * i;
foreach (var region in result.Regions)
{
if (region.RegionType == RegionType.None)
continue;
if (region.Rect.Contains(position))
{
hasRegion = true;
break;
}
}
if (!hasRegion)
{
var newRegion = new Region();
newRegion.RegionType = RegionType.Hallway;
newRegion.RegionId = result.Regions.Count;
newRegion.Rect = new Rect2d(position, new Vector2d(1, 1));
result.Regions.Add(newRegion);
++additionalHallwayCount;
}
}
if (error > 0)
{
x += xInc;
error -= dy;
}
else
{
y += yInc;
error += dx;
}
}
}
return result;
}
protected Vector2d GenerateRandomCenter(Random random)
{
double t = 2 * Math.PI * random.NextDouble();
double u = random.NextDouble(0, 2);
double r = u > 1 ? (2 - u) : u;
int x = (int)Math.Round(Parameters.GenerationRadius * r * Math.Cos(t));
int y = (int)Math.Round(Parameters.GenerationRadius * r * Math.Sin(t));
return new Vector2d(x, y);
}
protected Vector2d GenerateRandomSize(Random random)
{
var x = random.Next(Parameters.MinRegionSize.X, Parameters.MaxRegionSize.X);
var y = random.Next(Parameters.MinRegionSize.Y, Parameters.MaxRegionSize.Y);
return new Vector2d(x, y);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment