User:NotBrandX/BSP dungeon generation

From 1d4chan
Recursive dungeon mapmaking.png

So I don't forget; this is how roguelikes create dungeon maps.

  1. Start with a grid of the entire floor (eg. 80x20) and a minimum room size (eg. 3x3)
  2. Divide the long side of the dungeon into two sub-dungeons, roughly equal in size, making sure there's enough room on either side for the smallest room size.
  3. For each sub-dungeon
    1. if it's bigger than the minimum room size, goto step 2 and use the subdungeon.
    2. else, for each subdungeon that doesn't have a room in it, pick two random points in one half to be opposite corners in the room; draw the rectangle.
    3. pick a random points in each of the two subdungeon's room(s) closest to the other subdungeon, imagine a straight line between them. Draw a corridor joining the rooms along this line.
    4. This sub-dungeon is complete, go do the other subdungeon.

Arrrgh, hard to describe recursion in English; easier to use pictures.