DungeonGenerator

[barrybecker4]

Use PCG (Procedural Content Generation) to automatically generate rooms in a dungeon. Inspired by my son's work in hi pixel-perfect game that he wrote in C#.

Implementation will proceed in these phases:

1. Use binary space partitioning algorithm to generate randomly placed rooms.
   • rooms will be nodes within a graph. Each node will have properties for hight, width, xpos, ypos, color, connections.
2. Have parameters that control how the rooms look. Changing these parameters generates a new map.
   • min/max room width
   • min/max room height
   • Percent filled. 1% means just one room, while 100% means completely filled with rooms
   • border - space between room and rectangular cell border
   • color
3. Add hallways between rooms. All rooms need to be connected in some way.
   • first connect all adjacent rooms
   • then gradually increase the distance until room for a connected graph
   • hallways will be represented by properties for room1, room2, pathPoints.
4. Optionally add long hallway as node between partitions. It will be a node in the graph, like rooms, but be a long halway.
5. Add items and other decoration
6. Add support for multiple "Biomes", where a biome controls what parameters are used to create rooms, hallways, and items within a region of the dungeon (biome).

[barrybecker4]

How to add corridors

When doing the BSP to create the rooms, build a kd-tree. Each node of the tree will contain all its child rooms. We will guarantee that all rooms in a subtree are connected. Proof

Leaves are connected because they contain only 1 room. The partition one level up from leaves contains at most 2 rooms.

• If there are 2 rooms, connect them directly using a straight corridor At each successive parent level, ensure that there is at least one corridor that connects rooms in adjacent child partitions.
• in top/left partition, find all rooms closest to the bottom/right side
• in bottom/right partition, find all rooms closest to the top/left side
• for these 2 sets find rooms that are as close to adjacent in the vertical/horizontal direction. Depending on a "connected" parameter add between 1 and a maximum number of connections. In some cases, there may not be any rooms that are adjacent in the vertical/horizontal direction. In those cases, create a right-angled corridor based on room centers.

Add option to have extra hallway between partitions that allow connecting many rooms to that perpendicular hallway.

[barrybecker4]

This simulator has been added. Support for multiple biomes is a future feature.