Dungeon Generator

This is a dungeon generator made with Unity and C# that was developed using Space Partitioning.

What is Space Partitioning (BSP)?

A space-partitioning algorithm yields a division of 2D or 3D space
into disjoint subsets, so that any point in the space lies in exactly
one of these subsets.

Space-partitioning algorithms often operate hierarchically: each
cell in a space partition is further subdivided by applying the same
algorithm recursively. This allows space partitions to be arranged
in a so-called space-partitioning tree.

The entire dungeon area is represented by the root node of the
BSP tree and is partitioned recursively until a terminating
condition is met (such as a minimum size for rooms). The BSP
algorithm guarantees that no two rooms will be overlapping, and
allows for a very structured appearance of the dungeon.

How to do?

1.  start with the entire dungeon area (root node of BSP tree)
2. divide the area along a horizontal or vertical line
3. select one of the two new partition cells
4.  if this cell is bigger than the minimal acceptable size: go to step 2 (using this cell as the area to be divided)
5. select the other partition cell, and go to step 4
6. After partitioning:
1.  for every partition cell: create a room within the cell by randomly choosing two points
2. starting from the lowest layers, draw corridors to connect rooms corresponding to children of the same parent in the BSP tree
3. repeat 2 until the children of the root node are connected

The code is available to see only for business inquiries.