September 26, 2014

Dungeon Generator


Look! A Dungeon Generator. Once you have played enough dungeon crawlers, you just have to build your own dungeon crawler (#amiright?!). Since, my current fascination is web development (read: Dabbling, look at that neat calculator), I figured I might as well make a web game. Playing Heroes of Loot might have had something to do with this.

A procedural generated fast-paced infinite dungeon crawler is what I have in mind. Hence, first off, I need a neat Dungeon Generating algorithm. You know... those rooms and corridors. 


I looked at a few algorithm, and finally settles with the BSP (Binary Space Partitioning) Trees method. Here, have a look at the algorithm. The link explains the overall idea pretty well, aye? I implemented it in Javascript.


Edit: Hosted on http://toweroffun.bitballoon.com/ (Didn't add a preloader, because I didn't know how to use states when I made this).
Also look at this - Tower of Fun - My new hobby project!

Getting right to it


Docs:

Write a default index.html and place a div for the Phaser Engine to start in.  dungeon.js hosts the Dungeon object that actually houses the dungeon generation algorithm. main.js houses the Phaser engine code.

It would be wise through go through some Phaser documentation that I linked on this Tower of Fun post before delving into main.js.

Before we head further, I really hope you have read this - Dungeon Generation using BSP
OK! dungeon.js defines Dungeon, the object that does all the fancy procedural generation. If you looked at the source, it has these.
map
A 2D array that stores the integer indices for tile types. Here we have 3 types of tiles. Logically, we’d only need 2 types of tiles - walkable and non-walkable. But, I just wanted to extend it to this: * 0 - non-walkable tiles (grey in the jsFiddle above) * 1 - walkable room tile (green) * 2 - walkable corridor tile (blue)
map_size
The size of the tile grid, say 32x32
rooms
A list that stores the rooms that we would generate
stats
An object to store results, like number of rooms and some config parameters that you’ll see below.
tree
To BSP the grid, we need to store the “sub-Boxes” in a tree. That’s what this is for.
stack
Each time we create child nodes on the tree, ie: new sub-Boxes in a big Box, we push information about that pair onto the stack. Later on, once all rooms are built, and it’s time to place the corridors, we pop each pair of this stack and “join” the rooms
gid
Updates each time a new tree node is created. I wanted each node to have a unique ID, and the tree traversal is recursive, hence, keeping a global ID tracker was useful.
minRoomSize
Minimum Room Size. What did you think min stood for?
minSizeFactor
Alright, this one isn’t intuitive as the last one. This states the minimum ratio in which a box can be split into 2 smaller boxes. This ensures not having really small boxes or really big boxes.

The main function in the Dungeon object is Dungeon.generate(). It starts of by clearing all variables and the setting the map array to default values (all to 0 - walls). Next, a root node is create in the tree. The root node will be the biggest “Box”. The root Box is kept slightly smaller than the map as we would want the map to be fully enclosed, ie: no walkable tile touches the edge of the map.
        var X=1;
        var Y=1;
        var W=this.map_size-2;
        var H=this.map_size-2;

        // Root Node
        var rootBox={};
        rootBox.x = X;
        rootBox.y = Y;
        rootBox.w = W;
        rootBox.h = H;

        this.tree[this.gid]=rootBox;
        this.gid++;

        // Build Tree
        this.buildTree(1);
The root Box gets added to Dungeon.tree and the Dungeon.gid is incremented. Dungeon.buildTree() is called. This is going to recursively try to split the root Box into smaller boxes, until it hits the limit minRoomSize, ie: child boxes would not be able to house a room of minRoomSize.
Look at the Dungeon.buildTree() method:
        // Select a split - Horizontal((0) or Vertical(1)
        // This allows you to have a valid splitType oppurtunity
        var splitType=1;
        if(this.minSizeFactor*W < this.minRoomSize){
            // no space for splitting vertically, try Horizontal
            splitType = 0;
        } else if (this.minSizeFactor*H < this.minRoomSize){
            // no space for splitting vertically, try Vertical
            splitType = 1;
        } else {
            // random - Both H and V are valid splits
            if(Math.random()>0.5){splitType=0;}
        }
When splitting a parent Box, we have a choice to split vertically or horizontally. Once that choice is made, two child Boxes will be created. For a vertical split,
            roomSize = this.minSizeFactor*W;
            if(roomSize >= this.minRoomSize){
                var w1 = randPlus(roomSize, (W-roomSize));
                var w2 = W - w1;

                var box1={};
                box1.x = X;
                box1.y = Y;
                box1.w = w1;
                box1.h = H;
                box1.alignment = 'V';

                var box2={};
                box2.x = X+w1;
                box2.y = Y;
                box2.w = w2;
                box2.h = H;
                box2.alignment = 'V';

                ok++;
            }
Similarly, child boxes would be created if the split was horizontal. Finally, if a split was truly done, then the child nodes will be added to the tree under the parent node that they were split from.
            this.tree[this.gid]=box1;
            this.tree[root].L = this.gid;
            this.gid++;

            this.tree[this.gid]=box2;
            this.tree[root].R = this.gid;
            this.gid++;

            this.stack.push([this.tree[root].L,this.tree[root].R]);

            this.buildTree(this.tree[root].L);
            this.buildTree(this.tree[root].R)
You can see that the Dungeon.gid will be unique for every box. The pair of ids will be pushed onto the Dungeon.stack for later use. Now, that we have child boxes, they grow up to be parents and we call Dungeon.buildTree on them too.
When all boxes are discovered and a full Dungeon.tree is ready, we carve out rooms in the leaf nodes in that tree. A leaf node is easily identified by the lack of child nodes. Room objects are created with position and dimension properties. The ID of the Box is copied over to the room. Once all the rooms are conceived, the Dungeon.map is updated, ie: the indices on the map that overlap the rooms are flipped to 1 (walkable).
        // Next, build rooms in the leaf nodes of the tree
        for (var nodeID in this.tree){
            var node = this.tree[nodeID];
            if(node.hasOwnProperty("L")){continue;}
            var room = {};
            room.w = randPlus(this.minRoomSize, node.w);
            room.h = randPlus(this.minRoomSize, node.h);
            room.x = node.x + Math.floor((node.w-room.w)/2);
            room.y = node.y + Math.floor((node.h-room.h)/2);
            room.center={};
            room.center.x = Math.floor(room.x + room.w/2);
            room.center.y = Math.floor(room.y + room.h/2);
            room.id=nodeID;
            this.rooms.push(room);
            this.tree[nodeID].hasRoom = nodeID;
        }
        // Assign the rooms to the Map
        for (var i=0; i<this.rooms.length; i++) {
            var r = this.rooms[i];
            console.log("Room: ",[r.x,r.y,r.w,r.h]);
            for (var x = r.x; x<(r.x + r.w) ; x++) {
                for (var y = r.y; y<(r.y + r.h); y++) {
                    this.map[x][y] = 1;
                }
            }
        }
        // Build Corridors
        this.joinRooms();
Cool, huh? We are almost done. At this point we have rooms across the map, that aren’t connected to each other. This was precisely what the object was all along - to generate a bunch of disconnected rooms or varying sizes. Next up is the easy part - joining them.
Since, we already have a Dungeon.stack that had stored id pairs in the order of creation, we simply have to pop one pair at a time and “join” them. That’s where the Dungeon.joinRooms function comes in. Here, we pick a random thickness for the corridor and connect the two Boxes via a simple rectangle. Dimensions for horizontal or vertical corridors are calculated and they are placed connecting the two centers of the Boxes. Only the tiles on Dungeon.map with 0 are flipped to 2.
And, done. Dungeon.buildTree finally sets the results in Dungeon.stats. The map array is retrieved via the function Dungeon.getMap().

In main.js, the Dungeon object is used.
var MAP_SIZE = 32;
Dungeon.generate(MAP_SIZE);
Dungeon.print();
var map = Dungeon.getMap();
var rooms = Dungeon.getRooms();
var tree = Dungeon.getTree();
var stats = DUngeon.getStats();
Dungeon.print simply prints the 2D map array onto the console. To actually see the map drawn on the screen as a tileMap, you’d have to use the awesome power of html5 or CSS3. There are many ways to get this done, say, drawing directly on the html5 canvas or manipulating the DOM. I decided to pick Phaser as the engine for this project.
I am not going to talk about Phaser here. That’s for the next part. I try to keep the game logic completely independent of the Game Engine, because this would allow code portability, I guess. Modularizashun !! It just feels right to do it this way.
Onwards to the Next Part: Dungeon Drawing in Phaser using Tilemap
Back to TowerOfFun Project


Oh! And the whole of above was written in StackEdit. It’s clearly way too awesome. StackEdit is an html5 markdown editor that has integrated markdown extra and a freaking Live Preview. All I do is write the whole thing down in StackEdit and then simply copy over the html to the Blogger editor. Here - Hello StackEdit! - you can see what it is capable of.