Category: Dungeon Generation


prefab_standard_corridros

Look who’s back!  With corridors growing out of his face this time!

I reintegrated the Special Room code into the new corridor-supporting code base… sort of.  It works just fine, but only so long as corridors can connect to any part of the room (e.g. rather than just doors).   Given the way the BSP approach works, it’s not immediately clear to me how to make it work; in particular the case where the BSP tree pairs up the special room region with a region that is on the other side of the door.  In that scenario, my digger gnome (who only know how to go straight or do one L-corner) can’t connect them.  There are a few options that occurred to me – e.g.:

  1. Require that rooms have multiple exits on each edge (meh)
  2. Build rooms that have lots of floor around them; a variant of #1 above with its own issues, but might be okay…
  3. If it’s not possible to connect, then rotate the room until it is (better, but still meh).  I’d eventually like to support rotating rooms anyways for variety, so this may not be too bad.
  4. Populate the entire BSP tree except for the special room, and then pick any room in the “right direction” and dig towards it, stopping at anything you find.  Best solution, but I haven’t thought through if I can set up the BSP tree properly to work with this.
  5. implement a smarter Digger (eg A* based).  Intriguing, but not yet…

Still, for now this’ll suffice.  Here’s what it looks like with the crazy corridors approach; notice that the digger gnome is doing what it’s told, and is powering right through everything – the special room included – until it gets to its destination (that’s how the crazy corridors approach works).  Obviously you’d want to wrap the special room in something that keeps diggers from going through it; however, I can’t just stop them (it would no longer gaurantee all rooms were connected), and don’t yet have a way to go around them.  So; net result is that special rooms are back in … sort of.

prefab_with_crazy_corridors

And here’s the code: Code

Next up: Still not sure.  Flying out on a red eye tomorrow night and doing extended family stuff until Monday – hopefully will be able to get some coding time in (but the posts may not be posted until Monday).

Cheers,

Jeff

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

Per my last post, the DigCorridor function has bugged me, so I got around to rewriting it.  I’m much happier with the new function – bugs notwithstanding, it should function for just about any corridor-generating function I create.  While I was at it, I extracted the digging functionality out into a “DiggerGnome” class.  Partially to have fun with it, but also because I can see a world in which the corridor digging mechanism can be altered without altering the rest of the dungeon generation.  For instance, if the RoomGenerator is a “CaveRoomGenerator” type deal, then the Digger object could actually vary its path in a nonlinear fashion to be more appropriate to that level.  Similarly, imagine a pet that the player could have which digs quasi-randomly – a “drunk gnome” for instance :).

        // Note: curDirection is future-proofing; I can imagine a world in which we have nonlinear diggers.  Imagine a drunk diggergnome, for instance 🙂
        public void Dig(int startX, int startY, Direction startingDirection, int requiredDigDistance, bool continueDiggingAfterRequiredDistanceUntilHitFloor)
        {
            // Foreman: "Hey you, wake up!"
            // Gnome: "*snort* Huh? Wha'?"
            // Foreman: "Stand over there and face this way!"
            // Gnome: "*grumble*" <Starts shuffling over>
            int curX = startX;
            int curY = startY;
            Direction curDirection = startingDirection;

            // Foreman: "Alright you, start digging, and don't stop for anything until you've dug that far!
            //           After that, I may want you to keep digging until you complete the tunnel..."
            // Foreman: "And you're not done until I *say* you're done!"
            bool doneDigging = false;

            // Gnome: "*mutter*" <Picks up pickaxe, starts hacking away>
            do
            {
                // Forman: "Dig here!"
                _targetMap.Cells[curX, curY] = new Cell_Floor();

                // Foreman: "Hey, make sure you shore up these walls, you maggot!"
                // Gnome: <eyes foreman's back, fingers pick edge> "*grumble*"
                if (curDirection == Direction.Left || curDirection == Direction.Right)
                {
                    _targetMap.PaintCellIfEmpty(curX, curY - 1, new Cell_Wall());
                    _targetMap.PaintCellIfEmpty(curX, curY + 1, new Cell_Wall());
                }
                else
                {
                    _targetMap.PaintCellIfEmpty(curX - 1, curY, new Cell_Wall());
                    _targetMap.PaintCellIfEmpty(curX + 1, curY, new Cell_Wall());
                }

                // Foreman: "Alright, ease up - let's see if you've dug far enough yet..."
                // Gnome: *sneers* <plops down and leans against the cave wall>
                requiredDigDistance--;
                if (requiredDigDistance <= 0)
                {
                    // Foreman: <checks tunnel plan on paper> "Hmm, seems like you've dug the required distance - *finally*"
                    // Gnome: <starts to get up and head back to the start of the tunnel>
                    if (continueDiggingAfterRequiredDistanceUntilHitFloor)
                    {
                        // Foreman: "Hey! Where do you think you're going?  I didn't say you were done yet!  See if you broke through yet!"
                        // Gnome: *grumbles*
                        if ((curDirection != Direction.Right && _targetMap.Cells[curX - 1, curY].GetType() == typeof(Cell_Floor)) ||
                            (curDirection != Direction.Left && _targetMap.Cells[curX + 1, curY].GetType() == typeof(Cell_Floor)) ||
                            (curDirection != Direction.Down && _targetMap.Cells[curX, curY - 1].GetType() == typeof(Cell_Floor)) ||
                            (curDirection != Direction.Up && _targetMap.Cells[curX, curY + 1].GetType() == typeof(Cell_Floor)))
                        {
                            // Gnome: <gestures towards the light coming from in front of them and glares up at the foreman>
                            // Foreman: "Huh, we made it.  Must be my great management ability!"  
                            doneDigging = true;
                        }
                    }
                    else
                        doneDigging = true;
                }

                if (!doneDigging)
                {
                    // Foreman: "Alright you - keep moving, we're not done yet!"
                    switch (curDirection)
                    {
                        case Direction.Left: curX--; break;
                        case Direction.Right: curX++; break;
                        case Direction.Up: curY--; break;
                        case Direction.Down: curY++; break;
                    }

                    // <debug: needed since the bounding rect & circular room>
                    if (curX < 1 || curY < 1 || curX >= _targetMap.MapWidth - 1 || curY >= _targetMap.MapHeight - 1)
                        return;
                }

            } while (!doneDigging);

            // Foreman: "One more thing - make sure there aren't any un-shored up walls here.  Then you can skitter off"
            // Gnome: <climbs up from floor, mutters a curse at the foreman, and looks around>
            for (int x = curX - 1; x <= curX + 1; x++)
                for (int y = curY - 1; y <= curY + 1; y++)
                    _targetMap.PaintCellIfEmpty(x, y, new Cell_Wall());
        }

I’ll include the code in the next post, since it includes other stuff I’ve done tonight.

If you take a look at the day 3 post below, you’ll no doubt see that the DefaultCorridorGenerator function was pretty unwieldy (> 200 lines).  While a lot of that was comments, about 50 lines of it was dedicated to “ensuring variety” when placing corridors by including both possible corridor directions – e.g. in a case like

                //        _____
                //   X____|   |
                //    |   | R |
                //    |   |___|
                //  __|__
                //  |   |
                //  | L |
                //  |___|
                tunnelMeetX = RandomValueBetween(leftChild.BoundingRect.Left + 1, leftChild.BoundingRect.Right);
                tunnelMeetY = RandomValueBetween(rightChild.BoundingRect.Top + 1, Math.Min(rightChild.BoundingRect.Bottom - 1, leftChild.BoundingRect.Top));
                DigDownRightCorridor(tunnelMeetX, tunnelMeetY);

The corridor could actually exit the lower region from the top or the right edge of the region. I was worried that if I only chose one, then the map might seem to favor particular corridor orientations (granted, no one would really notice it, but I would 😉 ).

The problem with that ill-conceived sense of purity was that it resulted in a large and quite repetitive looking (and error-prone) function. Case in point – the above code snippet is hit in the case of a horizontal partition (dungeonNode.SplitOrientation == DungeonBSPNode.Orientation.Horizontal), and the vertical partition case had a similar, but different chunk of code with the child nodes reversed –

                 //        _____
                 //   X____|   |
                 //    |   | L |
                 //    |   |___|
                 //  __|__
                 //  |   |
                 //  | R |
                 //  |___|
                 tunnelMeetX = RandomValueBetween(rightChild.BoundingRect.Left + 1, Math.Min(rightChild.BoundingRect.Right - 1, leftChild.BoundingRect.Left));
                 tunnelMeetY = RandomValueBetween(leftChild.BoundingRect.Top + 1, leftChild.BoundingRect.Bottom);
                 DigDownRightCorridor(tunnelMeetX, tunnelMeetY);

The end result to the user is similar, and the code looks similar, but it’s sufficiently different that I couldn’t easily refactor it into down.

Well, turns out I don’t need to worry about it. It occurred to me on my (45 minute – oy!) drive into work that the partitioning approach gave just as much odds to vertical as horizontal splits, so as long as I ensured that one of them (Horiz, in my case) dug Down/Right corridors & Down/Left corridors, and the other (Vert) dug Up/Right & Up/Left corridors, then I’d have an equally random chance of having each different type of corridor in the level. Obvious in hindsight, but I’ll take pleasure from getting to remove some of that code instead :).

Code!

I picked up a DropBox account and put the source code up there. Consume at your own risk – it’s butt uhhhh-gly right now (hey, I’m doing this for me, not you 🙂 ) – but it might shed more light on what I’m talking about in these posts. I’ll try to include code each time I make a new post.

Code for 4-12 Post

Cheers,
Jeff

ellipseroomsWork is impinging upon my coding time (how dare it!), so didn’t get a chance to do too much tonight.  I did generalize the level generation code a bit, so that I can swap in different generators.  It’s just a first pass at generatlization, but I created a “RoundRoomGenerator” function alongside the “SquareRoomGenerator” that I previously had, and with no changes to the BSP code the generator can now create different kinds of rooms.  Round Rooms aren’t that interesting themselves, but you can imagine plugging in more complex room generators in the future, without having to worry about impact to partitioning or corridor generation logic.

There are a few errors in the pic; a couple of orphaned rooms and corridors without proper endcaps – these are both due to the DigCorridor logic that I wasn’t happy with.  I have some thoughts on how to clean that up, and hope to have that tomorrow.

So; code changes included:

New Room Generator Delegates

I created a few more roomGenerators, and randomly pick one:

            // Variety is the spice of life; mix things up a bit.
            RoomGeneratorDelegate roomGenerator;

            // Choose square or round rooms (or mix).  In future, have more complex room generators.
            switch (Rand.Next(3))
            {
                case 0:
                    roomGenerator = new RoomGeneratorDelegate(SquareRoomGenerator);
                    break;
                case 1:
                    roomGenerator = new RoomGeneratorDelegate(RoundRoomGenerator);
                    break;
                default:
                    roomGenerator = new RoomGeneratorDelegate(RandomShapeRoomGenerator);
                    break;
            }

New RoundRoomGenerator function

Very similar to the SquareRoomGenerator (hinting at further abstraction to come later). Only change is that when it paints the room, it paints an ellipse instead of a rectangle.

Obviously, I’m not stressing too much about the performance of this, since it’s just for example purposes.

        // Create a room in the area specified by the regionNode.
        public void RoundRoomGenerator(DungeonBSPNode dungeonRegion)
        {
            int MinIdealRoomSize = 7;

            // Convert from absolute normalized coordinates (0.0-1.0) to Map coordinates (0-(MapWidth-1), 0-(MapHeight-1))
            int xRegionStart = (int)Math.Ceiling((dungeonRegion.RegionEdges.Left * (TargetMap.MapWidth - 1)));
            int yRegionStart = (int)Math.Ceiling((dungeonRegion.RegionEdges.Top * (TargetMap.MapHeight - 1)));
            int xRegionEnd = (int)((dungeonRegion.RegionEdges.Right * (TargetMap.MapWidth - 1)));
            int yRegionEnd = (int)((dungeonRegion.RegionEdges.Bottom * (TargetMap.MapHeight - 1)));
            int regionWidth = xRegionEnd - xRegionStart;
            int regionHeight = yRegionEnd - yRegionStart;

            int roomWidth = RandomValueBetween(Math.Min(MinIdealRoomSize, regionWidth), regionWidth);
            int roomHeight = RandomValueBetween(Math.Min(MinIdealRoomSize, regionHeight), regionHeight);

            int xRoomStart = xRegionStart + Rand.Next(regionWidth - roomWidth);
            int yRoomStart = yRegionStart + Rand.Next(regionHeight - roomHeight);

            // Store the room coordinates in the Dungeon Region Node (we'll want them again later for corridor creation)
            dungeonRegion.BoundingRect = new Rectangle(xRoomStart, yRoomStart, roomWidth, roomHeight);
            dungeonRegion.RoomBuilt = true;

            // "Paint" the room into the Map
            TargetMap.PaintCellEllipse(xRoomStart, yRoomStart, xRoomStart + roomWidth, yRoomStart + roomHeight, new Cell_Wall(), true);
            TargetMap.PaintCellEllipse(xRoomStart + 1, yRoomStart + 1, xRoomStart + roomWidth - 1, yRoomStart + roomHeight - 1, new Cell_Floor(), true);
        }

PaintCellEllipse function

It’s not all that relevant, but here’s the function to fill an ellipse that fills the specified bounding rectangle:

        public void PaintCellEllipse(int xStart, int yStart, int xEnd, int yEnd, Cell cell)
        {
            // Draw an ellipse centered in the passed-in coordinates
            float xCenter = (xEnd + xStart) / 2.0f;
            float yCenter = (yEnd + yStart) / 2.0f;
            float radius = Math.Min(xEnd - xStart, yEnd - yStart) / 2.0f;
            float xAxis = (xEnd - xStart) / 2.0f;
            float yAxis = (yEnd - yStart) / 2.0f;
            float majorAxisSquared = (float)Math.Pow(Math.Max(xAxis, yAxis), 2.0);
            float minorAxisSquared = (float)Math.Pow(Math.Min(xAxis, yAxis), 2.0);

            for (int y = yStart; y <= yEnd; y++)
                for (int x = xStart; x <= xEnd; x++)
                {
                    // Only draw if (x,y) is within the ellipse
                    if (Math.Sqrt((x - xCenter) * (x - xCenter) / majorAxisSquared + (y - yCenter) * (y - yCenter) / minorAxisSquared) <= 1.0f)
                        Cells[x, y] = cell;
                }
        }

And just for fun – Mixed rooms

It’s clearly not a big leap to add a MixedRoomGenerator that just randomly selects from the square or round room generator –

        public void RandomShapeRoomGenerator(DungeonBSPNode dungeonRegion)
        {
            if (Rand.Next(2) == 0)
                RoundRoomGenerator(dungeonRegion);
            else
                SquareRoomGenerator(dungeonRegion);
        }

Which generates output like this:
mixedrooms
And that’s it! Not a huge step forward, but an interesting one…

Day 3: Corridors

corridors1As previously mentioned, the use of a BSP tree to generate the dungeon rooms has some nice side benefits – Jice (google away) did a good job of covering how you can work your way up the tree and generate corridors as you go.  To do that here, I changed the previous high level generation approach from:

1) Generate BSP tree

2) Iterate the leaf nodes and create a room in each

to:

1) Generate BSP tree

2) Iterate all nodes in inverse level order (aka breadth first) – for each node:

2A) If it’s a leaf node (Left & Right child == null), add a room to it (just like before)

* New – track bounding regions as we go

2B) If it’s not a leaf node (Left & Right Child != null), then add a corridor between the child nodes

* Also track bounding regions of internal nodes as we go.

Before, we called EnumerateLeafNodes in the Dungeon Generation function.  Now, we call BottomsUpLevelEnumerate and pass callbacks to GenerateRoom and GenerateCorridor functions.  Here’s the new node walking code:

public void BottomsUpByLevelEnumerate(RoomGeneratorDelegate addRoomCallback, CorridorGeneratorDelegate addCorridorCallback)
        {
            Stack stack1 = new Stack();
            Stack stack2 = new Stack();
            stack1.Push(this);
            while (stack1.Count &gt; 0)
            {
                DungeonBSPNode currentNode = (DungeonBSPNode)stack1.Pop();
                stack2.Push(currentNode);
                if (currentNode.Left != null)
                    stack1.Push(currentNode.Left);
                if (currentNode.Right != null)
                    stack1.Push(currentNode.Right);
            }

            while (stack2.Count &gt; 0)
            {
                DungeonBSPNode currentNode = (DungeonBSPNode)stack2.Pop();
                if (currentNode.Left == null &amp;&amp; currentNode.Right == null)
                {
                    // Leaf node - create a room
                    if (!currentNode.RoomBuilt)
                        addRoomCallback(currentNode);
                }
                else
                {
                    // non-leaf node; create corridor
                    if (currentNode.Left.RoomBuilt || currentNode.Right.RoomBuilt)
                        addCorridorCallback(currentNode);
                }
            }
        }

Other chunk of code that’s of interest is the GenerateCorridor callback.  Ye gods, that’s a lot of code!   I’m not happy with the DigCorridor code, but the core DefaultCorridorGenerator function, while too long, is pretty clean.

        public void DefaultCorridorGenerator(DungeonBSPNode dungeonNode)
        {
            DungeonBSPNode leftChild = dungeonNode.Left;
            DungeonBSPNode rightChild = dungeonNode.Right;

            if (leftChild == null || !leftChild.RoomBuilt)
                dungeonNode.BoundingRect = rightChild.BoundingRect;
            else if (rightChild == null || !rightChild.RoomBuilt)
                dungeonNode.BoundingRect = leftChild.BoundingRect;
            else
            {
                // Draw a corridor between our child nodes.  We have been keeping track of their bounding rectangles
                // as we've worked our way up the tree, so we can use that ensure we connect corridors to rooms
                if (dungeonNode.SplitOrientation == DungeonBSPNode.Orientation.Horizontal)
                {
                    // child nodes were split horizontally, so draw a horizontal corridor between them.
                    // 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' or 'Z' shapped corridor to connect them.
                    int minOverlappingY = Math.Max(leftChild.BoundingRect.Top, rightChild.BoundingRect.Top);
                    int maxOverlappingY = Math.Min(leftChild.BoundingRect.Bottom, rightChild.BoundingRect.Bottom);
                    if (maxOverlappingY - minOverlappingY &gt;= 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);

                        // Start at the border between the two regions at Y=corridorY and dig towards the outside
                        // edge of each region; we are gauranteed to eventually hit something since the regions' bounding
                        // rects overlapped.
                        DigCorridor(leftChild.BoundingRect.Right, corridorY, Direction.Left);
                        DigCorridor(leftChild.BoundingRect.Right+1, corridorY, Direction.Right);
                    }
                    else
                    {
                        // They don't overlap enough; dig an 'L' or 'Z' shaped corridor to connect them.
                        // For now, just support 'L' corridors
                        int tunnelMeetX, tunnelMeetY;

                        // For variety, the 'L' corridor can come out of the top of the bottom child or the side of the bottom child.
                        bool corridorExitsLeftChildsTopEdge = (rand.Next(2) == 0);

                        // Note that some of the math below (in particular the Mins and Maxs) are because the regions *can* be slightly overlapping in
                        // the appropriate dimension; we don't draw a straight line if they overlap by less than 3 (to minimize the number of odd corridors
                        // that attach to the outside corner of a room)
                        if (leftChild.BoundingRect.Top &gt; rightChild.BoundingRect.Top)
                        {
                            // Left child region's bounding rect is below the Right child region's bound rect.
                            if (corridorExitsLeftChildsTopEdge)
                            {
                                //        _____
                                //   X____|   |
                                //    |   | R |
                                //    |   |___|
                                //  __|__
                                //  |   |
                                //  | L |
                                //  |___|
                                tunnelMeetX = RandomValueBetween(leftChild.BoundingRect.Left + 1, leftChild.BoundingRect.Right);
                                tunnelMeetY = RandomValueBetween(rightChild.BoundingRect.Top + 1, Math.Min(rightChild.BoundingRect.Bottom - 1, leftChild.BoundingRect.Top));
                                DigDownRightCorridor(tunnelMeetX, tunnelMeetY);
                            }
                            else
                            {
                                //        _____
                                //        |   |
                                //        | R |
                                //        |___|
                                //  _____   |
                                //  |   |   |
                                //  | L |___|X
                                //  |___|
                                tunnelMeetX = RandomValueBetween(rightChild.BoundingRect.Left + 1, rightChild.BoundingRect.Right);
                                tunnelMeetY = RandomValueBetween(Math.Max(leftChild.BoundingRect.Top + 1, rightChild.BoundingRect.Bottom + 1), leftChild.BoundingRect.Bottom);
                                DigUpLeftCorridor(tunnelMeetX, tunnelMeetY);
                            }
                        }
                        else
                        {
                            // Left child region's bounding rect is above the Right child region's bound rect.
                            if (corridorExitsLeftChildsTopEdge)
                            {
                                //    _____
                                //    |   |____X
                                //    | L |   |
                                //    |___|   |
                                //          __|__
                                //          |   |
                                //          | R |
                                //          |___|
                                tunnelMeetX = RandomValueBetween(rightChild.BoundingRect.Left + 1, rightChild.BoundingRect.Right);
                                tunnelMeetY = RandomValueBetween(leftChild.BoundingRect.Top + 1, Math.Min(leftChild.BoundingRect.Bottom - 1, rightChild.BoundingRect.Top));
                                DigDownLeftLCorridor(tunnelMeetX, tunnelMeetY);
                            }
                            else
                            {
                                //    _____
                                //    |   |
                                //    | L |
                                //    |___|
                                //      |    _____
                                //      |    |   |
                                //     X|____| R |
                                //           |___|
                                tunnelMeetX = RandomValueBetween(leftChild.BoundingRect.Left + 1, leftChild.BoundingRect.Right);
                                tunnelMeetY = RandomValueBetween(Math.Min(leftChild.BoundingRect.Bottom, rightChild.BoundingRect.Top + 1), rightChild.BoundingRect.Bottom);
                                DigUpRightLCorridor(tunnelMeetX, tunnelMeetY);
                            }
                        }
                    }

                    // TBD: Need to set bounding rect for Special Rooms
                }
                else // Vertical split
                {
                    // child nodes were split vertically, so draw a vertical corridor between them.
                    // 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' or 'Z' shapped corridor to connect them.
                    int minOverlappingX = Math.Max(leftChild.BoundingRect.Left, rightChild.BoundingRect.Left);
                    int maxOverlappingX = Math.Min(leftChild.BoundingRect.Right, rightChild.BoundingRect.Right);
                    if (maxOverlappingX - minOverlappingX &gt;= 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.
                        DigCorridor(corridorX, leftChild.BoundingRect.Bottom, Direction.Up);
                        DigCorridor(corridorX, leftChild.BoundingRect.Bottom + 1, Direction.Down);
                    }
                    else
                    {
                        // They don't overlap enough; dig an 'L' or 'Z' shaped corridor to connect them.
                        // For now, just support 'L' corridors
                        int tunnelMeetX, tunnelMeetY;

                        // The 'L' corridor can come out of the top of the bottom child or the side of the bottom child.
                        bool corridorExitsRightChildsTopEdge = (rand.Next(2) == 0);

                        if (leftChild.BoundingRect.Left &gt; rightChild.BoundingRect.Left)
                        {
                            // Left (upper) child region's bounding rect is to the right of the Right (lower) child region's bound rect.
                            if (corridorExitsRightChildsTopEdge)
                            {
                                //        _____
                                //   X____|   |
                                //    |   | L |
                                //    |   |___|
                                //  __|__
                                //  |   |
                                //  | R |
                                //  |___|
                                tunnelMeetX = RandomValueBetween(rightChild.BoundingRect.Left + 1, Math.Min(rightChild.BoundingRect.Right - 1, leftChild.BoundingRect.Left));
                                tunnelMeetY = RandomValueBetween(leftChild.BoundingRect.Top + 1, leftChild.BoundingRect.Bottom);
                                DigDownRightCorridor(tunnelMeetX, tunnelMeetY);
                            }
                            else
                            {
                                //        _____
                                //        |   |
                                //        | L |
                                //        |___|
                                //  _____   |
                                //  |   |   |
                                //  | R |___|X
                                //  |___|
                                tunnelMeetX = RandomValueBetween(Math.Max(leftChild.BoundingRect.Left + 1, rightChild.BoundingRect.Right + 1), leftChild.BoundingRect.Right);
                                tunnelMeetY = RandomValueBetween(rightChild.BoundingRect.Top + 1, rightChild.BoundingRect.Bottom);
                                DigUpLeftCorridor(tunnelMeetX, tunnelMeetY);
                            }
                        }
                        else
                        {
                            // Left (upper) child region's bounding rect is to the left of the Right (lower) child region's bound rect.
                            if (corridorExitsRightChildsTopEdge)
                            {
                                //    _____
                                //    |   |____X
                                //    | L |   |
                                //    |___|   |
                                //          __|__
                                //          |   |
                                //          | R |
                                //          |___|
                                tunnelMeetX = RandomValueBetween(Math.Max(leftChild.BoundingRect.Right, rightChild.BoundingRect.Left + 1), rightChild.BoundingRect.Right);
                                tunnelMeetY = RandomValueBetween(leftChild.BoundingRect.Top + 1, leftChild.BoundingRect.Bottom);
                                DigDownLeftLCorridor(tunnelMeetX, tunnelMeetY);
                            }
                            else
                            {
                                //    _____
                                //    |   |
                                //    | L |
                                //    |___|
                                //      |    _____
                                //      |    |   |
                                //     X|____| R |
                                //           |___|
                                tunnelMeetX = RandomValueBetween(leftChild.BoundingRect.Left, Math.Min(rightChild.BoundingRect.Left, leftChild.BoundingRect.Right - 1));
                                tunnelMeetY = RandomValueBetween(rightChild.BoundingRect.Top + 1, rightChild.BoundingRect.Bottom);
                                DigUpRightLCorridor(tunnelMeetX, tunnelMeetY);
                            }
                        }
                    }
                }

                // Determine our bounding rectangle (as the union of our child nodes' rectangles).
                dungeonNode.BoundingRect = Rectangle.Union(leftChild.BoundingRect, rightChild.BoundingRect);
            }
            // TBD: Not quite right - "RoomOrCorridorBuilt" more accurate
            dungeonNode.RoomBuilt = true;
        }

        private void DigDownRightCorridor(int tunnelMeetX,int tunnelMeetY)
        {
            // Dig down and right from the specified meeting point until we meet something (note: caller is tasked with gauranteeing that
            // there is something there to meet!)

            DigCorridor(tunnelMeetX, tunnelMeetY+1, Direction.Down);
            DigCorridor(tunnelMeetX+1, tunnelMeetY, Direction.Right);

            // Draw the corner piece
            Cells[tunnelMeetX, tunnelMeetY] = new Cell_Floor();
            Cells[tunnelMeetX-1, tunnelMeetY] = new Cell_Wall();
            Cells[tunnelMeetX, tunnelMeetY - 1] = new Cell_Wall();
            Cells[tunnelMeetX - 1, tunnelMeetY - 1] = new Cell_Wall();
        }

        private void DigUpLeftCorridor(int tunnelMeetX,int tunnelMeetY)
        {
            // Dig up and left from the specified meeting point until we meet something (note: caller is tasked with gauranteeing that
            // there is something there to meet!)
            DigCorridor(tunnelMeetX, tunnelMeetY - 1, Direction.Up);
            DigCorridor(tunnelMeetX - 1, tunnelMeetY, Direction.Left);

            // Draw the corner piece
            Cells[tunnelMeetX, tunnelMeetY] = new Cell_Floor();
            Cells[tunnelMeetX + 1, tunnelMeetY] = new Cell_Wall();
            Cells[tunnelMeetX, tunnelMeetY + 1] = new Cell_Wall();
            Cells[tunnelMeetX + 1, tunnelMeetY + 1] = new Cell_Wall();
        }

        private void DigDownLeftLCorridor(int tunnelMeetX,int tunnelMeetY)
        {
            // Dig down and left from the specified meeting point until we meet something (note: caller is tasked with gauranteeing that
            // there is something there to meet!)
            // Dig the two corridors, but don't draw the actual corner piece where they meet (the DigCorridor algorithm doesn't handle it well).
            DigCorridor(tunnelMeetX, tunnelMeetY + 1, Direction.Down);
            DigCorridor(tunnelMeetX - 1, tunnelMeetY, Direction.Left);

            // Draw the corner piece
            Cells[tunnelMeetX, tunnelMeetY] = new Cell_Floor();
            Cells[tunnelMeetX, tunnelMeetY - 1] = new Cell_Wall();
            Cells[tunnelMeetX + 1, tunnelMeetY - 1] = new Cell_Wall();
            Cells[tunnelMeetX + 1, tunnelMeetY] = new Cell_Wall();

        }

        private void DigUpRightLCorridor(int tunnelMeetX, int tunnelMeetY)
        {
            // Dig up and right from the specified meeting point until we meet something (note: caller is tasked with gauranteeing that
            // there is something there to meet!)
            DigCorridor(tunnelMeetX, tunnelMeetY - 1, Direction.Up);
            DigCorridor(tunnelMeetX + 1, tunnelMeetY, Direction.Right);

            // Draw the corner piece
            Cells[tunnelMeetX, tunnelMeetY] = new Cell_Floor();
            Cells[tunnelMeetX - 1, tunnelMeetY] = new Cell_Wall();
            Cells[tunnelMeetX - 1, tunnelMeetY + 1] = new Cell_Wall();
            Cells[tunnelMeetX , tunnelMeetY + 1] = new Cell_Wall();
        }

        private int RandomValueBetween(int start, int end)
        {
            return start + rand.Next(end - start);
        }

        private void SetCellToWallIfNotFloor(int curX, int curY)
        {
            if (Cells[curX, curY].GetType() != typeof(Cell_Floor))
                Cells[curX, curY] = new Cell_Wall();
        }

        private void DigCorridor(int startX, int startY, Direction directionToDig)
        {
            int curX = startX;
            int curY = startY;

            // Start at (startX, startY) and dig in the specified direction until we hit floor.
            while (Cells[curX, curY].GetType() != typeof(Cell_Floor))
            {
                if (curX == 0 || curX &gt;= 79 || curY == 0 || curY &gt;= 79)
                    return;

                Cells[curX, curY] = new Cell_Floor();
                switch (directionToDig)
                {
                    case Direction.Left:
                        if (Cells[curX, curY - 1].GetType() == typeof(Cell_Floor))
                        {
                            // We hit the upper wall of a room; end-cap the corridor and stop building
                            SetCellToWallIfNotFloor(curX, curY+1);
                            SetCellToWallIfNotFloor(curX-1, curY+1);
                            Cells[curX - 1, curY + 1] = new Cell_Wall();
                            return;
                        }
                        if (Cells[curX, curY + 1].GetType() == typeof(Cell_Floor))
                        {
                            // We hit the lower wall of a room; end-cap the corridor and stop building
                            SetCellToWallIfNotFloor(curX, curY - 1);
                            SetCellToWallIfNotFloor(curX-1, curY - 1);
                            return;
                        }
                        SetCellToWallIfNotFloor(curX, curY - 1);
                        SetCellToWallIfNotFloor(curX, curY + 1);
                        curX--;
                        break;

                    case Direction.Right:
                        if (Cells[curX, curY - 1].GetType() == typeof(Cell_Floor))
                        {
                            // We hit the upper wall of a room; end-cap the corridor and stop building
                            SetCellToWallIfNotFloor(curX, curY + 1);
                            SetCellToWallIfNotFloor(curX+1, curY + 1);
                            return;
                        }
                        if (Cells[curX, curY + 1].GetType() == typeof(Cell_Floor))
                        {
                            // We hit the lower wall of a room; end-cap the corridor and stop building
                            SetCellToWallIfNotFloor(curX, curY - 1);
                            SetCellToWallIfNotFloor(curX + 1, curY - 1);
                            return;
                        }
                        SetCellToWallIfNotFloor(curX, curY - 1);
                        SetCellToWallIfNotFloor(curX, curY + 1);
                        curX++; 

                        break;
                    case Direction.Up:
                        if (Cells[curX - 1, curY].GetType() == typeof(Cell_Floor))
                        {
                            // We hit the right wall of a room; end-cap the corridor and stop building
                            SetCellToWallIfNotFloor(curX+1, curY);
                            SetCellToWallIfNotFloor(curX+1, curY - 1);
                            return;
                        }
                        if (Cells[curX + 1, curY].GetType() == typeof(Cell_Floor))
                        {
                            // We hit the left wall of a room; end-cap the corridor and stop building
                            SetCellToWallIfNotFloor(curX - 1, curY);
                            SetCellToWallIfNotFloor(curX - 1, curY-1);
                            return;
                        }
                        SetCellToWallIfNotFloor(curX - 1, curY);
                        SetCellToWallIfNotFloor(curX + 1, curY);
                        curY--;
                        break;
                    case Direction.Down:
                        if (Cells[curX - 1, curY].GetType() == typeof(Cell_Floor))
                        {
                            // We hit the right wall of a room; end-cap the corridor and stop building
                            SetCellToWallIfNotFloor(curX + 1, curY);
                            SetCellToWallIfNotFloor(curX + 1, curY+1);
                            return;
                        }
                        if (Cells[curX + 1, curY].GetType() == typeof(Cell_Floor))
                        {
                            // We hit the left wall of a room; end-cap the corridor and stop building
                            SetCellToWallIfNotFloor(curX - 1, curY);
                            SetCellToWallIfNotFloor(curX - 1, curY+1);
                            return;
                        }
                        SetCellToWallIfNotFloor(curX - 1, curY);
                        SetCellToWallIfNotFloor(curX + 1, curY);
                        curY++;
                        break;
                }
            }

        }

Um, holy cow that’s a lot of code for today! 🙂

Note that I’ve disabled Special Rooms for now, because I need to think through how the approach here will work for rooms with specific door locations…

Next up: The work week! Hopefully I’ll have time to do some fun stuff too…

smileyNotice anything in the image? :).  I really like the ‘special rooms’ that DCSS (and I’m other RLs) have – it adds something that transcends the “it’s just a bunch of repeating rooms” feeling that I sometimes get from other games.

So – I added the ability to include Special rooms in a level. For now, I’m going to (optionally) just place one special room in a level; I’m interested in the concept of hierarchical special rooms (e.g. imagine a “Castle” Special room, which itself has randomly placed special rooms within it), but that’s an extension for another day.

Creating the room and placing it in the Map was simple enough – what was interesting was how it was injected into the actual BSP tree so that the rest of the dungeon could still be randomly generated around it.  I didn’t want to just hope for a big enough region (chance for failure), and I briefly considered picking an arbitrary leaf node and collapsing it with its siblings until a big enough region was created (could create a massive region, and leave lots of it unused).  Ultimately though, the fun solution to code was to pre-partition the BSP Tree around the Special room, and then use the standard Partitioning code (see my previous post) to split up each of those regions as needed.

Creating the Special room and placing it in the Map

As mentioned above, nothing too complex here.  For now, it’s just created inline in the code; it’ll be easy enough to move to a file-system based approach later on.  The new PartitionDungeon function (and the new PaintRoom supporting function) looks like this:

        private DungeonBSPNode PartitionDungeon()
        {
            // Initialize a few variables.  These'll eventually be removed
            DungeonBSPNode.Map = this;

            // I eventually want to share the random # generator across all objects, so that all that's
            // necessary to completely recreate a particular run is the initial Seed &amp; the list of user inputs/
            DungeonBSPNode.rand = rand;

            // Create the root node;  it covers the entire coordinate space (0.0,0.0) - (1.0,1.0)
            DungeonBSPNode rootNode = new DungeonBSPNode(0.0f, 0.0f, 1.0f, 1.0f);

            // Add Special Room before partitioning
            if (true) // place special room
            {
                IncludeSpecialRoom = true; // Used in the AddRoom function to ensure we don't add a new Room over the Special Room.
                xSpecialRoomStart = 20;
                ySpecialRoomStart = 20;
                xSpecialRoomEnd = xSpecialRoomStart + 18;
                ySpecialRoomEnd = ySpecialRoomStart + 19;

                // Add the room.  Temporarily just doing here; will move to file-based model later.
                int[,] roomCells = {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, },
                                    { 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, },
                                    { 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, },
                                    { 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, },
                                    { 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, },
                                    { 0, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 0, },
                                    { 0, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 0, },
                                    { 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, },
                                    { 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, },
                                    { 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, },
                                    { 0, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 0, },
                                    { 0, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 0, },
                                    { 0, 1, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 1, 0, },
                                    { 0, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 1, 0, },
                                    { 0, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 0, },
                                    { 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, },
                                    { 0, 0, 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, },
                                    { 0, 0, 0, 0, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 0, 0, 0, 0, },
                                    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }};

                // Add the room to the Map.
                PaintRoom(xSpecialRoomStart, ySpecialRoomStart, roomCells);

                // Partition the remaining dungeon layer around the placed room
                rootNode.PartitionAround(xSpecialRoomStart, ySpecialRoomStart, xSpecialRoomEnd, ySpecialRoomEnd);
            }
            else
            {
                // No special room
                rootNode.Partition();
            }
            return rootNode;
        }

        private void PaintRoom(int startX, int startY, int[,] roomCells)
        {
            for (int y = 0; y &lt; 19; y++)
                for (int x = 0; x &lt; 18; x++)
                {
                    switch (roomCells[y, x])
                    {
                        case 3:
                            Cells[startX + x, startY + y] = new Cell_Door();
                            break;
                        case 2:
                            Cells[startX + x, startY + y] = new Cell_Floor();
                            break;
                        case 1:
                            Cells[startX + x, startY + y] = new Cell_Wall();
                            break;
                    }
                }
        }

Nothing too complex; only thing of note is that “rootNode.Partition” has been replaced with a new function call “rootNode.PartitionAround”, which is passed the (Map-space) coordinates of the Special room.  The PartitionAround function handles partitioning the BSP tree around that space.

Pre-partitioning the BSP Tree

This was fun to write; it just forcibly creates partitions of the appropriate size & location around the special room, and then recursively splits those up as needed.  The code handles cases where the special room is in the middle of the room as well as cases where it abuts one or more edges of the Map.

  public void PartitionAround(int x1, int y1, int x2, int y2)
        {
            double startX = (double)x1 / Map.MapWidth;
            double startY = (double)y1 / Map.MapHeight;
            double endX = (double)x2 / Map.MapWidth;
            double endY = (double)y2 / Map.MapHeight;

            // Create partitions around the carved out space, and don't partition the carved out space further

            // Here is how we create the partitions around the carved out space (marked with " XX ").  The #s
            // represent the splits...
            // ________________________
            // |                      |
            // |                      |
            // |                      |
            // |____1_________________|
            // |        |    |        |
            // |        | XX 4        |
            // |        |____|___3____|
            // |        |             |
            // |        2             |
            // |        |             |
            // |________|_____________|

            // Do first split (#1) horizontally along the top edge of the carved out space
            if (startY == TopEdge)
                Left = null;    // Carved out partition abuts the TopEdge, so no need to create a 'Left' part
            else
            {
                Left = new DungeonBSPNode(LeftEdge, TopEdge, RightEdge, startY);
                if (WeShouldSplit(startY - TopEdge))
                    Left.Partition();
            }
            Right = new DungeonBSPNode(LeftEdge, startY, RightEdge, BottomEdge);

            // Do second split (#2) vertically along the left edge of the carved out space
            if (startX == LeftEdge)
                Right.Left = null;    // Carved out partition abuts the LeftEdge, so no need to create a 'Left' part
            else
            {
                Right.Left = new DungeonBSPNode(LeftEdge, startY, startX, BottomEdge);
                if (WeShouldSplit(startX - LeftEdge))
                    Right.Left.Partition();
            }
            Right.Right = new DungeonBSPNode(startX, startY, RightEdge, BottomEdge);

            // Do third split (#3) horizontally along the bottom edge of the carved out space
            if (BottomEdge == endY)
                Right.Right.Right = null;    // Carved out partition abuts the BottomEdge, so no need to create a 'Right' part
            else
            {
                Right.Right.Right = new DungeonBSPNode(startX, endY, RightEdge, BottomEdge);
                if (WeShouldSplit(BottomEdge - endY))
                    Right.Right.Right.Partition();
            }
            Right.Right.Left = new DungeonBSPNode(startX, startY, RightEdge, endY);

            // Do fourth split (#4) vertically along the right edge of the carved out space
            if (RightEdge == endX)    // Carved out partition abuts the RightEdge, so no need to create a 'Right' part
                Right.Right.Left.Right = null;
            else
            {
                Right.Right.Left.Right = new DungeonBSPNode(endX, startY, RightEdge, endY);
                if (WeShouldSplit(RightEdge - endX))
                    Right.Right.Left.Right.Partition();
            }

            // Finally, partition the carved out space (and don't further partition it)
            Right.Right.Left.Left = new DungeonBSPNode(startX, startY, endX, endY);
        }

And that’s it!

Next up: connecting rooms.

bspdungeonMy general approach for my 70DRL is “get functional areas to a ‘good enough’ state that I can build other functional areas that depend on them.” With that stated, my first foray into RL’ing was a focus on BSP-based dungeon generation, because it’s quick and easy, and generates acceptable or better maps. There are a number of resources out there for dungeon generation approaches; my approach is based on JICE’s “simple method” summarized very nicely here.

nb: BSP Dungeon generation is actually a good place to start – 99% of my coding over the last few years has been in web dev (ASP.Net, etc), and I need to dust off the client cobwebs. I spent enough time with BSP trees back in my 3D days that I was able to put together a basic BSP tree class and a “good enough” room generation algorithm on top of it to generate a dungeon within which any  adventurer would surely be happy getting killed over and over again.

As an aside – I’m okay with the number of rooms which touch edges – it looks odd now, but my plan is to try merging all rooms that abut; the hope being that it creates some interesting looking architecture.  If not, then it’s easy enough to play with the variables in the source to reduce the sizes…

I’m not worrying about the architecture for the overall game just yet; right now I’m just trying to get my bearings again.  So, with that said, here’s a quick blurb about how this works:

Room Generation Workflow

I have two structures during generation that represent the dungeon level – (1) a Map class (basically a 2D array of Cells), and (2) a BSP tree (which partitions the space and creates gauranteed non-overlapping regions in which rooms are created).  The BSP tree essentially overlays the map (see the image above; the BSP partitions are rendered as red lines).

As of now, I regenerate the level any time a key is pressed (hey, just testing right now – promise the final game won’t work that way 😉 ).  The basic room generation flow right now is as follows:

1) Fill the map with “Granite”

2) Partition the map top-down using a BSP tree.  Each leaf node in the tree will represent a non-overlapping region of guaranteed minimum size (we’ll put rooms in these regions).  More on this later.

3) Iterate over the leaf nodes in the BSP tree, and drop a random-sized room in the region represented by each leaf node

Here’s the current function to Generate the Level:

        public void GenerateLevel()
        {
            Cells = new Cell[MapWidth, MapHeight];

            // Fill with Granite
            PaintCellRectangle(0, 0, MapWidth - 1, MapHeight - 1, new Cell_Granite(), true);

            // Create BSP tree to partition floor randomly (but w/o overlaps)
            partitionedTree = PartitionDungeon();

            // now that we have partitioned the dungeon into non-overlapping regions, create rooms in each "leaf" region
            // We do this by telling the partitioned dungeon tree to find all "leaf" nodes (e.g. those at the bottom of
            // the tree which have not been partitioned into smaller regions, and calling our "AddRoom" function with
            // each leaf node's coordinates.
            partitionedTree.EnumerateLeafNodes(new AddRoomDelegate(AddRoom));
        }

And here’s the PartitionDungeon function, which actually creates the partitioned tree (not much here – only thing of note is that the initial node covers the full normalized space):

        private DungeonBSPNode PartitionDungeon()
        {
            // Initialize a few variables.  These'll eventually be removed
            DungeonBSPNode.Map = this;

            // I eventually want to share the random # generator across all objects, so that all that's
            // necessary to completely recreate a particular run is the initial Seed &amp; the list of user inputs/
            DungeonBSPNode.rand = rand;

            // Create the root node;  it covers the entire space (0.0,0.0) - (1.0,1.0)
            DungeonBSPNode rootNode = new DungeonBSPNode(0.0f, 0.0f, 1.0f, 1.0f);

            // Do the actual partitioning.
            rootNode.Partition();

            return rootNode;
        }

Dungeon BSP Tree

Jice already gave a good description of how this algorithm works at a conceptual level, so I strongly recommend hitting up his (linked above) post if you’re new to BSP trees.  Here’s the DungeonBSPNode class in its entirety; those of you that might be struggling with BSP trees, take heart that the actual ‘meat’ of the class (the Partition() function) is very straightforward.

Note that I opted for normalized floating point coordinates during the partitioning process (I then convert into the Map’s coordinate space when creating rooms).  Presumably the iPhone is sufficiently powered for this to be okay (and I like the purity of floating point :)), but I may need to revisit this later on.

DUNGEONBSPNode.cs:

using System;
using System.Drawing;
using System.Diagnostics;

namespace iRogue
{
    public class DungeonBSPNode
    {
        // Orientation - Identifies which axis the Node is split upon.
        private enum Orientation { Horizontal, Vertical };

        ///
        /// Constructor.
        ///
        public DungeonBSPNode(double startX, double startY, double endX, double endY)
        {
            LeftEdge = startX;
            RightEdge = endX;
            TopEdge = startY;
            BottomEdge = endY;

            NodeWidth = RightEdge - LeftEdge;
            NodeHeight = BottomEdge - TopEdge;
        }

        ///
        /// Partitions (splits) this node into two halves, and then creates child nodes for
        /// each half and recursively partitions both of them (if they are not 'too small').
        ///
        public void Partition()
        {
            // Choose the axis along which we'll partition (split) this node.  If this is a very
            // narrow node in one axis, then favor the other axis in order to minimize long corridor-like rooms.
            if (NodeWidth / NodeHeight &gt; MaxPartitionSizeRatio)
                SplitOrientation = Orientation.Horizontal;
            else if (NodeHeight / NodeWidth &gt; MaxPartitionSizeRatio)
                SplitOrientation = Orientation.Vertical;
            else
                SplitOrientation = (r.Next(2) == 1) ? Orientation.Horizontal : Orientation.Vertical;

            // Split the Node.
            if (SplitOrientation == Orientation.Horizontal)
            {
                // Pick the location along the XAxis (between the LeftEdge and RightEdge) at which we will split.
                SplitLocation = LeftEdge + HomogenizedRandomValue() * NodeWidth;

                // Create our two child nodes
                Left = new DungeonBSPNode(LeftEdge, TopEdge, SplitLocation, BottomEdge);
                Right = new DungeonBSPNode(SplitLocation, TopEdge, RightEdge, BottomEdge);

                // Partition child nodes if either is not yet too small
                if (WeShouldSplit(SplitLocation - LeftEdge))
                    Left.Partition();
                if (WeShouldSplit(RightEdge - SplitLocation))
                    Right.Partition();
            }
            else // Vertical split
            {
                // Pick the location along the YAxis (between the TopEdge and BottomEdge) at which we will split.
                SplitLocation = TopEdge + HomogenizedRandomValue() * NodeHeight;

                // Create our two (Left = upper and Right = lower) child nodes
                Left = new DungeonBSPNode(LeftEdge, TopEdge, RightEdge, SplitLocation);
                Right = new DungeonBSPNode(LeftEdge, SplitLocation, RightEdge, BottomEdge);

                // Partition child nodes if either is not yet too small
                if (WeShouldSplit(SplitLocation - TopEdge))
                    Left.Partition();
                if (WeShouldSplit(BottomEdge - SplitLocation))
                    Right.Partition();
            }
        }

        private bool WeShouldSplit(double partitionSize)
        {
            // For variety, we don't split ~10% of the partitions which are small.  This allows creation of
            // a few slightly larger rooms in the dungeon (particularly useful later one when we're trying to place 'special' rooms)
            if (partitionSize &gt; SmallestPartitionSize &amp;&amp; partitionSize &lt; SmallestPartitionSize * 2.0 &amp;&amp; r.NextDouble() &lt;= .1)
                 return false;
            // If the partition is bigger than the "Smallest Partition Size" value, then split.
            return partitionSize &gt; SmallestPartitionSize;
        }

        ///
        /// Returns a random absolute normalized value (between 0.0 and 1.0).  Allows homogenization
        /// of the partitions to be controlled
        ///
        ///
        private double HomogenizedRandomValue()
        {
            return 0.5 - (r.NextDouble() * HomogeneityFactor);
        }

        public void EnumerateLeafNodes(AddRoomDelegate addRoomDelegate)
        {
            // If this node was partitioned, then recurse into our child nodes; otherwise, call the callback function
            if (Left != null || Right != null)
            {
                if (Left != null)
                    Left.EnumerateLeafNodes(addRoomDelegate);
                if (Right != null)
                    Right.EnumerateLeafNodes(addRoomDelegate);
            }
            else
                addRoomDelegate(LeftEdge, TopEdge, RightEdge, BottomEdge);
        }

        ///
        /// Test code to Render the BSP tree to a graphic context.  Used to validate the BSP tree code.
        ///
        ///

        public void Render(Graphics gr)
        {
            float w = Map.MapWidth * 8;
            float h = Map.MapHeight * 8;
            gr.FillRectangle(Brushes.Black, (float)LeftEdge * w + 10, (float)TopEdge * h + 10, (float)(RightEdge - LeftEdge) * w, (float)(BottomEdge - TopEdge) * h);
            gr.DrawRectangle(Pens.Red, (float)LeftEdge * w + 10, (float)TopEdge * h + 10, (float)(RightEdge - LeftEdge) * w, (float)(BottomEdge - TopEdge) * h);

            if (Left != null)
                Left.Render(gr);
            if (Right != null)
                Right.Render(gr);
        }

        // The Edges of this Node in the Map.  Note that we store all Edge values and the SplitLocation
        // in absolute (as compared to to relative) normalized (0.0-1.0) coordinates.  We don't convert
        // to actual 'dungeon ints' until we're placing rooms.
        // TBD: Move to floats?  Move to Rect?
        // TBD: Do a pass and see if it cleans up any math if I move to relative coordinates &amp; just calculate on the way 'down' the tree...
        public double LeftEdge;
        public double RightEdge;
        public double TopEdge;
        public double BottomEdge;

        public double NodeWidth;
        public double NodeHeight;

        // Whether we're Split horizontally or Vertically
        // TBD: Do I need to store this in the node, or can it just be local to the Partition function?
        private Orientation SplitOrientation;

        // The absolute normalized location at which this Node will be split.  Will be a value between
        // LeftEdge &amp; RightEdge, or TopEdge &amp; BottomEdge, depending on SplitOrientation's value.
        // TBD: Do I need to store this in the node, or can it just be local to the Partition function?
        public double SplitLocation;

        // Our Left &amp; Right Child Nodes.  "Left" and "Right" refer to the binary tree node positions, and
        // apply to both horizontal and vertical orientations (in the latter case, "Left" --&gt; "Up" and
        // "Right" --&gt; "Down".
        public DungeonBSPNode Left { get; set; }
        public DungeonBSPNode Right { get; set; }

        // TBD: Want our random factor to be completely reproducible.  An entire Dungeon run should be recreatable
        // just from the initial Random Seed and the list of user inputs.
        static public Random r;

        // The smallest size that a partition can get.  In absolute terms, so "0.1" would equate to 1/10th the
        // size of the map.
        /// TBD: Make SmallestPartitionSize something that is set by the caller to allow different dungeon generation schemas.
        static private double SmallestPartitionSize = .15;

        // When choosing which axis to split a Node on, we want to optimize the number of "squarish"
        // rooms, and minimize the number of "long corridor rooms."  To do this, when splitting a Node,
        // we look at the ratio of Width to Height, and if it crosses the MaxPartitionSizeRatio threshold
        // in either axis, then we forcibly split on the *other* axis.
        /// TBD: Make MaxPartitionSizeRatio something that is set by the caller to allow different dungeon generation schemas.
        static private double MaxPartitionSizeRatio = 1.5f;

        // The homogeneityFactor determines how "common" split partitions are.  The value is between 0.0 and 0.5.  A small value (e.g. .1)
        // creates a Dungeon with similar size partitions; A large value (e.g. 0.4) creates a Dungeon
        // with more varied sized partition.  The balance is finding the right number - too small a value == all partitions are the
        // same; too large a value == higher likelihood of long narrow "corridor rooms"
        /// TBD: Make HomogeneityFactor something that is set by the caller to allow different dungeon generation schemas.
        static private double HomogeneityFactor = 0.25;

        // A pointer back to our Map.  Used to generate rooms
        static public Map Map;
    }
}

Finally; Outputting Rooms

Using the code above, we are able to partition the dungeon map into a collection of gauranteed non-overlapping spaces; now, we fill those spaces with random-sized rooms.

Visually, I dislike small (eg 2×2) rooms, so we set a minimum ideal room size (note that the size includes space for the walls).

There’s a lot of code below, but that’s mostly just because I’m being verbose with variables to make it clearer.

Of interest – during the conversion to Map coordinates, we round the floating point source values for the Start coordinates up (using Math.Ceiling())  and the source values for the End coordinates down (using just an (int) cast) to ensure that we don’t overlap or leave holes on the edges between regions.

        // Create a room in the area specified by the regionNode.
        public void SquareRoomGenerator(DungeonBSPNode dungeonRegion)
        {
            int MinIdealRoomSize = 4;

            // Convert from absolute normalized coordinates (0.0-1.0) to Map coordinates (0-(MapWidth-1), 0-(MapHeight-1))
            int xRegionStart = (int)Math.Ceiling((dungeonRegion.LeftEdge * (MapWidth - 1)));
            int yRegionStart = (int)Math.Ceiling((dungeonRegion.TopEdge * (MapHeight - 1)));
            int xRegionEnd = (int)((dungeonRegion.RightEdge * (MapWidth - 1)));
            int yRegionEnd = (int)((dungeonRegion.BottomEdge * (MapHeight - 1)));
            int regionWidth = xRegionEnd - xRegionStart;
            int regionHeight = yRegionEnd - yRegionStart;

            int roomWidth = RandomValueBetween(Math.Min(MinIdealRoomSize, regionWidth), regionWidth);
            int roomHeight = RandomValueBetween(Math.Min(MinIdealRoomSize, regionHeight), regionHeight);

            int xRoomStart = xRegionStart + rand.Next(regionWidth - roomWidth);
            int yRoomStart = yRegionStart + rand.Next(regionHeight - roomHeight);

            // "Paint" the room into the Map
            PaintCellRectangle(xRoomStart, yRoomStart, xRoomStart + roomWidth, yRoomStart + roomHeight, new Cell_Wall(), true);
            PaintCellRectangle(xRoomStart + 1, yRoomStart + 1, xRoomStart + roomWidth - 1, yRoomStart + roomHeight - 1, new Cell_Floor(), true);
        }

        public void PaintCellRectangle(int xStart, int yStart, int xEnd, int yEnd, Cell cell, bool forceDraw)
        {
            for (int y = yStart; y <= yEnd; y++)
                for (int x = xStart; x <= xEnd; x++)
                {
                    if (forceDraw || Cells[x, y] == null || Cells[x, y].GetType() == typeof(Cell_Granite))
                        Cells[x, y] = cell;
                }
        }

nb: I have no idea how best to support zip-file attachments with a Live Journal blog.  I want to post the source code, but don’t know the combination cheapest-easiest-best-integrated solution…

Next up: supporting special rooms (and pre-partitioning the BSP tree to work around them).