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: The corridors could be (in blue):
These are pretty large corridors so we should probably scale them down to something manageable. But first there’s a bigger problem:
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:
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.
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) |