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 & 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 > MaxPartitionSizeRatio)
                SplitOrientation = Orientation.Horizontal;
            else if (NodeHeight / NodeWidth > 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 > SmallestPartitionSize && partitionSize < SmallestPartitionSize * 2.0 && r.NextDouble() <= .1)
                 return false;
            // If the partition is bigger than the "Smallest Partition Size" value, then split.
            return partitionSize > 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 & 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 & RightEdge, or TopEdge & 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 & 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" --> "Up" and
        // "Right" --> "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).

Advertisements