A “typical” BSP-based dungeon generation routine generates functionally clean levels (e.g. all rooms connected, no random or “dead end” corridors [which I hate! *grumble*]). However, it’s also fairly… straightlaced. I’m not sure I’d notice it in a game, but looking at the levels my generator is generating, they feel kind of blah. So I took a look at DCSS, and came to the realization that the DCSS dungeons were fabricated by utterly insane digger gnomes.

The funny thing was, I never questioned the odd layout artifacts that you can get in DCSS; e.g. doors in walls in the middle of a room (and where you can take two steps to walk around it!). In fact, I really do like the layouts, and I just find it odd that I never questioned it – maybe it’s because DCSS is my “brain coma candy…”

At any rate, so I took a look at an example DCSS map (btw; yes, I realize DCSS has multiple map types – I’m just focusing on one for now). Take a gander:
dcss_corridros

Now tell me – what crazy, addled, pea-brained digger gnome is goin to dig something like that?  It’s like a flattened termite’s nest (which, hey, may actually be how gnomes would dig!).  Still; it’s fun! So, I want it in my version :).

The Crazy Corridors Algorithm

Taking a look at the image above, it doesn’t take too long to come up with an algorithm that provides crazy corridors while maintaining the “all rooms must be connected (eg no orphans)” requirement.  Here’s what I do:

  1. Partition the map just like I did before
  2. Enumerate all leaf nodes (which contain the rooms), and create a list of rooms
  3. Randomize the list of rooms
  4. Connect room ‘n’ to room ‘n + 1’ (not looping at the end of the list).  Note that the DiggerGnome needs to be updated (we did this in the last post) to have a mode which says “just keep digging!”, since the previous model had it dig “until you run into something.”  Now, we explicitly do not want to stop, and instead keep going right through those rooms.  That’s what generates the crazy (and interesting!) look to the level.

And that’s it! Note that you want to randomize the list (step 3), because the list you get by enumerating leaf nodes will return rooms that are next to each other in the partitioning, thus reducing the number of long corridors.  We want lots of long corridors to maximize the craziness.  We could actually optimize further (e.g. don’t randomize, but instead generate a list of farthest-possible-rooms; and interesting problem but not for now) – but it’s not necessary, as the random approach works well enough.

I have no idea if this is how DCSS does it, but it works well for me.  Here’s the high level algorithm:

                // Mimic DCSS's approach - get a list of rooms; randomize it; then dig corridors between them all, going right through rooms as we go.
                // This approach generates odd (eg doors in the middle of nowhere), but cool looking layouts.

                // 1. Get the list of regions with rooms in them
                // 2. Randomize the list (so we don't connect too many rooms that are right next to each other; counter-intuitive, I know)
                // 3. Connect the lists in order (connect #0 to #1, connect #1 to #2, etc).  brute force it.

                // Generate the list of rooms.  Don't pass a corridor generator since we're handling it ourselves post-processing.
                partitionedTree.BottomsUpByLevelEnumerate(new RoomGeneratorDelegate(roomGenerator), null);

                // Get the list of rooms
                List<DungeonBSPNode> roomRegions = partitionedTree.GetRoomRegions();

                // Randomize the list order (Go go Gadget-C#!)
                roomRegions.Sort(delegate { return (Rand.Next(2) == 1) ? -1 : 1; });

                // Connect the room regions in the newly randomized list order
                DungeonBSPNode previousRoom = null;
                foreach (DungeonBSPNode currentRoom in roomRegions)
                {
                    if (previousRoom != null)
                        BruteForceConnectRooms(previousRoom, currentRoom);
                    previousRoom = currentRoom;
                }

GetRoomRegions() is just a Leaf enumeration of the BSP tree
btw – note the way the list of roomRegions gets sorted :). Gotta love C# (oy, gonna be some pain when I migrate to Objective C).

And here is the code for the BruteForceConnectRooms method. This code is very similar to the DefaultCorridorGenerator; while I could have merged it, I worry about conflating/confusing the functions (which already take a bit of parsing to fully grok). I may move them together later, but for now am keeping them separate and simply assuming I’ll never have to change anything in them ;-).

        private void BruteForceConnectRooms(DungeonBSPNode regionA, DungeonBSPNode regionB)
        {
            // We don't care if we go through existing rooms; the goal is that we actually get atypical rooms...
            DiggerGnome digger = new DiggerGnome(TargetMap);

            if (regionA.BoundingRect.Bottom < regionB.BoundingRect.Top || regionB.BoundingRect.Bottom < regionA.BoundingRect.Top)
            {
                // Vertical split.  Determine which one is the upper & lower region
                DungeonBSPNode upperRegion = (regionA.BoundingRect.Bottom < regionB.BoundingRect.Top) ? regionA : regionB;
                DungeonBSPNode lowerRegion = (upperRegion == regionA) ? regionB : regionA;

                // If the nodes' regions overlap horizontally by at least 3 (leaving room for walls), then we can just dig a
                // single vertical tunnel to connect them; otherwise, we need to dig an 'L' shapped corridor to connect them.
                int minOverlappingX = Math.Max(upperRegion.BoundingRect.Left, lowerRegion.BoundingRect.Left);
                int maxOverlappingX = Math.Min(upperRegion.BoundingRect.Right, lowerRegion.BoundingRect.Right);
                if (maxOverlappingX - minOverlappingX >= 3)
                {
                    // The regions overlap; we can dig a single vertical corridor to connect them
                    // Determine the range of X axis values that we can dig at in order to connect the regions
                    int corridorX = minOverlappingX + 1 + Rand.Next(maxOverlappingX - minOverlappingX - 2);

                    // Start at the border between the two regions at X=corridorX and dig towards the outside
                    // edge of each region; we are gauranteed to eventually hit something since the regions' bounding
                    // rects overlapped.
                    digger.Dig(corridorX, upperRegion.BoundingRect.Bottom, Direction.Up, 0, true);
                    digger.Dig(corridorX, upperRegion.BoundingRect.Bottom + 1, Direction.Down, lowerRegion.BoundingRect.Top - (upperRegion.BoundingRect.Bottom + 1), true);
                }
                else
                {
                    // They don't overlap enough; dig an 'L' shaped corridor to connect them.
                    int tunnelMeetX, tunnelMeetY;

                    if (upperRegion.BoundingRect.Left > lowerRegion.BoundingRect.Left)
                    {
                        //        _____
                        //        |   |
                        //        | L |
                        //        |___|
                        //  _____   |
                        //  |   |   |
                        //  | R |___|X
                        //  |___|    
                        tunnelMeetX = RandomValueBetween(Math.Max(upperRegion.BoundingRect.Left + 1, lowerRegion.BoundingRect.Right + 1), upperRegion.BoundingRect.Right);
                        tunnelMeetY = RandomValueBetween(lowerRegion.BoundingRect.Top + 1, lowerRegion.BoundingRect.Bottom);
                        digger.DigUpLeftCorridor(tunnelMeetX, tunnelMeetY, lowerRegion.BoundingRect.Right, upperRegion.BoundingRect.Bottom);
                    }
                    else
                    {
                        //    _____
                        //    |   |
                        //    | L |
                        //    |___|
                        //      |    _____
                        //      |    |   |
                        //     X|____| R |
                        //           |___|    
                        tunnelMeetX = RandomValueBetween(upperRegion.BoundingRect.Left, Math.Min(lowerRegion.BoundingRect.Left, upperRegion.BoundingRect.Right - 1));
                        tunnelMeetY = RandomValueBetween(lowerRegion.BoundingRect.Top + 1, lowerRegion.BoundingRect.Bottom);
                        digger.DigUpRightLCorridor(tunnelMeetX, tunnelMeetY, lowerRegion.BoundingRect.Left, upperRegion.BoundingRect.Bottom);
                    }
                }
            }
            else
            {
                // Horizontal split.  Determine which one is the left & right region
                DungeonBSPNode leftRegion = (regionA.BoundingRect.Right < regionB.BoundingRect.Left) ? regionA : regionB;
                DungeonBSPNode rightRegion = (leftRegion == regionA) ? regionB : regionA;

                // If the nodes' regions overlap vertically by at least 3 (leaving room for walls), then we can just dig a
                // single horizontal tunnel to connect them; otherwise, we need to dig an 'L' shapped corridor to connect them.
                int minOverlappingY = Math.Max(leftRegion.BoundingRect.Top, rightRegion.BoundingRect.Top);
                int maxOverlappingY = Math.Min(leftRegion.BoundingRect.Bottom, rightRegion.BoundingRect.Bottom);
                if (maxOverlappingY - minOverlappingY >= 3)
                {
                    // The regions overlap; we can dig a single horizontal corridor to connect them
                    // Determine the range of Y axis values that we can dig at in order to connect the regions
                    int corridorY = minOverlappingY + 1 + Rand.Next(maxOverlappingY - minOverlappingY - 2);

                    digger.Dig(leftRegion.BoundingRect.Right, corridorY, Direction.Left, 0, true);
                    digger.Dig(leftRegion.BoundingRect.Right + 1, corridorY, Direction.Right, rightRegion.BoundingRect.Left - (leftRegion.BoundingRect.Right + 1), true);
                }
                else
                {
                    // They don't overlap enough; dig an 'L' shaped corridor to connect them.
                    int tunnelMeetX, tunnelMeetY;

                    if (leftRegion.BoundingRect.Top > rightRegion.BoundingRect.Top)
                    {
                        // Left region's bounding rect is below the Right region's bound rect.
                        //        _____
                        //   X____|   |
                        //    |   | R |
                        //    |   |___|
                        //  __|__
                        //  |   |
                        //  | L |
                        //  |___|
                        tunnelMeetX = RandomValueBetween(leftRegion.BoundingRect.Left + 1, leftRegion.BoundingRect.Right);
                        tunnelMeetY = RandomValueBetween(rightRegion.BoundingRect.Top + 1, Math.Min(rightRegion.BoundingRect.Bottom - 1, leftRegion.BoundingRect.Top));
                        digger.DigDownRightCorridor(tunnelMeetX, tunnelMeetY, rightRegion.BoundingRect.Left, leftRegion.BoundingRect.Top);
                    }
                    else
                    {
                        // Left child region's bounding rect is above the Right child region's bound rect.
                        //    _____
                        //    |   |____X
                        //    | L |   |
                        //    |___|   |
                        //          __|__
                        //          |   |
                        //          | R |
                        //          |___|
                        tunnelMeetX = RandomValueBetween(rightRegion.BoundingRect.Left + 1, rightRegion.BoundingRect.Right);
                        tunnelMeetY = RandomValueBetween(leftRegion.BoundingRect.Top + 1, Math.Min(leftRegion.BoundingRect.Bottom - 1, rightRegion.BoundingRect.Top));
                        digger.DigDownLeftLCorridor(tunnelMeetX, tunnelMeetY, leftRegion.BoundingRect.Right, rightRegion.BoundingRect.Top);
                    }
                }
            }
        }

And what do we get for all that? Crazy Corridors! 🙂

crazycorridors1

Man, this is fun :).

Here’s the code: 4-14 Code

Next up – not sure yet.  May be time to move away from the level generation and into the actual game flow, but I may play around with a bit of dungeon population. (Oop, just remembered that I still need to re-enable Special Rooms with the corridors; had some good thoughts on that in the car – guess that’s next).

Cheers,
Jeff

Advertisements