# Connecting rooms after BSP

package byog.Core;

import byog.TileEngine.TERenderer;
import byog.TileEngine.TETile;
import byog.TileEngine.Tileset;

import java.util.ArrayDeque;
import java.util.Random;

public class World {
private final long SEED;
private final Random RANDOM;
private final TETile[][] world;
private final int WIDTH;
private final int HEIGHT;
private boolean occupied[][];
private ArrayDeque<Room> rooms = new ArrayDeque<>();

public World(long SEED, TETile[][] tiles, int width, int height) {
this.SEED = SEED;
this.RANDOM = new Random(SEED);
this.world = tiles;
this.WIDTH = width;
this.HEIGHT = height;
this.occupied = new boolean[width][height];
}

public void render() {
initialize();
split();
//connectRooms();
TERenderer ter = new TERenderer();
ter.initialize(WIDTH, HEIGHT);
ter.renderFrame(world);
}

// fill with nothingness
private void initialize() {
for (int i = 0; i < WIDTH; i++) {
for (int j = 0; j < HEIGHT; j++) {
world[i][j] = Tileset.NOTHING;
}
}
}

private void split() {
split(new Position(0, 0), new Position(WIDTH - 1, HEIGHT - 1), 0);
}

private void split(Position bottomLeft, Position topRight, int recursionDepth) {
String direction = getRandomOrientation();
// stop after 4 splitting iterations
if (recursionDepth == 4) {
makeRandomRoom(bottomLeft, topRight);
return;
}
recursionDepth++;
switch (direction) {
case "vertical": {
splitVertically(bottomLeft, topRight);
// calculate positions for splitting the left side
// bottomLeft will remain same and the topRight's y will remain same but
// the new X will be halved
int midX = (bottomLeft.x() + topRight.x()) / 2;
Position midTopRight = new Position(midX, topRight.y());
split(bottomLeft, midTopRight, recursionDepth);

// for right half:
Position midBottomLeft = new Position(midX, bottomLeft.y());
split(midBottomLeft, topRight, recursionDepth);
break;
}
// case horizontal
default: {
splitHorizontally(bottomLeft, topRight);
int midY = (bottomLeft.y() + topRight.y()) / 2;

// for top half:
Position midTopLeft = new Position(bottomLeft.x(), midY);
split(midTopLeft, topRight, recursionDepth);

// for bottom half:
Position midTopRight = new Position(topRight.x(), midY);
split(bottomLeft, midTopRight, recursionDepth);
}

}
}

private void makeRandomRoom(Position bottomLeft, Position topRight) {
int width, height;
do {
width = RANDOM.nextInt(Position.xDistance(bottomLeft, topRight) - 2); // -2 because of walls
height = RANDOM.nextInt(Position.yDistance(bottomLeft, topRight) - 2); // -2 because of walls
} while (width <= 0 || height <= 0);

/* TODO - add randomness to room generation; rn we start at bottom left coordinate,
you should be able to start at a different reasonable coordinate
*/
// +1 to not collide with the walls
int x = bottomLeft.x() + 1;
int y = bottomLeft.y() + 1;
for (int i = x; i <= x + width; i++) {
for (int j = y; j <= y + height; j++) {
world[i][j] = Tileset.GRASS;
}
}

Room room = new Room(new Position(x, y), new Position(x + width, y + height));
}

// since adjacent rooms were added together, we may remove two rooms at once and connect them
private void connectRooms() {
while (!rooms.isEmpty()) {
Room r1 = rooms.poll();
Room r2 = rooms.poll();

// horizontally aligned
if (r1.getBottomLeft().x() == r2.getBottomLeft().x()) {
Room atBottom = Room.smallerBottomLeftY(r1, r2);
Room atTop = atBottom == r1 ? r2 : r1;
int bottomY = atBottom.getBottomLeft().y() + atBottom.getHeight() + 1;
int topY = atTop.getBottomLeft().y() - 1;
int x = atBottom.getBottomLeft().x();
for (int i = bottomY; i <= topY; i++) {
world[x][i] = Tileset.GRASS;
}
} else {
Room atLeft = Room.smallerBottomLeftX(r1, r2);
Room atRight = atLeft == r1 ? r2 : r1;

int leftX = atLeft.getBottomLeft().x() + atLeft.getWidth() + 1;
int rightY = atRight.getBottomLeft().x() - 1;

int y = atLeft.getBottomLeft().y();

for (int i = leftX; i <= rightY; i++) {
world[i][y] = Tileset.GRASS;
}
}

}
}

private void splitVertically(Position bottomLeft, Position topRight) {
int midX = (bottomLeft.x() + topRight.x()) / 2;
for (int i = bottomLeft.y(); i <= topRight.y(); i++) {
world[midX][i] = Tileset.WATER;
}
}

private void splitHorizontally(Position bottomLeft, Position topRight) {
int midY = (bottomLeft.y() + topRight.y()) / 2;
for (int i = bottomLeft.x(); i <= topRight.x(); i++) {
world[i][midY] = Tileset.WATER;
}
}

private String getRandomOrientation() {
int direction = RANDOM.nextInt(2);
switch (direction) {
case 0:
return "horizontal";
default:
return "vertical";
}
}

}


Using the BSP algorithm, I am able to generate rooms (green floor) like: (The blue walls are just for clarity and will be removed later)

I cannot figure out how to connect adjacent rooms. I tried the connectRooms() method and it does work for 2 rooms but it cannot handle further connections:

So how do I proceed with connecting the rooms?

The answer is in your question title. You are meant to assign doors just after each split(), hierarchically, not after the entire BSP process has run. OR, you can do it after the process has run, but then you need to have kept the original BSP tree (see right hand side of diagrams below), so that you can rewalk the entire tree again. I'd just do it while the tree is being created, as below,

This ensures connectedness at every level of the tree and thus solves your problem. Visualising your structure as nodes on a binary tree should help you understand. The initial state is the "root" of the tree, the second state the first two "branches", etc. Each split "replaces" the rendering of the parent room, with that of its 2 children. Yet if you maintain the underlying BSP tree structure, all those ancestors still exist.

Here is a linear example (straight tunnel maze, no forks). D are doors.

+-----------+                      0
|0          |
|           |
|           |
|           |
|           |
|           |
|           |
|           |
|           |
+-----------+


1st split

+-----------+                      0
|1          |                     / \
|           |                    1=D=2
|           |
|           |
|           |
+--------D--+
|2          |
|           |
|           |
+-----------+


2nd split, notice how 1's connection to 2 now gets delegated down to 1's children, 3 & 4:

+-----------+                      0
|3    D    4|                     / \
|     |     |                    1 D 2
|     |     |                   /|
|     |     |                  3D4
|     |     |
+-----+--D--+
|2          |
|           |
|           |
+-----------+


3rd split

+-----------+                      0
|3    D    5|                     / \
|     |     |                    1 D 2
|     +----D|                   /|
|     |     |                  3D4
|     |    6|                   /|
+-----+--D--+                  5D6
|2          |
|           |
|           |
+-----------+


4th split

+-----------+                      0
|3    D    5|                     / \
|     |     |                    1 D 2
|     +----D|                   /|   |\
|     |     |                  3D4   7D8
|     |    6|                   /|
+-----+--D--+                  5D6
|7  |      8|
|   D       |
|   |       |
+---+-------+


Step 5 shows forking. Note how this can only happen at one of the ends of the linear path (could also happen in bottom left most room 7, as that is the other end of the chain):

+-----------+                      0
|3    D    5|                     / \
|     |     |                    1 D 2
|     +----D|                   /|   |\
|D-+-D|     |               ...3D4   7D8
|9 |10|    6|               .   /|\
+--++-+--D--+               .  5D6 \
|7  |      8|               .      |\
|   D       |               ...D...9 10
|   |       |               .        .
+---+-------+               ...D......


Notice how when forking (creating 9 & 10), we pick their parent's (4's) sibling (3) and join 9 & 10 to it via Doors. Let's call this "the nephew effect". ;) Here, branches are /|\, maze forks are represented by ....

Forks mean branches in a maze sense, but I prefer the use of fork here because graph terminology has branch meaning something else (which you can already see in step 1). Note than until step 4, you could lay one straight string through the entire maze (all rooms) from start to finish. At step 5 (fork), you could not, as the end of the string would have to be in either room 9 or 10.

P.S. Note that I say fork "could only happen at the ends" - actually no, you could also fork in the middle of the linear flow, but this leads to cycles, and those can cause problems with pathfinding etc. (not always, though).

• Thank you! Could you explain what you mean by forking and how would we utilize the D's in the end structure? Aug 11 '21 at 16:23
• @GoldCredential edited at the moment you asked. ;) The tree structures at the right hand side should explain this more clearly to you. Notice how on the left (rooms), 1 & 2 for instance are no longer visible, but their descendants are. In spite of this, the original graph (BSP, right) from which we render the rooms (left) is still intact with all nodes. Aug 11 '21 at 16:24
• II think I get the idea but I feel it's very hard to implement this in my recursive algorithm :/ Aug 12 '21 at 1:18