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 & 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 < 19; y++)
                for (int x = 0; x < 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.

Advertisements