(tl;dr: I was doing some BSP division of a parallelogram and getting undesired results, and since this was my first time really utilizing recursion in a meaningful way, I thought the problem was in my implementation... turns out it was just my RNG was giving the undesired results only when the program was run at normal speed, rather than stepped through. Declaring the System.Random object with program scope, rather than within the function using it, solved this... yay X_X)

I am attempting to cut a rectangle into two parts of random size at random direction (either horizontally or vertically). Then take each of those child rectangles and cut them... and keep doing this until the rectangles are "too small to cut."

I have a rectangle class that holds the minimum x and y in the rectangle, as well as its width and height (so all four corners can be calculated with this).

The plan is the create an array of something like x & y coordinates and "fill" each of the final children into it, to create "areas" to be used in random dungeon generation. Right now I'm just trying to get the array to fill up with numbers that will display as rectangles.

I'm pretty sure the rectangles are dividing properly, the problem is getting the final rectangles into the array. I've been storing all the rectangles in a list, and then checking through each rectangle in the list. If it has no children, it will then search through every 'node' in the array, and if it falls within the rectangle, it will assign it that rectangle's index number from the list (so that each rectangle now is uniquely numbered and "graphed" in the array).

I don't think I'm properly extracting the smallest of the children from the array... either that or my rectangles are not actually being created properly.

I've gone through step-by-step, and checked all the variables at the end. There are so many rectangles I'm not sure really what to look for. The final display also seems to always be cut horizontally or vertically, even though stepping through, there are cuts of both directions aplenty.

I've been at this for a couple days now, and this is the best I could come up with:

    class Program
    {
        public static int DUNGEONSIZE = 8;
        public static int MINSIZE = 5;

        static void Main(string[] args)
        {
            int borders = DUNGEONSIZE * MINSIZE; // create the dungeon's width and height
            int[,] dungeonSections = new int[borders, borders]; // create an array to store leafs
            int[,] dungeonMap = new int[borders, borders]; // create an array to store map (floor, wall, hall, etc.)
            List<Leaf> leafset = new List<Leaf>();

            Leaf trouble = new Leaf();


            MakeLeaf(trouble, 0, 0, borders, borders);

            Split(trouble, leafset);

            for (int i = 0; i < leafset.Count; i++)
            {
                if (leafset[i].firstChild == null && leafset[i].secondChild == null) /* if the leaf has no children,
                                                                                      * label every point inside of it
                                                                                      * with its index. */
                {
                    for (int ii = 0; ii < borders; ii++)
                    {
                        for (int jj = 0; jj < borders; jj++)
                        {
                            if (ii >= leafset[i].minx &&
                                jj >= leafset[i].miny &&
                                ii <= (leafset[i].minx + leafset[i].width) &&
                                jj <= (leafset[i].miny + leafset[i].height))
                            {
                                dungeonMap[ii, jj] = i;
                            }
                        }
                    }
                }
            }

            for (int i = 0; i < 41; i++)
            {
                Console.Write(".");
            }
            Console.WriteLine();

            for (int i = 0; i < borders; i++)
            {
                Console.Write(".");
                for (int j = 0; j < borders; j++)
                {
                    char x = (char)dungeonMap[i, j];
                    Console.Write(x);
                }
                Console.WriteLine();

            }


            Console.ReadLine();

        }

        //Split will take a leaf and continue to split it until no more splits can be made. It stores the children in a list.
        public static void Split(Leaf leaf, List<Leaf> list)
        {
            if (leaf.firstChild != null) { return; } // abort if already split
            if (leaf.height <= (MINSIZE * 2) || leaf.width <= (MINSIZE * 2)) { return; } // abort if too small

            Random rnd = new Random();
            bool horiz = (rnd.Next(2) > 0) ? true : false; //decide if split is horiz or vert

            leaf.firstChild = new Leaf(); // initialize leaf children
            leaf.secondChild = new Leaf();

            if (horiz) // split into children
            {
                int cut = rnd.Next(leaf.width / 3, leaf.width - leaf.width / 3);
                if (cut < MINSIZE) { cut = MINSIZE; }
                if (cut > leaf.width - MINSIZE) { cut = leaf.width - MINSIZE; }
                MakeLeaf(leaf.firstChild, leaf.minx, leaf.miny, cut, leaf.height);
                MakeLeaf(leaf.secondChild, leaf.minx + cut, leaf.miny, leaf.width - cut, leaf.height);
            }
            else
            {
                int cut = rnd.Next(leaf.height / 3, leaf.height - leaf.height / 3);
                if (cut < MINSIZE) { cut = MINSIZE; }
                if (cut > leaf.height - MINSIZE) { cut = leaf.height - MINSIZE; }
                MakeLeaf(leaf.firstChild, leaf.minx, leaf.miny, leaf.width, cut);
                MakeLeaf(leaf.secondChild, leaf.minx, leaf.miny + cut, leaf.width, leaf.height - cut);
            }

            list.Add(leaf.firstChild); // adds the children to the list
            list.Add(leaf.secondChild);

            Console.WriteLine("Children Made!!");

            Split(leaf.firstChild, list); // attempt to split children, if possible
            Split(leaf.secondChild, list);
        }


        //MakeLeaf will set a leaf's variables.
        public static void MakeLeaf(Leaf leaf, int minx, int miny, int width, int height)
        {
            leaf.minx = minx;
            leaf.miny = miny;
            leaf.width = width;
            leaf.height = height;
        }

    }

    class Leaf
    {
        public int minx;
        public int miny;
        public int width;
        public int height;
        public Leaf firstChild;
        public Leaf secondChild;
    }

Sorry if it's confusing... I am a noob.

I really don't know how to 'debug' this and figure out what is going wrong ._. I can't tell where exactly it is messing up. Going step-by-step, once I get to the for-for-for loop with the list and array, I don't even know what I'm looking for anymore.

EDIT1:

You get some weird chars if you use the char as is... I've been adding 65 to it to get roman letters. At least I'm always making a 40x40 square now. But it's always giving me either only horizontal splits or vertical splits in the visual representation.

I think it has something to do with the check for them being 'too small' (when it decides to split). I had it do the same check before saving the children to the list, so that it only saves the children who will fail the check... then I stopped the program at the array distribution and all the leafs in the list had a height of 40.

But I'm not sure what's wrong with it... I've tried changing it to other things and it either crashes or gives a similar result? I just want it so that it will refuse to split anything with a width or height less than 2(minsize).

EDIT2:

Okay, so I finally decided to pull out the big guns... I got couple sheets of paper out and mapped out the square it creates, as well as writting down every single leafs's four variables in a tree... marking the "too small to cut" ones on my graph.

Normally I woudl skip to certain parts of the code and check the variables... or step through to see if it was creating stuff right, then exit the program when it was working properly.

Well, I went step by step through the ENTIRE THING this time. It cut up the square perfectly into nice random areas, looked really good on my graph that I drew. Then I watched it go through the three embedded for loops to assign the leafs' index number to their contained coordinates. After it did leaf 4 and leaf 7 properly, skipping all the proper leafs, I skipped to the drawing part. I checked the array dungeonMap and compared it with my coordinates and graph I wrote. Everything was perfect! I started to think.... there's no way the drawing part is wrong... I watched it draw character by character... I realized it was doing it right.

I let the program run its course and lo and behold, it drew the right thing.

I was baffled. When I watched parts of the program, they responded perfectly and did what they were supposd to. When I watched the ENTIRE PROGRAM step-by-step, it worked perfectly and even gave the desired results.

But when I just run the build without pausing or anything, it doesn't give the desired results...

My head felt like it was going to explode.

Then I remember reading in the C# documentation on msdn about System.Random... and it said something about how if the numbers are generated too quickly/close to one another (since it's using the system clock), you can get predictable results.

So I thought... maybe when the program is running at "full speed," it's only generating all true or all false (different depending on run time of the program) for the "horiz" boolean in the Split function.

Every time I step through the program slowly, it creates everything perfeclty and provides desired results. It only gives the stupid results when I run the build normally.

This would also explain why even when I only stored 'baby' leafs in the list (that's what I call ones that can no longer be split) it was still only storing ones with 40 for width or height (because it was only cutting in one direciton, and eventually they'd all have the opposite edge be less than MINSIZE*2)...

I'm going to go try to research how to counter this (like I said, I'm a noob!) and add something to see if I can make it more random and see if it works. If anyone knows a solution, feel free to post it here, since this topic is already here and all. After I try it, I'll see if it works, and let everyone know.

Sorry to be such a pain!

EDIT3: I had it write the value of horiz to the console after every time it decided it... it was either always true or always false. I have a feeling this is the problem. MSDN's documentation for System.Random class is not helping... it just says to avoid this, only use one Random, which I'm already doing. EDIT4: Oh, now that I think about it, I guess I'm technically creating new Randoms every iteration/recursion....

EDIT5: Solved!! That was indeed the problem. I just declared the Random rnd outside of the function and now it works perfectly. Lesson learned, if you're going to be using a lot of RNG, try to make sure you're only creating one System.Random.

Wow. This took me days to figure out because I was looking it all the wrong places.

Well, I'll leave this here for anyone who might be able to learn from it.