Storing your rooms and rectangles is a very powerful and common practice to build levels and define maps. You may store the Rect in a varierty of ways such as {top, left, bottom, right} or {x, y, height, width}. This structure can be useful for many things such as moving rooms around during generation (pushing/expansion type algorithms), creating graphs such as Min Spanning Treets, or as the general output of a generator like a BSP.
In this guide I will use {top, left, bottom, right} as the Rect structure for berevity but any structure for defining a rectangle could work.
I will also assume an origin of the top left of the screen. I.e on the screen a larger Y value is further "down" and a larger x value is further right on the map.
For this article I will also try to spell out considerations for conceptualizing a room as being empty in its entire contents versus having a 1 tile ring of walls around it. (i.e. in the former style a room's top row would be open space, in the latter it would be row of walls). People like to use both and both have different advantages depending on the generator algorithm. The latter case can further be broken down into a case where you allow rooms to overlap by 1 tile (thus creating a single shared wall) vs styles where you only allow the rectangle rooms to touch eachother (thus creating a 2 tile shared wall). I will again try to spell out the differences here as best I can.
AABB, axis aligned bounding box, is a quick and simple technique to determine if two rectangles overlaps given that each rectangle is aligned to the axis of the same grid. In the case of roguelikes/map generation this is basically always true outside of hex grids; our rects will stretch horizontally from left -> right and vertically from top -> bot.
See here for detailed information on AABB, but the important part for this article is the 4 requirements for rooms overlapping:
- The left edge x-position of [A] must be less than the right edge x-position of [B].
- The right edge x-position of [A] must be greater than the left edge x-position of [B].
- The top edge y-position of [A] must be less than the bottom edge y-position of [B].
- The bottom edge y-position of [A] must be greater than the top edge y-position of [B].
The best way to visualize this is to think of each axis independently. Imagine rectangles as just a line segment along the x-axis and visualize scenarios following or breaking these rules. You will quickly see that it's impossible to have two lines overlap when the left side of one line segment is to the right (greater than) of the right side of the other line segment.
What AABB is ultimately doing is recognizing that 2 axis aligned rectangles overlap if (and only if) they overlap both along the x-axis line segments created by the rectangle's width and the y-axis line segments created by the rectangle's height.
(Feel free to skip this section if your generator already produces information on which rooms are adjacent to each other)
Detecting two overlapping rooms is trivial with AABB! It's what the algorithm is for, you merely have to run it between all pairs of rooms to find overlaps.
But what if you want to find what rooms touch other rooms. For example if I have the rooms A: {top: 2, left: 0, right: 8, bottom: 4} and B: {top: 5, left: 1, right: 5, bottom: 10} these rooms don't overlap but they do touch each other (top to bottom with Room B being below room A). When we want to connec rooms this is often the type of adjacency we are looking for.
Fortunately AABB can easily be adapted to handle this situation. One caveat with the simple example below is that we're going to start here from a system where we have ensures the rooms don't outright overlap. We either make sure this is impossible from the generator (i.e BSP) or have checked & resolved all cases of this occurring prior to finding which rooms touch.
All we need to do is expand the bounds of one of the rooms during the check (i.e we can check {top: 1, left: -1, right: 9, bottom: 5} against room B and AABB will return true that there is an overlap. Since we know there aren't any strict overlaps any true result will be from rooms merely touching.
To expand the bounds simple subtract 1 from top & left and add one to right and bottom. You can do this in a variety of ways, you can create a new rec, you can add +/- 1s to the various checks that part of AABB, or you could use <= over <
If you are generating rectangles that already overlap by one tile (to make shared single tile walls) then your AABB check will already return rooms you want to consider touching. But in this case you may need a better check to distinguish when rooms overlap outright rather than touch. What you can do here is shrink the bounds of one of the rooms (+1 to top/left, -1 to right/bottom) and if the AABB check still returns true then the rooms properly overlap rather than merely touching.
A possible edge-case here are rooms that touch only at the diagonal. For example {top: 1, left: 1, right: 3, bottom: 3} and {top: 4, left: 4, bottom: 8, right: 8} only overlap at the diagonal. Maybe this is ok for your design/vision, maybe you want to detect and not count these cases as touching.
Once we know what rooms are touching the next step is figuring out how two rooms touch. For all rooms in this section we are assuming you already know that the rooms touch, but don't overlap.
Fortunately the fundementals of AABB are still very useful here. We will be using the Rects defined for the rooms here without them being expanded or contracted as per the previous section, however is you are letting the rooms overlap by 1 tile for shared walls you will want to shrink the bounds for one of the rooms in these checks. With two arbitrary rooms that we are know are touching we know the following has to be true:
- One of the axis will have overlapping line segments (the two checks we perform for AABB will pass)
- One of the axis will have one of the two checks fail (the two line segments in this axis do not overlap, they merely touch.
Lets take an example step by step. Example Rectangles:
.012345
0...BBB
1AAABBB
2AAABBB
3AAA...
First we check the y-axis with the AABB checks.
- The Top edge of A is less than the bottom edge of B - True
- The Bottom Egde of A is greater than the top edge of B - True
Now we move to the x-axis:
- The left edge of A is less than the right edge of B - True
- The right edge of A is greater than the left edge of A - False! A's right edge is less than the left edge of B (A.right is 2, b.left is 3)
As you can see we will always end up with one failure in AABB when two rooms are touching but not overlapping. Which check fails will tell us how the rooms overlap. In this case since the right edge of A is less than the left of B we know that the rooms are touching horizontally with A on the left and B on the right.
The only case where two of these checks will simultaneously fail for touching rooms is if the rooms only touch diagonally. In that case you can handle those rooms separately, again possibly filtering them out or using similar principles described below to carve diagonally between the rooms.
** Deducing the shared edge **
From here we can deduce the shared edge between the two rooms! Since we know the rooms touch along a particular edge we already know one of the bounds of the touch. In our previous example the failed check lets us know Room A is to the left of Room B. We then know the x-coordinate of the touching area is A.right to B.left. All that's left is to figure out the opposite axis bounds.
This ends up being pretty straightforward. We know that the rooms overlap along this other axis already so there will be shared space between them (keeping in mind a diagonal touch possibility). All we need to do is simply find the constrains of that shared space. What that ends up being is taking the more centered of the two values for the opposite axis.
With our example we are looking at the y-axis so we would look for the largest of the top values and the smallest of the bottom values. If you had vertically touching rooms you'd look for the largest of the left values and the smallest of the right values. In this example case we end up with 1-2 as our vertical range of shared space.
If you are defining rooms with a border of 1 tile walls around them (i.e A.top is a row of walls) then you would want to add one to the top or left value and subtract 1 from the right or bottom value to determine the bounds of your connection. This way you are accounting for the row/column of walls that are part of the border of each room and looking for strictly the connection. If after doing this the bottom bound is less than the top bound (or the right bound is less than the left bound) your rooms will only properly connect diagonally. You will have to detect these edge cases and handle them appropriately.
So to recap with the example once we know how the rooms are touching and we grab the top/bottom values as described we end up finding this:
.01234
0...BBB
1AAABBB - Largest Top Value
2AAABBB
3AAABBB - Smallest Bottom Value
4AAA...
||
| \- Left Edge found from which AABB check failed
\- Right edge found from AABB check failed
As you an see we've now properly found a rectangular area that defines the common connection between the two rooms. At this point we can properly knock down walls in that rectangle to connect the rooms depending on how the rooms are stored.
Here's an example when the rooms have a border of walls around them:
.01234
0...###
1####B#
2#A##B# - Largest Top Value + 1 & smalled bottom value - 1
3#A####
4###...
||
| \- Left Edge found from which AABB check failed
\- Right edge found from AABB check failed
As you can see once we account for the walls we're left with a single bound for the y value (2). If this was a range we could randomly select within the range along the y-axis to find where to carve a door, but in this case we can use the only possible value of two. So now we know all of what we need to carve. If we carve out (2,2) and (3,2) we will have connected the two rooms!