If you've missed any earlier parts of this series, head over here to find them.

This part of the series discussed some various connections between rooms. I don't need to tell you again, a dungeon with just one room runs a great risc of being extremly boring to play. An important part of the gameplay is exploring, being surprised and feeling progress.

If I take a real life example, an office is sort of a dungeon. You have your entrance, there are corridors between different areas and there are doors into rooms where the nasty bosses reside. And somewhere within this deep dungeon, there is the final boss. The executive CEO which breathes fire out of his mouth and is feared and loathed by the minions of this dungeon. The minions will defend this CEO when faced with an attack from an outside company, but rest assure, he is hated. (If you CEO is a friendly, pleasant one, imagine he practices the occult in his free time and that his sugarsweet pleasantness is just a show for the gallery. If you don't have a CEO, substitute him with your wife.)

In this office dungeon, there are also rooms that are composed by merged rectangles (or cubes rather). This connection between two rooms, is named merged rooms. I will discuss the basic principle for connecting and placing two rooms in the article. I will also show you how to place a door. This sounds very basic and it really is, but it's the way it's performed is what's important. This is because I base most calculations on these principles throughtout the series.

I will discuss corridors, merges rooms, portals, paths, etc in later articles. Time to absorb!

Basic connection principle

As I've explained earlier, the edges of the room are the tiles from which you can pass into the passable bounds of the room. 

All connections to the room should overlap the edges. That also means that any connections starting or ending position can be calculated based on the edges of two rooms. Simple enough, eh? The edges of the room you've just generated can be used to calculate the position of the next. Pondering that statement, the generators which creates connections between rooms should also be able to position rooms according to their preferences.

The generators should be able to be weighted aswell, to ensure that your generated dungeon looks the way you want. Maybe you only want 80% doors and 20% corridors or that you only want to merge rooms together. The generators should also have a name, so you can control which to use at what point from the outside. Just like you would name your baby boy (or in my case, my baby girl).

    public abstract class ConnectionGenerator : IMapPartGenerator
    {
        public string Name { get; set; }
        public int UsageWeight { get; set; }
        public int UsageTimes { get; set; }
        public bool PreventChaining { get; set; }
        public MapGenerationSharedData Data { get; private set; }
        public abstract List<MapEntity> CreateConnection(MapEntity source, MapEntity target, Position suggestedDirection, bool placeTargetEntity);
        public abstract bool Place(MapEntity source, MapEntity target, Position suggestedDirection);

        public void Initialize(MapGenerationSharedData data)
        {
            Data = data;
            IsInitialized = true;
        }
    }

    public interface IMapPartGenerator
    {
        string Name { get; set; }
        int UsageWeight { get; set; }
        int UsageTimes { get; set; }
    }

Position is a class that looks a lot like Vector2 from XNA. It has some additional methods for swapping axis and inverting axis since it's also used as a direction. There's clockwise and counter clockwise turning and some other helpers attached to it aswell.

Instead of using Vector2, I made my own. I've also made an own Rectangle. Why? Because I want the library to be platform indepentent by default. And ofc, because I can.

    public struct Position : IEqualityComparer<Position>
    {
        public int X;
        public int Y;

        public static Position Up { get { return new Position(0, 1); } }
        public static Position Down { get { return new Position(0, -1); } }
        public static Position Left { get { return new Position(-1, 0); } }
        public static Position Right { get { return new Position(1, 0); } }
        public static Position Empty { get { return new Position(int.MinValue, int.MinValue); } }

        public bool Horizontal { get { return X != 0; } }
        public bool Vertical { get { return X != 0; } }

        public static Position RandomDirection(Random rand)
        {
            int dir = rand.Next(0, 5);
            
            switch (dir)
            {
                case 0:
                    return Up;
                case 1:
                    return Down;
                case 2:
                    return Left;
                default:
                    return Right;
            }
        }

        public int Length
        {
            get
            {
                if (Horizontal)
                    return Math.Abs(X);
                else
                    return Math.Abs(Y);
            }
        }

        public Position ClockWise()
        {
            return new Position(Y, X * -1);
        }

        public Position CounterClockWise()
        {
            return new Position(Y * -1, X);
        }

        public Position SwapAxis()
        {
            return new Position(Y, X);
        }

        public Position Positive()
        {
            return new Position((X < 0) ? X * -1 : X, (Y < 0) ? Y * -1 : Y);
        }

        public Position Negative()
        {
            return new Position((X > 0) ? X * -1 : X, (Y > 0) ? Y * -1 : Y);
        }

        public Position Invert()
        {
            return this * -1;
        }

        public Position Direction()
        {
            return new Position((X > 0) ? Math.Min(X, 1) : Math.Max(X, -1), (Y > 0) ? Math.Min(Y, 1) : Math.Max(Y, -1));
        }

        public Position DominantDirection()
        {
            if (Math.Abs(X) > Math.Abs(Y))
                return new Position((X > 0) ? Math.Min(X, 1) : Math.Max(X, -1), 0);
            else
                return new Position(0, (Y > 0) ? Math.Min(Y, 1) : Math.Max(Y, -1));
        }

        public Position(int x, int y)
        {
            X = x;
            Y = y;
        }

        public static Position operator +(Position a, Position b)
        {
            a.X += b.X;
            a.Y += b.Y;
            return a;
        }

        public static Position operator *(Position a, Position b)
        {
            a.X *= b.X;
            a.Y *= b.Y;
            return a;
        }

        public static Position operator *(Position a, int b)
        {
            a.X *= b;
            a.Y *= b;
            return a;
        }

        public static Position operator -(Position a, Position b)
        {
            a.X -= b.X;
            a.Y -= b.Y;
            return a;
        }

        public static bool operator ==(Position a, Position b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(Position a, Position b)
        {
            return !a.Equals(b);
        }

        public bool Equals(Position x, Position y)
        {
            return (x.X == y.X && y.Y == x.Y);
        }

        public int GetHashCode(Position obj)
        {
            return X * 1000 + Y;
        }

        public override string ToString()
        {
            return "X: " + X + " Y: " + Y;
        }
    }

PathItem is a position coupled with a direction. It also holds information on how far away it is from the nearest end of the path. For instance, if you have three ParthItems connected with each other from (0,0) to (2,0), the one in the middle would have 1 as the distance from the nearest edge within the path. It could also be NearestPathEnd, but I'm sticking with NearestEdge. The direction tells which direction this PathItem is facing. When I use them for edges, the direction will be pointing out from the bounds of the room. So, an edge on the the north wall of a room would be pointing North/Up (X: 0, Y: 1).

    public class PathItem
    {
        public Position Position { get; set; }
        public Position Direction { get; set; }
        public int NearestEdge { get; set; }

        public override string ToString()
        {
            return "Position " + Position + ", Direction " + Direction;
        }
    }

Connection by door

So, we have our basic classes to help us out with the connection. What now? Ahh yeah, we need to get the edges and compare them. But the second room hasn't been positioned yet, so we'll do this first. Get the edges from the first room, choose a direction and and align the room to the edge.

        // find common edges
        var matches = sourceEdges.FindMatchingEdges(targetEdges, suggestedDirection);
        var allGroups = (from x in matches orderby x.Count descending select x).ToList();

        public override List<MapEntity> CreateConnection(MapEntity source, MapEntity target, Position suggestedDirection, bool positionTargetEntity)
        {
            var fromRoom = (Room)source;
            var toRoom = (Room)target;

            var sourceEdges = (from x in fromRoom.GetEdges(1) where x.Direction == suggestedDirection select x).ToList();
            var alignTos = (from x in sourceEdges where x.NearestEdge > 1 select x).ToList();

            var alignTo = alignTos[Data.Next(0, alignTos.Count)];
            toRoom.Align(alignTo.Position, alignTo.Direction);

            // get target edges
            var invDirection = suggestedDirection.Invert();
            var targetEdges = (from x in toRoom.GetEdges(1) where x.Direction == invDirection select x).ToList();
            // find common edges
            var matches = sourceEdges.FindMatchingEdges(targetEdges, suggestedDirection);
            var allGroups = (from x in matches orderby x.Count descending select x).ToList();
        }

        public static void Align(this Room room, Position position, Position connectionDirection)
        {
            var from = position;

            if (connectionDirection.Y < 0 || connectionDirection.X < 0)
                from += new Position(room.Width, room.Height) * connectionDirection;
            else
                from += new Position(1, 1) * connectionDirection;

            room.Position = from;

            // center room
            if (connectionDirection.Y < 0 || connectionDirection.X < 0)
            {
                room.Position += new Position((room.Width / 2) * connectionDirection.Y,(room.Height / 2) * connectionDirection.X);
            }
            else
            {
                room.Position -= new Position((room.Width / 2) * connectionDirection.Y, (room.Height / 2) * connectionDirection.X);
            }
        }

Here we Align the second room to the first, so that their perimiters, but most importantly, edges, will overlap. So ok, now it's time to bring out some nifty matching of edges and sort them into groups. Why groups? It's helpful if we need a door of a certain size or if there is more than one set of edges on a room. This can happen if you have a room shaped like an U. At the top of that room, there are two ways of getting in and out from it, thus having two groups of edges at the top.

        public static List<List<PathItemPair>> FindMatchingEdges(this List<PathItem> sourceEdges, List<PathItem> targetEdges, Position direction)
        {
            List<PathItemPair> matches = new List<PathItemPair>();

            foreach (var edge in sourceEdges)
            {
                if (direction.Horizontal)
                {
                    var match = (from x in targetEdges where x.Position.Y == edge.Position.Y select x).FirstOrDefault();

                    if (match != null)
                        matches.Add(new PathItemPair() { First = edge, Second = match });
                }
                else
                {
                    var match = (from x in targetEdges where x.Position.X == edge.Position.X select x).FirstOrDefault();

                    if (match != null)
                        matches.Add(new PathItemPair() { First = edge, Second = match });
                }
            }

            if (matches.Count == 0)
                return null;

            // find clusters of corridors
            List<List<PathItemPair>> allGroups = new List<List<PathItemPair>>();
            List<PathItemPair> group = new List<PathItemPair>();
            allGroups.Add(group);

            var startMatch = matches[0];
            group.Add(startMatch);
            matches.Remove(startMatch);

            var widthDir = startMatch.First.Direction.SwapAxis();
            var widthInvDir = startMatch.First.Direction.SwapAxis();

            while (matches.Count > 0)
            {
                bool found = false;

                for (int i = 0; i < matches.Count; i++)
                {
                    if (matches[i].First.Position + widthDir == startMatch.First.Position
                        || matches[i].First.Position - widthDir == startMatch.First.Position)
                    {
                        startMatch = matches[i];
                        group.Add(startMatch);
                        matches.RemoveAt(i);
                        found = true;
                    }
                }

                if (!found)
                {
                    group = new List<PathItemPair>() { matches[0] };
                    allGroups.Add(group);
                    matches.RemoveAt(0);
                }
            }

            return allGroups;
        }

And voila! We have the all the PathItems where the door can be placed. We might have 5 items, and we only want two. Then prune the ends. Is it boring that the room you're going to is centered to it's entrance? Well then, change the align method or try to slide the second room until you are satisfied.

Tags: Generating dungeons