Random Dungeon Generation with Binary Space Partitions

One method used in computer games to generate random maps is the binary space partition (the BSP). In it's simplest application a space is subdivided into multiple smaller halves, this is repeated until enough breakdown is achieved and them details are added to flesh it out. It works in computer games, it should work in randomly building dungeons for table-top games.

Take a grid and block it off roughly in half.

Take those halves and split them in rough halves. I'm offsetting a little here and there .

Keep splitting up those halves either vertically or horizontally as you wish.

After a whiel you'll get enough complexity to suit your tastes, stop subdividing and draw in what fills those paces. (In my example here I went with rectangles one square in from the border of each space most of the time. I also decided to take my original couple dividing lines and make them wide corridors.)

 Add some details such as minor connecting corridors and doors and there you are a randomly generated dungeon map.

Quick and easy random BSP dungeon generation tables, mark 1a.

Die rolll	BSP split
1	Divide Vertically exactly down the middle
2	Divide Vertically offset to the west
3	Divide Vertically Offset to the east
4	Divide Horizontally exactly down the middle
5	Divide Hortizontally offset to the north
6	Divide Horizontally offset to the south

Die rolll	Detailing the BSP area
1	Ignore  the area, it’s full of stone.
2	Whole space is open.
3	Offset inward one square
4	Only fill the middle half of the space
5	Fill with a triangle that best fits.
6	Fill with an Oval that best fits

Die rolll	BSP connections
1-2	One Connection to one neighboring space
3	Two connections to same neighboring space.
4-5	One connection to each of two neighboring spaces.
6	one connection to  all neighboring spaces