Devlog 6: Class Setup and Binary Space Partitioner
This week explores the setup of key classes that are used to manage the generation process, as well as the implementation of the Binary Space Partitioning (BSP) algorithm.
The DungeonCreator class is responsible for managing the creation of a dungeon layout within Unity. It defines several properties related to the dungeon’s size and structure and provides a method to trigger the dungeon generation process.
The DungeonGenerator class is responsible for initiating the dungeon generation process. It initializes the dungeon’s size based on the provided dimensions and prepares for space partitioning using the BSP algorithm. The CalculateDungeon method, although not fully implemented, will use the BSP algorithm to generate the rooms and corridors, and return a list of nodes that represent the dungeon’s layout.
The Node class represents a structure used for creating hierarchical trees, with each instance of the class potentially being a part of a larger tree. It is abstract, meaning that it serves as a base class and is meant to be extended by other specific node types. Each Node has a reference to its parent node and a list of child nodes, allowing for a tree-like structure. The class also includes properties for tracking the boundaries of the node’s area in 2D space, with Vector2Int variables defining the corners of the node’s area.
The Node class has a Visited property, which can be used for traversal or marking purposes, as well as a TreeLayerIndex to indicate the depth or level of the node in the tree. The constructor automatically adds the current node to its parent’s list of children if the parent is provided, creating a connection between nodes. The AddChild and RemoveChild methods allow for dynamic modification of the tree by adding or removing child nodes as necessary. This structure is useful for representing hierarchical systems, such as in procedural generation, decision trees, or spatial partitioning algorithms.
The RoomNode class extends the Node class, representing a specific type of node that models a room in a dungeon generation system. It inherits all properties and methods from the Node class but adds functionality specific to rooms. The constructor of RoomNode takes in the bottom-left and top-right corners of the room, as well as a parent node and an index that represents the room’s position in the tree structure. It then calculates the positions of the other two corners (bottom-right and top-left) based on the provided corner coordinates.
The class has two properties, Width and Length, which are computed from the corner positions. Width calculates the horizontal distance between the left and right sides of the room, while Length calculates the vertical distance between the bottom and top sides. These properties are useful for determining the room’s size, which is important for the generation process.
The Line class represents a line in a grid-based system, with properties to define its orientation and its coordinates within the grid.
After the creation of these classes, the next step was to create the BinarySpacePartitioner class.
The BinarySpacePartitioner class uses a recursive method to divide a given space into smaller sections, simulating the creation of rooms and corridors in a dungeon. It employs a queue to manage nodes and iteratively splits the space using randomly chosen horizontal or vertical lines, ensuring that the resulting rooms meet the specified minimum size. The class encapsulates the logic for the BSP algorithm, making it easier to generate a variety of dungeon layouts by adjusting the parameters, such as room sizes and the number of iterations.
The last step was to test the algorithm, after changing the parameters inside the Unity editor, a breakpoint was used in the DungeonGenerator class to make sure that the algorithm was working, as there was currently no visual implementation.
As seen in the image, the original node, 0, was split - proving that the algorithm was successful.
Reference List
Sunny Valley Studio. (2019). Unity 3d procedural dungeon generator. [YouTube playlist]. Available from: https://www.youtube.com/playlist?list=PLcRSafycjWFfEPbSSjGMNY-goOZTuBPMW [accessed 6 November 2024].