BSP Dungeon Generation in Java for Dungeon Crawler

Question

Doogledude123 45 Posting Whiz

8 Years Ago

I'm having some issues with my BSP Dungeon Generation and I'm not sure why! I'd greatly appreciate the help :)
Occasionally I'll get an IllegalArgumentException in RandomHelper. That may help, but it's not the issue because it only happens rarely.
As you can see, this image shows that the Rooms are not in the right positions, and sometimes not even the right size!
It should also be spliting each leaf 4 times, but it only splits the room into 2 leafs, then stops.

Here's a link to help understand what I'm trying to accomplish.

And, all the relavent code:
BSPDungeon.java

public class BSPDungeon
{
    private BSPTree dungeonTree;

    public BSPDungeon(BSPTree dungeonTree)
    {
        this.dungeonTree = dungeonTree;
    }

    public void render(Graphics g)
    {
        dungeonTree.render(g);
    }
}

BSPDungeonGenerator.java

public class BSPDungeonGenerator
{
    public static BSPDungeon generate(int splitIterations, int minRoomWidth, int minRoomHeight, int dungeonW, int dungeonH)
    {
        Random rand = new Random();
        BSPTree dungeonTree = new BSPTree(dungeonW, dungeonH);

        dungeonTree.generateTree(rand, splitIterations);
        dungeonTree.finalizeNode();
        dungeonTree.generateRooms(rand, minRoomWidth, minRoomHeight);

        return new BSPDungeon(dungeonTree);
    }
}

BSPDungeonRoom.java
NOTE: TilePosition simply stores 2 Integers for an x and a y

public class BSPDungeonRoom
{
    private static final int TILE_SIZE = Tile.TILE_SIZE / 4;

    private TilePosition position;
    private int w, h;

    public BSPDungeonRoom(TilePosition position, int w, int h)
    {
        this.position = position;
        this.w = w;
        this.h = h;
    }

    public void render(Graphics g)
    {
        g.setColor(Color.GRAY);
        g.fillRect(position.getTileX() * TILE_SIZE, position.getTileY() * TILE_SIZE, w * TILE_SIZE, h * TILE_SIZE);
        g.setColor(Color.RED);
        g.drawRect(position.getTileX() * TILE_SIZE, position.getTileY() * TILE_SIZE, w * TILE_SIZE, h * TILE_SIZE);
    }
}

BSPNode.java

public class BSPNode
{
    private static final int TILE_SIZE = Tile.TILE_SIZE / 4;

    private boolean modifiable;

    private BSPNode parentNode;
    private BSPNode childNodeA;
    private BSPNode childNodeB;

    private BSPSplitType splitType;

    private BSPDungeonRoom dungeonRoom;

    private int nodeX, nodeY, nodeW, nodeH;
    private int splitX, splitY;

    public BSPNode(BSPNode parentNode, int nodeX, int nodeY, int nodeW, int nodeH)
    {
        this.parentNode = parentNode;
        this.nodeX = nodeX;
        this.nodeY = nodeY;
        this.nodeW = nodeW;
        this.nodeH = nodeH;

        modifiable = true;
    }

    public boolean isRoot()
    {
        // If the parentNode is null, treat this Node as the Root Node
        return parentNode == null;
    }

    public boolean isBalanced()
    {
        // Checks if this Node is NOT a Leaf, and ensures that both children Nodes are NOT null
        return !isLeaf() && childNodeA != null && childNodeB != null;
    }

    public boolean isLeaf()
    {
        // True if both children Nodes are null
        return childNodeA == null && childNodeB == null;
    }

    public BSPNode getChildNodeA()
    {
        return childNodeA;
    }

    public BSPNode getChildNodeB()
    {
        return childNodeB;
    }

    public int getNodeX()
    {
        return nodeX;
    }

    public int getNodeY()
    {
        return nodeY;
    }

    public int getNodeWidth()
    {
        return nodeW;
    }

    public int getNodeHeight()
    {
        return nodeH;
    }

    public void split(BSPSplitType splitType, int split)
    {
        if(modifiable)
        {
            this.splitType = splitType;

            if (splitType == BSPSplitType.VERTICAL)
            {
                splitX = split;

                childNodeA = new BSPNode(this, nodeX, nodeY, split, nodeH);
                childNodeB = new BSPNode(this, nodeX + split, nodeY, nodeW - split, nodeH);
            }
            else if (splitType == BSPSplitType.HORIZONTAL)
            {
                splitY = split;

                childNodeA = new BSPNode(this, nodeX, nodeY, nodeW, split);
                childNodeB = new BSPNode(this, nodeX, nodeY + split, nodeW, nodeH - split);
            }
        }
    }

    public boolean wasSplit()
    {
        // Node was split if the splitType was set
        return splitType != null;
    }

    public BSPSplitType getSplitType()
    {
        return splitType;
    }

    public boolean shouldHaveRoom()
    {
        // Should be a Room if this Node is a Leaf
        return isLeaf();
    }

    public boolean shouldHaveCorridor()
    {
        // Should be a Corridor if this Node's children have Rooms
        return childNodeA.shouldHaveRoom() && childNodeB.shouldHaveRoom();
    }

    public boolean isDungeonRoomNull()
    {
        return dungeonRoom == null;
    }

    public void setDungeonRoom(BSPDungeonRoom dungeonRoom)
    {
        this.dungeonRoom = dungeonRoom;
    }

    public BSPDungeonRoom getDungeonRoom()
    {
        return dungeonRoom;
    }

    public void render(Graphics g)
    {
        g.setColor(Color.LIGHT_GRAY);
        g.fillRect(nodeX * TILE_SIZE, nodeY * TILE_SIZE, nodeW * TILE_SIZE, nodeH * TILE_SIZE);

        g.setColor(Color.DARK_GRAY);
        g.drawRect(nodeX * TILE_SIZE, nodeY * TILE_SIZE, nodeW * TILE_SIZE, nodeH * TILE_SIZE);

        if(dungeonRoom != null)
            dungeonRoom.render(g);
    }

    public void finalizeNode()
    {
        modifiable = false;
    }
}

BSPSplitType.java

public enum BSPSplitType
{
    VERTICAL(0),
    HORIZONTAL(1);

    private int splitValue;

    BSPSplitType(int splitValue)
    {
        this.splitValue = splitValue;
    }

    public int getSplitValue()
    {
        return splitValue;
    }

    public static BSPSplitType getSplitTypeFromValue(int splitValue)
    {
        return splitValue == VERTICAL.getSplitValue() ? VERTICAL : HORIZONTAL;
    }

    public static BSPSplitType getRandomSplitType(Random rand)
    {
        return getSplitTypeFromValue(rand.nextInt(2));
    }
}

BSPTree.java

public class BSPTree
{
    private BSPNode rootNode;
    private ArrayList<BSPNode> finalizedNodeList;

    public BSPTree(int width, int height)
    {
        rootNode = new BSPNode(null, 0, 0, width, height);
    }

    public void generateTree(Random rand, int splitIterations)
    {
        ArrayList<BSPNode> nodeList;

        for (int i = 0; i < splitIterations; i++)
        {
            nodeList = getTreeNodes();

            for (BSPNode node : nodeList)
            {
                if(!node.isLeaf())
                    return;

                BSPSplitType splitType = BSPSplitType.getRandomSplitType(rand);
                int splitAt;

                if(splitType == BSPSplitType.VERTICAL)
                    splitAt = rand.nextInt(node.getNodeWidth());
                else if(splitType == BSPSplitType.HORIZONTAL)
                    splitAt = rand.nextInt(node.getNodeHeight());
                else splitAt = 0;

                node.split(splitType, splitAt);
            }
        }
    }

    public void generateRooms(Random rand, int minRoomWidth, int minRoomHeight)
    {
        ArrayList<BSPNode> nodeList = getTreeNodes();

        for (BSPNode node : nodeList)
        {
            if(node.shouldHaveRoom() && node.isDungeonRoomNull())
            {
                // Generate the Dungeon Room
                int roomX;
                int roomY;
                int roomW;
                int roomH;

                roomX = RandomHelper.randomInRange(rand, node.getNodeX(), node.getNodeX() + node.getNodeWidth());
                roomY = RandomHelper.randomInRange(rand, node.getNodeY(), node.getNodeY() + node.getNodeHeight());
                roomW = RandomHelper.randomInRange(rand, roomX + minRoomWidth, node.getNodeWidth());
                roomH = RandomHelper.randomInRange(rand, roomY + minRoomHeight, node.getNodeHeight());

                BSPDungeonRoom dungeonRoom = new BSPDungeonRoom(new TilePosition(roomX, roomY), roomW, roomH);

                node.setDungeonRoom(dungeonRoom);
            }
        }

        /*for (BSPNode node : nodeList)
        {
            if(node.shouldHaveCorridor() && node.isDungeonRoomNull())
            {
                // Generate the Dungeon Corridor
                int corridorX;
                int corridorY;
                int corridorW;
                int corridorH;

                BSPNode childA = node.getChildNodeA();
                BSPNode childB = node.getChildNodeB();

                BSPDungeonRoom dungeonCorridor = null;

                if(node.wasSplit() && node.getSplitType() == BSPSplitType.HORIZONTAL)
                {
                    corridorX = childA.getNodeX() + childA.getNodeWidth();
                    corridorY = rand.nextInt(childA.getNodeHeight()) + childA.getNodeY();
                }
                else if(node.wasSplit() && node.getSplitType() == BSPSplitType.VERTICAL)
                {

                }

                if(dungeonCorridor != null)
                    node.setDungeonRoom(dungeonCorridor);
            }
        }*/
    }

    public void render(Graphics g)
    {
        for (BSPNode node : finalizedNodeList)
        {
            node.render(g);
        }
    }

    public ArrayList<BSPNode> getTreeNodes()
    {
        ArrayList<BSPNode> nodeList = new ArrayList<>();
        BSPNode currentNode = rootNode;

        getNodes(currentNode, nodeList);

        return nodeList;
    }

    public void getNodes(BSPNode node, ArrayList<BSPNode> nodeList)
    {
        nodeList.add(node);
        if(!node.isLeaf())
        {
            getNodes(node.getChildNodeA(), nodeList);
            getNodes(node.getChildNodeB(), nodeList);
        }
    }

    public void finalizeNode()
    {
        ArrayList<BSPNode> nodeList = getTreeNodes();
        for (BSPNode node : nodeList)
        {
            node.finalizeNode();
        }

        finalizedNodeList = nodeList;
    }
}

And to Generate a Dungeon I simply call BSPDungeon dungeon = BSPDungeonGenerator.generate(4, 6, 6, 60, 60);.

java storage

Edited 8 Years Ago by pritaeas because: Moved to software dev.

2 Contributors
5 Replies
650 Views
1 Day Discussion Span
Latest Post 8 Years Ago Latest Post by JamesCherrill

JamesCherrill 4,733 Most Valuable Poster

8 Years Ago

I think you are wrong about randomHelper. It's crazy to ignore a known problem while looking for an unknown one. Track down and fix that problem before moving on. Maybe it's irrelevant to the one you're worrying about, but maybe not.

JamesCherrill 4,733 Most Valuable Poster

8 Years Ago

return rand.nextInt((max - min) + min);
is the same as return rand.nextInt(max );

did you mean this?
return rand.nextInt(max - min) + min;

ps: Are you writing too much between tests then testing with typical data? If so that's two mistakes you need to correct in your process:
1. Test early and often. Test each method before you write another one. 100 lines of code is up to 10x too many to write without stopping to test what you just wrote.
2. Test with trivial values first, like 1 or 2, not 6.

So you have to write a few hard-coded calls and a couple of prints just to test? Yes. It's still the quickest way to a working program.

Another rule of thumb: If you are finding more than 2 bugs when you test they you're not testing early enough.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Doogledude123 45 Posting Whiz · Answer 1 · 2016-02-17T18:21:57+00:00

I know why I'm getting that exception, but I don't know where the problem is. I'm getting a "bound must be positive" which means the number being passed into nextInt is negative, which obviously cannot work.

I realized I forgot to post my RandomHelper.java file, so here it is.

public class RandomHelper
{
    public static int randomInRange(Random rand, int min, int max)
    {
        return rand.nextInt((max - min) + min);
    }
}

Doogledude123 45 Posting Whiz · Answer 2 · 2016-02-18T06:14:26+00:00

Okay, I figured out some problems, although now it's being difficult.

Will post back later with results after I fool around with it some more.

Doogledude123 45 Posting Whiz · Answer 3 · 2016-02-18T06:29:10+00:00

Posting some updated code, broke after implementing minimum room sizes. Issue occurs with Random.nextInt() throwing an IllegalArgumentException because the node width/height is less than the minimum?

BSPDungeon.java

public class BSPDungeon
{
    private BSPTree nodeTree;
    private List<BSPDungeonRoom> dungeonRooms;

    public BSPDungeon(BSPTree nodeTree, List<BSPDungeonRoom> dungeonRooms)
    {
        this.nodeTree = nodeTree;
        this.dungeonRooms = dungeonRooms;
    }

    public void render(Graphics g)
    {
        nodeTree.render(g);
        /*for (BSPDungeonRoom dungeonRoom : dungeonRooms)
        {
            dungeonRoom.render(g);
        }*/
    }
}

BSPDungeonGenerator.java

public class BSPDungeonGenerator
{
    public static BSPDungeon generate(int splitIterations, int minRoomWidth, int minRoomHeight, int dungeonW, int dungeonH)
    {
        Random rand = new Random();
        BSPTree dungeonTree = new BSPTree(dungeonW, dungeonH);

        dungeonTree.generateTree(rand, splitIterations, minRoomWidth, minRoomHeight);
        dungeonTree.finalizeNode();

        //return new BSPDungeon(dungeonTree, dungeonTree.generateRooms(rand, minRoomWidth, minRoomHeight));
        return new BSPDungeon(dungeonTree, null);
    }
}

BSPDungeonRoom.java

public class BSPDungeonRoom
{
    private static final int TILE_SIZE = Tile.TILE_SIZE / 4;

    private static int nextRoomID = 0;

    public static int getNextRoomID()
    {
        return nextRoomID++;
    }

    private int roomID;
    private TilePosition position;
    private int w, h;

    public BSPDungeonRoom(int roomID, TilePosition position, int w, int h)
    {
        this.roomID = roomID;
        this.position = position;
        this.w = w;
        this.h = h;
    }

    public void render(Graphics g)
    {
        g.setColor(Color.GRAY);
        g.fillRect(position.getTileX() * TILE_SIZE, position.getTileY() * TILE_SIZE, w * TILE_SIZE, h * TILE_SIZE);
        g.setColor(Color.RED);
        g.drawRect(position.getTileX() * TILE_SIZE, position.getTileY() * TILE_SIZE, w * TILE_SIZE, h * TILE_SIZE);
    }

    public int getRoomID()
    {
        return roomID;
    }
}

BSPNode.java

public class BSPNode
{
    private static final int TILE_SIZE = Tile.TILE_SIZE / 4;

    private boolean modifiable;

    private BSPNode parentNode;
    private BSPNode childNodeA;
    private BSPNode childNodeB;

    private BSPSplitType splitType;

    private BSPDungeonRoom dungeonRoom;

    private int nodeX, nodeY, nodeW, nodeH;
    private int splitX, splitY;

    public BSPNode(BSPNode parentNode, int nodeX, int nodeY, int nodeW, int nodeH)
    {
        this.parentNode = parentNode;
        this.nodeX = nodeX;
        this.nodeY = nodeY;
        this.nodeW = nodeW;
        this.nodeH = nodeH;

        modifiable = true;
    }

    public boolean isRoot()
    {
        // If the parentNode is null, treat this Node as the Root Node
        return parentNode == null;
    }

    public boolean isBalanced()
    {
        // Checks if this Node is NOT a Leaf, and ensures that both children Nodes are NOT null
        return !isLeaf() && childNodeA != null && childNodeB != null;
    }

    public boolean isLeaf()
    {
        // True if both children Nodes are null
        return childNodeA == null && childNodeB == null;
    }

    public BSPNode getChildNodeA()
    {
        return childNodeA;
    }

    public BSPNode getChildNodeB()
    {
        return childNodeB;
    }

    public int getNodeX()
    {
        return nodeX;
    }

    public int getNodeY()
    {
        return nodeY;
    }

    public int getNodeWidth()
    {
        return nodeW;
    }

    public int getNodeHeight()
    {
        return nodeH;
    }

    public void split(BSPSplitType splitType, int split)
    {
        if(modifiable)
        {
            this.splitType = splitType;

            if (splitType == BSPSplitType.VERTICAL)
            {
                splitX = split;

                childNodeA = new BSPNode(this, nodeX, nodeY, split, nodeH);
                childNodeB = new BSPNode(this, nodeX + split, nodeY, nodeW - split, nodeH);
            }
            else if (splitType == BSPSplitType.HORIZONTAL)
            {
                splitY = split;

                childNodeA = new BSPNode(this, nodeX, nodeY, nodeW, split);
                childNodeB = new BSPNode(this, nodeX, nodeY + split, nodeW, nodeH - split);
            }
        }
    }

    public boolean wasSplit()
    {
        // Node was split if the splitType was set
        return splitType != null;
    }

    public BSPSplitType getSplitType()
    {
        return splitType;
    }

    public boolean shouldHaveRoom()
    {
        // Should be a Room if this Node is a Leaf
        return isLeaf();
    }

    public boolean shouldHaveCorridor()
    {
        // Should be a Corridor if this Node's children have Rooms
        return childNodeA.shouldHaveRoom() && childNodeB.shouldHaveRoom();
    }

    public boolean isDungeonRoomNull()
    {
        return dungeonRoom == null;
    }

    public void setDungeonRoom(BSPDungeonRoom dungeonRoom)
    {
        this.dungeonRoom = dungeonRoom;
    }

    public BSPDungeonRoom getDungeonRoom()
    {
        return dungeonRoom;
    }

    public void render(Graphics g)
    {
        g.setColor(Color.LIGHT_GRAY);
        g.fillRect(nodeX * TILE_SIZE, nodeY * TILE_SIZE, nodeW * TILE_SIZE, nodeH * TILE_SIZE);

        g.setColor(Color.DARK_GRAY);
        g.drawRect(nodeX * TILE_SIZE, nodeY * TILE_SIZE, nodeW * TILE_SIZE, nodeH * TILE_SIZE);

        if(dungeonRoom != null)
            dungeonRoom.render(g);
    }

    public void finalizeNode()
    {
        modifiable = false;
    }
}

BSPTree.java

public class BSPTree
{
    private BSPNode rootNode;
    private ArrayList<BSPNode> finalizedNodeList;

    public BSPTree(int width, int height)
    {
        rootNode = new BSPNode(null, 0, 0, width, height);
    }

    public void generateTree(Random rand, int splitIterations, int minRoomWidth, int minRoomHeight)
    {
        ArrayList<BSPNode> nodeList;

        boolean skipCurrent;
        for (int i = 0; i < splitIterations; i++)
        {
            nodeList = getTreeNodes();

            for (BSPNode node : nodeList)
            {
                skipCurrent = !node.isLeaf();

                if(!skipCurrent)
                {
                    BSPSplitType splitType = BSPSplitType.getRandomSplitType(rand);
                    int splitAt;

                    if (splitType == BSPSplitType.VERTICAL)
                        splitAt = RandomHelper.randomInRange(rand, minRoomWidth, (node.getNodeWidth() - minRoomWidth));
                    else if (splitType == BSPSplitType.HORIZONTAL)
                        splitAt = RandomHelper.randomInRange(rand, minRoomHeight, (node.getNodeHeight() - minRoomHeight));
                    else splitAt = 0;

                    node.split(splitType, splitAt);
                }
            }
        }
    }

    public List<BSPDungeonRoom> generateRooms(Random rand, int minRoomWidth, int minRoomHeight)
    {
        ArrayList<BSPNode> nodeList = getTreeNodes();
        ArrayList<BSPDungeonRoom> dungeonRooms = new ArrayList<>();

        for (BSPNode node : nodeList)
        {
            if(node.shouldHaveRoom() && node.isDungeonRoomNull())
            {
                // Generate the Dungeon Room
                int roomX;
                int roomY;
                int roomW;
                int roomH;

                roomX = RandomHelper.randomInRange(rand, node.getNodeX(), node.getNodeX() + node.getNodeWidth());
                roomY = RandomHelper.randomInRange(rand, node.getNodeY(), node.getNodeY() + node.getNodeHeight());
                roomW = RandomHelper.randomInRange(rand, roomX + minRoomWidth, node.getNodeWidth());
                roomH = RandomHelper.randomInRange(rand, roomY + minRoomHeight, node.getNodeHeight());

                BSPDungeonRoom dungeonRoom = new BSPDungeonRoom(BSPDungeonRoom.getNextRoomID(), new TilePosition(roomX, roomY), roomW, roomH);

                node.setDungeonRoom(dungeonRoom);
                dungeonRooms.add(dungeonRoom);
            }
        }

        /*for (BSPNode node : nodeList)
        {
            if(node.shouldHaveCorridor() && node.isDungeonRoomNull())
            {
                // Generate the Dungeon Corridor
                int corridorX;
                int corridorY;
                int corridorW;
                int corridorH;

                BSPNode childA = node.getChildNodeA();
                BSPNode childB = node.getChildNodeB();

                BSPDungeonRoom dungeonCorridor = null;

                if(node.wasSplit() && node.getSplitType() == BSPSplitType.HORIZONTAL)
                {
                    corridorX = childA.getNodeX() + childA.getNodeWidth();
                    corridorY = rand.nextInt(childA.getNodeHeight()) + childA.getNodeY();
                }
                else if(node.wasSplit() && node.getSplitType() == BSPSplitType.VERTICAL)
                {

                }

                if(dungeonCorridor != null)
                    node.setDungeonRoom(dungeonCorridor);
            }
        }*/

        return dungeonRooms;
    }

    public void render(Graphics g)
    {
        for (BSPNode node : finalizedNodeList)
        {
            node.render(g);
        }
    }

    public ArrayList<BSPNode> getTreeNodes()
    {
        ArrayList<BSPNode> nodeList = new ArrayList<>();
        BSPNode currentNode = rootNode;

        getNodes(currentNode, nodeList);

        return nodeList;
    }

    public void getNodes(BSPNode node, ArrayList<BSPNode> nodeList)
    {
        nodeList.add(node);
        if(!node.isLeaf())
        {
            getNodes(node.getChildNodeA(), nodeList);
            getNodes(node.getChildNodeB(), nodeList);
        }
    }

    public void finalizeNode()
    {
        ArrayList<BSPNode> nodeList = getTreeNodes();
        for (BSPNode node : nodeList)
        {
            node.finalizeNode();
        }

        finalizedNodeList = nodeList;
    }
}

And again, to generate a Dungeon, BSPDungeon dungeon = BSPDungeonGenerator.generate(4, 6, 6, 60, 60); // BSP Gen