Dungeon-Generator is a free and open-source BSP-based procedural 2D map generator. It was designed with roguelike games in mind, but it is not limited to them.

⭐ Features

• Various settings allow you to precisely customize the appearance of the dungeon.
• Generator receives seed value, so the outcome is always predictable.
• Rooms can be composed of two rectangular surfaces, creating unique structures.
• Algorithm can reduce room density in some areas, thus ensuring output looks more realistic.
• And a lot more!

💡 Example usage

#include <dgen/dgen.hpp>

int main()
{
    dg::Input input = dg::GetExampleInput();
    dg::Output output{};

    // In reality, you should set input member variables to your liking
    // and not depend on dg::GetExampleInput().

    dg::Generate(&input, &output);

    // Geometry of a dungeon is now generated, it should be processed
    // further (e.g., converting it to a tile map, postprocessing).

    return 0;
}

The generator fills object of type dg::Output with geometry data based on the data from object of type dg::Input. The output contains coordinates and dimensions of different dungeon structures, like rooms and paths.

⚙️ How does it work?

Function dg::Generate() performs internally several steps:

1. Algorithm recursively divides entire space into smaller cells, keeping the parent-cells in memory. This method is known as BSP, which produces binary-tree structure. In addition, leaf cells create Tag objects at the corners of them.
2. In some cells, Room objects are placed. Here Tag objects are also placed, but this time, on the room entrance axes, in between cells.
3. Algorithm creates Vertex objects based on Tag objects. Multiple tags are combined into one Vertex and all resulting vertices are linked together with pointers. To do this step, algorithm sorts Tag objects beforehand, based on their positions.
4. Previously created BSP-tree is traversed postorder, recursively connecting Room objects by searching path between them, using A* algorithm.
5. At this point, special method optimizes Vertex objects, based on created paths. This step is not required, but it helps reduce the size of generated data, without affecting its geometry.
6. Generator produces output data. Now the user can convert it e.g. to a tile map.

🔍 What is included in this repository?

Dungeon-Generator project consists of several sub-projects:

• dgen - generator library itself. Has no dependencies other than STL.
• dgen-app - application that uses dgen library. Requires SDL2 and SDL2_ttf.
• dgen-benchmark - micro-benchmarking utility. Measures performance of the dgen library.

🛠️ Building

Visual Studio

Prerequisites:

• Git (only for cloning)
• Microsoft Visual Studio 2022
• vcpkg (for dgen-app - make sure SDL2 and SDL2_ttf are installed)

Steps:

1. Clone this repository (or download by clicking Code -> Download ZIP).
2. Open Dungeon-Generator.sln.
3. Select startup project (e.g. dgen-app) and compile.

Compiled executables are located in the build directory.

CMake

Prerequisites:

• Git (only for cloning)
• Compiler that supports C++17
• CMake (version >= 3.21)

Steps:

1. Clone this repository (or download by clicking Code -> Download ZIP).
2. Open terminal in Dungeon-Generator directory.
3. Run the following command:

cmake -S . -B build && cmake --build build

CMake will detect if Dungeon-Generator is top level project. If so, it will automatically download SDL2 with SDL2_ttf and compile all targets. Otherwise, only dgen target will be created. Compiled executables are located in the build/bin directory.

🖼️ Images

The following image shows a visual representation of what dgen library can produce:

This geometry can be easily transformed into a tile map¹. For example:

¹Currently, the dgen library itself doesn't have this implemented yet.