2d Dungeon Layout Generator

DungeonGenerator.cs

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