• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
nesseggman

[SOLVED] Cutting up rectangles -- RNG giving predictable results?

0 posts in this topic

(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.

Edited by nesseggman
1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0