step1

Morgemil Part 10 – BSP Dungeon Generation Part 3

Today I’m connecting dungeon rooms together.

My very first inclination was to make a Minimum Spanning Tree of some sort. I quickly discarded that idea as I thought about how I would construct a dungeon: with lots of passages. So I’m going to make up my own algorithm which is likely not original at all.

Find all axis-aligned corridors between rooms. For example, given these rooms:step2 The corridors could be (in blue):step3
These are pretty large corridors so we should probably scale them down to something manageable. But first there’s a bigger problem:map_test2
Connecting all the axis-aligned corridors over the entire map doesn’t check to see if the corridor goes through an already existing room. Should probably check for that:
step5
That’s a little bit better, but not a whole lot better. Corridors can still intersect and they are huge. I’m okay with intersecting corridors because I think it is interesting. But corridors that large is not so good. Let’s change that.
step6
It should be noted that I have now made the map DungeonWalls tile the default black color and filled the entire map with it. Red is now the corridors.

This is not a sophisticated method but it is sufficient for the player to move around and explore.

Let’s lay down some code on how I did this. Taking each pair of rectangles (rooms), I tested if they shared an axis

  let ShareHorizontal (rect1 : Rectangle) (rect2 : Rectangle) =
    not (rect1.Left > rect2.Right || rect1.Right < rect2.Left)
  let ShareVertical (rect1 : Rectangle) (rect2 : Rectangle) =
    not (rect1.Top > rect2.Bottom || rect1.Bottom < rect2.Top)
 
  ///Assuming non-intersecting rectangles
  let ShareAxis (rect1 : Rectangle) (rect2 : Rectangle) =
    match rect1 with
    | _ when ShareHorizontal rect1 rect2 -> Some(Axis.Horizontal)
    | _ when ShareVertical rect1 rect2 -> Some(Axis.Vertical)
    | _ -> None

I created a corridor between those two rooms by

  ///Returns success and a axis-aligned corridor between the two rectangles if it exists.
  let Corridor (rect1 : Rectangle) (rect2 : Rectangle) =
    match ShareAxis rect1 rect2 with
    | None -> None
    | Some(ax) ->
      match ax with
      | Axis.Horizontal ->
        let first, second = SortVertical rect1 rect2
        let pos1 = Vector2i(Math.Max(first.Left, second.Left), first.Bottom + 1)
 
        ///Make corridor of width 2 if possible. But also handles a corridor of one width
        let minX = Math.Min(pos1.X + 1, Math.Min(first.Right, second.Right))
 
        let pos2 = Vector2i(minX, second.Top - 1)
        Some(Rectangle.Enclose pos1 pos2)
      | Axis.Vertical ->
        let first, second = SortHorizontal rect1 rect2
        let pos1 = Vector2i(first.Right + 1, Math.Max(first.Top, second.Top))
 
        ///Make corridor of heighth 2 if possible. But also handles a corridor of one height
        let minY = Math.Min(pos1.Y + 1, Math.Min(first.Bottom, second.Bottom))
 
        let pos2 = Vector2i(second.Left - 1, minY)
        Some(Rectangle.Enclose pos1 pos2)

In the top level after the dungeonRooms were defined and created

    ///For each room, tests it against every room after it
    let rec CreateRoomCorridors(L : list<Rectangle>) =
      match L with
      | head :: tail ->
        tail
        |> List.choose (Corridor head)
        |> List.append (CreateRoomCorridors tail)
      | [] -> []
 
    ///Tests for collisions with rooms
    let Collides(corr : Rectangle) = dungeonRooms |> List.exists (corr.Intersects)
 
    let dungeonCorridors =
      dungeonRooms
      |> CreateRoomCorridors
      |> List.filter (Collides >> not)
 
    //Draw the corridors on the map
    dungeonCorridors |> List.iter (GenerateCorridor dungeon_map)